RSA-CRT密碼防御算法的故障注入攻擊1

孔凡玉，喬詠，劉蓬濤，劉曉東，周大水

（1. 山東大學網絡信息安全研究所，山東 濟南 250100；2. 中標軟件有限公司，北京 100190；3. 山東政法學院網絡空間安全學院，山東 濟南 250014）

1 引言

自Diffie和Hellman提出第一個公鑰密碼體制——Diffie-Hellman密鑰協商協議[1]以來，公鑰密碼體制在數字簽名、密鑰協商等方面發揮了越來越重要的作用。RSA密碼算法[2]是最早提出的幾個公鑰密碼體制之一，其安全性基于大整數分解困難問題，可用于公鑰加密和數字簽名等功能，是幾十年以來應用最廣泛的公鑰密碼體制之一。近年來，基于橢圓曲線的SM2密碼算法標準和美國的ECDSA數字簽名標準逐漸推廣，但在IPSec協議、TLS/SSL協議以及瀏覽器等互聯網環境中，RSA密碼體制的實際應用依然很廣泛，其安全性分析非常重要。

長期以來，密碼攻擊者主要從數學計算的角度分析一個密碼算法的安全性，如通過大整數分解等方法攻擊RSA密碼體制。但是，Kocher等學者提出的側信道攻擊[3-5]拓展了傳統密碼分析的思路，能夠利用密碼算法實際執行時泄露的運算時間、電量消耗等信息恢復部分甚至整個秘密密鑰。被動式的側信道攻擊通過測量密碼運算的執行時間、電量消耗等信息分析密鑰，不影響密碼運算的正常執行；主動式的側信道攻擊則可以改變密碼運算的執行過程，使其產生對密碼分析有用的信息，故障注入攻擊是一種主動式攻擊方法。

Dan Boneh首次提出了故障注入攻擊[4]的概念，并提出了針對RSA密碼的中國剩余定理實現（RSA-CRT）的攻擊方法：當其中一個模冪運算發生錯誤時，可以通過錯誤的RSA簽名結果恢復 RSA私鑰。Shamir[6]通過在 RSA運算過程中引入一個隨機數r來判斷兩次模冪的結果是否存在錯誤，如果檢測到錯誤，則只返回錯誤提示，不返回錯誤的RSA簽名值，因此避免攻擊者使用錯誤的簽名值恢復私鑰。Joye等學者[7]進一步改進、細化了Shamir的方法，使用dp和dq替代私鑰指數d。Aumüller等[8]指出，在Shamir的方法中，如果計算兩次模冪的過程中不出錯，而是在中國剩余定理的結果合成運算中注入錯誤，使其中一個模冪結果出錯，則仍然能夠成功攻擊。Yen等[9]詳細分析了Shamir的方法和Aumüller的改進方法，對RSA-CRT的故障注入攻擊方法進行了系統的論述。

在FDTC 2014會議上，Rauzy和Guilley[10]對基于檢測和基于感染計算的兩類故障注入防御算法進行了分析，并提出了多個抵抗故障注入攻擊的算法。2016年，Battistello和Giraud[11]對Rauzy和 Guilley提出的感染計算的防御算法進行了分析，證明其不能抵抗故障注入攻擊。關于RSA-CRT密碼算法的故障注入攻擊和防御措施，可以參見相關參考文獻[12-22]。

本文針對Rauzy和Guilley提出的兩個基于檢測的 RSA-CRT安全防御算法，進行故障注入攻擊，在 RSA密碼運算過程中注入一個永久性錯誤，使防御算法不能檢測到錯誤的發生，然后利用錯誤的RSA簽名運算結果，計算出RSA私鑰。此攻擊表明，Rauzy和Guilley的RSA安全實現算法不能抵抗故障注入攻擊。

2 RSA-CRT密碼算法和故障注入攻擊

本節介紹 RSA密碼算法的中國剩余定理實現，以及針對 RSA-CRT實現的故障注入攻擊和防御措施。

