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

本文为看雪论坛优秀文章
看雪论坛作者ID：34r7hm4n

本文介绍如何利用可逆多项式和线性MBA表达式构造多项式MBA表达式，并用LLVM Pass实现一种简单的多项式MBA混淆。

MATH WARNING: 本文涉及少量抽象代数知识，基本上都是网安专业信安数学必修课中学到的内容。推荐这篇文章《代数结构入门：群、环、域、向量空间》（https://zhuanlan.zhihu.com/p/21583674），总结得很好。

原论文：Information Hiding in Software with Mixed Boolean-Arithmetic Transforms

1

基本概念

定义在集合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这一性质构造混淆表达式。

2

多项式求逆C语言实现

多项式求逆，即随机生成一个符合条件的多项式f(x)，生成对应的逆多项式g(x)。主要就是套公式，并没有什么技术含量，不过公式有点复杂所以写起来也比较麻烦。

用到的有以下几个运算：求逆、求组合数、次方、相乘、求和、取反。这些运算都是在Z/(2^n)上的，也就是说运算结果都要模2^n。可以用flint2这个库来实现，代码如下：

#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");
}

运行结果：

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：

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语言代码如下：

#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的多项式。

3

混淆思路

虽然原论文提供了几种混淆思路，但我个人感觉都不太好用。后来我采用了这里提到的方法：

这里举了一个对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表达式

4

LLVM Pass实现

线性MBA混淆的LLVM Pass实现也在上一篇文章提到过了，现在要介绍的多项式MBA混淆基于线性MBA混淆。
Github：
MBAObfuscation.cpp
MBAUtils.cpp

首先是把求逆多项式的代码移植一下，跟之前区别不大：

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混淆，代码如下，还是比较好理解的：

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;
}

对加法进行替换的代码修改如下，其他的运算同理：

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);
}

5

混淆效果

源代码：

#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");
    }
}

混淆后：

看雪ID：34r7hm4n

https://bbs.pediy.com/user-home-910514.htm

*本文由看雪论坛 34r7hm4n 原创，转载请注明来自看雪社区

# 往期推荐

球分享

球点赞

球在看

点击“阅读原文”，了解更多！