Sunday, August 18, 2013

UFO CTF 2013 - Broken brokoli (forensics 100)

This is a task from UFO CTF 2013, which was a sweet mixture of file format stegano, forensics and decoding weird alphabets (though that's probably not a legitimate CTF category).

You were given a single ZIP file (7117 bytes), which contained a single file called flag.rar (3402 bytes). The RAR file on the other hand contained a flag.bmp (180KB), but it was password protected (encrypted) so you couldn't extract it at this point.

Before I go any further, this is a good place to advertise the APPNOTE.TXT - .ZIP File Format Specification.

There are a couple of options where the password could be hidden in a ZIP archive - an extra field, a comment field, space between archived file and the ZIP headers, etc - and in the end it turned out that there is one more ZIP local file header (PK\3\4) in the ZIP archive, meaning that there is another archived file, which is not listed in the central directory. The local file header of this hidden file begins at offset D75h.

Parts of the header were wiped (zeroed), but still some information could be recovered:

50 4B 03 04 14 00 00 00 08 00 B8 63 D4 42 41 B2 68 F4 7F 0D 
00 00 86 34 03 00 07 00 00 00 00 00 00 00 00 00 00 ED DD 3B

The green part is, of course, the magic of the local file header. The yellow if the compression method - 8 means DEFLATE. Furthermore both the compressed size (pink) and the uncompressed size (cyan) were available: D7Fh bytes compressed would get decompressed into 33486h (210054 dec) bytes. Unfortunately the file name has been removed, but it wasn't really needed for anything.

There are several ways to extract this file. One is to add a zlib header in front of the DEFLATE data and just extract it using e.g. Python's zlib. Another would be fixing the local file header and placing it, and the data, in an external file, and then using Java stream ZIP decompression (which totally ignores the central directory and just looks for consequent local file headers from the beginning of the stream). Yet another would be to add a central directory record to describe this file and, again, fix the local file header. For an unknown reason I went for the first solution.

The question of "what exact values to choose for zlib header" can be answered by trying every possible zlib header - it turns out there aren't that many posibilities. The following Python code successfully extracted the hidden file:

import zlib

OFFSET = 0xd9a
SIZE   = 0xd7f
DSIZE  = 0x33486
d = open("brokenarchive.zip", "rb").read()[OFFSET:OFFSET+SIZE]
 
for m in [ "\x78\x01", "\x78\x9C", "\x78\xDA" ]:
  try:
    o = zlib.decompressobj().decompress(m + d, DSIZE)
    open("out.%.2x%.2x" % (ord(m[0]), ord(m[1])), "wb").write(o)
  except:
    pass

The output file turned out to be a BMP image:

The font is of course Wingdings, and after decoding you would get: #Ed&3m@cd0c! - the password to the flag.rar file extracted at the beginning.

As one could predict, the RAR file contained yet another BMP image with more Wingdings:

After decoding you would get flag is helloearthlings!!!!!!!!!, and a 100 points for your team :)

To sum up, a quick fun task if you know the ZIP format... and fluently read/write Wingdings ;>

Thursday, August 15, 2013

ebCTF 2013: crypto400

In this challenge we have an RSA signing service:

input: public_key (e,n) , data
It calculates the fingerprint of the provided public key sha1(public_key)
And then searches in ( fingerprint, d ) pair database for it.
Then it calculates $$m = sha1(current\_timestamp,data)$$ and $$signature = m^d (mod\ n)$$
output: current_timestamp, signature


Our task is to sign data with timestamp from 21.10.2005.
Signing service has a bug in searching procedure: only two bytes of fingerprint are compared. So it was possible to create public key with chosen n and bruteforce e with the same fingerprint which is used in real public_key.
After sending fake private key we are receiving: $$c=m^d mod\ n_{fake}$$ For given m,c,n when n is small we can bruteforce all x which satisfy conditions:
  • $$0<=x<=\varphi(n)$$
  • $$m^x = c\ ( mod\ n ) $$
We have also $$a^b\ mod\ n = a^{b\ mod\ \varphi(n)} mod\ n$$ $$b\ mod\ p\ =\ b\ mod\ \varphi(n)\ mod\ p\ if\ p|\varphi(n)$$ So when we choose small n and $$p|\varphi(n)$$ and we send it to the service, we will receive $$c = m^d\ mod\ n$$ where m is known. If for all x such that:
  • $$0<=x<=\varphi(n)$$
  • $$m^x = c\ (\ mod\ n )$$
$$y = x\ mod\ p$$ is the same value then we are sure that $$y = d\ mod\ p$$ When we have a lot of pairs $$(y_i,p_i)$$ and $$p_i$$ are pairwise coprime and $$\prod_i p_i>n_{real} $$ then we can calculate d using chinese remainder theorem. In my solution I used n and p values which satisfy $$n=2*p+1$$ and n,p are primes. Then $$\varphi(n)= n-1$$and$$p |\varphi(n)$$
#!/usr/bin/env python

import sys
import hashlib
import os
import socket
import time
import base64
import random
import datetime

from crt import ChineseRemainder

hostport = ('54.217.0.233', 2407)

# interpret string as little-endian long integer
def bin2int(s):
    return int(s[::-1].encode('hex'), 16)

# store integer as little-endian binary string of given length
def int2bin(i,n):
    return ("%x" % i).rjust(n*2,'0').decode('hex')[::-1]

def solve_dlp(x,y,n,p):
    solutions = set()
    for i in xrange(0,n):
        if pow(x,i,n) == y:
            solutions.add(i % p)
    return solutions

# read public key from file
with open("./pubkey0") as f:
    n = bin2int(f.read(1024 / 8))
    e = bin2int(f.read(32 / 8))


pubkeystring = int2bin(n,1024/8) + int2bin(e,32/8)
fingerprint=hashlib.sha1(pubkeystring).digest()


SIEVE_LEN = 1000000

sieve = [0]*SIEVE_LEN

for i in xrange(2,SIEVE_LEN):
    if sieve[i] == 0:
        j=2*i
        while j < SIEVE_LEN:
            sieve[j] = 1
            j+=i

primes_product = 1
crt = []
last_index = 100000
while primes_product < n:
    while sieve[last_index] == 1 or sieve[last_index*2+1] == 1:
        last_index+=1

    fake_n = 2*last_index+1
    prime = last_index 
    last_index+=1
    
    print 'using primes: ',fake_n,prime

    fake_e = 0
    while 1:
        fake_pubkeystring = int2bin(fake_n,1024/8) + int2bin(fake_e,32/8)
        fake_fingerprint=hashlib.sha1(fake_pubkeystring).digest()
        if fake_fingerprint[:2] == fingerprint[:2]:
            break
        fake_e += 1
    
    s = socket.create_connection(hostport)
    
    data = str(random.randint(0,1000))
    
    s.send(fake_pubkeystring + int2bin(len(data),32/8) + data)

    responsestring = ''
    while True:
        tmp = s.recv(1024)
        if not tmp: break
        responsestring += tmp


    ts = bin2int(responsestring[:4])
    sig = bin2int(responsestring[4:])
    if sig==0:
        continue

    m = bin2int(hashlib.sha1(int2bin(ts, 32/8) + data).digest() )
    m %= fake_n
    print 'received sig: ',sig
    print 'm: ',m
    x = solve_dlp(m,sig,fake_n,prime)
    if len(x)==1:
        x=x.pop()
        print 'solved: ',x
        crt.append( (x, prime) )
        primes_product *= prime

d = ChineseRemainder(crt)[0]
print 'private_key: ',d

ts = int(( datetime.datetime(2015, 10, 21) - datetime.datetime(1970, 1, 1)).total_seconds())
m = bin2int(hashlib.sha1(int2bin(ts, 32/8) + data).digest() )
sig = pow(m,d,n)
responsestring = int2bin(ts, 4) + int2bin(sig, 1024/8)
print base64.b64encode(pubkeystring + responsestring + data)

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

Sunday, August 4, 2013

ebCTF 2013: bin100 - bin300

bin100 - 'Dice Revenge'

Very similar challenge to one from teaser, roll some dices and win. Of course you have to roll 3 1 3 3 7 ;]
All rolls look alike:
 8048ebb:       e8 50 fc ff ff          call   8048b10 
 8048ec0:       89 c1                   mov    ecx,eax
 8048ec2:       ba ab aa aa 2a          mov    edx,0x2aaaaaab
 8048ec7:       89 c8                   mov    eax,ecx
 8048ec9:       f7 ea                   imul   edx
 8048ecb:       89 c8                   mov    eax,ecx
 8048ecd:       c1 f8 1f                sar    eax,0x1f
 8048ed0:       29 c2                   sub    edx,eax
 8048ed2:       89 d0                   mov    eax,edx
 8048ed4:       01 c0                   add    eax,eax
 8048ed6:       01 d0                   add    eax,edx
 8048ed8:       01 c0                   add    eax,eax
 8048eda:       89 ca                   mov    edx,ecx
 8048edc:       29 c2                   sub    edx,eax
 8048ede:       8d 42 01                lea    eax,[edx+0x1]
 8048ee1:       89 44 24 50             mov    DWORD PTR [esp+0x50],eax
 8048ee5:       83 7c 24 50 01          cmp    DWORD PTR [esp+0x50],0x1
