RSA Capture The Flag For Chinese Remainder Thereom — Meet Håstad’s Broadcast Attack

Our students love doing Capture The Flag (CTF) exercises, and it is a great way to develop coding skills in translating different cipher…
Photo by Mauro Sbicego on Unsplash

RSA Capture The Flag For Chinese Remainder Thereom — Meet Håstad’s Broadcast Attack

Our students love doing Capture The Flag (CTF) exercises, and it is a great way to develop coding skills in translating different cipher values. Hopefully, along the way, they will learn some core theories about discrete logarithms and exponential ciphers. One common challenge is to solve an RSA cipher and where the same message has been ciphered with three different moduli. This attack is known as Håstad’s Broadcast Attack [1].

So let’s create a challenge generator, and with a sample question of:

Bob has used the RSA with three different modulus' to encrypt the same message for Alice. These modulus values are 1028541090183196101522935378951727053, 611800257738058721678060612021626303, and 637990920592078042917836803557776639. The corresponding ciphered values are 909627621704647324353263925942071968, 143590219961128784057515688652190875, and 240523521479830533690881019502697561. Determine the message.

and another:

Bob has used the RSA with three different modulus' to encrypt the same message for Alice. These modulus values are 16291690676599334881, 12809246438477591491, and 11540201434385924291. The corresponding ciphered values are 15398372416686382412, 9202230456851114422, and 8685470170547581956. Determine the message.

You will see that the size of the integers differs, as we are using a given size of the prime numbers used to generate the modulus.

RSA theory

With RSA, we create two random prime numbers (p and q), and determine the modulus (N=pq). We encrypt a message with C=M^e (mod N) and decrypt with M=C^d (mod N), and where (e,N) is the encryption key and (d,N) is the decryption key. We can crack RSA with Chinese Remainder Theory (CRT), and where we create three ciphers with the same message and three different encryption keys.

We start by generating two prime numbers (p,q) and then calculate the modulus (N):

Now we have a message (M), and create a cipher with:

Next we create three ciphers:

We can then solve for M^e with the Chinese Remainder Theorem (CRT). Once we have this we can determine M. If we assume that e=3 and then we get:

We thus need to get the 3rd root of the result of the CRT method. In Python, we can either use:

M=res**(1.0/3.0)

or use a library:

M=libnum.nroot(res,3)

Coding

The coding is here:

from Crypto.Util.number import *
from Crypto import Random
import Crypto
import sys
import libnum
bits=60
msg="Hello1"
if (len(sys.argv)>1):
        msg=str(sys.argv[1])
if (len(sys.argv)>2):
        bits=int(sys.argv[2])
p = Crypto.Util.number.getPrime(bits, randfunc=Crypto.Random.get_random_bytes)
q = Crypto.Util.number.getPrime(bits, randfunc=Crypto.Random.get_random_bytes)
n1 = p*q

e=3
m=  bytes_to_long(msg.encode())
c1=pow(m,e, n1)

p = Crypto.Util.number.getPrime(bits, randfunc=Crypto.Random.get_random_bytes)
q = Crypto.Util.number.getPrime(bits, randfunc=Crypto.Random.get_random_bytes)
n2 = p*q
c2=pow(m,e, n2)

p = Crypto.Util.number.getPrime(bits, randfunc=Crypto.Random.get_random_bytes)
q = Crypto.Util.number.getPrime(bits, randfunc=Crypto.Random.get_random_bytes)
n3 = p*q
c3=pow(m,e, n3)
if ((m**e)<n3 or (m**e)<n2 or (m**e)<n1):
    print("Message is too short.")
    sys.exit()
print(f"Bob has used the RSA with three different modulus' to encrypt the same message for Alice. These modulus values are {n1}, {n2}, and {n3}. The corresponding ciphered values are {c1}, {c2}, and {c3}. Determine the message.")

