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

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

引言

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

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

針對SHA-1摘要碼的攻擊

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

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

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

信息認定碼

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

對基于MAC的安全系統(tǒng)算法的成功攻擊是要找出密鑰。對大多數(shù)現(xiàn)有的SHA-1存儲器件來說，其密鑰長度為64位，僅能寫入(不久將推出新型的、更長的密鑰長度器件)。攻擊者向器件發(fā)出質(zhì)詢碼，讀入器件生成的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次運算之內(nèi)發(fā)現(xiàn)SHA-1碰撞，但仍然需要經(jīng)過264次SHA-1運算才能找到密鑰。因此，此次新的攻擊雖然在任意兩條輸入信息之間找到碰撞的新攻擊方法，并不能用于為一個確定的輸入信息找到碰撞，這是因為需要仔細地選擇輸入信息。

結(jié)束語

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

注釋:

1. X. Wang、Y.L. Yin和H. Yu.，F(xiàn)inding 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）”，發(fā)現(xiàn)SHA-1中的一次碰撞最多需要280次運算。這一觀點說明，基本上，如果試圖匹配任意兩個n位的輸出元數(shù)，只須考慮2(n/2)個元數(shù)，而并非2(n)個元數(shù)，找到匹配的可能性極高。眾所周知，所有hash函數(shù)都具有加密特性，該特性僅由輸出數(shù)據(jù)的位數(shù)決定。
3. SHA-1算法在信息單元塊之間大約需要進行1740次基本的算術(shù)運算。假定其它操作還需20%的額外開銷，完全執(zhí)行一次算法需2100個時鐘周期。若使用一臺含64位CPU 的Cray X1超級計算機(截止到2005年最大規(guī)模的Cray計算機，單機柜結(jié)構(gòu))，發(fā)揮其每秒819億次浮點操作的峰值計算能力，需要連續(xù)工作12.4年才能生成一張完整的查找表。若采用廣告中宣稱的運算能力最強的Cray X1型超級計算機(帶64只機柜)，也需耗時兩個月。如此巨大的計算量使得此類攻擊所需花費的成本高而卻步。