（計算機軟件與理論專業(yè)論文）hash函數(shù)性質與安全性研究.pdf

h a s h 函數(shù)性質與安全性研究 摘要 h a s h 函數(shù)是密碼學中最基本的模塊之一，被廣泛應用于數(shù)字簽名、消息鑒 別、模擬r a n d o mo r a c l e 和偽隨機數(shù)生成器等領域，是近幾年密碼學研究的熱點 領域。本文對h a s h 函數(shù)的研究現(xiàn)狀和存在的問題做了全面的介紹，比較和分析 了h a s h 函數(shù)的各種設計思想和分析方法，并對若干問題進行了探討。m d 迭代方 式是目前最常用的設計方法，通常為了保證h a s h 函數(shù)的抗碰撞性需要壓縮函數(shù) 具有抗自由碰撞性。本文進一步研究了m d 迭代方式構造的h a s h 函數(shù)和壓縮函數(shù) 、 之間的關系；在黑盒子模型下證明了在壓縮函數(shù)不能抵抗某些自由碰撞攻擊的條 件下，m d 迭代方式構造的h a s h 函數(shù)仍然具有抗碰撞性。此結果放寬了對壓縮函 數(shù)的限制，更有利于壓縮函數(shù)的設計。平衡度是衡量h a s h 函數(shù)安全性的新指標， 本文重點研究了壓縮函數(shù)平衡度在m d 迭代方式下的保持問題。在原定義模型下， m d 迭代方式不能保持壓縮函數(shù)的平衡性，從而給壓縮函數(shù)的設計要求帶來了困 難。鑒于此本文提出了局部平衡度的概念，并證明當壓縮函數(shù)滿足局部平衡性要 求時，m d 迭代方式構造的h a s h 函數(shù)的平衡度要大于等于壓縮函數(shù)的平衡度。最 后從實際應用角度出發(fā)，討論了h a s h 函數(shù)針對目前攻擊方法的預防措施，通過 對算法簡單升級的辦法來增加其抵抗攻擊的能力。 關鍵詞：h a s h 函數(shù)，抗碰撞性，m d 構造方式，h a s h 函數(shù)平衡度，差分攻擊。 h a s h 函數(shù)性質與安全性研究 a b s t r a c t h a s hf o n c t i o ni so n eo ft h em o s t i m p o r t a n t f u n d a m e n t a lm o d u l e so f c r y p t o g r a p h y i ti sw i d e l yu s e di nm a n yc r y p t o g r a p h i ca p p l i c a t i o n s ，s u c ha sd i g i t a l s i g n a t u r e ，m e s s a g ea u t h e n t i c a t i o n ，r a n d o mo r a c l es i m u l a t i n ga n dp s e u d or a n d o m n u m b e rg e n e r a t o r d u r i n zr e c e n ty e a r s ，h a s hf u n c t i o nh a sa t t r a c t e dm o r ea n dm o r e a t t e n t i o ni nc r y p t o g r a p h i cf i e l d i nt h i st h e s i sw ed e s c r i b et h es t a t eo ft h ea r tf o r c r y p t o g r a p h i ch a s hf u n c t i o n sa n ds o m eo p e np r o b l e m s ，c o m p a r ea n da n a l y z ed e s i g n a n da t t a c km e t h o d so fh a s hf u n c t i o na n dd i s c u s si s s n r e sr e l a t e dt oo u rw o r k m d i t e r a t i v es t r u c t u r ei st h em o s tp o p u l a rm e t h o di nr e a ld e s i g n i no r d e rt oc o n t r u c t c o l l i s i o n - r e s i s t a n th a s hf u n c t i o nw en e e dt od e s i g nf r e e s t a r tc o l l i s i o n r e s i s t a n t c o m p r e s s i o nf u n c t i o n w ed i df u r t h e rr e s e a r c hw o r ko nt h er e l a t i o nb e t w e e nt h e s e c u r i t yp r o p e r t i e so fh a s hf u n c t i o na n dc o m p r e s s i o nf u n c t i o na n dp r o v et h a t ，u n d e r c e r t a i nc i r c u r n s t a n c e ，h a s hf u n c t i o nc a nb ec o l l i s i o nr e s i s t a n te v e n t h o u i g h c o m p r e s s i o nf u n c t i o ni sn o ta g a i n s tf r e e - s t a r tc o l l i s i o na r a c k t k sr e s u l tc a nr e l a xt h e s e c u r i t yr e q u i r e m e n to fc o m p r e s s i o nf u n c t i o ni nd e s i g n h a s hf u n c t i o nb a l a n c ei sa n e w l yi n t r o d u c e ds e c u r i t yc r i t e r i o no fh a s hf u n c t i o n w ed i s c u s st h ep r o b l e mo f b a l a l i c ep r e s e r v a f t o ni nm dt r a n s f o r m i no r i g i n a lm o d e lm dt r a n s f o r t r lc a nn o tk e e p t h eb a l a n c eo fc o m p r e s s i o nf u n c t i o n ，w h i c hm a ym a k et h ed e s i g no fc o m p r e s s i o n f u n c t i o nm u c ht r i c k i e r w ei n 打o d u c ep a r t i a l - b a l a n c ec o n c e p t i o nt os o l v et h i sp r o b l e m i tc a nb ep r o v e dt h a tt h eb a l a l i c eo f h a s hf u n c t i o nc a nb ee q u a lo rb i g g e rt h a nt h a to f c o m p r e s s i o nf u n c t i o nw h e nc o m p r e s s i o nf u n c t i o ni sp a r t i a lb a l a n c e f i n a l l yw e s u m m a r i z ek i n d so fa r a c kt e c h n i q u ea n ds o m el a t e s ta t t a c kr e s u l t s t h ew a yt o p r e v e n tt h e s ea t t a c k sf r o mt h ep r a c t i c a lp e r s p e c t i v ei sa l s od i s c u s s e d c o m b i n i n g o t h e r st e c h n i q u e sw ep u tf o r w a r ds e v e r a lp o s s i b l em e t h o d s k e y w o r d s ：h a s hf u n c t i o n ，c o l l i s i o n r e s i s t a n t ，m d s t r e n g h n e ds t r u c t u r e ，b a l a n c e d i f f e r e n t i a la t t a c k h a s h 函數(shù)性質與安全性研究 第一章引言 隨著計算機技術和網(wǎng)絡技術的迅速發(fā)展，信息化和網(wǎng)絡化成為當今世界經 濟與社會發(fā)展的大趨勢。而計算機網(wǎng)絡的開放性和共享性使得對信息安全的需要 更加強烈。信息安全的主要需求包括機密性和可鑒別性兩個部分。信息的機密性 是指未被授權的主體不能得到信息的內容。信息的可鑒別性包括兩個方面，一是 消息來源的鑒別( 數(shù)據(jù)源可鑒別) ，二是消息未被篡改過( 數(shù)據(jù)完整性) 。 過去，對消息的機密性保護是通過物理的安全和信任來得到的，比如檔案 被密封起來并放到絕對安全的地方。對消息可鑒別性的保護依賴于文件或者簽名 的難以偽造。而在電子時代，信件、合同及其他文件被二進制數(shù)據(jù)流所替代。電 子文件具有易復制和易修改的特性，特別是在開放的網(wǎng)絡環(huán)境，電子文件將更容 易被獲取、復制和修改，從而帶來更大的不安全性。 交流對話的保護同樣存在這個問題。對于面對面的交談，人們很容易找到 一個防止竊聽的環(huán)境。并且，交流雙方的身份鑒別也很容易實現(xiàn)。而在網(wǎng)絡中， 人們的身份只是一些代碼或信息流，攻擊者很容易通過截獲或者偽造這些信息來 冒充合法用戶。并且，竊聽這些對話也變得非常容易。 密碼技術可以很好的解決上述問題。很多世紀以來，密碼技術被用來保護 軍事和外交秘密。這些技術的大部分是加密方案，即通過密鑰將消息轉換成密文。 這些密碼對于末授權的用戶是不可鑒別的，只有擁有密鑰的用戶才嗡解密它們。 密碼研究者曾經認為只要保證了信息的機密性同時也就保證了信息的可鑒別性。 其理由如下：如果某個密文經過解密后得到了有意義的消息，那么這個密碼一定 是來源于擁有密鑰的實體。但事實上，構造一個假消息的密文并不一定要知道密 鑰：完整性保護取決于加密算法和算法的模式。 密碼學曾經只是少數(shù)人研究的藝術，但是隨著d e s 的公布以及公鑰體制的 提出，密碼學已經成為一個科學研究領域。新提出的概念和定義清楚地分開了機 密性和可鑒別性問題，并且使得鑒別算法成為一個重要的研究課題。經過近些 年的發(fā)展，已經提出了大量的鑒別方案。這些方案在實際中已經有了廣泛的商業(yè) 應用，比如為電子商務和無線通信系統(tǒng)做安全性保護等等。 鑒別算法主要包括兩個部分，一部分是沒有密鑰的h a s h 函數(shù)，另一部分是 h a s h 函數(shù)性質與安全性研究 有密鑰的m a c 。本論文的主要內容是h a s h 函數(shù)的性質和安全性分析。簡單的說 h a s h 函數(shù)就是把任意長度的輸入消息映射成固定長度的消息，而且一般情況輸 出長度均比輸入長度要短。h a s h 函數(shù)最常見的應用是數(shù)字簽名。在數(shù)字簽名體 制里，簽名算法通常只對消息的摘要進行簽名而不是原消息。h a s h 函數(shù)也用于 生成m a c ( 一般是有密鑰的h a s h 函數(shù)) 、密碼保護、零知識證明、密鑰推導算 法、模擬r a n d o mo r a c l e 等。 作為最基礎的密碼模塊，h a s h 函數(shù)的歷史并不算長，屬于密碼技術中比較 年輕的分支。最著名h a s h 函數(shù)是產生于上世紀九十年代初的m d 系列，包括 m d 4 、m d 5 和r i p e m d 等。隨后基于m d 系列，n s a 又設計了s h a 系列h a s h 函數(shù)，包括s h a 0 、s h a l 和s h a 2 。其中，m d 5 和s h a l 是在實際中應用最廣 泛的算法。另外，隨著密碼設計和分析技術的發(fā)展，又有一些新的輸出長度更長、 安全性更高的算法出現(xiàn)，如t i g e r 和w l i i f l p o o l 等。與其它密碼算法的研究類似， h a s h 函數(shù)的研究也主要有兩個方向，一個是設計原理和新算法的設計，另一個 是安全性分析。 近些年，h a s h 函數(shù)的設計技術并沒有得到很大的發(fā)展。設計主要包括壓縮 函數(shù)設計和模式構造兩部分。壓縮函數(shù)設計有直接構造和基于分組密碼構造等方 式。直接構造的算法仍是采用的m d 系列的設計思想和部分分組密碼的設計理 念，并沒有新的突破?；诜纸M密碼的構造方式由于效率的問題至今也沒有很好 的解決方案。同樣，模式構造方面最近的研究成果也不多。目前使用較多的仍是 d a m g a r d 等人提出的m d 迭代構造模式。本文針對m d 迭代模式的某些性質做 了一些探討，研究了在該模式下h a s h 函數(shù)和壓縮函數(shù)的安全性之間的關系，以 及平衡度的保持問題。通過分析證明，我們可以在保持h a s h 函數(shù)安全性的前提 下降低對壓縮函數(shù)安全性的要求，從而有利于壓縮函數(shù)的設計。 與設計方法相反，h a s h 函數(shù)的分析技術在近些年取得了巨大的進步。各種 分析方法不斷發(fā)現(xiàn)和完善，其中最突出的是差分分析方法。差分分析方法原是用 于分組密碼的攻擊方法，但對于h a s h 函數(shù)也是非常有效的。早在1 9 9 8 年，h d o b b e r t i n 就使用差分分析方法成功的找到了m d 4 算法的碰撞對。這種攻擊非常 有效，甚至可以找到有意義的碰撞對。但是，對于m d 5 和s h a 系列等算法， 由于算法本身的復雜性，差分分析不能很容易的找到碰撞對。因此，除了改善差 h a s h 函數(shù)性質與安全性研究 分分析技術本身以外，密碼分析者還提出了多種其它補充的分析方法。j o u x 等 人在對s h a 0 的分析過程中提出了近似碰撞和多塊消息連接的分析方法，并用此 方法攻破了s h a 0 算法。分析技術最大的突破是在2 0 0 4 年，王小云宣布攻破了 m d 5 算法。該攻擊采用的也是差分分析，并結合了近似碰撞和多塊消息連接攻 擊。該攻擊最有效的手段是提出了消息塊修正分析方法，此方法配合差分分析方 法可以很大地降低攻擊的復雜度。這種結合各種分析方法的攻擊對于直接設計的 h a s h 函數(shù)非常有效。王小云利用這種方法先后攻擊了m d 4 、r i p e m d 、h a v a l 和s h a 0 ，并且于2 0 0 5 年在理論上攻破了s h a - 1 算法。由于m d 5 和s h a l 等 都是實際中常用的h a s h 函數(shù)，這些攻擊成果給實際應用帶來了巨大的隱患。面 對這一狀況，我們有兩種解決辦法：一個是重新設計新的h a s h 算法，另一個是 采用某種簡單的方式將算法升級以抵抗新的攻擊方法。設計新的算法不是短時間 內可以完成的，并且將實際中的所有算法同時替換也是不現(xiàn)實的。而升級算法簡 單易行并且十分適合實際應用的需要。本文針對這一途徑進行了探討，在結合其 它改進方式的基礎上提出了新的解決方式。另外，j o u x 等人發(fā)現(xiàn)了針對m d 迭 代結構的多碰撞攻擊和前像攻擊。本文也對此進行了討論，并通過對m d 結構 稍做修改來抵抗這種攻擊。 本文的前三章包括了h a s h 函數(shù)的基本性質介紹，h a s h 函數(shù)的各種設計方 法的比較和分析。第四章是關于壓縮函數(shù)與h a s h 函數(shù)安全性質關系的一些分析 研究：第五章是h a s h 函數(shù)平衡度的分析，其中重點是壓縮函數(shù)平衡度在m d 構 造方式下的保持問題；第六章著重介紹了各種攻擊方法，并且針對這些攻擊方法 對目前的h a s h 函數(shù)結構做了改進以增強其安全性。最后總結全文，并對h a s h 函數(shù)未來的發(fā)展方向做了探討。 6 h a s h 函數(shù)性質與安全性研究 第二章h a s h 函數(shù)的基本概念 h a s h 函數(shù)是把任意長度的二進制串映射到特定長度的二進制串的函數(shù)，是 最基本的密碼學工具之一，廣泛應用于數(shù)字簽名、消息鑒別、模擬r a n d o mo r a c l e 和偽隨機發(fā)生器等領域。 1 1h a s h 函數(shù)的定義 定義1 1 ：我們稱函數(shù)h ： 0 ，1 ) + 一 0 ，1 ) “為h as h 函數(shù)，其中 0 ，1 ) + 代表任 意長度的比特串集合， 0 ，1 ) “代表長度為的n 比特的二進制串集合。其作用是 用于計算任意長度的消息的1 1 比特摘要。 事實上，構造一個可以有任意長度輸入的函數(shù)是非常困難的，因此，大部分 的h a s h 函數(shù)的設計是從某個輸入長度固定的壓縮函數(shù)入手，然后采用某種結構 將壓縮函數(shù)擴展生成輸入長度為任意值的h a s h 函數(shù)。這種擴展方式有迭代、樹 型和圖型等結構。為了方便介紹h a s h 函數(shù)的安全性要求，在這里介紹最常用的 迭代結構m e r k l e - - d a m g a r d 加強結構，簡稱為m d 方式 2 】。 m d 方式首先對消息填充，以滿足壓縮函數(shù)輸入長度的要求和保證其安全 性。填充方式是在消息末尾首先填充一比特“1 ”，然后填充足夠比特的“o ”，最 后將消息的長度填充到末尾。填充后消息長度正好為壓縮函數(shù)輸入長度的整數(shù) 倍。填充好的消息被分成固定大小的消息塊肘。，m ，初始變量設成某個固定 值，然后進行壓縮函數(shù)的迭代處理。設壓縮函數(shù)為f ，則h a s h 的處理過程總結 如下： 2 】 一填充原始消息并將消息分成固定長度的塊m ， 4 一將初始變量h 。設成固定值 設i 從1 到l ， 計算日，= f ( h h ，m ，) 一輸出h ( m ) = h ， h a s h 函數(shù)性質與安全性研究 1 2h a s h 函數(shù)的安全性質 安全性是對可能存在的攻擊而言的，因此在定義壓縮函數(shù)和h a s h 函數(shù)的安 全性之前，先介紹可能存在的攻擊方式。設h 是h a s h 函數(shù) o ，1 0 ，l y 斗 o ，1 r ， f 是壓縮函數(shù) 0 ，1 ) 0 ，1 1 ”斗 o ，1 y 。m 是任意長度的消息，m 是單塊長度消息， h 是f 的輸入或輸出中間變量。 h a s h 函數(shù)的攻擊方式： 前像攻擊：給定任意值y o ，1 ) ”，找到消息m 使得h ( m ) = y ； 二次前像攻擊：給定任意消息m ，找到消息m m 使得 h ( m ) = h ( m ) ： 碰撞攻擊：找到兩個消息m m 使得h ( m ) = ( m ) ； 壓縮函數(shù)的攻擊方式 因為壓縮函數(shù)有兩個變化的輸入變量，因此對于壓縮函數(shù)的攻擊可以分 為固定輸入中間變量和自由輸入中間變量攻擊。如果固定輸入中間變量，那 么對壓縮函數(shù)的攻擊等同于對h a s h 函數(shù)的攻擊。對于自由輸入中間變量的 攻擊，有如下攻擊方式： 自由前像攻擊：給定任意值y 0 ，1 ) ”，找到m 0 ，1 ) ”，h 0 ，1 y 使得 f ( h ，m ) = y ； 自由二次前像攻擊：給定消息m ，找到m o ，1 ) ，h 0 ，1 ) “使得r t l m 且 f ( h ，m ) = f ( h ，) ： 自由碰撞攻擊：找到兩對消息和中間變量m ，m 。 o ，1 “，h ， 0 1 1 “使 得( ，”) ( 。，r n 。) 且，( ，r n ) = 廠( ，m ) ： 半自由碰撞攻擊：找到兩個消息塊和一個中間變量 m ，m 1 o ，1 ) ，h o ，1 ) ”使得( ，m ) ( ，m ) 且廠( ，研) = f ( h ，m ) ：習 我們用對這些攻擊的抵抗性來定義h a s h 函數(shù)或壓縮函數(shù)的安全性要求。對 h a s h 函數(shù)性質與安全性研究 于某種攻擊方式，如果對h a s h 函數(shù)最好的攻擊方法是強力攻擊，那么就說該h a s h 函數(shù)是安全的。用攻擊中調用壓縮函數(shù)的次數(shù)來衡量攻擊的復雜度，定義如下： 抗碰撞性：h a s h 函數(shù)h ( 或者壓縮函數(shù)f ) 是抗碰撞的，如果最好的碰 撞攻擊的計算復雜度為2 ”。 抗前像( 二次前像) 性：h a s h 函數(shù)h ( 或者壓縮函數(shù)f ) 是抗前像( 二 次前像) 的，如果最好的前像( 二次前像) 攻擊的計算復雜度為2 ”。 抗自由碰撞性：壓縮函數(shù)是抗自由碰撞的，如果最好的自由碰撞攻擊復 雜度為2 ”。 抗自由前像( - - 次前像) 性：h a s h 函數(shù)h ( 或者壓縮函數(shù)f ) 是抗自由 前像( 二次前像) 的，如果最好的自由前像( 二次前像) 攻擊的計算復 雜度為2 ”。 抗半自由碰撞性：壓縮函數(shù)是抗半自由碰撞的，如果最好的半自由碰撞 攻擊的計算復雜度為2 “2 。 顯然，抗自由碰撞的函數(shù)一定是抗碰撞的，抗二次前像攻擊的函數(shù)定是抗 前像攻擊的。但是，抗碰撞性和抗前像性之問并不存在直接的關系。雖然對于安 全的h a s h 函數(shù)來說，前像攻擊的復雜度要高于碰撞攻擊，但是這兩種安全性不 能相互替代，也不存在嚴格遞增的關系3 1 ?？骨跋裥圆⒉荒鼙ＷC抗碰撞性，同樣 有抗碰撞性的h a s h 函數(shù)也不能保證其有抗前像性。因此，安全的h a s h 函數(shù)必 須同時滿足抗碰撞性和抗前像性。但是，通常對h a s h 函數(shù)安全性的研究更關注 抗碰撞性。這是因為相對來說單向性更容易滿足，并且前像攻擊的復雜度也更高。 1 3h a s h 函數(shù)的分類 廣義的分，h a s h 函數(shù)可以分為普通h a s h 函數(shù)和帶密鑰的h a s h 函數(shù)( m a c ) 。 普通h a s h 函數(shù)又有如下分類： 單向h a s h 函數(shù)( o n e - w a yh a s hf u n c t i o n ) ： 單向h a s h 函數(shù)是滿足如下條件的函數(shù)： a ) 函數(shù)的輸入x 可以是任意長度，輸出h ( x ) 是固定長度n 。 9 h a s h 函數(shù)性質與安全性研究 b 1 給定函數(shù)h 和輸入x ，h ( x ) 的計算應該很簡單 c ) 任意給定的h 的輸出y ，找到一個消息x 滿足 ( ) = j ，在計算上是不可行 的。任意給定x 和 ( x ) ，找到另一個消息一使得_ x ， ( _ ) = ( x ) 在計 算上也是不可行的。 抗碰撞h a s h 函數(shù)( c o l l i s i o n - - r e s i s t a n th a s hf u n c t i o n ) ： 抗碰撞h a s h 函數(shù)是滿足如下條件的函數(shù)： a 1 函數(shù)的輸入x 可以是任意長度，輸出h ( x ) 是固定長度n 。 b ) 給定函數(shù)h 和輸入x ，h ( x ) 的計算應該很簡單 c 1 滿足不可逆性和抗二次碰撞性 d 1 滿足抗碰撞性 泛單向h a s h 函數(shù)( u n i v e r s a lo n e - w a yh a s hf u n c t i o n ) 泛單向h a s h 函數(shù)是滿足如下條件的函數(shù) 幻輸入x 可以是任意長度，并且函數(shù)有一個隨機參數(shù)s ，s 是隨機選取的， 選定之后即可以公開，輸出值 k s ) 具有固定長度n 。 b ) 給定h 、s ，和輸入x ，h ( x ，s ) 的計算簡單。 c ) 在給定x 和h ( x ，s ) 之后，找到x 。使得，工x ，h ( x ，s ) = ( x ，s ) 在計算上是 不可行的。 m a c m a c 是滿足如下條件的函數(shù)： 曲輸入x 可以是任意長度，并且函數(shù)有另一個長度為k 的稱為密鑰的輸入， 輸出值h ( x ，k ) 具有固定長度n 。 b ) 給定h ，k ，和輸入x ，h ( x ，k ) 的計算簡單。 曲給定x ，在不知道k 的情況下，計算 ( x ，女) 是不可行的。即使在得到很 多消息和驗證碼對的情況下，確定k 或者計算一個新消息的m a c 值也 是不可行的。 h a s h 函數(shù)性質與安全性研究 1 4輸出長度的要求 設某個h a s h 函數(shù)的輸出空間為n 比特的字符串，即r - - - - f o ，1 ) “。如果該函數(shù) 可以滿足以下條件就稱該函數(shù)是完全安全的： 尋找前像或者二次前像的復雜度為2 ” 尋找碰撞的復雜度為2 2 由生日攻擊的性質知道，前像生只攻擊的復雜度為o ( 2 ”) ，碰撞生日攻擊 復雜度為o ( 2 “2 ) 。顯然，定義中的復雜度等于生日攻擊的復雜度，也就是說 對完全安全的h a s h 函數(shù)最有效的攻擊是生日攻擊。 對于具有完全安全性的h a s h 函數(shù)來說，現(xiàn)在的問題是輸出長度n 至少取何 值才能使生日攻擊是在實際中是不可行的。1 9 9 5 年，n = 1 2 8 被認為是足夠安全 的長度，所以m d 5 算法的輸出長度為1 2 8 位。但是隨著計算技術的發(fā)展，1 2 8 位已經不夠安全。最新的研究認為2 8 0 是較為安全的界限，所以h a s h 函數(shù)的輸 出應該至少應該大于等于1 6 0 位。單向函數(shù)的輸出長度應該大于等于8 0 位。如 果考慮到較為長期的安全性，h a s h 函數(shù)應該選擇更大的輸出長度，如1 9 2 位， 2 5 6 位和5 1 2 位等。目前最新的算法如t i g e r 和w h i r l p o o l 等的輸出長度都是5 1 2 位：至于單向函數(shù)，由于攻擊者可以同時搜尋大量不同的值的前像，所以其長度 更應該取較大的值。 i 5幾種常見h a s h 函數(shù)介紹 目前實際應用中比較常見的h a s h 算法是m d 5 、s h a l 和s h a 2 系列等算法， 另外一些新設計的算法有t i g e r 和w h i d p o o l 等。這里簡要的介紹一下m d 5 和 s h a l 算法的內部結構。 m d 5 和s h a l 都是采用的m d 迭代式構造方式，這里省略了消息的填充 和分塊部分，只介紹他們的壓縮函數(shù)的內部構造。 1 5 1 m d 5 m d 5 的輸出長度為1 2 8 位，消息的分組長度為5 1 2 比特。5 1 2 比特首先被 分成1 6 個3 2 比特的字。壓縮函數(shù)有四輪，每輪有1 6 步操作。連續(xù)的四步操作 h a s h 函數(shù)性質與安全性研究 有如f 形式： 盤= b + ( ( a + ，( 6 ，c ，d ) + w i + t i ) ) s i ) ， d = a + ( ( d + 州( 口，b ，c ) + + l + f 州) s 川) ， c = d + ( ( c + f + 2 ( d ，a ，b ) + w i + 2 + t “2 ) s i + 2 ) ， b = c + ( ( 6 + 固f + 3 ( 6 ，d ，a ) + w i + 3 + t f + 3 ) s i + 3 ) 其中，a 、b 、c 和d 是四個中間變量寄存器，初始值為m d 5 的初始向量。 t 州，s i + j ( ，= 0 , 1 ，2 ，3 ) 是與步數(shù)相關的常量，w i + ，是該步的消息字， s 。是循環(huán) h i u , s 。位，“+ ”是模3 2 加。消息字的順序和常量的取值這里不祥述。 每一輪都選取了不同的非線性輪函數(shù)，如下所示： 中，( ，y ，z ) = ( x a y ) v ( a z ) ，0 i 1 5 ， ，( x ，y ，z ) = ( x a z ) v ( y a _ 1 z ) ，1 6 f 3 1 ， ( x ，y ，z ) = x o y o z ，3 2 i 4 7 ， ( z ，y ，z ) = y o ( x m - 1 z ) ，4 8 f 6 3 ， 其中，x ，y 和z 都是3 2 比特的字5 1 。 1 5 2 s h a 1 s h a 1 的輸出長度為1 6 0 比特，消息塊長度為5 1 2 比特。s h a 1 的輪函數(shù) 與m d 5 類似，不同之處在于消息字處理順序的編排過程。m d 5 只是在每一輪中 對消息字的順序做簡單變換，而s h a 1 采用線性函數(shù)生成后續(xù)消息字，其生成 函數(shù)如下所示吼 m ，= ( m f 3 0 m f 一8 0 m f 一1 4 0 m f 1 6 ) 1 ，i = 1 6 ，一，7 9 ： 擴展后的消息經過四輪處理，每輪為2 0 步，算法描述為： h a s h 函數(shù)性質與安全性研究 f o ri = 1 ，2 ，8 0 ，礦= 。，b o ，c o ，d 。，) 為初始變量a 其中每一輪的非線性函數(shù)如下表所示： m ，( x ，】廠，z ) = ( z y ) v ( o z ) ，0 f 1 9 ， m 。( 工，y ，z ) = x o y o z ，2 0 f 3 9 ， m ，( ，y ，z ) = ( y ) v ( x z ) v ( y z ) ，4 0 i s5 9 ， 由，( x ，y ，z ) = x o y o z ，6 0 s i 7 9 這兩種算法都是基于非線性函數(shù)多輪處理的結構。這種結構因過于簡單因而 對差分攻擊的抵抗力非常弱，在第六章將具體介紹對它們的差分攻擊。 ，盯+ 0 一+ q + 卜 dc+ 6 ， +5 0 ( 3 l 的情況，隨后來看m t = 1 的 情況。 對于給定的任意長度輸入x ，h 的計算過程為： 將x 分成長度為m t 一1 大小的塊。如果最后一塊長度不足，那么在其后面 補充足夠的0 。設d 是需要補充的0 的個數(shù)。用x i ，x ：，z 州。+ 。) 來表示消息塊， 其中n = l x l 。在這些消息塊之后附加一個新塊x 。+ ，。這個新的消息塊是d 的 二進制表示。 按如下方式定義t 比特長度的h 0h 。： h = f ( o ”1 | | x i ) h 。= f ( h 川1 1 | h 。) 最后，令a ( x ) = h m 。 下面來證明h 的抗碰撞性。設i ，x i ( r e s p h ，一，) 是計算矗( x ) ， ( 一) 過程中的中 間變量。如果1x i * 1 一im o d ( m f ) 那么顯然有z 帥。- i ) “一州。廿1 ，因此 h ( x ) = h ) 意味著找到了f 的一個碰撞。假設lx w l m o d ( m t ) ，不失一般性， 假設l x l l z l 。 考慮下面等式 ( 曲= f ( h 忡。) | lx n l ( m - i - i ) + 1 ) = f ( h 圳。 1 1 一伽+ 1 ) + ) = h ( x ) ， 如果 州m _ ，) i l x n ( m - t - 1 ) + 1 ) h 。) 1 1 一州+ hj + j ，那么就得到了f 的碰撞對。否則， 可以考慮下面的等式f ( h m 。) 1 1x n l m - t - 1 ) + 1 ) = f ( h 。w 卅_ f ) i l f 帥。i 。) 并依次往前類 推。顯然，這個過程停止的情況要么是找到f 的一個碰撞，要么有下面等式成立 0 “1i l 而= h 川1 | 1x 顯然這個等式是不可能成立的。 在證明過程中，將對h a s h 函數(shù)的碰撞攻擊歸約為對壓縮函數(shù)的碰撞攻擊， 規(guī)約的復雜度變換是多項式級別的。由此證明，抗碰撞的壓縮函數(shù)在這種迭代構 造方式下是能夠構造任意輸入長度的抗碰撞的h a s h 函數(shù)的。 最后來討論m t = 1 的情況。如果f 滿足抗前像攻擊，那么可以如下構造h 。 h a s h 函數(shù)性質與安全性研究 首先選取t 比特長度的乩，按如下方式定義h ： h = f o 。l l ，) h + i = f ( h ，l ix ) 證明方法與前一種情況類似，h 的碰撞要么產生一個f 的碰撞，要么會生成j 的一個前像。而前面定義f 是抗前像攻擊的。 證明完畢 3 1 2m d 并行迭代模式 線性迭代模式雖然具有可證明安全，但是這種結構不能夠并行，效率比較低。 在定理3 1 的基礎上，下面來構造可并行的迭代方式。這種方式其實是一種樹型 結構。我們在定理3 2 中描述了并行構造方式并證明了其安全性。 定理3 2 設f 是一個將長度m 比特串映射到長度為t ( m ) 比特串的抗碰撞的函數(shù) 族，那么存在一個抗碰撞的h a s h 函數(shù)族h 可以將任意長度的串映射到t ( m 1 長度 的串。并且h 滿足如下性質： 設h 是h 的一個實例，那么對于長度為n 比特的消息串在n 2 t 個處理器的 情況下可以在o ( 1 0 9 2 0 t ) t m f ) 步內完成壓縮過程。 證明：設，f 是一個f 的一個實例。由定理3 1 ，構造h a s h 函數(shù)h ， 在t ( m t ) 步內將2 t 比特映射到t 比特。注意，既然現(xiàn)在輸入的長度已經是確定的了，那么 就沒有必要在h 的后面添加長度塊了。 按如下方式構造h h ： 設消息x 的長度為n 。用0 來填充x 使得x 的長度等于2 j t ，i 是某個整數(shù)。 現(xiàn)在構造序列五，x 2 ，j ，其中x 。由一來定義：將_ 分割成長度為2 t 的塊，使 用 來計算每一塊并把結果連接作為x 。 當x j 的長度等于t 時，停止計算。然后將x 的長度n 的二進制串使用定理 3 1 得到一個t 比特的塊如 。最終有 6 h a s h 函數(shù)性質與安全性研究 h ( x ) = ( x 川l e n ，) 。 對于這種并行方式的抗碰撞性的證明與前一定理證明類似。如果找到h 的碰撞 對，我們有：如果一，1 i l e n ，x 川腳，那么就得到h 。的碰撞，這與定理3 1 矛 盾。因此，假設n = n 。現(xiàn)在，x x t 意味著可以找到i 使得x i x 。，但是x 。x 。 顯然，這是h 1 的一個碰撞。 m d 構造方式是目前應用最多的模式，各種常用的h a s h 函數(shù)都采用了m d 方式。但是，m d 方式并不是完美的。第七章將會介紹對m d 方式的攻擊方法。 3 1 3 可擴展h a s h 構造方式 首先介紹可擴展性的概念?？蓴U展性是指這樣一種性質，在函數(shù)作用于一個 特定的消息之后，當消息被修改時可以很容易得到新消息的h a s h 值，而不需要 重新進行計算。具體來講，設對消息m 做了h a s h ，且其h a s h 值為x 。具有可擴 展性的h a s h 函數(shù)h 的修改函數(shù)f 可以以比直接重新計算m 更短的時間內得到 更新的h a s h 值一。更新所需要的時間與消息的長度無關，而只與修改的消息長 度有關嘲。 可擴展的構造方式適用于對經常做改動或者只有少量差異的消息集合做 h a s h 的情況。比如，要對硬盤上的文件系統(tǒng)做h a s h ，當某個文件被改動時，我 們并不希望重新對整個硬盤做h a s h 來得到新的h a s h 值。如果h a s h 函數(shù)具有可 擴展性，那么就可以做一個很簡單的更新操作來得到新的h a s h 值。 顯然，m d 線性迭代方式因為迭代的原因不可能具有可擴展性。對于并行的 樹型方式，如果要具有可擴展性就必須保留全部的中間變量并且計算并不簡單。 b e l l a r e 等人對此問題做了研究，并給出了一個可擴展h a s h 函數(shù)的構造方案。下 面來看具體的方案： 本方案上層的結構非常簡單。設x 是一個消息塊序列，x = 一，心，x 一其 中每個消息塊的長度為b 比特，其中b 是任意選取的一個參數(shù)。首先，使用函數(shù) h 來處理每一塊工，并得到輸出y ，。( 特別的，y ，= ( l i x ，) ) ，其中i 是塊索引 的二進制表示) 。隨后，這些輸出以某種方式混和來生成最終的h a s h 值 y = y l 固y 2o o n ，其中。表示混和運算。 h a s h 函數(shù)性質與安全性研究 這里，稱h 為隨機變換函數(shù)。實際中，h 可以從某些標準h a s h 函數(shù)如s h a 1 等導出的，將其看成完全安全的h a s h 函數(shù)或者隨機函數(shù)。混和函數(shù)。是一個典 型的群操作，意味著將y 。y ：y ?？醋鼋粨Q群g 的的元素，且該群的運算為 。 這個方案稱為隨機一混和方案。其結構如下圖所示： 圖3 1 簡單的表達式為： h a s h h 2 b 來對構造方式進行分類。這樣分類的原因是大多數(shù)的 分組密碼的分組只有6 4 位或1 2 8 位，新的如a e s 則有1 2 8 位，這個長度對于 h a s h 函數(shù)來說是遠遠不夠的，為了抗碰撞一般至少要兩倍的分組長度。 3 2 1 1單倍長度構造 單倍長度構造的h a s h 函數(shù)其輸出長度等于分組密碼的分組長度也就是說 h a s h 函數(shù)的輸出長度n = b 。這種構造方式是將壓縮函數(shù)的輸入做線性變換作為 分組密碼的輸入，并通過不同的組合來得到多種構造方式。 設壓縮函數(shù)為f ，輸入變量為h - _ i ，消息塊為x i ，輸出為h j ，則有 2 0 h a s h 函數(shù)性質與安全性研究 h i = ( x ，h h ) 。 設分組密碼的輸入變量為明文p 和密鑰k ：這兩個變量可以從以下四個值中 取值：( x ，h 。，x jo 日。，礦) ( v 是常數(shù)) 。另外，可以修改分組密碼的結構， 加入一個新變量前像反饋f f 與原輸出做異或運算，這樣就可以得到4 3 = 6 4 種不 同的方案。其結構如圖所示：