# Confidence DS CTF ’17 – Public Key Infrastructure

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 $\texttt{admin}$. An immediate conclusion is that we need to some kind of collision attack. But how? We cannot exploit any collision in the $\texttt{admin}$ account. What if we can create a collision in $r$ while keeping $s$ distinct?

from coll import Collider, md5pad, filter_disallow_binstrings
import os

random_string = os.urandom(64)

# 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 $Z = (r \cdot Q + s)^{65537} \mod M$, we need to perform some additional computations. Obviously, we could factor the modulus $M$ and compute $\phi(M)$ and then obtain the signature as easy as $Z^{65537^{-1} \mod \phi(M)}$… but factoring… The probability that it is smooth enough is not very high. Also, the number is around $300$ digits so not a good candidate for msieve or other factoring software… so what then?

Well… what if $2^{96} \cdot A + c$ and $2^{96} \cdot B + c$ both are prime? Then, we can easily recover the signature as $Z^{65537^{-1} \mod (M-1)}$! 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')

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 $\begin{array}{rcl} n_1 &= & 105830311539247723296176540884596952305269885491629657210626981367998\\ &&347855559972583535368860650411949121405830046936667132754993342040282\\ &&396579458814796410615711380733886667185822027819749278255976029130752\\ &&166929087394904457033345839480235723175883533744993499706397792250975\\ &&3538392909994754306314762383722990106537161406818023\\ \end{array}$

and $\begin{array}{rcl} n_2 &=& 105830311539247723296176540884596952305269885520672956204333681813273\\ &&006022550217898599044674310459977554450027911751595002340337873829980\\ &&015343362188266640170082456168713800027076364038815247707214102650115\\ &&472228269311796278082939271876115926467296299772272093195558205398667\\ &&4873073960726016011965433749481512129478713571026663\\ \end{array}$

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
return pow(int(server.recvline()), modinv(65537, n1-1), n1)

name = 'groci'
PORT = 1331

# Get first signature
r1, s1 = sig / Q, sig % Q

# Get second signature
sig = pow(int(server.recvline()), modinv(65537, n2-1), n2)
r2, s2 = sig / Q, sig % Q

# 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!
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

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))
print server.recvline()


We obtain the following signatures: $r_1 = 455070882754437660339639715779025537190883529105$ $s_1 = 719850042802710537609987071764516609303635832220$ $r_2 = 455070882754437660339639715779025537190883529105$ $s_2 = 584220801769294572739392594733340817152152143208$

Now, with our forced nonce re-use, we can use standard techniques to obtain the private key and sign our $\texttt{admin}$ account, which gives the flag
DrgnS{ThisFlagIsNotInterestingJustPasteItIntoTheScoreboard}! Note to reader: I apologize for the excessive use of memes.