李繼中，蔣烈輝，舒 輝

（1.信息工程大學(xué)，河南 鄭州450002；2.數(shù)學(xué)工程與先進(jìn)計(jì)算國家重點(diǎn)實(shí)驗(yàn)室，河南 鄭州450002）

0 引 言

二進(jìn)制代碼中的密碼算法技術(shù)主要分為靜態(tài)識(shí)別和動(dòng)態(tài)識(shí)別2種［1，2］，靜態(tài)識(shí)別主要采用特征字匹配［3］和基于指令統(tǒng)計(jì)屬性［4］的篩選，具有識(shí)別效率高、誤報(bào)率較高的特點(diǎn)；動(dòng)態(tài)識(shí)別是在對(duì)目標(biāo)代碼執(zhí)行指令監(jiān)控記錄的基礎(chǔ)上，針對(duì)指令序列采用累加百分比［5］進(jìn)行密碼函數(shù)大致位置定位，針對(duì)指令中的內(nèi)存數(shù)據(jù)和寄存器數(shù)據(jù)進(jìn)行密碼算法動(dòng)態(tài)特征字識(shí)別［6］，由于動(dòng)態(tài)記錄信息龐大，造成識(shí)別效率不高，但識(shí)別準(zhǔn)確性較高。

文獻(xiàn) ［7，8］中指出循環(huán)是密碼函數(shù)實(shí)現(xiàn)代碼中的重要特征之一，識(shí)別代碼中的循環(huán)特征對(duì)于密碼函數(shù)的篩選與定位具有重要作用。本文詳細(xì)分析了密碼算法循環(huán)特征產(chǎn)生機(jī)理，分別針對(duì)控制循環(huán)結(jié)構(gòu)和指令序列循環(huán)提出了識(shí)別算法。

1 密碼算法循環(huán)模式分析

1.1 密碼算法循環(huán)特征

密碼算法在設(shè)計(jì)中，通常會(huì)采用循環(huán)模式實(shí)現(xiàn)加解密功能。根據(jù)循環(huán)存在的粒度不同，密碼算法循環(huán)特征可分為2種：密碼函數(shù)內(nèi)部循環(huán)；加解密分組循環(huán)。在程序執(zhí)行流程中，密碼函數(shù)內(nèi)部循環(huán)包含于加解密分組循環(huán)內(nèi)部。

（1）密碼函數(shù)內(nèi)部循環(huán)

密碼函數(shù)內(nèi)部循環(huán)是指在密碼函數(shù)在設(shè)計(jì)時(shí)，使用相同或類似的功能函數(shù)對(duì)數(shù)據(jù)進(jìn)行反復(fù)操作，在Hash函數(shù)和分組密碼中體現(xiàn)的比較明顯。邏輯表達(dá)式是構(gòu)造Hash函數(shù)的重要組件，代碼實(shí)現(xiàn)時(shí)會(huì)反復(fù)循環(huán)運(yùn)用該類表達(dá)式，為了提高執(zhí)行效率，Hash函數(shù)代碼實(shí)現(xiàn)時(shí)通常進(jìn)行循環(huán)展開；分組算法設(shè)計(jì)時(shí)通常采用Feistel結(jié)構(gòu)和Spn結(jié)構(gòu)，該結(jié)構(gòu)以函數(shù)形式存在于代碼中，該函數(shù)中包括若干輪的循環(huán) （循環(huán)次數(shù)與密鑰長度相關(guān)）；公鑰算法通常在二進(jìn)制代碼中采用包含乘、除指令的循環(huán)實(shí)現(xiàn)模冪運(yùn)算。

（2）加解密分組循環(huán)

分組循環(huán)是指在數(shù)據(jù)加解密時(shí)，把輸入數(shù)據(jù)按照特定的分組長度 （128bits，256bits等）進(jìn)行數(shù)據(jù)填充與切割，并針對(duì)切割后的各個(gè)分組依次采用密碼函數(shù)進(jìn)行加解密處理，分組間的關(guān)系取決于使用的加密模式 （CBC、ECB、CFB等）。

1.2 密碼算法循環(huán)結(jié)構(gòu)

