国外杀人网站:SHA家族

来源:百度文库 编辑:音乐简谱网 时间:2019/09/16 23:22:31
维基百科,自由的百科全书汉漢▼▲

安全散列演算法Secure Hash Algorithm)能計算出一個數位訊息所對應到的,長度固定的字串(又稱訊息摘要)。且若輸入的訊息不同,它們對應到不同字串的機率很高;而SHA是FIPS所認證的五種安全雜湊演算法。這些演算法之所以稱作「安全」是基於以下兩點(根據官方標準的描述):「1)由訊息摘要反推原輸入訊息,從計算理論上來說是很困難的。2)想要找到兩組不同的訊息對應到相同的訊息摘要,從計算理論上來說也是很困難的。任何對輸入訊息的變動,都有很高的機率導致其產生的訊息摘要迥異。」

SHA家族的五個演算法,分別是SHA-1、SHA-224、SHA-256、SHA-384,和SHA-512,由美國國家安全局(NSA)所設計,並由美國國家標準與技術研究院(NIST)發佈;是美國的政府標準。後四者有時並稱為SHA-2。SHA-1在許多安全協定中廣為使用,包括TLSSSLPGPSSHS/MIMEIPsec,曾被視為是MD5(更早之前被廣為使用的雜湊函數)的後繼者。但SHA-1的安全性如今被密碼學家嚴重質疑;雖然至今尚未出現對SHA-2有效的攻擊,它的演算法跟SHA-1基本上仍然相似;因此有些人開始發展其他替代的雜湊演算法。緣於最近對SHA-1的種種攻擊發表,「美國國家標準與技術研究院(NIST)開始設法經由公開競爭管道(類似高級加密標準AES的發展經過),發展一個或多個新的雜湊演算法。」

目录

[隐藏]
  • 1 SHA-0和SHA-1
    • 1.1 SHA-0的破解
    • 1.2 SHA-1的破解
  • 2 SHA-2
  • 3 SHA 所定義的長度
  • 4 SHAd
  • 5 應用
  • 6 SHA-1 演算法
  • 7 SHA-2 演算法
  • 8 參見
  • 9 參考文献
  • 10 註解
  • 11 外部链接

[编辑] SHA-0和SHA-1

SHA-1 壓縮演算法中的一個迴圈。A, B, C, D 和 E 是這個state中的 32 位元文字;F 是會變化的非線性函數;<<<n 代表bit向左循環移動n個位置。n因操作而異。田代表modulo 232之下的加法,Kt 是一個常數。

最初載明的演算法於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-0和SHA-1可將一個最大264位元的訊息,轉換成一串160位元的訊息摘要;其設計原理相似於MIT教授Ronald L. Rivest所設計的密碼學雜湊演算法MD4MD5

[编辑] SHA-0的破解

CRYPTO 98上,兩位法國研究者提出一種對SHA-0的攻擊方式[1]:在261的計算複雜度之內,就可以發現一次碰撞(即兩個不同的訊息對應到相同的訊息摘要);這個數字小於生日攻擊法所需的280,也就是說,存在一種演算法,使其安全性不到一個理想的雜湊函數抵抗攻擊所應具備的計算複雜度。

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工時[2]

2004年8月17日,在CRYPTO 2004的Rump會議上,王小雲馮登國(Feng)、來學嘉(Lai),和于紅波(Yu)宣佈了攻擊MD5、SHA-0 和其他雜湊函數的初步結果。他們攻擊SHA-0的計算複雜度是 240,這意謂的他們的攻擊成果比Joux還有其他人所做的更好。請參見MD5 安全性。2005年二月,王小雲殷益群于紅波再度發表了對SHA-0破密的演算法,可在239的計算複雜度內就找到碰撞。

[编辑] SHA-1的破解

鑒於SHA-0的破密成果,專家們建議那些計畫利用SHA-1實作密碼系統的人們也應重新考慮。在2004年CRYPTO會議結果公佈之後,NIST即宣布他們將逐漸減少使用SHA-1,改以SHA-2取而代之。

