二進制代碼級的密碼算法循環(huán)特征識別

李繼中，蔣烈輝，舒 輝

（1.信息工程大學，河南 鄭州450002；2.數學工程與先進計算國家重點實驗室，河南 鄭州450002）

0 引 言

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

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

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

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

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

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

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

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

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

1.2 密碼算法循環(huán)結構

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

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

2 基于回向邊遍歷的控制結構循環(huán)識別

在二進制代碼反匯編結果中，采用四元組G＝（START，END，N，E）對函數中基本塊之間的控制關系進行描述，其中N是結點 （基本塊）集合，E是邊集合，START∈N是一個沒有入向邊的開始結點 （函數入口），END∈N是一個沒有出向邊的結束結點 （函數出口）。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

步驟1 從TRACE中取指令Ik，若k＞n則退出；

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

步驟3 采用算法FindPotentialLoops（History，Ik）更新PotentialLoopsStack結構，并把Ik添加到History指令序列中，轉步驟1；

步驟4 在PotentialLoopsStack結構中按照從棧頂到棧底的順序，依次匹配每條潛在循環(huán)指令序列中的等待指令，若匹配轉步驟5，否則轉步驟6；

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

步驟6 彈出棧頂的潛在循環(huán)指令序列直至Potential－LoopsStack為空，轉步驟1；

步驟7 匹配一個循環(huán)體，把該循環(huán)體用Lid代替，并存儲在LoopStorage結構中，調整該潛在循環(huán)指令序列的等待指針指向該指令序列的第一條指令，轉步驟1。

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

算法：FindPotentialLoops （History，Ik）

輸入：已處理的指令序列History，當前指令Ik

輸出：更新潛在循環(huán)指令序列的堆棧結構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)歸約過程中，對于循環(huán)L＝ （body）m和L′＝（body）n，L和L′具有相同的循環(huán)實體，為了歸約外層的循環(huán)結構，則把L和L′視為相同的循環(huán)并存儲在LoopStorage結構中。

4 測試與結論

4.1 測試環(huán)境

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

4.2 測試結果

（1）基于控制結構的密碼函數篩選測試

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

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

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

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

表1 基于控制結構的密碼函數篩選測試結果

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

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

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

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

5 結束語

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

此外，根據二進制代碼中靜態(tài)控制結構和動態(tài)指令序列的循環(huán)特征識別結果，并結合密碼函數循環(huán)體中內存操作數據的高熵值特性以及循環(huá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.信息論、編碼與密碼學 ［M］.2版.武傳坤，李徽，譯.北京：機械工業(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.深入淺出密碼學－常用加密技術原理與應用 ［M］.馬小婷，譯.北京：清華大學出版社，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決策的密碼算法識別技術 ［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）.［李洋，康緋，舒輝.基于動態(tài)二進制分析的密碼算法識別 ［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權威指南 ［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.