Write-up: RSA: Primes
Yay, more crypto :D
After opening the zip, we get a single file:
$ ls -la
-rw-rw-r-- 1 neowo neowo 191 Sep 27 15:36 pubkey.pem
And a cipher: YxM055BCDnkM/WH81o0XfxLHBVvOzcEXDj6fe2WNiUcvsNTSlov/aILkAuBAy1UWTayuoRO8jWrWqLZqMLiHoyd9lezwBQOM
The challenge’s title tells us the algorithm used was RSA, we have the public key, and now we need the private key! But how do? :(
A quick explanation of RSA
RSA is an asymmetrical encryption algorithm (trust me, it’s easier than it seems).
Why asymmetrical?
Imagine you’re trying to send some data to your friend. You would like to make sure that only yourself and your friend can read the data, so you use encryption.
Symmetrical encryption algorithm work like a lock: you put a lock on your data, and using the unique key can both open (decrypt) and close (encrypt) the lock. Once the lock is closed, its content (the data) is unreadable to an external eye. Assuming perfect encryption, the only way to open the lock is to know the key (or try every possible combination, which can take billions of millions of tries). Sounds fancy? But it doesn’t work when on a network. Your lock is perfect and the data is unreadable, but your friend doesn’t know the key! So you would need to share the key with them, but any external individual on the network can see you sharing the key. The algorithm is fine, the issue therefore lays in how to share the key with your peer and ensure that them and only them can receive the key.
So what do? Well, we use asymmetrical encryption algorithms! Those work by generating a pair of keys instead of a single key.
This time, instead of having a single lock for both encryption and decryption, you will have a unique key for encryption and its pair key both decryption. The one used for encryption is called “public key”, and the one used for decryption is a “private key”. It follows that your friend can share their public key freely on the internet, you will receive it, but it doesn’t matter who else does as that key can only be used for encryption. You can now use that key to close the lock on your data (encrypt), send it, and only your friend who knows the private key will be able to open the lock (decrypt it)! As long as the private key remains private, assuming perfect encryption, an attacker will not be able to read the data or open the lock.
Now how does RSA work?
Well it follows these steps:
Pretty cool huh? The whole premise of RSA resides in a very simple fact:
Multiplying two integers p*q=n is very easy for a computer, but factorizing that product is very hard.
Furthermore, by ensuring that both p and q are primes, we know that n will have a unique integer factorizing solution (aka there will be a single pair (p,q) such that p*q=n
With big primes, it gets exponentially harder to factorize n.
Flaw?
The challenge’s title hints to us that there’s something wrong with the primes.
We use the RsaCtfTool, available on github:
RsaCtfTool,
From which we can:
$ python3 RsaCtfTool.py --dumpkey --public pubkey.pem
private argument is not set, the private key will not be displayed, even if recovered.
['pubkey.pem']
Details for pubkey.pem:
n: 101275698317249343122448595496210998756554971585207628863575099522765893004385037141284938912498830190371729638439414839307538793230702339248933840573417397004415170718138121
e: 65537
An experienced user will notice that n isn’t that big, weird.
We can deduce that the input primes are small!
From here, it’s time to ex-ex-ex-explooooit
Exploit
We have a very basic solution (please don’t try to factorize it yourself):
Use ✨factordb✨
And wooow
Now that we have p and q, we can reconstruct the private key and decipher the message.
We convert our cipher to an int format:
95719788901704825705765295176270645491358687146207915267901398776198873132751367890722301082465220611788405772046955814716692665756172556415036572377530190652837229417005964
And now:
$ python3 RsaCtfTool.py --publickey pubkey.pem --decrypt 95719788901704825705765295176270645491358687146207915267901398776198873132751367890722301082465220611788405772046955814716692665756172556415036572377530190652837229417005964
private argument is not set, the private key will not be displayed, even if recovered.
['pubkey.pem']
[*] Testing key pubkey.pem.
attack initialized...
attack initialized...
[*] Performing system_primes_gcd attack on pubkey.pem.
100%|█████████████████████████████████████████████████████████████████████████████████| 7007/7007 [00:00<00:00, 745358.56it/s]
[+] Time elapsed: 0.0398 sec.
[*] Performing mersenne_primes attack on pubkey.pem.
25%|█████████████████████▋ | 13/51 [00:00<00:00, 304614.26it/s]
[+] Time elapsed: 0.0005 sec.
[*] Performing pastctfprimes attack on pubkey.pem.
[+] loading prime list file data/pastctfprimes.txt...
100%|███████████████████████████████████████████████████████████████████████████████████| 121/121 [00:00<00:00, 927807.65it/s]
[+] loading prime list file data/visa_emv.txt...
100%|████████████████████████████████████████████████████████████████████████████████████████| 2/2 [00:00<00:00, 79137.81it/s]
[+] loading prime list file data/ti_rsa_signing_keys.txt...
100%|█████████████████████████████████████████████████████████████████████████████████████| 34/34 [00:00<00:00, 695640.66it/s]
[+] Time elapsed: 0.0018 sec.
[*] Performing fibonacci_gcd attack on pubkey.pem.
100%|█████████████████████████████████████████████████████████████████████████████████| 9999/9999 [00:00<00:00, 144549.92it/s]
[+] Time elapsed: 0.0695 sec.
[*] Performing smallq attack on pubkey.pem.
[+] Time elapsed: 0.2861 sec.
[*] Performing lucas_gcd attack on pubkey.pem.
100%|█████████████████████████████████████████████████████████████████████████████████| 9999/9999 [00:00<00:00, 162713.23it/s]
[+] Time elapsed: 0.0619 sec.
[*] Performing factordb attack on pubkey.pem.
[*] Attack success with factordb method !
[+] Total time elapsed min,max,avg: 0.0005/0.2861/0.0766 sec.
Results for pubkey.pem:
Decrypted data :
HEX : 0x0002c1c91c0bdda8ff3818c931bd35a23c0f1564011ca32f90bbf19c501e4f1f00496e74616b6532347b42455f284052656675215f774954485f354d406c6c5f7037496d4573217d
INT (big endian) : 10404719823297572086251016212021044622273469792252667399041607561274203647100092678887835618843952598783471793780218517464720824656465547998895536933695764791090151104893
INT (little endian) : 120893037687015537916888648522186785322132984375523940618919293104915377062122868278390351737679136580813474497213186117480797425575547679580174663874020601028253116981641728
utf-16 : Ȁ직ଜ㣿줘봱ꈵ༼搕ᰁ⾣뮐鳱Ṑ䤀瑮歡㉥笴䕂⡟剀晥ⅵ睟呉彈䴵汀彬㝰浉獅紡
STR : b'\x00\x02\xc1\xc9\x1c\x0b\xdd\xa8\xff8\x18\xc91\xbd5\xa2<\x0f\x15d\x01\x1c\xa3/\x90\xbb\xf1\x9cP\x1eO\x1f\x00Intake24{BE_(@Refu!_wITH_5M@ll_p7ImEs!}'
PKCS#1.5 padding decoded!
HEX : 0x00496e74616b6532347b42455f284052656675215f774954485f354d406c6c5f7037496d4573217d
INT (big endian) : 2393320521445260043900152343482097827754771662171950322138051811578524591165399694695948558717
INT (little endian) : 1044052650602451218010412249961467926624694396163635744679032495111926056092627750919782605408512
utf-8 : Intake24{BE_(@Refu!_wITH_5M@ll_p7ImEs!}
utf-16 : 䤀瑮歡㉥笴䕂⡟剀晥ⅵ睟呉彈䴵汀彬㝰浉獅紡
STR : b'\x00Intake24{BE_(@Refu!_wITH_5M@ll_p7ImEs!}'
Flagged! :D