一種改進的密碼函數識別方法

林　偉　李　偉　祝躍飛　石小龍

(數學工程與先進計算國家重點實驗室　河南 鄭州 450002)

?

一種改進的密碼函數識別方法

林偉李偉祝躍飛石小龍

(數學工程與先進計算國家重點實驗室河南 鄭州 450002)

密碼函數識別在惡意代碼分析、軟件脆弱性分析等領域具有積極的作用。傳統的密碼函數識別算法由于識別方式單一而存在識別精度不高的問題。針對上述問題，提出一種改進的基于數據流分析的密碼函數識別方法,將數據流分析引入密碼函數識別中，利用遞進式多特征的方法對密碼函數進行識別。實驗表明，該方法能夠準確定位密碼函數在應用程序中的位置，相比現有方法提高了密碼函數的識別精度。

密碼函數識別常數特征匹配數據流分析

0　引　言

目前，為了實現安全通信，軟件大都采用加密方式對協議數據進行保護，同時惡意程序也采用加密方法來對抗安全人員的逆向分析。識別應用程序中的密碼算法能夠在惡意代碼分析、網絡數據安全傳輸等領域發揮積極的作用。

現有的密碼函數識別可以分為靜態和動態識別兩種。靜態識別方法原理是檢測二進制程序中是否存在密碼算法的靜態特征，使用的特征可能是一個代碼片段、特殊的常數(magicnumber)、特殊的結構體如S盒或者加密函數入口處的字符串等等。每當找到了對應的特征，這些工具就輸出算法的名字(比如MD5、RSA)，也可能輸出算法的實現方法(比如OpenSSL)。

文獻[1-4]利用加密函數的位運算指令占總指令的比例較大這個特征來對密碼函數進行識別。文獻[5]通過計算緩沖區的信息熵來判斷緩沖區是否被解密，因為解密過程會對降低消息的信息熵。同時文獻還利用了另外兩個特點，一是密碼算法一般都有循環結構，二是密碼算法大量使用算術運算指令。上面提到的文獻對密碼算法的識別僅限于區分密碼算法和非密碼算法，很多時候安全分析人員需要知道具體采用的是哪種密碼算法。文獻[6]對大量密碼函數樣本進行訓練，提取各函數的屬性信息，定義的屬性包括指令條數、邏輯運算類指令頻度、移位運算類指令頻度等，然后得到各類密碼函數的分類模型。文獻[7]提出了一種基于循環I/O的密碼算法識別方法。其基本思想是首先記錄程序的軌跡信息，然后識別軌跡里的循環結構，提取循環結構的輸入和輸出參數，最后將輸入和輸出內存數據代入到已知的密碼算法實現中進行檢驗，如果匹配成功則證明是該算法。此方法的局限性在于，部分密碼算法為了提高效率，在實現過程中可能會采取一些優化算法，會破壞密碼算法原有設計中的一些循環結構，比如AES加解密算法的一種優化算法就是將輪循環全部展開，在匯編代碼中將沒有循環結構存在，這時就會產生漏報。

綜上所述，密碼函數識別定位是分析網絡軟件、惡意程序的關鍵，現有的靜態密碼函數識別方法一般都是采用特征匹配的方法，適用性非常有限，而動態識別方法大都是利用密碼函數的指令比例特征對密碼函數進行分類，但因為密碼函數種類眾多，利用指令比例特征很難找到一個合適的分類模型使得所有的密碼函數僅屬于一個類別，因此準確率也有待提高。

1　密碼算法識別

1.1總體思路

本文將數據流分析引入密碼函數識別中，提出了一種遞進式的密碼函數識別方法。首先利用密碼函數的常數、運算指令比例等簡單特征排除掉絕大部分函數的干擾，識別出具有典型常數特征的密碼函數，比如MD5、SHA1等，并篩選出疑似密碼函數；然后利用數據流分析對可疑函數的數據依賴關系進行分析，判斷密碼函數的大致種類；最后再利用不同類型指令的比例特征對密碼函數的類別進一步區分。密碼函數識別的整體思路如圖1所示。

