點(diǎn)亮信號(hào)

Nina Bindel, 2022.9.23  翻譯：丁若禺

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

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

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

密鑰交換協(xié)議是互聯(lián)網(wǎng)安全的基石。密鑰交換是為了使兩方(Alice和Bob)完成計(jì)算來得到一個(gè)共享密鑰,。這個(gè)密鑰接下來會(huì)用于對(duì)稱加密,。本篇博客中我們會(huì)介紹最近提出的針對(duì)一種密鑰交換協(xié)議的攻擊背后的核心思想。具體來說,，我們將會(huì)討論在密鑰復(fù)用情況下,，針對(duì)密鑰交換協(xié)議的“信號(hào)泄漏攻擊”，這些協(xié)議基于錯(cuò)誤學(xué)習(xí)問題(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”已經(jīng)被ESORICS 2022（丹麥哥本哈根,，2022.9.26-30）接收，并且會(huì)在9月26號(hào)以線上參加的形式進(jìn)行匯報(bào),。這篇論文同樣也在ePrint上(https://eprint.iacr.org/2022/131),。

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

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

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

讓我們看個(gè)例子?，F(xiàn)在s_B = 1+2x-3x^2-x^213+4x^317-3x^511,，假設(shè)敵手想找出s_B的第3個(gè)系數(shù),，即-3。為了恢復(fù)該系數(shù),，敵手給Bob發(fā)送p_A = 0,，然后把信號(hào)中第3個(gè)值存起來，它對(duì)應(yīng)于s_B的第3個(gè)系數(shù),?？聪旅孢@張圖，我們知道這個(gè)信號(hào)值等于0,。然后敵手發(fā)送p_A = 1,，然后再把第3個(gè)信號(hào)值存起來，這次它還是0,。如下圖中所示,，信號(hào)值在p_A = 1800左右時(shí)第一次從0變到1，在p_A = 4000左右時(shí)從1變0,。敵手一直增大p_A直到p_A = 16384,，信號(hào)值會(huì)有6次明顯的翻轉(zhuǎn)。所以Bob私鑰s_B的第3個(gè)系數(shù)的絕對(duì)值等于3,。敵手需要對(duì)所有的系數(shù)都這樣做,，通常會(huì)有512或1024個(gè)系數(shù)。除此之外,，敵手需要做一套類似的過程來恢復(fù)系數(shù)的正負(fù)號(hào),，例如上面例子里第3個(gè)系數(shù)是負(fù)的。

放大圖中其中一個(gè)明顯的翻轉(zhuǎn)可以看出,，對(duì)于一些p_A,，信號(hào)值實(shí)際上是波動(dòng)的。這是由隨機(jī)誤差e_B引起的,?；谶@些波動(dòng)，我們可以區(qū)分穩(wěn)定區(qū)域（下圖中藍(lán)色和黃色區(qū)域）和非穩(wěn)定區(qū)域（下圖中波動(dòng)的白線）,。為了正確統(tǒng)計(jì)穩(wěn)定和不穩(wěn)定區(qū)域的數(shù)量,，并且能夠正確記錄明顯的翻轉(zhuǎn)次數(shù)，其實(shí)不需要要求發(fā)送q個(gè)不同p_A,。與之前的攻擊相反,，Bindel,、Stebila和Veitch表明,，只要確保在每個(gè)穩(wěn)定區(qū)域至少收集一個(gè)信號(hào)值，在每個(gè)不穩(wěn)定區(qū)域最多收集一個(gè)信號(hào)值,，那就足夠恢復(fù)可能的私鑰系數(shù)的絕對(duì)值了,。下面的圖片展示了一個(gè)例子,，假定私鑰系數(shù)的絕對(duì)值最大為3，把p_A設(shè)為圖中綠色點(diǎn)表示的值就足夠確定私鑰系數(shù)是否等于1,，2還是3,。這樣一來就可以把p_A需要的值從98310個(gè)減少到只有1266個(gè)，并且足夠恢復(fù)DXL密鑰交換中Bob使用的私鑰s_B,。

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

這種對(duì)信號(hào)泄漏的新解釋不僅減少了p_A所需值的數(shù)量（因此使攻擊更有效,、更實(shí)用），而且還使我們更容易發(fā)現(xiàn)方案是否能被這種攻擊破解,。

最后,，必須要提到的是，信號(hào)泄漏攻擊可以用認(rèn)證密鑰交換協(xié)議的通用構(gòu)造來防護(hù),。然而,，為了達(dá)到更好的效率，我們更希望直接從一個(gè)困難問題（如LWE問題）來構(gòu)造密鑰交換,。因此,，嘗試構(gòu)造這種“直接的”認(rèn)證密鑰交換協(xié)議經(jīng)常會(huì)失敗。針對(duì)信號(hào)泄漏攻擊的最新改進(jìn)再次提醒我們,，在嘗試這種構(gòu)造時(shí),，不要低估信號(hào)泄漏攻擊的威力。