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

引言

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

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

針對(duì)SHA-1摘要碼的攻擊

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

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

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

信息認(rèn)定碼

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

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

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

注意：盡管為找出機(jī)密密鑰所進(jìn)行的2(64)次運(yùn)算其復(fù)雜程度要小于為發(fā)現(xiàn)一對(duì)信息發(fā)生碰撞需要的2(69)次運(yùn)算，但兩種攻擊方式之間沒有可比性。如果研究人員找到一種在2(50)次運(yùn)算之內(nèi)發(fā)現(xiàn)SHA-1碰撞，但仍然需要經(jīng)過2(64)次SHA-1運(yùn)算才能找到密鑰。因此，此次新的攻擊雖然在任意兩條輸入信息之間找到碰撞的新攻擊方法，并不能用于為一個(gè)確定的輸入信息找到碰撞，這是因?yàn)樾枰屑?xì)地選擇輸入信息。

結(jié)束語

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

注釋:

1. X. Wang、Y.L. Yin和H. Yu.，F(xiàn)inding Collisions in the Full SHA-1, Advances in Cryptology—Crypto'05，       (PDF)

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

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