基于随机函数的哈希函数

王 勇，蔡国永

（1.桂林电子科技大学 广西可信软件重点实验室，广西 桂林541004；2.桂林电子科技大学 计算机科学与工程学院，广西 桂林541004）

0 引 言

现有的hash （又译为哈希、杂凑、散列）函数具有固定的结构和函数，这为密码分析提供了便利，且近年来在hash函数分析方面取得较好的进展，出现了非常有效的攻击方法，特别是王小云提出一系列hash函数的攻击方法，可以在现实中很快找到碰撞，许多研究对王小云的攻击做了进一步的改进［1－5］。这促进了新的hash算法的开发研究。针对常见的MD 结构算法存在较多的通用攻击，比如长度扩展攻击、多碰撞攻击、长消息第二原象攻击、牧群 （集群）攻击、木马消息攻击等，不过即使是通用攻击依然是针对不变的算法，在SHA－3 竞赛规则中，明文禁止使用MD 引擎。针对于MD 结构的局限性，产生了许多新的结构，比如宽管道结构［6］、双管道结构、Chop－MD 结构、海绵结构［7］等，最终Keccak算法胜出［8］。这些结构依然是基于固定算法的。文献 ［9］提出了多重不确定的密码体制的概念，即在密码体制中增加更多的不确定因素，这会给密码破译带来更大的困难，因为大量的密码分析都是以许多因素是确定和已知作为前提条件的。现在对hash的分析技术也是基于确定的算法，当一个hash函数的算法是不确定的时候，密码分析将很难着手。对于一个固定的函数，要保证这种单向性是比较困难的，因为原则上说可以根据hash函数的结构进行逆推 （虽然它是单向的，原文和hash值是多对一的映射关系，但是在借助一些数学方法和计算工具的情况下，可能进行成功的逆推，这提供了一个破解的入口），需要将算法设计得非常复杂。假如一个hash函数的算法是随机的、不确定的，则密码分析者很难着手。与传统的确定函数相比，我们借鉴随机变量，提出随机函数的概念，即这个函数的表达式、结构和形式是随机的、不确定的，比如随机函数y＝F（a，b，c），F（a，b，c）并没有明确的形式，它的具体形式可能是f1（a，b，c）、f2（a，b，c）、f3（a，b，c）、f4（a，b，c）之中的一个函数，但是函数在具体的情况下却是确定的。注意在这里的随机函数的随机指的是函数的形式是变化的、不确定的，理论上而言，hash函数都是可以攻破的，只是攻击难度的问题。鉴于确定的hash函数给予密码分析者明确的靶子，为许多密码分析创造了条件，从而影响安全性，在本文中采用随机函数来设计hash 函数。hash 函数由复杂的运算过程组成，但是它的关键部分都是集中在压缩函数 （或者利用分组密码函数）中，所以这里讨论的哈希函数主要指压缩函数，明文一般指当前分组的明文。

1 哈希函数的新设计原则

哈希函数设计主要是针对于现有的各种hash 分析方法，要求能够抗击各种攻击，包括抗碰撞攻击、抗原像攻击、抗第二原像攻击、抗生日攻击等，其中抗生日攻击主要是规定哈希值的长度不能低于一定的值。考虑到函数具体形式变化，所以我们可以将哈希值 （输出参数）的决定因素归结为函数和参数 （输入参数为明文，还有由此产生的中间参数）两大部分。在本文中，从函数的具体形式变化的角度，我们给出新的设计原则，以增强哈希函数的安全性，主要原则包括如下几点：

（1）打破前提条件原则。密码分析往往存在前提条件，如果打破这些前提，则密码分析很难进行。显然哈希函数的函数具体形式确定是密码分析的必要条件，可以通过对哈希函数随机化以破坏密码分析的这一前提条件，采用随机的、变化的函数来构造哈希函数。当然还有其它的前提条件可以被打破。

（2）函数具体形式f的单向性原则。对函数的具体形式f进行随机化，并且通过方案构造出一种新的单向性，已知明文（输入参数）m 可以很容易确定哈希函数的具体形式fi，而反过来，仅仅已知哈希值 （输出参数）H 很难确定哈希函数的具体形式fi，这种单向性显然增加了破译难度。

