niteCTF - Rabin to the Rescue

December 12, 2021

Another fun CTF that gave me plenty of challenges to learn from. I solved a good amount of the Crypto challenges in this one as well as the crypto related pwn challenge. This one got some good use out of my own RSA tooling so I decided to write it up.

Rabin to the Rescue - Crypto - 443 points

It may look like a piece of cake, but you need to dive deep into it.

nc rabin.challenge.cryptonite.team 1337

The challenge comes with one rabin_to_the_rescue.py which is the python source of the service running online. The code looks like this:

from Crypto.Util.number import *
from sympy import *
import random

def mixer(num):
while(num>1):
if(int(num) & 1):
num=3*num+1
else:
num=num/2
return num

def gen_sexy_primes():
p=getPrime(256)
q=p+6

while((p%4!=3) or (q%4!=3)):
p=getPrime(256)
q=nextprime(p+1)
return p, q

p, q=gen_sexy_primes()
n=p*q

def encrypt(m, e, n):
return pow(m, e, n)

e=int(mixer(q-p))*2

print("________________________________________________________________________________________________")
print("\n\n")
print("-----------------------------------")
print("-----------------------------------")
print("-----------------------------------")
print("               /\\")
print("            __/__\\__")
print("            \\/    \\/")
print("            /\\____/\\")
print("            ``\\  /``  ")
print("               \\/")
print("-----------------------------------")
print("-----------------------------------")
print("-----------------------------------")
print("\n\n")
print("Welcome to the Encryption challenge!!!!")
print("\n")
print("=> [G]et Flag")
print("=> E[x]it")
print("________________________________________________________________________________________________")

while(true):
choice=input(">>")
if choice.upper()=='E':
print("Enter message in hex:")
try:
m=bytes_to_long(bytes.fromhex(input()))
except:
print("Wrong format")
exit(0)
ciphertext=encrypt(m,e,n)
print(hex(ciphertext)[2:])
elif choice.upper()=='G':
with open('flag.txt','rb') as f:
t=random.randint(2, 2*5)
for i in range(t):
ciphertext=encrypt(flag,e,n)
print(hex(ciphertext)[2:])
elif choice.upper()=='X':
print("Exiting...")
break
else:

So its a service that will generate an “RSA” like set of encryption parameters, and then offers to do two things:

• Encrypt an arbitrary plaintext with the RSA parameters.
• Show you an encrypted flag.

There’s a few bugs in the implementation that help us and a few bugs that hinder us. Let’s explain

The Bugs

Prime Selection

This is how the large primes are chosen:

def gen_sexy_primes():
p=getPrime(256)
q=p+6

while((p%4!=3) or (q%4!=3)):
p=getPrime(256)
q=nextprime(p+1)
return p, q

The first bug is that the prime selection method is really weak for RSA. It wants “sexy primes”. Sexy primes are when two primes differ by just 6. Any modulus generated with such primes is trivially factorable with something like Fermat Factorisation method.

Exponent Selection

The exponent is selected by this method:

def mixer(num):
while(num>1):
if(int(num) & 1):
num=3*num+1
else:
num=num/2
return num

e=int(mixer(q-p))*2

Since p - q is always 6, this function always returns 2. It will never not be 2. This is a bug because RSA does not work properly with a modulus of 2 so we need to work around that later.

Encryption Rounds

I don’t know what is intended in this section of the code, maybe they intended for the flag to be encrypted multiple times?

t=random.randint(2, 2*5)
for i in range(t):
ciphertext=encrypt(flag,e,n)

Anyway it doesn’t do anything except encrypt the flag once, but repeatedly. Not real useful for security but necessary for us to make our lives easier.

The Solutions

Even though 2 is an invalid modulus, I still plan on solving this via RSA methods. So in order to solve this problem we need the modulus used in the encryption.

Since the server will encrypt any plaintext, we can use that as an oracle to learn the modulus using this method discussed here.

Since the exponent is only 2 though, encrypting small values like suggest 2, 3, 4 and 9 is insufficient. We need some value that is guaranteed to wrap modulo n.

So in order to do that I chose these numbers instead:

• e2 = 2^1000
• e4 = (2^1000)^2
• e3 = 3^1000
• e9 = (3^1000)^2

With these numbers chosen I connected to the server and asked it to encrypt my values as well as send me the ciphertext:

-----------------------------------
-----------------------------------
-----------------------------------
/\
__/__\__
\/    \/
/\____/\
``\  /``
\/
-----------------------------------
-----------------------------------
-----------------------------------

Welcome to the Encryption challenge!!!!

=> [G]et Flag
=> E[x]it
________________________________________________________________________________________________
>>e
Enter message in hex:
010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
657881fe3b2185abc8f6f97c2ba956a93711d718ac25d8c5d43f716d686bf092eeb05deb3cd65a4b733a7631781144a52306b939570d1ccfc7a1577394bd70c
>>e
Enter message in hex:
0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
30cd23bbc0e674d5ac7b5119051d79c1694eba71ffb99dd2849b504b8b52595bae6b5dc5ffcaef70f19286c56103fc0e7dd812aa732b5175dca224cedec42309
>>e
Enter message in hex:
>>e
Enter message in hex:
>>g
>>

With these numbers collected I want to calculate the following:

• gcd(e2^2 - e4, e3^2 - e9)

For this I have tooling already built; goRsaTool:

\$ cat > findmod.txt
e2 = 0x657881fe3b2185abc8f6f97c2ba956a93711d718ac25d8c5d43f716d686bf092eeb05deb3cd65a4b733a7631781144a52306b939570d1ccfc7a1577394bd70c
e4 = 0x30cd23bbc0e674d5ac7b5119051d79c1694eba71ffb99dd2849b504b8b52595bae6b5dc5ffcaef70f19286c56103fc0e7dd812aa732b5175dca224cedec42309

\$ goRsaTool -key findmod.txt -attack oraclemodulus
Recovered modulus:
n = 3823764509294606690677150613108312680560894488443794278642334173900438477843053351537343539446110446266124970385048950250278942540622478152965517651430033

Now we have n its a trivial matter to find the primes, I create a fake key with a fake exponent and factor the primes quickly. It was during writing this challenge that I improved my tool to print out the key’s prime numbers during verbose mode operation.

\$ cat > fakekey.txt
n = 3823764509294606690677150613108312680560894488443794278642334173900438477843053351537343539446110446266124970385048950250278942540622478152965517651430033
e = 65537

\$ goRsaTool -key fakekey.txt -attack fermat -verbose
rsatool: rsatool.go:94: starting up...
2021/12/13 22:28:42 fermat factorization attempt beginning with timeout 5m0s
Prime 0: 61836595227216437443312015875694562668835858514683229972362574341252303164867
Prime 1: 61836595227216437443312015875694562668835858514683229972362574341252303164699
...

Now we have at least one prime we can find the plaintext even if the real exponent is 2 by using my tool’s defectivee mode. We just need a partial known plaintext. Since we know the flag format is nite{we can use that:

\$ python -c "from Crypto.Util.number import bytes_to_long; print(bytes_to_long(b'nite{'))"

474215638395

\$ cat > realkey.txt
n = 3823764509294606690677150613108312680560894488443794278642334173900438477843053351537343539446110446266124970385048950250278942540622478152965517651430033
e = 2
p = 61836595227216437443312015875694562668835858514683229972362574341252303164867
kpt = 474215638395

\$ goRsaTool -key realkey.txt -attack defectivee
-----BEGIN RSA PRIVATE KEY-----
MIIBNgIBAAJASQIr7XFz2T5BWc0I3l1ealqLlIeMqnU/gL6irsRV3EAnDa/SqqiO
LVDTeEtMVk7kpBi9ByGGZ518hNZsL/dKkQIBAgJACSBFfa4ueyfIKzmhG8urzUtR
cpDxlU6n8BfUVdiKu4fitCSH8orIlTIxhW60AX3AJj634ZK7OhtdKa7diyxj9wIh
AIi2RcmLKSTB36OmatYlMHG5EX79RdZLYUmbr7/rShXDAiEAiLZFyYspJMHfo6Zq
1iUwcbkRfv1F1kthSZuvv+tKFRsCICItkXJiykkwd+jpmrWJTBxuRF+/UXWS2FJm
6+/60oVxAiAiLZFyYspJMHfo6Zq1iUwcbkRfv1F1kthSZuvv+tKFRwIgIv3kJd8M
DfrD6FzhcLc7ozPwqyt+EMECCzicOL2/Jxg=
-----END RSA PRIVATE KEY-----

Recovered plaintext:

Which yeah was the flag!

niteCTF - CBC-Jail

A unique combination of Python jailbreak and crypto flaw that had me learning a lot about AES-CBC mode. Super fun for me to get this solu...… Continue reading

HTB CyberSanta 2021 - Crypto Writeups

Published on December 04, 2021

TFC CTF 2021 - Jam

Published on November 28, 2021