Technology

September 23, 2022

Picture generated with OpenAI's DALL·E 2 using the following sentence "drawing of a female scientist breaking code by lighting the signal as van gogh"

By Nina Bindel

Key exchange is one of the fundamental building blocks that Internet security is built upon. The goal of key exchange is for two parties – often called Alice and Bob – to do computations such that at the end they agree on a shared secret key. This key is then used to encrypt messages using symmetric encryption. In this post we will explain the core idea behind a recently published attack against one kind of key exchange protocol. Specifically, we will discuss “signal leakage attacks” against key exchange protocols, which are based on the Learning with Errors (LWE) problem under “key re-use”.

*The respective paper “Light the Signal: Optimization of Signal Leakage Attacks against LWE-Based Key Exchange” by Yue Qin, Ruoyu Ding, Chi Cheng, Nina Bindel, Yanbin Pan, and Jintai Ding has been accepted at **ESORICS 2022** (September 26-30, 2022, Copenhagen, Denmark) and will be presented virtually on Monday, September 26. The paper can be accessed on **IACR eprint 2022/131**.*

One of the earliest and arguably simplest key exchange protocols was designed by Diffie, Hellmann, and (in an independent work) Merkle in 1976. The idea is that Alice and Bob each choose secrets s_{A} and s_{B}, respectively. For simplicity it is sufficient to think of these elements as integers although they are actually ‘group elements’ in a group ‘generated’ by an element *g*. Then they transmit *g* raised to the power of the respective secrets to each other. These transmitted public values are known as *p _{A}* and

Alternative protocols that share many similarities are key exchange protocols based on the so-called Learning with Errors problem. As before, Alice and Bob choose secrets. This time the secrets are polynomials with small coefficients, e.g., *s _{B} = 1+2x-3x^{2}-x^{213}+4x^{317}-3x^{511}*. Using a publicly-known polynomial

Unfortunately, this extra information allows for attacks to recover Bob’s secret *s _{B}* if Bob does not change his secret ‘every’ time, i.e., when he ‘re-uses’ his secret. This kind of attack is called ‘signal leakage attack under key re-use’ and was first described by Fluhrer and later carried out against the LWE-based DXL key exchange by Ding, Xie, and Lin. The idea is that an adversary pretending to be an honest user sends malformed

Let’s take a look at an example. Assume the adversary wants to find out the third coefficient of the secret polynomial *s _{B} = 1+2x-3x^{2}-x^{213}+4x^{317}-3x^{511}* from above. To do this, the adversary sends

Zooming into one of the switches reveals that for a few values the signal actually fluctuates. This is caused by the random element *e _{B}*. Based on this, one can distinguish between ‘stable’ (blue or yellow in the figure below) and ‘unstable’ (wavy white) regions. To count the number of stable and unstable regions correctly, and as such to be able to count the number of ‘main switches’ correctly, it is not necessary to request

Recently, Qin, Ding, Cheng, Bindel, Pan, and Ding were able to reduce this number further to only 29 values! The idea for this latest improvement is to choose the values even more cleverly. As can be seen in the above figure, actually the three red values are sufficient to uniquely identify the absolute value of the secret coefficient. The idea is to determine codewords that uniquely correspond to possible absolute values. For example, if the code word is *k _{1}-k_{2}-k_{3} = 0-1-1*, the absolute secret value is equal to 1. And if the code word is

This new interpretation of the signal leakage not only reduces the number of required values (therefore making the attack more efficient and more practical), but it also makes it easier to discover whether schemes can be broken by this kind of attack.

Lastly, it is important to mention that signal leakage attacks can be prevented using generic constructions of ‘authenticated’ key exchange protocols. It is, however, desirable to instead construct key exchange directly from a hard problem such as the Learning with Errors problem, e.g., to achieve better efficiency. Therefore, building such ‘direct’ authenticated key exchange protocols is attempted and failed regularly. The new improvements on the signal leakage attacks caution once more against underestimating the power of signal leakage attacks when attempting such constructions.