本文是本系列的第三篇，密碼學(xué)的安全性淺析-1 密碼學(xué)的安全性淺析-2由于側(cè)重點(diǎn)是對(duì)密碼學(xué)中的安全性問(wèn)題進(jìn)行分析，所以不會(huì)對(duì)密碼學(xué)基礎(chǔ)的核心概念進(jìn)行闡述，如果閱讀本系列文章時(shí)不明白所涉及的術(shù)語(yǔ)時(shí)請(qǐng)參考國(guó)內(nèi)大學(xué)的推薦教材，如《密碼學(xué)原理與實(shí)踐》《深入淺出密碼學(xué)》，如果只是感興趣而并非要深入了解，只閱讀《圖解密碼技術(shù)》也就夠了。

MAC

MAC是指消息認(rèn)證碼（帶密鑰的Hash函數(shù)），是密碼學(xué)中通信實(shí)體雙方使用的一種驗(yàn)證機(jī)制，保證消息數(shù)據(jù)完整性的一種工具。構(gòu)造方法由M.Bellare提出，安全性依賴于Hash函數(shù)，故也稱帶密鑰的Hash函數(shù)。消息認(rèn)證碼是基于密鑰和消息摘要所獲得的一個(gè)值，可用于數(shù)據(jù)源發(fā)送方認(rèn)證和完整性校驗(yàn)。MAC一般不會(huì)從頭設(shè)計(jì)，而是從已有的哈希函數(shù)改造而來(lái)，比如加前綴、后綴或其他方法。

加前綴

加前綴時(shí)，返回的是Hash(K||M)，從而將普通的哈希函數(shù)轉(zhuǎn)為帶密鑰的哈希函數(shù)，其容易受到長(zhǎng)度擴(kuò)展攻擊、碰撞攻擊。

長(zhǎng)度擴(kuò)展攻擊

長(zhǎng)度擴(kuò)展攻擊我們之前已經(jīng)提過(guò)，在這種攻擊場(chǎng)景下，攻擊者可以在不知道M1和K的基礎(chǔ)上，僅通過(guò)Hash(K||M1)就可以計(jì)算出Hash(K||M1||M2),相當(dāng)于攻擊者可以偽造有效的MAC標(biāo)簽。

碰撞攻擊

此處的碰撞攻擊是由于密鑰長(zhǎng)度不同導(dǎo)致的。如果密鑰K1是24比特的16進(jìn)制字符串a(chǎn)bcdef，消息M1是12，則返回的是Hash(abcded12)，如果密鑰K2是abcd，消息M2是ef12，則返回的也是Hash(abcded12)，這就發(fā)生了碰撞

加后綴

加后綴的方法返回的是Hash(M||K),此時(shí)可以抵御長(zhǎng)度擴(kuò)展攻擊，但是還是會(huì)存在碰撞的問(wèn)題。

設(shè)有兩個(gè)消息M1,M2,存在碰撞Hash(M1)=Hash(M2),比如在SHA-256中，此時(shí)就會(huì)存在Hash(M1||K)=Hash(M2||K)

換言之，攻擊者通過(guò)如下流程即可發(fā)動(dòng)攻擊：

1.找到兩個(gè)碰撞的消息M1,M2

2.請(qǐng)求受害者計(jì)算M1哈希的MAC標(biāo)簽Hash(M1||K)

3.猜測(cè)相同的Hash(M2||K),從而偽造一個(gè)有效的標(biāo)簽并破壞MAC的安全性

HMAC

HMAC，即散列消息認(rèn)證碼（Hash-based message authentication code），是一種通過(guò)特別計(jì)算方式之后產(chǎn)生的消息認(rèn)證碼（MAC），使用密碼散列函數(shù)，同時(shí)結(jié)合一個(gè)加密密鑰。它可以用來(lái)保證資料的完整性，同時(shí)可以用來(lái)作某個(gè)消息的身份驗(yàn)證。

HMAC從哈希函數(shù)構(gòu)造MAC,這比前面兩種方案都安全，IPSec,SSH,TLS等都使用了HMAC

CMAC

CMAC，Cipher-based Message Authentication Code，它是一種基于分組密碼的消息認(rèn)證碼算法是基于密碼的MAC，只提供一個(gè)分組密碼如AES，就可以構(gòu)造MAC。

CBC-MAC是最早的CMAC，其用CBC模式對(duì)全0初始值IV下的消息M進(jìn)行加密,并只保留最后一組密文作為消息M的標(biāo)簽.基本的計(jì)算過(guò)程就是分別計(jì)算C1=E(K,M1),C2=E(K,M2⊗C1),C3=E(K,M3⊗C2)...對(duì)M的每個(gè)分組只保留最后的Ci，這就是經(jīng)過(guò)CBC-MAC的M的標(biāo)簽。

其容易被攻擊者構(gòu)造出新的消息-標(biāo)簽對(duì)。攻擊流程如下

設(shè)存在兩個(gè)不同的消息M1,M2，對(duì)應(yīng)的標(biāo)簽分別為T1=E(K,M1),T2=E(K,M2),攻擊者由此可以構(gòu)造出新的消息-標(biāo)簽對(duì)，即消息M1||(M2⊗T1)的標(biāo)簽為T2，推導(dǎo)過(guò)程如下：

要對(duì)M1||(M2⊗T1)生成標(biāo)簽，則先要計(jì)算C1=E(K,M1)=T1,然后計(jì)算C2=E(K,(M2⊗T1)⊗T1))=E(K,M2)=T2

由此，攻擊者就從兩個(gè)消息-標(biāo)簽對(duì)，且不知道密鑰的情況下構(gòu)造出了新的消息-標(biāo)簽對(duì)，這意味著攻擊者可以偽造CBC-MAC的標(biāo)簽，所以CBC-MAC并不安全

AE

AE，Authenticated encryption，即認(rèn)證加密，這既能實(shí)現(xiàn)消息的保密，又能保護(hù)消息的真實(shí)性，即實(shí)現(xiàn)認(rèn)證。所以一個(gè)AE算法既有密碼算法的特性又有MAC的特性。要實(shí)現(xiàn)AE，如下圖所示有三種方式：

同時(shí)加密和MAC(Encrypt-and-MAC,E&M)

發(fā)送方：給定明文P，計(jì)算得到密文C=E(K1,P),同時(shí)計(jì)算得到認(rèn)證標(biāo)簽T=MAC(K2,P)，發(fā)送C,T

接收方：計(jì)算P=D(K1,C)得到P，然后用這個(gè)P計(jì)算MAC(K2,P),將結(jié)果與收到的T比較。如果C或T損壞，認(rèn)證都會(huì)失敗。

這個(gè)方案理論上是最不安全的。即使用的是安全的MAC，也有可能從中泄露明文P的信息，因?yàn)镸AC僅用于確保不可偽造，不能確保隨機(jī)。除非用的MAC非常強(qiáng)大，比如偽隨機(jī)函數(shù)等。

SSH使用的就是這種方案，其用的MAC是HMAC-SHA-256,保證了不會(huì)泄露P的信息

先MAC再加密(MAC-then-Encrypt,MtE)

發(fā)送方：首先計(jì)算T=MAC(K2,P)來(lái)保護(hù)消息P,然后加密得到C=E(K1,P||T),這里將明文和標(biāo)簽一起加密，得到密文。發(fā)送方發(fā)送C

接收方：解密C，即P||T=D(K1,C)得到P||T,然后通過(guò)得到的明文P計(jì)算標(biāo)簽MAC(K2,P)，并與得到的T比較，如果符合，則認(rèn)證成功。

這種方式隱藏了明文的認(rèn)證標(biāo)簽，從而防止標(biāo)簽泄露明文中的認(rèn)證信息。

在TLS1.3之前，都是使用該方案。

先加密再M(fèi)AC(Encrypt-then-MAC,EtM)

發(fā)送方：首先加密得到密文C=E(K1,P),然后計(jì)算認(rèn)證標(biāo)簽T=MAC(K2,C)，將其發(fā)送

接收方：使用MAC(K2,C)計(jì)算結(jié)果與收到的T比較，若相符，則再計(jì)算P=D(K1,C),得到明文。

這個(gè)方案的優(yōu)勢(shì)在于：1.接收方只需要計(jì)算MAC就可知道信息是否損壞，如果損壞就不需要進(jìn)一步解密了；2.對(duì)于攻擊者而言，除非能破解MAC，否則不能同時(shí)將C和T發(fā)送給接收方獲得解密結(jié)果，這使得攻擊者更難向接收方發(fā)送惡意數(shù)據(jù)

所以這種方案是三者之間最安全的，IPSec使用了方案

AES-GCM

除了如上三種，組成起來(lái)實(shí)現(xiàn)，也有專門的認(rèn)證加密算法，其可以表示為

加密：AE(K,P)=(C,T),K是密鑰，P是明文，C是密文，T是身份認(rèn)證標(biāo)簽

解密：AD(K,C,T)=P,如果C,T至少有一個(gè)無(wú)效，則AD會(huì)返回錯(cuò)誤，而如果返回明文，則可以確保這個(gè)明文是被用正確密鑰加密過(guò)的明文。