循環(huán)是密碼算法代碼實(shí)現(xiàn)時(shí)常用的結(jié)構(gòu)形式，循環(huán)體中包括密碼函數(shù)的核心操作部分 （如邏輯表達(dá)式、算術(shù)表達(dá)式、Feistel結(jié)構(gòu)函數(shù)等），按照循環(huán)結(jié)構(gòu)不同，密碼算法主要包括控制結(jié)構(gòu)循環(huán)和指令序列循環(huán)。

在二進(jìn)制代碼反匯編結(jié)果中，基本塊是單入口、單出口的連續(xù)指令序列，基本塊循環(huán) （基本塊自身所構(gòu)成的循環(huán)）和基本塊嵌套循環(huán)是典型的控制循環(huán)模式，常常出現(xiàn)在分組密碼、公鑰密碼和流密碼的實(shí)現(xiàn)代碼中；為了提高執(zhí)行效率，Hash函數(shù)通常采用加密主函數(shù)循環(huán)展開的方式，構(gòu)造成為一個(gè)大基本塊，簡單循環(huán)模式則蘊(yùn)藏在其中；此外，在對(duì)二進(jìn)制目標(biāo)代碼進(jìn)行動(dòng)態(tài)分析過程中，通常對(duì)記錄下的執(zhí)行指令序列進(jìn)行分析，抽取出基本塊循環(huán)和嵌套循環(huán)等密碼算法常用的循環(huán)模式。密碼算法常用的兩種循環(huán)結(jié)構(gòu)如圖1所示，其中循環(huán)體是指構(gòu)成循環(huán)的最小連續(xù)指令序列；因此，面向二進(jìn)制代碼的密碼算法循環(huán)特征識(shí)別主要分為控制結(jié)構(gòu)循環(huán)識(shí)別和指令序列循環(huán)識(shí)別。

2 基于回向邊遍歷的控制結(jié)構(gòu)循環(huán)識(shí)別

在二進(jìn)制代碼反匯編結(jié)果中，采用四元組G＝（START，END，N，E）對(duì)函數(shù)中基本塊之間的控制關(guān)系進(jìn)行描述，其中N是結(jié)點(diǎn) （基本塊）集合，E是邊集合，START∈N是一個(gè)沒有入向邊的開始結(jié)點(diǎn) （函數(shù)入口），END∈N是一個(gè)沒有出向邊的結(jié)束結(jié)點(diǎn) （函數(shù)出口）。

傳統(tǒng)的控制流圖循環(huán)檢測方法根據(jù)已識(shí)別的必經(jīng)節(jié)點(diǎn)對(duì)回向邊進(jìn)行循環(huán)判別，在控制節(jié)點(diǎn)判定時(shí)需要遍歷所有的有效路徑，效率比較低；密碼函數(shù)控制結(jié)構(gòu)中的回向邊比較少，首先獲取回向邊的源節(jié)點(diǎn)和目的節(jié)點(diǎn)，而后通過目的節(jié)點(diǎn)和源節(jié)點(diǎn)之間是否存在有效路徑來判別循環(huán)結(jié)構(gòu)，可以有效提高檢測效率；此外，基本塊循環(huán)并且基本塊內(nèi)部使用邏輯運(yùn)算或算術(shù)運(yùn)算是密碼函數(shù)的重要特征，針對(duì)該特征可進(jìn)行疑似密碼基本塊篩選。

針對(duì)X86指令集，在目標(biāo)二進(jìn)制代碼反匯編結(jié)果中，跳轉(zhuǎn)指令決定控制流圖的結(jié)構(gòu)，根據(jù)跳轉(zhuǎn)目的地址的方向不同，反匯編結(jié)果控制流圖中的有向邊可劃分為：回向邊、前向邊和順序邊，有向邊類型如圖2所示，假設(shè)跳轉(zhuǎn)指令地址和目的地址分別為SrcAddr，DstAddr，判別條件如下：①回向邊：SrcAddr＞DstAddr；②前向邊：SrcAddr＜DstAddr ＆ ＆ ！seq （SrcAddr，DstAddr）；③ 連續(xù)邊：seq （SrcAddr，DstAddr）。

其中函數(shù)seq（SrcAddr，DstAddr）判斷2個(gè)地址是否連續(xù)，若連續(xù)則返回1，否則返回0。

在反匯編結(jié)果控制流圖的有向邊中，回向邊決定著是否存在著循環(huán)，基于控制結(jié)構(gòu)的循環(huán)檢測算法主要步驟如下：

