ebCTF CRY300 writeup by Dirt#3478

EBCTF CRY300 writeup - By team Dirt#3478

The CRY300 challenge involved breaking an authentication system which employed elliptic curve signatures (ECDSA). Normally, elliptic curve cryptography is hard to break, so there was a particular weakness which was introduced through a weak random number generator.

When signing a message with a private ECDSA key, an ephemeral key is generated as well. The signing occurs with the combination of the private key and the ephemeral key. A reference to the ephemeral key which was used, together with the signature, makes up the security token. If two distinct messages are both signed with the same private and ephemeral keys, the security of the signature scheme falls apart: anyone who intercepts these two security tokens can generate other security tokens with this private and ephemeral key.

To solve the challenge, we need 1. to generate the proof-of-work, 2. to reverse some of the hashes, 3. to find out the (public) parameters of the elliptic curve, 4. to extract the ephemeral key from the eavesdropped communications and 5. to generate a new security token based on this ephemeral key.

== 1. Generate proof-of-work ==

First things first: in order to authenticate, we need to generate a proof-of-work: a 64-byte plaintext that starts with a given (random) substring and the MD5-hash of which starts with '0000'. The following code works:

===== CODE START ================
#!/usr/bin/python

import hashlib

pos = "********" # The requested substring
solution = ""
iterator = 0
while hashlib.md5(solution).hexdigest()[0:4] != "0000":
	solution = str(iterator)
	while len(solution) < 56:
		solution = "0" + solution
	solution = pos + solution
	iterator = iterator + 1

print iterator-1
print solution
print hashlib.md5(solution).hexdigest()
===== CODE END ==================

== 2. Reverse the MD5 hashes ==

We need a couple of plaintexts for the hashes: googling the hash value gives us:

Hotz f56334fbe02eaa05218c31b01a80f2f6
Bushing 00b37cb56bb57705348610253b1b82e4
Butler 98c131f9fb31f732b136f87e64ff686a

Hotz and Bushing have access level 0, Butler has access level 1. Our attack will consist of generating a valid security token for the password 'Butler'.

== 3. Public parameters of elliptic curve ==

Normally in ECDSA, the underlying field and the curve upon which calculations are performed are public. In this case however, we had to find these out as well.

We know the following:
- The elliptic curve is taken over a finite field of order p (with p a prime number)
- The elliptic curve has, by definition, the form y^2 = x^3 + a*x + b
- a = p - 3 (line 27 of service.py)
- The points G, P and Q are on the curve (line 40-45 of service.py, coordinates at lines 30-37)

If we denote G=(Gx,Gy), P=(Px,Py) and Q=(Qx,Qy), we have the following equations:
Gy^2 = Gx^3 + (p - 3)*Gx + b mod p
Py^2 = Px^3 + (p - 3)*Px + b mod p
Qy^2 = Qx^3 + (p - 3)*Qx + b mod p

Substracting the second equation from the first and the third equation from the second, we get:
Gy^2 - Py^2 = Gx^3 - Px^3 + (p - 3)*(Gx - Px) mod p
Py^2 - Qy^2 = Px^3 - Qx^3 + (p - 3)*(Px - Qx) mod p

Moving all terms without unknowns to the left, we get:
Gy^2 - Py^2 - Gx^3 + Px^3 - 3*(Gx - Px) = p*(Gx - Px) mod p
Py^2 - Qy^2 - Px^3 + Qx^3 - 3*(Px - Qx) = p*(Px - Qx) mod p

Since p = 0 mod p, we know that the right-hand side is 0 in both equations. In both equations, the left-hand side should therefore be a multiple of p if interpreted as integers. Putting them in a computer algebra system (we used Sage), we find that the greatest common divisor of the two is 89953523493328636138979614835438769105803101293517644103178299545319142490503, which is prime and therefore equal to p.

Since a = p - 3, we can now calculate a and b to get the unknown values:

a = 89953523493328636138979614835438769105803101293517644103178299545319142490500
b = 28285296545714903834902884467158189217354728250629470479032309603102942404639
p = 89953523493328636138979614835438769105803101293517644103178299545319142490503

We also need to find the order of G on the elliptic curve. Our computer algebra system tells us the order of the point G on the given elliptic curve is 89953523493328636138979614835438769106005948670998555217484157791369906305783.

== 4. Extract the ephemeral key ==

