BostonKeyParty CTF 2013 write-up

Hint: flag is not a frag: once you've got it, you can get one more...

MITM (Crypto 200)
I can't read this. Can you?
message 1: QUVTLTI1NiBFQ0IgbW9kZSB0d2ljZSwgdHdvIGtleXM=
encrypted: THbpB4bE82Rq35khemTQ10ntxZ8sf7s2WK8ErwcdDEc=
message 2: RWFjaCBrZXkgemVybyB1bnRpbCBsYXN0IDI0IGJpdHM=
encrypted: 01YZbSrta2N+1pOeQppmPETzoT/Yqb816yGlyceuEOE=
ciphertext: s5hd0ThTkv1U44r9aRyUhaX5qJe561MZ16071nlvM9U=
As these messages say, the encryption is double AES-ECB with two different keys with first 232 bits equal 0. A straitforward bruteforce is too long (6 bytes entropy).
An efficient solution is Meet-In-The-Middle attack -- first build a table of all possible encryptions of plaintext, then decrypt the ciphertext with all possible keys and look the decryption up in the table.


import sys
from Crypto.Cipher import AES

alph = [chr(i) for i in xrange(256)]
m = 'QUVTLTI1NiBFQ0IgbW9kZSB0d2ljZSwgdHdvIGtleXM='.decode('base64')
c = 'THbpB4bE82Rq35khemTQ10ntxZ8sf7s2WK8ErwcdDEc='.decode('base64')
flag = 's5hd0ThTkv1U44r9aRyUhaX5qJe561MZ16071nlvM9U='.decode('base64')
middle = dict();

for v in alph:
    x = v;
    print x.encode('hex')
    for v in alph:
        y = v;
        for v in alph:
            z = v;
            key1 = '%s%s%s%s' % ('\0' * 29, x, y, z)
            cipher =
            middle.update({cipher.encrypt(m): key1})

print "\nTable built...";

for v in alph:
    x = v;
    print x.encode('hex')
    for v in alph:
        y = v;
        for v in alph:
            z = v;
            key2 = '%s%s%s%s' % ('\0' * 29, x, y, z)
            cipher =
            d = cipher.decrypt(c)
            if d in middle:
                print "\nKeys found: %s; %s\nFlag:" % (middle[d].encode('hex'), key2.encode('hex'))
                cipher1 =[d])
                print cipher.decrypt(cipher1.decrypt(flag))
Flag retrieval:

>>> flag='s5hd0ThTkv1U44r9aRyUhaX5qJe561MZ16071nlvM9U='.decode('base64')
>>> key1='0000000000000000000000000000000000000000000000000000000000ff3f45'.decode('hex')
>>> key2='00000000000000000000000000000000000000000000000000000000009ae807'.decode('hex')
>>> cipher1 =, AES.MODE_ECB)
>>> cipher2 =, AES.MODE_ECB)
>>> cipher2.decrypt(cipher1.decrypt(flag))
"This time I didn't include sol'n"
ElGamal (Crypto 200)
I'm PRETTY SURE that El Gamal is secure on basically any group. Prove me wrong? Running at
This is a service that implements a captcha and ElGamal "game".
The bypass the captcha, one should bruteforce a 20-chars string with a specified prefix, whose SHA1 hash has a predefined suffix (\xff\xff\xff).
The "game" is as follows:
-- the server sends ElGamal public key (p, g, h) to a client;
-- the client sends two numbers to the server;
-- the server randomly chooses one of them and sends its encryption to the client;
-- the client should guess, which of numbers was encrypted.
The last three steps repeat 64 times.
The solution is to select a quadratic residue and quadratic non-residue over the field F_p.
By the way, the p in this task is generated as follows: p=2*q+1, where the q is prime.
Take a look at the encryption procedure:
def elgamal_encrypt(p, g, h, m):
    y = random.randrange(1, p) # Don't pick 0
    c1 = pow(g, y, p)
    s = pow(h, y, p)
    c2 = s * m % p
    return (c1, c2)
