一種基于密文分析的密碼識(shí)別技術(shù)*

丁 偉，談 程

（1.海軍南海艦隊(duì)參謀部信息保障處，廣東 湛江 524001；2.中國電子科技集團(tuán)公司第三十研究所，四川 成都 610041）

一種基于密文分析的密碼識(shí)別技術(shù)*

丁 偉1，談 程2

（1.海軍南海艦隊(duì)參謀部信息保障處，廣東 湛江 524001；2.中國電子科技集團(tuán)公司第三十研究所，四川 成都 610041）

密碼分析過程中，密碼分析者往往不知道密碼系統(tǒng)使用了哪一種密碼，導(dǎo)致密碼分析工作困難重重。因此，介紹一種基于密文分析的密碼識(shí)別方法。首先介紹建立的密碼識(shí)別系統(tǒng)的工作原理和過程，然后利用該系統(tǒng)對(duì)5類常見分組密碼（AES、Blowfish、3DES、RC5和DES）進(jìn)行識(shí)別。通過實(shí)驗(yàn)結(jié)果分析發(fā)現(xiàn)，當(dāng)訓(xùn)練密文和測(cè)試密文的密鑰一致時(shí)，識(shí)別率能達(dá)到90%左右；而當(dāng)密鑰不一致時(shí)，系統(tǒng)仍能夠以較高的識(shí)別率對(duì)AES與其他四類密碼進(jìn)行兩兩識(shí)別。

密碼識(shí)別系統(tǒng)；密碼識(shí)別；SVM分類器；分組密碼；識(shí)別率

0　引 言

密 碼分析學(xué)專門研究密碼破譯方法，并用于衡量密碼體制安全性。它的一般原理為：密碼分析者在不知道密碼系統(tǒng)使用的密鑰情況下，從截獲得到的密文推斷出明文消息或密鑰。Kerckhoffs對(duì)密碼分析的基本假設(shè)中，闡述了密碼分析者已知密碼算法及其實(shí)現(xiàn)的全部細(xì)節(jié)，現(xiàn)有的密碼分析技術(shù)也幾乎都建立在密碼算法已知的基礎(chǔ)上。但是，實(shí)際上密碼分析者通常獲得的大部分都是密文數(shù)據(jù)，且對(duì)應(yīng)的密碼算法是未知的。密碼算法已知是進(jìn)行密碼分析的先決條件，如果密碼分析者在不知道密碼算法實(shí)現(xiàn)細(xì)節(jié)的情形下對(duì)密碼系統(tǒng)所使用的密碼進(jìn)行識(shí)別，我們稱這一過程為密碼識(shí)別。進(jìn)一步地，如果密碼分析者僅掌握一些密文數(shù)據(jù)，在這種場景下的分析過程稱之為基于密文分析的密碼識(shí)別。

從公開文獻(xiàn)來看，國內(nèi)外關(guān)于密碼識(shí)別技術(shù)的研究并不多見。就目前來看，大部分對(duì)密碼識(shí)別技術(shù)的研究都是通過逆向分析手段，分析軟硬件中使用的密碼，如國內(nèi)解放軍信息工程大學(xué)蔣烈輝、舒輝教授的團(tuán)隊(duì)［1-3］。此外，國外有少部分學(xué)者對(duì)基于密文分析的密碼識(shí)別技術(shù)有一定研究。概括地講，對(duì)密碼識(shí)別技術(shù)的研究主要包括兩個(gè)方向：一是利用逆向分析技術(shù)進(jìn)行密碼識(shí)別；二是基于唯密文進(jìn)行密碼識(shí)別。本文針對(duì)方向二展開研究。相比方向一，方向二不需要掌握包含密碼算法的設(shè)備或模塊，僅基于一些密文數(shù)據(jù)來識(shí)別密碼，其研究更符合實(shí)際應(yīng)用場景。

