Lighting the Signal

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 sA and sB, 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 pA and pB. The shared secret key is then computed by taking the received public value again to the power of their own secrets. The security of this protocol is based on the discrete logarithm problem. That means, although the values g, pA and pB are publicly known, it is not possible to compute sA or sB from them. While this is true for our current computers, large fault-tolerant quantum computers will be able to solve the discrete logarithm problem, thereby breaking the security of the Diffie-Hellmann-Merkle key exchange and many other of today’s cryptographic algorithms (visit our blog post for more information about the quantum threat and actions to maintain security in the quantum era). 

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., sB = 1+2x-3x2-x213+4x317-3x511. Using a publicly-known polynomial a (similar to the element g above) and their respective secrets, they compute public values pA and pB and send them to each other. They are then able to compute values hA and hB which are ‘approximately’ the same. To be able to compute ‘exactly’ the same secret key, Bob needs to send additional information. This information is called the signal wB. The signal consists of a list of zeros and ones – as many as the secret has polynomial coefficients. It can be used, together with hA or hB, within a function KeyF that outputs the final key. 

Unfortunately, this extra information allows for attacks to recover Bob’s secret sB 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 pA. In particular, instead of a polynomial, the adversary sends q different integers, namely pA=0, pA=1, …., pA=q-1 for some system parameter q. By construction of the signal, it turns out that each element of the signal “flips” between zero and one twice as often as the absolute value of the corresponding secret coefficient. So by tracking the behavior of the signal as pA varies, the adversary can learn about the secret.

Let’s take a look at an example. Assume the adversary wants to find out the third coefficient of the secret polynomial sB = 1+2x-3x2-x213+4x317-3x511 from above. To do this, the adversary sends pA=0 to Bob, and stores the third value of the signal, which corresponds to the signal for the third polynomial coefficient. Looking at the diagram below, we can see that this signal value is equal to zero. Then the adversary sends pA=1, and again stores the third signal value, which is again equal to zero. As visualized in the diagram, the signal value changes from zero to one for the first time for a value around pA=1800, and back for pA=4000. Increasing pA further until pA=16384 leads to six ‘main’ switches. Therefore, the absolute value of Bob’s corresponding third secret coefficient is equal to 3. The adversary has to do this procedure for ‘all’ polynomial coefficients, which are usually 512 or 1024. In addition, the adversary needs to do a similar procedure to find out the sign of the secret coefficient (e.g., in the example above the secret coefficient is -3). 

Zooming into one of the switches reveals that for a few values the signal actually fluctuates. This is caused by the random element eB. 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 q different values for pA. Instead Bindel, Stebila and Veitch show that it suffices to make sure to choose at least one value in each stable and at most one value for each unstable region for every possible absolute secret value. For example in the picture below, assuming that the absolute value of the secret coefficient is at most 3, the green values for pA=ki are sufficient to determine whether the secret coefficient is equal to 1,2 or 3. This way, it was possible to reduce the number of needed values for pA from a total of 98310 to only 1266 to recover the secret used in the DXL key exchange. 

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 k1-k2-k3 = 0-1-1, the absolute secret value is equal to 1. And if the code word is 1-1-0 or 1-0-1, we know the absolute secret is 2 or 3, respectively. 

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. 

Recent posts