So just find 5 rands and put breaks on them:
mov    DWORD PTR [esp+0x50],eax
Something like this:
--- bin100.gdb ---
b *0x8048ee1
b *0x80490ee
b *0x80492fc
b *0x80494ff
b *0x8049744

commands 1
set $eax=3
c
end

commands 2
set $eax=1
c
end
commands 3
set $eax=3
c
end
commands 4
set $eax=3
c
end

commands 5
set $eax=7
c
end

run
quit
--- end --- 
Fire it up: gdb -q -nx -x bin100.gdb bin100 press some enters aaand...
[*] You rolled a seven, with a six sided dice! How awesome are you?!
[*] You rolled 3-1-3-3-7, what does that make you? ELEET! \o/
[*] Nice job, here is the flag: ebCTF{9a9689dbd47a1fd3fc0bf17d60edf545}

bin200 - 'No comment...'

Throw it in IDA, look around. Google for RunPerl or -p2x-exe/debug to find out its a perl script compiled
with perl2exe - you can find a decoder here - then run it:
$ python2 per2exe-dec.py ebCTF_BIN200.exe
p2x_stub.lib
p2x_header.pm
p2x_info.pm
_main.pl
P2XDLL/p2x5123.dl
$ cat _main.pl
#!/usr/bin/perl

print "\n[*] ebCTF BIN 200\n".
      "      No comment...\n\n";

$secret = "Sup3RSeCr3tStuFf!";

print "[*] What is the secret? ";
$answer = ;
chomp($answer);

if ($answer eq $secret) {
  print "\n[*] Yes, that is correct! However that was not the goal of this challenge.\n".
        "    Did you know that compiled code does not contain any comments?\n";
} else {
 print "\n[*] Isn't that cute...but it is WRONG!.\n";
}

# W e l l ,  w e l l,  i t  s e e m s  t h e r e  a c t u a l l y  i s  a  c o m m e n t . . .
#
# .----------------. .----------------. .----------------. .----------------.
#| .--------------. | .--------------. | .--------------. | .--------------. |
#| |  _________   | | |   ______     | | |     ______   | | |  _________   | |
#| | |_   ___  |  | | |  |_   _ \    | | |   .' ___  |  | | | |  _   _  |  | |
#| |   | |_  \_|  | | |    | |_) |   | | |  / .'   \_|  | | | |_/ | | \_|  | |
#| |   |  _|  _   | | |    |  __'.   | | |  | |         | | |     | |      | |
#| |  _| |___/ |  | | |   _| |__) |  | | |  \ `.___.'\  | | |    _| |_     | |
#| | |_________|  | | |  |_______/   | | |   `._____.'  | | |   |_____|    | |
#| |              | | |              | | |              | | |              | |
#| '--------------' | '--------------' | '--------------' | '--------------' |
# '----------------' '----------------' '----------------' '----------------'
# .----------------. .----------------. .----------------. .----------------.
#| .--------------. | .--------------. | .--------------. | .--------------. |
#| |  _________   | | |       __     | | |  _________   | | |  ________    | |
#| | |_   ___  |  | | |     .' _/    | | | |_   ___  |  | | | |_   ___ `.  | |
#| |   | |_  \_|  | | |     | |      | | |   | |_  \_|  | | |   | |   `. \ | |
#| |   |  _|      | | |    < <       | | |   |  _|  _   | | |   | |    | | | |
#| |  _| |_       | | |     | |_     | | |  _| |___/ |  | | |  _| |___.' / | |
#| | |_____|      | | |     `.__\    | | | |_________|  | | | |________.'  | |
#| |              | | |              | | |              | | |              | |
#| '--------------' | '--------------' | '--------------' | '--------------' |
# '----------------' '----------------' '----------------' '----------------'
# .----------------. .----------------. .----------------. .----------------.
#| .--------------. | .--------------. | .--------------. | .--------------. |
#| |   ______     | | |  ________    | | |   ______     | | |     ____     | |
#| |  |_   _ \    | | | |_   ___ `.  | | |  |_   _ \    | | |   .'    '.   | |
#| |    | |_) |   | | |   | |   `. \ | | |    | |_) |   | | |  |  .--.  |  | |
#| |    |  __'.   | | |   | |    | | | | |    |  __'.   | | |  | |    | |  | |
#| |   _| |__) |  | | |  _| |___.' / | | |   _| |__) |  | | |  |  `--'  |  | |
#| |  |_______/   | | | |________.'  | | |  |_______/   | | |   '.____.'   | |
#| |              | | |              | | |              | | |              | |
#| '--------------' | '--------------' | '--------------' | '--------------' |
# '----------------' '----------------' '----------------' '----------------'
# .----------------. .----------------. .----------------. .----------------.
#| .--------------. | .--------------. | .--------------. | .--------------. |
#| |    ______    | | |     ______   | | |   _______    | | |    ______    | |
#| |   / ____ `.  | | |   .' ___  |  | | |  |  ___  |   | | |  .' ____ '.  | |
#| |   `'  __) |  | | |  / .'   \_|  | | |  |_/  / /    | | |  | (____) |  | |
#| |   _  |__ '.  | | |  | |         | | |      / /     | | |  '_.____. |  | |
#| |  | \____) |  | | |  \ `.___.'\  | | |     / /      | | |  | \____| |  | |
#| |   \______.'  | | |   `._____.'  | | |    /_/       | | |   \______,'  | |
#| |              | | |              | | |              | | |              | |
#| '--------------' | '--------------' | '--------------' | '--------------' |
# '----------------' '----------------' '----------------' '----------------'
# .----------------. .----------------. .----------------. .----------------.
#| .--------------. | .--------------. | .--------------. | .--------------. |
#| |    ______    | | |     ____     | | |  _________   | | |      __      | |
#| |  .' ____ '.  | | |   .' __ '.   | | | |_   ___  |  | | |     /  \     | |
#| |  | (____) |  | | |   | (__) |   | | |   | |_  \_|  | | |    / /\ \    | |
#| |  '_.____. |  | | |   .`____'.   | | |   |  _|      | | |   / ____ \   | |
#| |  | \____| |  | | |  | (____) |  | | |  _| |_       | | | _/ /    \ \_ | |
#| |   \______,'  | | |  `.______.'  | | | |_____|      | | ||____|  |____|| |
#| |              | | |              | | |              | | |              | |
#| '--------------' | '--------------' | '--------------' | '--------------' |
# '----------------' '----------------' '----------------' '----------------'
# .----------------. .----------------. .----------------. .----------------.
#| .--------------. | .--------------. | .--------------. | .--------------. |
#| |   _______    | | |   _______    | | |     __       | | |   ______     | |
#| |  |  ___  |   | | |  |  _____|   | | |    /  |      | | |  |_   _ \    | |
#| |  |_/  / /    | | |  | |____     | | |    `| |      | | |    | |_) |   | |
#| |      / /     | | |  '_.____''.  | | |     | |      | | |    |  __'.   | |
#| |     / /      | | |  | \____) |  | | |    _| |_     | | |   _| |__) |  | |
#| |    /_/       | | |   \______.'  | | |   |_____|    | | |  |_______/   | |
#| |              | | |              | | |              | | |              | |
#| '--------------' | '--------------' | '--------------' | '--------------' |
# '----------------' '----------------' '----------------' '----------------'
# .----------------. .----------------. .----------------. .----------------.
#| .--------------. | .--------------. | .--------------. | .--------------. |
#| |  _________   | | |    _____     | | |     __       | | |  ________    | |
#| | |_   ___  |  | | |   / ___ `.   | | |    /  |      | | | |_   ___ `.  | |
#| |   | |_  \_|  | | |  |_/___) |   | | |    `| |      | | |   | |   `. \ | |
#| |   |  _|  _   | | |   .'____.'   | | |     | |      | | |   | |    | | | |
#| |  _| |___/ |  | | |  / /____     | | |    _| |_     | | |  _| |___.' / | |
#| | |_________|  | | |  |_______|   | | |   |_____|    | | | |________.'  | |
#| |              | | |              | | |              | | |              | |
#| '--------------' | '--------------' | '--------------' | '--------------' |
# '----------------' '----------------' '----------------' '----------------'
# .----------------. .----------------. .----------------. .----------------.
#| .--------------. | .--------------. | .--------------. | .--------------. |
#| |     __       | | |    ______    | | |    ______    | | |   _    _     | |
#| |    /  |      | | |   / ____ `.  | | |  .' ____ \   | | |  | |  | |    | |
#| |    `| |      | | |   `'  __) |  | | |  | |____\_|  | | |  | |__| |_   | |
#| |     | |      | | |   _  |__ '.  | | |  | '____`'.  | | |  |____   _|  | |
#| |    _| |_     | | |  | \____) |  | | |  | (____) |  | | |      _| |_   | |
#| |   |_____|    | | |   \______.'  | | |  '.______.'  | | |     |_____|  | |
#| |              | | |              | | |              | | |              | |
#| '--------------' | '--------------' | '--------------' | '--------------' |
# '----------------' '----------------' '----------------' '----------------'
# .----------------. .----------------. .----------------. .----------------.
#| .--------------. | .--------------. | .--------------. | .--------------. |
#| |      __      | | |   _______    | | |     ____     | | |    ______    | |
#| |     /  \     | | |  |  _____|   | | |   .' __ '.   | | |  .' ____ \   | |
#| |    / /\ \    | | |  | |____     | | |   | (__) |   | | |  | |____\_|  | |
#| |   / ____ \   | | |  '_.____''.  | | |   .`____'.   | | |  | '____`'.  | |
#| | _/ /    \ \_ | | |  | \____) |  | | |  | (____) |  | | |  | (____) |  | |
#| ||____|  |____|| | |   \______.'  | | |  `.______.'  | | |  '.______.'  | |
#| |              | | |              | | |              | | |              | |
#| '--------------' | '--------------' | '--------------' | '--------------' |
# '----------------' '----------------' '----------------' '----------------'
# .----------------. .----------------. .----------------.
#| .--------------. | .--------------. | .--------------. |
#| |     ____     | | |     ____     | | |     __       | |
#| |   .'    '.   | | |   .'    '.   | | |    \_ `.     | |
#| |  |  .--.  |  | | |  |  .--.  |  | | |      | |     | |
#| |  | |    | |  | | |  | |    | |  | | |       > >    | |
#| |  |  `--'  |  | | |  |  `--'  |  | | |     _| |     | |
#| |   '.____.'   | | |   '.____.'   | | |    /__.'     | |
#| |              | | |              | | |              | |
#| '--------------' | '--------------' | '--------------' |
# '----------------' '----------------' '----------------'

