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 find RSA implementations are Linux package managers(e.g. apt,pacman), SSL and digital signatures. In this homework we will explain and implement two different 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 different ciphertexts (of the same plaintext).

Second attack is a side channel attack (SCA). In SCAs we dont 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 find 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 staff 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(e_i,e_j) = 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 asistants respective public exponents, e₁ and e₂, to get c₁ = m^e1 (mod n) and c₂ = m^e2 (mod n). Later he sends c₁ and c₂ to the assistants.

In the above situation, an eavesdropper can recover the exam questions from c₁ and c₂ using the common modulus attack.

Recall that RSA performs encryption as follows:

C = M^e (mod N)

We also need to remember Bezouts identity.

Bezouts 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 e₁ and e₂ are chosen from a set of primes, they are co-prime, that is gcd(e₁,e₂) = 1. Then following the Bezouts identity, we know that there exists x and y, which satisfies e₁x + e₂y = 1. And we can find 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 e₁) gcd(e₁,e₂) = 1

c2 = me2 (mod n)(m encrpyted with e₂) e₁x + e₂y = 1

Now onto the attack. Main idea is to take the xth and yth powers of c₁ and c₂ to cancel out the public exponents e₁ and e₂.

(c1)x (c2)y = (me1)x (me2)y (mod n)

= me¹x me²y (mod n)

= _me¹x+e²y (mod n)

= m¹ = m (mod n)

Thats it. We broke the RSA. We also now have the exam questions!

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

Program Specifications

• 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 containing commands to compile (if necessary) and run your programs. make run command will be run in the directory containing your Makefile during evaluation.
• Your program should read a csv file called csv, which will be placed to the same path with your program, for the values of c₁, c₂, e₁, e₂ and n. First field will be the name of the parameter (i.e. one of the following: c1, c2, e1, e2 or n). Second field 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 file named 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 find 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 specific implementation error. There also may be other implementation errors which allow different 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 efficient 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) r 1

for bit in exp do r r r mod n (Squaring step) if bit == 1 then r = br 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 find out the exponent (in our context, the key). For example if the performed operations 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 Specifications

• 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 containing commands to compile (if necessary) and run your programs. make run command will be run in the directory containing your Makefile during evaluation.
• Your program should read the power trace from a file called trc, which will be placed to the same path with your program. This file will contain the power measurements of a chip during decryption. Each line in the file 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 shouldnt output anything other than the plaintext.
• Submit your programs as a zip file named zip, where XXXXXXX is your student id.

Note: A sample input/output will be provided.