步驟1 獲取函數(shù)內(nèi)部基本塊信息bblInfo＜bblBeginAddr，bblEndAddr＞，有向邊集合Edges＜edgeSrc，edgeDst＞；

步驟2 遍歷基本塊的出邊集合，若跳轉(zhuǎn)指令的目的地址edgeDst小于當(dāng)前指令地址edgeSrc，則把該邊加入到回向邊集合BackEdges＜＞中；若基本塊出邊地址edgeDst等于bblBeginAddr，則識(shí)別出基本塊循環(huán)，并把該基本塊信息添加到bblLoop＜＞結(jié)構(gòu)中；

步驟3 遍歷回向邊集合BackEdges＜＞，采用DFS（深度優(yōu)先搜索）算法判別跳轉(zhuǎn)指令的目的地址所在基本塊與跳轉(zhuǎn)指令所在基本塊之間是否存在路徑；

步驟4 輸出基本塊循環(huán)和普通循環(huán)的檢測結(jié)果。

相比于傳統(tǒng)的基于必經(jīng)節(jié)點(diǎn)識(shí)別的循環(huán)檢測方法，針對(duì)目標(biāo)二進(jìn)制代碼反匯編結(jié)果所設(shè)計(jì)的基于回向邊遍歷和DFS路徑發(fā)現(xiàn)的循環(huán)檢測算法，省略了控制節(jié)點(diǎn)識(shí)別步驟，時(shí)間復(fù)雜度是O（m＊n2），其中m是回向邊個(gè)數(shù)，n是基本塊節(jié)點(diǎn)個(gè)數(shù)；在二進(jìn)制代碼反匯編結(jié)果的控制流圖中，回向邊個(gè)數(shù)通常遠(yuǎn)小于基本塊節(jié)點(diǎn)個(gè)數(shù)，則O（m＊n2）≈O（n2），該算法主要是DFS路徑發(fā)現(xiàn)所產(chǎn)生的開銷。

3 基于循環(huán)體歸約的指令序列循環(huán)識(shí)別

指令序列根據(jù)產(chǎn)生方式不同可以分為循環(huán)體展開的指令序列和代碼動(dòng)態(tài)執(zhí)行所記錄的指令序列，這兩類指令序列中指令間具有較好的線性時(shí)序關(guān)系，描述為指令流T＝I1，I2，…，In，其中Ik表示指令流中的第k條指令。

在X86指令集中，假設(shè)指令序列α∈X86＊，Pref（α）是α的前綴序列集合，即若-γ∈X86＊且α＝βγ，則β∈Pref（α）；當(dāng)α∈X86＊且≥1時(shí)，α∈X86＋。

令TRACE為指令序列集合，一條指令序列L∈TRACE，則簡單循環(huán)定義為

上述定義只能識(shí)別不具有循環(huán)嵌套關(guān)系的指令循環(huán)體，不能反映循環(huán)體之間的嵌套、迭代等關(guān)系，為了解決該問題，引入循環(huán)標(biāo)識(shí)集合Lid表示已識(shí)別的嵌套內(nèi)層循環(huán)體，循環(huán)識(shí)別采用從內(nèi)到外的逐層歸約方式，令TRACELid是包含循環(huán)標(biāo)識(shí)的執(zhí)行記錄集合，則嵌套循環(huán)定義為

循環(huán)實(shí)例L的循環(huán)體BODY［L］∈（X86∪Lid）＋，嵌套循環(huán)控制流圖的執(zhí)行序列循環(huán)歸約如圖3所示，其中X1，X2∈Lid。

在指令序列T＝I1，I2，…，In中，一條指令I(lǐng)k若屬于循環(huán)實(shí)體BODY ［loop］，則指令I(lǐng)k是循環(huán)實(shí)體的內(nèi)部指令或是循環(huán)實(shí)體的開始指令，可以在指令序列的循環(huán)判別過程中根據(jù)可能存在的循環(huán)實(shí)體進(jìn)行指令歸約，基于指令序列的循環(huán)識(shí)別算法主要步驟為：

步驟1 從TRACE中取指令I(lǐng)k，若k＞n則退出；

