Skip to content

Instantly share code, notes, and snippets.

@neex neex/rsa_last_bit.sage Secret
Created Sep 3, 2018

Embed
What would you like to do?
# This is sage script!
from Crypto.PublicKey import RSA
from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes, bytes_to_long
import random
from rand_crack import RandCrack # https://github.com/tna0y/Python-random-module-cracker/blob/master/randcrack.py
TESTING = False
BLOCK_SIZE = 16
### Protocol parsing functions
if not TESTING:
from pwn import *
context(log_level='debug')
#r = process('python server.py', shell=True)
r = remote('crypto.chal.ctf.westerns.tokyo', 5643)
def skip_menu():
r.readuntil(' get encrypted key\n')
# Send multiple messages at once to make exploit work faster
def send_prepared(msgs):
r.send("".join(msgs))
def encrypt_rsa_prepare(m):
return "1\n{}\n".format(long_to_bytes(int(m)))
def encrypt_rsa_recv():
skip_menu()
r.readuntil('RSA: ')
s = r.readline().strip()
return bytes_to_long(s.decode('hex'))
def get_decrypted_rsa_last_byte_prepare(c):
return "2\n{}\n".format(long_to_bytes(c).encode('hex'))
def get_decrypted_rsa_last_byte_recv():
skip_menu()
r.readuntil('RSA: ')
s = r.readline().strip()
return bytes_to_long(s.decode('hex')) % 256
def get_encrypted_aes_key():
skip_menu()
r.send("4\n")
r.readuntil('here is encrypted key :)\n')
c = Integer(bytes_to_long(r.readline().strip().decode('hex')))
return c
def pad(s):
n = 16 - len(s)%16
return s + chr(n)*n
def get_encrypted_flag():
skip_menu()
r.send("3\n")
r.readuntil('another bulldozer is coming!\n')
return r.readline().strip().decode('hex')
def get_randbits_prepare():
return "1\n\n"
def get_randbits_recv():
skip_menu()
r.readuntil('AES: ')
s = r.readline().strip()
return s.decode('hex')
else:
privkey = RSA.generate(1024)
pubkey = privkey.publickey()
aeskey = os.urandom(16)
flag = 'FLAG' * 100
def encrypt_rsa_prepare(m):
return m
def encrypt_rsa_recv():
global prepared_msgs
m = prepared_msgs[0]
prepared_msgs = prepared_msgs[1:]
return Integer(bytes_to_long(pubkey.encrypt(long_to_bytes(int(m)), 0)[0]))
def get_encrypted_aes_key():
return Integer(bytes_to_long(pubkey.encrypt(aeskey, 0)[0]))
def get_decrypted_rsa_last_byte_prepare(c):
return c
def send_prepared(msgs):
global prepared_msgs
prepared_msgs = msgs
def get_decrypted_rsa_last_byte_recv():
global prepared_msgs
c = prepared_msgs[0]
prepared_msgs = prepared_msgs[1:]
return Integer(bytes_to_long(privkey.decrypt(long_to_bytes(int(c)))[-1]))
def pad(s):
n = 16 - len(s)%16
return s + chr(n)*n
def get_encrypted_flag():
iv = long_to_bytes(random.getrandbits(BLOCK_SIZE*8), 16)
print("real iv was {}".format(iv.encode('hex')))
aes = AES.new(aeskey, AES.MODE_CBC, iv)
return '#' * 16 + aes.encrypt(pad(flag))
def get_randbits_prepare():
return None
def get_randbits_recv():
return long_to_bytes(random.getrandbits(BLOCK_SIZE*8), 16)
### Exploit
def recover_n():
nums = [37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113]
preps = map(encrypt_rsa_prepare, nums)
send_prepared(preps)
t = None
for pp in nums:
c = encrypt_rsa_recv()
nd = pp ** e - c
if t is None:
t = nd
else:
t = gcd(t, nd)
return t
def recover_m(c):
nums = [(Zmod(n)(c) / Zmod(n)(2)**(e * i)) for i in xrange(128)]
preps = map(get_decrypted_rsa_last_byte_prepare, nums)
send_prepared(preps)
def get_last_bit(nn):
return get_decrypted_rsa_last_byte_recv() % 2
bits = map(get_last_bit, nums)
found = 0
nk = 0
for i in xrange(128):
for fb in range(2):
assert (found + 2 ** i * fb + nk * n) % (2 ** i) == 0
if ((found + 2 ** i * fb + nk * n) // (2 ** i)) % 2 == bits[i]:
found = found + 2 ** i * fb
if bits[i] == 1:
nk = nk + 2 ** i
break
return found
def recover_rand_state():
r = RandCrack()
send_prepared([get_randbits_prepare() for _ in xrange(200)])
for _ in xrange(200):
b = get_randbits_recv()[:16]
b = bytes_to_long(b)
for _ in xrange(4):
r.submit(b % (2 ** 32))
b //= 2 ** 32
return r
if __name__ == "__main__":
e = 65537
n = recover_n()
print "Recovered n={}".format(n)
if TESTING:
assert n == pubkey.n
encrypted_aes_key = get_encrypted_aes_key()
aes_key = recover_m(encrypted_aes_key)
print "Recovered aes key={}".format(aes_key)
if TESTING:
assert aes_key == bytes_to_long(aeskey)
rp = recover_rand_state()
real_iv = long_to_bytes(rp.predict_getrandbits(BLOCK_SIZE*8), 16)
print("predicted iv was {}".format(real_iv.encode('hex')))
encrypted_flag = get_encrypted_flag()[16:]
flag = AES.new(long_to_bytes(int(aes_key), 16), AES.MODE_CBC, real_iv).decrypt(encrypted_flag)
print "Recovered flag={!r}".format(flag)
print "n={}".format(n)
print "encrypted aes key={}".format(encrypted_aes_key)
print "aes key={}".format(aes_key)
print "encrypted flag={!r}".format(encrypted_flag)
print "flag={!r}".format(flag)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.