[论文笔记]Information Hiding in Software with Mixed Boolean-Arithmetic Transforms

今年9月腾讯tctf出了一道MBA混淆题,仅有1解。前些天又在看雪刷到了有关MBA算法的帖子,激起了我的兴趣,于是去读了一下提出MBA算法的论文 Information Hiding in Software with Mixed Boolean-Arithmetic Transforms,这篇博客简单记录了论文中的关键内容。

混合布尔算术(Mixed Boolean-Arithmetic, MBA)是2007年提出的一种混淆算法,这种算法由算数运算(例如ADD、SUB、MUL)和布尔运算(例如AND、OR、NOT)的混合使用组成。针对MBA的去混淆研究在长时间内都处于起步阶段,直到今年的一篇顶会论文MBA-Blast: Unveiling and Simplifying Mixed Boolean-Arithmetic Obfuscation才提出了完美的去混淆方案。

论文信息

title: Information Hiding in Software with Mixed Boolean-Arithmetic Transforms

author: Yongxin Zhou, Alec Main, Yuan X. Gu, and Harold Johnson Cloakware Inc., USA

publisher: Springer

year: 2007

url: https://link.springer.com/chapter/10.1007/978-3-540-77535-5_5

download: http://blog.bluesadi.cn/download/pdf/Information Hiding in Software with Mixed Boolean-Arithmetic Transforms.pdf

1 Introduction

Introduction部分讲了一下本篇论文的主要内容:介绍了一种名为 Boolean-arithmetic (BA) algebras 的代数系统,即混合布尔算术。基于这个代数系统,可以构造出复杂的MBA表达式来替代常量以及基本运算(加减乘除、异或等),并且化简MBA表达式是 NP-hard 的。

从Introduction中可以看出本篇论文涉及大量数学内容(主要是数论和线性代数,尤其是数论)。

2 Motivating Scenarios

Motivating Scenarios部分介绍了三种软件保护场景,如下图所示。在场景A中,常量CC和算法Algorithm Code均未受到保护,因此很容易进行逆向分析;在场景B中常量CC通过一段固定的代码生成,可以在一定程度上抵抗静态分析,但无法抵抗动态调试;在场景C中常量CC不再以出现在运算过程中,而是以变换后的形式CTC^T出现,同时需要对Algorithm Code进行变换,使得使用相同的输入和变换后的常量CTC^T能得到与场景A和场景B相同的输出:

image-20211211233124311

攻击者可以通过动态调试得到变换后的秘密常量CTC^T,但要想得到原先的常量C则需要第变换后的Algorithm Code进行逆向,分析出变换TT,进而对CTC^T进行换源。如果将MBA混淆应用于Algorithm Code,那么得到秘密常量CC将变得非常困难。最后还介绍了MBA混淆对软件水印算法的保护作用。这一部分应该是介绍了MBA混淆的应用场景。

3 Mixed Boolean-Arithmetic (MBA) Transforms

从这里开始正式介绍MBA混淆算法,也是全文最关键的部分。该部分涉及大量数论和线性代数内容,基本都是信安数学和线性代数这两门课的内容,不记得的同学可以自行复习一下。

3.1 Basic Definitions

Boolean-arithmetic algebra (BA-algebra), BA[n]是一个代数系统,其定义如下:

image-20211211234901789

其中BnB_n表示所有nn位二进制数的集合(其中nn为正整数),后面的所有运算都是建立在集合BnB_n上的运算,上标有s^s符号数的运算,否则为无符号数。

多项式MBA表达式的形式如下,其中aia^i是常量,ei,je_{i,j}是由x1,...,xtx_1, ..., x_t变量组成的按位运算表达式:

image-20211212094027384

线性MBA是多项式MBA的简化版,其形式如下:

image-20211212094923884

以下是多项式MBA和线性MBA的实例,其中第一个是多项式MBA,第二个是线性MBA:
image-20211212095034438

用MBA表达式可以对一些基本运算进行替换,例如x<syx<^sy成立当且仅当下面这个MBA表达式的最高有效位(MSB)为1:

image-20211212095243466

3.2 Linear MBA Identities and Expressions

这一部分主要介绍了构造线性MBA恒等式的原理和方法。

