基于组合随机性特征的哈希函数识别方案

Hash Function Recognition Scheme Based on Combinatorial Randomness Feature

摘要

加密算法的识别对于密码分析研究有着重要的意义，目前学者们已经在此领域展开了一些研究并取得了一定的进展。然而在针对哈希函数的识别方面，所展开的理论研究较少。本文对随机性检测特征进一步挖掘，利用欧氏距离筛选出对哈希函数最有区分度的3个检测项，基于选出的检测项的核心关注点重新构建特征生成方法，并结合随机森林模型，提出了一种基于组合随机性特征的哈希函数识别方案。通过实验分析，该识别方案明显优于传统的基于随机性检测特征的识别方案。

Abstract

The recognition of encryption algorithms is of great significance to the research of cryptographic analysis. At present, scholars have carried out some research and made some progress in this field. However, there are few theoretical studies on Hash function recognition. In this paper, the randomness detection features are further mined. The Euclidean distance is used to screen out the three detection items that have the most distinguishing degree to the Hash function. Based on the core concerns of the selected detection items, the feature generation method is reconstructed. Combined with the random forest model, a Hash function recognition scheme based on the combined randomness features is proposed. Through experimental analysis, the recognition scheme is obviously superior to the traditional recognition scheme based on random detection features.

Graphical abstract

关键词

密码分析 / 哈希函数 / 特征提取 / 随机性检测

Key words

cryptanalysis / Hash function / feature extraction / randomness test

0　 引 言

哈希函数作为用途最多的密码学算法之一，其安全性在信息安全领域至关重要，一直以来广受国内外学者的关注，针对哈希函数的密码分析攻击也一直有学者在研究。文献[1~4]给出了一些经典哈希函数的碰撞路线与碰撞实例。时至今日，关于哈希函数碰撞攻击的理论研究和实例研究依旧是密码学领域的重要议题^[5]。

进行哈希碰撞攻击的一个前提条件是假定已知当前密文是经由哪种哈希函数加密得到。这也是各类密码攻击技术一个广泛前提，即假定密文来自某一明确的单一加密算法，继而进行后续的密文分析工作并从中获取所需信息。但是实际环境中，学者往往无法得知所获密文具体来自于哪种算法，因此对各密文所属的加密算法进行识别是一项非常有意义的工作。该工作对于密文分析、加密算法的破解、安全性证明等工作有重要意义和实际价值。

在密文识别领域，国内外的研究者^[6，7]早期主要通过统计学方法进行该项研究，常见的处理方式是设计多个相关分类指标，依照设计的公式计算各密文对应的指标值，将所得结果与已测得的加密算法指标值进行匹配和比较，通过其数值特征来确定该密文可能是归属于哪种加密算法。但这种方法一般对于残留有一定的明文固有统计规律的古典密码较为有效。自Ramzan^[8]率先将神经网络应用于密文识别的研究后，国内外研究者^[9~13]也陆续将机器学习算法应用于密文识别。应用机器学习算法进行密文识别在古典密码与现代密码均取得较好效果。

由于哈希函数往往比常规的加密算法具有更高的随机性，故而传统的统计学方法理论上难以实现较好的识别效果。同时哈希函数是对原信息进行摘要，导致所得密文长度均为固定值并且一般都较短小，因此对密文数据的处理与传统加密算法有着差异。

在哈希函数的识别方面，所展开的理论研究较少，在实际应用中主要是开发者根据自身需求开发哈希函数破解工具。但目前在应用层面的哈希函数识别方法还停留在使用正则表达式根据不同哈希函数在实际输出上的直观差异来进行区分。这种方法有一定的局限性，例如对于长度同为128位的MD2密文和MD5密文几乎没有识别效果。

目前，学者们的研究重点主要集中于传统加密算法，例如分组加密算法，对称加密算法等。最常见的做法是直接使用NIST（national institute of standards and technology）随机性检测获得特征向量，将特征向量送入分类模型中进行识别。但相关研究几乎没有涉及到哈希函数，也没有哈希函数的识别方案。而哈希函数与传统加密算法具有一定的共性，可以尝试学习并改进现有的加密算法识别方法，摆脱当前仅依照正则表达式进行识别的困境。

针对以上不足，本文根据实验分析得出NIST随机性检测^[14]各项指标中对哈希函数影响最大的3个指标：块内最长1游程检测（test for the longest run of ones in a block）、线性复杂度检测（linear complexity test）和全局通用统计检测（Maurer’s “Universal Statistical” Test）。基于这3个指标构造出一种组合随机性特征提取算法，取名为LLU（LR&LC&US）特征提取算法。使用该算法对哈希函数进行特征提取，并结合随机森林模型对哈希函数进行识别，实验结果表明，该方案明显优于原始随机性特征的识别效果，同时，该方案解决了使用哈希函数破解工具无法对MD2与MD5区分的问题。

