分組密碼
分組密碼是一種對稱密鑰算法。它將明文分成多個(gè)等長的模塊，使用確定的算法和對稱密鑰對每組分別加密解密。分組加密是極其重要的加密協(xié)議組成，其中典型的如AES和3DES作為美國政府核定的標(biāo)準(zhǔn)加密算法，應(yīng)用領(lǐng)域從電子郵件加密到銀行交易轉(zhuǎn)帳，非常廣泛?；玖鞒碳?xì)節(jié)這里不展開，可以參考密碼學(xué)相關(guān)教材，本文專注于分析其中與安全性有關(guān)的部分。
分組大小
分組密碼有兩個(gè)重要的特征：分組大小和密鑰大小，其安全性也取決于這兩個(gè)值，大多數(shù)分組密碼的分組大小為64比特或128比特，比如DES的分組為64比特，AES的分組為128比特，這些都是2的n次冪，因?yàn)檫@可以讓數(shù)據(jù)的存儲(chǔ)、尋址、處理等操作更加方便。
但是各位有沒有想過為什么是64、128，而不是256或者更小的32呢？
首先分組不能太大，我們應(yīng)該讓密文的長度和內(nèi)存占用盡可能小。比如我們使用AES加密16比特信息時(shí)，需要將信息轉(zhuǎn)換為128比特，然后對其處理得到128比特密文，很明顯，分組越大，開銷也越大。64比特、128比特對于大多數(shù)CPU的寄存器都可以方便操作。
同時(shí)分組不能太小，分組太小的話容易受到代碼本攻擊Codebook attack。代碼本攻擊是用16比特分組進(jìn)行的：
1.首先得到對應(yīng)于每個(gè)16比特明文分組的2^16個(gè)密文
2.然后建立代碼本，即查找表，將每個(gè)密文分組映射到相應(yīng)的明文分組
3.對未知的密文分組進(jìn)行解密，查找表中對應(yīng)的明文分組
如果使用的是16比特分組長度的密碼，則攻擊者建立的查找表只需要16x2^16=
2^20比特內(nèi)存，即128kb；而如果使用的是分組長度為32比特，則內(nèi)存需要16gb，這對于攻擊者而言都是可行的；而如果要攻擊64比特分組的密碼，攻擊者必須要有1ZB的內(nèi)存，這是不可行的。
分組構(gòu)造
我們知道，分組密碼實(shí)際上是一個(gè)循環(huán)多輪的運(yùn)算，輪本身是很弱的一系列運(yùn)算，但是數(shù)量很多。而循環(huán)的構(gòu)造主要有兩種技術(shù)：代換-置換網(wǎng)絡(luò)（Substitution-Permutation Network，SP-network或SPN））(AES采用)和Feistel方案(DES采用)
在分組密碼中，我們會(huì)明確規(guī)定輪與輪之間是不相同的，這是為什么呢？因?yàn)槿绻嗤脑挘菀资艿交瑒?dòng)攻擊Slide attack。
滑動(dòng)攻擊中的攻擊者找到兩個(gè)明文-密文對(P1,C1)(P2,C2),設(shè)R是分組密碼的輪函數(shù)，有P2=R(P1)。當(dāng)輪函數(shù)相同時(shí)，兩個(gè)明文之間的關(guān)系蘊(yùn)含著對應(yīng)的各自密文之間的關(guān)系即C2=R(C1)，下圖是輪數(shù)為3時(shí)的示意圖
攻擊者一旦知道一輪的輸入和輸出就有助于恢復(fù)出密鑰。
我們一般可以通過使用不同的子密鑰作為參數(shù)確保每輪的運(yùn)算是不同的，從而防止滑動(dòng)攻擊。
AES
AES的全稱是Advanced Encryption Standard，意思是高級加密標(biāo)準(zhǔn)。它的出現(xiàn)主要是為了取代DES加密算法的，因?yàn)槲覀兌贾繢ES算法的密鑰長度是56Bit，因此算法的理論安全強(qiáng)度是2的56次方。但二十世紀(jì)中后期正是計(jì)算機(jī)飛速發(fā)展的階段，元器件制造工藝的進(jìn)步使得計(jì)算機(jī)的處理能力越來越強(qiáng)，雖然出現(xiàn)了3DES的加密方法，但由于它的加密時(shí)間是DES算法的3倍多，64Bit的分組大小相對較小，所以還是不能滿足人們對安全性的要求。于是1997年1月2號(hào)，美國國家標(biāo)準(zhǔn)技術(shù)研究所宣布希望征集高級加密標(biāo)準(zhǔn)，用以取代DES。AES也得到了全世界很多密碼工作者的響應(yīng)，先后有很多人提交了自己設(shè)計(jì)的算法。最終有5個(gè)候選算法進(jìn)入最后一輪：Rijndael，Serpent，Twofish，RC6和MARS。最終經(jīng)過安全性分析、軟硬件性能評估等嚴(yán)格的步驟，Rijndael算法獲勝。
AES組成
AES每輪的四個(gè)步驟如下示意
圖中所示的運(yùn)算都是必要的，如果缺乏任一，AES都是不安全的，具體分析如下：
如果沒有KeyExpansion，所有輪都會(huì)使用相同的密鑰K，則容易受到滑動(dòng)攻擊；
如果沒有AddRoundKey，加密將不依賴于密鑰；這意味著，攻擊者可以在沒有密鑰的情況下解密密文；
SubBytes引入了非線性操作，增加了密碼強(qiáng)度，如果沒有SubBytes，AES只是由線性函數(shù)構(gòu)成的大系統(tǒng)，使用基礎(chǔ)的高等代數(shù)知識(shí)就可以破解它。
如果沒有ShiftRows，給定列中的更改就不會(huì)影響其他列，那么攻擊者就可以為每列構(gòu)造4個(gè)2^32個(gè)元素的查找表來攻破AES
如果沒有MixColumns，字節(jié)的變化不會(huì)影響該狀態(tài)的其他任何字節(jié)。那么對于選擇明文攻擊而言，只需存儲(chǔ)16個(gè)查找表（每個(gè)表256字節(jié)）后就可以解密任何密文，因?yàn)檫@些表中保存著每個(gè)字節(jié)可能的加密值。
AES實(shí)現(xiàn)
雖然在上一節(jié)中我們看到有SubBytes(),ShiftRows(),MixColumns()等操作，但是實(shí)際中的AES實(shí)現(xiàn)代碼并不會(huì)用這些函數(shù)，因?yàn)樾侍?，AES通過會(huì)基于表實(shí)現(xiàn)。
AES基于表的實(shí)現(xiàn)實(shí)際上是利用查詢硬編碼在程序中并在執(zhí)行時(shí)加載到內(nèi)存中的表以及XOR運(yùn)算替換SubBytes(),ShiftRows(),MixColumns()等操作，比如在openssl中其對應(yīng)的C語言實(shí)現(xiàn)如下
但是基于查找表的實(shí)現(xiàn)容易受到基于時(shí)間的緩存攻擊cache-timing attack，當(dāng)程序讀取或者寫入緩存中的元素時(shí)存在時(shí)間變化上的差異，因?yàn)樵L問cache中的元素的相對位置不同則時(shí)間也不同，通過這種差異攻擊者就可以知道程序訪問了哪個(gè)元素，進(jìn)而推測秘密。
操作模式
分組密碼加密模式中最簡單的就是ECB，ECB模式下的分組密碼是不安全的，一個(gè)直觀的示意如下所示
左側(cè)為原始圖像，右側(cè)為使用AES以ECB模式加密后的結(jié)果，可以看到在加密后的圖像上還是很容易看出企鵝，這本質(zhì)上是因?yàn)樵紙D像中灰度陰影的所有分組都被加密到新圖像中相同的新灰度陰影中。
而在CBC模式中也存在一定問題，CBC通常與固定IV一起使用，而不是使用隨機(jī)IV，這會(huì)導(dǎo)致什么問題呢？設(shè)兩個(gè)明文分組P1||P2在CBC模式下加密得到密文C1||C2;另外有明文分組P1||P2'使用相同的IV加密得到C1||C2'。其中P2與P2’是不同的分組，在得到的密文中，雖然C2和C2‘不同，但是C1是相同的，即危害在于，即使攻擊者只拿到密文，但是攻擊者仍然可以推測出兩個(gè)明文的第一個(gè)分組是相同的。
中間相遇攻擊
在分組密碼領(lǐng)域，有兩種必須知道的攻擊方案，一種是已經(jīng)介紹過的padding oracle attack，另一種是中間相遇攻擊。
提到中間相遇攻擊，不知道大家有沒有想過一個(gè)問題，為什么DES進(jìn)一步派生出3DES，而不是2DES呢？
因?yàn)橥ㄟ^中間相遇攻擊，2DES的安全性依然相當(dāng)于DES，分析如下
設(shè)有一個(gè)2DES算法C=E(K2,E(K1,P))，其中P為明文，K1,K2均為56比特的密鑰。攻擊示意如圖
流程如下
1.首先構(gòu)建有2^56項(xiàng)的E(K1,P)的密鑰值表
2.對于K2的所有2^56個(gè)值，計(jì)算D(K2,C)并檢查結(jié)果值是否出現(xiàn)在表的索引中
3.如果出現(xiàn)，則從表中取出對應(yīng)的K1,并使用相應(yīng)的P,C驗(yàn)證找到的K1,K2是否正確，再用它們加密P看是否能得到C，如果可以則說明攻擊成功
可以看到，這種攻擊方式只需要2x2^56次操作即可，遠(yuǎn)小于
2^112
而如果我們將這種攻擊方式應(yīng)用于3DES,可以推算出來，第三階段需要計(jì)算K2,K3的所有2^112個(gè)值，這意味說3DES實(shí)際上只有112比特的安全性，盡管其密鑰長度為168比特。
序列密碼
序列密碼也稱為流密碼（Stream Cipher），它是對稱密碼算法的一種。序列密碼具有實(shí)現(xiàn)簡單、便于硬件實(shí)施、加解密處理速度快、沒有或只有有限的錯(cuò)誤傳播等特點(diǎn)，因此在實(shí)際應(yīng)用中，特別是專用或機(jī)密機(jī)構(gòu)中保持著優(yōu)勢，典型的應(yīng)用領(lǐng)域包括無線通信、外交通信。
基于硬件
基于硬件的序列密碼基本都離不開反饋移位寄存器FSR。
上圖所示是一個(gè)n級反饋移位寄存器。
其中，a0，a1，…，an1為初態(tài)。F為反饋函數(shù)或者反饋邏輯。如果F為線性函數(shù)，那么我們稱其為線性反饋移位寄存器LFSR，否則我們稱其為非線性反饋移位寄存器NFSR。ai+n=F(ai,ai+1,...,ai+n1)
FSR被無數(shù)序列密碼使用，因?yàn)樗浅：唵味胰菀桌斫?，從上圖可見，其包含由一些比特組成的數(shù)組以及一個(gè)更新的反饋函數(shù)F，F(xiàn)SR的狀態(tài)存儲(chǔ)在數(shù)組或寄存器中，每次更新就是使用F改變狀態(tài)并產(chǎn)生一個(gè)輸出比特。在使用FSR時(shí)，需要盡量避免使用短周期的，因?yàn)檫@樣會(huì)使輸出序列更容易預(yù)測。
LFSR中文為線性反饋移位寄存器，是具有線性反饋函數(shù)的FSR。在密碼學(xué)中，線性性質(zhì)意味著可預(yù)測性，也暗示著存在簡單并容易理解的數(shù)學(xué)結(jié)構(gòu)。在序列密碼中使用LFSR并不安全，假設(shè)一個(gè)LFSR的長度為n，攻擊者僅需要n比特輸出就可以還原該寄存器的初始狀態(tài)，由此可以反推之前的狀態(tài)信息并得到之后的輸出序列，這種攻擊基于Berlekamp-Massey(BM)算法，其依賴于LFSR的數(shù)學(xué)結(jié)構(gòu)去建立方程，求解方程即可。實(shí)際上攻擊者即使不知道n，也可以通過窮舉所有可能的長度進(jìn)行攻擊。
為了掩蓋LFSR的線性性質(zhì)，可以對LFSR的輸出序列進(jìn)行非線性過濾以得到非線性程度更高的密鑰序列，稱其為過濾生成器，如下所示
圖中的g為非線性函數(shù)，如異或、邏輯與、邏輯或等。
不過這還是會(huì)受到其他復(fù)雜的攻擊：
代數(shù)攻擊Algebraic attack:當(dāng)未知變量是LFSR的內(nèi)部狀態(tài)比特時(shí)，代數(shù)攻擊可以求解以內(nèi)部狀態(tài)為未知變量的非線性方程
立方攻擊Cube attacks:通過計(jì)算非線性方程的微商，使其方程的代數(shù)次數(shù)降到1次，進(jìn)而得到線性方程組從而求解
快速相關(guān)攻擊Fast correlation attacks:挖掘非線性過濾函數(shù)和線性函數(shù)的相似度來實(shí)施攻擊
為了徹底解決這個(gè)問題可以使用NFSR，即非線性反饋移位寄存器，它使用了非線性函數(shù)，它的輸出比特和狀態(tài)比特之間的代數(shù)關(guān)系的復(fù)雜性更高，隨著運(yùn)行次數(shù)的增加，復(fù)雜性呈指數(shù)規(guī)模增長。
A5/1
基于硬件的序列密碼中的一個(gè)代表算法就是A5/1，其被用于2G移動(dòng)通信中，用于對語音通信加密.示意圖如下
A5/1流密碼使用三個(gè)LFSR。雖然我們前面說LFSR不安全，但是A5/1使用小技巧是它變得較為安全，它使用的3個(gè)LFSR并非每一時(shí)刻都輸出，而是通過下面的鐘控規(guī)則決定每個(gè)寄存器的停走：如果某個(gè)寄存器的鐘控位（橙色）和另一個(gè)寄存器的鐘控位相同或著三個(gè)寄存器的鐘控位都相同，則對該寄存器作移位操作。
特別地，在2G通信中使用的A5/1算法有64比特密鑰和22比特nonce，其中加密每一幀所用的nonce不同，針對A5/1的攻擊旨在恢復(fù)算法的64比特的初始狀態(tài)（即三個(gè)寄存器的長度之和19+22+23）,然后通過算法的初始化原理恢復(fù)nonce和密鑰。這種攻擊屬于已知明文攻擊，因?yàn)楣粽咝枰啦糠置魑囊约皩?yīng)的密文，這樣通過異或運(yùn)算可以得到部分密鑰序列比特。針對A5/1的攻擊主要有兩類，分別是細(xì)致攻擊subtle attack以及暴力攻擊brutal attack.
subtle attack是挖掘算法內(nèi)部的線性性質(zhì)并利用它相對簡單的鐘控系統(tǒng)，攻擊者需要猜測一些內(nèi)部狀態(tài)比特以確定其他狀態(tài)比特，本質(zhì)上就是遍歷第一個(gè)和第二個(gè)寄存器的所有可能取值以及前11個(gè)時(shí)鐘周期里第三個(gè)寄存器的鐘控比特的所有可能取值，由此建立方程得到第三個(gè)寄存器的內(nèi)部狀態(tài)。偽碼如下
brutal attack將算法看做是一個(gè)64比特輸入(內(nèi)部狀態(tài))到64比特（前64比特密鑰序列）輸出的黑盒，本質(zhì)是通過消耗內(nèi)存降低暴力攻擊的成本：預(yù)算計(jì)算一個(gè)有2^64個(gè)元素的表，表中的元素是每個(gè)可能的密鑰和其對應(yīng)的輸出。在攻擊時(shí)，根據(jù)輸出，通過查表就可以得到對應(yīng)的密鑰。
基于軟件
RC4
在密碼學(xué)中，RC4（來自Rivest Cipher 4的縮寫）是一種流加密算法，密鑰長度可變。它加解密使用相同的密鑰，因此也屬于對稱加密算法.RC4應(yīng)用非常廣泛，在WEP中，RC4用于加密802.11幀的有效負(fù)載，這些數(shù)據(jù)通過數(shù)據(jù)包的形式進(jìn)行傳輸。在同一會(huì)話中交付的所有有效負(fù)載都使用相同的40比特或104比特的密鑰，且在幀頭有一個(gè)唯一的3字節(jié)的nonce編碼。
這里的關(guān)鍵在于RC4不支持nonce，而在WEP中使用nonce會(huì)造成風(fēng)險(xiǎn)，其原因在于：
nonce的比特?cái)?shù)太少，只有24比特，這意味著對于攻擊者而言，即使每條消息都隨機(jī)選擇一個(gè)nonce，只需等到2^12包，就能找到兩個(gè)用相同的nonce加密的包，他們有相同的密鑰序列，攻擊者可以用其去解密數(shù)據(jù)包；此外還有更嚴(yán)重的問題--nonce和密鑰的結(jié)合方式有助于恢復(fù)密鑰。WEP中的nonce是公開的，它的三個(gè)字節(jié)使攻擊者能夠在密鑰編排方案的三次迭代后確定S的值，基于此密鑰分析人員發(fā)現(xiàn)密碼序列的第一個(gè)字節(jié)和密鑰的第一個(gè)字節(jié)有很強(qiáng)的相關(guān)性，其導(dǎo)致的偏差可以被用于恢復(fù)密鑰。
在實(shí)際場景中，這就會(huì)造成選擇明文攻擊。
在TLS中也使用過RC4，這時(shí)存在風(fēng)險(xiǎn)的原因是在于，RC4存在統(tǒng)計(jì)數(shù)據(jù)偏差：RC4生成的密鑰序列的第二個(gè)字節(jié)是0的概率是1/128，而理想情況下應(yīng)該是1/256;不僅如此，實(shí)際上，前256個(gè)字節(jié)都有偏差，之前就有研究人員發(fā)現(xiàn)，其中某字節(jié)為0的概率為1/256+c/256^2,c取值介于0.24到1.34.
通過這種缺陷去攻擊TLS的過程也非常直觀，只需要收集密文并尋找明文，攻擊者需要收集很多密文，并且這些密文是同不同的密鑰對相同的明文加密得到的。設(shè)攻擊者拿到了同一明文P1加密得到的多組密文，現(xiàn)在要解密明文P1.前4個(gè)密文字節(jié)是這樣的：
由于前面提到RC4存在統(tǒng)計(jì)偏差，密鑰序列字節(jié)SK1i取值為0的可能性更大，所以對應(yīng)的C1i等于P1的可能性更大。在給定C1i后，為了確定P1,只需計(jì)算每個(gè)字節(jié)值出現(xiàn)次數(shù)并返回出現(xiàn)次數(shù)最多的那個(gè)值，它就是P1.
哈希函數(shù)
散列函數(shù)（Hash function）又稱散列算法、哈希函數(shù)，是一種從任何一種數(shù)據(jù)中創(chuàng)建小的數(shù)字“指紋”的方法。散列函數(shù)把消息或數(shù)據(jù)壓縮成摘要，使得數(shù)據(jù)量變小，將數(shù)據(jù)的格式固定下來。該函數(shù)將數(shù)據(jù)打亂混合，重新創(chuàng)建一個(gè)叫做哈希值或散列值（hash values，hash codes，hash sums，或hashes）的指紋。其運(yùn)行的示意圖如下
生日攻擊
我們知道哈希函數(shù)存在原像攻擊和碰撞攻擊。
給定任意哈希值H，原像是指滿足Hash(M)=H的消息M，原像攻擊指給定隨機(jī)哈希值，攻擊者可以找到原始消息，這一般也被稱作第一原像攻擊。
除此之外，還存在第二原像攻擊，即給定消息M1時(shí)，攻擊者能夠找到另一條消息M2,其哈希值與M1的哈希值相同。
而碰撞攻擊則是指攻擊者可以找到具有相同哈希值的兩條不同的消息。
碰撞攻擊的本質(zhì)是鴿巢原理：有n只鴿子和m個(gè)鴿洞,所有鴿子都住在鴿巢里,如果n>m,那么至少有二只鴿子必須住在同一鴿巢里。
可以說這是不可避免的，但是對于哈希函數(shù)而言，碰撞應(yīng)該像原始消息一樣難于找到。
通過上面的表述，我們可以看到第二原像攻擊與碰撞攻擊存在一定聯(lián)系：
第二原像攻擊定義為：
給定固定消息m1，找到另一個(gè)消息m2，使hash（m2）=hash（m1）。
碰撞攻擊定義為：
找到兩個(gè)任意不同的消息m1和m2，使hash（m1）=hash（m2）。
區(qū)別在于第二原像攻擊是給定了m1的，而碰撞攻擊沒有。就攻擊難度而言，前者更難。同時(shí)，我們也可以看出，任何具有抗碰撞性的哈希函數(shù)，也能夠抵御第二原像攻擊。
找到碰撞與找到原像要快，需要2^(n/2)次
而不是2^n次，這背后的原理我們稱之為生日攻擊。
生日攻擊是一種密碼學(xué)攻擊手段，所利用的是概率論中生日問題的數(shù)學(xué)原理。這種攻擊手段可用于濫用兩個(gè)或多個(gè)集團(tuán)之間的通信。此攻擊依賴于在隨機(jī)攻擊中的高碰撞概率和固定置換次數(shù)（鴿巢原理）。
舉個(gè)例子
設(shè)一位老師問一個(gè)有30名學(xué)生的班級（n=30）每個(gè)人的生日在哪一天以確定是否有兩個(gè)學(xué)生同一天生日（對應(yīng)碰撞）。從直覺角度考慮，機(jī)率看起來很小。若老師選擇特定日期（例如9月16日），則至少有一名學(xué)生在那天出生的幾率是1-（364/365）^30，約為7.9%。但是，與我們的直覺相反的是，至少一名學(xué)生和另外任意一名學(xué)生有著相同生日的幾率大約為70.63%（n=30時(shí)），即
1-365!(365-n)!x365^n
更簡潔的結(jié)論就是，如果班級有23人，則其中有兩個(gè)學(xué)生出生日期相同的概率為1/2。
知道生日攻擊的原理后，我們看看對應(yīng)的攻擊方案：
樸素的生日攻擊方案如下：
1.計(jì)算任意選擇的2^(n/2)個(gè)消息的哈希，并將所有的消息-哈希對存下來
2.重排哈希值列表
3.搜索排序后的列表以查找具有相同哈希值的兩個(gè)連續(xù)條目
可以看到，這種方法需要大量的內(nèi)存，同時(shí)對大量元素進(jìn)行排序會(huì)減慢搜索的速度。
研究人員在此基礎(chǔ)上提出了低內(nèi)存的攻擊方案：Rho攻擊（來自Pollard Rho算法），流程如下
1.給定具有n比特哈希值的哈希函數(shù)，選擇一些隨機(jī)哈希值H1,設(shè)H1'=H1
2.計(jì)算H2=Hash(H1),H2'=Hash(Hash(H1'))
3.迭代該過程并計(jì)算Hi+1=Hash(Hi)，Hi+1'=Hash(Hash(Hi'))，直到有一個(gè)i可以滿足Hi+1=Hi+1'
對應(yīng)的示意圖如下
可以看到這個(gè)序列最終會(huì)形成一個(gè)循環(huán)，循環(huán)從H5開始，找到的碰撞是Hash(H4)=Hash(H10)=H5,只要我們能夠找到循環(huán)，就能夠找到碰撞。對于攻擊者而言，首先找到循環(huán)點(diǎn)，然后發(fā)現(xiàn)碰撞，不需要在內(nèi)存中存儲(chǔ)大量的值，也不需要排序。
循環(huán)以及尾部各自有大約2^(n/2)個(gè)值，所以大約需要
2^(n/2)x2次哈希運(yùn)算就能找到碰撞
這里再多說一句，密碼學(xué)中一般使用Pollard Rho算法分解大整數(shù)，其基于大整數(shù)n=pq中p和q之間有一個(gè)因子很小,在此情況下,可以利用該算法完成對n的分解,它是基于尋找指定哈希函數(shù)的碰撞的思想才設(shè)計(jì)出來的，也就是我們上文提到的過程。假設(shè)找到了碰撞，即找到不相等的x,x'并且有
x mod p=x'mod p
那實(shí)際上我們就知道x,x'相差p的整數(shù)倍，由此可以知道gcd(x-x',n)，如果不是1也不是n，那么就分解成功。
長度擴(kuò)展攻擊
對消息進(jìn)行哈希處理的最簡單方法就是將其分成多個(gè)分組，并使用類似的算法連續(xù)處理每個(gè)分組。這種方法被稱為迭代哈希，其主要有兩種形式：
1.使用壓縮函數(shù)迭代哈希，將輸入轉(zhuǎn)換為較小的輸出，如下所示
這種結(jié)構(gòu)也被稱為Merkel-Damgard結(jié)構(gòu)
2.使用將輸入轉(zhuǎn)換為相同大小的輸出的函數(shù)進(jìn)行迭代哈希，是的任意兩個(gè)不同的輸入給出兩個(gè)不同的輸出，如下所示
這種函數(shù)被稱為海綿函數(shù)
基于M-D結(jié)構(gòu)的有MD4,MD5,SHA-1,SHA-2系列，基于后者的最著名的海綿函數(shù)是Keccak，也被稱為SHA-3。
對于M-D而言，其主要威脅就是長度擴(kuò)展攻擊。長度擴(kuò)展攻擊是指一種針對特定加密散列函數(shù)的攻擊手段，攻擊者可以利用H（消息1）和消息1的長度，不知道消息1內(nèi)容的情形下，將攻擊者控制的消息2計(jì)算出H（消息1‖消息2）。我們來看下面的例子
設(shè)存在未知消息M的Hash(M)，M由M1,M2組成，那么攻擊者對于任意消息M3都可以確定Hash(M1||M2||M3)。這種攻擊可行的原因在于M1||M2的哈希是跟在M2之后的鏈值，所以可以將另一個(gè)分組M3添加到哈希中。
SHA-2就存在這個(gè)問題，解決方案也很簡單，如BLAKE2中讓最后一個(gè)壓縮函數(shù)與其他函數(shù)都不同即可。
繞過存儲(chǔ)證明協(xié)議
存儲(chǔ)證明協(xié)議在云計(jì)算中應(yīng)用廣泛，其使用哈希函數(shù)，使得服務(wù)器能夠向用戶證明服務(wù)器確實(shí)存儲(chǔ)了應(yīng)該存儲(chǔ)的用戶文件。Kotla等人就提出一種存儲(chǔ)證明協(xié)議（詳情見SafeStore:A Durable and Practical Storage System），設(shè)要存的文件為M,過程如下：
1.客戶端選擇一個(gè)隨機(jī)值C并發(fā)送給服務(wù)器
2.服務(wù)器計(jì)算Hash(M||C)并返回給客戶端
3.客戶端計(jì)算Hash(M||C)并比服務(wù)器返回的值作比較，如果吻合則說明服務(wù)器確實(shí)存儲(chǔ)著M
這個(gè)協(xié)議可行的前提是如果服務(wù)器不知道M，那么就不能正確計(jì)算出H(M||C)
但是這里的缺陷在于，Hash是一個(gè)迭代的哈希，其會(huì)逐分組處理輸入信息，計(jì)算每個(gè)分組之間的中間鏈值。服務(wù)器利用這一點(diǎn)完成可以實(shí)現(xiàn)欺騙，怎么做呢？
當(dāng)服務(wù)器接收到M時(shí)，計(jì)算H1=Compress(H0,M1),H0是哈希函數(shù)的初始值，然后記錄H1并刪除M，此時(shí)服務(wù)器已經(jīng)沒有存儲(chǔ)著M了。當(dāng)客戶端發(fā)送C時(shí)，服務(wù)器可以計(jì)算出Compress(H1,C)并將其作為Hash(M||C)的結(jié)果返回。此時(shí)客戶端會(huì)驗(yàn)證成功，由此就欺騙了該協(xié)議。
對于SHA-1，SHA-2,SHA-3以及BLAKE2都存在這個(gè)問題。其實(shí)對應(yīng)的解決方案很簡單，要求服務(wù)器計(jì)算Hash(C||M)而不是Hash(M||C)即可。
參考
1.https://www.iacr.org/archive/eurocrypt2000/1807/18070595-new.pdf
2.https://ieeexplore.ieee.org/document/6378229
3.https://eprint.iacr.org/2018/522.pdf
4.http://www.dcs.fmph.uniba.sk/diplomovky/obhajene/getfile.php/master-mv.pdf?id=132&fid=219&type=application%2Fpdf
5.SafeStore:A Durable and Practical Storage System
