（通信与信息系统专业论文）基于信源概率分布的加密哈希函数设计.pdf

摘要 摘要 网络多媒体技术、通信技术和传输技术的迅速发展给人们带来极大的便利 的同时，信息安全成为人们不容忽视的问题。而无线网络因为其特殊的性质， 安全问题尤其突出。加密哈希函数是信息安全领域的重要的工具之一，主要运 用在文件校验、数字签名、鉴权协议等方面。安全加密哈希函数的设计需要符 合三个原则：抗第一原像攻击，抗第二原像攻击，抗碰撞攻击。目前已提出的 加密哈希函数设计主要为m d 系列和$ h a 系列。针对加密哈希函数的攻击也备 受关注。对加密哈希函数最主要的攻击是生日攻击，生日攻击方法依赖于消息 摘要的长度，即哈希值的长度。这种攻击对加密哈希函数提出了一个必要的安 全条件，即消息摘要必须足够长。传统的加密哈希函数的设计都假设需要发送 的信息都是等可能发生的，从信息论的角度出发，一般信源的信息量是最小的。 实际上，对于发送者来说，信源的概率分布，或者信息量是可以通过长期的统 计获得，且在某些情况下信源的概率分布还可能非常规律。本文考虑利用发送 信息的不等可能概率分布来设计加密哈希函数，与传统加密哈希函数设计相比， 攻击成功的概率大大减少。换言之，在同等攻击概率下，所需要的消息摘要的 长度也可能可以比传统加密哈希函数所需要的要短一些。 本文具体研究工作如下： 通过分析讨论加入信源概率分布后的加密哈希函数映射问题，得到信源概 率、映射关系和攻击成功概率之间的关系。通过对攻击成功概率进行最优化， 提出了基于信源概率分布的加密哈希函数设计函数的启发式算法，并对启发式 算法进行了仿真，通过算法的仿真结果评估了该优化算法的具体性能。优化的 算法通过多次迭代找出了次优的映射关系，实现了攻击成功概率的收敛。与传 统算法进行了对比，该次优算法在参数相同的情况下，使得攻击成功概率减少， 提高了通信过程的安全性能。 其次，本文介绍了平衡度的定义、生日攻击的平衡度分析，以及常用的m d ( m e r k l e - d a m g a r d ) 变换的平衡度的结论，以往研究表明一般传统的好的加密哈 希函数的平衡度大小接近于l 。将“平衡度”概念引入本文提出的优化加密哈希函 数算法中，导出优化加密哈希函数的平衡度计算公式。通过传统的理想加密哈 希函数与优化加密哈希函数的平衡度仿真以及对比分析，验证出当信源不等概 摘要 分布时，好的加密哈希函数不再具备平衡度大小趋近于1 的特征。平衡度定义 与结论的完善以及相应的理论证明成为下一步研究的重点方向。 关键词：加密哈希函数；一映射关系；信源概率分布；生日攻击；平衡度；信息 安全 a b s t r a c t t h er a p i dd e v e l o p m e n to fm u l t i m e d i at e c h n o l o g y , c o m m u n i c a t i o nt e c h n o l o g y a n d 缸乏m s i n i s s i o nt e c h n o l o g yh a sb r o u g h tg r e a tc o n v e n i e n c e ；m e a n w h i l e ，i n f o r m a t i o n s e c u r i t yh a sb e c o m eap r o b l e m w h i c hc a n n o tb ei g n o r e d d u et ot h es p e c i a lc h a r a c t e r , t h es e c u r i t yi s s u e so fw i r e l e s sn e t w o r kh a v e b e e nh i g h l i g h t e d a sa ni m p o r t a n t t o o lm 廿l ef i e l do fi i 讧b m a t i o ns e c u r i t y , c r y p t o g r a p h i ch a s hf u n c t i o ni sm a i n l yu s e di nf i l e v a l i d a t i o n ，d i g i t a ls i g n a t u r ea n da u t h e n t i c a t i o np r o t o c o le t c t h ed e s i g no fas e c u r e c r y p t o g r a p h i ch a s hf u n c t i o ns h o u l da b i d eb y t h r e ep r i n c i p l e s ，w h i c ha r ea n t i - p r e i m a g e a t t a c k a n t i s e c o n dp r e i m a g ea t t a c ka n da n t i - c o l l i s i o na t t a c k n o w a d a y s ，p r o p o s e d c r y p t o g r a p h i ch a s hf u n c t i o n sm a i n l ya r em d s e r i e sa n ds h as e r i e s ，a tt h es a m et i m e ， a t t a c k sa g a i n s tc r y p t o g r a p h i ch a s hf u n c t i o n sa r ea l s oo fg r e a tc o n c e r n , o n et y p i c a l a t t a c ko fw h i c hi sb i r t h d a ya t t a c k b i r t h d a ya t t a c kd e p e n d so nt h el e n g t ho ft h e m e s s a g ed i g e s t ，w h i c hi st h el e n g t ho fh a s hv a l u e s u c ha t t a c kp r o p o s e sa n e c e s s a r y s e c u r i t yc o n d i t i o nt h a tt h el e n g t ho ft h em e s s a g ed i g e s ts h o u l db el o n ge n o u g h t h e t r a d i t i o n a ld e s i g no fc r y p t o g r a p h i ch a s hf u n c t i o na s s u m e dt h a tt h ei n f o r m a t i o nt ob e s e n ta l ee q u a l l yp r o b a b l ee v e n t sw h i c hm e a n st h ea m o u n to fs o u r c ei n f o r m a t i o ni s s m a l l e s tf r o mt h ep e r s p e c t i v eo fi n f o r m a t i o nt h e o r y a c t u a l l y , f r o mt h es i g h to ft h e s e n d e r , t h ep r o b a b i l i t yd i s t r i b u t i o no ft h es o u r c ei n f o r m a t i o no rt h ea m o u n to fs o u r c e i n f o r m a t i o nc a nb eo b t a i n e dt h r o u g hl o n g - t e r ms t a t i s t i c s m o r e o v e r , t h ep r o b a b i l i t y d i s t r i b u t i o no fs o u r c ei n f o r m a t i o nm a yb ev e r yr e g u l a ri ns o m ec a s e s t h eu n e q u a l l y p r o b a b l ed i s t r i b u t i o n o fs o u r c ei n f o r m a t i o ni st a k e ni n t oa c c o u n tt od e s i g nt h e c r y p t o g r a p h i c h a s hf u n c t i o ni nt h i s d i s s e r t a t i o n 。c o m p a r e d w i t ht r a d i t i o n a l c r y p t o g r a p h i ch a s hf u n c t i o n ，t h ep r o b a b i l i t yo fs u c c e s s f u la t t a c ko ft h eo p t i m i z e d h a s hf u n c t i o ni sg r e a t l yr e d u c e d i no t h e rw o r d s ，t h el e n g t ho ft h em e s s a g ed i g e s tm a y b es h o r t e rw i n lt h es a m ea t t a c kp r o b a b i l i t y t h es p e c i f i cr e s e a r c hw o r k so ft h i sd i s s e r t a t i o na r ea sf o l l o w s t h r o u g ha n a l y z i n ga n dd i s c u s s i n gt h em a p p i n gp r o b l e mo fc r y p t o g r a p h i ch a s h f u n c t i o na f t e rc o n s i d e r i n gt h ep r o b a b i l i t yd i s t r i b u t i o no fs o u r c ei n f o r m a t i o n ，t h e r e l a t i o n s h i pa m o n gi n f o r m a t i o np r o b a b i l i t y , m a p p i n gr e l a t i o na n dp r o b a b i l i t yo f i i i a b s 。l 。l t a c t s u c c e s s f u la t t a c ki so b t a i n e d i nt h i sd i s s e r t a t i o n , t h ep r o b a b i l i t yo fs u c c e s s f u la t t a c k w a so p t i m i z e d , a n dt h e nah e u r i s t i ca l g o r i t h mo fc r y p t o g r a p h i ch a s hf u n c t i o nb a s e d o np r o b a b i l i t yd i s t r i b u t i o no fs o l i c e i n f o r m a t i o nw a sp r o p o s e d t h eh e u r i s t i c a l g o r i t h m i sb e e ns i m u l a t e da n de s t i m a t e dt h r o u g hs i m u l a t i o nr e s u l t s t h r o u g h m u l t i p l ei t e r a t i o n s ，o p t i m i z e da l g o r i t h mh a sf o u n das u b o p t i m a lm a p p i n gr e l a t i o nt o a c h i e v et h ec o n v e r g e n c eo ft h ep r o b a b i l i t yo fs u c c e s s f u la t t a c k c o m p a r e dw i t ht h e t r a d i t i o n a l a l g o r i t h m ，t h es u b - o p t i m a la l g o r i t h mh a sm a d et h ep r o b a b i l i t yo f s u c c e s s f u la t t a c kr e d u c e dw i t ht h es a l l l ep a r a m e t e r s ，w h i c hi m p r o v e st h es a f e t y p e r f o r m a n c eo f t h ec o m m u n i c a t i o np r o c e s s s e c o n d l y , t h ed e f i n i t i o n so ft h ed e g r e eo fb a l a n c ea n dt h eb a l a n c ea n a l y s i so ft h e b i r t h d a ya t t a c ka r ei n t r o d u c e d ，a sw e l la st h ec o n c l u s i o n so ft h eb a l a n c eo fm d ( m e r k l e d a m g a r d ) t r a n s f o r mw h i c hi sc o m m o n l yu s e d t h ec o n c l u s i o n so fp r e v i o u s s t u d i e sh a v es h o w nt h a tt h eb a l a n c es i z eo fat r a d i t i o n a lc r y p t o g r a p h j ch a s hf u n c t i o n w i t hg o o ds e c u r i t yp e r f o r m a n c ei sc l o s et o1 m o r e o v e r ，t h ec o n c e p to fb a l a n c ei n t o t h ep r o p o s e dh a s hf u n c t i o ni si n t r o d u c e da n di t sb a l a n c ef o r m u l ai se x p o r t e d t h r o u g h t h eb a l a n c es i m u l a t i o na n dc o m p a r i s o nb e t w e e nt r a d i t i o n a li d e a lc r y p t o g r a p h i ch a s h f u n c t i o na n do p t i m i z e dh a s hf u n c t i o n ，i th a sv e r i f i e di nt h i sd i s s e r t a t i o nt h a tag o o d c r y p t o g r a p h i ch a s hf u n c t i o nn ol o n g e rp o s s e s s e st h ec h a r a c t e rt h a tt h ed e g r e eo f b a l a n c ei sc l o s et o1w h e nt h ep r o b a b i l i t yo fs o u r c ei n f o r m a t i o ni su n e q u a l l yp r o b a b l e t h ep e r f e c tb a l a n c ed e f i n i t i o na n dc o n c l u s i o n s 弱w e l la st h ec o r r e s p o n d i n gt h e o r e t i c p r o o f sw i l lb et h en e x tr e s e a r c hf o c u s k e yw o r d s ：c r y p t o g r a p h i ch a s hf u n c t i o n ；m a p p i n gr e l a t i o n ；p r o b a b i l i t yd i s t r i b u t i o n o fs o u r c ei n f o r m a t i o n ；b i r t h d a ya t t a c k ；b a l a n c ed e g r e e ；i n f o r m a t i o n s e c u r i t y i v 第1 章引言 第1 章引言 1 1 研究背景及意义 全球网络化的发展标志着人类进入了信息社会。信息作为一种资源，它的 普遍性、共享性、增值性、可处理性和多效用性，使其对于人类具有特别重要 的意义【玎。信息安全的实质就是要保护信怠系统或信息网络中的信息资源免受各 种类型的威胁、干扰和破坏，即保证信息的安全性。根据国际标准化组织的定 义，信息安全性的含义主要是指信息的完整性、可用性、保密性和可靠性。信 息安全得到国家、政府、部门和各个行业的极大重视，是一个不容忽视的国家 安全战略。在众多通信方式中，无线网络由于其无线特征被广泛运用，与此同 时，因为无线网络中传送的数据是利用无线电波在空中辐射传播，它的数据安 全性成了最重要的问题。信息认证技术在无线通信安全中占据重要地位，它通 过数字签名、消息摘要以及身份认证理论和技术实现信息完整性检测，保护信 息的抗否认性。信息认证技术包含信源、信宿、消息完整性、消息的序号和时 间等方面，好的信息认证技术使得接收方在收到发送方的报文时，能够验证收 到的报文是真实且未被篡改，这包含两个含义：一个是验证信息的发送者是真 正合法的而不是冒充的，即数据起源认证；二是验证信息在传送过程中未被篡 改、重放或延迟等，即数据安全认证。信息认证的检验内容应包括：证实报文 的信源、信宿、报文内容是否遭到偶然或有意的篡改、报文的序号是否正确、 报文的到达时间是否在指定的期限内等。总之，信息认证使接收者能识别报文 的源、内容的真伪、时间有效性等，这种认证只在相互通信的双方之间进行， 而不允许第三者进行上述认证。 数据的完整性可以通过消息认证模式来保证，一个消息认证方案是由一个 三元组( k ，丁，i ，) 组成：k 代表密钥生成算法，用于随机生成密钥k ；t 代表标签 算法，由密钥k 及消息m 生成标签6 = 瓦( m ) ；v 代表验证算法，由密钥k 、消 息必和标签6 验证通信过程是否保证了数据的完整性，输出1 位d = 玩( 尬6 ) 。 要求对于明文空间中的所有消息m 满足：当6 = 圪( 时) 时，输出d = l ，代表数 据的完整性；否则输出d = 0 ，代表数据被更改，通信过程不安全。从消息认证 方案可以看出，通信过程中三元组中的标签算法丁的好与坏尤为关键，关系到整 第1 章引言 个通信过程是否安全，加密哈希函数算法就属于标签算法r ，通常，在通信过程 中，为了检验信息或文档的完整性，利用加密哈希函数将需要发送的信息生成 一个摘要信息，发送者将原信息和摘要一起发送给接收者，接收者收到信息后 再次运行掇整啥希丞数褥载耨舱摘要。如果该摘要与收郅筋摘要一样，说踞信 息未被篡改；如果不一样，说明信息被篡改，通信过程不安全。加密哈希函数 必须是单向函数，即根据信息可以计算出相应的哈希值，但是无法通过特定的 哈希值恢复其对应的原始消息。加密哈希函数需要满足以f 三个标准：原像计 算困难性。第二原像计算困难性和抗碰撞性，符合这些标准的加密哈希函数在 信息安全领域有着非常广泛的应用。 加密哈希函数算注是公开的，对于攻击者来说也一样，攻击者只需要截取 信息，也可以计算得蟊信息的摘要值。加密哈希函数是从一个可变大小钓信息 创建一个固定大小的摘要，减少了安全传输数据量的大小，这种函数的创建最 好用迭代来完成，即在创建摘要时重复使用一介压缩函数，这种方案称为迭代 姐密哈希函数。在设讨压缩函数时，有砥神不同的方法，鄹从s c r a t c k 割锝压缩 函数；或者利用已有臼勺分组密码构造压缩函数。 在通信物理层传输的研宄一，哈夫曼【1 1 利用佰源信息的概率分布设计出了最 优的信源编码，成功宴现最小的信息冗余度。受到物理层方法的启发，考虑将 信源信息的概率分布应用于加密哈希函数设计中，一般来说，现在的文献都假 设需要发送的信息为随机等概率发生，并未考虑发送信息的_ 真实概率分布问题。 实际上，发送信息的概率分布可以通过长期观察统计获得，而且在某些特定的 锖况下，信息概率分布也符合一些常舄的分布委型。如果戮爆信息懿不等摄分 布，将少量的发生概率大的信息对应于一个消息摘要，而将大量的发生概率小 的信息对应于一个消息摘要，虽然这样的不均匀分布导致要寻找可以替换发生 概率小的信息更容易，且可能造成总钵寻找碰撞成功概率升高。但是由于该信 息很有可能不足需要发送的信息，相比之下攻击成功的概率是可能减少的，所 以将信源概率分布信息加入考虑范围中很有必要。如果能够设计出优化的加密 哈希函数，该函数可猷建立一个最优的映射关孬将攻击成功的概率降到最低， 使得新加密哈希函数酌安全性能优于传统加密蛤希函数，这将大大提高通信传 输过程的安全性。根据现在的所有文献来看，本文的创新在于佶鉴物理层编码 方法理念到高层安全算法设计中，将发送信息的概率分布考虑边加密哈希函数 算法设计中，该研究终合了信息论、概率论、信息安全理论等多方硬内容，具 2 第1 章引言 有较大的科学研究意义。 1 2 加密哈希函数技术及其攻击的研究现状 所有的加密哈希函数都需要从可变大小的信息创建一个固定大小的摘要， 运用迭代可以顺利完成这种函数的创建。般使用带有可变长度输入的加密哈 希函数，创建一个带有固定长度输出的函数并使用必要的次数，这种方案被称 为迭代加密哈希函数。而这种固定长度输出函数称为压缩函数，这种压缩函数 压缩一个n 比特的串来创建一个m 比特的串，这里咒通常大于m 。 m e r k l e d a m g a r d 方案【2 】就是一个迭代加密哈希函数，它是今天许多加密哈希函数 的基础，具体方案如图1 1 所示。 篷鳝函数压缩函数压编蘧数 图1 1m e r k l e d a r n g a r d 方案 该方案运用步骤为： ( 1 ) 把信息长度和附加材料附着在信息上，这样就创建出了一个扩充信息。 可以将这个扩充信息均匀地分为，2 比特的分组，这里刀代表由压缩函数处理的分 组的大小。 ( 2 ) 把信息分成，个分组分别处理，每一个分组都是狞比特。可以把每一个分 组分别称为m 1 ，m ，m ，将这些分组放入压缩函数进行迭代处理，并把每次迭 代中创建的摘要称为日，日，e 。 ( 3 ) 开始迭代之前，给摘要风设置一个固定的值，这个值称为i v ( 起始值或 者起始向量) 。 ( 4 ) 利用压缩函数在每次对q 一，和m 的迭代操作中创建一个新的e 。用数 学方式来表达，就是说t , = 厂( i - , - ”m i ) ，这里的厂就是压缩函数。 ( 5 ) 经过多次迭代后，得到最后的消息摘要，也就是只。 3 第1 章引言 m e r k l e - d a m g a r d 方案是由压缩函数对信息进行多次迭代处理，因此如果压 缩函数具有抗碰撞性，对应的这种加密哈希函数也具有抗碰撞性，这样设计加 密哈希函数就等价于设计一个具有抗碰撞性的压缩函数。并把它嵌入到 m e r l d e d a m g a r d 方案中。如前文所述，加密哈希函数的设计方法之_ 是压缩函 数是s c r a t c h 制得的，这些压缩函数是特别为适应这个目的设计的，比如消息摘 要( 泗) 群，安全哈希算法( s h a ) 群，t l i p e m d 和h a v a l 。另一种是压缩 函数利用已有的分组密码构造出，使用这一方、法的主要方案包括r a b m 方案。 d a v i e s m e y e r 方案，m a t y a s m e y e r - o s e a s 方案和m i y a g u c h i p r e n e e l 方案。前景广 阔的加密哈希函数之一就是基于m e r k l e d a m g a r d 方案的s h a 5 1 2 ，该方案使用 5 1 2 比特的消息摘要：另一种有前景的加密哈希函数就是w h i r l p o o l ，该函数已 被n e s s i e 认可，w h i r l p o o l 是一个基于m i y a g u c h i p r e n e e l 方案的迭代加密哈希 函数，它运用一个对称分组密码来代替压缩函数，这个分组密码是一个与这一 目的相适应的改进型a e s 密码。 总体来说，目前从s c r a t c h 制得的如密哈希函数主要有m d x 系列和s h a 系 列，m d x 系列包括m d 4 t 3 1 、m d 5 1 4 1 、h a v a l 5 1 、r i p e n d l 6 等；s h a 系列包括 s h a o 【7 1 、s h a 1i s 、s h a 2 5 6 、s h a 3 8 4 f 9 1 等。由r o nr i v e s t 设计的集中哈希算 法，称为m d 2 、m d 4 和m d 5 ，这里的m d 代表消息摘要( m e s s a g ed i g e s t ) 。m d 2 是r i v e s t 在1 9 8 9 年开发的算法，加密后结果是唯一的，安全性不佳。为了提高 m d 2 算法的安全性，r i v e s t 将其升级为m d 4 算法，m d 4 算法使用了基本的算 术和布尔运算，其设计原则采用了迭代结构的思想，m u 4 把信息分成5 1 2 比特 的分组并创建了一个t 2 8 比特的摘要，结果由于大小为1 2 8 比特消息摘要太小 了而不能抵抗碰撞攻击。m d 5 算法是m d 4 的加强版，在m d 4 的基础上增加了 “安全带子”的概念，虽然复杂度大一些，但却更为安全。其他加密哈希函数算 法也相继被提出，包括h a v a l 、姗e m d 、r i p e n d 一1 2 8 、r i p e m d 一1 6 0 、s h a 一0 和s h a ，1 等，它们的大多数也是基于m d 4 算法的设计原则。s h a 称为安全哈 希算法，是一个标准，该标准由美国国家标准与技术研究院( n i s t ) 提出并公布为 联邦信息处理标准( f i p1 8 0 ) ，也可以被称为安全哈希标准( s h s ) 。该标准主要基 于m d 5 ，在1 9 9 5 年曾由f i p1 8 0 】修订，包括s h a 1 ，之后又在f i p l 8 0 2 下作 了修订，定义了四个新的版本：s h a - 2 2 4 、s h a ，2 5 6 、s h a 一3 8 4 和s h a - 5 1 2 。表 1 1 列出了这些版本的特点。 4 第1 章引言 r i p m e d 算法是欧洲计划r i p e 的组成部分，它有几个版本，r i p e m d - 1 6 0 是一个带有1 6 0 比特消息摘要的哈希算法，是h a n sd o b b e r t i n ，a n t o o nb o s s e l a e r s 和b a r tp r e n e e l 在1 9 9 6 年提出来的【6 】。r i p e m d 1 6 0 运用与m d 5 相同的结构， 创建的哈希值大小为1 6 0 比特。h a v a l 是一个可变长度的哈希算法，可以有大 小为1 2 8 、1 6 0 、1 9 2 、2 2 4 和2 5 6 几种消息摘要，分组大小是1 0 2 4 比特。 近十几年，对于加密哈希函数的设计和分析一直在进展，同时也包括对加 密哈希函数的攻击。1 9 9 2 年，b e r td e nb o e r 等人对m d 4 的最后两轮迭代进行了 攻击【5 1 1 ，他们指出如果剥夺m d 4 三轮算法的第一轮，就有可能在给定一个初始 输入值的情况下找出两个不同的消息哈希到相同的输出，在普通电脑上只需要1 毫秒就能找到碰撞。1 9 9 6 年，h d o b b e r t i n 对m d 4 算法完整算法进行攻击i l ， 并以2 啦的概率找到碰撞，在普通电脑上只耗费了几秒钟的时间，并给出了实际 运用中找出碰撞的例子；1 9 9 8 年，h d o b b e r t i n 证明了m d 4 算法的前两圈不是 单向函数f 】1 】，这意味着m d 4 算法容易遭受原像攻击或者第二原像攻击。在这之 前，h d o b b e r t i n 也找出了对于两圈r r i p e m d 的碰撞【1 2 】，复杂度为2 川，他还 分析了m d 4 算法的攻击。随着m d x 系列加密哈希函数的进展，对于其安全性 的分析也随之更加深入，19 9 4 年，b a r td e nb o e r 和a b o s s e l a e r s 找到了m d 5 算 法中压缩函数的一种伪碰撞【l3 1 ，证明出同一个明文在不同的初始值下仍然可以 得到相同的哈希摘要值。在1 9 9 6 年欧洲密码大会上，h d o b b e r t i n 公开了另一 种形式的伪碰撞【14 1 ，使得两个不同初始值下的不同消息仍然可以产生碰撞。在 1 9 9 8 年国际密码大会上，ec h a b a t l d 和a j o u x 证明了用差分攻击方法可以以2 6 1 的复杂度找到s h a 0 的一个碰撞【l5 1 ，复杂度小于生日攻击，但是对于s h a 1 ， 该方法就比生日攻击复杂度要高，说明了s h a 1 提升了s h a 0 的安全性能。 针对加密哈希函数的更为有效的攻击方法出现在2 0 0 4 年。e l ib i h a m 和r a 6 5 第1 章引言 c h c n 提出了两个对s h a - 0 中压缩算法的几乎完全碰撞【1 6 j ，并证明出s h a 。0 的 强度在每轮迭代中是有变化的。a j o u x 给出了一个由四个明文块构成的s h a 0 的碰撞【1 。刀。2 0 0 5 年v a n d i e r e n d o n c k h 等人提出基于x o r 结构的加密哈希函数 【2 引，并保证其抗碰撞性。2 0 0 6 年d o n g h o o nc h a n g 等人提出了基于r c 4 的新加 密哈希函数【2 4 】，其中加密哈希函数的输入从1 6 比特到6 4 比特可变，该设计标 准与之前所熟知的加密哈希函数设计标准完全不同，但是作者证明了其安全性， 而且其效率与s h a - 1 相当。2 0 0 7 年j i el i a n g 等给出了对加密哈希函数m d 5 更 优的碰撞攻击1 2 引，该攻击基于2 0 0 5 年王小云提出的m d 5 差分路线，改进的攻 击提高了成功的可能性和复杂度，对于m d 5 的完整攻击在5 小时内完成。2 0 0 9 年，j u t l a c s 给出了一个构造加密哈希函数的新技术【2 6 j ，用来评估相似的哈希 编码的距离，和设计实际的加密哈希函数。2 0 0 9 年2 月的i c c s n 会议中， s e l v a k u m a r a l 等对一些加密哈希函数进行了系统描述与分析【7 | ，正式给出了 几种不同的方法定义的安全性能和对加密哈希函数的攻击。接下来1 0 月的国际 计算机与信息技术会议中，鉴于选用合适的地址映射方案可以避免碰撞， f e n g l o n gs o n g 等人提出了一种新的基于x o r 的映射方案哈希映射函数1 2 剐。 2 0 1 1 年的国际电子信息及控制工程会议中，j i a l i nc h e n 等人指出了在各种文献 中加密哈希函数的两种相似的碰撞测试存在的问题1 2 圳，并建立了碰撞测试的随 机映射和随机自映射概率模型，分别用于检验遍历各态历经性的随机映射和随 机自映射，同时也利用测试模型分析了很多混沌加密哈希函数和传统加密哈希 函数。在2 0 0 4 年国际密码学大会上，王小云等人宣布了一系列典型加密哈希函 数的碰撞，并当场破解，包括m d 4 18 1 、m d 5 【1 9 j 、h a v a l 1 2 8 f 圳，王小云提出 一套针对m d x 系列的加密哈希函数的分析技术，得出了很多重要结论，将m d 4 和r i p e m d 算法碰撞的复杂性分别降低到2 s 和2 1 8 。同时给出了得到满足差分 路线的充分条件的方法，以及如何使用明文修改技术来提高碰撞攻击的成功概 率。她利用明文修改技术攻击m d 5 算法，用两个明文块产生了完全碰撞，将 攻击复杂度分别降低到2 3 9 和2 3 2 。2 0 0 5 年，王小云进一步改进攻击方案，对 s h a 0 2 、s h a 1t 2 2 】算法进行碰撞攻击，对s h a 0 完整算法的攻击复杂度少于 2 3 9 ，对s h a 1 的攻击复杂度少于2 6 9 ，这是首次对s h a 1 的攻击复杂度少于理 论值2 。这一攻击技术对现有的加密哈希函数提出了严峻的挑战，促进了新哈 希算法的开发研究。虽然已经转到安全性更强的s h a 2 算法，但是s h a 2 的 设计与s h a 1 相同，潜在危险仍然存在。因此，美国n i s t 于2 0 0 7 年开始在 6 第1 章引言 全球征集新的哈希算法，并将被命名为s h a 3 ；截止2 0 0 8 年1 1 月，共提交6 4 个算法；2 0 0 8 年1 2 月有5 1 个算法被n i s t 接受作为第一轮候选算法；2 0 0 9 年 7 月，n i s t 公布了进入第二轮的1 4 个算法；2 0 1 0 年公布进入最终一轮的5 个 算法；最终的算法将在2 0 1 2 年宣布。 2 0 1 0 年公布的s h a 3 备选的五个方案也被热烈讨论着，五个方案分别是： 来自瑞士的b l a k e ，g r a z 理工大学和丹麦理工大学合作的g r a s t l ，新加坡华裔 信息安全专家伍宏君的j h ，j o a nd a e m e n 为主要成员的k e c c a k ，以及b r u c e s c h n e i e r 为负责人的s k e i n 。b l a k e 算法借鉴了加密哈希函数l a k e 和流密码 c h a c h a 的设计方法，并使用h a i f a 迭代框架【3 0 1 ，h a i f a 迭代框架由b i h a m 和 d u n k e l m a n 提出，针对m i ) 迭代结构的弱点在压缩函数中加入了随机盐和计数 器。它的压缩算法是流密码c h a c h a 的修改版，c h a c h a 有优秀的安全性能，可 以并行实现。g r a s t l 算法是由k u n d s e n 和m e n d e l 等人设计的哈希算法，采用了 宽管道m d 迭代结构，能抵抗一般的通用攻击，压缩函数主要由2 个排列组成， 排列基于a e s t 3 1 】构造，采用s p n 结构，s 盒与a e s 的相同。j h 算法采用宽管 道的m d 结构，使用了有效差分传播的设计，其中e d p 的设计采用s p n 结构。 k e c c a k 是由s t 微电子公司和n x p 半导体公司共同设计的哈希算法，它使用基 于s p o n g e 构造的s p o n g e 函数【3 2 1 ，k e c c a k 的状态更新使用的是作用在三维数组 上的5 步迭代排列。s k e i n 是由一个专家团队提交的哈希算法，既可以使用迭代 结构，也可以使用树结构，s k e i n 主要由三个部件组成：t h r e e f i s h 可调分组密码、 唯一分组迭代和可选参数系统。它有三个版本，对应不同的内部状态大小： s k e i n 2 5 6 、s k e i n 5 1 2 、s k e i n 1 0 2 4 ，其中s k e i n 5 1 2 是主要版本，其余两个在特 殊环境下使用。近两年很多研究者提出了对这五种方案的安全性分析。h eq i a n g 等使用拼接分段技术对b l a k e 算法进行了攻击【3 3 1 ，v i d a l i 等人对b l a k e 的变 体b l o k e 和b r a k e 进行了碰撞分析【3 4 | ，b l o k e 和b r a k e 是b l a k e 稍弱 一点的版本。还有r i s h i r a jb h a t t a c h a r y y a 等对j h 加密哈希函数的安全性分析【3 5 i ， 以及j o o y o u n gl e e 对j h 加密哈希函数的抗碰撞性分析【3 6 j 等，今年将公布s h a 3 的最终方案。 加密哈希函数是密码学和信息安全领域中一个非常重要的基本组成部分， 本文讨论其在保证信息完整性方面的运用。由上文的研究现状总结可以发现， 自从以m d 5 为代表的m d 系列加密哈希函数被王小云等人破译后，加密哈希函 数的安全性能又引起了研究者们极大的关注。加密哈希函数的设计发展空间很 7 第1 章引言 大，探寻性能更优越的加密哈希函数方案是信息安全领域的重要前沿课题。过 去的研究中，研究者的重点都放在压缩函数及迭代问题上，信源的概率分布一 直被忽略，基于信源概率分布的加密哈希函数算法研究不但具有较高的学术价 值，而且在信息安全领域也有着广阔的应用前景。其研究的理论成果可直接应 用到实际加密哈希函数的设计中，提高实际加密哈希函数的安全性能。 1 3 主要工作及章节安排 本文借鉴哈夫曼信源编码中利用的信源信息概率分布的设计思路，将信源 概率分布引入加密哈希函数设计中。加密哈希函数的设计需要符合三个基本原 则，而对加密哈希函数三个基本原则最常用的攻击为生日攻击。引入信源概率 参数后，通过对整体加密哈希函数的框架数学分析，得到信源概率、映射和生 日攻击成功概率的关系，得到基于信源概率分布的加密哈希映射原则，通过理 论推导、证明，提出了一个启发式算法，并对该算法进行仿真与分析，比较了 优化的加密哈希函数与传统加密哈希函数生日攻击概率大小。介绍了平衡度概 念，通过对优化的加密哈希函数算法进行平衡度仿真，验证和分析。 本文主要工作和的结构安排如下： 第一章为引言，主要介绍本课题的研究背景和研究意义，以及加密哈希函 数设计的发展过程和研究现状。 第二章详细介绍相关基础理论知识，包括加密哈希函数的设计准则、消息 认证码的构成、信息完整性如何保证以及加密哈希函数的原理和作用、生日攻 击等。 第三章对加入信源概率分布信息的通信过程进行建模，将问题转换为直观 的数学最优化问题。通过理论推导，提出了一种基于信源概率分布的加密哈希 函数映射设计方法，并对该设计进行了仿真和讨论。 第四章引入平衡度概念，计算第三章提出的优化加密哈希函数算法的平衡 度，仿真了优化算法平衡度，与传统加密哈希函数算法平衡度对比，并对仿真 结果进行了分析讨论。 第五章对全文进行了总结，并对未来的研究进行了展望。 8 第2 章加密哈希函数基础理论 第2 章加密哈希函数基础理论 加密哈希函数常用来保证通信信息的完整性，被发送的消息利用加密哈希 函数产生一个长度大大减少的消息摘要，消息摘要将与消息一起发送，传输过 程中保证消息摘要在信道内安全传输无法被修改。本章简要阐述加密哈希函数 的基础理论，包括信息完整性和信息验证原理、加密哈希函数的设计标准以及 针对加密哈希函数最常见的生日攻击等。 2 1 信息完整性 2 1 1 鸽舍原理 w a t 巧b d e c 于1 9 9 0 年提出了鸽舍原理( p i g e o n h o l ep r i n c i p l e ) p7 1 ，鸽舍原理 是一个很著名的数学问题，它指的是：如果有玎+ 1 只鸽子需要占据胛个鸽舍，那 么最少存在一个鸽舍被两只或者两只以上的鸽子占据。鸽舍原理可一般表述为： 如果k n + 1 只鸽子要占据，z 个鸽舍，那么至少有一个鸽舍被k + 1 只或者更多只鸽 子所占据。 消息摘要需要保证安全传输，而安全信道能保证的安全传输信息长度有限， 所以控制摘要长度很为关键，但是，摘要信息太短又会使得加密哈希函数的安 全性能降低，攻击成功概率加大。这样的话，加密哈希函数的设计尤其重要， 既要保证它的安全可靠性，又不能有太高的复杂度和太长的摘要信息。一般来 说，需要发送的信息比其对应的消息摘要长很多，这就意味着一个摘要会有多 个信息与之对应。假设信息长度为6 比特，消息摘要是4 比特，这时所有可能 的信息数和摘要数就分别是2 6 个和2 4 个，根据鸽舍原理的描述，由于每个信息 都必须对应一个摘要，所以至少有一个摘要被大于四个信息映射到，这就是攻 击者进行攻击的漏洞所在，在后面章节中将会提及攻击者如何发动攻击。 2 1 2 消息与消息摘要 加密哈希函数