Tags: crypto rsa
Rating:
This RSA encryption service is so secure we're not even going to tell you how we encrypted it
nc be.ax 31124
Downloads
The challange gave the script running in server (main.py):
#!/usr/local/bin/python
import random
import time
import math
import binascii
from Crypto.Util.number import *
p, q = getPrime(512), getPrime(512)
n = p * q
phi = (p - 1) * (q - 1)
flag = open('./flag.txt').read().encode()
random.seed(int(time.time()))
def encrypt(msg):
e = random.randint(1, n)
while math.gcd(e, phi) != 1:
e = random.randint(1, n)
pt = bytes_to_long(msg)
ct = pow(pt, e, n)
return binascii.hexlify(long_to_bytes(ct)).decode()
def main():
print('Secure Encryption Service')
print('Your modulus is:', n)
while True:
print('Options')
print('-------')
print('(1) Encrypt flag')
print('(2) Encrypt message')
print('(3) Quit')
x = input('Choose an option: ')
if x not in '123':
print('Unrecognized option.')
exit()
elif x == '1':
print('Here is your encrypted flag:', encrypt(flag))
elif x == '2':
msg = input('Enter your message in hex: ')
print('Here is your encrypted message:', encrypt(binascii.unhexlify(msg)))
elif x == '3':
print('Bye')
exit()
if __name__ == '__main__':
main()
Basically two 512-bit primes are generated (p and q), n = p*q and phi = (p-1)*(q-1) are set, the flag is loaded from file and the random generator is initialized with time.time() as seed. This seed make possible to us to solve the challenge, since we can bruteforce it (let's back here after).
When we connect to server, there is a menu when we can choose between encrypt the flag or encrypt a known message. For both of them, it is used the same function to encrypt:
def encrypt(msg):
e = random.randint(1, n)
while math.gcd(e, phi) != 1:
e = random.randint(1, n)
pt = bytes_to_long(msg)
ct = pow(pt, e, n)
return binascii.hexlify(long_to_bytes(ct)).decode()
See that there is only one of the variables that is random (e) and that if gcd(e, phi) == 1 at first time, we don't need phi to encrypt any message locally. We don't know phi but we know it is necessarily divisible by 2. A random odd e and an even phi have a great chance to be coprimes.
Let's start by getting the seed. One way to do so is setting the seed as te epoch time before connect the server, encrypt one known message using server and try seed's sequentially until the locally encrypted known message results in the same ciphertext as the message encrypted in the server (assuming only that phi is even), so let's use the following encrypt function:
def encrypt(msg, n):
e = random.randint(1, n)
while e % 2 == 0:
e = random.randint(1, n)
pt = bytes_to_long(msg)
ct = pow(pt, e, n)
return binascii.hexlify(long_to_bytes(ct)).decode()
And this script to find the seed:
while True:
prox = False
seed = int(time.time())
conn = remote('be.ax', 31124)
data = conn.recvuntil(b'option: ').decode()
n = int(re.search(r'is: (\d+)', data).group(1))
print('n =', n)
conn.sendline(b'2')
txt = b'aa'
conn.sendlineafter(b'hex: ', txt)
data = conn.recvline().decode()
print(data)
ctxt = re.search(r'message: ([0-9a-f]+)', data).group(1)
random.seed(seed)
enc = encrypt(binascii.unhexlify(txt.decode()), n)
t0 = time.time()
while enc != ctxt:
seed += 1
random.seed(seed)
enc = encrypt(binascii.unhexlify(txt.decode()), n)
if time.time() - t0 > 10:
prox = True
break
if prox:
conn.close()
continue
As we are assuming that the only possible common factor between e and phi is 2, sometimes we won't find the seed. To avoid this situation, if it takes more than 10 seconds to find the seed, the connection is closed and it tries again.
Found the seed, now we can encrypt the flag using the server to get the ciphertext and get the cooresponding e using the seed locally.
But how can we find the flag given the ciphertext and the e if we didn't factorize n? That is possible because we know that the original message is the same and the n is the same, so we can use the Common Modulus Attack. Let's see how it works.
First we have to obtain two versions of encrypted flag and the e for each of them, so that the e's are coprimes:
random.seed(seed)
encrypt(binascii.unhexlify(txt.decode()), n)
e2 = e1 = random.randint(1, n)
conn.recvuntil(b'option: ')
conn.sendline(b'1')
data = conn.recvline().decode()
cflag2 = cflag1 = bytes_to_long(bytes.fromhex(re.search(r'flag: ([0-9a-f]+)', data).group(1)))
while gcd(e1, e2) != 1:
conn.recvuntil(b'option: ')
conn.sendline(b'1')
data = conn.recvline().decode()
cflag2 = bytes_to_long(bytes.fromhex(re.search(r'flag: ([0-9a-f]+)', data).group(1)))
e2 = random.randint(1, n)
while e2 % 2 == 0:
e2 = random.randint(1, n)
After we must find a and b such that a * e1 + b * e2 == 1 using the extended GCD algorithm:
def extended_gcd(x, y):
# a*x + b*y = 1
a = 0
b = 1
lasta = 1
lastb = 0
while y != 0:
quo = x // y
x, y = y, x % y
a, lasta = lasta - quo * a, a
b, lastb = lastb - quo * b, b
return lasta, lastb
After we have a and b, the flag can be determined with m == (c1 ** a * c2 ** b) % n, but one of them will be negative:
a, b = extended_gcd(e1, e2)
if a < 0:
print('a < 0')
cflag1 = inverse(cflag1, n)
a = -a
if b < 0:
print('b < 0')
cflag2 = inverse(cflag2, n)
b = -b
flag = long_to_bytes((pow(cflag1, a, n)*pow(cflag2, b, n)) % n)
if b'corctf' in flag:
print(flag)
break
conn.close()
It was important to check if the flag was found because of the e and phi relation discussed before. Now we have the full solver:
from pwn import *
from Crypto.Util.number import bytes_to_long, long_to_bytes, inverse
from math import gcd
def extended_gcd(x, y):
# a*x + b*y = 1
a = 0
b = 1
lasta = 1
lastb = 0
while y != 0:
quo = x // y
x, y = y, x % y
a, lasta = lasta - quo * a, a
b, lastb = lastb - quo * b, b
return lasta, lastb
def encrypt(msg, n):
e = random.randint(1, n)
while e % 2 == 0:
e = random.randint(1, n)
pt = bytes_to_long(msg)
ct = pow(pt, e, n)
return binascii.hexlify(long_to_bytes(ct)).decode()
while True:
prox = False
seed = int(time.time())
conn = remote('be.ax', 31124)
data = conn.recvuntil(b'option: ').decode()
n = int(re.search(r'is: (\d+)', data).group(1))
print('n =', n)
conn.sendline(b'2')
txt = b'aa'
conn.sendlineafter(b'hex: ', txt)
data = conn.recvline().decode()
print(data)
ctxt = re.search(r'message: ([0-9a-f]+)', data).group(1)
random.seed(seed)
enc = encrypt(binascii.unhexlify(txt.decode()), n)
t0 = time.time()
while enc != ctxt:
seed += 1
random.seed(seed)
enc = encrypt(binascii.unhexlify(txt.decode()), n)
if time.time() - t0 > 10:
prox = True
break
if prox:
conn.close()
continue
random.seed(seed)
encrypt(binascii.unhexlify(txt.decode()), n)
e2 = e1 = random.randint(1, n)
conn.recvuntil(b'option: ')
conn.sendline(b'1')
data = conn.recvline().decode()
cflag2 = cflag1 = bytes_to_long(bytes.fromhex(re.search(r'flag: ([0-9a-f]+)', data).group(1)))
while gcd(e1, e2) != 1:
conn.recvuntil(b'option: ')
conn.sendline(b'1')
data = conn.recvline().decode()
cflag2 = bytes_to_long(bytes.fromhex(re.search(r'flag: ([0-9a-f]+)', data).group(1)))
e2 = random.randint(1, n)
while e2 % 2 == 0:
e2 = random.randint(1, n)
assert gcd(e1, e2) == 1
a, b = extended_gcd(e1, e2)
if a < 0:
print('a < 0')
cflag1 = inverse(cflag1, n)
a = -a
assert a > 0
if b < 0:
print('b < 0')
cflag2 = inverse(cflag2, n)
b = -b
assert b > 0
flag = long_to_bytes((pow(cflag1, a, n)*pow(cflag2, b, n)) % n)
if b'corctf' in flag:
print(flag)
break
conn.close()
Running it, after at most a few tries:
corctf{y34h_th4t_w4snt_v3ry_h1dd3n_tbh_l0l}
