首页
论坛
课程
招聘
[原创]多项式MBA原理及其在代码混淆中的应用
2022-3-2 10:55 8925

[原创]多项式MBA原理及其在代码混淆中的应用

2022-3-2 10:55
8925

上文《线性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+593005452
g(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+1736062996
g(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进行混淆的例子,大概的思路就是:

  1. 生成一对互逆的一次多项式f(x)和g(x)
  2. 构造与x+y等价的线性MBA表达式E2=(x^y)+2*(x&y)(关于什么是线性MBA表达式见我的上一篇文章)
  3. 构造E3=g(f(E2)),由之前提到过的性质,g(f(E2))实际上就等于E2
  4. 用等价但更复杂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");
    }
}

混淆后:
图片描述


看雪招聘平台创建简历并且简历完整度达到90%及以上可获得500看雪币~

收藏
点赞8
打赏
分享
打赏 + 55.00雪花
打赏次数 2 雪花 + 55.00
 
赞赏  Editor   +50.00 2022/04/06 恭喜您获得“雪花”奖励,安全圈有你而精彩!
赞赏  orz1ruo   +5.00 2022/03/03 原创内容~
最新回复 (13)
雪    币: 4694
活跃值: 活跃值 (4694)
能力值: ( LV17,RANK:787 )
在线值:
发帖
回帖
粉丝
无名侠 活跃值 12 2022-3-2 23:17
2
0
太卷了,我tctf之后看了这篇论文一直想试试,结果咕咕到现在也没开始,学习!!
雪    币: 70
活跃值: 活跃值 (638)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
hixhi 活跃值 2022-3-3 11:37
3
0
太卷了,本来不用去这么搞数学的。。。
雪    币: 12476
活跃值: 活跃值 (7739)
能力值: ( LV12,RANK:360 )
在线值:
发帖
回帖
粉丝
34r7hm4n 活跃值 7 2022-3-3 12:57
4
0
无名侠 太卷了,我tctf之后看了这篇论文一直想试试,结果咕咕到现在也没开始,学习!!
我也是拖了好久才去看。。。老懒狗了
雪    币: 2690
活跃值: 活跃值 (1850)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
caolinkai 活跃值 2022-3-3 14:54
5
0
厉害了
雪    币: 4712
活跃值: 活跃值 (2306)
能力值: ( LV9,RANK:195 )
在线值:
发帖
回帖
粉丝
天水姜伯约 活跃值 4 2022-3-14 22:27
6
0
我一年前看到过这篇论文,那会英文太菜,没看懂。感谢楼主这篇文章让我明白了这篇文章在干啥
雪    币: 12476
活跃值: 活跃值 (7739)
能力值: ( LV12,RANK:360 )
在线值:
发帖
回帖
粉丝
34r7hm4n 活跃值 7 2022-3-14 22:48
7
0
天水姜伯约 我一年前看到过这篇论文,那会英文太菜,没看懂[em_85]。感谢楼主这篇文章让我明白了这篇文章在干啥
哇,是大佬
雪    币: 4712
活跃值: 活跃值 (2306)
能力值: ( LV9,RANK:195 )
在线值:
发帖
回帖
粉丝
天水姜伯约 活跃值 4 2022-3-14 23:23
8
0
34r7hm4n 哇,是大佬
别别别,我老菜了老哥能恰个v吗?我v私你了。混淆在学界是非常边缘的研究方向了,同行太少了
雪    币: 2872
活跃值: 活跃值 (1690)
能力值: ( LV13,RANK:240 )
在线值:
发帖
回帖
粉丝
IamHuskar 活跃值 4 2022-3-15 08:05
9
0
天水姜伯约 别别别,我老菜了[em_85]老哥能恰个v吗?我v私你了。混淆在学界是非常边缘的研究方向了,同行太少了
混淆不是边缘的研究方向吧? c# java js那些 都是混淆为主 vm为辅。难道vm为主了?
雪    币: 12476
活跃值: 活跃值 (7739)
能力值: ( LV12,RANK:360 )
在线值:
发帖
回帖
粉丝
34r7hm4n 活跃值 7 2022-3-15 09:05
10
0
天水姜伯约 别别别,我老菜了[em_85]老哥能恰个v吗?我v私你了。混淆在学界是非常边缘的研究方向了,同行太少了
加了
雪    币: 4712
活跃值: 活跃值 (2306)
能力值: ( LV9,RANK:195 )
在线值:
发帖
回帖
粉丝
天水姜伯约 活跃值 4 2022-3-15 10:33
11
0
IamHuskar 混淆不是边缘的研究方向吧? c# java js那些 都是混淆为主 vm为辅。难道vm为主了?
学术界是把VM算入代码混淆的。混淆近几年的发文量很少了,而且已经没有大牛课题组的参与这个研究方向了。现在混淆更像是学术圈的小圈子自嗨了,比如CEA LIST的那个组,和ASU的几个组。
雪    币: 2872
活跃值: 活跃值 (1690)
能力值: ( LV13,RANK:240 )
在线值:
发帖
回帖
粉丝
IamHuskar 活跃值 4 2022-3-22 12:49
12
0
天水姜伯约 学术界是把VM算入代码混淆的。混淆近几年的发文量很少了,而且已经没有大牛课题组的参与这个研究方向了。现在混淆更像是学术圈的小圈子自嗨了,比如CEA LIST的那个组,和ASU的几个组。
有没有什么讨论群。留个方式 加一个。其实我对这个还比较感兴趣。不过现在没什么时间研究罗。
雪    币: 4712
活跃值: 活跃值 (2306)
能力值: ( LV9,RANK:195 )
在线值:
发帖
回帖
粉丝
天水姜伯约 活跃值 4 2022-3-27 11:54
13
0
IamHuskar 有没有什么讨论群。留个方式 加一个。其实我对这个还比较感兴趣。不过现在没什么时间研究罗。
没,之前有个群,但是解散了。你有兴趣可以关注下学术界的会议像acsac, dsn, usenix, oakland, ccs, ndss。但是咋说呢,学术界最近的进展比较小,acsac2021有一篇做的是修改abi约定(vtable顺序啥的),dsn2021有一篇做的是用rop做混淆,我个人觉得这些工作都不是很好,不算什么好结果。ccs2021, blackhat2021做的是用program synthesis做反混淆,但是这还属于起步期,他们合成出的表达式基本上都只有2个输入,还不算太可用吧。我个人认为学术界可能出现的好突破应该是不可区分混淆,应该属于密码学研究的范畴
雪    币: 9
活跃值: 活跃值 (460)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
bullyxy 活跃值 2022-3-29 09:49
14
0
天水姜伯约 没,之前有个群,但是解散了。你有兴趣可以关注下学术界的会议像acsac, dsn, usenix, oakland, ccs, ndss。但是咋说呢,学术界最近的进展比较小,acsac2021有一篇做 ...
进展小才好,跟不上大佬了
游客
登录 | 注册 方可回帖
返回