In this challenge we had a service written in Python:
service.py:
#! /usr/bin/env python
import string
import random
import SocketServer
import threading
import hashlib
import ecdsa
import base64
import os
#our own password database
access = {"f56334fbe02eaa05218c31b01a80f2f6":0, "00b37cb56bb57705348610253b1b82e4":0,
"f2131629ea6c08f7f5f326d8bb6eb5fd":0, "6fa95b1427af77b3d769ae9cb853382f":0,
"58cd57027cf126fcc9bd93dea9d74c1a":0, "f1cd318e412b5f7226e5f377a9544ff7":1,
"98c131f9fb31f732b136f87e64ff686a":1, "6f3249aa304055d63828af3bfab778f6":2}
#alphabet for passwords
alphabet = string.lowercase + string.uppercase
#read the curve parameters and flag from file
p,b,q,_sk,flag = open("secrets").read().split(',')
_p = int(p,16)
_b = int(b,16)
_q = int(q,16)
_sk = int(_sk,16)
ec = ecdsa.CurveFp( _p, _p-3, _b )
#some points that really should be on the curve we're going to use
_Gx = 0x337ef2115b4595fbd60e2ffb5ee6409463609e0e5a6611b105443e02cb82edd8L
_Gy = 0x1879b8d7a68a550f58166f0d6b4e86a0873d7b709e28ee318ddadd4ccf505e1aL
_Qx = 0x2a40fd522f73dc9f7c40b2420e39e62c5742ff2f11805a1577ed7f60153a0be1L
_Qy = 0x3085e99246006b71b4211eff47ff3efc0f93103ee7379dc3bcc6decdc46073a3L
_Rx = 0xbd0a442367bdc24cb09c49404e3d307ba99122e7b78e14f0d84870d0df97aa59L
_Ry = 0x22c88612db6b6af6f196cd815fc5f57fe871d3b6588b0c7a59e06cc759d736b2L
#check the curve is loaded ok
if not ec.contains_point(_Gx,_Gy):
exit()
if not ec.contains_point(_Qx,_Qy):
exit()
if not ec.contains_point(_Rx,_Ry):
exit()
g = ecdsa.Point( ec, _Gx, _Gy, _q )
seed = os.urandom(32)
#construct the server key material
server_public_key = ecdsa.Public_key( g, g * _sk)
server_secret_key = ecdsa.Private_key(server_public_key, _sk )
#some extended interfaces to Lis's ecdsa script
def sign(hashed_data, privkey):
h = int(hashed_data,16)
k = get_ephemeral_key()
signature = privkey.sign( h, k )
return encode_signature(signature)
def encode_signature(signature):
rhex = "%064x" % signature.r
shex = "%064x" % signature.s
return base64.b64encode(rhex.decode('hex') + shex.decode('hex'))
def verify(signature, hashed_input, pubkey):
tmp = signature.replace("\n", "")
try:
tmp = base64.b64decode(tmp).encode('hex')
except:
return False
if len(tmp) != 128:
return False
sig = ecdsa.Signature(int(tmp[:64],16),int(tmp[64:],16))
h = int(hashed_input,16)
return pubkey.verifies(h, sig)
def get_ephemeral_key():
k = ""
while len(k) < 32:
k += hashlib.md5(seed + str(random.randint(0,255))).digest()
return int(k.encode('hex'),16)
#server
class threadedserver(SocketServer.ThreadingMixIn, SocketServer.TCPServer):
pass
class incoming(SocketServer.BaseRequestHandler):
def handle(self):
cur_thread = threading.current_thread()
#hashcash
cash = os.urandom(4).encode('hex')
self.request.send("Please send a string of 64 characters, consisting of only 0-9a-f that starts with %s which md5 digest starts with 0000:\n" % cash)
resp = self.request.recv(128).strip()
if len(resp) != 64 or not all(c in '0123456789abcdef' for c in resp) or not resp.startswith(cash) or not hashlib.md5(resp).hexdigest().startswith('0000'):
self.request.send('Sorry :(')
return
#request password
self.request.send("Please enter your password:\n")
password = self.request.recv(32)
password = password.replace("\n", "")
#we only understand simple passwords
if not all(c in alphabet for c in password):
self.request.send("Access denied\n")
return
token = hashlib.md5(password).digest().encode('hex')
#you better be in our database
if not token in access:
self.request.send("Access denied\n")
return
#retrieve allowed access level
level = access[token]
if level == 2:
#you really really deserve this
self.request.send("There you go: " + flag)
if level == 1:
#you seem to belong here
self.request.send("Please present your security token for today:\n" )
sec_token = self.request.recv(1024)
if verify(sec_token, token, server_public_key):
self.request.send("There you go: " + flag)
else:
self.request.send("Access denied\n")
if level == 0:
self.request.send("Sorry level 0 has been temporarily disabled while we investigate a potential security breach.\n")
# Code disabled while we investigate the breach
#self.request.send("Here is your security token for today:\n" )
#self.request.send( sign(token, server_secret_key) + "\n" )
server = threadedserver(("127.0.0.1", 3016), incoming)
server.allow_reuse_address = True
server.timeout = 4
server_thread = threading.Thread(target=server.serve_forever)
server_thread.daemon = True
server_thread.start()
server_thread.join()
ecdsa.py:
#! /usr/bin/env python
#
# credits to Lis
# taken from https://bitcointalk.org/index.php?topic=23241.0
#
class CurveFp( object ):
def __init__( self, p, a, b ):
self.__p = p
self.__a = a
self.__b = b
def p( self ):
return self.__p
def a( self ):
return self.__a
def b( self ):
return self.__b
def contains_point( self, x, y ):
return ( y * y - ( x * x * x + self.__a * x + self.__b ) ) % self.__p == 0
class Point( object ):
def __init__( self, curve, x, y, order = None ):
self.__curve = curve
self.__x = x
self.__y = y
self.__order = order
if self.__curve: assert self.__curve.contains_point( x, y )
if order: assert self * order == INFINITY
def __add__( self, other ):
if other == INFINITY: return self
if self == INFINITY: return other
assert self.__curve == other.__curve
if self.__x == other.__x:
if ( self.__y + other.__y ) % self.__curve.p() == 0:
return INFINITY
else:
return self.double()
p = self.__curve.p()
l = ( ( other.__y - self.__y ) * \
inverse_mod( other.__x - self.__x, p ) ) % p
x3 = ( l * l - self.__x - other.__x ) % p
y3 = ( l * ( self.__x - x3 ) - self.__y ) % p
return Point( self.__curve, x3, y3 )
def __mul__( self, other ):
def leftmost_bit( x ):
assert x > 0
result = 1L
while result <= x: result = 2 * result
return result / 2
e = other
if self.__order: e = e % self.__order
if e == 0: return INFINITY
if self == INFINITY: return INFINITY
assert e > 0
e3 = 3 * e
negative_self = Point( self.__curve, self.__x, -self.__y, self.__order )
i = leftmost_bit( e3 ) / 2
result = self
while i > 1:
result = result.double()
if ( e3 & i ) != 0 and ( e & i ) == 0: result = result + self
if ( e3 & i ) == 0 and ( e & i ) != 0: result = result + negative_self
i = i / 2
return result
def __rmul__( self, other ):
return self * other
def __str__( self ):
if self == INFINITY: return "infinity"
return "(%d,%d)" % ( self.__x, self.__y )
def double( self ):
if self == INFINITY:
return INFINITY
p = self.__curve.p()
a = self.__curve.a()
l = ( ( 3 * self.__x * self.__x + a ) * \
inverse_mod( 2 * self.__y, p ) ) % p
x3 = ( l * l - 2 * self.__x ) % p
y3 = ( l * ( self.__x - x3 ) - self.__y ) % p
return Point( self.__curve, x3, y3 )
def x( self ):
return self.__x
def y( self ):
return self.__y
def curve( self ):
return self.__curve
def order( self ):
return self.__order
INFINITY = Point( None, None, None )
def inverse_mod( a, m ):
if a < 0 or m <= a: a = a % m
c, d = a, m
uc, vc, ud, vd = 1, 0, 0, 1
while c != 0:
q, c, d = divmod( d, c ) + ( c, )
uc, vc, ud, vd = ud - q*uc, vd - q*vc, uc, vc
assert d == 1
if ud > 0: return ud
else: return ud + m
class Signature( object ):
def __init__( self, r, s ):
self.r = r
self.s = s
class Public_key( object ):
def __init__( self, generator, point ):
self.curve = generator.curve()
self.generator = generator
self.point = point
n = generator.order()
if not n:
raise RuntimeError, "Generator point must have order."
if not n * point == INFINITY:
raise RuntimeError, "Generator point order is bad."
if point.x() < 0 or n <= point.x() or point.y() < 0 or n <= point.y():
raise RuntimeError, "Generator point has x or y out of range."
def verifies( self, hash, signature ):
G = self.generator
n = G.order()
r = signature.r
s = signature.s
if r < 1 or r > n-1: return False
if s < 1 or s > n-1: return False
c = inverse_mod( s, n )
u1 = ( hash * c ) % n
u2 = ( r * c ) % n
xy = u1 * G + u2 * self.point
v = xy.x() % n
return v == r
class Private_key( object ):
def __init__( self, public_key, secret_multiplier ):
self.public_key = public_key
self.secret_multiplier = secret_multiplier
def sign( self, hash, random_k ):
G = self.public_key.generator
n = G.order()
k = random_k % n
p1 = k * G
r = p1.x()
if r == 0: raise RuntimeError, "amazingly unlucky random number r"
s = ( inverse_mod( k, n ) * \
( hash + ( self.secret_multiplier * r ) % n ) ) % n
if s == 0: raise RuntimeError, "amazingly unlucky random number s"
return Signature( r, s )
And captured session (1000 requests):
Bushing N2H4IbYdza03JAPqQMSClxFCWaZbw3qMT1btugW9lAMm7jPtethECcB64qSwiNDT2GAUPNcZe+LHC32q73PmSQ==
Hotz wNpp5moxL1+Z0I40PJQCC/LegcOQocP+8Y9GV7Mv+5xCxqlIuZkMQDSpRWffZGG4NdkaOvAfttTtQuCaJZonxA==
Hotz l3O9KitquB8KznEtDn4NJnWOxk1oJfYxMp3A9MjMOrezkBIzao9RQnWqF+ARC61MVNXRnzCypm3/RCPCT3XtFQ==
[...]
Bushing Ny/2AWoDfM70LbVBrnUQw85Wr2aV0pNihTimg6aYCnqw0jxp2VTQ/Xkss3jNXSLWX4u2/G2RplnMKDbIia1DVQ==
Bushing aPL6Qh+7UQwZ0EIEvPgPHW+YkcqIrpULimmgt4xdqCgHwOb7LGxyGh7hNT5b/Yyo1crvsQ5AxEZZiuQ80QJBmg==
Bushing P3uwUNm7bDwpgRe6KgZXPmk1PmQOpLeVPtr+cQjI5yxb17YBZw8wh1jp24O5avzZ4cXdMeJvC0jABBCkMtX9PA==
Hotz PEoOFXZD/Qs4b/4Omsn3O87UUpFsd8i25mJvo91hp+K0W3bX7bbhHU/i2hSSmGLAXuNS7dIoO3Sxn/liqNGNlg==
To get flag we need to:
1. Break MD5 level2 hash (6f3249aa304055d63828af3bfab778f6)
or
2. Break one of MD5 level1 hashes (f1cd318e412b5f7226e5f377a9544ff7, 98c131f9fb31f732b136f87e64ff686a) and sign it with ECDSA private key.
Level2 hash seems to be unbreakable, level1 hashes are easy to break but we don't have the private key and all captured data are level0
ECDSA is safe if all messages are signed with different random value of ephemeral key (k), otherwise when we have 2 messages that used the same value of k we can calculate k using formula $$k = \frac{hash_1 - hahs_2}{s_1-s_2}\ (mod\ n)$$
and then the private key: $$d_A = \frac{s_1*k-hash_1}{r_1}\ (mod\ n)$$
And then we can sign our hash:
$$s = \frac{hash+d_A*r_1}{k}\ (mod\ n)$$
and the signature is $$(r_1,s)$$
Let's look at get_ephemeral_key() function:
def get_ephemeral_key():
k = ""
while len(k) < 32:
k += hashlib.md5(seed + str(random.randint(0,255))).digest()
return int(k.encode('hex'),16)
There are only 255*255 possible outputs of this function in one session (seed value is random but stays the same for the whole session)! And we have 1000 captured samples, so there is a huge probability that two messages were using the same k (birthday paradox). We can calculate k and the private key value from all pairs and if two disjoint pairs will give us the same private key, we can assume that this is true private_key.
import base64
import hashlib
n = G_ORDER
def inverse_mod( a, m ):
if a < 0 or m <= a: a = a % m
c, d = a, m
uc, vc, ud, vd = 1, 0, 0, 1
while c != 0:
q, c, d = divmod( d, c ) + ( c, )
uc, vc, ud, vd = ud - q*uc, vd - q*vc, uc, vc
assert d == 1
if ud > 0: return ud
else: return ud + m
f = open('captured-sessions.txt','r')
data = f.read()
lines = data.split("\n")
sigs = []
zs = []
for line in lines:
dwa = line.split(' ')
if len(dwa) <> 2:
continue
tmp = base64.b64decode(dwa[1]).encode('hex')
r = int(tmp[:64],16)
s = int(tmp[64:],16)
sigs.append( (r,s) )
hashed_input = hashlib.md5(dwa[0]).digest().encode('hex')
zs.append(int(hashed_input,16))
keys = dict()
for i in range(0,1000):
for j in range(i+1,1000):
(r1,s1) = sigs[i]
(r2,s2) = sigs[j]
z1 = zs[i]
z2 = zs[j]
if z1 == z2:
continue
k = (z1 - z2)*inverse_mod(s1-s2,n) % n
d = (s1*k - z1)*inverse_mod(r1,n) % n
ii = i
jj =j
if d in keys:
(ii,jj) = keys[d]
if ii <> i and jj <> j and i<>jj and j<>ii:
print d,k,r1
keys[d]=(i,j)
But there is a problem, we need Order of G. Let's look at verify function:
def verifies( self, hash, signature ):
G = self.generator
n = G.order()
r = signature.r
s = signature.s
if r < 1 or r > n-1: return False
if s < 1 or s > n-1: return False
c = inverse_mod( s, n )
u1 = ( hash * c ) % n
u2 = ( r * c ) % n
xy = u1 * G + u2 * self.point
v = xy.x() % n
return v == r
Before expensive (time) calculations there is a check if values of r and s are between 1 and n-1. So we can use binary search and time checks to find value of n.
import base64
import socket
import re
import random
import hashlib
import datetime
hostport = ('54.216.116.38', 3016)
def int2bin(d):
s=""
for i in range(0,32):
s+=chr(d%256)
d/=256
return s[::-1]
ordera = 0
orderb = 2**256 - 1
while 1:
s = socket.create_connection(hostport)
d= s.recv(1024)
m = re.search('.*starts with (.*) which md5.*', d)
pref = m.group(1)
while 1:
st = "01234567"*7
resp = pref + ''.join(random.sample(st,len(st)))
if hashlib.md5(resp).hexdigest().startswith('0000'):
break
s.send(resp)
d= s.recv(1024)
password = "Kevin"+("\n"*27)
s.send(password)
d= s.recv(1024)
si=2
orderc = ordera + (orderb - ordera)/2
ri = orderc
tmp = int2bin(ri) + int2bin(si)
sig = base64.b64encode(tmp)
s.send(sig)
n1=datetime.datetime.now()
d= s.recv(1024)
n2=datetime.datetime.now()
x=(n2-n1).microseconds
if x<100000:
orderb = orderc
else:
ordera = orderc
print x,ordera, orderb
s.close()
And that is everything what we need to solve this task.
import base64
import socket
import re
import random
import hashlib
import datetime
hostport = ('54.216.116.38', 3016)
def int2bin(d):
s=""
for i in range(0,32):
s+=chr(d%256)
d/=256
return s[::-1]
ordera = 0
orderb = 2**256 - 1
s = socket.create_connection(hostport)
d= s.recv(1024)
m = re.search('.*starts with (.*) which md5.*', d)
pref = m.group(1)
while 1:
st = "01234567"*7
resp = pref + ''.join(random.sample(st,len(st)))
if hashlib.md5(resp).hexdigest().startswith('0000'):
break
s.send(resp)
d= s.recv(1024)
password = "Kevin"+("\n"*27)
s.send(password)
d= s.recv(1024)
n = 89953523493328636138979614835438769106005948670998555217484157791369906305783
da =68503307448214310387573639006216872681840007669594105206515313184282784925849
k = 36738773201348520209625638351073339244477604751576415245956940910111085841389
ri = 59596085284558034169187633095832466866630673714956966387930595096089236063353
hash = int('f1cd318e412b5f7226e5f377a9544ff7',16)
si = ( inverse_mod( k, n ) * ( hash + ( da * ri ) % n ) ) % n
tmp = int2bin(ri) + int2bin(si)
sig = base64.b64encode(tmp)
s.send(sig)
d= s.recv(1024)
print d
