一種基于分支條件混淆的代碼加密技術

耿 普 祝躍飛

(戰略支援部隊信息工程大學 鄭州 450002)

代碼加密[1-7]和代碼混淆都是重要的代碼保護技術，傳統的代碼加密技術在加密代碼的粒度上越來越細，從文件、程序節區粒度到函數[7-8]、基本塊粒度，甚至到單個機器指令[5]的粒度；另外在解密函數上也引入了多態[4]的方法，加密代碼每次解密執行后的再次加密會通過秘鑰變化和解密函數變化來增加逆向分析的難度；但是在隱藏解密秘鑰方面還缺少相關研究.分支條件混淆[9-13]是代碼混淆[14]研究的一個新方向，通過混淆分支條件，能夠隱藏程序執行邏輯、對抗符號執行[11,15-16]，特別是在對觸發條件的保護上具有較好的效果，能夠阻礙生成滿足觸發條件的程序輸入.

雖然分支條件混淆能夠保護程序的觸發條件，但是無法保護基于觸發條件的程序代碼.于是Sharif等人[9]結合分支條件混淆和代碼加密，提出了一種基于分支條件混淆的條件代碼加密技術，使用滿足分支條件的輸入作為代碼加解密秘鑰對條件代碼進行加密，因此在程序內存中不需要存儲秘鑰，而是在運行時直接獲取分支條件的輸入作為秘鑰；另外由于混淆使得逆向分析者難以獲取滿足分支條件的輸入，也就無法獲取加解密秘鑰，因此結合分支條件混淆的代碼加密實現了解密秘鑰的隱藏.然而該分支混淆方法均只能應用于等于條件；另外，受限于解密秘鑰唯一性要求，基于分支條件混淆的代碼加密技術只能應用于單個等于條件的分支；這些限制極大阻礙了基于分支條件混淆的代碼加密技術的應用.

王志等人[11]在Sharif[9]分支條件混淆方法的基礎上，提出了一種基于保留前綴加密的分支混淆技術，把分支條件混淆從等于判斷的條件擴展到大小判斷的條件.然而在非等條件下，分支條件為真的輸入不具備唯一性要求，因此不能使用分支輸入作為秘鑰對條件代碼進行加密.在分支條件取值為真的輸入不唯一的條件下，為解決使用分支輸入產生唯一性秘鑰的要求，在多輸入分支條件下，結合分支條件混淆，本文提出了一種基于拉格朗日插值法的秘鑰生成技術，實現了解密秘鑰和分支條件混淆的結合，隱藏了代碼解密秘鑰.

本文的主要貢獻有4個方面：

1) 基于拉格朗日插值法，在分支條件取值為真的輸入不唯一的條件下，提出了一種使用分支條件輸入生成代碼加解密秘鑰的方法；

2) 通過對多個等于條件取或形成的復合條件的分支輸入進行處理，完成了多輸入條件下的秘鑰生成，實現條件代碼加密，避免了代碼復制和復合條件拆分帶來的空間損耗；

3) 完成了基于分支混淆的條件代碼加密方法從等于條件分支到區間條件分支的擴展;

4) 針對等于條件和區間條件通過邏輯運行形成的復雜條件，實現了分支混淆和復雜條件代碼加密的結合，實現了復雜條件分支下的基于分支混淆的代碼加密.

1 基礎知識

1.1 前綴算法

前綴算法是一種把一個整數區間轉變為一個前綴集合的算法，并且保證區間中的每一個整數均在前綴集合能找到一個與之匹配的前綴，反之在集合中沒有匹配到前綴的整數一定不屬于該區間.并且前綴算法得到的前綴集合元素個數有2個特點，其中n表示整數的二進制位數：

1) 區間前綴集合元素個數最大值為2n-2;

2) 區間前綴集合元素個數平均值為((n-2)×22n-1+(n+1)2n+1)(22n-1+2n-1)，在32 b或者64 b程序中，該值都接近為n-2.

前綴算法偽代碼如算法1所示：

算法1.一個整數區間到前綴集合的轉換算法.

輸入:區間起始值的二進制表示a1a2…an;區間結束值的二進制表示b1b2…bn;

輸出:區間的前綴集合Prefix.

PrefixSearch_Prefix(a1a2…an，b1b2…bn)