2.1 RSA密碼和中國剩余定理實現

RSA密碼算法[2]是基于整數分解困難問題的公鑰密碼體制，其公鑰包括模數N和公鑰指數e，其中N=pq，為了保證安全性，要求p和q為512 bit以上長度的素數。RSA密碼的私鑰為p、q和私鑰指數d，滿足e·d≡1 modφ(N)，其中，φ(N)=(p–1)·(q–1)是歐拉函數。

RSA加密或驗證簽名的過程，即計算模冪MemodN；RSA解密或簽名的過程，即計算模冪MdmodN。為了提高加密和驗簽的速度，一般選擇比較短的公鑰指數e，如e=65 537，私鑰指數d是與模N長度相同或接近的整數，RSA私鑰運算S=MdmodN的時間復雜性為O(log3(N))。

采用中國剩余定理可以提高 RSA私鑰運算的速度（簡稱 RSA-CRT），即先計算兩個模冪Sp=Mdpmodp和Sq=Mdqmodq，然后組合成最后的計算結果。

其中，dp=dmod (p–1)，dq=dmod (q–1)。由于素數p和q的長度為模N的一半，因此每次Sp或Sq的計算量約為計算S=MdmodN的所以采用中國剩余定理能夠提高約4倍速度。

2.2 RSA-CRT密碼的故障注入攻擊

當RSA-CRT運算中的一個模冪運算Sp=Mdpmodp發生錯誤，即得到錯誤的模冪結果S′p，那么最后的RSA-CRT運算結果為

根據RSA-CRT的正確運算結果S和錯誤結果S′，可以通過歐幾里得算法計算出素數q，即計算[4]

或者由 RSA-CRT的錯誤結果S′，直接計算出素數q，即計算

存在兩大類抵抗故障注入攻擊的RSA-CRT實現算法：一類是 Shamir[6]提出的基于錯誤檢測的方法，隨機選擇一個隨機數r，用于盲化素數p和q，先計算模pr和qr的模冪，然后通過模r運算判斷兩次模冪的結果是否存在錯誤，如果判斷沒有錯誤，則正常計算并返回結果RSA簽名S，否則，返回計算失??；另一類是基于感染計算的方法[12]，即不管是否存在模冪運算錯誤，都返回RSA簽名結果，但利用錯誤的RSA簽名結果不能計算出秘密素數p或q。文獻[10,17]對 RSA-CRT密碼的故障注入攻擊和防御方法進行了詳細論述。

3 Rauzy等提出的RSA-CRT密碼防御算法

Rauzy和Guilley在FDTC 2014會議上的論文[10]系統地分析了基于檢測和基于感染計算的兩類故障注入防御算法，指出這兩類算法之間可以通過一定的方法相互轉化。Rauzy和Guilley[10]認為，基于感染計算的抵御算法比基于檢測的算法更好，因為它避免了分支判斷，減少了故障注入的可能性，同時提出了多個抵抗故障注入攻擊的算法。但 Battistello和Giraud[11]對Rauzy和Guilley提出的兩個感染計算的防御算法進行了分析，表明其不能抵抗故障注入攻擊。

本文主要對Rauzy和Guilley提出的基于檢測的防御算法[10]進行分析，一個被稱為“一種直接的防御算法”（原文中的Algorithm 9），另一個是改進的Shamir方法（原文中的Algorithm 10）。下面分別對這兩個算法進行簡要描述。

3.1 一種直接的RSA-CRT防御算法

Rauzy和Guilley提出的“一種直接的防御算法”（參考文獻[10]中的Algorithm 9）是對模冪Sp、Sq和 CRT綁定結果均進行驗證，并被證明能夠抵抗一階故障注入攻擊，其算法描述如下。

算法1一種直接的RSA-CRT防御算法[10]

輸入：消息M，密鑰（p,q,dp,dq,iq）

輸出：RSA簽名值MdmodN，或返回失敗

Begin

Step 1Sp=Mdpmodφ(p)modp；