圖1　系統架構圖

1.2密碼函數初步識別

程序執行軌跡包含的函數調用非常多，因此首先根據密碼函數的一些簡單特征對函數進行初步識別篩選，排除掉絕大部分函數的干擾，然后再對疑似密碼函數進行深度識別。經過分析本文選取了以下三種特征：

1) 指令總數：密碼函數因為其功能的復雜性，要實現加密或解密功能，所需要的指令不會很少，因此指令總數有一個最小限制。通過對Feiq軟件的一次執行軌跡進行分析，本文得到如表1所示的統計結果，可以看出指令數目小于10的函數調用次數占所有函數調用次數的42.8%，而指令數目小于200的函數調用更是占了85.8%，因此僅用指令總數這個特征就可以排除掉大部分非密碼函數的干擾。如表1所示。

表1　不同指令數目的函數所占比例

2) 算術運算與邏輯運算指令比例：密碼函數的算術運算、邏輯運算指令比較多，控制轉移指令比較少，這幾類指令在常見的密碼算法實現中具有非常明顯的統計特性，可以作為區分密碼函數和非密碼函數的重要指標。

3) 函數使用的常數：密碼算法實現中使用的常數分主要分為兩類。第一是指令中的立即數，第二是存儲在內存中的常數，利用這個特征可以對一些特殊的密碼函數進行識別。

提取函數的信息之后，根據上述密碼函數特征對函數進行初步識別篩選，為了避免對同一密碼函數重復識別，本文只對最內層的密碼函數進行識別，如果子函數被識別為密碼函數，那么就不對其父函數進行識別，如果子函數不是密碼函數，再將子函數的信息并入到父函數再進行識別。對每個函數調用識別的具體步驟如下：

Step1若函數指令總數N在一定的閾值范圍內，執行Step2，否則認為該函數不是密碼函數，結束所有步驟。

Step2將函數所有指令使用的立即數和訪問的內存與密碼函數知識庫中的特征進行匹配，檢測其中是否包含了一些特定密碼算法才會使用的常數，如果包含則說明函數是該密碼算法的一個實現，識別成功，結束所有步驟。

Step3計算函數算術運算和邏輯運算所占的比例，若大于一定的閾值，則標記該函數為疑似密碼函數。

密碼函數初步識別篩選將函數調用序列中大部分函數過濾掉，并對一些包含常數特征的密碼函數進行識別，比如MD5、SHA1等，再根據指令總數、算術邏輯運算指令比例等特征篩選出疑似密碼函數，有待進一步分析。

1.3基于數據流分析的密碼函數分類

密碼算法為了防止被破解，在設計時會盡量滿足雪崩效應。雪崩效應是指當輸入發生最微小的改變(比如改變一個二進制位)時，也會導致輸出的劇變(比如輸出中一半的二進制位發生反轉)，比如圖2所示的SHA-1散列函數，輸入只改變了一個二進制位，輸出卻完全不一樣。若某種密碼或散列函數的雪崩特性不夠好，那么密碼分析者就能夠僅僅從輸出推測輸入，這可能導致該算法部分乃至全部被破解。

圖2　SHA-1函數雪崩效應示意圖

同時由于不同類型密碼算法的輸入輸出依賴關系不一樣，如圖3所示，分組密碼算法每個輸入字節會影響輸出的每一個字節，而流密碼算法每個輸入字節僅影響一個輸出字節，因此可以利用這個特征對不同類型的密碼函數進行識別。

圖3　不同類型密碼函數輸入輸出依賴關系

明密文緩沖區定位是為了在函數所有的輸入輸出中發現滿足密碼函數特性的輸入和輸出緩沖區，如果找不到則說明函數不是密碼函數，密碼函數常見的種類有Hash函數、分組密碼函數、公鑰密碼函數、流密碼函數。可以根據明密文緩沖區的特點將這四類密碼函數分為兩種：