步驟2 判斷潛在循環(huán)堆棧結(jié)構(gòu)PotentialLoops Stacks是否為空，若為空，轉(zhuǎn)步驟3更新Potential LoopsStack結(jié)構(gòu)，否則，轉(zhuǎn)步驟4；

步驟3 采用算法FindPotentialLoops（History，Ik）更新PotentialLoopsStack結(jié)構(gòu)，并把Ik添加到History指令序列中，轉(zhuǎn)步驟1；

步驟4 在PotentialLoopsStack結(jié)構(gòu)中按照從棧頂?shù)綏５椎捻樞?，依次匹配每條潛在循環(huán)指令序列中的等待指令，若匹配轉(zhuǎn)步驟5，否則轉(zhuǎn)步驟6；

步驟5 調(diào)整當(dāng)前循環(huán)指令序列中的循環(huán)指針指向下一條指令，若循環(huán)指針不為空，轉(zhuǎn)步驟1；否則，轉(zhuǎn)步驟7；

步驟6 彈出棧頂?shù)臐撛谘h(huán)指令序列直至Potential－LoopsStack為空，轉(zhuǎn)步驟1；

步驟7 匹配一個(gè)循環(huán)體，把該循環(huán)體用Lid代替，并存儲(chǔ)在LoopStorage結(jié)構(gòu)中，調(diào)整該潛在循環(huán)指令序列的等待指針指向該指令序列的第一條指令，轉(zhuǎn)步驟1。

潛在指令序列循環(huán)實(shí)體是根據(jù)當(dāng)前指令內(nèi)容，從已處理的指令序列 （History）中識(shí)別出可能的循環(huán)實(shí)體，具體算法偽代碼如下：

算法：FindPotentialLoops （History，Ik）

輸入：已處理的指令序列History，當(dāng)前指令I(lǐng)k

輸出：更新潛在循環(huán)指令序列的堆棧結(jié)構(gòu)Potential－LoopsStack

for（int j＝1；j＜k；j＋＋）

｛if （Historyj＝＝Ik）

｛sp＝Historyj＋1； ／／下條指令指針，等待指令

／／History（j，k－1）指在History指令序列中取j至k－1的部分

PUSH （PotentialLoopStack，History （j，k－1），sp）；｝

｝

在循環(huán)歸約過程中，對(duì)于循環(huán)L＝ （body）m和L′＝（body）n，L和L′具有相同的循環(huán)實(shí)體，為了歸約外層的循環(huán)結(jié)構(gòu)，則把L和L′視為相同的循環(huán)并存儲(chǔ)在LoopStorage結(jié)構(gòu)中。

4 測試與結(jié)論

4.1 測試環(huán)境

操作系統(tǒng)：Windows7SP1，處理器：Intel（R）Core（TM）i5－2400＠3.10GHz，內(nèi)存：4.00GB，硬盤：1000GB；反匯編工具［9］：IDA 6.2.0111006，動(dòng)態(tài)記錄工具［10］：Pin 2.11。

4.2 測試結(jié)果

（1）基于控制結(jié)構(gòu)的密碼函數(shù)篩選測試

通過對(duì)大量密碼函數(shù)實(shí)例研究發(fā)現(xiàn)密碼函數(shù)內(nèi)部的基本塊個(gè)數(shù)不會(huì)太多，核心基本塊常常采用自身循環(huán)結(jié)構(gòu)，基本塊內(nèi)部的運(yùn)算類指令頻次比較高，并存在數(shù)條有效異或指令，因此依據(jù)逆向分析經(jīng)驗(yàn)設(shè)置疑似密碼函數(shù)篩選條件：①函數(shù)內(nèi)部基本塊個(gè)數(shù)不大于20；②存在基本塊循環(huán)且循環(huán)體內(nèi)包含代數(shù)運(yùn)算類指令頻次 （除去數(shù)據(jù)傳輸類指令）大于0.5；③存在基本塊循環(huán)且循環(huán)體內(nèi)包含至少一條有效異或指令；④存在基本塊循環(huán)且循環(huán)體內(nèi)包含至少一條乘、除類指令 （針對(duì)公鑰密碼）；⑤存在基本塊內(nèi)部指令條數(shù)不少于50且代數(shù)運(yùn)算類指令頻次 （除去數(shù)據(jù)傳輸類指令）大于0.8（針對(duì)Hash函數(shù)基本塊循環(huán)展開）；