從認(rèn)證角度看，其功能與MAC一樣，這意味著想要偽造AD能接收并解密的密文和標(biāo)記對(duì)(C,T)是不可能的

從加密角度看，認(rèn)證加密比普通密碼算法更安全，因?yàn)樗�只有在�?biāo)簽有效的情況下才會(huì)用密鑰進(jìn)行解密。這可以防止選擇密文攻擊。

認(rèn)證加密算法中目前唯一被承認(rèn)的正式標(biāo)準(zhǔn)就是AES-GCM,其基于AES算法，采用Galois計(jì)數(shù)器模式（GCM）實(shí)施。其示意圖如下

GCM本質(zhì)上是對(duì)CTR模式的改進(jìn)，集成了一個(gè)小組件計(jì)算身份認(rèn)證標(biāo)簽，其示意如下

AES-GCM容易受到攻擊，包括nonce重放攻擊以及由弱哈希密鑰、短標(biāo)簽等引發(fā)的攻擊。

nonce重放攻擊

這是AES-GCM最大的漏洞。如果用戶在兩次AES-GCM中使用相同的nonce N,攻擊者就可以獲得身份認(rèn)證密鑰H,繼而可以使用H為任何密文、關(guān)聯(lián)數(shù)據(jù)偽造標(biāo)簽。

其基本代數(shù)結(jié)構(gòu)如下

標(biāo)簽T通過(guò)下式計(jì)算得到：

上式中的GHASH是一個(gè)通用哈希函數(shù)，其輸入輸出線性相關(guān)

此時(shí)如果有用相同nonce計(jì)算得到的兩個(gè)標(biāo)簽T1,T2，將其異或可以得到

可以看到，此時(shí)AES的部分就消去了

然后利用GHASH的線性特性，攻擊者就可以確定H，從而拿到身份認(rèn)證密鑰

弱哈希密鑰

GHASH存在重大缺陷，哈希密鑰H的某些取值大大簡(jiǎn)化了對(duì)GCM認(rèn)證機(jī)制的攻擊，概括來(lái)說(shuō)，如果H的取值屬于某個(gè)特定的數(shù)學(xué)上定義的子群中時(shí)，攻擊者可以通過(guò)僅僅對(duì)前一條消息分組進(jìn)行變換從而猜測(cè)出某個(gè)消息的身份認(rèn)證標(biāo)簽T。

GHASH的內(nèi)部結(jié)構(gòu)我們這里略去，直接到最后一步，此時(shí)有

GHASH將消息的長(zhǎng)度與Xn異或，將結(jié)果乘以H，然后將這個(gè)值與AES(K,N||0)異或，從而得到身份認(rèn)證標(biāo)簽T

這里的漏洞在于，如果H=0,則不論Ci為何值都有Xn=0，與消息無(wú)關(guān)。這意味著，如果H=0,那么所有的消息都會(huì)具有相同的身份認(rèn)證標(biāo)簽；而如果H=1,那么標(biāo)簽實(shí)際上只是密文分組的異或，這樣會(huì)導(dǎo)致重新排序的密文分組會(huì)有相同的身份認(rèn)證標(biāo)簽。

當(dāng)然，除了H=0,H=1之外，當(dāng)H取其他值時(shí)也會(huì)發(fā)生異常情況。例如基于5階循環(huán)群的例子，設(shè)H=10d04d25f93556e69f58ce2f8d035a4,這是一個(gè)屬于長(zhǎng)度為5的循環(huán)的，H的取值滿足H^5=H，那么對(duì)任何5的倍數(shù)e，都有

H^e=H

那么在前面的Xn的表達(dá)式中，交換分組Cn（和H相乘）和分組Cn-4（和H^5相乘）不會(huì)改變身份認(rèn)證標(biāo)簽，這實(shí)際上就相當(dāng)于偽造了。即，攻擊者可在不知道密鑰的情況下，利用這個(gè)屬性構(gòu)造新的消息及其有效認(rèn)證標(biāo)簽。

更詳細(xì)的分析可以閱讀論文《Cycling Attacks on GCM, GHASH and Other Polynomial MACs and Hashes》

短標(biāo)簽

實(shí)際中AES-GCM通常返回128比特的標(biāo)簽，不過(guò)它可以生成任意長(zhǎng)度的標(biāo)簽，但是長(zhǎng)度越小，被偽造的可能性越高。

使用128比特長(zhǎng)度時(shí)，偽造成功的概率為1/2^128;但是，由于GCM結(jié)構(gòu)內(nèi)在缺陷，當(dāng)長(zhǎng)度較短時(shí)，偽造的概率要大于

