點(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ì)算來(lái)得到一個(gè)共享密鑰。這個(gè)密鑰接下來(lái)會(huì)用于對(duì)稱加密。本篇博客中我們會(huì)介紹最近提出的針對(duì)一種密鑰交換協(xié)議的攻擊背后的核心思想。具體來(lái)說(shuō)，我們將會(huì)討論在密鑰復(fù)用情況下，針對(duì)密鑰交換協(xié)議的“信號(hào)泄漏攻擊”，這些協(xié)議基于錯(cuò)誤學(xué)習(xí)問(wèn)題(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)單來(lái)說(shuō)，這些私鑰是整數(shù)，并且在生成元為g的群上。然后他們分別用自己的私鑰計(jì)算g的s_A次冪和g的s_B次冪發(fā)送給對(duì)方，傳輸?shù)木褪撬麄兊墓€p_A和p_B。他們得到共享的密鑰只需要用對(duì)方的公鑰計(jì)算自己的私鑰次冪。這個(gè)協(xié)議的安全性基于離散對(duì)數(shù)問(wèn)題。也就是，即使p_A和p_B是公開的，也不可能根據(jù)p_A和p_B來(lái)算出s_A和s_B。雖然這對(duì)我們目前的計(jì)算機(jī)來(lái)說(shuō)確實(shí)是困難的，但是對(duì)于大型容錯(cuò)量子計(jì)算機(jī)，離散對(duì)數(shù)問(wèn)題將會(huì)被解決。所以在量子計(jì)算機(jī)時(shí)代，Diffie-Hellmann-Merkle（DHM）密鑰交換以及一些其他的密碼算法將會(huì)被破解（可以訪問(wèn)這個(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í)問(wèn)題（LWE）的密鑰交換協(xié)議。像之前一樣，Alice和Bob先選擇自己的私鑰。這次私鑰是具有小系數(shù)的多項(xiàng)式，如s_B = 1+ 2x - 3x^2- x^213 + 4x^317 - 3x^511。通過(guò)用一個(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)，之后被用來(lái)攻擊Ding、Xie和Lin三人提出的基于LWE的DXL密鑰交換。其思想是，一個(gè)偽裝成誠(chéng)實(shí)用戶的敵手發(fā)送壞的p_A。具體來(lái)說(shuō)，在某個(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ì)值的兩倍。因此，通過(guò)跟蹤信號(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è)值存起來(lái)，它對(duì)應(yīng)于s_B的第3個(gè)系數(shù)。看下面這張圖，我們知道這個(gè)信號(hào)值等于0。然后敵手發(fā)送p_A = 1，然后再把第3個(gè)信號(hào)值存起來(lái)，這次它還是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ù)。除此之外，敵手需要做一套類似的過(guò)程來(lái)恢復(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。這樣一來(lái)就可以把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)造來(lái)防護(hù)。然而，為了達(dá)到更好的效率，我們更希望直接從一個(gè)困難問(wèn)題（如LWE問(wèn)題）來(lái)構(gòu)造密鑰交換。因此，嘗試構(gòu)造這種“直接的”認(rèn)證密鑰交換協(xié)議經(jīng)常會(huì)失敗。針對(duì)信號(hào)泄漏攻擊的最新改進(jìn)再次提醒我們，在嘗試這種構(gòu)造時(shí)，不要低估信號(hào)泄漏攻擊的威力。