多項式MBA原理及其在代碼混淆中的應用
VSole2022-04-04 16:45:35
本文介紹如何利用可逆多項式和線性MBA表達式構造多項式MBA表達式，并用LLVM Pass實現一種簡單的多項式MBA混淆。
MATH WARNING: 本文涉及少量抽象代數知識，基本上都是網安專業信安數學必修課中學到的內容。推薦這篇文章《代數結構入門：群、環、域、向量空間》（https://zhuanlan.zhihu.com/p/21583674），總結得很好。
原論文：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這一性質構造混淆表達式。
多項式求逆C語言實現
多項式求逆，即隨機生成一個符合條件的多項式f(x)，生成對應的逆多項式g(x)。主要就是套公式，并沒有什么技術含量，不過公式有點復雜所以寫起來也比較麻煩。
用到的有以下幾個運算：求逆、求組合數、次方、相乘、求和、取反。這些運算都是在Z/(2^n)上的，也就是說運算結果都要模2^n。可以用flint2這個庫來實現，代碼如下：
#include "flint/fmpz_mod_poly.h"#include "flint/flint.h"#include #include #include #include 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(""); flint_printf("g(x) = "); fmpz_mod_poly_print_pretty(&g, "x", &ctx); flint_printf(""); flint_printf("g(f(x)) = "); fmpz_mod_poly_print_pretty(&res, "x", &ctx); flint_printf("");}
運行結果：
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：
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 #include #include #include 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的多項式。
混淆思路
雖然原論文提供了幾種混淆思路，但我個人感覺都不太好用。后來我采用了這里提到的方法：
這里舉了一個對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表達式
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);}
混淆效果
源代碼：
#include #include #include 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..."); if(argc <= 1){ printf("Input your flag as an argument."); return 0; } input = argv[1]; printf("Your flag is: %s", input); unsigned char dest[100] = {0}; encrypt(dest, input); bool result = strlen(input) == 22 && !memcmp(dest, enc, 22); if(result){ printf("Congratulations~"); }else{ printf("Sorry try again."); }}
混淆后：
VSole
網絡安全專家