README.md

Hastad's Broadcast Attack

Prerequisites:

1. RSA Encryption/Decryption
2. Chinese Remainder Theorem- Wikipedia
3. Chinese Remainder Theorem- Crypto@Stanford

We will start by discussing the simplest form of Hastad's Broadcast Attack on unpadded messages and then generalise the attack on linearly padded messages using Coppersmith's Theorem.

Hastad's Broadcast Attack on unpadded messages

Suppose Alice sends an unpadded message M to k people P₁, P₂, ..., P_k each using a same small public key exponent e and different moduli N for ith individual, the public key for ith individual (N_i, e). The attack states that as soon as k >= e, the message M is no longer secure and we can recover it easily using Chinese Remainder Theorem.

Let us understand this attack using an example: Alice sends a message M to 3 three different people using the same public key exponent e = 3. Let the ciphertext received by ith receiver be C_i where C_i = M³ mod N_i. We have to assume that gcd(N_i, N_j) == 1 where i != j

Quick Question: What if GCD(N_i, N_j) != 1?
Then the moduli pair (N_i, N_j) is vulnerable to Common Prime Attack

We can now write:

Thus we can get the following by solving using Chinese Remainder Theorem:

where b_i = N/N_i, b_i^' = b_i^-1 mod N_i and N = N₁* N₂* N₃. Since we know that M < N_i (If our message M is larger than the modulus N, then we won't get the exact message when we decrypt the ciphertext, we will get an equivalent message instead, which is not favourable).
Therefore we can write M < N₁N₂N₃. We can easily calculate M now by directly taking the cube root of M³ to get M.

You can find an implementation of this attack here: hastad_unpadded.py

     

Hastad's Broadcast Attack on padded message

Hastad also showed that applying linear padding to the message M prior to encryption does not protect from this attack.

Assuming C_i = f_i(M)^e for 1<=i<=k (k --> number of individuals the message is to be sent/has been sent). Here f_i is a linear function to pad the message M, so that the recipients receive slightly different messages.

For ith individual, Message M = i*2^m + M, where m is the number of bits in M. Hastad proved that a system of univariate equations modulo relatively prime composites, such as applying fixed polynomial could be solved if sufficient equations are provided.

This attack is an application of Chinese Remainder Theorem and Coppersmith's Theorem.

Exploit in a Nutshell:

1. Calculate N = n1*n2*...
2. Calculate each element T[j] as per the above conditions using CRT
3. Assign P. = PolynomialRing(Zmod(N))
4. g[j] = (i*(2^m) + x)^e - c, where the message is padded using the above conditions
5. Assign g = Sum_of(T[j] * g[j])
6. Check if g is a monic polynomial, if not transform it into a monic polynomial
7. Find small roots of g and check if that is the flag

Resources

1. Wikipedia- Coppersmith's Attack
2. Wikipedia- Chinese Remainder Theorem
3. Cryptanalysis of RSA using Lattice Methods- Crypto@Stanford