1/2^n

比如如果長(zhǎng)度為32比特，則成功偽造的概率為1/2^16而不是我們以為的

1/2^32

根據(jù)Ferguson的論文指出，對(duì)于n比特標(biāo)簽，成功偽造概率為2^m/

2^n

其中2^m是攻擊者能夠獲得的對(duì)應(yīng)標(biāo)簽的最長(zhǎng)消息的分組數(shù)目。

舉個(gè)例子，如果使用48比特的標(biāo)簽去處理4GB的消息（2^28個(gè)塊）,

那么能夠偽造的概率為2^20，這在密碼學(xué)中是一個(gè)很高的概率了。

更詳細(xì)的分析可以閱讀論文《AuthenticationweaknessesinGCM》

RSA

RSA加密算法是一種非對(duì)稱加密算法，在公開密鑰加密和電子商業(yè)中被廣泛使用。RSA是由羅納德·李維斯特（Ron Rivest）、阿迪·薩莫爾（Adi Shamir）和倫納德·阿德曼（Leonard Adleman）在1977年一起提出的.RSA的工作原理就是創(chuàng)建一個(gè)被稱為陷門置換的數(shù)學(xué)對(duì)象。陷門置換描述的是符合下述性質(zhì)的函數(shù)：

將數(shù)字x變換為同一范圍內(nèi)的數(shù)字y，除非知道私鑰，否則不能從y計(jì)算得到x，這個(gè)私鑰就稱為陷門.

陷門置換

陷門置換是RSA的核心。給定模數(shù)n和公開指數(shù)e，RSA陷門置換將群Zn中的數(shù)x通過(guò)y= x^e mod n變換為群Zn中的另一個(gè)數(shù)y。

在加密時(shí)，n和e就是RSA的公鑰

為了能夠從y計(jì)算出x，則需要另一個(gè)數(shù)d，通過(guò)如下計(jì)算得到x

d就是陷門，也是RSA私鑰的一部分，d也被稱為秘密指數(shù)

d并不能任意取值，其必須滿足

這樣才能得到

這里需要注意，我們用的是模φ(n)而不是模n

φ(n)=(p-1)(q-1)，這個(gè)數(shù)對(duì)RSA的安全性至關(guān)重要，如果攻擊者能從模數(shù)n中求出φ(n)，就等價(jià)于破解了RSA。這是因?yàn)槿绻�知道�?n)，在計(jì)算e模φ(n)的逆，就可以得到d。為此，p和q也應(yīng)該保密，因?yàn)棣?n)可以由其計(jì)算得到

整個(gè)RSA的安全級(jí)別取決于n的大小、p與q的選擇、陷門置換的應(yīng)用；如果n太小，則容易對(duì)其分解，從而泄露私鑰；如果p與q太小或者太接近，則容易從n中確定出相應(yīng)取值；陷門置換不應(yīng)該被直接用于簽名或加密

陷門置換的誤用

在教科書中的RSA介紹中，通常會(huì)看到誤用陷門置換的情況，其被直接用于加密或者簽名了。即，RSA中的明文只是要加密的消息。這看起來(lái)沒問(wèn)題，實(shí)際上存在很大的風(fēng)險(xiǎn)。

加密

這種教科書式的RSA加密是確定性的，即對(duì)同一明文加密兩次，得到的密文是相同的。除此之外，更大的問(wèn)題是，當(dāng)給定兩個(gè)密文y1=x1^e mod n和

y2=x2^e mod n時(shí)，攻擊者可以通過(guò)將其相乘，得到明文x1xx2的密文：

這個(gè)結(jié)果就是消息x1xx2 mod n對(duì)應(yīng)的密文，這意味著，攻擊者可以從兩個(gè)RSA密文中構(gòu)造出新的有效密文。這種弱點(diǎn)我們稱之為擴(kuò)展性風(fēng)險(xiǎn)（安全的密碼應(yīng)該確保只有在知道x1,x2時(shí)才能得到兩者相乘的密文，如果只知道y1，y2是不能夠得到的）

為了使RSA不可擴(kuò)展，提出了OAEP，其中密文由待加密消息和一些padding組成,他們一起組成了RSA-OAEP。

OAEP的示意圖如下

圖中， n是RSA模數(shù)的位數(shù)，k0和k1是協(xié)議中的固定整數(shù)。m是n-k0-k1位長(zhǎng)的明文消息，G和H是隨機(jī)預(yù)言，如加密散列函數(shù)，⊕是異或運(yùn)算。

編碼過(guò)程包括如下步驟：

