Failed File Transfer - Crypto

Task

Hello, Investigator,

We have intercepted a transmission that was sent to the thief of Anthony’s invention. We believe it may contain information pertinent to your investigation! Additionally, the sender accidentally failed to encrypt the file with the thief's most recent provisioned key, requiring them to resend the message. I am not sure why, but the keys don’t seem all that different… There may be a vulnerability with the provisioning process. Nevertheless, we have provided you with all attempts captured in transmission and the keys used for posterity. Good luck!

Solution

There are 6 files attached to this task:

szczygielka@hacks$ ls
file1.txt  file2.txt  file3.txt  pk1.pem  pk2.pem  pk3.pem

The files file1.txt, file2.txt and file3.txt contain encrypted messages, and the files pk1.pem, pk2.pem and pk3.pem corresponding OpenSSL public keys. We also know that 2 of these ciphertexts should contain the same message.

At first glance, pk1.pem and pk2.pem seems to be very similar. Let's check where the differences are:

Let's check the N and e values of these two keys. We can do that using Python:

from Crypto.PublicKey import RSA

pk1= RSA.importKey(open('pk1.pem', 'r').read())
pk2= RSA.importKey(open('pk2.pem', 'r').read())

print("Public key pk1.pem:")
print("N:", pk1.n)
print("e:", pk1.e,"\n")

print("Public key pk2.pem:")
print("N:", pk2.n)
print("e:", pk2.e)

After running the script, we get the following values:

szczygielka@hacks$ python3 check_public_keys.py 
Public key pk1.pem:
N: 28328155133789285412996485843849200476439065854667450765531808634398279813714628611356505714448351029445206816297052695426468253209725620716288482361102009067488713792451157452440320904129625879607490043398774470615404369860538006179371183327649709712501068068177273167061064338155527388645013573819301396993041088782234723965610645795972735632259386678942658723374218497702728373253510668221460843692893157119362969141683846788307008594470839378698903964555806830095684319234830057112110046745094252937455819876945923393366316612953799035331034631039025141050433840806360637677929177247521035208032331912039593186471
e: 17 

Public key pk2.pem:
N: 28328155133789285412996485843849200476439065854667450765531808634398279813714628611356505714448351029445206816297052695426468253209725620716288482361102009067488713792451157452440320904129625879607490043398774470615404369860538006179371183327649709712501068068177273167061064338155527388645013573819301396993041088782234723965610645795972735632259386678942658723374218497702728373253510668221460843692893157119362969141683846788307008594470839378698903964555806830095684319234830057112110046745094252937455819876945923393366316612953799035331034631039025141050433840806360637677929177247521035208032331912039593186471
e: 65537

We can see that the N values for both keys are the same:

$$N_1=N_2$$

Common modulus attack

A common modulus attack can be used to recover the message if we have 2 ciphertexts of the same message, encrypted with 2 RSA keys that use the same modulus and relatively prime encryption exponents. That means that the greatest common divisor of $e_{1}$ and $e_{2}$ should be equal 1:

$$gcd(e_1,e_2)=1$$

The Euclidean Algorithm states that for given integers $e_1$and $e_2$, there is always an integral solution to the equation:

$$ae_{1}+be_{2}=gcd(e_1,e_2)$$

From Bézout's Theorem, we know that for positive integers $e_1$ and $e_2$, if $gcd(e_1,e_2)=1$, exist integers $a$ and $b$ such that:

$$ae_1+be_2=1$$

Based on this knowledge we can calculate the message as:

$$C_{1}^a\cdot C_{2}^b=(M_{1}^{e_{1}})^a\cdot(M_{2}^{e_{2}})^b=M_{1}^{ae_{1}}\cdot M_{2}^{be_{2}} =M^{ae_{1}+be_{2}}=M^{1}=M$$

All the attack assumptions have been met, so we can use this attack to get the message. Using all of this information we can implement a Python script to calculate the message:

from Crypto.PublicKey import RSA
from Crypto.Util.number import long_to_bytes,bytes_to_long

public_key_1 = RSA.importKey(open('pk1.pem', 'r').read())
public_key_2 = RSA.importKey(open('pk2.pem', 'r').read())
c1=bytes_to_long(open('file1.txt', 'rb').read())
c2=bytes_to_long(open('file2.txt', 'rb').read())

def egcd(a, b):
  if (a == 0):
    return (b, 0, 1)
  else:
    g, y, x = egcd(b % a, a)
    return (g, x - (b // a) * y, y)

cdg, a, b = egcd(public_key_1.e,public_key_2.e)
msg = pow(c1,a,public_key_1.n) * pow(c2,b,public_key_1.n) % public_key_1.n
print(long_to_bytes(msg))

After executing the script we get the flag.

Flag:

RS{Y0U_C4NT_R3AD_M3_R1GHT??}