（3）顾头不顾尾原则。在基于随机函数的哈希破译中，函数具体形式fi和消息 （输入参数）m 以及中间计算得到的参数 （中间参数），对于破译者而言是未知的，如果破译者可以固定其中一个单独去破译另一个，则他可以各个击破，好的哈希设计应该是当我们去调整其中一个的时候，另外一个也变化，比如调整输入的消息的时候，函数的形式也发生了变化，这样破译者就顾头不顾尾，顾尾不顾头，破译会很困难，明文修改会带来哈希函数具体形式的变化，这也导致破译哈希的明文 （消息）修改技术实现起来非常困难。

（4）对差分密码分析的 “各说各话”原则。一般对于差分密码分析以相同的函数为前提条件之一，如果我们考虑差分的时候，两个差分分析的明文的哈希函数的具体形式都不一样，去进行差分密码分析必然是困难的，因为一些输入参数、中间参数的运算方式、转移轨迹都完全不一样，想要进行比特跟踪都困难，如果通过差分进行各种方式的比较，由于两者各说各话，驴头不对马嘴，所以不具有可比性，这使得差分分析非常困难。

（5）哈希函数不能或很难用数学方式来表示的 “难表达”原则。一个函数，如果能够用数学方式表达，则密码分析相对会容易一些，比如可以采用列出方程的方法，进行代数等攻击，而一个难于用数学方式表达的函数，则很难进行攻击。

（6）约束条件更多原则。在密码分析中，受到的约束越多，参数进行修改和调整的自由度就更小，在这样的条件下进行适应性的修改以得到合适的消息 （原像）或者碰撞就会更加困难。约束条件更多可能是一个伪命题，但是我们可以只要求一定条件下或者说在可行的密码分析路径下约束条件更多。

（7）在可以单一地进行处理的求解单元下 “解更少”原则。从理论意义上来看解更少是一个伪命题，在哈希值长度一定的情况下，在一定的明文消息空间中的解的数目平均而言是不变的。但是，在密码学领域有许多要求从理论上看起来是伪问题，在实际意义上却可以认为是成立的，比如伪随机就是看起来是随机的，其实并不随机，公钥密码学和hash函数的单向性从理论意义上不成立，在无限的计算能力下并不是单向的，但是在实际限制下可以认为是单向的。我们假设满足hash值的消息称为破译者可以得到的解。我们这里解更少原则就是要求单一地进行处理的求解单元下，或者说在可以不用逐一讨论的情况下的解更少，它不能是把各种不同的函数的具体形式逐一讨论。从另一个角度说，是在具有可行性的现实密码分析路径下，比如满足可用数学方式表达（但是不能是分类讨论这类复杂、非单一的表达）的原则下，满足条件的解更少。满足条件的解更少，通过密码分析能够找到的解必然属于这些解的子集，所以通过密码分析找到的解一般会更少，找到解会更困难。

2 基于随机函数的哈希函数的构造方法

基于以上原则，我们来探讨哈希函数构造方法。通过对函数的具体形式进行随机化，将确定的函数f（m）变成随机函数F（m），显然是可以增强安全性的，但是，哈希函数值本身必须是确定的，而且不同的人都能按照某种公开的计算规则来计算，所以对于不同的人在运算某个具体消息的时候，函数F（m）的具体形式fi（m）不仅应该是确定的，而且不同的人得到的i应该是相同的，这里m 指当前分组的明文消息，所以，应该采用某种方式来确定函数的具体形式，我们可以构造一个函数S 使得i＝S，利用这个函数的值来指定到底是哪个具体形式。这个函数的自变量可以采用公开的参数、秘密的参数 （比如密钥），但是公开参数显然不符合安全性的考虑，这样等于将hash的具体形式暴露给破译者，如果采用密钥来控制，则不符合hash函数公开的特质，则将hash 函数变成消息认证码 （MAC）。这意味着采用随机函数构造hash 似乎是矛盾的，不可能的。但是，我们考虑在密码学中出现的许多单向性都具有这样的特点：在理论上说它是公开的，但是实际上考虑到计算能力的限制，它又是保密的，比如无论是传统的hash函数，还是公钥密码学，实际上他们都是可以破译的，但是破译计算量太大。这意味着我们可以利用类似的单向性机制来消弭上面的这种矛盾。

