一种基于密文分析的密码识别技术*

丁　伟，谈　程

（1.海军南海舰队参谋部信息保障处，广东 湛江 524001；2.中国电子科技集团公司第三十研究所，四川 成都 610041）

一种基于密文分析的密码识别技术*

丁伟1，谈程2

（1.海军南海舰队参谋部信息保障处，广东 湛江 524001；2.中国电子科技集团公司第三十研究所，四川 成都 610041）

密码分析过程中，密码分析者往往不知道密码系统使用了哪一种密码，导致密码分析工作困难重重。因此，介绍一种基于密文分析的密码识别方法。首先介绍建立的密码识别系统的工作原理和过程，然后利用该系统对5类常见分组密码（AES、Blowfish、3DES、RC5和DES）进行识别。通过实验结果分析发现，当训练密文和测试密文的密钥一致时，识别率能达到90%左右；而当密钥不一致时，系统仍能够以较高的识别率对AES与其他四类密码进行两两识别。

密码识别系统；密码识别；SVM分类器；分组密码；识别率

0　引 言

密 码分析学专门研究密码破译方法，并用于衡量密码体制安全性。它的一般原理为：密码分析者在不知道密码系统使用的密钥情况下，从截获得到的密文推断出明文消息或密钥。Kerckhoffs对密码分析的基本假设中，阐述了密码分析者已知密码算法及其实现的全部细节，现有的密码分析技术也几乎都建立在密码算法已知的基础上。但是，实际上密码分析者通常获得的大部分都是密文数据，且对应的密码算法是未知的。密码算法已知是进行密码分析的先决条件，如果密码分析者在不知道密码算法实现细节的情形下对密码系统所使用的密码进行识别，我们称这一过程为密码识别。进一步地，如果密码分析者仅掌握一些密文数据，在这种场景下的分析过程称之为基于密文分析的密码识别。

从公开文献来看，国内外关于密码识别技术的研究并不多见。就目前来看，大部分对密码识别技术的研究都是通过逆向分析手段，分析软硬件中使用的密码，如国内解放军信息工程大学蒋烈辉、舒辉教授的团队［1-3］。此外，国外有少部分学者对基于密文分析的密码识别技术有一定研究。概括地讲，对密码识别技术的研究主要包括两个方向：一是利用逆向分析技术进行密码识别；二是基于唯密文进行密码识别。本文针对方向二展开研究。相比方向一，方向二不需要掌握包含密码算法的设备或模块，仅基于一些密文数据来识别密码，其研究更符合实际应用场景。

1　技术发展现状分析

基于密文分析进行密码识别的思想首先在古典密码的识别中得到了实现。Pooja M设计了一种分类古典密码的方案［4］，包括置换密码、代换密码、维吉利亚密码以及置换代换密码。该方案分为四步，通过排除方式进行选择，并基于字母使用频率进行分析。从应用角度讲，研究古典密码识别已没有多大实际意义。Manindra等人在现代密码识别领域进行了更深入的研究［5-7］。文献［5］对分组密码DES和IDEA进行识别研究，利用线性规划思想构造分类器，将密文分成大小为320 bit的块，以密文块为单位输入进行预处理。先获得好的分类器，然后根据不同密文情形分别建立四种模型，包括静态模型、动态模型、拓展动态模型和子文件索引模型，并进行了相关的识别验证。文献［6］提出了重复加密模型，但实验结果并不是很理想，于是提出随机密钥解密模型，基本思路是用随机产生密钥解密密文，将得到的“明文”作为识别模型的输入进行密码算法识别。文献［7］通过改变各项参数对分类器性能进行优化调整，同时运用支持向量机得到一些较好的分类器。

