3.2 Hash函數

Hash函數，也稱為散列函數、哈希函數、雜湊函數，是現代密碼學中另外一類重要的函數，它能夠將任意長的字符串M映射成一個較短的定長字符串L，這一特性使其在數字簽名和消息的完整性校驗等方面有著重要的應用。Hash函數主要分為兩類：一類是有密鑰控制的Hash函數，即基于Hash函數的消息認證碼；另一類是不帶有密鑰的Hash函數，用于產生消息摘要。

本節將介紹Hash函數的基本概念、基本用法、安全性以及常見的Hash函數，包括MD4和MD5算法以及SHA系列的安全Hash算法。

3.2.1 Hash函數的概念

1. Hash函數的基本概念

Hash函數的輸入長度是可變的，返回一個固定長度串，這個串被稱為輸入信息的Hash值，也稱為消息摘要。計算給定輸入內容的Hash值是簡單的，但給定某個Hash值，求其輸入內容是比較困難的，即Hash函數是單向函數。Hash函數H一般滿足下列性質。

1）函數H是公開的，其輸入內容可為任意長度。

2）函數H的輸出長度固定。

3）不同的輸入內容不能產生相同的函數值（即無碰撞性）。

4）無法根據函數值推導出輸入的內容。

Hash值的長度由具體的Hash函數確定，例如MD4算法的輸出為128位，SHA-1的輸出為160位。

2. Hash函數的通用結構

圖3-2展示了Hash函數的一種通用結構，目前包括MD5、SHA-1等被廣泛使用的Hash函數都采用這種結構。

在圖3-2中，Hash函數的具體工作過程如下。

1）先把原始消息M分成L個固定長度為b的分組M_i（1≤i≤L），如果最后一個分組長度不夠，需要將它填充成長度b。

2）將CV₀的初始值設定為IV。

3）重復使用壓縮函數f，每次按次序將原始消息的分組M_i與上一級壓縮函數的輸出值CV_i-1作為輸入，并產生一個固定長度為n的輸出，即CV_i=f（CV_i-1，M_i-1），其中1≤i≤L。

4）最后一個輸出值CV_i作為Hash值，即H（M）=CV_L。

3. Hash函數的基本用法

Hash函數與對稱加密算法、公鑰加密算法以及數字簽名算法結合使用，可以實現有效的保密與認證等安全功能。圖3-3展示了Hash函數的6種應用方法。

圖3-3a可以實現保密性和認證，發送方A將消息M與其Hash值H（M）連接，用對稱密碼算法加密后發送至接收方B。接收方用與發送方共享的密鑰K對密文解密后得到M′和H（M），而后計算M′的Hash值H（M′），通過比較H（M）和H（M′）來完成對消息M的認證。

圖3-3b只提供了認證，未對消息M進行保密，只對消息的Hash值進行了加解密變換。

在圖3-3c中，發送方A采用公鑰密碼算法，用A自己的私鑰PR_a對消息M的Hash值進行簽名得到E（PR_a，H（M）），而后與M連接后發出，接收方B用A的公鑰PU_a對E（PR_a，H（M））進行解密得到H（M），再與B自己由接收消息M′計算得到的H（M′）進行比較來實現認證。該方案提供了認證和數字簽名，稱作簽名—哈希方案。這個方案用對消息M的Hash值簽名來代替對任意長消息M本身的簽名，大大提高了簽名速度和有效性。

在圖3-3d中，發送方A發送給接收方B的信息是E（K，[M || E（PR_a，H（M））]），是在圖3-3c的方案基礎上增加了對稱密鑰加密保護，可提供認證、數字簽名和保密性。

圖3-3e是在哈希運算H中增加了通信雙方共享的秘密值S，加大了對手攻擊的困難性。但是，它僅僅提供了認證。

圖3-3f是在圖3-3e的方案基礎上增加了對稱密鑰加密保護，可以提供保密性和認證。

4.針對Hash函數的攻擊方法

Hash函數的安全性在于良好的單向性以及對碰撞的有效避免，通過Hash值來求得原消息是非常困難的，尋找兩組消息使其Hash值相同也是非常困難的。對于Hash函數的攻擊，其主要目標是用相同Hash值的非法消息來代替合法消息，以此來偽造信息。