上述條件③主要針對(duì)分組密碼和流密碼，條件④主要針對(duì)公鑰密碼，條件⑤主要針對(duì)基本塊循環(huán)展開的Hash函數(shù)；條件①與條件②，③，④，⑤之間為 “與”關(guān)系，條件②，③，④，⑤之間為 “或”關(guān)系。

針對(duì)壓縮軟件WinRar、局域網(wǎng)通信軟件FeiQ、密碼學(xué)工具SHA1KeyGen和BlowfishKGM分別進(jìn)行基于控制結(jié)構(gòu)的密碼函數(shù)篩選測試，結(jié)果見表1，其中FNbbl表示函數(shù)內(nèi)基本塊個(gè)數(shù)，Nbbl表示基本塊指令條數(shù)，F(xiàn)bbl表示基本塊運(yùn)算類指令頻次，NbblLoop表示基本塊循環(huán)個(gè)數(shù)，NComLoop表示普通循環(huán)個(gè)數(shù)，Tloop表示循環(huán)類型，基本塊循環(huán)與普通循環(huán)分別表示為B、C。根據(jù)目標(biāo)二進(jìn)制代碼反匯編結(jié)果中的函數(shù)個(gè)數(shù)、用戶函數(shù)個(gè)數(shù)和篩選出的疑似密碼函數(shù)個(gè)數(shù)，分別計(jì)算應(yīng)用軟件winrar3.91和FeiQ2.4的篩選比例分別為2.66%和1.04%；通過動(dòng)態(tài)調(diào)試分析，疑似密碼函數(shù)篩選結(jié)果包含了加解密主函數(shù)、密鑰產(chǎn)生函數(shù)和動(dòng)態(tài)S盒產(chǎn)生函數(shù)等密碼關(guān)鍵函數(shù)。

表1 測試結(jié)果中，密碼核心函數(shù)都包括了基本塊自身循環(huán)，winrar3.91采用的AES加解密函數(shù)循環(huán)控制結(jié)構(gòu)相同并且核心基本塊具有相同的運(yùn)算類指令頻次，并且加解密函數(shù)使用的S盒是動(dòng)態(tài)產(chǎn)生；SHA1KeyGen中的SHA1算法包含4個(gè)基本塊循環(huán)結(jié)構(gòu)，每輪循環(huán)執(zhí)行次數(shù)為16次；在FeiQ2.4和BlowfishKGM采用的BlowFish密碼函數(shù)核心基本塊循環(huán)中存在葉子函數(shù) （在控制流圖中，不包含函數(shù)調(diào)用的一類函數(shù)）調(diào)用，該葉子函數(shù)是一個(gè)運(yùn)算類指令頻次較高的基本塊，完成Feistel網(wǎng)絡(luò)結(jié)構(gòu)的相關(guān)功能。

表1 基于控制結(jié)構(gòu)的密碼函數(shù)篩選測試結(jié)果

（2）基于指令序列的密碼循環(huán)識(shí)別測試

根據(jù)產(chǎn)生機(jī)制，基于指令序列的循環(huán)主要分為循環(huán)展開和動(dòng)態(tài)執(zhí)行2種情況，Hash函數(shù)為了提高執(zhí)行效率，通常采用循環(huán)結(jié)構(gòu)展開的方式，在二進(jìn)制代碼反匯編結(jié)果中對(duì)應(yīng)一個(gè)高密度算術(shù)運(yùn)算的大基本塊，針對(duì)循環(huán)結(jié)構(gòu)展開的測試用例主要從Hash函數(shù)中選??；針對(duì)動(dòng)態(tài)執(zhí)行指令序列中的循環(huán)識(shí)別，采用動(dòng)態(tài)二進(jìn)制插樁工具Pin記錄下目標(biāo)代碼的執(zhí)行結(jié)果，并在設(shè)置密碼算法的開始與結(jié)束地址后進(jìn)行局部循環(huán)識(shí)別，測試用例主要從分組密碼和流密 碼中選取。測試結(jié)果詳見表2。

表2 基于指令序列的密碼循環(huán)識(shí)別測試結(jié)果

在測試結(jié)果中，選取的開始與結(jié)束地址包含了密碼算法的加密操作主要步驟，循環(huán)指令條數(shù)在總記錄指令條數(shù)的百分比范圍為21.47%－96.46%，具有較好的覆蓋率。

