基于決策樹的SM4 分組密碼工作模式識別

紀文桃，李媛媛，秦寶東，2

（1.西安郵電大學網絡空間安全學院，西安 710121；2.西安郵電大學無線網絡安全技術國家工程實驗室，西安 710121）

0 概述

密碼學包括2 個重要的分支，即密碼編碼學和密碼分析學。在信息時代，網絡安全已成為國家安全的重要組成部分，而密碼編碼學和密碼分析學在其中扮演著不可或缺的角色。目前，網絡空間中不僅存在多種數據類型，例如視頻、文本、圖像等，而且數據量大、冗余度高。因此，需要研究合理的數據處理方案。機器學習與密碼學的結合可實現對大量密文數據的有效處理。機器學習提供了聚類分類算法來分析數據，而密碼學則能保證數據安全。

密碼編碼學是一種保護信息在傳遞過程中不被第三方或者敵方所解讀、利用和竊取的技術，它解決的主要問題是信息的安全性問題。在現實生活中，總會存在一些用戶在未經信息持有者授權或者本就無意愿將信息共享的情況下，對所傳輸的信息進行非法獲取、惡意篡改以及刪除和偽造。密碼學者對此采取的措施主要是使用密碼分析技術來進一步完善所設計的密碼方案并優化方案中所包含的密碼算法。目前使用較多的密碼分析技術都是基于Kerckhoffs［1］這一原則，即在進行密碼分析時分析者是知道具體密碼算法的。根據可用于密碼分析的信息，密碼分析攻擊的手段可分為唯密文攻擊和已知明文攻擊、選擇明文攻擊、選擇密文攻擊和側信道攻擊。在現實情況下，密文數據是密碼分析者唯一容易獲得的信息。已知的密碼分析技術大部分是基于某種具體密碼算法或者在已知密文所使用的密碼算法的前提下設計的。因此，密碼分析的首要任務是對獲取的密文數據所使用的密碼算法進行識別。密碼算法識別不僅是進一步開展密碼分析的基礎，同時也是發現密碼算法是否存在安全隱患的一種重要方式，對增強密碼算法的安全性具有重要的影響。

本文通過GMSSL 對明文文本進行加密，生成與其對應的關于SM4 4 種工作模式的密文文本，并利用特征提取算法對這些密文文本進行特征提取，形成后續分類模型和測試階段所需要的特征向量。最后借助機器學習算法對國密算法SM4 的4 種工作模式進行模型構建和識別測試，以驗證本文方案的有效性。

1 相關工作

基于密文特征的密碼體制識別往往都同機器學習技術互相配合［2］。2011 年，MANJULA 和ANITHA［3］提出基于C4.5 決策樹的密碼體制識別方案。該方案提取了8 種密文特征，對11 種加密算法進行識別，包括古典算法、分組密碼算法和非對稱加密算法，并從訓練文件數量和所用密文文件大小兩方面進行試驗，得到的識別率為70%～75%。2012 年，CHOU 等［4］提出利用支持向量機對密碼體制進行識別。通過對數據集的分析發現密碼的工作模式主導著分類任務的執行。該方案提取了12 種密文特征，對高級加密標準（Advance Encryption Standard，AES）和數據加密標準（Data Encryption Standard，DES）分別在電碼本（Electronic Codebook，ECB）模式和密碼分組鏈接（Cipher-Block Chaining，CBC）模式下進行算法識別。實驗結果表明，對每個明文使用CBC 模式和隨機初始向量時性能較差，而使用ECB 模式時，某些數據集的性能相對較好。2013 年，MISHRA 等［5］提出并實現了將模式識別和決策樹結合從而識別分組密碼和流密碼的方案。該方案包括3 個子模塊技術，即塊長度/流檢測、熵/重現分析和基于字典/決策樹的方法。這3 個部分的實現大幅提高了密碼算法的識別率。2013 年，WILLAM 等［6］提出基于神經網絡的區分攻擊方法，其利用語言學和信息檢索方法，從MARS、RC6、Rijndael、Serpent、和Twofish 加密的密文中生成分類模型，然后將獲取的密文集合提交到“聚類過程”，并將結果輸入到分類器中，從而得到以上5 種加密算法的分類結果。2014 年，LOMTE 等［7］對WILLAM 等提出的方案做進一步研究。后者在聚類識別過程中使用單一的密鑰進行加密的，而前者在訓練和測試過程中設置了不同的密鑰，相比較而言，識別率有所下降。2015 年，吳楊等［8-9］提出了基于k 均值（K-means）聚類的密碼體制分層識別方案，對5 種分組密碼（AES、Camellia、DES、3DES、SMS4）進行兩兩識別，其在特征提取部分使用了密文隨機性度量值的方法，大幅提高了典型分組密碼的識別率，高達90%左右。2016 年，MELLO 等［10］在ECB 模式下，對7 種不同語言編寫的純文本文件使用7 種密碼算法進行編碼。這些文件提供了6 種數據挖掘算法的信息，以用于識別文本加密的算法。通過大量的元數據和大量的耗時計算，得到了非常高的識別率。2016 年，TAN 等［11］提出一種基于支持向量機的密碼體制識別方案，對5 種常見的分組密碼算法進行識別，分別為AES、Blowfish、3DES、RC5和DES，其對這5 種算法在4 種不同的情況下進行試驗，即訓練和測試密文的密鑰是否相同，在此基礎上，利用其他4種加密算法與AES進行一一識別，當訓練和測試階段的密鑰相同時其識別率較高。2017 年，BARBOSA 等［12］提出對加密的多媒體文件進行密碼算法識別。該過程使用4 種加密算法對音頻和視頻文件進行加密，然后將加密的文件提交給數據挖掘算法，并將其產生的混淆矩陣編譯成圖表。2017 年，黃良韜等［13］提出基于隨機森林的密碼體制分層識別方案，并介紹了3 種簇分方式，即CM-簇分、CSN-簇分和CSBP-簇分。首先將已加密的文件按照大的分類進行歸類，然后從每一類中區分出具體的密碼算法。實驗結果表明，加入分層的方案較單分的密碼體制識別效果更佳。在以往的密碼體制識別中，多數密碼算法都是在ECB 模式下的，2018 年，TAN 等［14］提出基于CBC 模式的密碼體制識別方案。該方案用5 種算法進行多類識別和一對一識別，在此基礎上考慮了訓練和測試時密鑰是否相同以及初始向量是否相同的情況，其中一對一識別是將AES 與其他4 種算法進行識別。2019 年，趙志誠等［15］采用隨機性測試進行密文特征的提取，提出了基于隨機森林的識別方案。該方案中對6 種分組密碼進行兩兩識別，在不同的特征下其識別率各有差異，部分特征下其識別率能達到80%以上。