目前，對Hash函數較有效的攻擊方法是生日攻擊和中途相遇攻擊，這兩種方法對Hash值為128位的Hash函數在理論上是有效的，但是當Hash值超過160位時，在計算上就是不可行的，所以目前使用Hash值大于160位以上的Hash函數是較為安全的。下面將介紹這兩種針對Hash函數的攻擊方法。

（1）生日攻擊

生日攻擊是指為了尋找到能夠發生碰撞的消息而在消息空間中進行搜索的一種攻擊方式。它適用于任何Hash函數，并被作為衡量一個Hash函數安全與否的重要參考。它來源于概率論上著名的生日悖論問題，即在一個教室中至少需要有多少個學生才能保證有兩個學生的生日相同的概率不小于1/2。若從某些人中指定一個人，則他與其他人的生日相同的概率為1/365，但是如果不指定某個日期，從這些人里面找到生日相同的人，成功的概率就大得多。

將生日問題推廣到消息的集合中，就可以得到在生日攻擊的成功概率盡量低的情況下所需的Hash值長度。按照現在的計算條件，要想使一個Hash函數比較安全，其輸出的Hash值長度不應小于128位。

（2）中間相遇攻擊

中間相遇攻擊的思路與生日攻擊類似，但這種攻擊只適合于具有分組鏈接結構的Hash函數。這種攻擊也是通過不斷地搜索和計算，在消息集合中尋找能夠產生碰撞的消息。在進行中間相遇攻擊時，攻擊者首先隨意選出若干個消息分組，將它們分為兩部分。然后對其中的第一部分從初值開始進行迭代，到中間的某一步結束，得到I個輸出；第二部分從Hash值（任意選定）開始用逆函數進行反向迭代，也是到中間的某一步結束，得到J個輸出。最后，對這兩部分的輸出進行比較，如果能得到相同的輸出值，就可以得到一對碰撞消息。

類似于生日攻擊，可以通過計算得到為了獲得對應的碰撞消息概率所需的消息數I+J的大小。通過研究發現，為了能夠抵抗選擇明/密文攻擊，需要分組加密函數的分組長度不小于128位，同時函數還需要具有偽隨機置換的性質。

目前常用的Hash算法有：MD4、MD5、SHA-1和SHA-2。這些算法的優點是運算速度要比對稱密碼算法快。下面將逐一介紹MD4、MD5和SHA-1算法。

3.2.2 MD4和MD5算法

美國麻省理工學院教授Ronald Rivest分別于1990年和1991年設計出了MD4和MD5兩種信息摘要算法。MD5是在MD4的基礎上發展而來的，雖然比MD4稍微晚一些，但更加安全。下面對這兩種算法做詳細介紹。

1.算法簡介

MD4算法是一種用來測試信息完整性的Hash算法。它是通過32位操作數的位操作來實現的，所以適用在32位的處理器上并用高速軟件進行實現。它的安全性并不是基于大數分解這樣的數學難題，有人很快就用分析和差分的方法成功攻擊了MD4算法三輪變換中的兩輪，證明了它并不像期望的那樣安全。于是，Rivest對MD4算法進行了改進，從而發明了MD5算法。

MD5算法是MD4的改進版本。消息在初始化處理之后，需要對附加位進行填充。消息首先被拆成若干個512位的分組，其中最后一個分組是“消息尾部+1和0組成的填充字節+64位消息長度”，以確保不同長度的消息在填充后不相同。之后，MD5將每一個512位分組又劃分為16個32位子分組。

接下來，每個512位消息分組就以16個32位字的形式進入算法的主循環，512位消息分組的個數決定了循環的次數。圖3-4所示，MD5的主循環有4輪，每輪進行16次操作，每一輪的操作過程相似。每次操作對a、b、c、d中的3個做一次非線性函數運算，并將所得結果加上第4個變量、一個子分組和一個常數。再將所得結果向右循環移動一位，并加上a、b、c、d中的一個。最后，用該結果取代a、b、c、d中的一個。MD5算法的輸出由4個32位分組組成，將它們級聯形成一個128位的Hash值。