{

for (intk=1;(k≤n) && (ak=bk);

k++)

if (k=n+1)

return {a1a2…an};

endif

endfor

if((akak+1…an=00…0) && (bkbk+1…bn=11…1))

if (k=1)

return {*};

else

return{a1a2…ak-1};

endif

endif

PrefixA=Search_Prefix(ak+1ak+2…an,11…1);

PrefixB=Search_Prefix(00…0,bk+1bk+2…bn)

return{a1a2…ak-10+PrefixA,a1a2…ak-11+PrefixB};

}

1.2 保留前綴Hash加密

保留前綴加密[17].假設a=a1a2…an，b=b1b2…bn為2個n位整數，如果a1a2…ak=b1b2…bk，其中k

標準形式定理(canonical form theorem)[17].假設fi是一個從{0,1}i到{0,1}上的函數，其中i=1，2，…，n-1，并且f0是一個常量函數，F是一個{0,1}n上的函數，其定義對任意給定的整數a=a1a2…an，令:

(1)

其中,⊕表示異或運算，i=1，2，…，n，f0為常數，可以得出結論：1)F是一個保留前綴加密函數;2)任意保留前綴加密函數必定有F的表示形式.定理的證明參見文獻[6]，此處省略.

保留前綴Hash加密[11]是一種把Hash函數引入到保留前綴加密計算的加密算法，表示為Fh(a)其中fi-1(a1a2…ai-1)=T(Hash(a1a2…ai-1))，其中T為取位函數，即選擇Hash結果的某一位.

1.3 Sharif提出的條件代碼加密方法介紹

Sharif提出的基于分支條件混淆的條件代碼加密如圖1所示，主要是通過分支輸入生成條件代碼的加解密秘鑰，從而保證程序中不需要存儲秘鑰，實現了解密秘鑰隱藏和分支條件混淆的結合.逆向攻擊者解密代碼的難度等同于找到使得分支條件取值為真的輸入的難度，而分支條件混淆的目的正是阻礙攻擊者獲取使得分支條件取值為真的輸入.

Fig. 1 Example of conditional code encryption圖1 條件代碼加密示意圖

Fig. 2 The process of duplicate condition and compound condition圖2 重復條件代碼和復合條件代碼的復制處理

Fig. 3 The example of branch obfuscation based on prefix-preserving algorithm圖3 基于保留前綴Hash加密的分支條件混淆示意圖

另外，本文把形如a≤x≤b的條件稱為區間條件，把單個的等于比較條件、單個的區間條件成為基本條件.多個基本條件通過邏輯運算組合成的條件成為復合條件.

在Sharif提出的基于分支條件混淆的代碼加密方法中，對重復條件和多個等于條件取或的復合條件，需要使用條件代碼復制的方法，把復合條件拆分為多個簡單條件，然后再對各個簡單條件的代碼進行加解密，增加了混淆的損耗，同時降低了混淆的隱蔽性.如圖3所示:

1.4 基于保留前綴加密的分支混淆方法介紹

Sharif等人[9]提出的分支條件混淆僅針對等于條件，通過使用Hash值比較代替明文比較，使得攻擊者難以從Hash值比較中恢復出明文比較關系，達到分支條件混淆的目的.如對分支條件if(x=a)，其中x是任意類型的值，實質就是一片內存的內容，通過分支條件混淆后變為if(Hash(x)=Hash(a)).

王志等人[11]提出了基于保留前綴加密和Hash函數的路徑分支混淆技術，使用加密前綴匹配替代分支條件，實現分支條件混淆.例如分支條件if(9≤x≤15)，首先把條件轉換為整數區間[9,15]；然后使用前綴算法獲取區間的前綴集合S={1001,101*，11*}；接下來使用保留前綴Hash加密算法對S進行加密得到ES；最后使用加密前綴匹配函數替換分支條件，即if(9≤x≤15)變為if(isMatch(x,ES))，其中isMatch(x,ES)如算法2所示.

算法2.isMatch算法.

輸入：整數x、加密前綴集合ES;

輸出：true或者false，true表示x滿足分支條件，false表示x不滿足分支條件.

boolisMatch(x,HS)