对于安全的hash函数，在已知哈希值和算法的时候，明文 （消息）m 本质上是可以推导的，但是通过哈希值计算明文的困难让我们权宜地认为它是未知的，所以，如果hash函数的具体形式由明文确定，即i＝S（m），哈希值H＝fi（m），则刚好满足上面提到的 “已知明文可以很容易确定函数的具体形式，已知哈希值很难确定函数的具体形式”要求。因此，基于随机函数的构造方法可以是，首先设计不同的函数（当然这些函数一般应该满足现有hash函数设计的原则），作为随机函数的不同具体形式，给它们赋予不同的编号i，然后设计函数S，使得i＝S（m），这样建立通过m 确定不同具体形式的映射关系，这样得到明文消息m 的时候，可以确定哈希函数的具体形式，从而计算哈希值。

3 基于随机函数的哈希函数的安全性分析

在以上设计中，由于函数具体形式未知，所以打破了密码分析的基本条件，从而使得许多现有密码分析方法无法进行，满足打破前提条件原则。

根据以上设计，哈希函数的生成者 （这里称为加密者）是可以很容易确定hash函数的具体形式的，但是，仅仅知道哈希值则不能确定哈希函数的具体形式，因此，这种设计满足了函数具体形式的单向性原则。

进一步，这种设计也容易满足顾头不顾尾原则，因为hash函数的具体形式与明文是相关的，中间参数与明文也是相关的，所以，改变中间参数一般会导致明文也会变化，明文变化一般也会导致哈希函数的具体形式发生变化，反之亦然，所以参数和函数两者都是相关的，我们无法通过固定其中一个，试图通过调整另外一个，达到破译的目的。

哈希函数由明文确定，这意味着不同的明文一般有不同的哈希函数具体形式，差分密码分析的对比的明文是不同的，而且寻找碰撞的目的本身就是要求不同的明文对应相同的哈希值，所以，在这种情况下，函数的具体形式不同，导致现在采用的一些密码分析方法的前提就失去了，比如，现在采用的一些密码分析方法要求哈希函数是固定（相同）的，且是已知的，在这里采用随机哈希函数，且函数由明文确定，导致了函数具体形式一般不同，这样，由于不同函数下明文、中间参数的运算方式不同、参数转移轨迹都完全不一样，想要进行比特跟踪会非常困难，要进行比较和差分分析也不具有可比性。

“难表达”原则也很显然是具备的，因为，函数的具体形式本身都是不确定的，采用某种数学方程来表示它必然困难，故很难采用代数方程攻击之类的方法。当然这种难表达还使得到其它的密码分析更加困难。

对于采用随机函数的哈希函数，在讨论的时候，我们没有有效方法将不同的函数当作一个函数统一处理，所以，分别讨论不同的哈希函数的具体形式fi的时候，一方面明文消息m 运算得到的哈希函数的具体形式应该是fi，另外一方面，以明文m 作为输入，用fi函数计算的结果应该是给定的哈希值HASH，i＝S（m），HASH＝fi（m），即m需要满足的条件更多，参数进行修改和调整的自由度就更小，在这样的条件下进行适应性的修改以得到合适的消息（原像、明文）或者碰撞就会更加困难。

在我们进行上面讨论的时候，由于约束条件越多，实际上就会导致 “解更少”，这是假定我们无法将随机函数变成一个确定的函数的前提下，采取各个击破的前提下。

可见，构造的哈希函数在现实的角度上来看满足我们提出的这些新原则。

下面我们从hash函数常见的攻击方法着手逐一讨论：

关于抗碰撞性攻击：由于hash函数具有将任意长度的消息转化成固定长度hash 值的性质，消息的空间是非常大，而hash值的空间则很有限，所以必然是一种多对一的关系，即存在多个消息m1，m2，…，得到相同hash 值，这称为碰撞，在认证的时候我们往往出示的是哈希值，有了碰撞就可能用m1假冒m2。抗碰撞性攻击要求找到这种碰撞是困难的。在这里构造的随机哈希函数，由于不同的消息对应不同的哈希函数，显然寻找碰撞是非常困难的，我们以非常成功的差分密码分析为例，现有的方法使用到了明文修改技术和比特跟踪技术，本方法之所以能够规避，①不同的消息对应的哈希函数是不一样的，所以，它们的参数的影响的轨迹和数值是不一样的，这样很难将它们放在一起进行比较；②为了简化问题，可能我们会假设碰撞消息的函数具体形式都是一样的，这样给差分的消息增加了约束条件，这样满足条件的解就会减少，甚至于没有；③在王小云的哈希破译中，采用了明文修改技术，在这里构造的哈希函数，其函数的具体形式随着明文变化而变化，一旦哈希函数的具体形式变化了，就很难对运算进行有效控制，出现顾头不顾尾的局面。