1　技術(shù)發(fā)展現(xiàn)狀分析

基于密文分析進(jìn)行密碼識(shí)別的思想首先在古典密碼的識(shí)別中得到了實(shí)現(xiàn)。Pooja M設(shè)計(jì)了一種分類古典密碼的方案［4］，包括置換密碼、代換密碼、維吉利亞密碼以及置換代換密碼。該方案分為四步，通過排除方式進(jìn)行選擇，并基于字母使用頻率進(jìn)行分析。從應(yīng)用角度講，研究古典密碼識(shí)別已沒有多大實(shí)際意義。Manindra等人在現(xiàn)代密碼識(shí)別領(lǐng)域進(jìn)行了更深入的研究［5-7］。文獻(xiàn)［5］對(duì)分組密碼DES和IDEA進(jìn)行識(shí)別研究，利用線性規(guī)劃思想構(gòu)造分類器，將密文分成大小為320 bit的塊，以密文塊為單位輸入進(jìn)行預(yù)處理。先獲得好的分類器，然后根據(jù)不同密文情形分別建立四種模型，包括靜態(tài)模型、動(dòng)態(tài)模型、拓展動(dòng)態(tài)模型和子文件索引模型，并進(jìn)行了相關(guān)的識(shí)別驗(yàn)證。文獻(xiàn)［6］提出了重復(fù)加密模型，但實(shí)驗(yàn)結(jié)果并不是很理想，于是提出隨機(jī)密鑰解密模型，基本思路是用隨機(jī)產(chǎn)生密鑰解密密文，將得到的“明文”作為識(shí)別模型的輸入進(jìn)行密碼算法識(shí)別。文獻(xiàn)［7］通過改變各項(xiàng)參數(shù)對(duì)分類器性能進(jìn)行優(yōu)化調(diào)整，同時(shí)運(yùn)用支持向量機(jī)得到一些較好的分類器。

A. Soni首次提出用Adaboost算法對(duì)密碼進(jìn)行分類［8］，通過構(gòu)建比隨機(jī)猜測(cè)稍好的弱分類器，對(duì)各弱分類器進(jìn)行訓(xùn)練，最終得到一個(gè)強(qiáng)分類器用于對(duì)密碼進(jìn)行識(shí)別，但最終平均識(shí)別率僅維持在55%左右。S. Mishra等人將密文數(shù)據(jù)檢測(cè)、熵值分析和字典決策樹法結(jié)合使用［9］，對(duì)AES、DES和Blowfish密碼進(jìn)行識(shí)別。他指出，分組密碼二進(jìn)制密文中0和1幾乎是均勻分布的，尤其是AES密碼。但在數(shù)據(jù)量足夠大的情況下，還是能捕獲到DES和Blowfish密文的一些特征。另外，有學(xué)者對(duì)AES標(biāo)準(zhǔn)的5個(gè)候選算法進(jìn)行識(shí)別研究［10-12］。R. Torres等人［10］運(yùn)用以Calisnki-Harabasz索引作為評(píng)價(jià)函數(shù)的遺傳算法來尋找不同密碼對(duì)應(yīng)的密文中隱藏特征。W. Souza等人［11］運(yùn)用聚類和分類的思想，雖然在CBC模式下根據(jù)訓(xùn)練得到的特征對(duì)密文分類效果不佳，但是仍然可以對(duì)密文進(jìn)行聚類。V. Lomte等人［12］以神經(jīng)網(wǎng)絡(luò)為模型，提出了語言法和信息恢復(fù)法對(duì)各密文進(jìn)行識(shí)別。

