-
-
[原创]多项式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
定义在集合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这一性质构造混淆表达式。
多项式求逆，即随机生成一个符合条件的多项式f(x)，生成对应的逆多项式g(x)。主要就是套公式，并没有什么技术含量，不过公式有点复杂所以写起来也比较麻烦。
用到的有以下几个运算：求逆、求组合数、次方、相乘、求和、取反。这些运算都是在Z/(2^n)上的，也就是说运算结果都要模2^n。可以用flint2这个库来实现，代码如下：
运行结果：
flint2的整数（fmpz）是用signed long实现的，也就是说Z/(2^n)的n不能取64，因为2^64无法用signed long表示出来，所以这里选取的n是32：
如果只要生成degree为1，也就是f(x)和g(x)都为ax+b这种形式的式子，公式会简单很多，并且可以只用z3实现（安装flint2实在太麻烦了）。度数为1（即x的最高次方为1）的多项式求逆C语言代码如下：
使用度数为1的多项式有几个好处，一是代码实现简单，二是用z3实现可以拓展到64位，三是混淆后对程序大小和速度的影响相对来说比较小。所以接下来的混淆只会用度数为1的多项式。
虽然原论文提供了几种混淆思路，但我个人感觉都不太好用。后来我采用了这里提到的方法：
这里举了一个对x+y进行混淆的例子，大概的思路就是：
线性MBA混淆的LLVM Pass实现也在上一篇文章提到过了，现在要介绍的多项式MBA混淆基于线性MBA混淆。
Github：
MBAObfuscation.cpp
MBAUtils.cpp
首先是把求逆多项式的代码移植一下，跟之前区别不大：
然后按照上述混淆思路，在线性MBA表达式的基础上插入多项式MBA混淆，代码如下，还是比较好理解的：
对加法进行替换的代码修改如下，其他的运算同理：
源代码：
混淆后：
#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");
}#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");
}[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课
|
|
|---|---|
|
|
|
|
|
|
|
|
我也是拖了好久才去看。。。老懒狗了 |
|
|
|
|
|
我一年前看到过这篇论文，那会英文太菜，没看懂
 。感谢楼主这篇文章让我明白了这篇文章在干啥
|
|
|
哇，是大佬 |
|
|
别别别，我老菜了 老哥能恰个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个输入，还不算太可用吧。我个人认为学术界可能出现的好突破应该是不可区分混淆，应该属于密码学研究的范畴 |
|
|
进展小才好，跟不上大佬了
|
天水姜伯约