64位的消息長度限制導致了MD5的安全輸入長度必須小于2⁶⁴位，因為大于64位長度的信息會被忽略。4個32位寄存器字a、b、c、d被稱為鏈接變量，將始終參與運算并形成最終的Hash結果。

2. MD5算法的安全性

對于任何一個Hash函數來說，碰撞都是不可避免的，從一個規模較大的集合映射到一個規模較小的集合，必然會出現相同的情況。所以，對Hash函數而言，應該具有的特性是碰撞阻力，即實踐過程中難以發生，而并非避免碰撞。

Rivest猜想對于128位的Hash值來說，MD5的強度已經達到了最大。理論上，要執行2⁶⁴次運算才能找出具有相同Hash值的兩個消息，現在需要執行2¹²⁸次運算才能找到某個固定散列值的原消息。然而，2004年山東大學的王小云等人成功地找出了MD5算法的碰撞。發生碰撞的消息是由兩個1024位長的串M、N構成，用M_i‖N_i表示M‖N的碰撞。在IBM P690上找到M和M_i的時間大約為1h，找到M和M_i之后，則只需15s至5min就可以找出N和N_i。

3.2.3 安全Hash算法

1.安全Hash算法（SHA）的發展過程

1993年，美國國家標準與技術研究院（NIST）公布了安全散列算法SHA-0。1995年，NIST又公布了改進后的版本SHA-1，其設計上模仿了MD5算法，接受任意長度的輸入消息，但生成的是160位的消息摘要，抗窮舉搜索的能力更強。2001年，NIST公布SHA-2作為聯邦信息處理標準，包含SHA-224、SHA-256、SHA-384、SHA-512等6個算法，分別生成224位、256位、384位和512位的Hash值。2008年，NIST啟動了安全Hash函數SHA-3的評選。2012年10月，Guido Bertoni、Joan Daemen、Michael Peeters和Gilles Van Assche設計的密碼學函數族Keccsk被選中，被公布為新的Hash函數標準。

接下來對SHA-1算法做簡單介紹。

2. SHA-1算法

SHA-1算法首先將消息填充為512位的整數倍。填充方法與MD5完全一樣：先添加一個1，然后填充盡量多的0使其長度為512的倍數剛好減去64位，最后64位表示消息填充前的長度。

SHA-1算法有5個32位變量（而MD5僅有4個），先對它們進行初始化：h₀ =0x67452301、h₁=0xEFCDAB89、h₂=0x98BADCFE、h₃=0x10325476、h₄=0xC3D2E1F0。完成初始化之后，將這5個變量復制到另外的變量中：h₀到a，h₁到b，h₂到c，h₃到d，h₄到e。

然后開始算法的主循環部分。它一次可以處理512位消息，循環的次數是消息中512位分組的數目。主循環有4輪，每輪有20次操作（MD5有4輪，每輪有16次操作）。圖3-5所示，每次操作選取a、b、c、d、e中的3個數進行一次非線性運算，然后進行與MD5中類似的移位和加運算。

在這之后，a、b、c、d、e分別加上h₀、h₁、h₂、h₃、h₄ ，然后讓下一個消息分組繼續運行算法。最后，SHA-1算法的輸出結果由h₀、h₁、h₂、h₃和h₄級聯而成。

3.針對SHA系列算法的攻擊進展

1997年，王小云首次使用“比特追蹤法”分析SHA-0算法，并在理論上攻破了SHA-0算法。隨后，在2004年CRYPTO的Rump會議上，王小云、馮登國、來學嘉和于紅波宣布了攻擊MD5、SHA-0和其他Hash函數的初步結果。2005年2月，王小云和殷益群、于紅波等人發表了攻破SHA-0的算法，只需要2³⁹次計算就能找到碰撞，對SHA-1的攻擊只需要2⁶⁹次計算就能找到一組碰撞。之后，在2005年8月的CRYPTO會議接近尾聲時，王小云、姚期智、姚儲楓再次發表了攻破SHA-1的算法，可以通過2⁶³次計算找到碰撞。

目前，針對SHA-2的攻擊算法也已經出現，這里不做詳細介紹，有興趣的讀者可查閱相關資料。