A. Soni首次提出用Adaboost算法对密码进行分类［8］，通过构建比随机猜测稍好的弱分类器，对各弱分类器进行训练，最终得到一个强分类器用于对密码进行识别，但最终平均识别率仅维持在55%左右。S. Mishra等人将密文数据检测、熵值分析和字典决策树法结合使用［9］，对AES、DES和Blowfish密码进行识别。他指出，分组密码二进制密文中0和1几乎是均匀分布的，尤其是AES密码。但在数据量足够大的情况下，还是能捕获到DES和Blowfish密文的一些特征。另外，有学者对AES标准的5个候选算法进行识别研究［10-12］。R. Torres等人［10］运用以Calisnki-Harabasz索引作为评价函数的遗传算法来寻找不同密码对应的密文中隐藏特征。W. Souza等人［11］运用聚类和分类的思想，虽然在CBC模式下根据训练得到的特征对密文分类效果不佳，但是仍然可以对密文进行聚类。V. Lomte等人［12］以神经网络为模型，提出了语言法和信息恢复法对各密文进行识别。

基于密文分析的密码识别技术虽能够克服基于逆向分析的密码识别技术的不足，更符合实际应用场景，但该技术处于起步阶段。目前，国内尚无关于这方面的公开研究成果，国外也仅有少数人研究。总体来讲，当前基于密文分析的密码识别工作仅仅做了一些探索性研究，很多实验密文数据不符合实际情形，如所有密文对应同一密钥，且没有严格限制测试所用的密文文件大小。在真实密码分析场景中，截获的密文数据包大小有限，且多次截获的密文对应的密钥很可能不一致。本文充分考虑密文文件大小和加密密钥一致性等问题，针对AES、Blowfish、3DES、RC5和DES这5种常见的分组密码进行识别研究。

2　识别模型建立

本文考虑ECB模式下对几种常见分组密码进行识别。基于机器学习主流算法之一支持向量机（Support Vector Machine，SVM）构造分类器，从而建立基于密文分析的密码识别模型和系统，原理如图1所示。在该密码识别系统中，按要求输入密文数据，即可输出得到识别出的密码名称。

图1　密码识别系统的基本原理

整个密码识别过程分为两个步骤进行。首先，利用已知密码名称的密文文件对SVM分类器进行训练，然后通过这些分类器对未知密码名称的密文文件进行识别。我们建立的密码识别系统的具体工作过程，如图2所示。

图2　密码识别系统的工作过程

首先，分别生成若干基于AES、Blowfish、3DES、RC5和DES密码算法的密文文件，其中一部分作为训练文件，剩余部分作为测试文件。通过从训练密文文件中提取密文特征，进而筛选出关键特征构建密文特征匹配库；结合SVM算法，建立基于密文分析的密码识别模型。提取测试密文文件的密文特征，然后传送至识别模型即可进行密码识别。基于密文分析的密码识别主要由K个分类器来完成，其中K由密文特征匹配库中的密码种类数k决定，具体分为两种情形。

情形一，一对多。每一个分类器将其中的一类密码和余下k-1类密码分开（将余下k-1类密码看成同一类），则分类器个数K=k。

情形二，一对一。任意两类密码之间构造一个分类器，每个分类器识别两种不同类别的密码，则分类器个数K=k（k-1）/2。

本文考虑一对一的方式进行密码识别。计数器用于对分类结果进行统计，从而识别得到测试密文文件所用的密码。通过产生大量测试密文文件，观察识别结果的同时，不断调整识别模型中的算法参数，从而优化密码识别系统，改善密码识别效果。

3　实验结果与分析

根据前面建立的基于密文分析的密码识别系统，对AES、Blowfish、3DES、RC5和DES密码进行识别。准备220个相同大小的明文文本文件，对应于上述各密码算法，在ECB模式下加密得到1 100个密文文件（每种密码对应220个密文文件）。对应每一种密码，40个密文文件用于训练，剩余的180个密文文件按照每组20个进行分组，进行9次测试。显然，加密密钥和密文文件大小对识别率会产生较大影响，因此在实验中需考虑这些因素。

3.1训练密文和测试密文的密钥一致

首先考虑训练密文和测试密文对应的加密密钥一致的情形。对AES、Blowfish、3DES、RC5和DES密文文件的识别结果如表1所示。

表1　密钥一致时的识别结果（5类密码）

