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

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

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

　　從根本上講，這些設(shè)備的實(shí)用性取決于安全散列算法的堅(jiān)固性和安全性，這一算法是由美國(guó)國(guó)家標(biāo)準(zhǔn)技術(shù)研究所(NIST 在聯(lián)邦信息處理標(biāo)準(zhǔn)180-1 (FIPS PUB 180-1) 及ISO/IEC 10118-3 中定義的。近來(lái)，幾位中國(guó)學(xué)者攻擊了這種算法(見注釋一)。本文指出，盡管某些采用SHA-1 算法的應(yīng)用其安全性有待重新評(píng)估，但Dallas Semiconductor/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è)給定的信息摘要不可能通過(guò)計(jì)算導(dǎo)出信息源；(2) 要找到兩條不同的信息使之產(chǎn)生相同的摘要在計(jì)算上是不可行的。第一條推論表明，由SHA-1 算法所得出的結(jié)果并不包含足夠的信息，不足以由此推出算法輸入中的全部文本信息(也就是說(shuō)，該算法是不可逆的)；還包括如果僅僅知道摘要(輸出)的話，找出對(duì)應(yīng)的原文信息(輸入)需要耗費(fèi)大量的資源和時(shí)間。第二條推論表明，發(fā)現(xiàn)兩個(gè)計(jì)算結(jié)果相同的獨(dú)一無(wú)二的輸入信息需要耗費(fèi)大量的資源和時(shí)間(也就是說(shuō)，該算法具有抗沖撞性)。上述假定并不表明不存在兩條摘要相同的信息，只是很難找到而已。

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

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

信息認(rèn)定碼

　　Dallas Semiconductor/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)證你是否知道密鑰，以及在傳輸過(guò)程中數(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ǔ)器件來(lái)說(shuō)，其密鑰長(zhǎng)度為64 位，僅能寫入(不久將推出新型的、更長(zhǎng)的密鑰長(zhǎng)度器件)。攻擊者向器件發(fā)出質(zhì)詢碼，讀入器件生成的MAC 碼，接著對(duì)全部64 位數(shù)執(zhí)行一次窮舉搜索，直到發(fā)現(xiàn)相匹配的MAC 碼。這一過(guò)程需要進(jìn)行264 次SHA-1 運(yùn)算，一臺(tái)64 CPU Cray X1 超級(jí)計(jì)算機(jī)需要花費(fèi)十多年時(shí)間才能計(jì)算出(參見注釋3)。

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

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

結(jié)束語(yǔ)

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

注釋:

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

2. 遵循"生日悖論(birthday paradox）”，發(fā)現(xiàn)SHA-1 中的一次碰撞最多需要280 次運(yùn)算。這一觀點(diǎn)說(shuō)明，基本上，如果試圖匹配任意兩個(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ī)(目前最大規(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)的成本高而卻步。