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

引言

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

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

針對SHA-1摘要碼的攻擊

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

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

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

信息認定碼

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

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

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

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

結束語

已有文獻記載了對采用SHA-1存儲器件的系統的攻擊(參見Whitepaper 3: Why are SHA-1 Devices Secure?)。但是，利用公開可讀的MAC發現被隱藏的密鑰是人們所知的唯一攻擊方法。就SHA-1而言，我們知道所定義的SHA-1算法具有兩點安全性：防碰撞和不可逆性。2005年中國學者提出的攻擊算法表明只是SHA-1算法的抗沖突略有不足，但這種攻擊不會影響Maxim的SHA-1存儲器件的安全性。

注釋:

1. X. Wang、Y.L. Yin和H. Yu.，Finding Collisions in the Full SHA-1, Advances in Cryptology—Crypto'05，http://www.infosec.sdu.edu.cn/paper/sha1-crypto-auth-new-2-yao.pdf (PDF)
2. 遵循"生日悖論(birthday paradox）”，發現SHA-1中的一次碰撞最多需要280次運算。這一觀點說明，基本上，如果試圖匹配任意兩個n位的輸出元數，只須考慮2(n/2)個元數，而并非2(n)個元數，找到匹配的可能性極高。眾所周知，所有hash函數都具有加密特性，該特性僅由輸出數據的位數決定。
3. SHA-1算法在信息單元塊之間大約需要進行1740次基本的算術運算。假定其它操作還需20%的額外開銷，完全執行一次算法需2100個時鐘周期。若使用一臺含64位CPU 的Cray X1超級計算機(截止到2005年最大規模的Cray計算機，單機柜結構)，發揮其每秒819億次浮點操作的峰值計算能力，需要連續工作12.4年才能生成一張完整的查找表。若采用廣告中宣稱的運算能力最強的Cray X1型超級計算機(帶64只機柜)，也需耗時兩個月。如此巨大的計算量使得此類攻擊所需花費的成本高而卻步。