Log in as admin to get the flag.
nc pki.hackable.software 1337
This was a fun challenge, because it required many steps to complete. The first thing we notice is that MD5 is being used:
def h(x): return int(hashlib.md5(x).hexdigest(), 16) def makeMsg(name, n): return 'MSG = {n: ' + n + ', name: ' + name + '}' def makeK(name, n): return 'K = {n: ' + n + ', name: ' + name + ', secret: ' + SECRET + '}' def sign(name, n): k = h(makeK(name, n)) r = pow(G, k, P) % Q s = (modinv(k, Q) * (h(makeMsg(name, n)) + PRIVATE * r)) % Q return (r*Q + s)
Naturally, we cannot register as . An immediate conclusion is that we need to some kind of collision attack. But how? We cannot exploit any collision in the
account. What if we can create a collision in
while keeping
distinct?
from coll import Collider, md5pad, filter_disallow_binstrings import os def nullpad(payload): return payload + b'\x00' * (64 - len(payload) % 64) def left_randpad(payload): random_string = os.urandom(64) return random_string[:len(payload) % 64] + payload # nullpad the prefix so that it does not interfere # with the two collision blocks prefix = nullpad(b'K = {n: ') suffix = b', name: groci, secret:' collider = Collider() collider.bincat(prefix) collider.safe_diverge() c1, c2 = collider.get_last_coll() collider.bincat(suffix) cols = collider.get_collisions() # here are our collisions! A = next(cols) B = next(cols)
The above code creates a collision such that k = h(makeK(name, n))
generates the same value. The problem is that the server does not return the signature, but str(pow(sign(name, n), 65537, int(n.encode('hex'), 16)))
.
To get the signature, which is computed as , we need to perform some additional computations. Obviously, we could factor the modulus
and compute
and then obtain the signature as easy as
… but factoring…
The probability that it is smooth enough is not very high. Also, the number is around digits so not a good candidate for msieve or other factoring software… so what then?
Well… what if and
both are prime? Then, we can easily recover the signature as
! No need for time-consuming factoring! Embodied in Python, it could look like this:
import hashlib from Crypto.Util.number import isPrime def num2b(i): c = hex(i).strip('L') c = (len(c) % 2) * '0' + c[2:] return c.decode('hex') # get the payloads A = int(A[64:64*3].encode('hex'), 16) B = int(B[64:64*3].encode('hex'), 16) # PURE BRUTEFORCE, NOTHING FANCY HERE! # append the same data to both payload until # they resulting numbers are BOTH prime mul = 2 ** 96 for i in range(1, 2**20, 2): if isPrime(AA + i) and isPrime(BB + i): print AA+i print BB+i break
As an example, we obtain
and
Putting this into action, we might do something like:
def connect(name, n): name_encoded = base64.b64encode(name) n_encoded = base64.b64encode(n) server = remote('pki.hackable.software', 1337) payload = 'register:' + name_encoded + ',' + n_encoded server.send(payload + '\n') return pow(int(server.recvline()), modinv(65537, n1-1), n1) payload1 = nullpad('K = {n: ') + num2b(n1) payload2 = nullpad('K = {n: ') + num2b(n2) name = 'groci' PORT = 1331 assert(h(makeK(name, payload1)) == h(makeK(name, payload2))) assert(h(makeMsg(name, payload1)) != h(makeMsg(name, payload2))) # Get first signature sig = connect(name, payload1) r1, s1 = sig / Q, sig % Q z1 = h(makeMsg(name, payload1)) # Get second signature connect(name, payload2) sig = pow(int(server.recvline()), modinv(65537, n2-1), n2) r2, s2 = sig / Q, sig % Q z2 = h(makeMsg(name, payload2)) # Make sure we got a nonce re-use assert(r1 == r2) # OK, use standard nonce re-use technique... delta = modinv(((s1 - s2) % Q), Q) k = ( ((z1 - z2) % Q) * delta) % Q r_inv = modinv(r1, Q) PRIVATE = (((((s1 * k) % Q) - z1) % Q) * r_inv) % Q # Now that we know the private key, # lets forge/sign the admin account! name = 'admin' n = 'snelhest' k = h(makeK(name, n)) r = pow(G, k, P) % Q s = (modinv(k, Q) * (h(makeMsg(name, n)) + PRIVATE * r)) % Q sig = r*Q + s # connect and login name_encoded = base64.b64encode(name) n_encoded = base64.b64encode(n) server = remote('pki.hackable.software', 1337) payload = 'login:' + name_encoded + ',' + n_encoded + ',' + base64.b64encode(num2b(sig)) server.send(payload + '\n') print server.recvline()
We obtain the following signatures:
Now, with our forced nonce re-use, we can use standard techniques to obtain the private key and sign our account, which gives the flag
DrgnS{ThisFlagIsNotInterestingJustPasteItIntoTheScoreboard}
!
Note to reader: I apologize for the excessive use of memes.