1　 相关知识

1.1　哈希函数

哈希函数H可将任意长度的消息x单向映射成固定长度的二进制串即哈希值。

定义 1 哈希函数：哈希函数是一个单向映射

H:{\{\mathrm{0,1}\}}^{\mathrm{*}}\to {\{\mathrm{0,1}\}}^n

其中,{\{\mathrm{0,1}\}}^{\mathrm{*}}表示任意长度的二进制串的集合，{\{\mathrm{0,1}\}}^n表示长度为n的二进制串的集合，消息x\in {\{\mathrm{0,1}\}}^{\mathrm{*}}的像H(x)称为x的哈希值。

常用的哈希函数分为MD（message digest）系列算法以及SHA（secure Hash algorithm）系列算法。本文所用算法从这两类中选择比较常见的MD2、MD5、SHA-1、SHA-256、SHA-512进行实验分析。

1.2　随机性检测

现有的随机性检测标准有我国制定的随机检测规范GM/T 0005-2012《随机性检测规范》以及NIST制定的相关标准，其中使用最为广泛的版本为NIST 2010年发布的SP 800-22，它包含15项随机性检测标准，这些检测可以很好地反应出加密数据的某些模式特征，进而被众多研究人员充分论证并使用，本文也基于此标准进行研究。根据具体检测指标和规则以及参考文献中的相关数据，选定其中如表 1所示的10项进行针对5种哈希函数的随机性检测实验。

现有的识别算法常常直接使用所有NIST检测的返回值构造特征向量。这种方法方便简单，可直接通过相关的测试套件生成。本文通过对NIST检测单项重新组合，并按照对应的算法重新设计向量生成方案，提高了识别准确率。

1.3　随机森林

随机森林（random forest，RF）是一种有监督的集成学习算法，主要是通过多棵决策树的组合使分类结果更准确。在执行分类任务时，各决策树分别进行分类判断然后经最终投票决定输入样本的所属类别。在数据集的选取方面，随机森林通过bootstrap方法给各决策树选定训练数据，该过程是一个有放回的随机抽样，故而单个或多个子数据集的元素均可能重复以及原始数据集的部分元素可能不会被任何子数据集包含。在特征选取方面，随机森林算法是在决策树的每个节点需要分裂时，从M个属性中选取出m(m\ll M)个属性，进而从选出的属性子集中通过特定的规则来选定一个属性作为该节点的分裂属性。该过程是一个无放回的随机抽样。该分裂步骤在决策树构成过程中需反复进行直至节点无法再进行分裂。

1.4　哈希函数识别问题相关定义

结合文献[12]中对于密码体制的单层与分层识别方案定义，给出哈希函数识别问题中的相关基本定义。

定义2 （哈希值）设原始消息M经由某种单一哈希函数\mathrm{H}\mathrm{F}加密后得到哈希值H=\mathrm{H}\mathrm{F}\left(M\right)=(h_{\mathrm{1}},h_{\mathrm{2}},\dots ,h_n)，其中n为哈希值长度，h_i为0或1。遵循大多数研究中将加密后数据表示为以比特或字节为基本字符的有序集合^[12]。

本文使用的哈希函数直接加密原始消息M后得到的哈希值H长度较短，难以进行后续识别，故而对原始消息M进行分块，将M的大小记为W(M)，分块大小为K，即M=\left(m_{\mathrm{1}},m_{\mathrm{2}},\dots ,m_n\right)，其中n向上取整，即n=⌈\frac{W(M)}{K}⌉。经过这一过程后得到原始消息M对应的哈希值：

\mathrm{P}\mathrm{H}=\left(\mathrm{p}{\mathrm{h}}_{\mathrm{1}},\mathrm{p}{\mathrm{h}}_{\mathrm{2}},\dots ,\mathrm{p}{\mathrm{h}}_n\right)

其中\mathrm{p}{\mathrm{h}}_i=\mathrm{H}\mathrm{F}(m_i)。