5 結(jié)束語

循環(huán)模式是鑒別密碼函數(shù)的重要特征之一，對(duì)于同一目標(biāo)二進(jìn)制代碼，動(dòng)態(tài)循環(huán)指令序列是靜態(tài)控制循環(huán)結(jié)構(gòu)展開執(zhí)行的結(jié)果，針對(duì)大數(shù)據(jù)量的動(dòng)態(tài)指令序列循環(huán)檢測效率不高的問題，可以根據(jù)靜態(tài)控制循環(huán)結(jié)構(gòu)識(shí)別結(jié)果，對(duì)代碼動(dòng)態(tài)執(zhí)行結(jié)果進(jìn)行局部循環(huán)識(shí)別與驗(yàn)證。

此外，根據(jù)二進(jìn)制代碼中靜態(tài)控制結(jié)構(gòu)和動(dòng)態(tài)指令序列的循環(huán)特征識(shí)別結(jié)果，并結(jié)合密碼函數(shù)循環(huán)體中內(nèi)存操作數(shù)據(jù)的高熵值特性以及循環(huán)體輸入、輸出數(shù)據(jù)的嚴(yán)格關(guān)聯(lián)關(guān)系進(jìn)行準(zhǔn)確篩選與定位。

［1］Ranjan Bose.Information theory coding and cryptography［M］.2nd ed.WU Chuankun，LI Hui，transl.Beijing：China Machine Press，2010 （in Chinese）.［Ranjan Bose.信息論、編碼與密碼學(xué) ［M］.2版.武傳坤，李徽，譯.北京：機(jī)械工業(yè)出版社，2010.］

［2］Christof Paar，Jan Pelzl.Understanding cryptography：A textbook for students and practitions ［M］.MA Xiaoting，transl.Beijing：QingHua University Press，2012 （in Chinese）.［Christof Paar，Jan Pelzl.深入淺出密碼學(xué)－常用加密技術(shù)原理與應(yīng)用 ［M］.馬小婷，譯.北京：清華大學(xué)出版社，2012.］

［3］Liu Tieming，Jiang Liehui，He Hongqi，et al.Researching on cryptographic algorithm recognition based on static characteris－tic－code ［C］／／Future Generation Information Technology Conference，2009：140－147.

［4］LI Jizhong，JIANG Liehui.Cryptogram algorithm recognition technology based on Bayes decision－making ［J］.Computer Engineering，2008，34 （20）：159－160 （in Chinese）.［李繼中，蔣烈輝.基于Bayes決策的密碼算法識(shí)別技術(shù) ［J］.計(jì)算機(jī)工程，2008，34 （20）：159－160.］

［5］Wang Zhi，Jiang Xuxian，Cui Weidong，et al.ReFormat：Automatic reverse engineering of encrypted messages ［R］.NC State University，2008.

［6］LI Yang，KANG Fei，SHU Hui.Cryptographic algorithm recognition based on dynamic binary analysis ［J］.Computer Engineering，2012，38 （17）：106－109 （in Chinese）.［李洋，康緋，舒輝.基于動(dòng)態(tài)二進(jìn)制分析的密碼算法識(shí)別 ［J］.計(jì)算機(jī)工程，2012，38 （17）：106－109.］

［7］Felix Gr bert.Automatic identification of cryptographic primitives in software［D］.Ruhr University Bochum，2010.

［8］Joan Calvet，JoséM Fernandez，Marion Jean－Yves.Aligot：Cryptographic function identification in obfuscated binary programs［C］／／ACM Conference on Computer and Communications Security，2012：169－182.

［9］Chris Eagle.The IDA pro book－the unofficial guide to the world’s most popular disassembler ［M］.SHI Huayao，DUAN Guiju，transl.Beijing：Post ＆ Telecom Press，2010 （in Chinese）.［Chris Eagle，IDA Pro權(quán)威指南 ［M］.石華耀，段桂菊，譯.北京：人民郵電出版社，2010.］

［10］Luk C，Cohn R，Muth R，et al.Pin：Building customized program analysis tools with dynamic instrumentation ［C］／／ACM SIGPLAN Conference on Programming Language Design and Implementation，2005：190－200.