Acoustic Cryptanalysis - A Side-Channel Attack

 Side-Channel Attack:

A Side-Channel Attack is any attack based on information gained from the implementation of a computer system, rather than weaknesses in the implemented algorithm itself. In layman terms, side-channel attacks basically exploit timing information, power consumption, electromagnetic leaks, or even sound(yes!)  produced by your computer to "hack" it.

Acoustic Cryptanalysis Attack:

In a basic sense, an Acoustic Cryptanalysis attack means to exploit the sound emitted by a cryptographic system to figure out the cryptographic key and break the system. This can be achieved in a few ways - listening to the sound of your victim typing the passphrase and steal their passphrase or listening to the ultrasonic noise emanations from capacitors and inductors on computer motherboards. To break a system using the sound of keystrokes of the keyboard we need a sophisticated machine learning model, including high data to distinguish one keypress from another. On the other hand, listening to the capacitors and inductors though sounds out of a science-fiction movie is a very realistic attack. In 2016, Genkin, Shamir, and Tromer published another paper that described a key extraction attack that relied on acoustic emissions from laptop devices during the decryption process. They demonstrated their attack with a "simple mobile phone" at a distance of 30cm away from the victim machine. In this post, we try to learn about the latter method.

So what exactly are we trying to listen to? The sound source in laptops is capacitors and whine, collectively called “coil whine”. This emancipates sounds which are measured and analyzed. 

Though Side-Channel attacks seem very different from each other, they have a certain methodology to them.

 

The basic steps are:

1. Find key-dependent instruction.
2. Record emanations using high-bandwidth equipment.
3. Obtain traces.
4. Analyze the recordings and "guess" or "recover" the key.

Implementation of the attack: 

In the paper, they attack GnuPG (a software that implements RSA encryption). To use GnuPG, we send “adaptive cipher-texts” to the victim machine which uses Enigmail, which decrypts the massages as soon it receives them.

The amplifier and digitizer are used to record acoustic emancipations and graph them in this way. The vertical axis is a time axis and the horizontal axis is the frequency axis.

In the paper, they describe that all operations performed by the computer emit different acoustic emancipations which allow us to identify different operations. They find out the correlation of acoustic emancipations with a basic code( For this purpose they wrote a simple program that executes (partially unrolled) loops containing one of the following x86 instructions: HLT (CPU sleep), MUL (integer multiplication), FMUL (floating-point multiplication), main memory access (forcing L1 and L2 cache misses), and REP NOP (short-term idle) ).

How does RSA decrypt the message?

At the heart of RSA decryption is a modular exponentiation m = c^d mod N  where N = pq is the RSA modulus, d is the private decryption exponent, and c is the ciphertext is decrypted. The key-dependent steps of the GnuPG’s implementation of RSA is – Chinese Remainder Theorem and Multiplication (Karatsuba vs Normal). 

GnuPG uses the Chinese Remainder Theorem (CRT) to perform this exponentiation. With Chinese remaindering, the function m = cd mod N is computed in two steps. First, evaluate m1 = c^d1 mod p and m2 = c^d2 mod q (where d1 and d2 are precomputed from d). Then, combine m1 and m2 using CRT to yield m. This speeds up the process by a factor of four. For further optimization, RSA also implements square and multiply and sliding window.

GnuPG uses Karatsuba multiplication when multiplying two numbers with an equal number of words. GnuPG uses normal multiplication, which runs in time O(nm) when multiplying two numbers with an unequal number of words of size n and m. This step depends highly on the input.

To learn in detail about RSA implementation, watch a video lecture here.

Obtaining the traces:

Since GnuPG represents large numbers in arrays of 32-bit limbs, GnuPG optimizes the number of modulo reductions by always checking (at the end of every multiplication and squaring) whether the number of limbs in the partially computed result exceeds the number of limbs in the modulus. If so, a modular reduction operation is performed. If not, the reduction will not decrease the limb count, and thus is not performed. This implementation of RSA still uses the same Karatsuba vs Normal multiplication which we exploit.

One problem with the acoustic attack is that the emanation is very low and quick for us to analyze. Hence the idea is to use "adaptive cipher-texts" to target the 6inner-most loops which will create a ripple big enough for us to analyze.

On running a sample RSA decryption, we find out that we can differentiate mod p and mod q of the algorithm. Here, in the image, the arrow points to the time difference between mod p  and mod q denoting that we can differentiate them.

"Guessing" the key:

In the "guessing" the key phase, we make approximate guesses on individual bits of the key. We exploit the Multiplication decision(Karatsuba vs Normal) to make a guess. Depending on the bit, the key is passed to the multiplication module differently which creates a difference in their frequency as they will have different numbers of limbs. We can notice the difference in the frequency in the below picture as well as the above one.

The attacker just needs to jot down half the bits of the key and can generate the whole private key, without ever even touching the victim machine.

Conclusion:

Worrying about the ultrasonic-sound made by the computer may seem "paranoid" but Acoustic cryptanalysis is a realistic attack. Side-channel attacks have been around for ages but have not gotten the same level of attention as remote attacks have. The reason being the physical proximity required by these sorts of attacks. With the increase in popularity of IoT devices where most of the devices contain sensors, these attacks will become more feasible.