定义 3 （哈希特征提取）使用哈希特征提取算法\mathrm{H}\mathrm{F}\mathrm{T}提取经过哈希值生成步骤的数据\mathrm{P}\mathrm{H}的特征，得到特征向量\mathrm{h}\mathrm{f}\mathrm{t}=\left(\mathrm{h}\mathrm{f}{\mathrm{t}}_{\mathrm{1}},\mathrm{h}\mathrm{f}{\mathrm{t}}_{\mathrm{2}},\dots ,\mathrm{h}\mathrm{f}{\mathrm{t}}_n\right)，其中n为特征向量\mathrm{h}\mathrm{f}\mathrm{t}的维数，故而哈希特征提取过程可形式化表示为\mathrm{h}\mathrm{f}\mathrm{t}=\mathrm{H}\mathrm{F}\mathrm{T}\left(\mathrm{P}\mathrm{H}\right)。在已有文献中特征提取算法\mathrm{H}\mathrm{F}\mathrm{T}可以是统计字符频率、计算熵特征以及直接使用或改进随机性检测相关方法，而特征向量维数n则可达1.0×10⁶。

2　 LLU特征提取算法

2.1　设计目标

受限于哈希函数的构造过程，明文信息经其加密后得到的哈希值序列往往依旧留存某种与其中的0和1排列情况有关的固有特征。通过随机性检测可以找出其显著特征项所对应的衡量指标，进而根据该项指标的相关计算值可以构造新的基于显著随机性特征的特征提取算法，更好地实现哈希函数的识别任务。

本文首先对输入数据集进行10项随机性检测，得到的各项返回值即密文数据的原始随机性特征（NIST特征）。通过计算每两种哈希函数所对应的同一项返回值之间的欧氏距离，得到10组两两组合的哈希函数的各10项距离值。进而通过一定的计算过程得到其中被认为具有显著差异的3个检测项，根据以上检测项的核心计算指标进一步构造LLU特征提取算法。该算法主要是将每个哈希值序列对应的3项返回结果经过一定的规则重新划分，得到各5个显著特征值，再将其组合得到一个15维的特征向量，以此来显示各哈希函数所生成的哈希值序列之间的显著性差异，使得对后续的哈希函数识别取得更好的效果。

2.2　随机性检测项选取

本文通过实验选取对哈希函数最有区分度的3个检测项，以此构建特征提取算法。

实验数据来自Caltech-256 object category dataset图片库（http://www.vision.caltech.edu/Image_Datasets/Caltech256/256_ObjectCategories.tar）,随意选取其中不同大小的图片5 000张，然后对单张图片按照256位固定大小进行分块后再进行加密和拼接，得到经MD2、MD5、SHA-1、SHA-256、SHA-512这5种哈希函数分别加密后的文件共计25 000份，并且保证所有文件大小均在2 Kb以上，以满足实验要求。使用python3.7实现NIST随机性检测算法后，输入实验数据进行本文1.2节10项随机性检测相关指标，得到每种哈希函数所对应的密文文件检测后返回的p-value，即共5份csv格式存储的10项原始随机性特征值。

为挑选出对5种哈希函数最有区分度的检测项，通过编码使用欧氏距离公式进行5种算法两两之间单一检测项返回值的相似度度量到10组10项距离数据，共计100个距离值。此过程如算法1。

10组10项距离值如表2所示，将5种算法MD2、MD5、SHA-1、SHA-256、SHA-512按顺序编号为a～e。求出单一检测项返回值的10组距离值的平均值即表2均值行所对应的数据。接着记录对于任意一组哈希函数组合距离值最大的前3个检测项，综合得到①～⑩个检测项命中的频数，然后将频数与均值综合得到各检测项返回值对应距离的加权平均值，即表 2综合行所对应的数据。

综合评价值排名前3的检测项为：④块内最长1游程检测、⑧全局通用统计检测、⑨线性复杂度检测。故而选定基于这3个检测项进行基于NIST随机性检测的特征提取算法的构建。

2.3　LLU特征提取算法设计

根据2.2节中选定的3个随机性检测项，本文仅使用随机性检测项的核心关注点，省去p值理论的计算过程来构建LLU特征提取算法。对于块内最长1游程检测，其核心关注点为每个分块内连续1比特的最大长度值；对于线性复杂度检测，其核心关注点为线性反馈移位寄存器(LFSR)的长度；对于全局通用统计检测，其核心关注点为测试块与匹配序列块之间的距离值。由于以上3个检测项内部均为分块进行相关计算，故对于单个待检测哈希值序列，其对应均能得到多个相关参数值，将所得参数值进行分组并再次计算，输出其新的特征值，将三组相关参数重新进行组合即可得到新的特征向量。具体算法如算法2所示。

3　 识别方案设计