An ECDSA signature, in general, is generated in the following way:

G: generator point on the curve
hash: value to be signed
sm: secret multiplier (part of private key)
n: order of G on the curve

1. Generate an ephemeral key k, calculate p1 = kG (scalar multiplication of points on curve) and let r be the x-coordinate of p1.
2. Calculate s = k^-1 * (hash + (r * sm)) mod n
3. The secret token is r,s

Now, if two distinct messages hash and hash' are both signed with the same ephemeral key k, we get:

s = k^-1 * (hash + (r * sm)) mod n
s' = k^-1 * (hash' + (r * sm)) mod n

(remember that r is calculated from k)

Solving for k^-1, we get

k^-1 = (s - s')/(hash - hash') mod n

Searching through the captured sessions, we look for lines with the same ephemeral key (first bytes of security token):

$ cat captured-sessions.txt | cut -d" " -f2 | sort | cut -c -30 | uniq -d
g8IwXPGZdVhLTVQsc4NxjbQdys2/5q
KVKN3KKUwmAMMDUC9QrKvBmPyu2h5t
wNpp5moxL1+Z0I40PJQCC/LegcOQoc

$ cat captured-sessions.txt | grep g8IwXPGZdVh
Hotz g8IwXPGZdVhLTVQsc4NxjbQdys2/5q2EzHvGo4lLxHlW9NTSxduU5nPoqdQt4Cn58GL17cq37J1SrbrK1/b67w==
Bushing g8IwXPGZdVhLTVQsc4NxjbQdys2/5q2EzHvGo4lLxHmOCiSFewnBx/EQ3Ij7ZX+iE+dPiDSBMezXcwzWWeVm1w==

The first attempt works: we have found two distinct messages, MD5(Hotz) and MD5(Bushing), which are signed with the same ephemeral key. We find k^-1 with the following code:

===== CODE START ================
hashHotz = "f56334fbe02eaa05218c31b01a80f2f6"
hashBushing = "00b37cb56bb57705348610253b1b82e4"
hashButler = "98c131f9fb31f732b136f87e64ff686a"

secTokenHotz = "g8IwXPGZdVhLTVQsc4NxjbQdys2/5q2EzHvGo4lLxHlW9NTSxduU5nPoqdQt4Cn58GL17cq37J1SrbrK1/b67w=="
secTokenBushing = "g8IwXPGZdVhLTVQsc4NxjbQdys2/5q2EzHvGo4lLxHmOCiSFewnBx/EQ3Ij7ZX+iE+dPiDSBMezXcwzWWeVm1w=="

hash1 = int(hashHotz,16)
hash2 = int(hashBushing,16)
hash3 = int(hashButler,16)

tmpHotz = base64.b64decode(secTokenHotz).encode('hex')
tmpBushing = base64.b64decode(secTokenBushing).encode('hex')

sigHotz = ecdsa.Signature(int(tmpHotz[:64],16),int(tmpHotz[64:],16))
sigBushing = ecdsa.Signature(int(tmpBushing[:64],16),int(tmpBushing[64:],16))

kinv = (sigHotz.s-sigBushing.s)*inverse_mod(hash1-hash2,n) % n

print kinv
===== CODE END ==================

The value of k^-1 is 64177781991311767079417471012576014125644196091350459505499548533470939053671.

== 5. Generate a new signature ==

Now that we have the value of k^-1, we can calculate the signature for Butler. We reuse the previously found formula for k^-1:

k^-1 = (s - s')/(hash - hash') mod n

We denote the hash of Butler with hash' and the signature of butler with s'. Isolating s', we get:

s' = k^-1*(hash' - hash) + s mod n

Adding to the previous code block, this code yields the signature and security token for Butler:

===== CODE START ================
sButler = (kinv*(hash3-hash1)+sigHotz.s) % n

print sButler

sigButler = ecdsa.Signature(sigHotz.r,sButler)
output = encode_signature(sigButler)

print output
===== CODE END ==================

== 6. Finally ==

We connect to the server using netcat (telnet under Ubuntu sends a CRLF, while we need only an LF). We resolve the proof-of-work requirement, enter password 'Butler' and the security token we generated (g8IwXPGZdVhLTVQsc4NxjbQdys2/5q2EzHvGo4lLxHlfB7uuzOhxzGGWeEKY0tGJ8bgH441xVCkDcfdIUhJREA==).