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
sys.exit(0)
print keygen.crack(keygen.bfs(keygen.alphanum()+',+/',5,minDepth=5,prefix=sys.argv), 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
WHHEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE
> 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
> 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
> 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)
l, r = l1, r1
else:
l1 = l
r1 = l ^ F2(r, key)
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),splitLR(keypair)

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),[k0,k1]) != ux(m0): continue
if whee.encrypt(ux(m1),[k0,k1]) != ux(m1): 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