基于AES的双倍长度Hash函数

基于AES的双倍长度Hash函数 第 21 卷第 2 期平顶山学院学报Vol . 21 No . 2 Ap r . 2006 Journal of Pingdingshan U niversity 2006 年 4 月 函数基于 A ES 的双倍长度 Hash 1 王红瑞,王天芹 ()河南大学 ,开封 475001 摘 要 : MD5 和 SHA1 相继被攻击后 , Hash 函数常用的 MD 设计方法已经不能满足现实的安全性需 求 ,人们纷纷转而研究基于分组密码的 Hash 函数 , Whirlpool 就是其中一个很好的代表 . 这里参照 Whirlpool ,在 分析近来提出的新的攻击方法的基础上构建了一个基于 A ES 的双倍长度 Hash 函数 D H ,它产生 512 位散列值 ,220 () Ω安全性为2. 关 键 词 : Hash 函数 ;A ES ;双倍长度的 Hash 函数 ;基于分组密码的 Hash 函数 () 文章编号 :1673 - 1670 200602 - 0030 - 02 中图分类号 : TP315 文献标识码 :A 先进行一次密钥加 ,然后做 10 次轮处理 . 其中 ,每轮有 函数设计方法简介 0 Hash ρ( ) ( ( ) βσθα四步操作k x?k ???x, k 为密钥 , x 为消息分 通常 , Hash 函数的设计分以下两个步骤 : ) 组 ,均为 4 ×8 的矩阵: n m n 首先 ,设计一个压缩函数 f :{0 ,1}×{0 ,1}? { 0 ,1}.α( ) 、字节变换 : b= e :e = Sb ,0 ?i ?3 ,0 ?j ?7 . 唯 1 ij ij 可直接设计 ,也可基于加密算法 E 通过 P GV 方法构建 .一的非线性变换 ,对矩阵中每个元素通过 S 盒变换 ,我们采 3 然后 ,通过对 f 进行域扩展得到 Hash 函数 H : { 0 ,1} 用 Whirlpool 中的 S 盒 .n ?{0 ,1}.θ() ?i ?3 ,0 ?j ?,0 2 、行移位变换 : e= t : t = e () ij i - jmod 4 ,j 为了增加散列值的长度以达到更好的安全性 ,我们既 7 . 该变换将各行的元素分散到其他行中 . 可以设计新的有更长输出的压缩函数 ,也可以使用安全的 σ( ) 3 、列混和变换 : t = u : u = t ×C ,其中 C 是一个 8 ×8 () 方法连接两个散列值 一般称作双倍长度的 Hash 函数. 的矩阵 ,用于混和各列的元素 ,我们采用 Whirlpool 中的 C. β( ) 4 、密钥加 : k u= v : v= u?k,0 ?i ?3 ,0 ?j ?7 .ij ij ij 1 Hash 算法描述 0 r r r - 1 iρ) ( 轮密钥的产生如下 : K= K ; K=c ] K,其中 K我们构建了一个基于分组密码 E 的双倍长度 Hash 函r r ( ) ?S4 r - 1+ j ,c ?0 ,1 ?i ? i 轮用到的轮密钥 ;c 是第 0 ,j i ,j 3 512 512 数 D H :{0 ,1} ×{0 ,1}?{0 ,1},它能处理所有长度 <3 ,0 ?j ?7 . 128 2的消息 . 1 . 3 基于 E 的压缩函数 Fs 的构建 1 . 1 预处理和一些参数说明关于 P GV , 我 们 选 择 不 同 于 Whirlpool 的 Mat yas - 采用一般的 MD 填充方法 ,在原始消息后填充 1 和若 ) ( ) ( Meyer - Oseas 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 :f h,m= E h,m?m. i - 1 i i - 1 i i 干个 0 ,后续原始消息长度的 128 位二进制表示 ,使填充后 首先定义两个基本的相互独立的函数 f 和 f ,我们取 1 2 的消息长度为 255 的整数倍 . 0 ( ) f h,0 ‖m ,i ?L i - 1 i 0 将填充后的 消 息 进 行 分 组 , 我 们 得 到 M = m‖m‖( ) ; 1 2 fh ,m=1 i - 1 i 0)( ,1 ‖mL f h L - 1 ( ) ‖m,其中| m| = 255 ,1 ?i ?L . 求 b 、r 0 ?r < 3满足L i 1 ( ) f h,1 ‖m ,i ?L i - 1 i 1L = 3 b + r , 产 生 新 的 分 组 M = M‖M‖‖M‖ 3 1 2 b ( ) . fh ,m=2 i - 1 i 1 ( )f h,0 ‖mL L - 1 M,其中| M| = 3 ×255 ,1 ?i ?b ;| M| = r ×255 . b + 1 i b + 1 然后 ,在此基础上定义两个使用相同的链接变量 h 来 初始值 H,取 512 位的 0 . . . 0 .0 处理 s 块连续分组的函数 :s 512 3 3 256 512 s ( 压缩函数 F:{0 ,1}×{0 ,1}?{ 0 ,1}, FH-i 0 s ( ) ( ),m‖‖m,其中 h= f,mf ; h = hh 1 j - 1 j j + sj + s i 1 i - 1 i 0 1 0 1 ) 1 ,M= H. 其中 H= h‖h,| H | = 512 ,| h= | h| = 256 . i i i i i i i i s 1 ( ) ( ). fh,m‖ ‖m= h,其中 h= fh,m 2 j - 1 j j + sj + s i 2 i - 1 i Hash 函数 D H 的输出是 dh. 这里 ,s ?{1 ,2 ,3 ,4} , 1 ?j ?L - s , j ?i ?j + s. 1 . 2 加密模块 E 的构建s 0s s 1 ( ) ( )最后 ,构造压缩函数 FH, M= fh , M‖f i - 1 i 1 i - 1 i 2参考 Whirlpool 算 法, 我 们 构 建 了 加 密 过 程 E : { 0 , 1256 256 256 ) ( ,M= H. hi - 1 i i 1}×{0 ,1}?{ 0 ,1}. 以字节为单位 ,将 32 字节的输 s ( 1 . 4 基于 F的 Hash 函数 D H 的构建 Hash 函数 D H H0 , μ() 入转换成 4 ×8 的矩阵进行处理 , a= b : b= a,1 ?i ? ij 4i + j ) 3 ,1 ?j ?7 ,ai 为输入的第 i 个字节 , bij 为矩阵 b 中位于第 i M定义如下 : ( )Algorit hm D H H0 , M 行 、第 j 列的字节 . 输出的时候进行相应的逆转换 . For i = 1 to b do 证消息前缀固定 . 4 ( )Hi = FH,M 2 . 3 双倍长度的 Hash 函数及其安全性 在并行技术发展很i - 1 i r + 1 快的今天 ,需要产生很长的散列值 ( ) If r > 0 t hen dh = FH,Mb b + 1 时 ,我们倾向于并行运行多个较小的模块来达到更高的效 Else if r = 0 t hen dh = Hb 率和代码使用率 . Ret urn dh 4 r + 1 D H 用到了两个压缩函数 ———F和 F因此 D H 上的 算法设计及其安全性分析 2 4 r + 1 冲突必定是 F或者 F上的冲突 . 6 文中详细研究了函 s s s 数 F= f‖f的安全性 ,指出 :若 f和 f是相互独立的 ,那 2 . 1 压缩函数的设计及其安全性1 2 1 2 s n 2 s - 1 () ) Ω( 目前 ,直接设计的压缩函数多遵循 MD 原则 ,然而新的 么找到 F的一个冲突的复杂性为2/ sn,所以 D H ) 3 256 2 220 ( ) Ω ( ) Ω ( 攻击方法使这种设计原则很难继续满足现实的安全性要 的安全性为2/ 4×2564= 2, 对实际应用来 求 . 说 ,这是足够安全的 . 基于分组密码的压缩函数设计原则以前很少被使用 , 3 小结 主要由于分组密码自身不完善 ,而 A ES 的出现改变了这种 状况 ,它有足够的分组长度 、没有弱密钥 、而且还能有效抵 MD 设计原则已不能满足目前的安全需求 , 在找到理 抗差分攻击 . 目前的 Hash 函数设计都倾向于使用基于分组 论上更加安全高效的直接设计原则以前 ,基于分组密码的密码的构造方式 . Whirlpool 就是其中一个很好的例子 ,其加 Hash 函数将是我们的首选 . 这里构建的具有 512 位散列值 密过程基于 Rijndael ,在效率上高出许多 ,同样能抵抗差分 的双倍长度 Hash 函数 D H 与 Whirlpool 算 法 相 比 , 在 并 行 1 攻击. 我们构建的加密过程只是在处理规模上与它不同 , 环境下有更高的运行效率 ,也有足够的安全性 ,在那些要求 所以也是能够抵抗差分攻击的 . 更高效率的环境下 ,可以选择使用它 . (4 文中提出的攻击 lo ng message p re - image at tack 和 ) herding at tack虽然对一般的 Hash 函 数 只 是 理 论 上 的 , 但 是对那些压缩函数很容易计算出固定点的 Hash 函数 ,弱冲 参考文献 : n/ 2 n Ο( ) 突攻击的复杂度会降低到max{2,2/ L }. 通常认为 12 种安全的 P GV 构造方案中只有 4 个能够 1 ISO/ I EC 10118 - 3 : 2004 , Dedicated hash - f unctio ns 5 S . 抵抗常规的定点攻击 ,然而中作者提到 Kelsey 在他的未 2 公开发表的文章 A Lo ng Message At tack o n SHAx , MDx , 王小云 , 来 学 佳 . Collisio n for MD4 , MD5 , HAVAL - Tiger , N - Hash , and Snef ru 中 使 用 特 殊 方 法 找 到 了 128 , R IP EMD DB/ OL . ht tp : / / www . i nfo sec . sdu. Miyaguchi - Preneel 方案的固 定 点. 所 以 不 同 于 Whirlpool , edu. cn/ paper/ 199 . p df 我们使用的是效率稍低但没有固定点的 Mat yas - Meyer - 3 BAR T PR EN EEL etc. Hash f unctio ns based o n block ci 2 Oseas 方案 . p hers : a synt hetic app roach DB/ OL . ht tp : / / po rt al . acm . o rg/ cit atio n . cf m ? id = 188105 . 188183 2 . 2 域扩展及其安全性 Mer kle 目前大多数域扩展都采用增强的 MD 方法 , R.4 J O HN KEL SE Y etc. Herdin g Hash Functio ns and t he 和 I. Damgard 证明如果初始值是固定的 ,且填充内容包含 Nost radamus At tack DB/ OL . ht tp : / / ep ri nt . iacr . o rg/ 原始消息的 长 度 信 息 , 那 么 , 如 果 压 缩 函 数 是 抗 冲 突 攻 击 2005/ 281 . p df 〗 的 ,对应的 Hash 函数也是抗冲突攻击的 . 5 J EAN - SEBAS T I EN CORON . Mer kle - Dam gard Re2 () 但是 5 文中 ,作者从不可辨性 indifferentiable角度证 visited : how to co nst ruct a hash f unctio n DB/ OL . 明了它并不能保持模型的随机性 . 同时作者证明 :对前缀固 ht tp : / / www . eleves. ens. f r/ ho me/ co ro n/ p ublicatio ns/ () 定 p refix - f ree的消息 ,使用 MD 方法构建出来的 Hash 函 mer kle . p df 数与随机模型是不可辨的 . 我们的构建中 ,通过 f和 f在 6 M R IDUL NAND I. Desi gn of Efficient Secure L arge Hash 1 2 每块分组的头一位分别填充 0 、0 、 0 、1 和 1 、1 、 1 、0 ,来保 Values DB/ OL . ht tp : / / ep ri nt . iacr . o rg/ 2004/ 296 . p df A Double - Length Ha sh Funct ion Ba sed on AES WAN G Ho ng - rui , WAN G Tian - qin ( )Depart ment of Co mp uter and Info r matio n Engineering , Henan U niversit y , Kaifeng , Henan 475001 , China Abstract :Anno uncement s of t he breaking of MD5 and SHA1 have showed t hat t he mo st pop ular MD de2 sign p rinciples fo r hash f unctio ns co uldn’t be securely used any mo re . L uckily , t he emergence of t he A ES has motivated renewed interest in building a block - cip her based hash f unctio n . Whirlpool is o ne of t he best ex2 amples , following w hich we co nst ruct a do uble lengt h hash f unctio n wit h a 512 - bit hash and a collisio n resis2 Ω() tance of 2220. Key words : hash f unctio n ; A ES ; do uble - lengt h hash f unctio n ; block - cip her based hash f unctio n Whirlpool