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

丁　偉，談　程

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

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

丁偉1，談程2

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

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

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

0　引 言

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

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

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

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

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

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

2　識別模型建立

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

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

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

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

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

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

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

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

3　實驗結(jié)果與分析

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

3.1訓練密文和測試密文的密鑰一致

首先考慮訓練密文和測試密文對應的加密密鑰一致的情形。對AES、Blowfish、3DES、RC5和DES密文文件的識別結(jié)果如表1所示。

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

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

對于Blowfish、3DES、RC5和DES密碼，分組長度為64 bit，而AES的分組長度為128 bit，因此考慮對除AES外的其余四種密碼對應的密文文件進行識別。如表2所示，當密文文件大小為100 KB或500 KB時，識別率達到了100%，且標準差為0。

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

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

3.2訓練密文和測試密文的密鑰不一致

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

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

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

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

3.3密碼間兩兩識別

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

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

4　結(jié) 語

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

［1］ 李繼中，蔣烈輝，尹青等.基于Bayes決策的密碼算法識別技術(shù)［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ù)研究［J］.計算機工程與設(shè)計，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］ 李繼中，蔣烈輝，舒輝等.基于動態(tài)循環(huán)信息熵的密碼函數(shù)篩選技術(shù)［J］.計算機應用， 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—），男，碩士，高級工程師，主要研究方向為密碼對抗、保密通信；

談 程（1988—），男，碩士，工程師，主要研究方向為密碼對抗。

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