上述工作主要針對不同密碼算法進行識別，或者在特定工作模式下進行識別，而缺乏對分組密碼工作模式的識別，特別是國密SM4 分組密碼算法的工作模式識別。分組密碼的工作模式又對密碼算法的識別起著主導作用，這將對輿論分析、互聯網審查、電子取證和網絡監控具有推進作用。無論是對不同算法識別還是對分組密碼工作模式的識別，都利用機器學習將其視為模式分類的問題，使用機器學習的各種分類方法來嘗試捕獲加密后的密文文件中隱含的行為。通過機器學習算法對大量密文文本進行分析計算，生成對應的分類模型，再將測試文本投入分類器中進行比較，最后得到分類結果。這樣就可以避免人為地去分析論證密碼工作模式本身的區別，而是將這一行為交由機器學習去完成，通過與統計學方法的結合，智能地挖掘和分析在同一明文文本集下經由不同工作模式加密后產生的密文文本之間所隱含的不同信息。本文主要研究SM4 分組密碼工作模式識別方法。SM4 算法是我國國家密碼管理局提出的一種分組長度和密鑰長度均為16 字節的分組密碼算法，適用于無線局域網產品。它的安全性能較高，可以抵抗差分、線性和代數等分析技術。SM4 算法現已實現的工作模式有6 種，在本文中用到了密文分組鏈接模式（CBC）、密文反饋模式（CFB）、計數器模式（CTR）、輸出反饋模式（OFB）這4 種。若直接使用SM4算法加密消息，它的安全性是非常脆弱的。為了在不同的場景中更好地保護明文的安全性，需要借助不同的工作模式。對工作模式的識別能夠提高密碼算法的安全性，從而更好地抵抗密碼攻擊。

本文提出基于C4.5 的分組密碼工作模式識別方案并對國密SM4 算法的4 種工作模式進行識別。首先利用加密工具在不同的工作模式下對大量的文本文件進行加密，得到密文文件；然后構造訓練階段和測試階段所需的特征向量空間，該空間是由特征提取算法對密文文件處理后得到的，每個特征向量中包括5 個值，即大寫字母數量、小寫字母數量、數字字符數量、其他字符數量和標簽值。在此基礎上，在訓練階段通過對特征空間的學習生成決策樹，在測試階段根據生成的決策樹進行決策，最后將決策值與標簽值相比較得到分類結果。

2 系統模型

本文設計基于決策樹的密碼體制識別系統，系統模型如圖1 所示，其中包含4 個部分：1）生成特定工作模式的密文文件；2）提取密文特征；3）生成決策樹模型；4）進行測試分類。

圖1 分組密碼工作模式識別模型Fig.1 Block-cipher working mode recognition model