2005年RijmenOswald發表了對SHA-1較弱版本(53次的加密迴圈而非80次)的攻擊:在280的計算複雜度之內找到碰撞。

2005年二月,王小雲殷益群于紅波發表了對完整版SHA-1的攻擊,只需少於269的計算複雜度,就能找到一組碰撞。(利用生日攻擊法找到碰撞需要280的計算複雜度。)

這篇論文的作者們寫道;「我們的破密分析是以對付SHA-0的差分攻擊、近似碰撞、多區塊碰撞技術、以及從MD5演算法中尋找碰撞的訊息更改技術為基礎。沒有這些強力的分析工具,SHA-1就無法破解。」此外,作者還展示了一次對58次加密迴圈SHA-1的破密,在233個單位操作內就找到一組碰撞。完整攻擊方法的論文發表在2005年八月的CRYPTO會議中。

殷益群在一次面談中如此陳述:「大致上來說,我們找到了兩個弱點:其一是前置處理不夠複雜;其二是前20個迴圈中的某些數學運算會造成不可預期的安全性問題。」

2005年8月17日CRYPTO會議尾聲中王小雲姚期智姚儲楓再度發表更有效率的SHA-1攻擊法,能在263個計算複雜度內找到碰撞。

2006年CRYPTO會議上,Christian RechbergerChristophe De Cannière宣布他們能在容許攻擊者決定部分原訊息的條件之下,找到SHA-1的一個碰撞。

在密碼學的學術理論中,任何攻擊方式,其計算複雜度若少於暴力搜尋法所需要的計算複雜度,就能被視為針對該密碼系統的一種破密法;但這並不表示該破密法已經可以進入實際應用的階段。

就應用層面的考量而言,一種新的破密法出現,暗示著將來可能會出現更有效率、足以實用的改良版本。雖然這些實用的破密法版本根本還沒誕生,但確有必要發展更強的雜湊演算法來取代舊的演算法。在「碰撞」攻擊法之外,另有一種反譯攻擊法(Pre-image attack),就是由雜湊出的字串反推原本的訊息;反譯攻擊的嚴重性更在碰撞攻擊之上,但也更困難。在許多會應用到密碼雜湊的情境(如用戶密碼的存放、文件的數位簽章等)中,碰撞攻擊的影響並不是很大。舉例來說,一個攻擊者可能不會只想要偽造一份一模一樣的文件,而會想改造原來的文件,再附上合法的簽章,來愚弄持有私密金鑰的驗證者。另一方面,如果可以從密文中反推未加密前的使用者密碼,攻擊者就能利用得到的密碼登入其他使用者的帳戶,而這種事在密碼系統中是不能被允許的。但若存在反譯攻擊,只要能得到指定使用者密碼雜湊過後的字串(通常存在影檔中,而且可能不會透露原密碼資訊),就有可能得到該使用者的密碼。

[编辑] SHA-2

SHA-2 的第t個加密迴圈。圖中的深藍色方塊是事先定義好的非線性函數。ABCDEFGH一開始分別是八個初始值,Kt是第t個金鑰,Wt是本區塊產生第t個word。原訊息被切成固定長度的區塊,對每一個區塊,產生n個word(n視演算法而定),透過重複運作迴圈n次對ABCDEFGH這八個工作區段循環加密。最後一次迴圈所產生的八段字串合起來即是此區塊對應到的雜湊字串。若原訊息包含數個區塊,則最後還要將這些區塊產生的雜湊字串加以混合才能產生最後的雜湊字串。

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年曾對這些新變種作過一些研究,聲稱他們沒有找到弱點。

[编辑] SHA 所定義的長度

下表中的中繼雜湊值(internal state)表示對每個資料區塊壓縮雜湊過後的中繼值(internal hash sum)。詳情請參見Merkle-Damgård construction