Theorem 1 与构造线性MBA恒等式的方法有关。首先构造了一个MBA表达式:n,s,tn,s,t为正整数,xix_iBnB^n上的变量,其中i=1,...,ti=1,...,teje_j为由xix_i组成的按位运算表达式,其中j=0,...,s1j=0,...,s-1,构造出线性MBA表达式如下:

e=j=0s1ajeje=\sum_{j=0}^{s-1}a_je_j

接着令(v0,j,...,vi,j,...,...,v2t1,j)T(v_{0,j},...,v_{i,j},...,...,v_{2^t-1,j})^Teje_j的真值表列,其中j=0,...,s1j=0,...,s-1,构造出e0,...,es1e_0,...,e_{s-1}的真值表矩阵:

A=(vi,j)2t×sA=(v_{i,j})_{2^t \times s}

有如下定理:e=0e=0当且仅当AY=0AY=0Z/(2n)Z/(2^n)上有解,其中Ys×1=(a0,...,as1)TY_{s\times 1}=(a_0,...,a_{s-1})^T,证明过程略,可以从直观上理解。

通过上述定理我们可以通过真值表矩阵来生成MBA恒等式,举个例子:

首先选取几个布尔表达式f0(x,y)=x,f1(x,y)=y,f2(x,y)=xy,f3(x,y)=¬(xy),f4(x,y)=1f_0(x,y)=x,f_1(x,y)=y,f_2(x,y)=x\lor y,f_3(x,y)=\lnot(x\land y),f_4(x,y)=-1,(选择1-1的原因是1-1在补码表示中的任何位都是11)构造出真值表矩阵:

A=(00011011111011111101)A= \left( %左括号 \begin{array}{ccccc} 0 & 0 & 0 & 1 & 1\\ 0 & 1 & 1 & 1 & 1\\ 1 & 0 & 1 & 1 & 1\\ 1 & 1 & 1 & 0 & 1\\ \end{array} \right) %右括号

AY=0AY=0求解出Y=(1,1,1,1,1)TY=(1,1,-1,1,-1)^T,进而构造出MBA恒等式,此时我们就得到了x+yx+y的一种替换方案,以达到混淆的目的:

x+y(xy)+(¬(xy))(1)=0    x+y=(xy)(¬(xy))1x+y-(x \lor y)+(\lnot(x \land y))-(-1)=0 \iff x+y=(x \lor y)-(\lnot(x \land y))-1

Theorem 2 证明了对任意一个真值表列AjA_j,都有唯一的布尔表达式eje_j与之对应。

3.3 Permutation Polynomials and Other Invertible Functions

Theorem 3 定义了一种运算\circg(x)f(x)=g(f(x))g(x)\circ f(x)=g(f(x))。证明了对任意f(x)Pm(Z/(2n))f(x)\in P_m(Z/(2^n)),存在g(x)Pm(Z/(2n))g(x)\in P_m(Z/(2^n))使得g(f(x))=xg(f(x))=xPmP_m的定义如下:

image-20211212210616708

g(x)g(x)的公式如下:

image-20211212210720595

image-20211212210647910

3.4 Code Transforms Via Zero and Invertible MBA Functions

介绍了两种混淆数据和代码的方法,第一种方法:

tk=(i=1k1ti+i=k+1nti)t_k=-(\sum_{i=1}^{k-1}t_i+\sum_{i=k+1}^nt_i)

第二种方法运用了多项式MBA的特性,例如将ff转换为S1SfTT1S^{-1}\circ S\circ f\circ T \circ T^{-1},其中SfTS\circ f\circ T可以用第一种方法进行替代。

还介绍了一种名为interlocking技术,没太明白是什么意思。

推论:BA[n]BA[n]中的所有运算都可以表示为多项式MBA表达式。

image-20211212224509056

4 Protection Methods

4.1 Simple Constant Hiding Using MBA Transforms

提出了一种非常巧妙的利用线性MBA和多项式MBA构造常量替换的方法,其中i=1raiei=0\sum_{i=1}^ra_ie_i=0

K=q(p(K))=q(i=1raiei+p(K))K=q(p(K))=q(\sum_{i=1}^ra_ie_i+p(K))

4.2 Algorithm and Data Hiding Example: Software Watermarking

略过

5 Security of MBA Transforms

安全性证明:经测试MathematicaTM,MapleTMMathematica^{TM}, Maple^{TM}均无法化简大多数MBA表达式。并且以下问题是 NP-hard 的:

image-20211212232302743

没太看明白。

6 Conclusion

略过