分組密碼的工作模式［16］包括電子密碼本（ECB）模式、密文分組鏈接模式（CBC）、密文反饋模式（CFB）、輸出反饋模式（OFB）和計數器模式（CTR）。在該系統模型中，使用了國密SM4 算法的4 種工作模式，電子密碼本模式除外。CBC 模式相比較其他4 種工作模式較為流行，除第一個明文分組與隨機產生的初始向量［17］異或后加密生成密文外，其他明文分組都與前一個密文輸出進行異或后生成相應的密文。在信息傳輸過程中，只要一個明文分組出現錯誤，則會影響其后的密文分組。因此它的加密過程不能并行化，相反解密過程不受該情況的影響，從而可實現并行計算。CFB 模式首先對隨機產生的初始化向量加密，將加密后的結果與明文分組相異或，而后續的過程是對前一個分組加密后的結果進行加密，然后與當前明文相異或，得到對應的密文。與CBC 模式相比，CFB 模式的錯誤傳播性質更為突出，一個明文分組的錯誤可能會導致其后所有密文分組出現錯誤。不僅僅是加密，其解密過程也依賴其他的明文分組，因此，其加密過程和解密過程均不能實現并行化。OFB 模式的第一步操作與CFB 相同，不同的是OFB 把隨機初始向量加密后的結果作為下一分組的輸入，對該輸入加密后再與明文分組進行異或運算得到對應的密文分組。OFB 模式規避了CFB模式和CBC 模式由于明文出錯而帶來的錯誤傳播的風險，但隨之而來的是一旦密文被惡意篡改，檢測工作將變得不再容易。CTR 模式是將計數器進行分組，將每個計數器分組加密后與明文分組進行異或運算，得到對應的密文分組。每個分組的加密與解密過程相互獨立，不會有錯誤傳輸的困擾，也因此加解密均可并行。

將明文加密成特定密碼工作模式的密文文件后，再對其進行特征提取。特征提取的工作是最重要也是最難的一步，因為其本質是對密數據的處理和分析，而且它對后續模型的生成和分類的結果起著決定性的作用。特征提取的方法很多，如統計學方法、隨機性檢測［18-19］、密碼學中的熵特性和信號中的頻域特征等。本文借助統計學方法和信息熵的結合來實現密文數據的特征提取。首先利用統計學方法對密文文本中的大小寫字符、數字字符以及特殊字符的個數進行統計，然后分別計算其對應的熵，以此為基礎形成特征向量，進而得到特征向量空間。

對密文數據特征提取后即進入學習和分類的過程，這是機器學習算法的本質。機器學習算法包括2 個階段：第1 個階段是訓練階段，即將得到向量空間的一部分傳遞給決策樹算法進行學習，并生成分類模型，也稱決策樹模型；第2 個階段為測試階段，即將向量空間的另一部分投入到機器學習算法中進行測試，依據訓練階段生成的決策樹模型來進行分類。訓練階段和測試階段的向量空間中都包含密文的特征，而決策樹算法是有監督學習算法，它的學習標簽包含在訓練階段，而在測試階段將標簽隱藏，待測試完成后，用決策樹模型預測的結果與測試數據所隱藏的標簽進行對比，就可得到實驗的結果。

在得到結果之前，要借助決策樹算法［20］來生成模型以及進行分類。決策樹算法包括ID3 和C4.5 算法，ID3 算法主要借助信息熵和信息增益作為測試屬性的衡量標準，而C4.5 是在ID3 的基礎上對信息增益加以調節得到分裂信息，用分裂信息和信息增益率來劃分屬性。ID3 在對屬性的劃分中往往偏向于選擇樣本較多的，而C4.5 采用信息增益率規避了這一點，并且C4.5 算法在樹的構造過程中，不僅能夠將連續數據進行離散化處理，而且還可以對樹進行剪枝處理，從而得到更優的樹。本文中選用的是C4.5，具體操作如下：

1）假設有包含N種屬性的數據集S 和包含K種屬性的子集合A。令pi表示每個目標屬性的概率，|Si|表示子集Si的樣本數，|S|表示數據集S 的樣本數。將數據集按照每一個屬性進行劃分，并計算其對應的信息熵、分裂信息和信息增益率，具體如下：

信息熵：

2）將上一步中計算出的每一個屬性的信息增益率進行比較，選擇最大的一個作為決策樹的節點。

3）在子節點上利用剩余的屬性繼續執行第1 步和第2 步，直到該節點為純葉子結點。

4）對生成的決策樹進行剪枝處理，包括先剪枝和后剪枝2 種方法，以防止過擬合。

該算法結合密文特征提取的結果得到上文描述的信息熵、信息增益和信息增益率，對數據集進行合理高效的劃分，在本地生成用于測試階段判斷分類的樹結構，根據這個樹結構得到所需的分類結果。

