Introduction Link to heading

The challenge as hosted on Hack The Box entails the following

Challenge name: RSAisEasy
Challenge Points: 10 points
Challenge Diff: Easy
Challenge Creator: [ryaagard](https://app.hackthebox.com/users/222411)

The challenge tests the challenger’s ability to detect flaws in arithmetic logic and basics in Number Theory. The challenge is quite simple as it implements basic RSA.

The challenge Link to heading

Zip file:

└─$ ls -la
-rw-r--r--  1 pyp pyp 1434 May 22  2021 output.txt
-rw-r--r--  1 pyp pyp  474 May 22  2021 RSAisEasy.py
-rw-r--r--  1 pyp pyp 1385 Dec 28 15:30 RSAisEasy.zip
-rw-r--r--  1 pyp pyp   69 Dec 28 16:05 secrets.py (Implementation of mine)

The secrets.py is a required module in the RSAisEasy.py and it contains the following:

flag1 = b"HTB{FAKE_FLAG_FOR"
flag2 = b"_TESTING_ON_THE_LOCAL_SERVER}"

RSAisEasy.py Link to heading 

#!/usr/bin/env python3
from Crypto.Util.number import bytes_to_long, getPrime
from secrets import flag1, flag2
from os import urandom

flag1 = bytes_to_long(flag1)
flag2 = bytes_to_long(flag2)

p, q, z = [getPrime(512) for i in range(3)]

e = 0x10001

n1 = p * q
n2 = q * z

c1 = pow(flag1, e, n1)
c2 = pow(flag2, e, n2)

E = bytes_to_long(urandom(69))

print(f'n1: {n1}')
print(f'c1: {c1}')
print(f'c2: {c2}')
print(f'(n1 * E) + n2: {n1 * E + n2}')

The script entails the following:

  • It imports a few functions used to generate prime numbers and convert bytes to integers.
  • It then import two flags, from the secrets(this caused us to guess but don’t worry because on the output.txt it got from the server)
  • It converts the flags to integers from bytes
  • Initializes three primes p, q, z of 512-bits and public exponent e of known value = 0x10001
  • It then calculates two moduli, n1 and n2 with a common factor q –> The common factor q is the GCD of the two numbers.
  • It then encrypts the flags using the two different moduli, same e giving c1 and c2.
  • It then gives the output of n1,c1,c2 and (n1 * E) + n2 where E is a random number The last output is what breaks the RSA system, this is because of the given values.

The attack Link to heading

Let us understand what we have first:

  • n1 –> First modulus, product of p and q
  • c1 and c2 –> CIphertext of both flags (encrypted)
  • (n1 * E ) + n2 –> This can be interpreted as product of n1 remainder is n2 modulo n1 Because of the above property we can be able to recover n2 and q can be recovered from two ways. We will discuss both of them.

Proof of concept Link to heading

  • Recovering n2: 
    (n1 * E + n2) mod n1 ≅ (n1 * E) mod n1 + n2 mod n1
(n1 * E) mod n1 + n2 mod n1 ≅ n1 mod n1 * E mod n1 + n2 mod n1
n1 mod n1 * E mod n1 + n2 mod n1 ≅ (0 * E) mod n1  + n2 mod n1 
(0 * E) mod n1  + n2 mod n1 ≅ 0 + n2 mod n1 ≅ n2 mod n1
Makes the answer n2 mod n1 if n2 < n1 we should be able to capture n2

# Proof through python
└─$ python3 -i RSAisEasy.py
n1: 92562127319911401213124154291661518376061048040176170006196020884496981597399578968567097674484018868453862495498828784896652605342087203489428068057112945167669715614267081386905784019173684510665248542428846503270774979184638997154896043687544251090744330497334676748724846670684190709759296879419967125939
c1: 50291565571649610953081821690459960598918359237049578126294207401600804593311061614972805851016901547430630529989933276034588119723791999202433242786688334655594822568332218429145506251047211248333812983958996085290064464898696312256520766991564617515627077207829928749292091068481593338401046895660331928158
c2: 81546162894727525942978635887768251774244271039054268363189874693654355422146202392590421509242903210826675803222855061094727895654129662155085558015339850830892443425873689357068529777269411685758163126960291365297833876459038616158148678381512473785822582297121451151745009793169605385645286052459797631239
(n1 * E) + n2: 535315960508762109039386873542567779541699775358191108985324928732383842947496869011415568825361505761289055837928847569005070849001900611117952785339303454746450538959015830466834716302325879737110232685434551231987894676942046770366765111874398769641315030858080289200270551870809988928565681826022392250572944638184259940607061494733931371108030528613146410359673964826711187839587611642597252612666559102062142837918155675543574881536207827836738194890599713632236609452
>>> beta = 535315960508762109039386873542567779541699775358191108985324928732383842947496869011415568825361505761289055837928847569005070849001900611117952785339303454746450538959015830466834716302325879737110232685434551231987894676942046770366765111874398769641315030858080289200270551870809988928565681826022392250572944638184259940607061494733931371108030528613146410359673964826711187839587611642597252612666559102062142837918155675543574881536207827836738194890599713632236609452
>>> beta % n1 == n2
True
  • Recovering q:
    1. There are two ways to recover q but without n2 you cannot decrypt the second flag:
    # First method --> gcd of beta(n1 * E + n2) and n1
n1 = p * q
n2 = q * z
beta = (p * q * E + q * z) --> (q * (p *E) + q (z)) --> q (p * E + z)
Because of the equations above:
q is common to beta and n1 which we both know, thus GCD(beta, n1) == q

    >>> from math import gcd
>>> gcd(beta,n1) == q
True

    # 2nd method --> gcd of n1 and n2 (you must have recovered n2)
n1 = p * q
n2 = q * z
since q is common and n1 and n2 are known(after n2 has being recovered), thus GCD(n1,n2) == q

With q recovered `p and z` can be calculated and corresponding phi's. From that the private exponents `d1 and d2` can be found and the messages reversed.
# The solution
Knowing the details above let us write a python script to solve the challenge:
```python
from Crypto.Util.number import GCD,long_to_bytes

e = 0x10001
n1 = 101302608234750530215072272904674037076286246679691423280860345380727387460347553585319149306846617895151397345134725469568034944362725840889803514170441153452816738520513986621545456486260186057658467757935510362350710672577390455772286945685838373154626020209228183673388592030449624410459900543470481715269
c1 = 92506893588979548794790672542461288412902813248116064711808481112865246689691740816363092933206841082369015763989265012104504500670878633324061404374817814507356553697459987468562146726510492528932139036063681327547916073034377647100888763559498314765496171327071015998871821569774481702484239056959316014064
c2 = 46096854429474193473315622000700040188659289972305530955007054362815555622172000229584906225161285873027049199121215251038480738839915061587734141659589689176363962259066462128434796823277974789556411556028716349578708536050061871052948425521408788256153194537438422533790942307426802114531079426322801866673
beta = 601613204734044874510382122719388369424704454445440856955212747733856646787417730534645761871794607755794569926160226856377491672497901427125762773794612714954548970049734347216746397532291215057264241745928752782099454036635249993278807842576939476615587990343335792606509594080976599605315657632227121700808996847129758656266941422227113386647519604149159248887809688029519252391934671647670787874483702292498358573950359909165677642135389614863992438265717898239252246163

n2 = beta % n1
print(f"n2: {n2}")
q = GCD(beta, n1) # Since q is a common factor(the largest)
p = n1 // q
z = n2 // q
print(f"P: {p}\nQ: {q}\nZ: {z}")
phi_1,phi_2 = (p-1) * (q-1), (q-1) * (z-1)
print(f"Phi_1: {phi_1}\n, Phi_2: {phi_2}")
d_1,d_2 = pow(e,-1,phi_1),pow(e,-1,phi_2)
print(f"D_1: {d_1}\nD_2: {d_2}")
flag1,flag2 = pow(c1,d_1,n1),pow(c2,d_2,n2)
flag = long_to_bytes(flag1) + long_to_bytes(flag2)
print(f"FLAG: {flag.decode()}")

Running we recover the flag:

FLAG: HTB{1_m1ght_h4v3_m3ss3d_uP_jU$t_4_l1ttle_b1t?}

Notes:

  • We see that the last part broke the RSA system revealing a whole system of secrets. The common factor q allowed it easy to find the respective primes and this made the system also insecure. For future use, different co-prime moduli should encrypt different messages.

“Dreaming, after all, is a form of planning.” — Gloria Steinem