第1列表示训练和测试密文文件的大小，第2列表示9次测试的平均识别率，第3列表示这9个识别率的标准偏差值。从表1中数据可以看出，密文文件越大，识别率越高。当密文文件大小为4 KB时，平均识别率虽然只有29.67%，但仍高于随机猜测正确率20%。标准差值反映了识别结果的可靠性。一般来说，该值越小，说明识别结果可信程度越高。当密文文件不低于100 KB时，识别率几乎达到95%以上，且标准差也小于5%，说明提出的识别系统在密文文件较大时能达到一个较好的识别效果。当密文文件大小为20 KB时，虽然平均识别率达到85.11%，但标准差达到了9.75%，说明在此条件下进行识别并不能保证每次都能达到较高的识别率。

对于Blowfish、3DES、RC5和DES密码，分组长度为64 bit，而AES的分组长度为128 bit，因此考虑对除AES外的其余四种密码对应的密文文件进行识别。如表2所示，当密文文件大小为100 KB或500 KB时，识别率达到了100%，且标准差为0。

表2　密钥一致时的识别结果（4类密码，AES除外）

比较表1和表2的结果，显然可以发现Blowfish、3DES、RC5和DES比AES更容易被识别。当密文文件为4 KB时，表1中的识别率仅为29.67%，而表2中达到了98.33%。

3.2训练密文和测试密文的密钥不一致

当训练密文和测试密文对应的加密密钥一致时，只要密文文件足够大，提出的密码识别系统能够以一个较高的识别率识别出上述几种分组密码。在现实环境下，我们能够以任意密钥生成任意多的训练密文，而截获到的密文（即测试密文）对应的密钥却是未知的。因此，基本上排除了训练密文和测试密文对应的加密密钥一致的可能性，密钥不一致更符合实际情形。对应于AES、Blowfish、3DES、RC5和DES密码，各生成9组密文文件，且训练密文文件和9组密文文件的密钥均不一致。如表3所示，当密文文件大于20 KB时，平均识别率大概维持在35%～40%范围。显然，训练密文和测试密文的密钥不一致时的识别效果要比密钥一致时差很多，但仍高于随机猜测正确率。

表3　密钥不一致时的识别结果（5类密码）

表4为密钥不一致时，Blowfish、3DES、RC5和DES密文的识别结果。凭直觉认为，识别的密码种类数减少，平均识别率就应提高。但表4中的最大平均识别率只有24.86%，甚至低于25%的随机猜测正确率。这表明当训练密文和测试密文的密钥不一致时，系统对Blowfish、3DES、RC5和DES这四种密码的识别是失败的。在加入AES密文文件后，反而无形中提高了识别率，表明当训练密文和测试密文的密钥不一致时，AES的密文特征与其他四种密码存在较显著的差异。

表4　密钥不一致时的识别结果（4类密码，AES除外）

3.3密码间两两识别

由表3和表4可知，当训练密文和测试密文的密钥不一致时，对多类密码进行识别的效果不太理想。在密钥不一致的基础上，考虑对这5类密码进行两两识别，识别结果如表5所示。当密文文件大于20 KB，AES和其他四种密码进行两两识别的识别率总能达到85%以上。而Blowfish、3DES、RC5和DES间进行两两识别，识别率维持在50%左右，表明此情形下的密码识别是不成功的。这些结果也验证了3.2节给出的结论。

表5　密钥不一致时的5类密码间两两识别结果/（%）

4　结 语

本文提出一种基于密文分析的密码识别技术，并建立密码识别系统，针对AES、Blowfish、3DES、RC5和DES5类常见分组密码展开识别研究。通过密码识别实验发现，当训练密文和测试密文的加密密钥一致时，识别效果较好；当加密密钥不一致时，识别效果较差，但可以很好地对包含AES在内的密码进行两两识别。

［1］ 李继中，蒋烈辉，尹青等.基于Bayes决策的密码算法识别技术［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］.计算机工程与设计，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］ 李继中，蒋烈辉，舒辉等.基于动态循环信息熵的密码函数筛选技术［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