{intencPrefixofInput=encInput(x);

inttmpFlag[32]={0};tmpFlag[0]=1?31;

for(inti=1;i<32;i++){tmpFlag[i]=tmpFlag[i-1]|(1?(31-i));}

for(intj=0;j

{tmpLen=ES[j].prefixLen;

tmpPrefix=encPrefixofinput&tmpFlag[tmpLen];

if(tmpPrefix=ES[j].prefix){return true;}

}

return fasle;

}

2 多輸入條件下的秘鑰生成

基于分支條件混淆的條件代碼加密，由于使用分支條件的輸入作為加解密秘鑰，導致該加密方法僅能用于單個等于條件的分支.對于具有多個輸入值使得分支條件取值為真的分支，由于輸入不具有唯一性，導致秘鑰不能直接使用分支輸入.因此需要對輸入進行處理，使得多個輸入x1,x2,x3,…輸入經過處理后得到相同的輸出y，使用y作為解密秘鑰，從而保證秘鑰的唯一性.

2.1 拉格朗日插值法

拉格朗日插值法是18世紀法國數學家約瑟夫·拉格朗日發明的一種多項式插值方法.用于尋找二維平面上經過n+1個點的n次多項式，使得多項式在給定的n+1個觀測點能取到給定的值.經過n+1個點的次數不超過n的多項式只有一個，即拉格朗日多項式.本文使用拉格朗日插值保證多輸入條件下的輸出唯一性.

對給定的n+1個點(x0,y0)，(x1,y1)，(x2,y2)，…，(xn,yn)，首先根據每個點得出n+1個拉格朗日基本多項式，其中第i個點(xi,yi) 的拉格朗日基本多項式為

2.2 輸入處理多項式生成

一方面，拉格朗日多項式的系數不是整數，即存在除法，因此在使用計算機計算的過程中可能會出現實際值與計算值有出入的問題；另外一方面，拉格朗日多項式具備鮮明的特征，給攻擊者從拉格朗日多項式中獲取分支輸入提供了便利；最后，如果多項式的次數過低，則在某個分支輸入已知的情況下會導致其他分支輸入泄露，從而會導致分支條件混淆被還原.因此需要對拉格朗日多項式進行變換，以實現多項式系數的整數化、消除拉格朗日多項式的特征和提高多項式次數.

首先，通過對插值多項式L(x)進行去分母和模運算變化，使得多項式的系數整數化，同時消除拉格朗日多項式的特征.即取

3 基于分支條件混淆的條件代碼加密

使用拉格朗日多項式進行多輸入分支的條件代碼加密密鑰生成，解決了大小比較分支的輸入不唯一問題，使得條件代碼加密和分支混淆緊密結合在一起，對條件代碼進行更好的混淆保護.同時通過密鑰構造解決Sharif條件代碼加密方法中的代碼復制問題，提升混淆的效率和隱蔽性.

3.1 Sharif條件代碼加密方法的改進

重復條件和復合條件需要使用代碼復制變轉換為多個簡單條件，根本原因在于能夠執行到條件代碼的分支輸入不唯一，因此不能直接使用分支輸入作為秘鑰.通過對輸入進行處理，使得多個輸入生成相同的輸出，則不需要使用代碼復制的手段，減少了加密導致的空間占用.在Sharif分支條件混淆的基礎上，對多輸入進行處理的步驟如圖4所示.

1) 判斷等于條件的輸入x,y是否為整數，若不是整數，則對輸入進行加鹽的Hash計算，然后取Hash值的前4個字節作為拉格朗日插值法的插值點的橫坐標；若x,y為整數，則直接取x,y作為插值點橫坐標；然后取一個隨機整數作為多項式在插值點x和y處的取值，生成拉格朗日多項式.

2) 使用拉格朗日多項式變換，得到輸入預處理函數inputProcess.

3) 在使用Hash值比較替代整數比較的過程中，依次判斷輸入x,y是否使得分支條件取值為真，使用第一個使分支條件取值為真的輸入作為inputProcess函數的參數計算該分支的輸出值keysource，使用keysource生成解密秘鑰，最后進行條件代碼的解密和再次加密.

Fig. 4 The process of compound condition and duplicate condition圖4 復合條件和重復條件處理示意圖

3.2 大小比較分支的條件代碼加密

對分支條件if(a≤x≤b)，應用基于保留前綴加密Hash算法的分支條件混淆技術混淆后，分支條件為if(isMatch(x,ES))，其中ES={es1,es2,…,esm}為區間[a,b]對應前綴集合應用保留前綴Hash加密算法Fh計算后得到加密前綴數據.對區間條件在基于保留前綴Hash加密的分支混淆后，條件代碼加密過程如圖5所示，加密步驟如下：

Fig. 5 Example of interval condition process圖5 區間條件分支處理示意圖

