密碼學的安全性淺析3
前言
本文是本系列的第三篇，由於側重點是對密碼學中的安全性問題進行分析，所以不會對密碼學基礎的核心概念進行闡述，如果閱讀本系列文章時不明白所涉及的術語時請參考國內大學的推薦教材，如《密碼學原理與實踐》《深入淺出密碼學》，如果只是感興趣而並非要深入了解，只閱讀《圖解密碼技術》也就夠了。
MAC
MAC是指消息認證碼（帶密鑰的Hash函數），是密碼學中通信實體雙方使用的一種驗證機制，保證消息數據完整性的一種工具。構造方法由M.Bellare提出，安全性依賴於Hash函數，故也稱帶密鑰的Hash函數。消息認證碼是基於密鑰和消息摘要所獲得的一個值，可用於數據源發送方認證和完整性校驗。MAC一般不會從頭設計，而是從已有的哈希函數改造而來，比如加前綴、後綴或其他方法。
加前綴
加前綴時，返回的是Hash(K||M)，從而將普通的哈希函數轉為帶密鑰的哈希函數，其容易受到長度擴展攻擊、碰撞攻擊。
長度擴展攻擊
長度擴展攻擊我們之前已經提過，在這種攻擊場景下，攻擊者可以在不知道M1和K的基礎上，僅通過Hash(K||M1)就可以計算出Hash(K||M1||M2),相當於攻擊者可以偽造有效的MAC標籤。
碰撞攻擊
此處的碰撞攻擊是由於密鑰長度不同導致的。如果密鑰K1是24比特的16進制字符串abcdef，消息M1是12，則返回的是Hash(abcded12)，如果密鑰K2是abcd，消息M2是ef12，則返回的也是Hash(abcded12)，這就發生了碰撞
加後綴
加後綴的方法返回的是Hash(M||K),此時可以抵禦長度擴展攻擊，但是還是會存在碰撞的問題。
設有兩個消息M1,M2,存在碰撞Hash(M1)=Hash(M2),比如在SHA-256中，此時就會存在Hash(M1||K)=Hash(M2||K)
換言之，攻擊者通過如下流程即可發動攻擊：
1.找到兩個碰撞的消息M1,M2
2.請求受害者計算M1哈希的MAC標籤Hash(M1||K)
3.猜測相同的Hash(M2||K),從而偽造一個有效的標籤並破壞MAC的安全性
HMAC
HMAC，即散列消息認證碼（Hash-based message authentication code），是一種通過特別計算方式之後產生的消息認證碼（MAC），使用密碼散列函數，同時結合一個加密密鑰。它可以用來保證資料的完整性，同時可以用來作某個消息的身份驗證。
HMAC從哈希函數構造MAC,這比前面兩種方案都安全，IPSec,SSH,TLS等都使用了HMAC
CMAC
CMAC，Cipher-based Message Authentication Code，它是一種基於分組密碼的消息認證碼算法是基於密碼的MAC，只提供一個分組密碼如AES，就可以構造MAC。
CBC-MAC是最早的CMAC，其用CBC模式對全0初始值IV下的消息M進行加密,並只保留最後一組密文作為消息M的標籤.基本的計算過程就是分別計算C1=E(K,M1),C2=E(K,M2⊗C1),C3=E(K,M3⊗C2)…對M的每個分組只保留最後的Ci，這就是經過CBC-MAC的M的標籤。
其容易被攻擊者構造出新的消息-標籤對。攻擊流程如下
設存在兩個不同的消息M1,M2，對應的標籤分別為T1=E(K,M1),T2=E(K,M2),攻擊者由此可以構造出新的消息-標籤對，即消息M1||(M2⊗T1)的標籤為T2，推導過程如下：
要對M1||(M2⊗T1)生成標籤，則先要計算C1=E(K,M1)=T1,然後計算C2=E(K,(M2⊗T1)⊗T1))=E(K,M2)=T2
由此，攻擊者就從兩個消息-標籤對，且不知道密鑰的情況下構造出了新的消息-標籤對，這意味着攻擊者可以偽造CBC-MAC的標籤，所以CBC-MAC並不安全
AE
AE，Authenticated encryption，即認證加密，這既能實現消息的保密，又能保護消息的真實性，即實現認證。所以一個AE算法既有密碼算法的特性又有MAC的特性。要實現AE，如下圖所示有三種方式：
同時加密和MAC(Encrypt-and-MAC,E&M)
發送方：給定明文P，計算得到密文C=E(K1,P),同時計算得到認證標籤T=MAC(K2,P)，發送C,T
接收方：計算P=D(K1,C)得到P，然後用這個P計算MAC(K2,P),將結果與收到的T比較。如果C或T損壞，認證都會失敗。
這個方案理論上是最不安全的。即使用的是安全的MAC，也有可能從中泄露明文P的信息，因為MAC僅用於確保不可偽造，不能確保隨機。除非用的MAC非常強大，比如偽隨機函數等。
SSH使用的就是這種方案，其用的MAC是HMAC-SHA-256,保證了不會泄露P的信息
先MAC再加密(MAC-then-Encrypt,MtE)
發送方：首先計算T=MAC(K2,P)來保護消息P,然後加密得到C=E(K1,P||T),這裡將明文和標籤一起加密，得到密文。發送方發送C
接收方：解密C，即P||T=D(K1,C)得到P||T,然後通過得到的明文P計算標籤MAC(K2,P)，並與得到的T比較，如果符合，則認證成功。
這種方式隱藏了明文的認證標籤，從而防止標籤泄露明文中的認證信息。
在TLS1.3之前，都是使用該方案。
先加密再MAC(Encrypt-then-MAC,EtM)
發送方：首先加密得到密文C=E(K1,P),然後計算認證標籤T=MAC(K2,C)，將其發送
接收方：使用MAC(K2,C)計算結果與收到的T比較，若相符，則再計算P=D(K1,C),得到明文。
這個方案的優勢在於：1.接收方只需要計算MAC就可知道信息是否損壞，如果損壞就不需要進一步解密了；2.對於攻擊者而言，除非能破解MAC，否則不能同時將C和T發送給接收方獲得解密結果，這使得攻擊者更難向接收方發送惡意數據
所以這種方案是三者之間最安全的，IPSec使用了方案
AES-GCM
除了如上三種，組成起來實現，也有專門的認證加密算法，其可以表示為
加密：AE(K,P)=(C,T),K是密鑰，P是明文，C是密文，T是身份認證標籤
解密：AD(K,C,T)=P,如果C,T至少有一個無效，則AD會返回錯誤，而如果返回明文，則可以確保這個明文是被用正確密鑰加密過的明文。
從認證角度看，其功能與MAC一樣，這意味着想要偽造AD能接收並解密的密文和標記對(C,T)是不可能的
從加密角度看，認證加密比普通密碼算法更安全，因為它只有在標籤有效的情況下才會用密鑰進行解密。這可以防止選擇密文攻擊。
認證加密算法中目前唯一被承認的正式標準就是AES-GCM,其基於AES算法，採用Galois計數器模式（GCM）實施。其示意圖如下
GCM本質上是對CTR模式的改進，集成了一個小組件計算身份認證標籤，其示意如下
AES-GCM容易受到攻擊，包括nonce重放攻擊以及由弱哈希密鑰、短標籤等引發的攻擊。
nonce重放攻擊
這是AES-GCM最大的漏洞。如果用戶在兩次AES-GCM中使用相同的nonce N,攻擊者就可以獲得身份認證密鑰H,繼而可以使用H為任何密文、關聯數據偽造標籤。
其基本代數結構如下
標籤T通過下式計算得到：
上式中的GHASH是一個通用哈希函數，其輸入輸出線性相關
此時如果有用相同nonce計算得到的兩個標籤T1,T2，將其異或可以得到
可以看到，此時AES的部分就消去了
然後利用GHASH的線性特性，攻擊者就可以確定H，從而拿到身份認證密鑰
弱哈希密鑰
GHASH存在重大缺陷，哈希密鑰H的某些取值大大簡化了對GCM認證機制的攻擊，概括來說，如果H的取值屬於某個特定的數學上定義的子群中時，攻擊者可以通過僅僅對前一條消息分組進行變換從而猜測出某個消息的身份認證標籤T。
GHASH的內部結構我們這裡略去，直接到最後一步，此時有
GHASH將消息的長度與Xn異或，將結果乘以H，然後將這個值與AES(K,N||0)異或，從而得到身份認證標籤T
這裡的漏洞在於，如果H=0,則不論Ci為何值都有Xn=0，與消息無關。這意味着，如果H=0,那麼所有的消息都會具有相同的身份認證標籤；而如果H=1,那麼標籤實際上只是密文分組的異或，這樣會導致重新排序的密文分組會有相同的身份認證標籤。
當然，除了H=0,H=1之外，當H取其他值時也會發生異常情況。例如基於5階循環群的例子，設H=10d04d25f93556e69f58ce2f8d035a4,這是一個屬於長度為5的循環的，H的取值滿足H^5=H，那麼對任何5的倍數e，都有
H^e=H
那麼在前面的Xn的表達式中，交換分組Cn（和H相乘）和分組Cn-4（和H^5相乘）不會改變身份認證標籤，這實際上就相當於偽造了。即，攻擊者可在不知道密鑰的情況下，利用這個屬性構造新的消息及其有效認證標籤。
更詳細的分析可以閱讀論文《Cycling Attacks on GCM, GHASH and Other Polynomial MACs and Hashes》
短標籤
實際中AES-GCM通常返回128比特的標籤，不過它可以生成任意長度的標籤，但是長度越小，被偽造的可能性越高。
使用128比特長度時，偽造成功的概率為1/2^128;但是，由於GCM結構內在缺陷，當長度較短時，偽造的概率要大於
1/2^n
比如如果長度為32比特，則成功偽造的概率為1/2^16而不是我們以為的
1/2^32
根據Ferguson的論文指出，對於n比特標籤，成功偽造概率為2^m/
2^n
其中2^m是攻擊者能夠獲得的對應標籤的最長消息的分組數目。
舉個例子，如果使用48比特的標籤去處理4GB的消息（2^28個塊）,
那麼能夠偽造的概率為2^20，這在密碼學中是一個很高的概率了。
更詳細的分析可以閱讀論文《AuthenticationweaknessesinGCM》
RSA
RSA加密算法是一種非對稱加密算法，在公開密鑰加密和電子商業中被廣泛使用。RSA是由羅納德·李維斯特（Ron Rivest）、阿迪·薩莫爾（Adi Shamir）和倫納德·阿德曼（Leonard Adleman）在1977年一起提出的.RSA的工作原理就是創建一個被稱為陷門置換的數學對象。陷門置換描述的是符合下述性質的函數：
將數字x變換為同一範圍內的數字y，除非知道私鑰，否則不能從y計算得到x，這個私鑰就稱為陷門.
陷門置換
陷門置換是RSA的核心。給定模數n和公開指數e，RSA陷門置換將群Zn中的數x通過y= x^e mod n變換為群Zn中的另一個數y。
在加密時，n和e就是RSA的公鑰
為了能夠從y計算出x，則需要另一個數d，通過如下計算得到x
d就是陷門，也是RSA私鑰的一部分，d也被稱為秘密指數
d並不能任意取值，其必須滿足
這樣才能得到
這裡需要注意，我們用的是模φ(n)而不是模n
φ(n)=(p-1)(q-1)，這個數對RSA的安全性至關重要，如果攻擊者能從模數n中求出φ(n)，就等價於破解了RSA。這是因為如果知道φ(n)，在計算e模φ(n)的逆，就可以得到d。為此，p和q也應該保密，因為φ(n)可以由其計算得到
整個RSA的安全級別取決於n的大小、p與q的選擇、陷門置換的應用；如果n太小，則容易對其分解，從而泄露私鑰；如果p與q太小或者太接近，則容易從n中確定出相應取值；陷門置換不應該被直接用於簽名或加密
陷門置換的誤用
在教科書中的RSA介紹中，通常會看到誤用陷門置換的情況，其被直接用於加密或者簽名了。即，RSA中的明文只是要加密的消息。這看起來沒問題，實際上存在很大的風險。
加密
這種教科書式的RSA加密是確定性的，即對同一明文加密兩次，得到的密文是相同的。除此之外，更大的問題是，當給定兩個密文y1=x1^e mod n和
y2=x2^e mod n時，攻擊者可以通過將其相乘，得到明文x1xx2的密文：
這個結果就是消息x1xx2 mod n對應的密文，這意味着，攻擊者可以從兩個RSA密文中構造出新的有效密文。這種弱點我們稱之為擴展性風險（安全的密碼應該確保只有在知道x1,x2時才能得到兩者相乘的密文，如果只知道y1，y2是不能夠得到的）
為了使RSA不可擴展，提出了OAEP，其中密文由待加密消息和一些padding組成,他們一起組成了RSA-OAEP。
OAEP的示意圖如下
圖中， n是RSA模數的位數，k0和k1是協議中的固定整數。m是n-k0-k1位長的明文消息，G和H是隨機預言，如加密散列函數，⊕是異或運算。
編碼過程包括如下步驟：
-
用 k1 位長的 0 將消息填充至 n – k0 位的長度。
-
隨機生成 k0 位長的串 r
-
用 G 將k0 位長的 r 擴展至 n – k0 位長。
-
X = m00…0 ⊕ G(r)
-
H 將 n – k0 位長的 X 縮短至 k0 位長。
-
Y = r ⊕ H(X)
-
輸出為 X || Y，在圖中 X 為最左邊的塊，Y 位最右邊的塊。
隨後可以使用 RSA 加密編碼的消息
解碼過程包括如下步驟：
-
恢復隨機串 r 為 Y⊕H(X)
-
恢復消息 m00…0 為 X ⊕ G(r)
簽名
教科書中的RSA簽名同樣是簡化過的，通過直接計算y = x^d mod n對消息x進行簽名。這雖然簡單，便於初學者理解，但是其存在簽名被偽造的風險。
舉個最簡單的例子，因為有
0^d mod n=0
1^d mod n=1
(n-1)^d mod n = n-1
那麼攻擊者一直可以在不知道d的情況下偽造0，1，n-1的簽名
更嚴重的攻擊手段我們稱之為盲簽名攻擊，即消息M不會被受害者主動簽名，但是攻擊者可以讓M被受害者簽名。攻擊流程如下
1.攻擊者找到某個值R，R^eM mod n是受害者會簽名的一條信息，此時得到的簽名記做S=(R^eM)^d mod n，現在的問題就是攻擊者怎樣能得到M的簽名，即M^d
2.推導如下
且
所以有
S=(ReM)^d
RM^d
為了得到M^d,將S除R即可
為了避免這種攻擊，提出了RSA概率簽名方案PSS,PSS之於RSA簽名等同於OAEP之於RSA加密，它能讓簽名更安全，其流程比較複雜，基本示意圖如下
此外還有更簡單的簽名方案，即FDH，全域哈希。
Bellcore攻擊
Bellcore攻擊屬於錯誤攻擊的一種，其迫使算法的一部分執行不當，產生錯誤的結果，將其與正確結果相比較，從而獲得關於算法內部值的信息。
Bellcore適用於使用中國剩餘定理的確定性的RSA簽名方案。
由相關基礎知識，我們有
其中
假設攻擊者在就按xq時產生錯誤，得到錯誤值xq』，繼續使用xq『並得到相應的x』。那麼攻擊者現在就可以計算正確的簽名x和錯誤的簽名x『的差，並由此分解模數n：
由上式，x-x’是p的倍數，即p是x-x’的除數，由於p也是n的除數，所以n和x-x’的最大公約數是p，即
然後就可以計算出q=n/p以及d，從而破解RSA簽名
共享模數n
我們直接舉個例子。
設攻擊者的私鑰為(n,d1),受害者的私鑰為(n,d2)，受害者公鑰為(n,e2),此時攻擊者知道n，不知道p和q，所以不能從公開指數e2計算秘密指數d2。那麼怎麼從d中計算出p和q呢？
我們知道d和e滿足
雖然我們不知道d或φ(n)，但是我們可以計算出kφ(n)=ed-1
根據歐拉定理，對於任何一個與n互素的數a，有a^(φ(n))=1 mod n，所以，對模數n，有下式：
由於kφ(n)是偶數，所以可以寫成2^st,所以可以把
寫成如下形式
式子中的x可以通過kφ(n)計算得到
x^2-1=（x-1）(x+1)，這意味
x^2-1可以被n整除，即x-1或x+1二者必有其一與n有相同的因數，從而可以算出n的因數,從而攻破RSA。
參考
1.//link.springer.com/content/pdf/10.1007%2F0-387-34805-0_39.pdf
2.《foundations of cryptography》
3.//link.springer.com/chapter/10.1007/3-540-68697-5_1
4.//eprint.iacr.org/2006/043.pdf
5.//link.springer.com/chapter/10.1007/978-3-540-74143-5_2
6.//www.cs.ucdavis.edu/~rogaway/papers/ae.pdf
7.//link.springer.com/chapter/10.1007/978-3-642-34047-5_13
9.//competitions.cr.yp.to/caesar.html
10.//www.sciencedirect.com/science/article/abs/pii/S1574013715300290
更多網安技能的在線實操練習，請點擊這裡>>
