Breaking The Encryption on Your Mobile Phone — Without Touching It

Breaking The Encryption on Your Mobile Phone — Without Touching It

A paper presented at the USENIX Security Symposium outlined how RSA encryption keys can be cracked from the radio waves emitted by a mobile phone [here]:

The researchers used the EM radiation emitted from the processor is it performs complex RSA calculations, and then used a timing attack to recover the private key. Figure 2 outlines the capture of the signal and the identification of the key parts of the signal which are gathered:

It works without even knowing the actual ciphertext. This type of attack is known as a side-channel attack, and these types of attacks have been well-known in the industry to break encryption. Common side channel attack vectors include monitoring variations in the electrical power signal, and temperature levels, and have even included monitoring the sound emitted from a system.

In the past, the electromagnetic radiation has also been used to attack a range of devices including SIM card readers and mobile phones, but it has often been used to identify the tell-tail signs of symmetric key encryption (such as in AES). This new paper focuses on a more challenging area of public key encryption, and the tell-tail signs of the RSA method. The researchers focus on finding the point at which the OpenSSL library uses Montgomery modular multiplication, and then pick off its operations, in order to provide a guess for the numbers used within the decryption process of RSA. This reveals the decryption key (d,N).

Montgomery modular multiplication

With the RSA method — which is a public key method, where we have a public key and private key — and the Diffie-Hellman method — where we perform a secret key exchange — we perform large exponential calculations, such as:

C = Mᵉ (mod N)

M = Cᵈ (mod N)

and where we will continually multiply large integers by an exponent to get a result. As we are using an exponential method, the values of the Cᵈ and Mᵉ operation become very large (often with more than 2,048 bits), and is thus a complex operation. The method that OpenSSL uses for the RSA method in order to reduce this complexity is with Montgomery modular multiplication. It must be remembered that x to the power of y, is basically x multiplied by x for y times.

In a traditional multiplication of two values (x and y) for a modulus of N, we multiply x times y and then divide by N to find the remainder. The number of bits in the multiplication will then be the number of bits in x added to the number of bits in y. In Montgomery reduction we add multiples of N in order to simply the multiplication.

An example of this is here, and a sample run for x=10, y=5 and N=29 is:

x=	10
y=	5
N=	29

x*y (mod N)
Result (Montgomery)=	21
Result (x*y % mod)=	21

x^y (mod N)
Result (Montgomery)=	8
Result (x^y % mod)=	8

In this case we get 50 (mod 29) which is 21, and 10⁵ mod 29 which is 8.

Experiments

For the experiments the researchers used a Samsung Galaxy Centura SCH-S738C smart phone, an Alcatel Ideal smart phone, and an A13-OLinuXino board (Figure 3).

The antenna was placed just above the back of the phone, and picks up the EM radiation from the CPU. As it performs its relatively long multiplication process, the evaluation system then triggers the data capture. The success rate for picking the required 2,048 bit decryption key was over 95%, with a success of over 99% for the Samsung phone (Figure 4).

Conclusions

Like it or not, your mobile phone, just like any other electrical device, gives our radio waves. Unfortunately these radio waves can give away your most precious of processions — your encryption keys. The researchers have already disclosed the finding to the OpenSSL developers, and have proposed a solution to the problem.

If you are interested in side-channel work on breaking encryption, you can read more here:

If you want to learn more about the Montgomery multiplication method: