A guest write-up by keidii - one of our guest players, who bravely fought with Dragon Sector against the ASIS CTF 2013 challenges!
Download: ASIS CTF Finals 2013 "Inaccessible" (PDF)
Inaccessible was a two-phase stegano/forensics challenge, where you started with a set of 100 GIF files. See the write-up for more details.
Trivia: Something one team discovered - it seems that one of the photos promoting the CTF contained a visible name of the file and directory of an early version of this task.
Since I never had a chance to work with volatility and Linux dumps, I've decided to take a crack at this challenge.
We were given a memory dump. Looking at strings we could tell it's from a VirtualBox image running Ubuntu with a 3.5.0-23-generic kernel.
strings /tmp/mem.dump | grep BOOT_ BOOT_IMAGE=/vmlinuz-3.5.0-23-generic
Since the profile available on volatilty site is for older kernel we had to make our own (the steps are described here).
After that it's time to play ;]
First: bash_history it's quite long but this looks important:
$ ./vol.py -f /tmp/mem.dump --profile=LinuxUbuntu12_10-3_5_0-23x64 linux_bash -H 0x6ee4c0
Volatile Systems Volatility Framework 2.3_beta
....
967 bash 2013-08-26 11:27:53 UTC+0000 uname -a
967 bash 2013-08-26 11:27:53 UTC+0000 wget 172.16.133.149:8090/asis-ctf -O /tmp/
967 bash 2013-08-26 11:27:53 UTC+0000 wget 172.16.133.149:8090/asis-ctf
967 bash 2013-08-26 11:27:53 UTC+0000 ls
967 bash 2013-08-26 11:27:53 UTC+0000 du -h asis-ctf
967 bash 2013-08-26 11:27:53 UTC+0000 chmod +x asis-ctf
967 bash 2013-08-26 11:27:53 UTC+0000 ./asis-ctf
967 bash 2013-08-26 11:27:53 UTC+0000 sudo poweroff
967 bash 2013-08-26 11:27:54 UTC+0000 ls
967 bash 2013-08-26 11:30:37 UTC+0000 ./asis-ctf
967 bash 2013-08-26 12:00:04 UTC+0000 sudo apt-get install lynx
967 bash 2013-08-26 12:00:27 UTC+0000 lynx
967 bash 2013-08-26 12:10:44 UTC+0000 sudo apt-get install elinks
967 bash 2013-08-26 12:10:57 UTC+0000 elinks
967 bash 2013-08-26 12:14:58 UTC+0000 clear
967 bash 2013-08-26 12:15:00 UTC+0000 ls
967 bash 2013-08-26 12:15:28 UTC+0000 cp asis-ctf flag1
...
So lets take a look at procesess:
vol.py -f /tmp/mem.dump --profile=LinuxUbuntu12_10-3_5_0-23x64 linux_pstree Volatile Systems Volatility Framework 2.3_beta Name Pid Uid ... .login 837 0 ..bash 967 1000 ...asis-ctf 9425 1000 ...nano 15584 1000 .apache2 16346 0 ...
And lets dump the asis-ctf process memory and analyze it:
$ vol.py -f /tmp/mem.dump --profile=LinuxUbuntu12_10-3_5_0-23x64 linux_dump_map -p 9425 -D foo/
Volatile Systems Volatility Framework 2.3_beta
Task VM Start VM End Length Path
---------- ------------------ ------------------ ------------------ ----
9425 0x0000000000400000 0x0000000000401000 0x1000 foo/task.9425.0x400000.vma
9425 0x0000000000600000 0x0000000000601000 0x1000 foo/task.9425.0x600000.vma
9425 0x0000000000601000 0x0000000000602000 0x1000 foo/task.9425.0x601000.vma
9425 0x00007fd496e34000 0x00007fd496fe9000 0x1b5000 foo/task.9425.0x7fd496e34000.vma
9425 0x00007fd496fe9000 0x00007fd4971e8000 0x1ff000 foo/task.9425.0x7fd496fe9000.vma
9425 0x00007fd4971e8000 0x00007fd4971ec000 0x4000 foo/task.9425.0x7fd4971e8000.vma
9425 0x00007fd4971ec000 0x00007fd4971ee000 0x2000 foo/task.9425.0x7fd4971ec000.vma
9425 0x00007fd4971ee000 0x00007fd4971f3000 0x5000 foo/task.9425.0x7fd4971ee000.vma
9425 0x00007fd4971f3000 0x00007fd497215000 0x22000 foo/task.9425.0x7fd4971f3000.vma
9425 0x00007fd497408000 0x00007fd49740b000 0x3000 foo/task.9425.0x7fd497408000.vma
9425 0x00007fd497411000 0x00007fd497415000 0x4000 foo/task.9425.0x7fd497411000.vma
9425 0x00007fd497415000 0x00007fd497416000 0x1000 foo/task.9425.0x7fd497415000.vma
9425 0x00007fd497416000 0x00007fd497418000 0x2000 foo/task.9425.0x7fd497416000.vma
9425 0x00007fff62ff0000 0x00007fff63012000 0x22000 foo/task.9425.0x7fff62ff0000.vma
9425 0x00007fff63048000 0x00007fff63049000 0x1000 foo/task.9425.0x7fff63048000.vma,/
To do real RE we should reconstruct the binary, but I didn't bother assuming it's a really simple app, and IDA can follow programs headers, excluding sections which are not present dumped image.
The binary was indeed simple, it waits for input, if input was 'flag' it prints the flag.
The flag was put on the stack byte-by-byte:
LOAD:0000000000400683 mov byte ptr [rbp+var_A0], 66
LOAD:000000000040068A mov byte ptr [rbp+var_A0+1], 73
LOAD:0000000000400691 mov byte ptr [rbp+var_A0+2], 85
LOAD:0000000000400698 mov byte ptr [rbp+var_A0+3], 82
LOAD:000000000040069F mov byte ptr [rbp+var_A0+4], 76
LOAD:00000000004006A6 mov byte ptr [rbp+var_A0+5], 65
LOAD:00000000004006AD mov byte ptr [rbp+var_A0+6], 87
LOAD:00000000004006B4 mov byte ptr [rbp+var_A0+7], 78
LOAD:00000000004006BB mov [rbp+var_98], 100
LOAD:00000000004006C2 mov [rbp+var_97], 95
LOAD:00000000004006C9 mov [rbp+var_96], 105
LOAD:00000000004006D0 mov [rbp+var_95], 55
LOAD:00000000004006D7 mov [rbp+var_94], 105
LOAD:00000000004006DE mov [rbp+var_93]
...
and printed:
400867
LOAD:0000000000400867 loc_400867:
LOAD:0000000000400867 mov eax, [rbp+idx]
LOAD:000000000040086D add eax, eax
LOAD:000000000040086F cdqe
LOAD:0000000000400871 movzx eax, byte ptr [rbp+rax+var_A0]
LOAD:0000000000400879 movsx eax, al
LOAD:000000000040087C sub eax, [rbp+idx]
LOAD:0000000000400882 sub eax, 1
LOAD:0000000000400885 mov edi, eax
LOAD:0000000000400887 call sub_400500
LOAD:000000000040088C add [rbp+idx], 1
Since we don't have a runnable binary, we have to do it `manually` - easiest method, use idapython:
Python>
add = 0x400683
for i in range(0,38):
OpDecimal(add,1)
sys.stdout.write(chr(int(GetOpnd(add,1)) - i -1))
add = Rfirst(Rfirst(add))
print ""
ASIS_cb6bb012a8ea07a426254293de2bc0ef
Python>
Done.
This is a task from the ASIS CTF Finals 2013, "Stego" (steganography) category, and it was solved by quite a lot of teams. It was another of my favorite tasks in this CTF - it was quite easy, but required a couple of interesting steps to get to the end. This task was solved collaboratively by Gynvael Coldwind and Samlis Coldwind.
We were given an audio/video file called windows.mp4 (mirror), which looked more or less like this (the windows faded in and faded out at different positions):
In addition to the fading in/out there was an audio track with something that sounded like speech but wasn't quite understandable, and quite a lot of metadata. Some of the metadata contained interesting information, e.g.:
After either reversing the audio track, or downloading the original file, you would hear the synthesised voice saying a long number: 51324984652187698521487459648201.
One thing I didn't mention before was the task description which went like this:
Append what you find to "ASIS_" and send that as flag.
However, sending in ASIS_51324984652187698521487459648201 didn't work, which means that the video track was also important.
The fading in and out windows didn't reveal anything while taking the frames individually, so we decided to change the black background to transparent on each frame, and merge them all together. This resulted in the following image:
Yes, it's a QR code. Adding a white background and playing with the contrast / brightness made it readable for my QR reader in my cell phone, and resulted in the following string: xorwith313.
XORing the 51324984652187698521487459648201 value with 313 (both treated as bignums) gives 51324984652187698521487459648496, and appending ASIS_ at the beginning gives you the flag: ASIS_51324984652187698521487459648496.
This is a task from the ASIS CTF Finals 2013, "Stego" (steganography) category, and it was solved by 2 teams including ours. This was one of my favorite tasks on this CTF, since it was unconventional, interesting and didn't involve too much guessing.
We were given the following description:
Find the flag. Flag is in the form of ASIS_X which X is not a MD5 hash.
And the following PNG image:
The PNG file itself (as in: the PNG format) was clean - it did not contain any hidden data and there was no LSB-stegano - basically what you see is what you get, and what you get it an 8x8 matrix. The bitmap had total of 37-color squares: black plus 36 shades of grey, starting from RGB(5,5,5), up to RGB(180,180,180).
The important part here is that the RGBs of the shades of grey were always divisible by 5; so the darkest was RGB(5,5,5), then RGB(10,10,10), then RGB(15,15,15), ... - you get the picture. Dividing the RGB (or actually the average luminosity) by 5 you would get this:
.. 28 .. .. .. 7 .. .. .. 16 .. .. 22 6 14 30 .. 19 .. .. .. .. .. .. .. 31 20 34 26 .. .. .. 27 35 17 29 .. 15 33 .. 1 23 21 9 5 2 25 18 36 4 .. 32 13 3 .. 24 .. .. .. .. 10 11 8 12
We can transcribe to coordinates of each square, counting from top-left, in the order pointed to by the above chart (by luminosity):
1: 0,5 2: 5,5 3: 5,6 4: 1,6 5: 4,5 [...]
There are a couple of things that can be deduced here:
idx = x + y * 8 doesn't give you anything meaningful (i.e. converting what you get to base64 alphabet and decoding it doesn't give you anything meaningful).At this point I've changed my approach. In the task description we were given the information that the flag begins with ASIS_ (same as the flags in most of the tasks), so we did have a part of the plaintext. Encoding the ASIS_ string to base64 we get QVNJU18=, so we are sure that the first few chars will be Q, V, N, J, U and 1 (I'm not taking the last char ("8") into account, since it contains two bits of the next character 8-bit character, which in this case are of course zeroes, but could be anything in the full flag).
Translating the given base64 characters into indexes in the base64 alphabet gives you: 16, 21, 13, 9, 20, 53. And now the big question - how to get the value of e.g. 16 using the coordinates of the first square (0,5)?
Well, you can't do that using the top-left coordinates - if you would want to get 16 from the standard formula mentioned above you would have to have coordinates 0,2. But isn't 0,2 the coordinates of the first square in bottom-left coordinates which we haven't yet tried? Well, yes, it is.
Let's test this idea for the second square: bottom-left coordinates are 5,2, which means that the idx is 5 + 2 * 8, so 21, which is exactly the second element in the above number list!
So to get the flag you need to, going from the darkest to the brightest square:
idx = x + y * 8 formula.From what I've read on IRC most of the teams were really really close with this task, but didn't end up testing the bottom-left coordinates. Funnily I did test this coordinate system, but due to a bug in my code I didn't get the code until did the plaintext attack - lucky me ;)
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 ;>
#!/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)
#! /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()
#! /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:
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