整体的识别方案设计如图1所示，其中各参数如定义2和定义3，M表示原始消息，PH表示各原始消息的哈希值，LAB代表生成哈希值所使用的哈希函数种类，hft代表提取的哈希特征。图1中，左半部分为训练部分，右半部分为整个实验的测试部分。

本文方案使用随机森林（RF）模型进行分类，RF模型的实现是基于RandomForestClassifier和DecisionTree-Classifier模块，用基尼指数作为每次集合划分的标准。传入之前划分好的训练集进行训练，然后利用测试集对已经训练好的模型进行测试，得到模型的分类准确率。

在参数优化方面主要是针对随机森林中的决策树个数（ne）、每次划分的基尼指数最少减小值（mid）和每棵决策树的最大深度（md），根据不同的哈希函数使用GridSearchCV进行参数自适应得到准确率最高的参数组合，每个不同的分类组合都有其特定对应的参数。在每次分类选择的特征数mf参数上，增大mf的值在一般情况下对于模型的分类效果有一定的提升，但是会降低单个树的多样性。考虑到随机森林基于集成学习思想的优点，减小mf不仅会提升算法速度，还可降低测试误差。

4　 实验结果与分析

4.1　实验环境与数据

本文实验环境的主机配置为MacOS_Monterey_V12.1操作系统，处理器为2.9 GHz 六核Intel Core i9，内存为32 GB 2400 MHz DDR4。

本文实验数据依然是从Caltech-256数据集中随意选取的不同大小的图片5 000张，按照256位的大小对单张图片进行分块、加密、拼接，得到5种哈希函数分别加密后的文件共计25 000份保存在txt文件中，并且保证所有文件大小均在2 Kb以上。

加密部分实验在IDEA2021中使用java1.8编写，所用到的5种哈希算法调用OpenSSL密码库中的相关实现。

哈希函数识别部分实验在Pycharm2021中使用python3.7编写程序实现。其中RF模型通过调用Scikit-learn包实现。实验用到的哈希值数据集按照固定8∶2的比例随机进行抽取分为训练集和测试集。

4.2　实验结果

本文对于多种哈希函数识别的实验首先在两类哈希函数的识别上展开，实验首先进行MD2、MD5、SHA-1、SHA-256和SHA-512这5种哈希函数生成的哈希值密文文件的两两识别。在对组成的10组识别任务完成实验测试后，对比原始随机性特征与本文提出的LLU特征提取算法的识别效果。通过多类哈希函数的识别效果，进一步说明LLU特征提取算法的优越性。

1）　两类哈希函数的识别

分别使用原始随机性特征和LLU特征，对5种哈希函数进行两两识别，实验结果如表3~5所示。

由实验结果可知，原始随机性特征对于两类哈希函数识别任务的准确率稳定在49%至59%之间，LLU特征较之有明显提升，其识别准确率在68%至76%之间。

2）　多类哈希函数的识别

同样分别使用原始随机性特征以及LLU特征，对3种哈希函数进行识别，结果如表6与表7所示。

由实验结果可知，当哈希函数类别增加到3时，利用原始随机性特征有较明显的下降，其准确率基本在40%左右。而对于LLU特征而言，其识别准确率略有下降，但平均识别准确率仍能达到68.4%。

对4种哈希函数的识别结果如表8。由结果可知，此时使用原始随机性特征进行识别的准确率在30%左右。利用LLU特征进行识别时，准确率较两类与三类哈希函数的识别的准确性有所下降，但仍在60%左右，比原始随机性特征识别准确率最高的两类哈希函数识别率还高。

4.3　实验分析

对两类、三类以及四类哈希函数的识别实验表明本文提出基于LLU特征提取的哈希函数识别方案明显优于传统的基于随机性检测特征的识别方案。

通过本文特征值提取方法的构造，说明在密文识别以及分析领域，直接选取所有NIST检测项的返回值作为特征值时，其中各参数之间并不一定都是正向作用，可能存在着如本文中增加检测项，识别效果反而下降的情况。究其原因，可能是因为NIST各检测项之间存在着相关性，且一些检测项存在着片面性。

5　 结 语

当前绝大多数的加密算法识别方法研究均未单独聚焦哈希函数的识别任务。但在实际应用中，该项工作十分重要，本文填补了这一空白。同时本文提出的LLU特征提取算法对哈希函数的特征值的提取明显优于传统的直接使用随机性检测返回值作为特征的方法，本文方法为使用NIST随机性检测进行密文分析提供了一种新思路。

