Skip to content

Instantly share code, notes, and snippets.

@sampritipanda
Created September 2, 2018 04:19
Show Gist options
  • Save sampritipanda/f9a2eff5664287aa110c92d3fe0399ba to your computer and use it in GitHub Desktop.
Save sampritipanda/f9a2eff5664287aa110c92d3fe0399ba to your computer and use it in GitHub Desktop.
Tokyo Westerns CTF 2018 - Mixed Cipher
from pwn import *
from randcrack import RandCrack
from gmpy import gcd
from Crypto.Util.number import long_to_bytes
from Crypto.Cipher import AES
# proc = remote('crypto.chal.ctf.westerns.tokyo', 5643)
proc = process('./server.py')
# context.log_level = 'debug'
BLOCK_SIZE = 16
def aes_decrypt(key, s):
iv = s[:BLOCK_SIZE]
aes = AES.new(key, AES.MODE_CBC, iv)
return aes.decrypt(s[BLOCK_SIZE:])
def encrypt(s):
proc.recvlines(6)
proc.sendline('1')
proc.recvuntil("text: ")
proc.sendline(s)
rsa = proc.recvline().strip().split()[1]
aes = proc.recvline().strip().split()[1]
return [int(rsa, 16), aes.decode('hex')]
def decrypt(c):
proc.recvlines(6)
proc.sendline('2')
proc.recvuntil("text: ")
s = long_to_bytes(c).encode('hex')
proc.sendline(s)
proc.recvline()
rsa = proc.recvline().strip().split()[1]
print rsa
return rsa.decode('hex')
def print_flag():
proc.recvlines(6)
proc.sendline('3')
proc.recvline()
proc.recvline()
return proc.recvline().strip().decode('hex')
def get_enc_key():
proc.recvlines(6)
proc.sendline('4')
proc.recvline()
return int(proc.recvline().strip(), 16)
rc = RandCrack()
for i in range(156):
iv = encrypt('a')[1][:16]
iv = iv[::-1]
rc.submit(u32(iv[0:4]))
rc.submit(u32(iv[4:8]))
rc.submit(u32(iv[8:12]))
rc.submit(u32(iv[12:16]))
a_enc = encrypt('a')[0]
rc.predict_getrandbits(128)
b_enc = encrypt('b')[0]
rc.predict_getrandbits(128)
e = 65537
n = gcd(ord('a')**e - a_enc, ord('b')**e - b_enc)
print 'N: ', n
enc_key = get_enc_key()
enc_flag = print_flag()
actual_iv = long_to_bytes(rc.predict_getrandbits(128), 16)
enc_flag = actual_iv + enc_flag[16:]
print 'Encrypted Key: ', enc_key
print 'Encrypted Flag: ', enc_flag.encode('hex')
bounds = [(0, 1), (1, 1)]
c = enc_key
for _ in range(0, n.bit_length(), 2):
print _, bounds
nm_half = bounds[0][0] * bounds[1][1] + bounds[1][0] * bounds[0][1]
dm_half = bounds[0][1] * bounds[1][1] * 2
g = gcd(nm_half, dm_half)
nm_half, dm_half = nm_half / g, dm_half / g
c = (pow(4, e, n) * c) % n
res = ord(decrypt(c)[-1]) % 4
if res == 0:
nm = bounds[0][0] * dm_half + bounds[0][1] * nm_half
dm = bounds[0][1] * dm_half * 2
g = gcd(nm, dm)
nm, dm = nm / g, dm / g
bounds[1] = (nm, dm)
elif res == 1:
nm = bounds[0][0] * dm_half + bounds[0][1] * nm_half
dm = bounds[0][1] * dm_half * 2
g = gcd(nm, dm)
nm, dm = nm / g, dm / g
bounds[0] = (nm, dm)
bounds[1] = (nm_half, dm_half)
elif res == 2:
nm = nm_half * bounds[1][1] + dm_half * bounds[1][0]
dm = dm_half * bounds[1][1] * 2
g = gcd(nm, dm)
nm, dm = nm / g, dm / g
bounds[0] = (nm_half, dm_half)
bounds[1] = (nm, dm)
else:
nm = nm_half * bounds[1][1] + dm_half * bounds[1][0]
dm = dm_half * bounds[1][1] * 2
g = gcd(nm, dm)
nm, dm = nm / g, dm / g
bounds[0] = (nm, dm)
key = long_to_bytes(bounds[1][0] * n / bounds[1][1])
print 'Key: ', key.encode('hex')
print aes_decrypt(key, enc_flag)
class RandCrack:
def __init__(self):
self.counter = 0
self.mt = []
self.state = False
def submit(self, num):
if self.state:
print("Already got enough bits")
return
bits = self._to_bitarray(num)
assert(all([x == 0 or x == 1 for x in bits]))
self.counter +=1
self.mt.append(self._harden_inverse(bits))
if self.counter == 624:
self._regen()
self.state = True
def _predict_32(self):
if not self.state:
print("Didn't recieve enough bits to predict")
return 0
if self.counter >= 624:
self._regen()
self.counter += 1
return self._harden(self.mt[self.counter-1])
def predict_getrandbits(self,k):
if not self.state:
print("Didn't recieve enough bits to predict")
return 0
if k == 0:
return 0
words = (k-1) // 32 + 1
res = []
for i in range(words):
r = self._predict_32()
if k < 32:
r = [0]*(32-k) +r[:k]
res = r + res
k -= 32
return self._to_int(res)
def predict_randbelow(self, n):
k = n.bit_length()
r = self.predict_getrandbits(k)
while r >= n:
r = self.predict_getrandbits(k)
return r
def predict_randrange(self, start, stop=None, step=1, _int=int):
# Adopted messy code from random.py module
# In fact only changed _randbelow() method calls to predict_randbelow()
istart = _int(start)
if istart != start:
raise ValueError("non-integer arg 1 for randrange()")
if stop is None:
if istart > 0:
return self.predict_randbelow(istart)
raise ValueError("empty range for randrange()")
# stop argument supplied.
istop = _int(stop)
if istop != stop:
raise ValueError("non-integer stop for randrange()")
width = istop - istart
if step == 1 and width > 0:
return istart + self.predict_randbelow(width)
if step == 1:
raise ValueError("empty range for randrange() (%d,%d, %d)" % (istart, istop, width))
# Non-unit step argument supplied.
istep = _int(step)
if istep != step:
raise ValueError("non-integer step for randrange()")
if istep > 0:
n = (width + istep - 1) // istep
elif istep < 0:
n = (width + istep + 1) // istep
else:
raise ValueError("zero step for randrange()")
if n <= 0:
raise ValueError("empty range for randrange()")
return istart + istep*self.predict_randbelow(n)
def predict_randint(self, a,b):
return self.predict_randrange(a, b+1)
def predict_choice(self, seq):
try:
i = self.predict_randbelow(len(seq))
except ValueError:
raise IndexError('Cannot choose from an empty sequence')
return seq[i]
def _to_bitarray(self, num):
k = [int(x) for x in bin(num)[2:]]
return [0] * (32-len(k)) + k
def _to_int(self, bits ):
return int("".join(str(i) for i in bits), 2)
def _or_nums(self, a, b):
if len(a) < 32:
a = [0]* (32-len(a))+a
if len(b) < 32:
b = [0]* (32-len(b))+b
return [x[0] | x[1] for x in zip(a, b)]
def _xor_nums(self, a, b):
if len(a) < 32:
a = [0]* (32-len(a))+a
if len(b) < 32:
b = [0]* (32-len(b))+b
return [x[0] ^ x[1] for x in zip(a, b)]
def _and_nums(self, a, b):
if len(a) < 32:
a = [0]* (32-len(a))+a
if len(b) < 32:
b = [0]* (32-len(b))+b
return [x[0] & x[1] for x in zip(a, b)]
def _decode_harden_midop(self, enc, and_arr, shift):
NEW = 0
XOR = 1
OK = 2
work = []
for i in range(32):
work.append((NEW,enc[i]))
changed = True
while changed:
changed = False
for i in range(32):
status = work[i][0]
data = work[i][1]
if i >= 32-shift and status == NEW:
work[i] = (OK,data)
changed = True
elif i < 32-shift and status == NEW:
if and_arr[i] == 0:
work[i] = (OK, data)
changed = True
else:
work[i] = (XOR, data)
changed = True
elif status == XOR:
i_other = i+shift
if work[i_other][0] == OK:
work[i] = (OK, data ^ work[i_other][1])
changed = True
return [x[1] for x in work]
def _harden(self, bits):
bits = self._xor_nums(bits, bits[:-11])
bits = self._xor_nums(bits, self._and_nums(bits[7:] + [0] * 7 , self._to_bitarray(0x9d2c5680)))
bits = self._xor_nums(bits, self._and_nums(bits[15:] + [0] * 15 , self._to_bitarray(0xefc60000)))
bits = self._xor_nums(bits, bits[:-18])
return bits
def _harden_inverse(self, bits):
# inverse for: bits = _xor_nums(bits, bits[:-11])
bits = self._xor_nums(bits, bits[:-18])
# inverse for: bits = _xor_nums(bits, _and_nums(bits[15:] + [0] * 15 , _to_bitarray(0xefc60000)))
bits = self._decode_harden_midop(bits, self._to_bitarray(0xefc60000), 15)
# inverse for: bits = _xor_nums(bits, _and_nums(bits[7:] + [0] * 7 , _to_bitarray(0x9d2c5680)))
bits = self._decode_harden_midop(bits, self._to_bitarray(0x9d2c5680), 7)
# inverse for: bits = _xor_nums(bits, bits[:-11])
bits = self._xor_nums(bits, [0] * 11 + bits[:11]+[0] * 10)
bits = self._xor_nums(bits, bits[11:21])
return bits
def _regen(self):
# C code translated from python sources
N = 624
M = 397
MATRIX_A = 0x9908b0df
LOWER_MASK = 0x7fffffff
UPPER_MASK = 0x80000000
mag01 = [self._to_bitarray(0), self._to_bitarray(MATRIX_A)]
l_bits = self._to_bitarray(LOWER_MASK)
u_bits = self._to_bitarray(UPPER_MASK)
for kk in range(0,N-M):
y = self._or_nums(self._and_nums( self.mt[kk], u_bits), self._and_nums(self.mt[kk+1],l_bits))
self.mt[kk] = self._xor_nums(self._xor_nums( self.mt[kk+M] , y[:-1]) , mag01[y[-1] & 1])
for kk in range(N-M-1, N-1):
y = self._or_nums(self._and_nums( self.mt[kk], u_bits), self._and_nums(self.mt[kk+1],l_bits))
self.mt[kk] = self._xor_nums(self._xor_nums( self.mt[kk+(M-N)] , y[:-1]) , mag01[y[-1] & 1])
y = self._or_nums(self._and_nums( self.mt[N-1], u_bits), self._and_nums(self.mt[0],l_bits))
self.mt[N-1] = self._xor_nums(self._xor_nums( self.mt[M-1] , y[:-1]) , mag01[y[-1] & 1])
self.counter = 0
if __name__ == "__main__":
import random, time
print("Testing random module cracker...")
cracker = RandCrack()
random.seed(time.time())
for i in range(624):
cracker.submit(random.randint(0,4294967294))
print("Guessing next 32000 random bits success rate: {}%"
.format(sum([random.getrandbits(32)==cracker.predict_getrandbits(32) for x in range(1000)])/10))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment