Crypto 1 - RSA Leaks

Challenge Description

DinoCorp has been experimenting with dinosaurs for years. Their labs are located on an island in the middle of the ocean. We managed to intercept an encrypted message from the head scientist. It looks like something is wrong. Can you decrypt the message?

  • This challenge has a downloadable part.

Steps

Unzip challenge files:

unzip crypto_rsa_leaks.zip

First thoughts

If we check the files we have:

  • top_secret.enc
  • chall.py

Encrypted file

The first is the encrypted file:

cat top_secret.enc
PΩ&mh|��A����ۆ���] |��<EM�N��u���J]{��V��,�ۨ���lM�c�t3�F"%��c�R���3�߳��lBr�t5���e��{�T���5�.��h����N��E.D��I	]��V|��.l)M��V����-��:%��'x�c1��޲k��݅a�2�)����b����c�R�|,��)>s�-��7�~�N&-���Xf7cѺ�)�>��

Maybe some flag is in there…

Python file

The python script looks like the code used to encrypt that file which will be very usefull for the decryption later.

If we inspect the python file we can see that the file is encrypted using the AES algorithm.

from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
import os

def encrypt(key, msg):
	crypto = AES.new(key, AES.MODE_CBC,key)
	return crypto.encrypt(pad(msg, 16))

key = os.urandom(16)

dt = open('top_secret.txt', 'rb').read()
enc_dt = encrypt(key, dt)

open('top_secret.enc', 'wb').write(enc_dt)

We can see that the key that was used to encrypt top_secret.enc is random, so we can’t guess it.

AES Weakness

We can notice that the AES mode that is used is CBC which normally uses an Initialization Vector (iv) with the encryption key, that must be completely random and only used once. In the code it uses the key as the iv, so the only task is to find the encyption key and we can easily decrypt the file.

RSA Leak

The challenge is called RSA Leak, but we only see AES, where is RSA?? If we inspect the next lines of the python file we see:

e = 65537
p = getPrime(2048)
q = getPrime(2048)
n = p * q
phi = (p-1) * (q-1)
d = inverse(e,phi)
leak = d%(p-1)

m = bytes_to_long(key)
c = pow(m, e, n)

print("n =", n)
print("e =", e)
print("c =", c)
print("leak =", leak)

'''
n = 543346225106663839111039968130785919016674641442996947812903103961755757079710613958740656879366504536243949055081229279878847991991020265270521336740184071296007365845955543904514452178745251178017195685670677629615717682000756419358887339167959722314058630840417488268287438697328233522412108184658751013876152267533109001879057870100884570649142724035557404313469941702528743455730246416012857026044688799419871933126223604059106506915509486446055415017812904850452159015059157564683943172148086610263348065871518493559327939141603969951298317790806014999079897467791459559710128539993864924803946308721204182514260441583951453042844581691575723308340926826117020851043176059890812821074969931293813815379851313979195484143762712739522631708756764141004276382172566136550224343125782309848385520151311515356301666720087082869494478122289554751225720706466262056073529846239170626622207748133910502086300376146161254765393123697546740102010473067029287843821054608641705871287041674577944652663378334888090501981819169373536733106788513809866388068409564729035077680592083285548788178468014729687591248054282599589140714614678271338526650720345208366676617716192558887537911803293631187790827357732153175768489068993635898024052551
e = 65537
c = 342687544435106722668753497617515697889931274688490881240891816722749099146913989991258053161870598022267306801706896840975736768817716849174817550584877304834761138428220219383933451950538973937978550318148717726898756891201241849945349408391213670877684390668029494847973373888129660672608125871426900184315031308767595096908289192829052335676921218493543693489389075325900187437084099747465190092682284690309488373644355369940087232841306774773098886960660864202502969303605977242881124335312245227434434993200362631610909272954885316746210968474509770535407786066676696809998246503112517731735445573586194795029530624738419722131531334888597726145787478695795801946906624068441146103359904580816389357515942520450329471812204346735266376866571219351658484269996212380218802337897282338756083577264008672340254009688647002117044513595757383766430992134114562872758268410311932129930806546393458039299547554414131770457486019324332641141299808921605107811104106258801911298863427454394754299136469527954273925721710957719112643911294176392671506076508661460578503180302746649644657457691978605886382637184156205665012838070707129507637259169757513623029490781405370749894374763608925173066405668703470452660056668364569998124780301
leak = 10133216471752755080604184970259815785205981120172554626789548467233131819116108801216792157264987031671165719292412479618830500445861722282735722578711291141496054632488603107741733268902534656060845058658635517791685098389523659637487226838069605215006741618804094285713684089322777788183466907011464794698302853722754111358230154577743207775760592176122031328467302912224772973799738480446432346669849741723026153357388273187130779859516662464542786794102557681400604400186483607530002942528044503745837703412474159461539216180935911622191237331615647765264857848350920862479435982274570852168761683723103602763375
'''

These are all variables that are related to the RSA encryption. Besides the usuall public variables like:

  • n which is composed of two random secret prime numbers p q (n = p*q)
  • e, an integer with usuall value of 65537
  • c, the ciphertext

We also get a leak which is:

  • leak = d % (p-1)
  • where d is the secret private key.

If we search for weakness in the RSA encryption scheme, we can find information about the chinese remainder theorem, and that the leak value in reality is:

  • leak = dp = d%(p-1)

We will use that info shortly.

Attack Plan

Now we have enough to form an attack plan, although the details are not exact yet:

  • We have the n, e, c, dp RSA values as comment.
  • If we can find the d value we can decrypt the c ciphertext.
  • We decrypt c to the plain text m value using m = c^d mod n, which is the key and iv used for AES.
  • With the AES key we can decrypt the .enc file.

RSA-CRT

From the CRT (Chinese Remainder Theorem) implementation we can find that:

Part of Proof:

  • dp = d % (p-1)
  • e*dp = e*d % (p-1)
  • e*dp = 1 % (p-1)
  • e*dp - 1 = 0 % (p-1)

So we know:

  • e*dp - 1 = 0 % (p-1) which means e*dp - 1 equally divides p-1
  • So we can write: e*dp - 1 = k*(p-1), where k<e since k(p-1) is multiple of e*dp - 1
  • Solving for p we get: p = (e*dp-1+k)/k
  • We can try all possible k from 0-e=65537, such that N/p=q is a positive integer.
  • Then we find q as: q = N/p
  • Then d as: d = 1/e * (p-1) * (q-1)
  • Finally, decrypt m as: m = c^d mod n

We write the following python script to do all of these actions and also decrypt the encrypted file using the found key as the key and iv for the AES algorithm:

#!/usr/bin/python3

import sys
from Crypto.Util.number import inverse, long_to_bytes
from Crypto.Cipher import AES

#### Constant - Known Values of RSA
e = 65537
n = 543346225106663839111039968130785919016674641442996947812903103961755757079710613958740656879366504536243949055081229279878847991991020265270521336740184071296007365845955543904514452178745251178017195685670677629615717682000756419358887339167959722314058630840417488268287438697328233522412108184658751013876152267533109001879057870100884570649142724035557404313469941702528743455730246416012857026044688799419871933126223604059106506915509486446055415017812904850452159015059157564683943172148086610263348065871518493559327939141603969951298317790806014999079897467791459559710128539993864924803946308721204182514260441583951453042844581691575723308340926826117020851043176059890812821074969931293813815379851313979195484143762712739522631708756764141004276382172566136550224343125782309848385520151311515356301666720087082869494478122289554751225720706466262056073529846239170626622207748133910502086300376146161254765393123697546740102010473067029287843821054608641705871287041674577944652663378334888090501981819169373536733106788513809866388068409564729035077680592083285548788178468014729687591248054282599589140714614678271338526650720345208366676617716192558887537911803293631187790827357732153175768489068993635898024052551
dp = 10133216471752755080604184970259815785205981120172554626789548467233131819116108801216792157264987031671165719292412479618830500445861722282735722578711291141496054632488603107741733268902534656060845058658635517791685098389523659637487226838069605215006741618804094285713684089322777788183466907011464794698302853722754111358230154577743207775760592176122031328467302912224772973799738480446432346669849741723026153357388273187130779859516662464542786794102557681400604400186483607530002942528044503745837703412474159461539216180935911622191237331615647765264857848350920862479435982274570852168761683723103602763375
c = 342687544435106722668753497617515697889931274688490881240891816722749099146913989991258053161870598022267306801706896840975736768817716849174817550584877304834761138428220219383933451950538973937978550318148717726898756891201241849945349408391213670877684390668029494847973373888129660672608125871426900184315031308767595096908289192829052335676921218493543693489389075325900187437084099747465190092682284690309488373644355369940087232841306774773098886960660864202502969303605977242881124335312245227434434993200362631610909272954885316746210968474509770535407786066676696809998246503112517731735445573586194795029530624738419722131531334888597726145787478695795801946906624068441146103359904580816389357515942520450329471812204346735266376866571219351658484269996212380218802337897282338756083577264008672340254009688647002117044513595757383766430992134114562872758268410311932129930806546393458039299547554414131770457486019324332641141299808921605107811104106258801911298863427454394754299136469527954273925721710957719112643911294176392671506076508661460578503180302746649644657457691978605886382637184156205665012838070707129507637259169757513623029490781405370749894374763608925173066405668703470452660056668364569998124780301

def RSA_find_p():
    for k in range(1, e):
        p = (e*dp - 1 + k) // k
        # Check if p can divide n
        if n % p == 0:
            return p
    return -1


def AES_decrypt(key, msg):
        crypto = AES.new(key, AES.MODE_CBC,key)
        return crypto.decrypt(msg)

if __name__ == '__main__':

    if len(sys.argv) < 2:
        print('Usage:', sys.argv[0], '<top_secret.enc>')
        exit(1)

    top_secret_file = sys.argv[1]

    #### Find p
    p = RSA_find_p()
    print('p =', p)
    if p < 0:
        print('Can not find p')
        exit()

    #### Find q
    q = n // p
    print('q =', q)

    #### Find d
    phi = (p-1) * (q-1)
    d = inverse(e,phi)
    print('d =', d)

    #### Find m (Decrypt)
    m = pow(c, d, n)
    print('m         =', m)

    #### Find AES key
    key = long_to_bytes(m)
    print('m (bytes) = ', key)

    #### Decrypt file
    dt = open(top_secret_file, 'rb').read()
    print('Encrypted file:', dt)

    decr_dt = AES_decrypt(key, dt)
    print('Decrypted file:', decr_dt)

Run python script to do the above automatically and we get the flag:

python3 rsa_leak.py

# ...
Decrypted file: b'To DinoCorp,\nUnfortunately, our experiments failed. The situation got out of control. I have spent all my life\nstudying these beautiful animals. Trying to bring them back to life was wrong.\nPlease send help!!\nECSC{r54_l34k5_l34d_70_fl4g5}\x02\x02'

Flag

Flag: ECSC{r54_l34k5_l34d_70_fl4g5}

Resources