mod=[n1,n2,n3]
rem=[c1,c2,c3]
res=libnum.solve_crt(rem,mod)
print("\n\nAnswer:")
print(f"\nCipher 1: {c1}, N1={n1}")
print(f"Cipher 2: {c2}, N2={n2}")
print(f"Cipher 3: {c3}, N3={n3}")

print(f"\nWe can solved M^e with CRT to get {res}")
val=libnum.nroot(res,3)
print(f"If we assume e=3, we take the third root to get: {val}")
print(f"\nDecipher: {long_to_bytes(val)}")

A sample run with 64-bit primes is:

Bob has used the RSA with three different modulus' to encrypt the same message for Alice. These modulus values are 231260178677650390496020549417087327073, 256987093516394106832852956074712721493, and 199511472277154118882579159116148423523. The corresponding ciphered values are 68738548514009089363505881427598015940, 116875596554950291943348476519343695417, and 78802962949012540753836484408691516347. Determine the message.
Answer:
We have used 64-bit primes here and which generates 128-bit modulus values. The values of:
Cipher 1: 68738548514009089363505881427598015940, N1=231260178677650390496020549417087327073
Cipher 2: 116875596554950291943348476519343695417, N2=256987093516394106832852956074712721493
Cipher 3: 78802962949012540753836484408691516347, N3=199511472277154118882579159116148423523
We can solved M^e with CRT to get 8461871598322886801331718165501781158188510835784
If we assume e=3, we take the third root to get: 20377714673266994
Next we convert this integer to bytes, and display as a string.
Decipher: b'Hello12'

And for 32-bit primes:

Bob has used the RSA with three different modulus' to encrypt the same message for Alice. These modulus values are 5549606389411464503, 13891273370047465057, and 6123192259444467997. The corresponding ciphered values are 2895633871948428917, 12334561072050872687, and 1113100318830978380. Determine the message.
Answer:
We have used 32-bit primes here and which generates 64-bit modulus values. The values of:
Cipher 1: 2895633871948428917, N1=5549606389411464503
Cipher 2: 12334561072050872687, N2=13891273370047465057
Cipher 3: 1113100318830978380, N3=6123192259444467997
We can solved M^e with CRT to get 8461871598322886801331718165501781158188510835784
If we assume e=3, we take the third root to get: 20377714673266994
Next we convert this integer to bytes, and display as a string.
Decipher: b'Hello12'

The following are some examples:

  • “Hello12”, Prime numbers with 16 bits Try.
  • “Hello12”, Prime numbers with 32 bits Try.
  • “Hello12”, Prime numbers with 64 bits Try.
  • “Hello123458”, Prime numbers with 128 bits Try.

Conclusions

There are not many cases in that we would use the same message, and with three different moduli, so this type of attack is probably only an academic exercise. But, there are attacks that are very much alive, including the Coppersmith attack:

https://asecuritysite.com/rsa/copper

and the Bleichenbacher’s attack [3]:

https://asecuritysite.com/rsa/c_c3

The Bleichenbacker’s attack has been continually compromising some systems for decades, but TLS 1.3 now overcomes it by dropping support for PCKS#v1.5. The solution is to use padding, and one of the most popular methods is Optimal Asymmetric Encryption Padding (OAEP). The method was first published by Bellare and Rogaway as [here][2]:

https://asecuritysite.com/rsa/node_rsa

Reference

[1] Hastad, J. (1988). Solving simultaneous modular equations of low degree. siam Journal on Computing, 17(2), 336–341 [here].

[2] Bellare, M., & Rogaway, P. (1994, May). Optimal asymmetric encryption. In Workshop on the Theory and Application of of Cryptographic Techniques (pp. 92–111). Springer, Berlin, Heidelberg.

[3] Bleichenbacher, D. (1998, August). Chosen ciphertext attacks against protocols based on the RSA encryption standard PKCS# 1. In Annual International Cryptology Conference (pp. 1–12). Springer, Berlin, Heidelberg.