1) 對n位整數區間[a,b]，計算其前綴集合S={s1,s2,…,sk},對j位前綴元素si，取隨機數ri的尾部n-j比特與si一起組合成n位整數ti，使用t1,t2,…,tk作為拉格朗日插值點的橫坐標，取隨機數tmp作為所有插值點的縱坐標，計算輸入預處理函數inputProcess.保存隨機數數組R={r1,r2,…,rk}.

2) 在算法2中，若x使得isMatch返回true，則在isMatch中記錄與x相匹配的加密前綴esi的下標i，獲取esi對應前綴的位長，假設為m；然后取x的前m位和ri的后n-m位組合成inputProcess函數的輸入inputNum，計算得到分支的輸出keysource，然后使用keysource生成解密秘鑰key，使用key進行條件代碼的解密和再次加密.

3.3 復雜條件分支的條件代碼加密

由等于條件和區間條件通過邏輯運算形成的復雜條件中，復雜條件的混淆是通過對構成復雜條件的每個基本條件進行混淆而完成；秘鑰生成則是通過對每個基本條件進行單獨的輸入處理，但是需要保證每個基本條件在其輸入使得條件取值為真時的輸出都是相等的.為統一表示，令等于條件if(x=a)混淆后為if(isMatch(x,ES))，但是在等于條件下，isMatch算法變為{returnmemcmp(Hash(x),ES,hashLen);}，其中ES為a的Hash值；令等于條件if(x=a)的輸入處理函數為inputProcess(x)，等于條件下的inputProcess函數偽代碼如下：

inputProcess(x)

{

if (xis interger){returnx;}

else {inttmp=Hash(x);

returnfirstFourBytes(tmp);}

}

下面介紹復雜分支條件下的代碼加密過程，加密示意圖如圖6所示.

1) 根據與運算和或運算的結合律：(c11)&&(c12‖c13)=(c11&&c12)‖(c11&&c13)，把復雜條件轉換為基本條件與運算結合成的復合條件的或運算式，即形如(c11&&c12)‖(c21&&c22)‖(c31&&c32)，其中cij表示基本條件；記無或運算相隔的與運算條件為一組，即group[0]={c11,c12},group[1]={c21,c22},group[2]={c31,c32}共3組.

2) 對分支條件if((c11&&c12)‖(c21&&c22)‖(c31&&c32))的每個基本條件進行混淆，混淆后的分支條件為if(isMatch(x11,ES11) &&isMatch(x12,ES12))‖(isMatch(x21,ES21) &&isMatch(x22,ES22))‖(isMatch(x31,ES31) &&isMatch(x32,ES32))).

3) 對每個基本條件cij分別計算輸入其輸入處理函數，并記為inputPrecess[i][j]；設函數inputPrecess[i][j]的分支輸出為為Yij，randA為一隨機整數數，并令Rij=randA-Yij，修改inputPrecess[i][j]=inputPrecess[i][j]+Rij，則修改后所有基本條件的預處理函數inputProcess[i][j]，在其輸入為使得條件Cij取值為真的分支輸入值時，預處理函數的取值均為randA.

4) 在混淆后復雜條件執行時，按照順序計算每組條件與運算的取值，找到第1組取值為true的條件.假設第i組條件與運算的取值為true，則隨機選擇第i組條件中的任意一個條件代表該復雜分支條件進行分支輸出計算，假設選中條件為Cij，則選取inputProcess[i][j]為復雜分支條件的輸出計算函數，選取x[i][j]為inputProcess[i][j]的計算參數，計算結果則為randA，使用randA計算秘鑰，然后對條件代碼進行解密和2次加密.

Fig. 6 Example of complicated condition process圖6 復雜條件分支處理示意圖

Fig. 7 The encipher and decipher example of multi-thread code圖7 多線程代碼加解密示意圖

3.4 多線程處理

如果需要加密的代碼是一段多個線程共用的代碼，則在解密和2次加密的過程中需要進行加解密的操作同步，否則會導致加解密錯亂，程序執行出現不可控錯誤.本文采用臨界區對加加解密操作進行同步，解密操作在進入臨界區后首先判斷加密代碼是否在使用中.如果否,則解密;如果是，則不需要解密、直接返回，退出臨界區.

同樣，在2次加密的過程中，進入臨界區后首先判斷需要加密的代碼是否在使用中.如果否，則對代碼進行2次加密；如果是，則加密函數直接返回，退出臨界區.處理過程如圖7所示.