Step 2ifSp≠Mdpmodpthen return error；

Step 3Sq=Mdqmodφ(q)modq；

Step 4ifSq≠Mdqmodqthen return error；

Step 5S=CRT(Sp,Sq)=Sq+q·(iq·(Sp–Sq) modp)；

Step 6if ((S≠Spmodp) or (S≠Sqmodq))then return error；

Step 7returnS；

End

3.2 改進的Shamir防御算法

Rauzy和Guilley提出的改進的Shamir方法（參考文獻[10]中的 Algorithm 10）對原來的Shamir方法進行了修改，并被認為能夠抵抗故障注入攻擊，其算法描述如下。

算法2RSA-CRT實現的改進Shamir防御算法[10]

輸入：消息M，密鑰（p,q,dp,dq,iq）

輸出：RSA簽名值MdmodN，或返回失敗

Begin

Step 1選擇一個小的隨機數r；

Step 2p′=p·r；

Step 3q′=q·r；

Step 4if ((p′≠0 modp) or (q′≠0 modq))then return error；

Step 5S′p=Mdmodφ(p′)modp′；

Step 6S′q=Mdmodφ(q′)modq′；

Step 7ifS′p≠S′qmodrthen return error；

Step 8Sp=S′pmodp；

Step 9Sq=S′qmodq；

Step 10S= CRT(Sp,Sq) =Sq+q· (iq· (Sp–Sq)modp)；

Step 11if ((S≠S′pmodp) or (S≠S′qmodq))then return error；

Step 12returnS；

End

4 針對Rauzy等的RSA-CRT防御算法的攻擊

Yen等[9]將故障注入攻擊中發生的錯誤分為兩類：一類是暫時性的錯誤，即僅在這一次運算時某個數據臨時出錯，之后恢復原來的正確值；另一類是永久性的錯誤，即在某個時間點修改了某個數據后，這個錯誤值將一直保持到整個RSA運算過程結束。對RSA-CRT密碼算法的故障注入攻擊方法，包括在 RSA運算過程中的哪個時間點注入錯誤，以及注入的是臨時性錯誤還是永久性錯誤。根據注入錯誤的次數，可以分為一階故障注入攻擊、二階故障注入攻擊等，分別表示攻擊者能夠在RSA運算過程中注入一個、兩個以及更多的錯誤。

本文主要對Rauzy和Guilley提出的基于檢測的防御算法的故障注入攻擊，采用了一階故障注入攻擊方法，產生的是一個永久性錯誤，并能夠順利通過防御算法的錯誤檢測流程，從而導致產生、輸出一個錯誤的RSA簽名結果，以用于求解 RSA私鑰。下面分別對這兩個算法的攻擊方法進行描述。

4.1 對算法1的故障注入攻擊

Rauzy和Guilley提出的“一種直接的防御算法”（算法1），分別在Step 2和Step 4對模冪Sp、Sq結果進行錯誤檢測，在Step 5進行CRT組合運算，然后在Step 6檢測CRT組合運算結果是否有錯誤。

本文提出的故障注入攻擊方法是在Step 5計算過程中，對Sp注入一個永久性錯誤，攻擊方法描述如下。

攻擊方法1針對算法1的故障注入攻擊

輸入：消息M，密鑰（p,q,dp,dq,iq）

輸出：RSA簽名值MdmodN，或返回失敗

Begin

Step 1Sp=Mdpmodφ(p)modp；

Step 2ifSp≠Mdpmodpthen return error；

Step 3Sq=Mdqmodφ(q)modq；

Step 4ifSq≠Mdqmodqthen return error；

Step 5對Sp注入一個永久性錯誤，即將其修改為S′p，計算：

Step 6if ((S′≠S′pmodp) or (S′≠Sqmodq))then return error；

Step 7returnS′；

End

下面說明故障注入攻擊方法1能夠成功恢復RSA私鑰。