演算法 輸出雜湊值長度 (bits) 中繼雜湊值長度 (bits) 資料區塊長度 (bits) 最大輸入訊息長度 (bits) 一個Word長度 (bits) 迴圈次數 使用到的運算子 碰撞攻擊 SHA-0 160 160 512 264 − 1 32 80 +,and,or,xor,rotl 是 SHA-1 160 160 512 264 − 1 32 80 +,and,or,xor,rotl 存在263 的攻擊 SHA-256/224 256/224 256 512 264 − 1 32 64 +,and,or,xor,shr,rotr 尚未出現 SHA-512/384 512/384 512 1024 2128 − 1 64 80 +,and,or,xor,shr,rotr 尚未出現

[编辑] SHAd

SHAd 函數是一個簡單的相同 SHA 函數的重述:

SHAd-256(m)=SHA-256(SHA-256(m))。它會克服有關延伸長度攻擊的問題。

[编辑] 應用

SHA-1, SHA-224, SHA-256, SHA-384 和 SHA-512 都被需要安全雜湊演算法的美國聯邦政府所應用,他們也使用其他的密碼演算法和協定來保護敏感的未保密資料。FIPS PUB 180-1 也鼓勵私人或商業組織使用 SHA-1 加密。Fritz-chip 將很可能使用 SHA-1 雜湊函數來實現個人電腦上的數位版權管理

首先推動安全雜湊演算法出版的是已合併的數位簽章標準

SHA 雜湊函數已被做為 SHACAL 分組密碼演算法的基礎。

[编辑] SHA-1 演算法

以下是 SHA-1 演算法的伪代码

Note: All variables are unsigned 32 bits and wrap modulo 232 when calculatingInitialize variables:h0 := 0x67452301h1 := 0xEFCDAB89h2 := 0x98BADCFEh3 := 0x10325476h4 := 0xC3D2E1F0Pre-processing:append the bit '1' to the messageappend k bits '0', where k is the minimum number >= 0 such that the resulting messagelength (in bits) is congruent to 448 (mod 512)append length of message (before pre-processing), in bits, as 64-bit big-endian integerProcess the message in successive 512-bit chunks:break message into 512-bit chunksfor each chunkbreak chunk into sixteen 32-bit big-endian words w[i], 0 ≤ i ≤ 15Extend the sixteen 32-bit words into eighty 32-bit words:for i from 16 to 79w[i] := (w[i-3] xor w[i-8] xor w[i-14] xor w[i-16]) leftrotate 1Initialize hash value for this chunk:a := h0b := h1c := h2d := h3e := h4Main loop:for i from 0 to 79if 0 ≤ i ≤ 19 thenf := (b and c) or ((not b) and d)k := 0x5A827999else if 20 ≤ i ≤ 39f := b xor c xor dk := 0x6ED9EBA1else if 40 ≤ i ≤ 59f := (b and c) or (b and d) or (c and d)k := 0x8F1BBCDCelse if 60 ≤ i ≤ 79f := b xor c xor dk := 0xCA62C1D6temp := (a leftrotate 5) + f + e + k + w[i]e := dd := cc := b leftrotate 30b := aa := tempAdd this chunk's hash to result so far:h0 := h0 + ah1 := h1 + bh2 := h2 + ch3 := h3 + dh4 := h4 + eProduce the final hash value (big-endian):digest = hash = h0 append h1 append h2 append h3 append h4

上述關於 f 運算式列於 FIPS PUB 180-1 中,以下替代運算式也許也能在主要迴圈裡計算 f

(0  ≤ i ≤ 19): f := d xor (b and (c xor d))         (alternative)(40 ≤ i ≤ 59): f := (b and c) or (d and (b or c))   (alternative 1)(40 ≤ i ≤ 59): f := (b and c) or (d and (b xor c))  (alternative 2)(40 ≤ i ≤ 59): f := (b and c) + (d and (b xor c))   (alternative 3)

[编辑] SHA-2 演算法

以下是SHA-256 演算法的虛擬碼。注意,64個word w[16..63]中的位元比起 SHA-1 演算法,混合的程度大幅提升。