本文的不足以及深入研究的建议：1） 实验仅在5种常见的哈希函数上展开，还有许多哈希函数类别未涉及，综合其他算法的实验结果，各项参数与数据处理方式还需要进一步优化;2） 基于随机性特征进行特征值提取，未来可以进一步尝试利用机器学习算法强大的特征提取能力提取密文特征。

参考文献

[1] VAN ROMPAY B， BIRYUKOV A， PRENEEL B， et al. Cryptanalysis of 3-pass HAVAL［C］//Advances in Cryptology—ASIACRYPT 2003. Berlin： Springer， 2003： 228-245. DOI： 10.1007/978-3-540-40061-5_14 .

[2] WANG X Y， LAI X J， FENG D G， et al. Cryptanalysis of the Hash Functions MD4 and RIPEMD［C］//Lecture Notes in Computer Science. Berlin： Springer， 2005： 1-18. DOI： 10.1007/11426639_1 .

[3] LIANG J， LAI X J. Improved collision attack on Hash Function MD5［J］. Journal of Computer Science and Technology， 2007， 22（1）： 79-87. DOI： 10.1007/s11390-007-9010-1 .

[4] STEVENS M， LENSTRA A K， DE WEGER B. Chosen-prefix collisions for MD5 and applications［J］. International Journal of Applied Cryptography， 2012， 2（4）： 322-359. DOI： 10.1504/IJACT.2012.048084 .

[5] BAKHTIYOR A， ORIF A， ILKHOM B， et al. Differential collisions in SHA-1［C］//2020 International Conference on Information Science and Communications Technologies （ICISCT）. New York： IEEE Press， 2021： 1-5. DOI： 10.1109/ICISCT50599.2020.9351441 .

[6] RAO M B. Classiflcation of RSA and IDEA Ciphers［D］. Kanpur： Indian Institute of Technology， 2003.

[7] GIRISH C. Classication of Modern Ciphers［D］.Kanpur：Indian Institute of Technology， 2002.

[8] RAMZAN Z. On Using Neural Networks to Break Cryptosystems［R］. Cambridge：Massachusetts Institute of Technology， 1998.

[9] 赵志诚， 赵亚群， 刘凤梅. 基于随机性测试的分组密码体制识别方案［J］. 密码学报， 2019， 6（2）： 177-190. DOI： 10.13868/j.cnki.jcr.000293 .

[10] ZHAO Z C， ZHAO Y Q， LIU F M. Scheme of block ciphers recognition based on randomness test［J］. Journal of Cryptologic Research， 2019， 6（2）： 177-190. DOI： 10.13868/j.cnki.jcr.000293（Ch ）.

[11] 纪文桃， 李媛媛， 秦宝东. 基于决策树的SM4分组密码工作模式识别［J］. 计算机工程， 2021， 47（8）： 157-161. DOI： 10.19678/j.issn.1000-3428.0058608 .

[12] JI W T， LI Y Y， QIN B D. Working mode recognition for SM4 block cipher based on decision tree［J］. Computer Engineering， 2021， 47（8）： 157-161. DOI： 10.19678/j.issn.1000-3428.0058608（Ch ）.

[13] KANT S. Classification models for symmetric key cryptosystem identification［J］. Defence Science Journal， 2012， 62（1）： 38-45. DOI： 10.14429/dsj.62.1440 .

[14] 黄良韬， 赵志诚， 赵亚群. 基于随机森林的密码体制分层识别方案［J］. 计算机学报， 2018， 41（2）： 382-399. DOI： 10.11897/SP.J.1016.2018.00382 .

[15] HUANG L T， ZHAO Z C， ZHAO Y Q. A Two-stage cryptosystem recognition scheme based on random forest［J］. Chinese Journal of Computers， 2018， 41（2）： 382-399. DOI： 10.11897/SP.J.1016.2018.00382（Ch ）.

[16] 王旭， 陈永乐， 王庆生， 等. 结合特征选择与集成学习的密码体制识别方案［J］. 计算机工程， 2021， 47（1）： 139-145. DOI： 10.19678/j.issn.1000-3428.0056918 .

[17] WANG X， CHEN Y L， WANG Q S， et al. Cryptosystem identification scheme combining feature selection and ensemble learning［J］. Computer Engineering， 2021， 47（1）： 139-145. DOI： 10.19678/j.issn.1000-3428.0056918（Ch ）.

[18] RUKHIN A， SOTO J， NECHVATAL J， et al. A statistical test suite for random and pseudorandom number generators for cryptographic applications［J］.Applied Physics Letters， 2010， 22（7）： 1645-179.

基金资助

湖北省重点新产品计划(2021BAA030)