We've got (h**y)*m%p and (g**y)%p. Note that h=(g**x)%p.
Thus, c1=m*g**(xy)%p. Now, g is quadratic non-residue, so, g**q=-1 mod p, thus, if c1**q==c2**q, then m is quadratic residue.

import hashlib
import random
import re
import socket
import string

def captcha_brute():
    while True:
        yield ''.join(random.choice(string.printable) for x in xrange(8))

def dostep(s, keys):
    s.send('4 5')
    ciphers ='\((\d+), (\d+)\)', s.recv(2048))
    oddity = pow(int(, (keys[0]-1)/2, keys[0])
    if pow(int(, (keys[0]-1)/2, keys[0]) == oddity:

def doit():
    s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    s.connect(('', 31333))
    captcha ="'(.*)' and", s.recv(128)).group(1)
    print 'Got captcha prefix: %s' % captcha
    for hypo in captcha_brute():
        if hashlib.sha1(captcha + hypo).digest().endswith('\xff\xff\xff'):
            print 'Got captcha string: %s' % hypo
            s.send('%s%s\n' % (captcha, hypo))
    keys = [int(x) for x in re.findall('\[(\d+)\]', s.recv(2048))]
    print 'Got key: %s' % keys
    for x in xrange(64):
        dostep(s, keys)
    print s.recv(256)

if __name__ == '__main__':
Launch it, get the flag:

$ python 
Got captcha prefix: dIvJHzqDgsLE
Got captcha string: Dga~Da	>
Got key: [27327395392065156535295708986786204851079528837723780510136102615658941290873291366333982291142196119880072569148310240613294525601423086385684539987530041685746722802143397156977196536022078345249162977312837555444840885304704497622243160036344118163834102383664729922544598824748665205987742128842266020644318535398158529231670365533130718559364239513376190580331938323739895791648429804489417000105677817248741446184689828512402512984453866089594767267742663452532505964888865617589849683809416805726974349474427978691740833753326962760114744967093652541808999389773346317294473742439510326811300031080582618145727L, 5, 20599707842594080592806871467326264953318180578075914297545006296180897682961098521127710022600676392677668750693678564792536292518950622938780897835891915555589850066943772162015009984914946562701717400736264614213787020758542839173228762792777962213550206429083155330550831114870108139897214362241748644979044149494735257180022300704454594371552542966255959771002365203754880986709812539529114965772704520892679302744068505344055006318771271820340027277292046958730350617532918746562489553013311683595749640694279885263440543884521931809685313385537513009949934029547000769052966029024839725485582148553004288917091L]
Augh!  I lose, again!
Door 2 (Crypto 300)
The server uses signed messages to operate doors, but we haven't been able to figure out how to crack the system. A source leaked a traffic dump to us that contains signed messages. However, the sessions from the dump still use the old door protocol. Since then the commands have been changed to all capital letters. You need to open door no 8. Server at (hint: crypto door 2 now does not require 'OPEN' in the text, any valid message/tag pair other than the ones provided is a valid solution)
At first, the task was unsolvable since we cannot simply forge an arbitrary CBC-MAC signed message.
But we can implement existential forgery by an adaptively chosen text attack.
To do that, we should take any two sessions from the dump.pcap, take command1 and command2, tag1 and tag2.
Then, we can construct message command1||command2^tag1, whose CBC-MAC tag will be tag2.

The final payload is:

{"door": 8, "tag": [110, 35, 179, 108, 224, 0, 240, 59, 250, 59, 206, 158, 141, 214, 122, 173], "command": "close # 67012\u0000\u0000\u0000\u00ec\u008d\u00f9u\u007f\u0018\u0097\u00a3\u00f9\u00adh\u00cf\u00b0\u00a7\u00b0K"}
(I haven't saved the flag).