基于密文分析的密碼識(shí)別技術(shù)雖能夠克服基于逆向分析的密碼識(shí)別技術(shù)的不足，更符合實(shí)際應(yīng)用場景，但該技術(shù)處于起步階段。目前，國內(nèi)尚無關(guān)于這方面的公開研究成果，國外也僅有少數(shù)人研究?？傮w來講，當(dāng)前基于密文分析的密碼識(shí)別工作僅僅做了一些探索性研究，很多實(shí)驗(yàn)密文數(shù)據(jù)不符合實(shí)際情形，如所有密文對(duì)應(yīng)同一密鑰，且沒有嚴(yán)格限制測(cè)試所用的密文文件大小。在真實(shí)密碼分析場景中，截獲的密文數(shù)據(jù)包大小有限，且多次截獲的密文對(duì)應(yīng)的密鑰很可能不一致。本文充分考慮密文文件大小和加密密鑰一致性等問題，針對(duì)AES、Blowfish、3DES、RC5和DES這5種常見的分組密碼進(jìn)行識(shí)別研究。

2　識(shí)別模型建立

本文考慮ECB模式下對(duì)幾種常見分組密碼進(jìn)行識(shí)別?；跈C(jī)器學(xué)習(xí)主流算法之一支持向量機(jī)（Support Vector Machine，SVM）構(gòu)造分類器，從而建立基于密文分析的密碼識(shí)別模型和系統(tǒng)，原理如圖1所示。在該密碼識(shí)別系統(tǒng)中，按要求輸入密文數(shù)據(jù)，即可輸出得到識(shí)別出的密碼名稱。

圖1　密碼識(shí)別系統(tǒng)的基本原理

整個(gè)密碼識(shí)別過程分為兩個(gè)步驟進(jìn)行。首先，利用已知密碼名稱的密文文件對(duì)SVM分類器進(jìn)行訓(xùn)練，然后通過這些分類器對(duì)未知密碼名稱的密文文件進(jìn)行識(shí)別。我們建立的密碼識(shí)別系統(tǒng)的具體工作過程，如圖2所示。

圖2　密碼識(shí)別系統(tǒng)的工作過程

首先，分別生成若干基于AES、Blowfish、3DES、RC5和DES密碼算法的密文文件，其中一部分作為訓(xùn)練文件，剩余部分作為測(cè)試文件。通過從訓(xùn)練密文文件中提取密文特征，進(jìn)而篩選出關(guān)鍵特征構(gòu)建密文特征匹配庫；結(jié)合SVM算法，建立基于密文分析的密碼識(shí)別模型。提取測(cè)試密文文件的密文特征，然后傳送至識(shí)別模型即可進(jìn)行密碼識(shí)別?；诿芪姆治龅拿艽a識(shí)別主要由K個(gè)分類器來完成，其中K由密文特征匹配庫中的密碼種類數(shù)k決定，具體分為兩種情形。

情形一，一對(duì)多。每一個(gè)分類器將其中的一類密碼和余下k-1類密碼分開（將余下k-1類密碼看成同一類），則分類器個(gè)數(shù)K=k。

情形二，一對(duì)一。任意兩類密碼之間構(gòu)造一個(gè)分類器，每個(gè)分類器識(shí)別兩種不同類別的密碼，則分類器個(gè)數(shù)K=k（k-1）/2。

本文考慮一對(duì)一的方式進(jìn)行密碼識(shí)別。計(jì)數(shù)器用于對(duì)分類結(jié)果進(jìn)行統(tǒng)計(jì)，從而識(shí)別得到測(cè)試密文文件所用的密碼。通過產(chǎn)生大量測(cè)試密文文件，觀察識(shí)別結(jié)果的同時(shí)，不斷調(diào)整識(shí)別模型中的算法參數(shù)，從而優(yōu)化密碼識(shí)別系統(tǒng)，改善密碼識(shí)別效果。

3　實(shí)驗(yàn)結(jié)果與分析

