-
-
[原创]多项式MBA原理及其在代码混淆中的应用
-
2022-3-2 10:55
-
上文《线性MBA混淆的LLVM Pass实现》介绍了线性MBA的原理和LLVM Pass实现。本文介绍如何利用可逆多项式和线性MBA表达式构造多项式MBA表达式，并用LLVM Pass实现一种简单的多项式MBA混淆。
MATH WARNING: 本文涉及少量抽象代数知识，不过基本上都是网安专业信安数学必修课中学到的内容。推荐这篇文章《代数结构入门：群、环、域、向量空间》，总结得很好。
原论文：Information Hiding in Software with Mixed Boolean-Arithmetic Transforms
0x00. 基本概念
定义在集合Z/(2^n)上的多项式集合Pm。n一般取32或者64，即系数和变量都为32位整数或64位整数的多项式：
定义集合Pm上的运算◦，◦即函数复合，例如f(x)◦g(x)=f(g(x))。集合Pm与运算◦构成一个群：
对于Pm中的多项式f(x)，一定存在一个g(x)，使得f(x)与g(x)满足f(x)◦g(x)=x或者说f(g(x))=x。g(x)可以通过以下公式来求解：
待会我们就要利用f(g(x))=x这一性质构造混淆表达式。
0x01. 多项式求逆C语言实现
多项式求逆，即随机生成一个符合条件的多项式f(x)，生成对应的逆多项式g(x)。主要就是套公式，并没有什么技术含量，不过公式有点复杂所以写起来也比较麻烦。
用到的有以下几个运算：求逆、求组合数、次方、相乘、求和、取反。这些运算都是在Z/(2^n)上的，也就是说运算结果都要模2^n。可以用flint2这个库来实现，代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 | #include "flint/fmpz_mod_poly.h"#include "flint/flint.h"#include <time.h>#include <cstdio>#include <cstdint>#include <iostream>using namespace std;int factorial(int n){ int fc=1; for(int i=1;i<=n;++i) fc *= i; return fc;}int combo(int n,int m){ return factorial(n) / (factorial(m) * factorial(n-m));}fmpz** gen_poly(int degree){ fmpz_mod_ctx ctx; fmpz n = 1LL << 32; fmpz_mod_ctx_init(&ctx, &n); fmpz_mod_poly_struct f, g; fmpz_mod_poly_init(&f, &ctx); fmpz_mod_poly_init(&g, &ctx); fmpz m = degree; fmpz *a = new fmpz[m + 1]; fmpz *b = new fmpz[m + 1]; fmpz a1_inv; fmpz *A = new fmpz[m + 1]; fmpz *A_sum = new fmpz[m + 1]; a[0] = rand(), a[1] = rand() | 1; for(int i = 2;i <= m;i ++){ a[i] = (rand() >> 16) << 16; } // Calculate a1_inv fmpz_mod_inv(&a1_inv, a + 1, &ctx); // Calculate A fmpz_mod_pow_ui(A + m, &a1_inv, m, &ctx); fmpz_mod_neg(A + m, A + m, &ctx); fmpz_mod_mul(A + m, A + m, a + m, &ctx); for(int k = m - 1; k >= 0;k --){ fmpz sum = 0; for(int j = k + 1;j <= m;j ++){ fmpz tmp; fmpz_mod_pow_ui(&tmp, a, j - k, &ctx); fmpz_mod_mul(&tmp, &tmp, A + j, &ctx); fmpz_mod_mul_ui(&tmp, &tmp, combo(j, k), &ctx); fmpz_mod_add(&sum, &sum, &tmp, &ctx); } fmpz_mod_pow_ui(A + k, &a1_inv, k, &ctx); fmpz_mod_mul(A + k, A + k, a + k, &ctx); fmpz_mod_neg(A + k, A + k, &ctx); fmpz_mod_sub(A + k, A + k, &sum, &ctx); A_sum[k] = sum; } // Calculate bm fmpz_mod_pow_ui(b + m, &a1_inv, m + 1, &ctx); fmpz_mod_neg(b + m, b + m, &ctx); fmpz_mod_mul(b + m, b + m, a + m, &ctx); // Calculate bk for(int k = 2;k < m;k ++){ fmpz_mod_pow_ui(b + k, &a1_inv, k + 1, &ctx); fmpz_mod_mul(b + k, b + k, a + k, &ctx); fmpz_mod_neg(b + k, b + k, &ctx); fmpz tmp; fmpz_mod_mul(&tmp, &a1_inv, A_sum + k, &ctx); fmpz_mod_sub(b + k, b + k, &tmp, &ctx); } // Calculate b1 fmpz sum = 0; for(int j = 2;j <= m;j ++){ fmpz tmp; fmpz_mod_pow_ui(&tmp, a, j - 1, &ctx); fmpz_mod_mul(&tmp, &tmp, A + j, &ctx); fmpz_mod_mul_ui(&tmp, &tmp, j, &ctx); fmpz_mod_add(&sum, &sum, &tmp, &ctx); } fmpz_mod_mul(&sum, &sum, &a1_inv, &ctx); fmpz_mod_sub(b + 1, &a1_inv, &sum, &ctx); // Calculate b0 b[0] = 0; for(int j = 1;j <= m;j ++){ fmpz tmp; fmpz_mod_pow_ui(&tmp, a, j, &ctx); fmpz_mod_mul(&tmp, &tmp, b + j, &ctx); fmpz_mod_add(b, b, &tmp, &ctx); } fmpz_mod_neg(b, b, &ctx); fmpz **coeff = new fmpz*[2]; coeff[0] = a, coeff[1] = b; delete[] A; delete[] A_sum; return coeff;}int main(){ int degree = 10; srand(time(NULL)); fmpz** coeff = gen_poly(degree); fmpz_mod_ctx ctx; fmpz n = 1LL << 32; fmpz_mod_ctx_init(&ctx, &n); fmpz_mod_poly_struct f, g, res; fmpz_mod_poly_init(&f, &ctx); fmpz_mod_poly_init(&g, &ctx); fmpz_mod_poly_init(&res, &ctx); for(int i = 0;i <= degree;i ++){ fmpz_mod_poly_set_coeff_ui(&f, i, coeff[0][i], &ctx); fmpz_mod_poly_set_coeff_ui(&g, i, coeff[1][i], &ctx); } fmpz_mod_poly_compose(&res, &g, &f, &ctx); flint_printf("f(x) = "); fmpz_mod_poly_print_pretty(&f, "x", &ctx); flint_printf("\n"); flint_printf("g(x) = "); fmpz_mod_poly_print_pretty(&g, "x", &ctx); flint_printf("\n"); flint_printf("g(f(x)) = "); fmpz_mod_poly_print_pretty(&res, "x", &ctx); flint_printf("\n");} |
运行结果：
1 2 3 | f(x) = 1756102656*x^10+947978240*x^9+368902144*x^8+1950089216*x^7+497156096*x^6+1583087616*x^5+178454528*x^4+202440704*x^3+932052992*x^2+421111353*x+593005452g(x) = 2268332032*x^10+395247616*x^9+2160525312*x^8+2187591680*x^7+3999137792*x^6+833880064*x^5+806682624*x^4+1138688000*x^3+2095448064*x^2+3762448393*x+1736062996g(f(x)) = x |
flint2的整数（fmpz）是用signed long实现的，也就是说Z/(2^n)的n不能取64，因为2^64无法用signed long表示出来，所以这里选取的n是32：
1 2 3 | fmpz_mod_ctx ctx;fmpz n = 1LL << 32;fmpz_mod_ctx_init(&ctx, &n); |
如果只要生成degree为1，也就是f(x)和g(x)都为ax+b这种形式的式子，公式会简单很多，并且可以只用z3实现（安装flint2实在太麻烦了）。度数为1（即x的最高次方为1）的多项式求逆C语言代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 | #include "flint/fmpz_mod_poly.h"#include "flint/flint.h"#include "z3++.h"#include <time.h>#include <cstdio>#include <cstdint>#include <iostream>using namespace std;using namespace z3;uint64_t inverse(uint64_t n){ context c; solver s(c); expr a = c.bv_val(n, 64); expr a_inv = c.bv_const("a_inv", 64); s.add(a * a_inv == 1); s.check(); model m = s.get_model(); return m.eval(a_inv).get_numeral_uint64();}void gen_univariate_poly(uint64_t *a, uint64_t *b){ uint64_t a0, a1, b0, b1, a1_inv; a0 = ((uint64_t)rand() << 32) | rand(), a1 = ((uint64_t)rand() << 32LL) | (rand() | 1); // Calculate a1_inv a1_inv = inverse(a1); // Calculate b1 b1 = a1_inv; // Calculate b0 b0 = -(b1 * a0); uint64_t **coeff = new uint64_t*[2]; a[0] = a0, a[1] = a1, b[0] = b0, b[1] = b1;} |
使用度数为1的多项式有几个好处，一是代码实现简单，二是用z3实现可以拓展到64位，三是混淆后对程序大小和速度的影响相对来说比较小。所以接下来的混淆只会用度数为1的多项式。
0x02. 混淆思路
虽然原论文提供了几种混淆思路，但我个人感觉都不太好用。后来我采用了这里提到的方法：
这里举了一个对x+y进行混淆的例子，大概的思路就是：
- 生成一对互逆的一次多项式f(x)和g(x)
- 构造与
x+y等价的线性MBA表达式E2=(x^y)+2*(x&y)（关于什么是线性MBA表达式见我的上一篇文章） - 构造E3=g(f(E2))，由之前提到过的性质，g(f(E2))实际上就等于E2
- 用等价但更复杂E3表达式替代原
x+y表达式
0x03. LLVM Pass实现
线性MBA混淆的LLVM Pass实现也在上一篇文章提到过了，现在要介绍的多项式MBA混淆基于线性MBA混淆。
Github：
MBAObfuscation.cpp
MBAUtils.cpp
首先是把求逆多项式的代码移植一下，跟之前区别不大：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | uint64_t inverse(uint64_t n, uint32_t bitWidth){ context c; solver s(c); expr a = c.bv_val(n, bitWidth); expr a_inv = c.bv_const("a_inv", bitWidth); s.add(a * a_inv == 1); s.add(a_inv != 0); s.check(); model m = s.get_model(); return m.eval(a_inv).get_numeral_uint64();}void generateUnivariatePoly(uint64_t *a, uint64_t *b, uint32_t bitWidth){ uint64_t a0, a1, b0, b1, a1_inv; a0 = cryptoutils->get_uint64_t(), a1 = cryptoutils->get_uint64_t() | 1; // Calculate a1_inv a1_inv = inverse(a1, bitWidth); // Calculate b1 b1 = a1_inv; // Calculate b0 b0 = -(b1 * a0); a[0] = a0, a[1] = a1, b[0] = b0, b[1] = b1;} |
然后按照上述混淆思路，在线性MBA表达式的基础上插入多项式MBA混淆，代码如下，还是比较好理解的：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | Value* llvm::insertPolynomialMBA(Value *linearMBAExpr, BinaryOperator *insertBefore){ IRBuilder<> builder(insertBefore->getContext()); builder.SetInsertPoint(insertBefore); Type *operandType = insertBefore->getOperand(0)->getType(); uint32_t bitWidth = operandType->getIntegerBitWidth(); uint64_t a[2], b[2]; generateUnivariatePoly(a, b, bitWidth); Value *expr; expr = builder.CreateMul(ConstantInt::get(operandType, b[1]), linearMBAExpr); expr = builder.CreateAdd(expr, ConstantInt::get(operandType, b[0])); expr = builder.CreateMul(ConstantInt::get(operandType, a[1]), expr); expr = builder.CreateAdd(expr, ConstantInt::get(operandType, a[0])); return expr;} |
对加法进行替换的代码修改如下，其他的运算同理：
1 2 3 4 5 6 7 | void MBAObfuscation::substituteAdd(BinaryOperator *BI){ int64_t *terms = generateLinearMBA(TermsNumber); terms[2] += 1; terms[4] += 1; Value *mbaExpr = insertPolynomialMBA(insertLinearMBA(terms, BI), BI); BI->replaceAllUsesWith(mbaExpr);} |
0x04. 混淆效果
源代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | #include <cstdio>#include <cstring>#include <cstdlib>char *input;char enc[100] = "\x86\x8a\x7d\x87\x93\x8b\x4d\x81\x80\x8a\\x43\x7f\x49\x49\x86\x71\x7f\x62\x53\x69\x28\x9d"; void encrypt(unsigned char *dest, char *src){ int len = strlen(src); for(int i = 0;i < len;i ++){ dest[i] = (src[i] + (32 - i)) ^ i; } }//flag{s1mpl3_11vm_d3m0} int main(int argc, char *argv[]){ printf("Welcome to LLVM world...\n"); if(argc <= 1){ printf("Input your flag as an argument.\n"); return 0; } input = argv[1]; printf("Your flag is: %s\n", input); unsigned char dest[100] = {0}; encrypt(dest, input); bool result = strlen(input) == 22 && !memcmp(dest, enc, 22); if(result){ printf("Congratulations~\n"); }else{ printf("Sorry try again.\n"); }} |
混淆后：
[CTF入门培训]顶尖高校博士及硕士团队亲授《30小时教你玩转CTF》，视频+靶场+题目！助力进入CTF世界
|
|
|---|---|
|
|
|
|
|
|
|
|
我也是拖了好久才去看。。。老懒狗了 |
|
|
|
|
|
我一年前看到过这篇论文，那会英文太菜，没看懂
 。感谢楼主这篇文章让我明白了这篇文章在干啥
|
|
|
哇，是大佬 |
|
|
别别别，我老菜了 老哥能恰个v吗？我v私你了。混淆在学界是非常边缘的研究方向了，同行太少了
|
|
|
混淆不是边缘的研究方向吧？ c# java js那些 都是混淆为主 vm为辅。难道vm为主了？ |
|
|
加了 |
|
|
学术界是把VM算入代码混淆的。混淆近几年的发文量很少了，而且已经没有大牛课题组的参与这个研究方向了。现在混淆更像是学术圈的小圈子自嗨了，比如CEA LIST的那个组，和ASU的几个组。 |
|
|
有没有什么讨论群。留个方式 加一个。其实我对这个还比较感兴趣。不过现在没什么时间研究罗。 |
|
|
没，之前有个群，但是解散了。你有兴趣可以关注下学术界的会议像acsac, dsn, usenix, oakland, ccs, ndss。但是咋说呢，学术界最近的进展比较小，acsac2021有一篇做的是修改abi约定（vtable顺序啥的），dsn2021有一篇做的是用rop做混淆，我个人觉得这些工作都不是很好，不算什么好结果。ccs2021, blackhat2021做的是用program synthesis做反混淆，但是这还属于起步期，他们合成出的表达式基本上都只有2个输入，还不算太可用吧。我个人认为学术界可能出现的好突破应该是不可区分混淆，应该属于密码学研究的范畴 |
|
|
进展小才好，跟不上大佬了
|
天水姜伯约