关于抗第一原像攻击：抗第一原像攻击要求对于任意一个消息m，容易得到它的hash值h（m）；但反过来根据它的hash值h（m）很难推导出相应的消息m，这里的消息m 称为h（m）的原像［10］。在这里，我们构造的函数在已知m 的时候很容易计算哈希函数的具体形式fi，也很容易得出哈希值，但是已知哈希值的时候，是无法知道哈希函数的具体形式的，即使是我们限定是某个具体的哈希函数形式fi，fi是特定的m 才能得出的，所以会增加更多的约束条件，从而增加破译难度。

关于抗第二原像攻击：类似于前面的分析，由于不同的原像的函数的具体形式不一样，所以很难找到不同明文的哈希值是一样的，我们也可以得出这样的设计会增加破译的难度。另一方面，对于确定且相同的函数，不同的原像之间可能存在关系，消息m1和消息m2的关系就可以用于破译，但是，对于基于随机函数的hash函数，不同的明文对应于不同的hash函数，所以，消息m1和消息m2的关系就会很难利用于破译。即使是我们限定两个原像 （消息m1和消息m2）对应于相同的hash函数具体形式，这会带来更多的对两个原像的限制，使得原像受到的约束条件更多，破译更难。

在加密算法中，许多密码分析基于统计特征，假如统计特征用于hash函数的破译，也是存在困难的，原因在于本随机函数F 的统计特征不是单个函数的统计特征，而且对于所有使用某个确定函数f 的明文消息m 和对应的hash值H，由于并不是所有的明文都是使用该函数f，所以也只是该确定函数f 的明文消息和对应hash值中的一部分的统计特征，因而我们使用随机函数整体的统计特征，对这一部分也未必是有效的。

针对于其它的一些攻击方法，由于我们这里打破了哈希函数形式是固定不变的这一前提，也会增加破译的难度。

随机函数是确定函数的一种推广和随机化，应该说确定函数是随机函数的特例，将哈希函数的函数推广到随机函数，大大拓展了函数的形式和内容，在这样的更加宽阔的空间中必然存在更加优秀的函数。

4 潜在的安全威胁分析

下面我们对破译者可能采取的分析方法做一定的展望。

对于随机函数，如果能够想办法确定函数的具体形式fi，则会更容易破译，我们分析以下几种可能性：①随机函数的不同的具体形式的输出值存在差异，某个输出值或者某一部分输出值明显只能由某个随机函数的具体形式fj得出，则可以确定哈希函数具体形式即为该函数fj，随机函数退化为确定性函数，失去了前面讨论的价值。②不同的随机函数的运算量、运算速度不一样，则在加密领域使用的能量攻击、定时攻击等边信道攻击也可能用于判定函数的具体形式。

退一步，即使是攻击者不能知道函数的具体形式，但是他能够知道函数的具体形式更可能是哪个，哪个的概率较大，也会带来安全威胁。

密码分析者还可能将F（m）的不同的具体形式f1（m）、f2（m）、f3（m）、…，统一为一个新的确定的函数g（m），注意到前面是m 确定了fi，这种随机函数的统一是可能存在的，一旦能够统一，则随机函数可以退化为确定函数，从而丧失优势。

5 基于随机函数的哈希函数的优化思路

根据前面的分析，我们在此给出一些优化思路，以进一步增强安全性和防范潜在的攻击：①随机函数的各个具体函数的输入输出空间 （所有可能值构成的集合）应该尽量是相同的，最好输入输出都遍历所有可能的值，具有很好的遍历性。②在运算量、能耗等方面应该具有很好的对等性，不能有太大的差异。③在消息等概率的情况下，随机函数的各个具体形式出现的概率应该是相近的，最好是等概率出现，即函数S 的值是等概率的。④哈希函数的各个具体形式应该具有很大的差异，一方面可以防止统一为某个确定的函数，一方面使得密码分析非常困难。⑤我们对比一个确定性hash函数，它的运算量和随机哈希函数的所有具体形式的运算量都是类似的，在采用同等运算量的函数的情况下，本方法相比确定的函数，会存在一定的附加工作量，主要用于确定随机函数的具体形式，这些工作量并不算大，要进一步减少这部分工作量，可以尽量复用哈希函数运算中的一些中间结果。为了减少运算量，还可以将整个函数分为一些运算部件，在一些部件中采用随机函数部件，这样通过乘积效应放大随机函数具体形式的数目，减少随机函数设计的难度。