3 實驗結果與分析

在整個實驗過程中，本文用到的實驗工具包括GMSSL、VS2010 和VS Code。GMSSL 同OpenSSL一樣，都是密碼工具箱。它實現了本文所需的SM4加密算法，即在CBC 模式、CFB 模式、CTR 模式和OFB 模式下的SM4 密碼算法對1 000 份明文文本加密，得到4 種工作模式下各1 000 份的密文文本。明文是隨機選取的大小在1 KB～200 KB 之間的文本文檔，都是分組規模的倍數。密文特征提取的工作是由VS2010 所提供的C 語言編寫的特征提取算法所完成，得到大小寫字符、數字字符和特殊字符的統計個數。4 000 份密文文本都會產生一組包含4 個特征值的特征向量，從而構成所需的特征空間。決策樹算法是在VS Code 上用python 語言實現，進而為訓練階段學習模型的生成以及測試階段分類的實現提供了方法。在訓練階段和測試階段所用的密鑰空間是相同的，所有的密鑰都是隨機值，并且測試階段和訓練階段文本的大小是相同的。在同一密鑰空間下，對同一工作模式下的不同文本文檔的密鑰是不同的。本文構建了3 種實驗模型，分別為混合分類模型、混合文本大小分類模型和一對一分類模型。混合分類模型是將4 種工作模式的樣本直接投給分類器進行區分；混合文本大小分類模型是在混合分類的基礎上，對密文文本進行甄選，將不同文本大小作為分類的影響因子；一對一分類模型是將4 種工作模式兩兩組合，每組單獨進行測試。在混合分類模型中，所用到的訓練樣本數和測試樣本數是相同的并且都包含于同一個密鑰空間。此外，該模型將樣本數量作為測試結果的影響因子。在這3 種模型中，正確率指的是測試數據根據訓練模型的預測與其標簽是否一致的數量（即預測結果正確的數量）與參與測試的數據數量的比值，用公式表示如下：

表1 給出了測試結果隨著樣本數量增加的變化情況。在每次測試中，4 種工作模式的樣本數都是平均的。當樣本總數從8 個增加到100 個時，其正確率也逐漸增加，從16.7%增加至26.5%。當樣本數較大時，測試結果的正確率更接近于穩定值25%。

表1 混合分類模型測試結果Table 1 Test result of hybrid classification model

在混合分類模型的基礎上，混合文本大小分類模型將文本大小也考慮為其影響因素。測試結果如表2所示。可以看出，該模型同時受到文本大小和樣本數目的影響，其測試結果隨著兩者逐漸增大有著微小的變化。與混合分類模型相比，其測試結果更為穩定。

表2 混合文本大小分類模型測試結果Table 2 Test result of mixed text size classification model

通過上述分類結果可以看出，以上2 種分類模型對SM4 算法的4 種工作模式，即密文鏈接模式、密文反饋模式、輸出反饋模式和計數器模式，混合時的分類效果并不顯著，其識別正確率范圍為16%～26%。如果樣本總數超過100 時，其識別正確率在20%以上。

表3給出了一對一分類模型的分類結果。將CBC、CFB、OFB 和CTR 進行兩兩組合，得到6 組分類樣本。在每組分類樣本中，訓練階段和測試階段的樣本總數均為1 000 例。其中，CBC vs CFB 的識別率最高，測試結果達到97.61%。而CFB vs OFB 的識別率最低，其測試結果達到97.36%。從表3 還可以看到，4 種工作模式分類的結果是非常顯著的，其正確率高達95%以上，只有OFB 與CTR 識別的結果為91.67%。通過表1～表3的分類結果可以看出，將4 種工作模式混合傳遞給分類器進行分類的結果并不明顯，而當對其進行一對一分類時，分類結果良好。

表3 一對一分類模型測試結果Table 3 Test result of one-to-one classification model

4 結束語

本文提出一種基于決策樹C4.5 算法的SM4 分組密碼工作模式識別方案，并分別以混合分類、混合文本大小分類、一對一分類這3 種情況測試該方案的可行性和有效性。在本文方案中，訓練階段和測試階段所用的樣本數目相同，并且對明文文本加密時兩階段使用相同的密鑰空間。在進行一對一分類時，CBC 模式與CFB、OFB、CTR 模式之間的區分正確率都在90%以上，但不足之處在于將4 種工作模式混合后的區分率并不高。下一步將結合一些優化算法對C4.5 算法本身進行優化，以便更好地應用于本文方案，同時對密文進行特征提取時增加提取的特征數量，進而完善特征向量空間。此外，還將嘗試結合其他的機器學習算法進一步提高方案性能。