None
Whee
PlaidCTF - crypto - 375

Challenge Text

Although it seems like The Plague's messaging service is secure, there are bound to be bugs in any 20th century crypto system. We've recovered a version of the block cipher The Plague implemented. Use their online encryptor tool, at 54.82.75.29:8193, to break the cipher and figure out Plague's secret plans.

Challenge code available here

This was a really great challenge that required some extensive thinking to solve, but tackled some very interesting issues in cryptography. Normally on a CTF, I immediately dive into talking with the service before reading it's source code (when available). So let's jack in:

nc -vv 54.82.75.29 8193
Connection to 54.82.75.29 8193 port [tcp/*] succeeded!
We would first like some proof of work.
Send us a string starting with n7WzSynCCN5X5q7p, of length 21, such that its sha1 sum ends in ffffff
> no
Invalid proof of work!

Proofs of work are pretty straightforward and a great way to mitigate players spamming CTF servers. The first step then is creating a simple program that generates valid proofs with the stated prefix, matching length, and the required sha1 ending. Here's one way (keygen.bfs just generates a breadth first traversal of the keyspace and keygen.crack automates scheduling validation attempts).

import hashlib
import stdlib.ctf.Keygen as keygen

def validate(key):
    if len(key) < 5: return False
    return hashlib.sha1(key).hexdigest().endswith('ffffff')

if __name__ == '__main__':
    import sys
    if len(sys.argv) < 2:
        print 'usage: %s <prefix>'%sys.argv[0]
        sys.exit(0)
    print keygen.crack(keygen.bfs(keygen.alphanum()+',+/',5,minDepth=5,prefix=sys.argv[1]), validate)
$ python proof.py n7WzSynCCN5X5q7p
1417707771.79 -> 281,223 (n7WzSynCCN5X5q7pabbKH)
n7WzSynCCN5X5q7paor/M

$ echo -n 'n7WzSynCCN5X5q7paor/M' | sha1sum
4852097fb188b2e9b4da2436fe93c1844bffffff  -

Reconnect to test...

$ nc -vv 54.82.75.29 8193
Connection to 54.82.75.29 8193 port [tcp/*] succeeded!
We would first like some proof of work.
Send us a string starting with g5jHoPJQGvaDxsk4, of length 21, such that its sha1 sum ends in ffffff
> g5jHoPJQGvaDxsk4aqfL7
WHHEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE
dcd25edf8371ef8822c1511faeb55e0318eca3ad0cd0c9c74096eef8582b4601ed3683d252d0a50a6239c1511f74f75b53fb57103991c4ec253e9591acd47b660f503c9751038e8f4759c3
Send your encryption string:
> AAAAAAAAAA # 'A'*10
ac0dcfac0dcfac0dcf77168d

Again...

$ nc -vv 54.82.75.29 8193
Connection to 54.82.75.29 8193 port [tcp/*] succeeded!
We would first like some proof of work.
Send us a string starting with WRpH57ZoN/1eMJX7, of length 21, such that its sha1 sum ends in ffffff
> WRpH57ZoN/1eMJX7aV3Y6
WHHEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE
dcd25edf8371ef8822c1511faeb55e0318eca3ad0cd0c9c74096eef8582b4601ed3683d252d0a50a6239c1511f74f75b53fb57103991c4ec253e9591acd47b660f503c9751038e8f4759c3
Send your encryption string:
> AAAAAAAAAAA # 'A'*11
ac0dcfac0dcfac0dcf70be6e

And again...

$ nc -vv 54.82.75.29 8193
Connection to 54.82.75.29 8193 port [tcp/*] succeeded!
We would first like some proof of work.
Send us a string starting with Mkdbkh/rJu9DvPMf, of length 21, such that its sha1 sum ends in ffffff
> Mkdbkh/rJu9DvPMfa5nAm
WHHEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE
808f88aabac9204aa4472d6af7902ebe030e72d6ab86721473e34b61800633bb221d2b6da1b6c9e7ca10472d6a7b19cc42c9d068a2cc0a5a553c618d3e1de656d31673e177c01d32aca3b5
Send your encryption string:
> AAAAAA # 'A' * 6
3e5185279044

Testing the service many times helps establish behaviors like the hexadecimal string before "Send your encryption string" changing every couple minutes along with the encrypted response (ie, server is rekeyed). The next step is investigating the source code to better understand what is happening and how to crack it. The two most important functions for cracking it are key generation and data encryption - copied below:


M = 12
N = 24 # M * 2
K = 24 # N = M * 2
numrounds = 2 ** 24 # Protip: would not bruteforce this if I were you.

def gen_key():
  k0 = random.randint(0,2**(K/2)-1)
  k1 = random.randint(0,2**(K/2)-1)
  return [k0, k1]

def encrypt_block(plaintext, key):
  txt = plaintext
  l, r = (txt >> M) & ((1 << M) - 1), txt & ((1 << M) - 1)
  for x in xrange(numrounds):
    if x % 2 == 0:
      l1 = r
      r1 = l ^ F(r, key[0])
      l, r = l1, r1
    else:
      l1 = l
      r1 = l ^ F2(r, key[1])
      l, r = l1, r1
  return l << M | r

def get_blocks(txt):
  n = N / 8
  if len(txt) % n != 0:
    txt += '\x00' * (n - len(txt) % n)
  block_strs = [txt[i*n:i*n+n] for i in range(len(txt) / n)]
  return [extract(s) for s in block_strs]

def encrypt(plaintext):
  blocks = get_blocks(plaintext)
  out = [encrypt_block(block, KEY) for block in blocks]
  return unblocks(out)

Key generation is straightforward; select two random integers in range(0,2^12-1). Encryption uses a relatively straightforward Feistel Cipher; split each plaintext block then xor each half with a seeded array (16,777,216 times - ow) and recombine them. Generating the seeded array looks complex in source code, but we can treat it as a constant and generally ignore it during analysis since it is static/non-keyed. The get_blocks function helps explain why 'A'*10 and 'A'*11 produced such similar outputs though ("ac0dcfac0dcfac0dcf77168d" vs "ac0dcfac0dcfac0dcf70be6e"); each string is broken up into 3-byte blocks which means the first block didn't change (eg, encrypt("AAA",unknown_key) == "ac0dcf").

We could attempt Differential Analysis except for the massive number of rounds (16 million). The trivial key and key schedule suggests potentially using ehe weak key schedule to reduce the number of rounds though... which is exactly what a Slide Attack can accomplish. Just let the automated script keep performing proofs of work and querying the server to collect the 2^(n/4) plaintext-ciphertext pairs required while writing the attack implementation.

The key to performing a Slide Attack is finding two plaintext-ciphertext pairs (p0,c0 p1,c1) such that p0=F(p1) and c0=F(c1). Upon finding such a pair, the key can be brute forced using p=(l,r) and p0=(r0,l0 ^ F(r0,k)). See below:


def splitLR(value):    return int(value[:3],16),int(value[3:],16)
def splitKP(keypair):  return splitLR(keypair[0]),splitLR(keypair[1])

def getSlidPairs(flag,keyset):
    import itertools
    possibleKeys = []
    for m0,m1 in itertools.permutations(keyset, 2):
        (mp0l,mp0r),(mc0l,mc0r) = splitKP(m0)
        (mp1l,mp1r),(mc1l,mc1r) = splitKP(m1)
        if mp0r != mp1l: continue # not a pair
        if mc0r != mc1l: continue # not a pair
        keys = []
        for k0 in xrange(4096):
            for k1 in xrange(4096):
                if mp1r != mp0r ^ whee.f2[mp0l ^ whee.f1[mp0r ^ k0] ^ k1]: continue
                if mc1r != mc0r ^ whee.f2[mc0l ^ whee.f1[mc0r ^ k0] ^ k1]: continue
                if whee.encrypt(ux(m0[0]),[k0,k1]) != ux(m0[1]): continue
                if whee.encrypt(ux(m1[0]),[k0,k1]) != ux(m1[1]): continue
                print flag,m0,m1,k0,k1
                print 'flag? ',whee.decrypt(ux(flag),[k0,k1])

Running this on our collected pairs yields the flag...

$ python attack.py
...
dcd25edf8371ef8822c1511faeb55e0318eca3ad0cd0c9c74096eef8582b4601ed3683d252d0a50a6239c1511f74f75b53fb57103991c4ec253e9591acd47b660f503c9751038e8f4759c3 ('163000', '1c7afc') ('000115', 'afcf4b') 2361 4047
dcd25edf8371ef8822c1511faeb55e0318eca3ad0cd0c9c74096eef8582b4601ed3683d252d0a50a6239c1511f74f75b53fb57103991c4ec253e9591acd47b660f503c9751038e8f4759c3 ('011000', '7a193a') ('000193', '93ad5d') 333 2811
dcd25edf8371ef8822c1511faeb55e0318eca3ad0cd0c9c74096eef8582b4601ed3683d252d0a50a6239c1511f74f75b53fb57103991c4ec253e9591acd47b660f503c9751038e8f4759c3 ('011000', '7a193a') ('000193', '93ad5d') 2167 2461
dcd25edf8371ef8822c1511faeb55e0318eca3ad0cd0c9c74096eef8582b4601ed3683d252d0a50a6239c1511f74f75b53fb57103991c4ec253e9591acd47b660f503c9751038e8f4759c3 ('105000', 'e52a3f') ('000179', 'a3ff90') 965 1054
flag? Gotta love it when you can SLIDE. The flage is id_almost_rather_be_sledding

Code available on Github

- Kelson (kelson@shysecurity.com)