6 结束语

鉴于现有的大多数哈希函数的破译均以知道哈希函数作为前提条件，因此去除和打破这些前提条件会带来更好的安全性。本文打破这一前提，提出一种基于随机函数的哈希函数的构造方法，将传统的确定函数推广到了随机函数，提出一些新的哈希函数的设计原则，并且论证本方法构造的哈希函数符合这些原则，并且相对于现有的攻击方法有很好的安全性。本文提出的这类方法对设计确定函数的哈希函数同样具有借鉴意义，比如顾头不顾尾原则和难于表达原则。基于随机函数的哈希函数体现了一种随机变化的特点，这当然是对于破译不利的。即使是抛开以上对具体密码分析的讨论，我们也可以很容易确定基于随机函数的哈希函数中能够选出更好的算法，因为传统的确定型hash函数只是随机函数的一种特例，属于其子集，在更加广泛的随机函数中自然能够选出更好的函数。同样在这一新的领域也会有新的问题，比如如何选择随机函数的具体形式，让它们搭配的更好。本文开启了一个新的领域，而对于这类的哈希函数，传统的攻击方法并不能凑效 （除了暴力破解），需要有新的破译方法，将会引出新的方向。而随机函数也是传统确定函数的一种推广，也具有重要的研究价值。

［1］LI Lin.Cryptanalysis of the Hash functions RIPEMD－128and HMAC－MD4 ［D］.Jinan：Shandong University，2007 （in Chinese）.［黎琳.Hash函数RIPEMD－128和HMAC－MD4的安全性分析 ［D］.济南：山东大学，2007.］

［2］WANG Yu，RUAN Yanhua，CHEN Jianhua.New attack on Haval－128 ［J］.Computer Engineering and Design，2008，29（20）：5159－5162 （in Chinese）.［汪玉，阮艳华，陈建华.新的Haval－128的碰撞攻击 ［J］.计算机工程与设计，2008，29（20）：5159－5162.］

［3］Liang Jie，Lai Xuejia.Improved collision attack on hash function MD5 ［J］.Journal of Computer Science and Technology，2007，22 （1）：79－87.

［4］Zhong Jinmin，Lai Xuejia，Duan Ming.Improved preimage attack on 3－pass HAVAL ［J］.Journal of Shanghai Jiao Tong University （Science），2011，16 （6）：713－721.

［5］ZHANG Shaolan.Design and security analysis on several cryptography Hash functions ［D］.Beijing：Beijing University of Posts and Telecommunications，2011 （in Chinese）. ［张绍兰.几类密码Hash函数的设计和安全性分析 ［D］.北京：北京邮电大学，2011.］

［6］Lucks Stefan.A failure－friendly design principle for hash functions ［G］.LNCS 3788：Advances in Cryptology－ASIACRYPT，2005：474－494.

［7］Guido Bertoni，Joan Daemen，Michael Peeters，et al.On the in differentiability of the sponge construction ［G］.LNCS 4965：Advances in Cryptology－EUROCRYPT，2008：181－197.

［8］Alshaikhli IF，Alahmad MA，Munthir K.Comparison and analysis study of SHA－3finalists［C］／／International Conference on Advanced Computer Science Applications and Technologies，2012：366－371.

［9］WANG Yong，HUANG Xionghua，CAI Guoyong.Information theory and coding ［M］.Beijing：Tsinghua University Press，2013：255－266 （in Chinese）. ［王勇，黄雄华，蔡国永.信息论与编码 ［M］.北京：清华大学出版社，2013：255－266.］

［10］Sasaki Y，Aoki K.Finding preimage in full MD5faster than exhaustive search ［G］.LNCS 5479：Advances in Cryptology－EUROCRYPT，2009：134－152.