複製鏈接
請複製以下鏈接發送給好友
https://baike.baidu.hk/item/SHA-1/1699692
複製
複製成功

SHA-1

鎖定
SHA-1（英語：Secure Hash Algorithm 1，中文名：安全散列算法1）是一種密碼散列函數，美國國家安全局設計，並由美國國家標準技術研究所（NIST）發佈為聯邦數據處理標準（FIPS）。SHA-1可以生成一個被稱為消息摘要的160位（20字節）散列值，散列值通常的呈現形式為40個十六進制數。
中文名
SHA-1
外文名
Secure Hash Algorithm 1
發    佈
1995年
提出者
美國國家安全局
屬    性
密碼散列函數
學    科
密碼學

目錄

  1. 1 介紹
  2. 2 SHA-0和SHA-1
  3. ▪ SHA-0的破解
  4. ▪ SHA-1的破解
  5. 3 SHA-1算法

SHA-1介紹

SHA-1（英語：Secure Hash Algorithm 1，中文名：安全散列算法1）是一種密碼散列函數，美國國家安全局設計，並由美國國家標準技術研究所（NIST）發佈為聯邦數據處理標準（FIPS）。SHA-1可以生成一個被稱為消息摘要的160位（20字節）散列值，散列值通常的呈現形式為40個十六進制數。 [1] 
SHA-1已經不再視為可抵禦有充足資金、充足計算資源的攻擊者。2005年，密碼分析人員發現了對SHA-1的有效攻擊方法，這表明該算法可能不夠安全，不能繼續使用，自2010年以來，許多組織建議用SHA-2或SHA-3來替換SHA-1。Microsoft、Google以及Mozilla都宣佈，它們旗下的瀏覽器將在2017年前停止接受使用SHA-1算法簽名的SSL證書。
2017年2月23日，CWI Amsterdam與Google宣佈了一個成功的SHA-1碰撞攻擊，發佈了兩份內容不同但SHA-1散列值相同的PDF文件作為概念證明。

SHA-1SHA-0和SHA-1

最初載明的算法於1993年發佈，稱做安全散列標準（Secure Hash Standard），FIPSPUB 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可將一個最大2^64比特的消息，轉換成一串160位的消息摘要；其設計原理相似於MIT教授Ronald L. Rivest所設計的密碼學散列算法MD4和MD5。 [1] 

SHA-1SHA-0的破解

在CRYPTO98上，兩位法國研究者提出一種對SHA-0的攻擊方式：在2的計算複雜度之內，就可以發現一次碰撞（即兩個不同的消息對應到相同的消息摘要）；這個數字小於生日攻擊法所需的2，也就是説，存在一種算法，使其安全性不到一個理想的散列函數抵抗攻擊所應具備的計算複雜度。
2004年時，Biham和Chen也發現了SHA-0的近似碰撞，也就是兩個消息可以散列出幾乎相同的數值；其中162比特中有142比特相同。他們也發現了SHA-0的完整碰撞（相對於近似碰撞），將本來需要80次方的複雜度降低到62次方。
2004年8月12日，Joux, Carribault, Lemuet和Jalby宣佈找到SHA-0算法的完整碰撞的方法，這是歸納Chabaud和Joux的攻擊所完成的結果。發現一個完整碰撞只需要2的計算複雜度。他們使用的是一台有256顆Itanium2處理器的超級計算機，約耗80,000 CPU工時。
2004年8月17日，在CRYPTO2004的Rump會議上，王小云，馮登國（Feng）、來學嘉（Lai），和於紅波（Yu）宣佈了攻擊MD5、SHA-0和其他散列函數的初步結果。他們攻擊SHA-0的計算複雜度是2，這意味着他們的攻擊成果比Joux還有其他人所做的更好。請參見MD5安全性。
2005年二月，王小云和殷益羣、於紅波再度發表了對SHA-0破密的算法，可在2的計算複雜度內就找到碰撞。

SHA-1SHA-1的破解

鑑於SHA-0的破密成果，專家們建議那些計劃利用SHA-1實現密碼系統的人們也應重新考慮。在2004年CRYPTO會議結果公佈之後，NIST即宣佈他們將逐漸減少使用SHA-1，改以SHA-2取而代之。
2005年，Rijmen和Oswald發表了對SHA-1較弱版本（53次的加密循環而非80次）的攻擊：在2的計算複雜度之內找到碰撞。
2005年二月，王小云、殷益羣及於紅波發表了對完整版SHA-1的攻擊，只需少於2的計算複雜度，就能找到一組碰撞。（利用生日攻擊法找到碰撞需要2的計算複雜度。）
這篇論文的作者們寫道；“我們的破密分析是以對付SHA-0的差分攻擊、近似碰撞、多區塊碰撞技術、以及從MD5算法中查找碰撞的消息更改技術為基礎。沒有這些強力的分析工具，SHA-1就無法破解。”此外，作者還展示了一次對58次加密循環SHA-1的破密，在2個單位操作內就找到一組碰撞。完整攻擊方法的論文發表在2005年八月的CRYPTO會議中。
殷益羣在一次面談中如此陳述：“大致上來説，我們找到了兩個弱點：其一是前置處理不夠複雜；其二是前20個循環中的某些數學運算會造成不可預期的安全性問題。”
2005年8月17日的CRYPTO會議尾聲中王小云、姚期智、姚儲楓再度發表更有效率的SHA-1攻擊法，能在2個計算複雜度內找到碰撞。
2006年的CRYPTO會議上，Christian Rechberger和Christophe De Cannière宣佈他們能在容許攻擊者決定部分原消息的條件之下，找到SHA-1的一個碰撞。
在密碼學的學術理論中，任何攻擊方式，其計算複雜度若少於暴力搜索法所需要的計算複雜度，就能被視為針對該密碼系統的一種破密法；但這並不表示該破密法已經可以進入實際應用的階段。
就應用層面的考量而言，一種新的破密法出現，暗示着將來可能會出現更有效率、足以實用的改良版本。雖然這些實用的破密法版本根本還沒誕生，但確有必要發展更強的散列算法來取代舊的算法。在“碰撞”攻擊法之外，另有一種反譯攻擊法（Pre-image attack），就是由散列出的字符串反推原本的消息；反譯攻擊的嚴重性更在碰撞攻擊之上，但也更困難。在許多會應用到密碼散列的情境（如用户密碼的存放、文件的數字簽名等）中，碰撞攻擊的影響並不是很大。舉例來説，一個攻擊者可能不會只想要偽造一份一模一樣的文件，而會想改造原來的文件，再附上合法的簽名，來愚弄持有公鑰的驗證者。另一方面，如果可以從密文中反推未加密前的用户密碼，攻擊者就能利用得到的密碼登錄其他用户的賬户，而這種事在密碼系統中是不能被允許的。但若存在反譯攻擊，只要能得到指定用户密碼散列過後的字符串（通常存在影檔中，而且可能不會透露原密碼信息），就有可能得到該用户的密碼。
2017年2月23日，Google公司公告宣稱他們與CWI Amsterdam合作共同創建了兩個有着相同的SHA-1值但內容不同的PDF文件，這代表SHA-1算法已被正式攻破。

SHA-1SHA-1算法

以下是SHA-1算法的偽代碼：
Note: All variables are unsigned 32 bits and wrap modulo 232when calculating
İniyorlar 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
上述關於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-1 功能，可以方便的生成字符串文本的 hash 值。 [2] 
參考資料