1) 第一種是前三類密碼函數，函數存在一個輸入緩沖區和一個輸出緩沖區，其中輸入緩沖區中的每個字節會影響輸出緩沖區的很多字節，反之輸出緩沖區的每個字節會依賴輸入緩沖區的許多字節；

2) 第二種是流密碼函數，函數存在一個輸入緩沖區和一個輸出緩沖區，緩沖區大小相等，并且每個輸入字節只影響對應位置的一個輸出字節。

定位明密文緩沖區存在兩個干擾，一是普通函數也可能會存在滿足上述特性的輸入輸出緩沖區，二是密碼函數中滿足上述特性的緩沖區不一定是函數的明密文，也有可能是密碼函數的密鑰、S盒以及一些臨時變量。

本文采取三種方法來排除上述兩個干擾：

1) 利用函數的指令數目、指令比例等特征對函數進行初步識別篩選，過濾掉絕大部分的普通函數，根據實際經驗，篩選出來的函數一般都是密碼函數；

2) 記錄函數結束時的棧指針esp的值，因為函數結束時存于棧中的局部變量已經被釋放，因此函數內部訪問的地址小于esp的內存視為函數的局部變量；

3) 設置加密和解密的緩沖區不小于4個字節，防止一些臨時讀寫的內存或者離散訪問的內存被誤認為是加解密緩沖區。

秦鐵崖來京城之前，翻閱舊案卷宗，去了趟證物庫房，翻出這個煙花筒帶在身邊。秦鐵崖道：“你不叫喬十二郎，你是陸楓橋。”

為了識別第一類緩沖區，首先給出內存依賴度的定義：

定義1內存依賴度是指污點分析中，單個內存單元所依賴的污染源字節數，比如若指令movbyteptr[edi],al執行后內存單元的污點狀態為{1,2,4}，則該內存單元的依賴度為3。

對第一類緩沖區，由于雪崩效應密碼函數輸出的每個內存單元會依賴于輸入的全部字節或者大部分字節，表現出高依賴度的特征，因此可以采用如下方式定位輸入輸出緩沖區。標記疑似密碼函數所有輸入內存單元中連續字節數不小于4的地址為初始污點，對疑似密碼函數的執行軌跡進行污點分析，然后逐字節檢查每個字節污染的輸出單元，如果找到一塊輸入和輸出，輸入的每個字節都污染了輸出的很多字節，并且輸出的每個字節也依賴很多輸入字節，則說明定位成功。設計定位第一類緩沖區密碼算法如下所示，如果定位成功算法返回定位到的輸入輸出緩沖區，否則返回NULL。如算法1所示。

算法1定位第一類緩沖區算法

Input：函數執行軌跡FuncTrace，及函數讀寫的所有內存單元In和Out

Output：若定位成功，返回定位到的輸入輸出緩沖區InBuf和Outbuf，否則返回NULL

1.InitTaintSource(In) //初始化In中連續字節數不小于4的內存單元為初始污點

2.TaintAnalysis(FuncTrace) //對執行軌跡進行局部污點分析

3.foreachbyteiintaintsource

4.calculateT(i) //計算字節i污染的內存單元集合，用T(i)表示

5.endfor

6.InBuf= {污染源第一個字節}

7.OutBuf=T(0)

8.for(污染源中剩下的字節)

9.if(T(i)∩T(i-1)！=NULL)

10.pushitoInBuf;

11.pushT(i)toOutBuf;

12.endif

13.ifsizeof(InBuf)

14.InBuf= {第i個污染源字節}

15.OutBuf=T(i);

16.endif

17.endfor

18.ifsizeof(InBuf)

19.returnNULL;

20.endif

21.returnInBuf,OutBuf