根據(jù)前面建立的基于密文分析的密碼識(shí)別系統(tǒng)，對(duì)AES、Blowfish、3DES、RC5和DES密碼進(jìn)行識(shí)別。準(zhǔn)備220個(gè)相同大小的明文文本文件，對(duì)應(yīng)于上述各密碼算法，在ECB模式下加密得到1 100個(gè)密文文件（每種密碼對(duì)應(yīng)220個(gè)密文文件）。對(duì)應(yīng)每一種密碼，40個(gè)密文文件用于訓(xùn)練，剩余的180個(gè)密文文件按照每組20個(gè)進(jìn)行分組，進(jìn)行9次測(cè)試。顯然，加密密鑰和密文文件大小對(duì)識(shí)別率會(huì)產(chǎn)生較大影響，因此在實(shí)驗(yàn)中需考慮這些因素。

3.1 訓(xùn)練密文和測(cè)試密文的密鑰一致

首先考慮訓(xùn)練密文和測(cè)試密文對(duì)應(yīng)的加密密鑰一致的情形。對(duì)AES、Blowfish、3DES、RC5和DES密文文件的識(shí)別結(jié)果如表1所示。

表1　密鑰一致時(shí)的識(shí)別結(jié)果（5類密碼）

第1列表示訓(xùn)練和測(cè)試密文文件的大小，第2列表示9次測(cè)試的平均識(shí)別率，第3列表示這9個(gè)識(shí)別率的標(biāo)準(zhǔn)偏差值。從表1中數(shù)據(jù)可以看出，密文文件越大，識(shí)別率越高。當(dāng)密文文件大小為4 KB時(shí)，平均識(shí)別率雖然只有29.67%，但仍高于隨機(jī)猜測(cè)正確率20%。標(biāo)準(zhǔn)差值反映了識(shí)別結(jié)果的可靠性。一般來說，該值越小，說明識(shí)別結(jié)果可信程度越高。當(dāng)密文文件不低于100 KB時(shí)，識(shí)別率幾乎達(dá)到95%以上，且標(biāo)準(zhǔn)差也小于5%，說明提出的識(shí)別系統(tǒng)在密文文件較大時(shí)能達(dá)到一個(gè)較好的識(shí)別效果。當(dāng)密文文件大小為20 KB時(shí)，雖然平均識(shí)別率達(dá)到85.11%，但標(biāo)準(zhǔn)差達(dá)到了9.75%，說明在此條件下進(jìn)行識(shí)別并不能保證每次都能達(dá)到較高的識(shí)別率。

對(duì)于Blowfish、3DES、RC5和DES密碼，分組長度為64 bit，而AES的分組長度為128 bit，因此考慮對(duì)除AES外的其余四種密碼對(duì)應(yīng)的密文文件進(jìn)行識(shí)別。如表2所示，當(dāng)密文文件大小為100 KB或500 KB時(shí)，識(shí)別率達(dá)到了100%，且標(biāo)準(zhǔn)差為0。

表2　密鑰一致時(shí)的識(shí)別結(jié)果（4類密碼，AES除外）

比較表1和表2的結(jié)果，顯然可以發(fā)現(xiàn)Blowfish、3DES、RC5和DES比AES更容易被識(shí)別。當(dāng)密文文件為4 KB時(shí)，表1中的識(shí)別率僅為29.67%，而表2中達(dá)到了98.33%。

3.2訓(xùn)練密文和測(cè)試密文的密鑰不一致

當(dāng)訓(xùn)練密文和測(cè)試密文對(duì)應(yīng)的加密密鑰一致時(shí)，只要密文文件足夠大，提出的密碼識(shí)別系統(tǒng)能夠以一個(gè)較高的識(shí)別率識(shí)別出上述幾種分組密碼。在現(xiàn)實(shí)環(huán)境下，我們能夠以任意密鑰生成任意多的訓(xùn)練密文，而截獲到的密文（即測(cè)試密文）對(duì)應(yīng)的密鑰卻是未知的。因此，基本上排除了訓(xùn)練密文和測(cè)試密文對(duì)應(yīng)的加密密鑰一致的可能性，密鑰不一致更符合實(shí)際情形。對(duì)應(yīng)于AES、Blowfish、3DES、RC5和DES密碼，各生成9組密文文件，且訓(xùn)練密文文件和9組密文文件的密鑰均不一致。如表3所示，當(dāng)密文文件大于20 KB時(shí)，平均識(shí)別率大概維持在35%～40%范圍。顯然，訓(xùn)練密文和測(cè)試密文的密鑰不一致時(shí)的識(shí)別效果要比密鑰一致時(shí)差很多，但仍高于隨機(jī)猜測(cè)正確率。

