Acoustic Cryptanalysis of RSA and Its Counter Measure

• Prof. J P Agrawal Saurabh Sharma Siddharth Gupta

ABSTRACT

Acoustics has come up as a new vulnerability in the field of information security. The RSA encryption algorithm, although h very hard to break mathematically, has been broken recently by using acoustics and power analysis of emanations. Acoustic Cryptanalysis is the side-channel attack which targets implementations of cryptographic algorithms. The cryptographic algorithms are quite secure at the mathematical level, but inadvertently leak secret information through signatures in power consumption, electromagnetic emanations, timing variations, and acoustical emanations. This paper presents a software based countermeasure which is based on application of specific mitigation techniques to ensure that even if there is leakage of information it would bear minimal useful information.

INTRODUCTION

Acoustic cryptanalysis is a form of side channel attack that aims at deriving the private key in a public key cryptography system using acoustical vibrations of a laptop. A side channel attack is basically an attack that gives attacker an additional channel of information about the system, the noise generated by computers is one such potential channel other channels include keystroke acoustic emanations, acoustic emanations from printers, power analysis via the USB port and timing attacks. Side channel attacks can only be performed on public key cryptography system because the encrypted text i.e. ciphers text depends upon the text that is encrypted. So while decryption the cipher text produces a unique acoustic spectrum which helps the attacker to extract the key.

In this case we put our emphasis on a different source of computer noise i.e. vibration of electronic components like capacitors and transistors in the circuit of the CPU. These acoustic vibrations are related to the system activity since the amount of power drawn from the CPU depends upon the operation which is performed.

As a study case, we will focus on the GnuPG (GNU Privacy Guard), a cross-platform, open-source implementation of the OpenPGP Standard. We will demonstrate a key extraction attack that can extract 4096-bit RSA secret keys when used by GnuPG running on a laptop computer by analyzing the vibrations generated by the computer during decryption of chosen cipher texts.

RELATED WORK

Analysis of acoustical vibrations is relatively a newer practice commonly used in military context such as identification of vehicles through the sound signature of their engine. Similarly computer programmers monitor the functioning of their systems by listening to sound generated by mechanical components. Some of the successfully implemented experiments involving side channel attacks include :

ï‚· Electromechanical ciphers.

ï‚· Keyboard acoustic emanations.

ï‚· Acoustic emanations from printers.

ï‚· Power analysis.

ï‚· Power analysis via the USB port.

ï‚· Timing attacks.

THE EXPERIMENTAL SETUP

(A) laptop on which the decryption is being performed

(B) Brüel&Kjær 4190 microphone capsule mounted on a Brüel&Kjær 2669 preamplifier held by a flexible arm.

(C) Brüel&Kjær 5935 microphone power supply and amplifier,

(D) National Instruments MyDAQ device with a 10 kHz RC low-pass filter cascaded with a 150 kHz RC high-pass filter on its A2D input

(E) laptop computer performing the attack.

Here, the microphone power, amplification and some filtering are done by an integrated, battery operated Brüel&Kjær 5935 microphone power supply. After a self-built 10 kHz RC low-pass filter cascaded with a 150 kHz RC high-pass using capacitors and resistors, A2D conversion is done by the compact, USB-operated National Instruments MyDAQ device. The MyDAQ device captures at 200 K sample/sec. The Brüel&Kjær 5935 amplifier is limited to a frequency of 100 kHz.

OBSERVING THE ACOUSTIC LEAKAGE

1. Distinguishing various CPU operations

We can distinguish between various operations performed by CPU by analyzing the low bandwidth leakage of acoustical emanations. Our analysis begins by taking into account simple operations like: 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). We concluded that these operations exhibit a unique frequency spectrum on execution.

2. Distinguishing various code lengths

These acoustical emanations can also determine the length of loop being executed. For example the leakage produced by a code executing 10000 ADD instructions in an infinite loop will have a different acoustic spectrum than a program executing 20000 ADD instructions in an infinite loop.

3. Leakage source

The observed acoustical emanations are not caused by the rotation of the fan, hard seeks or audio speakers as it is verified by disabling these components. Rather it is caused by the capacitors and resistors in the power regulation circuit of the CPU. The precise source of the emanations is difficult to characterize, since it is different in every machine and it is typically located in hard to reach places. Acoustic localization is also difficult due to mechanical coupling of capacitors and resistors and because of acoustic reflections due to other components.

PERFORMING THE ATTACK

The attacker sends an encrypted email to the target machine. This email when received by the target machine undergoes the process of decryption so as to extract the data that has been sent. The email which is sent involves sending a chosen ciphertext, it cannot have any random data in it. The data which is sent via the email has to be a specially crafted ciphertext. Through this attack we try to get the ‘q’ i.e. one of the prime factor of the key ‘n’.

Enigmail provides an integrated graphical user interface and handles e-mail encoding and user interaction; the actual cryptography is done by an external GnuPG executable. Received e-mail messages are decrypted upon the user’s request. In addition and by default, Enigmail automatically decrypts incoming e-mail messages. Thus, an attacker can send a suitably-crafted e-mail message to the victim, containing a chosen ciphertext. When this e-mail message is fetched by the target computer, the attacker observes the acoustic emanations during decryption, and obtains a bit of the secret key. The attacker then sends additional e-mail messages, until all key bits are recovered. If the messages are backdated or made to look like spam messages, they may even go unnoticed. But this doesn’t affects our attack as it will still be decrypted by the email client.

1. Choosing the ciphertext

q is a 2048 bit number

q₂₀₄₈ q₂₀₄₇ q₂₀₄₆ q_{2045…………} q₂ q₁