對于第二類緩沖區，因為密文和明文只有一一對應的依賴關系，可以在輸入輸出緩沖區中利用滑動窗口的方法識別出滿足一一對應的兩個內存塊，即流密碼函數的輸入和輸出。設計的定位算法如算法2所示。

算法2定位第二類緩沖區

Input：函數執行軌跡FuncTrace，及函數讀寫的所有內存單元In和Out

Output：若定位成功，返回輸入輸出緩沖區InBuf和Outbuf，否則返回NULL

1.InitTaintSource(In)

//初始化Input中連續字節數不小于4的內存單元為初始污點

2.TaintAnalysis(FuncTrace)

//對函數的執行軌跡進行局部污點分析

3.OutBuf=GetBytesWithContinuousLabel(Output)

//獲取Output中污染標簽連續的內存單元塊

4.ifsizeof(OutBuf)

//T為輸出緩沖區大小的最小閾值

5.renturnNULL

6.endif

7.InBuf=GetDependencySource(OutBuf);

//獲取OutBuf依賴的輸入緩沖區

8.returnInBuf,OutBuf

不同密碼函數的輸入輸出依賴關系不一樣，因此我們可以依此對不同密碼函數進行區分。流密碼函數的輸入輸出緩沖區大小相等，并且每個輸入字節僅影響一個輸出字節；Hash函數與其他密碼函數的一個主要區別就是函數輸出緩沖區的大小，Hash函數的輸出緩沖區一般都比輸入要小很多，并且Hash函數的每個輸入字節都會影響所有的輸出字節；分組密碼函數每個輸入字節會影響全部輸出字節，并且輸入和輸出緩沖區相等，公鑰密碼函數的特征與此類似。根據上面的分析，可以用圖4所示的決策樹對密碼函數的類別進行劃分。

圖4　密碼函數分類決策樹

利用數據流分析對密碼函數進行分類只是將疑似密碼函數分為了流密碼函數、Hash函數等較大的類別，同時可以根據輸出緩沖區的大小對密碼函數對密碼函數進一步區分，比如對Hash函數，根據輸出緩沖區大小可以得到如圖5所示的決策樹。對一個疑似密碼函數，密碼函數分類的最終結果是得到其所有可能的類別集合，比如若輸出緩沖區大小為16個字節，則疑似密碼函數可能的類別為{MD2、MD4、MD5、RIPEMD、…}。

圖5　Hash函數根據緩沖區大小的分類

1.4基于特征統計的密碼算法識別

不同密碼函具有各自獨特的指令統計特征，利用該特征可以對密碼函數進行識別。本文定義了一個五維特征向量來對密碼函數進行描述[8]，其中各個元素的含義如下：

N：指令總數。

Rarith：算術運算指令比例。算法運算指令反映了函數的算法操作，包括ADC、ADD、DEC等指令。

Rlogic：邏輯運算指令比例。包括AND、SHL、SHR、ROL、SAL等指令。

Rspecial：特殊運算指令比例。公鑰密碼算法比如RSA包含很多大數的運算，反映到匯編指令則是MUL、IMUL、DIV、IDIV等算術運算指令，因此可以利用這一指標對公鑰密碼函數進行識別。

Rconj：條件跳轉指令比例。通過對密碼函數進行分析，發現其中條件跳轉指令的比例比一般函數要低很多。因此選取它作為密碼函數的特征指標之一。

在獲取了待檢測函數的五維特征向量后，需要一種數據分類模型，對該函數所屬的密碼算法類別進行識別。常見的數據分類算法有決策樹方法、人工神經網絡方法、貝葉斯方法和支持向量機方法等，不同的分類方法有不同的特點，分別適用不同類型的數據，評價一個分類算法的標準包括準確率、執行效率、強壯性、伸縮性和可解釋性等，上述四種方法的性能評估如表2所示，綜合考慮算法的性能以及實現難度，本文選擇貝葉斯方法來實現這一目標。如表2所示。

