點亮信號

Nina Bindel, 2022.9.23  翻譯：丁若禺

本文為合作者Nina Bindel 博士介紹我們最新工作的博文，發表在 Nina Bindel 供職的SandBox AQ公司的Blog上（https://www.sandboxaq.com/post/lighting-the-signal），由Nina Bindel授權翻譯刊載。

------------------------------------

本圖片由OpenAI DALL·E 2使用以下句子生成：“drawing of a female scientist breaking code by lighting the signal as van gogh”

密鑰交換協議是互聯網安全的基石。密鑰交換是為了使兩方(Alice和Bob)完成計算來得到一個共享密鑰。這個密鑰接下來會用于對稱加密。本篇博客中我們會介紹最近提出的針對一種密鑰交換協議的攻擊背后的核心思想。具體來說，我們將會討論在密鑰復用情況下，針對密鑰交換協議的“信號泄漏攻擊”，這些協議基于錯誤學習問題(Learning with Errors, LWE)。

由Yue Qin, Ruoyu Ding, Chi Cheng, Nina Bindel, Yanbin Pan和Jintai Ding共同撰寫的論文“Light the Signal: Optimization of Signal Leakage Attacks against LWE-Based Key Exchange”已經被ESORICS 2022（丹麥哥本哈根，2022.9.26-30）接收，并且會在9月26號以線上參加的形式進行匯報。這篇論文同樣也在ePrint上(https://eprint.iacr.org/2022/131)。

最早也是最簡單的密鑰交換協議之一是在1976年由Diffe, Hellman還有（在另一個獨立工作里）Merkle設計的。他們的想法是Alice和Bob各自選擇自己的私鑰s_A和s_B。簡單來說，這些私鑰是整數，并且在生成元為g的群上。然后他們分別用自己的私鑰計算g的s_A次冪和g的s_B次冪發送給對方，傳輸的就是他們的公鑰p_A和p_B。他們得到共享的密鑰只需要用對方的公鑰計算自己的私鑰次冪。這個協議的安全性基于離散對數問題。也就是，即使p_A和p_B是公開的，也不可能根據p_A和p_B來算出s_A和s_B。雖然這對我們目前的計算機來說確實是困難的，但是對于大型容錯量子計算機，離散對數問題將會被解決。所以在量子計算機時代，Diffie-Hellmann-Merkle（DHM）密鑰交換以及一些其他的密碼算法將會被破解（可以訪問這個博客(https://www.sandboxaq.com/post/historic-milestone-in-cybersecurity-nist-unveils-new-pqc-suite-of-algorithms)以了解更多關于量子威脅和在量子時代維護安全的方法）。

與DHM有許多相似性的備用協議是基于所謂的錯誤學習問題（LWE）的密鑰交換協議。像之前一樣，Alice和Bob先選擇自己的私鑰。這次私鑰是具有小系數的多項式，如s_B = 1+ 2x - 3x^2- x^213 + 4x^317 - 3x^511。通過用一個公開的多項式a（類似上面的生成元g）和他們各自的私鑰，他們分別計算公鑰p_A和p_B并發送給對方。然后他們就可以計算兩個近似相等的h_A和h_B。為了能算出一樣的共享密鑰，Bob需要發送額外的信息。這個信息就是信號w_B。信號由一系列0和1組成——個數和私鑰多項式系數的個數一樣多。信號可以與h_A或者h_B作為函數KeyF的輸入，輸出是最后的共享密鑰。

不幸的是，如果Bob每次都重用他的私鑰，那么這個額外的信息會允許攻擊者恢復s_B。這種攻擊叫做密鑰復用下的信號泄漏攻擊，它首先被Fluhrer發現，之后被用來攻擊Ding、Xie和Lin三人提出的基于LWE的DXL密鑰交換。其思想是，一個偽裝成誠實用戶的敵手發送壞的p_A。具體來說，在某個公共參數為q的情況下, 敵手發送的不是多項式，而是q個不同的整數, 即p_A = 0，p_A = 1，…，p_A = q - 1。根據信號的計算方式，事實上這樣做會導致信號的每一位會在0和1之間翻轉，其頻率是相應的私鑰系數絕對值的兩倍。因此，通過跟蹤信號在p_A變化時的行為，對手可以了解到私鑰的系數大小。

讓我們看個例子。現在s_B = 1+2x-3x^2-x^213+4x^317-3x^511，假設敵手想找出s_B的第3個系數，即-3。為了恢復該系數，敵手給Bob發送p_A = 0，然后把信號中第3個值存起來，它對應于s_B的第3個系數。看下面這張圖，我們知道這個信號值等于0。然后敵手發送p_A = 1，然后再把第3個信號值存起來，這次它還是0。如下圖中所示，信號值在p_A = 1800左右時第一次從0變到1，在p_A = 4000左右時從1變0。敵手一直增大p_A直到p_A = 16384，信號值會有6次明顯的翻轉。所以Bob私鑰s_B的第3個系數的絕對值等于3。敵手需要對所有的系數都這樣做，通常會有512或1024個系數。除此之外，敵手需要做一套類似的過程來恢復系數的正負號，例如上面例子里第3個系數是負的。

放大圖中其中一個明顯的翻轉可以看出，對于一些p_A，信號值實際上是波動的。這是由隨機誤差e_B引起的。基于這些波動，我們可以區分穩定區域（下圖中藍色和黃色區域）和非穩定區域（下圖中波動的白線）。為了正確統計穩定和不穩定區域的數量，并且能夠正確記錄明顯的翻轉次數，其實不需要要求發送q個不同p_A。與之前的攻擊相反，Bindel、Stebila和Veitch表明，只要確保在每個穩定區域至少收集一個信號值，在每個不穩定區域最多收集一個信號值，那就足夠恢復可能的私鑰系數的絕對值了。下面的圖片展示了一個例子，假定私鑰系數的絕對值最大為3，把p_A設為圖中綠色點表示的值就足夠確定私鑰系數是否等于1，2還是3。這樣一來就可以把p_A需要的值從98310個減少到只有1266個，并且足夠恢復DXL密鑰交換中Bob使用的私鑰s_B。

最近，Qin、Ding、Cheng、Bindel、Pan和Ding可以把p_A需要的值降低到29個。最新的這個改進的想法是更加巧妙地選擇p_A的值。從上圖可以看出，實際上紅色表示的這三個值就足以唯一地確定私鑰系數的絕對值。這一想法是確定與可能的私鑰系數絕對值唯一對應的碼字。例如，如果碼字k_1-k_2-k_3 = 0-1-1，對應私鑰系數的絕對值就是1。如果碼字是1-1-0或者1-0-1，我們就可以知道絕對值分別是2或3。

這種對信號泄漏的新解釋不僅減少了p_A所需值的數量（因此使攻擊更有效、更實用），而且還使我們更容易發現方案是否能被這種攻擊破解。

最后，必須要提到的是，信號泄漏攻擊可以用認證密鑰交換協議的通用構造來防護。然而，為了達到更好的效率，我們更希望直接從一個困難問題（如LWE問題）來構造密鑰交換。因此，嘗試構造這種“直接的”認證密鑰交換協議經常會失敗。針對信號泄漏攻擊的最新改進再次提醒我們，在嘗試這種構造時，不要低估信號泄漏攻擊的威力。