4 分析與評估

4.1 條件代碼加密的時間和空間消耗

由于本文提出的代碼加密是基于分支條件混淆，因此時間和空間的消耗都是基于分支條件已經被混淆的程序來計算的.

首先是加密算法消耗的存儲空間，本文采用AES-128加密算法對條件代碼進行加密，AES算法源代碼通過編譯得到的obj文件占用空間為58 807 B；其次inputProcess函數通過把系數和最高次數記為參數后，該函數的算法占用416 B.上述算法是所有的分支條件代碼加密所共用的代碼，因此隨著被選擇加密的分支條件越多，每個分支占用的共用空間就越少.另外由于每個分支條件需要存儲自己的多項式系數，需要增加加密和解密的外包函數，因此每個分支條件單獨占用的空間平均是30×4+83+83=283 B.即對單個區間條件構成的分支，對m個分支條件的代碼進行加密，平均每個分支條件的代碼加密需要消耗283+(416+58 807)m字節的空間.如果是m個復雜條件，且每個復雜條件由k個基本條件構成，則每個復雜分支平均消耗120×k+(416+58 807)m字節的空間用于代碼加密.

其次是時間消耗，時間消耗主要在于AES128一次加密和解密的時間，即平均每個分支多消耗0.003 3 ms(由10 000次AES加密和解密消耗32.8 ms時間計算得到單次加解密時間).

Table 1 Consumption Data of Time and Space表1 加密消耗的時間和空間數據

4.2 與其他加密方法的比較

Sharif第1次提出了基于分支條件混淆的代碼解密方法，通過分支條件混淆實現了秘鑰隱藏；通過逆向分析獲取加解密秘鑰的的難度，等同于找到使得被混淆分支條件取值為真的程序輸入的難度.即相比其他的加密方法，基于分支條件混淆的代碼加密方法能更好的對抗解密秘鑰獲取攻擊.

在基于分支條件混淆的代碼加密研究方面，除了Sharif在基于等于條件混淆的代碼加密研究外，還沒有相關的研究.與Sharif的加密方法相比，本文提出的方法在2個方面具有優勢：

1) 把Sharif的方法從等于條件擴展到了區間條件和復雜條件，具有更好的通用性；

2) 對多個等于條件取或的分支，本文提出的方法不需要代碼復制，從而節省了代碼占用的空間.

綜上所述，本文提出的代碼加密方法在時間和空間消耗上是可接受的；由于解密秘鑰通過分支混淆隱藏，使得加密后代碼能較好對抗逆向分析，因此該加密方法能夠實際使用，且具有比較好的代碼保護功能.

Table 2 Comparison of Different Methods表2 加密方法優勢對比

5 結 論

基于分支條件混淆的條件代碼加密，通過滿足分支條件的輸入產生秘鑰，同時利用分支混淆隱藏分支條件，從而隔離秘鑰和程序，極大地提高了解密難度.由于秘鑰生成和分支條件緊密聯系在一起，只有在加密的條件代碼所在分支因正確的輸入而得到執行時，通過分支輸入可以計算出秘鑰，實現解密，否則就會導致解密錯誤，產生不可預測的錯誤導致程序運行終止.雖然基于分支條件混淆的條件代碼解密具有較好的抗程序分析效果，但是當前研究僅能在等于條件分支上實現該類加密方式，極大地限制了該方法的使用.本文通過構建輸入預處理函數，對具有多個正確輸入的分支進行處理，完成了多輸入分支下利用分支輸入產生具有唯一性秘鑰的方法.利用該方法，對多個等于條件取或的分支和重復條件代碼分支的條件代碼加密進行了優化，減少了加密對空間的消耗；區間條件分支使用基于保留前綴加密和Hash函數的分支混淆方法進行分支條件混淆，本文使用整數區間對應的前綴集合生成輸入預處理函數，實現了區間條件分支下基于分支輸入產生唯一性秘鑰的方法，從而對區間條件分支的條件代碼進行加密.最后對等于和區間條件復合而成的復雜條件分支進行處理，對該分支同樣實現了基于分支輸入產生唯一性秘鑰的方法，進而對條件代碼進行加密.通過以上處理完成了基于分支條件混淆的條件代碼加密從等于條件分支到區間條件分支和復雜條件分支的擴展，提高了代碼保護的范圍，增強了代碼安全性.