Thursday, August 15, 2013

ebCTF 2013: crypto300

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

No comments:

Post a Comment