表3　密鑰不一致時(shí)的識(shí)別結(jié)果（5類密碼）

表4為密鑰不一致時(shí)，Blowfish、3DES、RC5和DES密文的識(shí)別結(jié)果。憑直覺認(rèn)為，識(shí)別的密碼種類數(shù)減少，平均識(shí)別率就應(yīng)提高。但表4中的最大平均識(shí)別率只有24.86%，甚至低于25%的隨機(jī)猜測(cè)正確率。這表明當(dāng)訓(xùn)練密文和測(cè)試密文的密鑰不一致時(shí)，系統(tǒng)對(duì)Blowfish、3DES、RC5和DES這四種密碼的識(shí)別是失敗的。在加入AES密文文件后，反而無形中提高了識(shí)別率，表明當(dāng)訓(xùn)練密文和測(cè)試密文的密鑰不一致時(shí)，AES的密文特征與其他四種密碼存在較顯著的差異。

表4　密鑰不一致時(shí)的識(shí)別結(jié)果（4類密碼，AES除外）

3.3 密碼間兩兩識(shí)別

由表3和表4可知，當(dāng)訓(xùn)練密文和測(cè)試密文的密鑰不一致時(shí)，對(duì)多類密碼進(jìn)行識(shí)別的效果不太理想。在密鑰不一致的基礎(chǔ)上，考慮對(duì)這5類密碼進(jìn)行兩兩識(shí)別，識(shí)別結(jié)果如表5所示。當(dāng)密文文件大于20 KB，AES和其他四種密碼進(jìn)行兩兩識(shí)別的識(shí)別率總能達(dá)到85%以上。而Blowfish、3DES、RC5和DES間進(jìn)行兩兩識(shí)別，識(shí)別率維持在50%左右，表明此情形下的密碼識(shí)別是不成功的。這些結(jié)果也驗(yàn)證了3.2節(jié)給出的結(jié)論。

表5　密鑰不一致時(shí)的5類密碼間兩兩識(shí)別結(jié)果/（%）

4　結(jié) 語

本文提出一種基于密文分析的密碼識(shí)別技術(shù)，并建立密碼識(shí)別系統(tǒng)，針對(duì)AES、Blowfish、3DES、RC5和DES5類常見分組密碼展開識(shí)別研究。通過密碼識(shí)別實(shí)驗(yàn)發(fā)現(xiàn)，當(dāng)訓(xùn)練密文和測(cè)試密文的加密密鑰一致時(shí)，識(shí)別效果較好；當(dāng)加密密鑰不一致時(shí)，識(shí)別效果較差，但可以很好地對(duì)包含AES在內(nèi)的密碼進(jìn)行兩兩識(shí)別。

［1］ 李繼中，蔣烈輝，尹青等.基于Bayes決策的密碼算法識(shí)別技術(shù)［J］.計(jì)算機(jī)工程，2008，34（20）：159-160，163. LI Ji-zhong，JIANG Lie-hui，YIN Qing，et al.Cryptogram Algorithm Recognition Technology based on Bayes Decision-making［J］.Computer Engineeri ng，2008，34（20）：159-160，163.