1. 用 k1 位長(zhǎng)的 0 將消息填充至 n - k0 位的長(zhǎng)度。
2. 隨機(jī)生成 k0 位長(zhǎng)的串 r
3. 用 G 將k0 位長(zhǎng)的 r 擴(kuò)展至 n - k0 位長(zhǎng)。
4. X = m00...0 ⊕ G(r)
5. H 將 n - k0 位長(zhǎng)的 X 縮短至 k0 位長(zhǎng)。
6. Y = r ⊕ H(X)
7. 輸出為 X || Y，在圖中 X 為最左邊的塊，Y 位最右邊的塊。

隨后可以使用 RSA 加密編碼的消息

解碼過(guò)程包括如下步驟：

1. 恢復(fù)隨機(jī)串 r 為 Y⊕H(X)
2. 恢復(fù)消息 m00...0 為 X ⊕ G(r)

簽名

教科書中的RSA簽名同樣是簡(jiǎn)化過(guò)的，通過(guò)直接計(jì)算y = x^d mod n對(duì)消息x進(jìn)行簽名。這雖然簡(jiǎn)單，便于初學(xué)者理解，但是其存在簽名被偽造的風(fēng)險(xiǎn)。

舉個(gè)最簡(jiǎn)單的例子，因?yàn)橛?/p>

0^d mod n=0

1^d mod n=1

(n-1)^d mod n = n-1

那么攻擊者一直可以在不知道d的情況下偽造0，1，n-1的簽名

更嚴(yán)重的攻擊手段我們稱之為盲簽名攻擊，即消息M不會(huì)被受害者主動(dòng)簽名，但是攻擊者可以讓M被受害者簽名。攻擊流程如下

1.攻擊者找到某個(gè)值R，R^eM mod n是受害者會(huì)簽名的一條信息，此時(shí)得到的簽名記做S=(R^eM)^d mod n，現(xiàn)在的問(wèn)題就是攻擊者怎樣能得到M的簽名，即M^d

2.推導(dǎo)如下

且

所以有

S=(ReM)^d

RM^d

為了得到M^d,將S除R即可

為了避免這種攻擊，提出了RSA概率簽名方案PSS,PSS之于RSA簽名等同于OAEP之于RSA加密，它能讓簽名更安全，其流程比較復(fù)雜，基本示意圖如下

此外還有更簡(jiǎn)單的簽名方案，即FDH，全域哈希。

Bellcore攻擊

Bellcore攻擊屬于錯(cuò)誤攻擊的一種，其迫使算法的一部分執(zhí)行不當(dāng)，產(chǎn)生錯(cuò)誤的結(jié)果，將其與正確結(jié)果相比較，從而獲得關(guān)于算法內(nèi)部值的信息。

Bellcore適用于使用中國(guó)剩余定理的確定性的RSA簽名方案。

由相關(guān)基礎(chǔ)知識(shí)，我們有

其中

假設(shè)攻擊者在就按xq時(shí)產(chǎn)生錯(cuò)誤，得到錯(cuò)誤值xq’，繼續(xù)使用xq‘并得到相應(yīng)的x’。那么攻擊者現(xiàn)在就可以計(jì)算正確的簽名x和錯(cuò)誤的簽名x‘的差，并由此分解模數(shù)n：

由上式，x-x'是p的倍數(shù)，即p是x-x'的除數(shù)，由于p也是n的除數(shù)，所以n和x-x'的最大公約數(shù)是p，即

然后就可以計(jì)算出q=n/p以及d，從而破解RSA簽名

共享模數(shù)n

我們直接舉個(gè)例子。

設(shè)攻擊者的私鑰為(n,d1),受害者的私鑰為(n,d2)，受害者公鑰為(n,e2),此時(shí)攻擊者知道n，不知道p和q，所以不能從公開指數(shù)e2計(jì)算秘密指數(shù)d2。那么怎么從d中計(jì)算出p和q呢？

我們知道d和e滿足

雖然我們不知道d或φ(n)，但是我們可以計(jì)算出kφ(n)=ed-1

根據(jù)歐拉定理，對(duì)于任何一個(gè)與n互素的數(shù)a，有a^(φ(n))=1 mod n，所以，對(duì)模數(shù)n，有下式：

由于kφ(n)是偶數(shù)，所以可以寫成2^st,所以可以把

寫成如下形式

式子中的x可以通過(guò)kφ(n)計(jì)算得到

x^2-1=（x-1）(x+1)，這意味

x^2-1可以被n整除，即x-1或x+1二者必有其一與n有相同的因數(shù)，從而可以算出n的因數(shù),從而攻破RSA。