Transcibe this huge comment and you get the flag: ebCTF{edbdb03c7998fa751be21d1364a58600}. Victory.

bin300 - Crack the password'

Quick look at disassembly reveals it's a binary that loads obfuscated lua script and executes it via luaL_loadbuffer. We can just break there and read the script:
--- moon.gdb ---
b luaL_loadbuffer
set print elements 0
commands 1
call printf("%s\n",$rsi)
end
run
quit
--- end ---
$ gdb -q -nx -x moon.gdb moon
Reading symbols from /tmp/moon...(no debugging symbols found)...done.
Breakpoint 1 at 0x411110
warning: no loadable sections found in added symbol-file system-supplied DSO at 0x7ffff7ffa000
warning: Could not load shared library symbols for linux-vdso.so.1.
Do you need "set solib-search-path" or "set sysroot"?

Breakpoint 1, 0x0000000000411110 in luaL_loadbuffer ()
p = 54111037
g = 56321

io.write("Enter your password: ")
io.flush()
password=io.read()
if string.len(password) ~= 32 then
    print("Wrong!")
    return 0
end

v = g
alpha = "0123456789abcdef"
for loop =1,32 do
    v = v * g
    v = v % p
    r = v % 16
    good = string.sub(alpha,r+1,r+1)
    if good ~= string.sub(password,loop,loop) then
        print("Wrong!")
        return 0
    end
end
print("Well done, the flag is: ebCTF{"..password.."}")
-- f02233aca4839124ee6ffa766883c47e

$1 = 488
A debugging session is active.

        Inferior 1 [process 2096] will be killed.

Quit anyway? (y or n) [answered Y; input not from terminal]
My first guess that the comment is the flag paid off - just wrap it with ebCTF{} and submit. Done.