-
SHA家族
鎖定
- 中文名
- SHA家族
- 外文名
- Secure Hash Algorithm
- 別 名
- 安全散列算法
- 國 家
- 美國
SHA家族家族成員
SHA家族的五個算法,分別是SHA-1、SHA-224、SHA-256、SHA-384,和SHA-512,由美國國家安全局(NSA)所設計,並由美國國家標準與技術研究院(NIST)發佈;是美國的政府標準。後四者有時並稱為SHA-2。SHA-1在許多安全協定中廣為使用,包括TLS和SSL、PGP、SSH、S/MIME和IPsec,曾被視為是MD5(更早之前被廣為使用的雜湊函數)的後繼者。但SHA-1的安全性如今被密碼學家嚴重質疑;雖然至今尚未出現對SHA-2有效的攻擊,它的算法跟SHA-1基本上仍然相似;因此有些人開始發展其他替代的雜湊算法。
[1]
SHA家族SHA-0和1
最初載明的算法於1993年發佈,稱做安全雜湊標準(Secure Hash Standard),FIPS PUB 180。這個版本常被稱為SHA-0。它在發佈之後很快就被NSA撤回,並且由1995年發佈的修訂版本FIPS PUB 180-1(通常稱為SHA-1)取代。SHA-1和SHA-0的算法只在壓縮函數的訊息轉換部分差了一個位元的循環位移。根據NSA的説法,它修正了一個在原始算法中會降低雜湊安全性的弱點。然而NSA並沒有提供任何進一步的解釋或證明該弱點已被修正。而後SHA-0和SHA-1的弱點相繼被攻破,SHA-1似乎是顯得比SHA-0有抵抗性,這多少證實了NSA當初修正算法以增進安全性的聲明。
SHA家族SHA-0破解
在CRYPTO 98上,兩位法國研究者提出一種對SHA-0的攻擊方式:在261的計算複雜度之內,就可以發現一次碰撞(即兩個不同的訊息對應到相同的訊息摘要);這個數字小於生日攻擊法所需的2的80次方,也就是説,存在一種算法,使其安全性不到一個理想的雜湊函數抵抗攻擊所應具備的計算複雜度。
2004年時,Biham和 Chen也發現了SHA-0的近似碰撞,也就是兩個訊息可以雜湊出幾乎相同的數值;其中162位元中有142位元相同。他們也發現了SHA-0的完整碰撞(相對於近似碰撞),將本來需要80次方的複雜度降低到62次方。
2004年8月12日,Joux, Carribault, Lemuet和Jalby宣佈找到SHA-0算法的完整碰撞的方法,這是歸納Chabaud和Joux的攻擊所完成的結果。發現一個完整碰撞只需要251的計算複雜度。他們使用的是一台有256顆Itanium2處理器的超級電腦,約耗80,000 CPU工時。
2004年8月17日,在CRYPTO 2004的Rump會議上,王小云,馮登國、來學嘉,和於紅波宣佈了攻擊MD5、SHA-0 和其他雜湊函數的初步結果。他們攻擊SHA-0的計算複雜度是2的40次方,這意味着他們的攻擊成果比Joux還有其他人所做的更好。請參見MD5 安全性。2005年二月,王小云和殷益羣、於紅波再度發表了對SHA-0破密的算法,可在2的39次方的計算複雜度內就找到碰撞。
SHA家族SHA-1破解
鑑於SHA-0的破密成果,專家們建議那些計劃利用SHA-1實作密碼系統的人們也應重新考慮。在2004年CRYPTO會議結果公佈之後,NIST即宣佈他們將逐漸減少使用SHA-1,改以SHA-2取而代之。
2005年,Rijmen和Oswald發表了對SHA-1較弱版本(53次的加密循環而非80次)的攻擊:在2的80次方的計算複雜度之內找到碰撞。
2005年二月,王小云、殷益羣及於紅波發表了對完整版SHA-1的攻擊,只需少於2的69次方的計算複雜度,就能找到一組碰撞。(利用生日攻擊法找到碰撞需要2的80次方的計算複雜度。)
這篇論文的作者們寫道;“我們的破密分析是以對付SHA-0的差分攻擊、近似碰撞、多區塊碰撞技術、以及從MD5算法中尋找碰撞的訊息更改技術為基礎。沒有這些強力的分析工具,SHA-1就無法破解。”此外,作者還展示了一次對58次加密循環SHA-1的破密,在2的33次方個單位操作內就找到一組碰撞。完整攻擊方法的論文發表在2005年八月的CRYPTO會議中。
殷益羣在一次面談中如此陳述:“大致上來説,我們找到了兩個弱點:其一是前置處理不夠複雜;其二是前20個循環中的某些數學運算會造成不可預期的安全性問題。”
2006年的CRYPTO會議上,Christian Rechberger和Christophe De Cannière宣佈他們能在容許攻擊者決定部分原訊息的條件之下,找到SHA-1的一個碰撞。
在密碼學的學術理論中,任何攻擊方式,其計算複雜度若少於暴力搜尋法所需要的計算複雜度,就能被視為針對該密碼系統的一種破密法;但這並不表示該破密法已經可以進入實際應用的階段。
就應用層面的考量而言,一種新的破密法出現,暗示着將來可能會出現更有效率、足以實用的改良版本。雖然這些實用的破密法版本根本還沒誕生,但確有必要發展更強的雜湊算法來取代舊的算法。在“碰撞”攻擊法之外,另有一種反譯攻擊法(Pre-image attack),就是由雜湊出的字串反推原本的訊息;反譯攻擊的嚴重性更在碰撞攻擊之上,但也更困難。在許多會應用到密碼雜湊的情境(如用户密碼的存放、文件的數位簽章等)中,碰撞攻擊的影響並不是很大。舉例來説,一個攻擊者可能不會只想要偽造一份一模一樣的文件,而會想改造原來的文件,再附上合法的簽章,來愚弄持有私密金鑰的驗證者。另一方面,如果可以從密文中反推未加密前的使用者密碼,攻擊者就能利用得到的密碼登入其他使用者的帳户,而這種事在密碼系統中是不能被允許的。但若存在反譯攻擊,只要能得到指定使用者密碼雜湊過後的字串(通常存在影檔中,而且可能不會透露原密碼資訊),就有可能得到該使用者的密碼。
[1]
SHA家族SHA-1算法
以下是 SHA-1 算法的偽代碼:
Initialize variables: h0 := 0x67452301 h1 := 0xEFCDAB89 h2 := 0x98BADCFE h3 := 0x10325476 h4 := 0xC3D2E1F0 Pre-processing: append the bit '1' to the message append k bits '0', where k is the minimum number >= 0 such that the resulting message length (in bits) is congruent to 448 (mod 512) append length of message (before pre-processing), in bits, as 64-bit big-endian integer Process the message in successive 512-bit chunks: break message into 512-bit chunks for each chunk break chunk into sixteen 32-bit big-endian words w[i], 0 ≤ i ≤ 15 Extend the sixteen 32-bit words into eighty 32-bit words: for i from 16 to 79 w[i] := (w[i-3] xor w[i-8] xor w[i-14] xor w[i-16]) leftrotate 1 Initialize hash value for this chunk: a := h0 b := h1 c := h2 d := h3 e := h4 Main loop: for i from 0 to 79 if 0 ≤ i ≤ 19 then f := (b and c) or ((not b) and d) k := 0x5A827999 else if 20 ≤ i ≤ 39 f := b xor c xor d k := 0x6ED9EBA1 else if 40 ≤ i ≤ 59 f := (b and c) or (b and d) or (c and d) k := 0x8F1BBCDC else if 60 ≤ i ≤ 79 f := b xor c xor d k := 0xCA62C1D6 temp := (a leftrotate 5) + f + e + k + w[i] e := d d := c c := b leftrotate 30 b := a a := temp Add this chunk's hash to result so far: h0 := h0 + a h1 := h1 + b h2 := h2 + c h3 := h3 + d h4 := h4 + e Produce the final hash value (big-endian): digest = hash = h0 append h1 append h2 append h3 append h4
SHA家族SHA-2
NIST發佈了三個額外的SHA變體,這三個函數都將訊息對應到更長的訊息摘要。以它們的摘要長度(以位元計算)加在原名後面來命名:SHA-256,SHA-384和SHA-512。它們發佈於2001年的FIPS PUB 180-2草稿中,隨即通過審查和評論。包含SHA-1的FIPS PUB 180-2,於2002年以官方標準發佈。2004年2月,發佈了一次FIPS PUB 180-2的變更通知,加入了一個額外的變種SHA-224",這是為了符合雙金鑰3DES所需的金鑰長度而定義。
SHA-256和SHA-512是很新的雜湊函數,前者以定義一個word為32位元,後者則定義一個word為64位元。它們分別使用了不同的偏移量,或用不同的常數,然而,實際上二者結構是相同的,只在循環執行的次數上有所差異。SHA-224以及SHA-384則是前述二種雜湊函數的截短版,利用不同的初始值做計算。
這些新的雜湊函數並沒有接受像SHA-1一樣的公眾密碼社羣做詳細的檢驗,所以它們的密碼安全性還不被大家廣泛的信任。Gilbert和Handschuh在2003年曾對這些新變種作過一些研究,聲稱他們沒有找到弱點。
[2]
SHA家族應用
SHA-1, SHA-224, SHA-256, SHA-384 和 SHA-512 都被需要安全雜湊算法的美國聯邦政府所應用,他們也使用其他的密碼算法和協定來保護敏感的未保密資料。FIPS PUB 180-1也鼓勵私人或商業組織使用 SHA-1 加密。Fritz-chip 將很可能使用 SHA-1 雜湊函數來實現個人電腦上的數位版權管理。
首先推動安全雜湊算法出版的是已合併的數位簽章標準。
SHA家族參見
- 編碼
- 密碼學
- 加密技術
- 算法
- 參考資料
-
- 1. Eli Biham, Rafi Chen, Near-Collisions of SHA-0, Cryptology ePrint Archive, Report 2004/146, 2004
- 2. Florent Chabaud, Antoine Joux: Differential Collisions in SHA-0. CRYPTO 1998. pp. 56–71.
- 3. Henri Gilbert, Helena Handschuh: Security Analysis of SHA-256 and Sisters. Selected Areas in Cryptography 2003: pp. 175–193.