GnuPG always generates RSA keys in which the most significant bit of q is set, i.e., q2048 = 1. Considering we know the first i-1 bits of q

e.g. i=4 , we know q₂₀₄₈ q₂₀₄₇ q₂₀₄₆ =110

Now we need to find the next bit of q , which can be 0 or 1

So , we create a ciphertext with first i-1 bits equal to that of first i-1 bits of q, the next bit 0 and the remaining bits to be 1

q₂₀₄₈ q₂₀₄₇ q₂₀₄₆ 0 111111………….11111

2. Recording the emmisions

We use our experimental setup to record the acoustic emissions that are created during the decryption. Placing the microphone with respect to the laptop body has a large influence on the obtained signal. Laptops have cooling system for heat dissipation. It has a fan that requires large intake of air and some exhaust holes. Also, there are other holes and gaps for ports such as USB, Express Card slot, SD card reader, and Ethernet port. Any of these ports can be used as a position for the microphone. Typically, the best microphone placement is near the Ethernet port or the fan exhaust vent.

We record the sound using the LABVIEW software. We compute the sliding-window Fourier transform of the trace, yielding a sequence of spectra, and then aggregate these spectra by taking the median value of each bin. (The use of median effectively rejects temporally-local outliers, such as transient spikes.) The spectrum is truncate to the frequency range of interest (determined manually).

3. Extracting the key

The most significant bit of a prime number is always 1. Using this fact we create a desired ciphertext and obtain the power – frequency templates for 0 and 1. Thus, if the attacker were to have two spectrum templates describing the leakage of zero and one bits, he could classify an unknown signal by checking the similarity between it and the templates he has. Concretely, in our case a template is a vector of real numbers describing the signal power at each frequency bin. The classification is based on computing the correlation of the Fourier spectrum of the leakage with the two templates.

Recall that q is chosen to be a prime such that its most significant bit is always set to one. Moreover, this information is known to an attacker. Thus, obtaining an example of a leakage of a one bit can be done by measuring the leakage resulting from the decryption of g2048;1. Obtaining an example of a leakage of a zero bit is more tricky. This is because the attacker does not know in advance the location of the first zero bit in q. However, this problem can be easily avoided. Consider any number l such that q < l < 2q (for example l= 2²⁰⁴⁸ – 1). Notice that the reduction of l modulo q is equivalent to computing l – q and will cause the bits of the result to be random thus achieving a similar spectrum as the sound of zero bits of q at the beginning of the attack.

After this we compare the data acquired with the templates of 0 and 1 and the output of the comparison gives one bit of the q. Then this attack has to repeated 2048 times to get all the bits of q.

These templates are updated dynamically in the matter of 20 bits. After receiving the acoustic spectrum of every attack bit we try to match the frequencies with the ones in the predefined templates. Whenever we get a matching frequency we check it’s corresponding value for power if this value is in range according the given threshold of the template we classify the bit as 0 or 1. By repeating this same procedure to attack every bit we obtain all the 2048 bits of prime q and in turn find the key.

COUNTER MEASURE

Cipher text randomization : One countermeasure that is effective in stopping our attack ciphertext randomization. If we have a cipher text c, instead of decrypting c immediately what we can generate a 4096 bit random value r, compute re and then decrypt re* c and multiply the result by r^-1. Since ed = 1 mod (n)

It does not stop the attacker from extracting the key but it masks the original key so that even if the attacker is able to extract the key he doesn’t has the correct key.

In implementation we have used the random library of python. Using this library random.randint(range) generates a random integer which can be multiplied to the value of cipher text and it changes the acoustic spectrum of the ciphertext which masquerades the original key.

Why software based countermeasures are better than hardware based countermeasures?

Enforce a proper layering can seem to be an effective countermeasure. Unfortunately, such low-level physical leakage prevention, is most of the times, impractical due to the significantly bad cost vs. security tradeoff because of the following reasons :

(1) Suitable manipulation at the higher levels can amplify any leakage remnants, similar to what we do in our chosen-ciphertext attack

(2) Low-level mechanisms try to protect all computation, even though most of it is insensitive or does not induce easily-exploitable leakage

(3) Essential performance-enhancing mechanisms produce leakage as an inevitable side effect.

REFRENCES

[1] M. Hanspach and J. Keller, ―In guards we trust: Security and privacy in operating systems revisited,â€- in Proc. 5th ASE/IEEE International Conference on Information Privacy, Security, Risk and Trust, Washington D.C., USA: IEEE, Sept 2013.

[2] M. Hanspach and M.Goetz, ―On Covert acoustical mesh network in air, revisited,â€- in Journal of Communications Vol. 8, No. 11, November 2013.

[3] R. Otnes, A. Asterjadhi, P. Casari, M. Goetz, T. Husøy, I. Nissen, et al., Underwater Acoustic Networking Techniques, ser. Springer Briefs in Electrical and Computer Engineering, Springer, 2012.

[4] R. Frankland, ―Side channels, compromising emanations and surveillance: Current and future technologies,â€- Department of Mathematics, Royal Holloway, University of London, Egham, Surrey TW20 0EX, England, Tech. Rep., Mar. 2011.

[5] Daniel Genkin, Adi Shamir, Eran Tromer, RSA Key Extraction via Low-Bandwidth Acoustic Cryptanalysis December 18, 2013.

[6]Nikita Borisov, Ian Goldberg, and David Wagner. Intercepting mobile communications: the insecurity of 802.11

[7] H. E. Bass and Roy G. Keeton. Ultrasonic absorption in air at elevated temperatures. The Journal of the Acoustical Society of America.

[8]Taher ElGamal. A public key cryptosystem and a signature scheme based on discrete logarithms.IEEE Transactions on Information Theory, 31(4):469–472, 1985.

1