SHA-1 器件的安全性是否依然足夠安全？

　　近來，幾名中國學者對安全散列算法(SHA)的強大安全性做出了攻擊。本白皮書將討論這種攻擊方式，其結果表明：盡管比起最初的想法, SHA-1 算法在抗碰撞上略有不足，但Dallas Semiconductor/Maxim 的SHA-1 存儲器件的安全性并未受到影響。因此，該公司的SHA-1 存儲器件(DS1963S、DS1961S、DS2432) 仍可以為附件/外設鑒別及防竄改、存儲器認證應用提供低成本、有效的解決方案。
引言

　　Dallas Semiconductor/Maxim 的SHA-1 存儲器件將為附件/外設鑒別及防竄改、存儲器認證應用提供低成本、高效的解決方案。這些SHA-1 存儲器件具有可鑒別特性，特別適合那些要求防范造假的應用，如大批量消耗品、高附加值硬件、硬件許可管理、樓宇進出控制或自動售貨機。

　　從根本上講，這些設備的實用性取決于安全散列算法的堅固性和安全性，這一算法是由美國國家標準技術研究所(NIST 在聯(lián)邦信息處理標準180-1 (FIPS PUB 180-1) 及ISO/IEC 10118-3 中定義的。近來，幾位中國學者攻擊了這種算法(見注釋一)。本文指出，盡管某些采用SHA-1 算法的應用其安全性有待重新評估，但Dallas Semiconductor/Maxim 的SHA-1 存儲器件的安全性不會受這一研究聲明的影響。

針對SHA-1 摘要碼的攻擊

　　FIPS PUB 180-1 標準中規(guī)定：SHA-1 能夠以安全的方式將數(shù)據(jù)計算壓縮成一段特定的信息。如文檔資料中所定義，SHA-1 算法的安全性有兩層含義：(1) 由一個給定的信息摘要不可能通過計算導出信息源；(2) 要找到兩條不同的信息使之產生相同的摘要在計算上是不可行的。第一條推論表明，由SHA-1 算法所得出的結果并不包含足夠的信息，不足以由此推出算法輸入中的全部文本信息(也就是說，該算法是不可逆的)；還包括如果僅僅知道摘要(輸出)的話，找出對應的原文信息(輸入)需要耗費大量的資源和時間。第二條推論表明，發(fā)現(xiàn)兩個計算結果相同的獨一無二的輸入信息需要耗費大量的資源和時間(也就是說，該算法具有抗沖撞性)。上述假定并不表明不存在兩條摘要相同的信息，只是很難找到而已。

　　從理論上來說，發(fā)現(xiàn)一次碰撞(摘要相同的兩條信息)最多需要進行280 雜散運算(參見注釋2)。學者們近來對于SHA-1 的攻擊表明：這一數(shù)字已經減小到只需269 次運算。這一新發(fā)現(xiàn)削弱了上文關于SHA-1 的第二條結論，因為它有效地將這種“計算上的不可行性”減小了211 級。但這并不意味著“發(fā)現(xiàn)信息摘要相同的兩條不同的信息”在計算上是可行的，只是相對先前的技術來說稍微易于實現(xiàn)而已。而且，研究人員的此次發(fā)現(xiàn)也并不意味著“由一個給定摘要反推出生成摘要的原始信息”在計算上是可行的，因為這次新的攻擊是建立在小心仔細地選擇兩個輸入信息基礎上的。唯一證明攻擊SHA-1 的方法是找到對應于某個給定摘要的一條信息，而沒有必要就是原始信息，如果要推出該原始信息，需要采用窮舉法進行2160 次搜索運算。

　　雖然有關SHA-1 算法的第二條結論的權威性由于中國學者的研究而被削弱，但沒理由懷疑該研究會對SHA-1 的第一條結論產生任何的影響。因此總的來說，SHA-1 仍然是不可逆的，只是或許在碰撞上略有不足。盡管如此，對于那些依賴于數(shù)字簽名的應用領域(如時間標注的或公證文檔來說，此項研究成果仍不失為一記警鐘。由于對于應用來說，輸入數(shù)據(jù)中的許多信息是相互關聯(lián)的，因此，出自中國學者、針對特定應用的攻擊是否有效還有待觀察。

信息認定碼

　　Dallas Semiconductor/Maxim 的SHA-1 存儲器件安全性依賴于雙向數(shù)據(jù)通信中的信息認證碼(MAC)。計算MAC 僅需要輸入公開的字符串(由存儲器內容、器件的唯一序列號和隨機質詢碼等組成)，和結合密碼字結合在一起，進行SHA-1 運算。以及一個作為SHA-1 算法輸入信息的機密密鑰。計算出的摘要(或散列)被稱為MAC。將MAC 連同信息一起傳輸，提供了一種安全的方法，驗證你是否知道密鑰，以及在傳輸過程中數(shù)據(jù)未被篡改。在讀操作期間，SHA-1 存儲器件以MAC 響應，據(jù)此驗證其是真實可信的，以及主機正確地接收數(shù)據(jù)。在寫操作期間，主機提供MAC，以驗證它有權對器件的存儲內容進行修改和器件正確地接收到新存儲器內容。

　　對基于MAC 的安全系統(tǒng)算法的成功攻擊是要找出密鑰。對大多數(shù)現(xiàn)有的SHA-1 存儲器件來說，其密鑰長度為64 位，僅能寫入(不久將推出新型的、更長的密鑰長度器件)。攻擊者向器件發(fā)出質詢碼，讀入器件生成的MAC 碼，接著對全部64 位數(shù)執(zhí)行一次窮舉搜索，直到發(fā)現(xiàn)相匹配的MAC 碼。這一過程需要進行264 次SHA-1 運算，一臺64 CPU Cray X1 超級計算機需要花費十多年時間才能計算出(參見注釋3)。

　　找到一條與給定摘要相匹配的信息源，需要2160 次運算(遠超過找出密鑰所需的264 次運算)。由于輸入信息的長度被固定為512 位，并且其中448 位是已知的公開數(shù)據(jù)，因此最直接的方法是尋找剩下64 位的正確值(即密鑰)。只要由一個給定的摘要不能反推出生成摘要的原始信息"，那么就不存在比窮舉法搜索密鑰更成功的攻擊方法。

　　注意：盡管為找出機密密鑰所進行的264 次運算其復雜程度要小于為發(fā)現(xiàn)一對信息發(fā)生碰撞需要的269 次運算，但兩種攻擊方式之間沒有可比性。如果研究人員找到一種在250 次運算之內發(fā)現(xiàn)SHA-1 碰撞，但仍然需要經過264 次SHA-1 運算才能找到密鑰。因此，此次新的攻擊雖然在任意兩條輸入信息之間找到碰撞的新攻擊方法，并不能用于為一個確定的輸入信息找到碰撞，這是因為需要仔細地選擇輸入信息。

結束語

　　已有文獻記載了對采用SHA-1 存儲器件的系統(tǒng)的攻擊(參見Whitepaper 3: Why are SHA-1 Devices Secure?)。但是，利用公開可讀的MAC 發(fā)現(xiàn)被隱藏的密鑰是人們所知的唯一攻擊方法。就SHA-1 而言，我們知道所定義的SHA-1 算法具有兩點安全性：防碰撞和不可逆性。最近的攻擊只表明：SHA-1 算法的防碰撞比以前略有下降，但這種攻擊不會影響Dallas Semiconductor/Maxim 的SHA-1 存儲器件的安全性。

注釋:

1. Collision Search Attack on SHA-1 (PDF)

2. 遵循"生日悖論(birthday paradox）”，發(fā)現(xiàn)SHA-1 中的一次碰撞最多需要280 次運算。這一觀點說明，基本上，如果試圖匹配任意兩個n 位的輸出元數(shù)，只須考慮2(n/2)個元數(shù)，而并非2(n)個元數(shù)，找到匹配的可能性極高。眾所周知，所有hash 函數(shù)都具有加密特性，該特性僅由輸出數(shù)據(jù)的位數(shù)決定。

3. SHA-1 算法在信息單元塊之間大約需要進行1740 次基本的算術運算。假定其它操作還需20%的額外開銷，完全執(zhí)行一次算法需2100 個時鐘周期。若使用一臺含64 位CPU 的Cray X1 超級計算機(目前最大規(guī)模的Cray 計算機，單機柜結構)，發(fā)揮其每秒819 億次浮點操作的峰值計算能力，需要連續(xù)工作12.4 年才能生成一張完整的查找表。若采用廣告中宣稱的運算能力最強的Cray X1 型超級計算機(帶64 只機柜)，也需耗時兩個月。如此巨大的計算量使得此類攻擊所需花費的成本高而卻步。