首先，本文的攻擊方法不改變 Step1～Step4的運算，因此Step1～Step4能夠順利執行，不會返回錯誤。然后，在Step 5中，對Sp注入一個永久性錯誤，即將其修改為S′p，并計算S′=CRT(S′p,Sq)。因為S′p是一個永久性錯誤，CRT組合運算只是按照上面的運算公式計算S′，其結果S′依然滿足S′=S′pmodp和S′=Sqmodq，因此 Step 6 并不能檢測到S′p的錯誤，Step 7會返回一個錯誤的RSA簽名值S′。根據錯誤的RSA簽名值S′，容易計算出素數q=GCD((S′e–M) modN,N)，從而恢復 RSA私鑰。

4.2 對算法2的故障注入攻擊

Rauzy和Guilley提出的改進的Shamir方法（算法2），在Step 4檢測p′和q′的正確性，在Step 7 檢測模冪S′p、S′q的正確性，在 Step 10 進行 CRT組合運算，然后在Step 11檢測CRT組合運算結果是否存在錯誤。

本文提出的故障注入攻擊方法是在Step 8計算過程中，對S′p注入一個永久性錯誤，攻擊方法描述如下。

攻擊方法2針對算法2的故障注入攻擊

輸入：消息M，密鑰（p,q,dp,dq,iq）

輸出：RSA簽名值MdmodN，或返回失敗

Begin

Step 1選擇一個小的隨機數r；

Step 2p′=p·r；

Step 3q′=q·r；

Step 4if ((p′≠0 modp) or (q′≠0 modq)) then return error；

Step 5S′p=Mdmodφ(p′)modp′；

Step 6S′q=Mdmodφ(q′)modq′；

Step 7ifS′p≠S′qmodrthen return error；

Step 8對S′p注入一個永久性錯誤，即將其修改為S′*p，計算：S*p=S′*pmodp；

Step 9Sq=S′qmodq；

Step 10S*=CRT(S*p,Sq)=Sq+q· (iq· (S*p–Sq)modp)；

Step 11if ((S*≠S′*pmodp) or (S*≠S′qmodq))then return error；

Step 12returnS*；

End

下面說明故障注入攻擊方法2能夠成功恢復RSA私鑰。

首先，本文的攻擊方法不改變 Step1～Step7的運算過程，因此不會返回錯誤。然后，在Step 8中，對S′p注入一個永久性錯誤，即將其修改為S′*p，并計算出一個錯誤的模冪值S*p=S′*pmodp。在Step 10中，CRT組合運算將錯誤的模冪S*p和正確的模冪Sq進行組合計算，得到錯誤的S*。因為在Step 8中，S*p是由S′*p模p計算出來的，因此 Step 11 中的S*滿足S*=S′*pmodp和S*=S′qmodq。所以，Step 12會返回一個錯誤的RSA簽名值S*。根據錯誤的RSA簽名值S*，容易計算出素數q=GCD((S*e–M) modN,N)，從而恢復RSA私鑰。

不管在硬件還是軟件實現中，Sp和S′p等大整數都是以數組的形式存儲在內存或寄存器中，如在Intel CPU中，可以是以32或64比特為單位的數組進行存儲。所以，本文提出的故障注入攻擊，只要對Sp和S′p等數據的某一個32或64比特存儲單位進行修改，就可以實現相應的故障注入攻擊。

5 結束語

故障注入攻擊等側信道攻擊方法表明，一個密碼算法的正確、安全實現與其安全性密切相關。針對 RSA-CRT密碼實現的故障注入攻擊是一種很強大的攻擊技術，僅需要一次模冪出現錯誤即可攻擊成功，因此必須采用安全的實現算法以抵抗故障注入攻擊。

本文對Rauzy和Guilley提出的兩個故障注入攻擊算法進行了分析，提出了一階故障注入攻擊算法，表明這兩個算法不能抵抗故障注入攻擊。如何在抵抗故障注入攻擊的同時，提高RSA-CRT密碼實現的速度，并分析在手機、物聯網、車聯網等移動環境下的實際攻擊技術，是下一步需要研究的方向。