Note: All variables are unsigned 32 bits and wrap modulo 232 when calculatingInitialize variables(first 32 bits of the fractional parts of the square roots of the first 8 primes 2..19):h0 := 0x6a09e667h1 := 0xbb67ae85h2 := 0x3c6ef372h3 := 0xa54ff53ah4 := 0x510e527fh5 := 0x9b05688ch6 := 0x1f83d9abh7 := 0x5be0cd19Initialize table of round constants(first 32 bits of the fractional parts of the cube roots of the first 64 primes 2..311):k[0..63] :=0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2Pre-processing:append the bit '1' to the messageappend k bits '0', where k is the minimum number >= 0 such that the resulting messagelength (in bits) is congruent to 448 (mod 512)append length of message (before pre-processing), in bits, as 64-bit big-endian integerProcess the message in successive 512-bit chunks:break message into 512-bit chunksfor each chunkbreak chunk into sixteen 32-bit big-endian words w[0..15]Extend the sixteen 32-bit words into sixty-four 32-bit words:for i from 16 to 63s0 := (w[i-15] rightrotate 7) xor (w[i-15] rightrotate 18) xor (w[i-15] rightshift 3)s1 := (w[i-2] rightrotate 17) xor (w[i-2] rightrotate 19) xor (w[i-2] rightshift 10)w[i] := w[i-16] + s0 + w[i-7] + s1Initialize hash value for this chunk:a := h0b := h1c := h2d := h3e := h4f := h5g := h6h := h7Main loop:for i from 0 to 63s0 := (a rightrotate 2) xor (a rightrotate 13) xor (a rightrotate 22)maj := (a and b) xor (a and c) xor (b and c)t2 := s0 + majs1 := (e rightrotate 6) xor (e rightrotate 11) xor (e rightrotate 25)ch := (e and f) xor ((not e) and g)t1 := h + s1 + ch + k[i] + w[i]h := gg := ff := ee := d + t1d := cc := bb := aa := t1 + t2Add this chunk's hash to result so far:h0 := h0 + ah1 := h1 + bh2 := h2 + ch3 := h3 + dh4 := h4 + eh5 := h5 + fh6 := h6 + gh7 := h7 + hProduce the final hash value (big-endian):digest = hash = h0 append h1 append h2 append h3 append h4 append h5 append h6 append h7

其中 ch 函數及 maj 函數可利用前述 SHA-1 的優化方式改寫。

SHA-224 和 SHA-256 基本上是相同的,除了:

  • h0h7 的初始值不同,以及
  • SHA-224 輸出時截掉 h7 的函數值。

SHA-512 和 SHA-256 的結構相同,但:

  • SHA-512 所有的數字都是64位元,
  • SHA-512 執行80次加密迴圈而非64次,
  • SHA-512 初始值和常數拉長成64位元,以及
  • 二者位元的偏移量和循環位移量不同。

SHA-384 和 SHA-512 基本上是相同的,除了:

  • h0h7 的初始值不同,以及
  • SHA-384 輸出時截掉 h6h7 的函數值。

[编辑] 參見

  • 编码
  • 密码学
  • 加密技术
  • 演算法

[编辑] 參考文献

  • Eli Biham, Rafi Chen, Near-Collisions of SHA-0, Cryptology ePrint Archive, Report 2004/146, 2004 (to appear CRYPTO 2004) [1]
  • Florent Chabaud, Antoine Joux: Differential Collisions in SHA-0. CRYPTO 1998. pp56–71
  • Henri Gilbert, Helena Handschuh: Security Analysis of SHA-256 and Sisters. Selected Areas in Cryptography 2003: pp175–193

[编辑] 註解

  1. ^ Chabaud and Joux, 1998
  2. ^ http://www.md5crk.com/sha0col/

[编辑] 外部链接

  • FIPS PUB 180-2安全雜湊標準
  • RFC 3174美國安全雜湊演算法 1 (SHA1)
  • 這個 Javascript SHA-1 計算機會展示計算過程中的中繼值