［2］ 張經(jīng)緯，舒輝，蔣烈輝等.公鑰密碼算法識(shí)別技術(shù)研究［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2011，32（10）：3243-3246，3273. ZHANG Jing-wei，SHU Hui，JIANG Lie-hui，et al.Research on Public Key's Cryptography Algorithm Recognition Technology［J］.Computer Engineering and Design，2011，32（10）：3243-3246，3273.

［3］ 李繼中，蔣烈輝，舒輝等.基于動(dòng)態(tài)循環(huán)信息熵的密碼函數(shù)篩選技術(shù)［J］.計(jì)算機(jī)應(yīng)用， 2014，34（04）：1025-1028，1033. LI Ji-zhong，JIANG Lie-hui，SHU Hui，et al.Technique of Cryptographic Function Filtration based on Dynamic Loop Information Entropy［J］.Journal of Computer Applicati-ons，2014，34（04）：1025-1028，1033.

［4］ Pooja M.Classification of Ciphers［D］.Department ofComputer Science and Engineering，Indian Institute of Technology，2001.

［5］ Girish C.Classication of Modern Ciphers［D］.Department of Computer Science and Engineering，Indian Institute of Technology，2002.

［6］ MBrahmaji M.Classication of RSA and Idea Ciphers［D］. Department of Computer Science and Engineering，Indian Institute of Technology，2003.

［7］ Saxena G.Classication of Ciphers Using Machine Learning［D］.Department of Computer Science and Engineering，Indian Institute of Technology，2008.

［8］ Soni A.Learning Encryption Algorithms from Ciphertext［R］.BTP report，Department of Computer Science and Engineering，Indian Institute of Technology.

［9］ Mishra S，Bhattacharjya A.Pattern Analysis of Cipher Text：A Combined Approach［C］.2013 International Conference on Recent Trends in Information Technology：393-398.

［10］ Torres R，Oliveira G，Xexéo J，et al.Identification of Keys and Cryptographic Algorithms Using Genetic Algorithm and Graph Theory［J］.IEEE LATIN AMERICA TRANSACTIO NS，2011，9（02）：178-183.

［11］ Souza W，Carvalho L，Xexéo J.Identification of N Block Ciphers［J］.IEEE LATIN AMERICA TRANSACTIO NS，2011，9（02）：184-191.

［12］ Lomte V，Shinde A.Review of a New Distinguishing Attack Using Block Cipher with a Neural Network［J］.International Journal of Science and Research，2014，3（08）：733-736.

丁 偉（1977—），男，碩士，高級(jí)工程師，主要研究方向?yàn)槊艽a對(duì)抗、保密通信；

談 程（1988—），男，碩士，工程師，主要研究方向?yàn)槊艽a對(duì)抗。

An Approach of Identifying Cipher based on Ciphertext Analysis

DING Wei1， TAN Cheng2
（1.Information Assurance Department of Naval Staff of South Sea Fleet， Zhanjiang Guangdong 524001， China；2.No.30 Institute of CETC， Chengdu Sichuan 610041， China）

In fact， the details about the cryptographic algorithm applied in a cryptosystem are often unknown to one cryptanalyst. When a cryptanalyst works on cryptanalysis， he will have much trouble if he doesn't know anything about which kind of cipher is used. In this paper， we introduce an approach to identifying cipher with no other information but ciphertext. Firstly， we present the whole implementation architecture of our identification system of cipher. Then we apply our identification system in identifying 5 common block ciphers， namely AES， Blowfish， 3DES， RC5 and DES. Through analyzing the experiment results， we conclude that the identification rate can obtain around 90% if keys are the same for training and testing ciphertexts. When we use different keys for training and testing ciphertexts， we can still identify AES from anyone of the other 4 ciphers with a high identification rate in one to one identification.

identification system of cipher； cipher identification； SVM classifier； block cipher； identification rate

TN919.72

A

1002-0802（2016）-10-1382-05

10.3969/j.issn.1002-0802.2016.10.022

2016-06-22；

2016-09-13

data：2016-06-22；Revised data：2016-09-13