ceng Homework 1 - Smashing RSA for fun and pro t(?)! Solution

Overview

In this assignment we will break the RSA encryption system. RSA, is a public-key cryptosystem which is commonly used in secure communication. Some examples of where you can nd RSA implementations are Linux package managers(e.g. apt,pacman), SSL and digital signatures. In this homework we will explain and implement two di erent attacks on RSA.

First attack is one of the simplest attacks that can be performed on RSA and is extremely rare to happen in the real world. But it may be useful if you are interested in cryptography (and/or cybersecurity competitions). It is called "common modulus attack" and with this attack we can get the plaintext from two di erent ciphertexts (of the same plaintext).

Second attack is a side channel attack (SCA). In SCAs we don’t try to break the cryptosystem directly, but we try exploit the implementation. We can use the extra information from time measurements, power consumption levels or even acoustic measurements along with many other side channels to nd out the plaintext or cipher keys. In this assignment we will perform a power analysis side channel attack on RSA.

Attack 1: Common Modulus Attack

Consider the following scenairo:

The sysadmins of CENG issue each person in sta roster with an individual RSA key. To simplify the public key infrastructure (PKI) maintenance for the department, admins decide to generate a single modulus N and each person will be issued a personalized public encryption exponent e, and corresponding private decryption exponent d. Moreover, all key generations are performed by admins. This way the admins will also have a copy of each generated RSA key-set. They swear that they will not spy on us and propose the following reasons:

When someone loses a key, admins can reissue the key. Possibly preventing data loss.

In case of an internal security leak, admins can easily investigate it with all the keys available to them.

Further assume that to speed up the process of generating e, admins decide to select it from a set of pregenerated prime numbers. Therefore the greatest common divisor (gcd) of each generated e pair is 1 [gcd(ei; ej ) = 1].

Now suppose that a professor wants to send the exam questions, m, to two assistants of the course. He encrpyts the questions with each asistant’s respective public exponents, e1 and e2, to get c1 = me1 (mod n) and c2 = me2 (mod n). Later he sends c1 and c2 to the assistants.

In the above situation, an eavesdropper can recover the exam questions from c1 and c2 using the common modulus attack.
Recall that RSA performs encryption as follows:

C = Me    (mod N)

We also need to remember Bezout’s identity.

Bezout’s identity. Let a and b be integers with greatest common divisor d. Then, there exist integers x and y such that ax + by = d. More generally, the integers of the form ax + by are exactly the multiples of d.

Since we know that e1 and e2 are chosen from a set of primes, they are co-prime, that is gcd(e1; e2) = 1. Then following the Bezout’s identity, we know that there exists x and y, which satis es e1x + e2y = 1. And we can nd x and y with the Extended Euclidean Algorithm. To sum up everything we know, we have the following:

c1
= me1
(mod n)(m encrpyted with e1)
gcd(e1; e2) = 1
c2
= me2
(mod n)(m encrpyted with e2)
e1x + e2y = 1

Now onto the attack. Main idea is to take the xth and yth powers of c1 and c2 to cancel out the public exponents e1 and e2.

(c1)x   (c2)y = (me1 )x   (me2 )y
(mod n)
= me1x   me2y
(mod n)
= me1x+e2y
(mod n)
= m1 = m
(mod n)

That’s it. We broke the RSA. We also now have the exam questions!

Your task is to write a program which nds out the plaintext from the given two ciphertexts, public exponents and the common modulus.

Program Speci cations

You can write your programs in any language you choose as long as they can be run on inek machines. Python is highly recommended because it makes dealing with huge numbers easy.

Since you can use any programming language you will have to provide a Makefile contain-ing commands to compile (if necessary) and run your programs. make run command will be run in the directory containing your Make le during evaluation.

Your program should read a csv le called crackme.csv, which will be placed to the same path with your program, for the values of c1, c2, e1, e2 and n. First eld will be the name of the parameter (i.e. one of the following: c1, c2, e1, e2 or n). Second eld will be the value of the parameter in hexadecimal format.

You should output the plaintext of the message to the stdout and you should output nothing else.

Submit your programs as a zip le named eXXXXXXXp1.zip, where XXXXXXX is your student id.

Note: A sample input/output will be provided.
Attack 2: Power Analysis SCA

In this side channel attack we will monitor the power consumption of the chip performing the RSA encryption or decryption to nd out the key. Instead of attacking the RSA algorithm itself, we are trying to exploit the implementation of the algorithm. We will focus on one speci c implementation error. There also may be other implementation errors which allow di erent side channels to be exploited.

RSA utilizes modular exponentiation with big numbers. Since we deal with huge numbers exponentiation takes time. So we need an e cient algorithm for this. Luckly we have such an algorithm called exponentiation by squaring (or square and multiply). Psuedo code looks like this:

function ModPower(b, exp)

    • 1

for bit in exp do

    • r r mod n (Squaring step) if bit == 1 then

r = b r mod n (Multiplication step) end if

end for

return r

end function

Important thing to take away from this function is that we go over the exponent bit by bit. And remember, we are using keys as exponents to encrypt or decrypt the messages in RSA. You see where this is going?

If you were given a list of squaring and multiplication operations during the execution of this function you can nd out the exponent (in our context, the key). For example if the performed op-

erations are [Square, Multiply, Square, Multiply, Square, Square, Square, Multiply] we can easily say that the exponent is 11001:

Square    Multiply    Square    Multiply    Square    Square    Square    Multiply


1    1    0    0    1

Now think about the power consumption of the processor during this process. For simplicity assume that the processor only consumes power during squaring and multiplication.





















Figure 1: A Sample power trace with performed operations annotated
In the power trace if the power consumption is increased for a short duration bit is 0, and if it is increased for a longer duration bit is 1.

As you can see it is quite straightforward to get the key from a power trace. The program you will write will take in a power trace and a ciphertext and will output the plaintext.

Program Speci cations

You can write your prorams in any language of your choosing as long as they can be run on inek machines. Python is highy recommended because it makes dealing with huge numbers easy.

Since you can use any programming language you will have to provide a Makefile contain-ing commands to compile (if necessary) and run your programs. make run command will be run in the directory containing your Make le during evaluation.

Your program should read the power trace from a le called ptrace.trc, which will be placed to the same path with your program. This le will contain the power measurements of a chip during decryption. Each line in the le will be a single power measurement value between 0 and 15 sampled in regular intervals.

Your program will read a ciphertext encrypted with a public key and the value of n from stdin as a hex string separated by a newline character and will output the corresponding plaintext to stdout. It shouldn’t output anything other than the plaintext.

Submit your programs as a zip le named eXXXXXXXp2.zip, where XXXXXXX is your student id.

Note: A sample input/output will be provided.