Babyring

Description

nc pwnable.org 10001


Files

#!/usr/bin/python2
import os,random,sys,string
from hashlib import sha256
from struct import pack, unpack
import SocketServer
from Crypto.Cipher import ARC4

from flag import flag

K = 64

def gen():
from Crypto.Util.number import getStrongPrime
e = 65537
Ns = []
for i in range(K):
p = getStrongPrime(2048)
q = getStrongPrime(2048)
Ns.append(p*q)
return e,Ns

e,Ns = 65537,#list trimmed[...]
def proof_of_work(self):
proof = ''.join([random.choice(string.ascii_letters+string.digits) for _ in xrange(20)])
digest = sha256(proof).hexdigest()
self.request.send("sha256(XXXX+%s) == %s\n" % (proof[4:],digest))
self.request.send('Give me XXXX:')
x = self.request.recv(10)
x = x.strip()
if len(x) != 4 or sha256(x+proof[4:]).hexdigest() != digest:
return False
return True

def handle(self):
if not self.proof_of_work():
return
self.request.settimeout(3)
try:
self.request.sendall("message: ")
msg = self.request.recv(0x40).strip()
ys = []
for i in range(K):
self.request.sendall("x%d: " % i)
x = int(self.request.recv(0x40).strip())
ys.append(pow(x,e,Ns[i]))
self.request.sendall("v: ")
v = int(self.request.recv(0x40).strip())

key = sha256(msg).digest()[:16]
E = ARC4.new(key)
cur = v
for i in range(K):
pt = (ys[i]^cur)%(1<<64)
ct = unpack('Q', E.encrypt(pack('Q',pt)))[0]
cur = ct

if cur == v:
self.request.sendall("%s\n" % flag)
self.request.sendall("fin\n")
finally:
self.request.close()

pass

if __name__ == "__main__":
HOST, PORT = '0.0.0.0', 10001
server.serve_forever()


The first part is obviously proof of work, in which we have to find 4 bytes XXXX such that sha256(XXXX + 16-char-val) = sha256_hash for provided 16-char-val postfix and sha256_hash
Which is easy to solve

using permutations may not always work (in case of repeated characters), earlier I used combinations_with_replacement which had some weird issues which I could not debug python from hashlib import sha256 import string from itertools import permutations as take CHARSET_SHA = string.printable[:62].encode() #0-9a-zA-Z as in challenge

def pow_sha(postfix, hash_val): for prefix in take(CHARSET_SHA, 4): prefix_bytes = bytes(prefix) shaa = sha256(prefix_bytes+postfix).hexdigest() if shaa == SHA_256_HASH: return prefix_bytes

HOST, PORT = “pwnable.org”, 10001 REM = remote(HOST, PORT) SHA_CHALL = REM.recvuntil(b’XXXX:’) #print(SHA_CHALL.decode()) SHA_256_HASH = re.search(b”[0-9a-f]{64}”,SHA_CHALL).group(0).decode() POSTFIX_STR = re.search(b”[0-9a-zA-Z]{16}”,SHA_CHALL).group(0) PREFIX_CHALL = pow_sha(POSTFIX_STR, SHA_256_HASH) REM.send(PREFIX_CHALL)


Now comes the main part of the challenge, in which we have to provide 64 xi values a message msg and a value v
The msg is sha256 hashed and first 16 bytes are taken to form the key for ARC4
The value v is XORed with last 64 bits of pow(x[i], e, Ns[i]) and then ARC4 encrypted. The goal is to produce the final value equal to the input v.

Since ARC4 is simply a stream cipher, and encryption is just XORing the plaintext with a keystream, our final value cur is essentially v^ys[0]^...ys[63]^xors[0]^xors[1]...^xors[63], where ys[0..63] are the last 64 bits of the respective y[0..63]  and xors[0]^xors[1]...^xors[63] part is essentially dependent on key and an invariant for a given key, lets call it invariant(key) (bye bye ARC4).
All we need to do is to find x[0..63] such that ys[0]^ys[1]...^ys[63] == invariant(key) and we will have cur==v for all v as a consequence.

python
from Crypto.Cipher import ARC4
from hashlib import sha256
from struct import pack, unpack

def encrypt_64(v,key,y):
E = ARC4.new(key)
cur = v
for i in range(64):
pt = (cur^y[i])%(1<<64)
ct = unpack('Q',E.encrypt(pack('Q',pt)))[0]
cur = ct
return cur

def invariant(key):
key_val = sha256(key).digest()[:16]
return encrypt_64(0,key_val,[0 for i in range(64)])

print(invariant(b'aaa'))
# 911494890333775973


One could simply put x[i] as some value such that ys[i] == invariant and all other xs == 0 but only if one could solve ANY of the RSA by factoring 4096 bit Ns, which is obviously not feasible!

Not knowing much linear algebra, I found this stackexchange post and this showing all that needs to be done is to have a set of 64 64-bit vectors, and we can represent any 64 bit value using xor of a subset of the vectors. Taking the corresponding ys for xs = 2 for all i, and solving the subset for given invariant, we will only set x[i] = 2 in the i in subset else x[i]=0 (to have no effect).

Sagemath ftw! CoCalc for the poor

#Ns not shown here
last_64 = [pow(2,e,i)%(1<<64) for i in Ns]
invariant = 911494890333775973 #for msg = b'aaa'
I = GF(2**64)
last_64_mat = [ list(map(int, bin(i)[2:].zfill(64))) for i in last_64  ]
mat = matrix(I,last_64_mat)
invariant_vec = list(map(int, bin(invariant)[2:].zfill(64)))
invariant_vec = matrix(I,invariant_vec)
op = mat.solve_left(invariant_vec)
print(op[0])


Awesome! we have (0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1) as our output vector, we just have to return xi as 2*op and we are done ;)

xs = (0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1)
xs = [2*i for i in xs]
REM.recv()
REM.send(b'aaa') #message
for i in range(64):
REM.send(str(xs[i]).encode()) #xi's
REM.recv()

REM.send(b'0') #v any v would do the job ;)
REM.recv()
#flag{babbbcbdbebfbgbhbibjbkblbmbnbobpbqbrbsbtbubvbwbxby}


Unorganized code in files solve.py, part2.sage and test.py

flag{babbbcbdbebfbgbhbibjbkblbmbnbobpbqbrbsbtbubvbwbxby}

Some words for the nerds

jekyll.environment != "beta" -%}