表2　各分類算法性能比較

貝葉斯分類的基本流程如下：

1) 設x={a1,a2,…,am}，其中ai為x的一個特征屬性；

2) 獲取類別集合C={y1,y2,…,yn}；

3) 計算條件概率P(y1|x)，P(y2|x)，…，P(yn|x)；

4) 如果P(yk|x)=max{P(y1|x),P(y2|x),…,P(yn|x)}，則x∈yk。

問題的關鍵在于如何計算第3步中的各個條件概率，可以采用如下方法：

1) 找到一個已經分好類的訓練樣本集。

2) 統計得到各類別下各個屬性的條件概率分布：

P(a1|y1),P(a2|y1),…,P(am|y1),…,P(am|yn)

3) 根據貝葉斯定理有如下推導：

因為分母對所有類別為常數，只需要將分子最大化即可，若各特征屬性是條件獨立的，則有：

P(x|yi)P(yi)=P(a1|yi)…P(am|yi)P(yi)

根據上述分析，利用貝葉斯分類對密碼函數進行識別的基本步驟如下：

Step1通過加密算法庫、網頁論壇等方式收集密碼算法樣本，通過手工定位的方法確定各個程序中密碼算法的所在位置，運行程序收集密碼函數的特征。

Step2分類器訓練，這一步的主要任務就是生成分類器，計算每個類別的出現頻率和每個特征屬性對每個類別的條件概率估計。

Step3使用分類器對目標函數進行分類。輸入是分類器和待分類函數，輸出是待分類函數所屬的算法類別。

2　實現與測試

2.1測試環境

本文測試環境如表3所示。

表3　測試環境

2.2功能測試

(1) 測試對象EncryptDemo

EncryptDemo是本文為了測試系統的功能自己編寫的一款加密通訊程序。軟件分為客戶端和服務端，客戶端每發送一個明文命令，服務端就回應一個加密的數據包，客戶端再回應一個確認包。數據包的加密方法如所圖6所示，客戶端收到數據包后，將數據包解密還原成明文，并計算SHA-1摘要，與數據包中的摘要作比對。客戶端和服務端的加解密函數基于開源加密算法庫xyssl-0.8實現。

圖6　EncryptDemo協議格式設計

(2) 密碼函數識別

首先根據函數使用的常數、指令比例等特征對密碼函數進行初步識別，識別結果如圖7所示。識別出了SHA1_init、SHA1_update和AES_DE函數，除此之外還識別出了一個疑似密碼函數sub_44110d。

圖7　EncryptDemo密碼函數初步識別結果

然后利用污點分析定位疑似密碼函數中的加解密緩沖區，對函數sub_44110d的第一次調用實例的輸入和輸出定位結果如圖8所示。

圖8　EncryptDemo密碼函數進一步識別結果

圖8中省略了一些輸入和輸出內存單元，輸入輸出緩沖區都是0x43字節，并且輸出的每個字節依賴于輸入的每一個字節，因此我們判定它為流密碼函數，根據貝葉斯識別算法，算法是RC4的概率為87%，是SEAL的概率為13%，因此判斷sub_44110d為RC4函數。

另外本文對公開軟件中的8種密碼算法進行了識別，并與3種密碼識別軟件進行了對比，結果如表4所示。

表4　識別結果

3種工具都聲稱能夠檢測本文測試的8種密碼算法，本文的測試結果見表4所示，其中Π表示成功識別了程序中的加密算法，Ο表示未能識別指定的密碼算法，可以看出沒有任何一個工具能夠識別所有的加密算法。這是因為對于惡意軟件來說，使用靜態的方法很難識別其中的密碼算法，因為攻擊者可以很容易地混淆惡意程序把算法的靜態特征給隱藏起來。

(3) 性能分析

本文的方法的時間開銷包含三個部分：指令特征的統計、基于數據流分析的密碼函數分類和特征統計的樣本訓練。其中特征統計的樣本訓練的時間開銷取決于樣本復雜度和訓練次數，差異性較大，因此本文只給出了前兩個部分的時間開銷。本文采取PIN平臺進行的指令特征的統計和數據流分析，其中時間開銷為軟件從啟動到啟動完畢的時間開銷，如表5所示。

表5　時間開銷

3　結　語

傳統的密碼函數識別算法中的靜態密碼函數識別方法一般都是采用特征匹配的方法，而動態識別方法是利用密碼函數的指令比例特征對密碼函數進行分類，兩者的準確精度不高。針對上述問題，本文提出了一種改進的基于數據流分析的密碼函數識別方法,將數據流分析引入密碼函數識別中，利用遞進式多特征的方法對密碼函數進行識別。實驗表明，該方法能夠準確定位密碼函數在應用程序中的位置，相比現有方法提高了密碼函數的識別精度。

[1]CaballeroJ,YinH,LiangZ,etal.Polyglot:Automaticextractionofprotocolmessageformatusingdynamicbinaryanalysis[C]//Proceedingsofthe14thACMconferenceonComputerandcommunicationssecurity.ACM,2007:317-329.

[2]LinZ,JiangX,XuD,etal.AutomaticProtocolFormatReverseEngineeringthroughContext-AwareMonitoredExecution[C]//NDSS,2008,8:1-15.

[3]WangZ,JiangX,CuiW,etal.ReFormat:Automaticreverseengineeringofencryptedmessages[M]//ComputerSecurity-ESORICS2009.SpringerBerlinHeidelberg,2009:200-215.

[4]WondracekG,ComparettiPM,KruegelC,etal.AutomaticNetworkProtocolAnalysis[C]//NDSS,2008,8:1-14.

[5]LutzN.Towardsrevealingattackersintentbyautomaticallydecryptingnetworktraffic[J].Master’sThesis,ETH,Zürich,Switzerland,2008.

[6] 李洋,康緋,舒輝.基于動態二進制分析的密碼算法識別[J].計算機工程,2012,38(17):106-109,115.

[7]CalvetJ,FernandezJM,MarionJY.Aligot:Cryptographicfunctionidentificationinobfuscatedbinaryprograms[C]//Proceedingsofthe2012ACMconferenceonComputerandcommunicationssecurity.ACM,2012:169-182.

[8] 李繼中.基于相似性判定的密碼算法識別技術研究[D].解放軍信息工程大學,2009.

ANIMPROVEDMETHODOFCRYPTOGRAPHICFUNCTIONRECOGNITION

LinWeiLiWeiZhuYuefeiShiXiaolong

(State Key Laboratory of Mathematical Engineering and Advanced Computing,Zhengzhou 450002,Henan,China)

Cryptographicfunctionrecognitionhasapositiveeffectinmaliciouscodeanalysis,softwarevulnerabilityanalysisandotherfields.Traditionalcryptographicfunctionrecognitionalgorithmhastheproblemoflowidentificationaccuracyduetoitssinglemode.Inlightoftheaboveproblem,weproposedanimprovedmethodofcryptographicfunctionrecognitionwhichisbasedondataflowanalysis.Itintroducesdataflowanalysistocryptographicfunctionrecognition,andusesprogressivemulti-featureapproachtorecognisethecryptographicfunctions.Experimentsshowedthatthemethodcouldaccuratelylocatethepositionofcryptographicfunctionsintheapplication,comparedtoexistingmethods,theaccuracyofcryptographicfunctionrecognitionwasimproved.

CryptographicfunctionrecognitionConstantfeaturematchingDataflowanalysis

2014-06-13。國家自然科學基金項目(61309007)；國家科技支撐計劃項目(2012BAH47B01)。林偉，博士生，主研領域：信息安全。李偉，講師。祝躍飛，教授。石小龍，碩士生。

TP393.08

ADOI:10.3969/j.issn.1000-386x.2016.03.071