Forum EPFL 2014 Crypto Challenge

For the Forum EPFL 2014 job fair, we created a crypto challenge—in the spirit of CTF hacking contests—and offered to award a quadcopter drone to the first student to solve it and Bus Pirate devices to the next 2nd to 10th.

After about 10 days, no one solved it, although the difficulty was well below that of a competitive crypto challenge at (say) DEFCON qualifications.

Given the password-protected ZIP archive https://www.kudelskisecurity.com/kschallenge.zip, a first step was to recover the password: 1234. OK, next step:

The ZIP archive contained:

• a text file named ciphertext and containing the string “407747220c5f2754c6fd192502c8f597814bc95ce897eb6a3c45ba4a7150fe86d054d1607e94bf0fc90790ddba8925b50c8c6159b091651442779e86febfc6b1bd736d77d28d89d96ebee2d4038f26cb77a1b843afdb1c7bf3c01518a77b6f87d25b8071cafbfc30ee3f569f72342dcc” (224 characters, thus 112 bytes); one was supposed to deduce that this was the hexadecimal representation of a ciphertext (encrypted message).
• a command-line Python script named challenge.py, taking as parameter a file name and encrypting the file with CBC-AES-128 (from Python’s Crypto.Cipher module) using a key generated by a custom PRNG. The script is copied below:

#!/usr/bin/env python

# Copyright (c) 2014 Nagravision SA, all rights reserved

import os
import sys
import hashlib
from Crypto.Cipher import AES

ZEROBLOCK = '\x00'*16

def encrypt(key, iv, plaintext):
    assert len(key) == 16, 'key isnt 16-byte'
    assert len(iv) == 16, 'iv isnt 16-byte'
    assert len(plaintext) % 16 == 0, 'plaintext length isnt multiple of 16'
    cipher = AES.new(key, AES.MODE_CBC, iv)
    return cipher.encrypt(plaintext)


def xor(xs, ys):
    return ''.join(chr(ord(x) ^ ord(y)) for x, y in zip(xs, ys))


class PRNG(object):

    def __init__(self):
        self.state_bytes = 64
        self.key = ZEROBLOCK
        self.iv = ZEROBLOCK
        # get low-entropy string from the environment
        entropy = ''.join(os.listdir('/proc'))
        # hash to make a higher-entropy string
        seed = int(hashlib.sha256(entropy).hexdigest(), 16)
        # ensure distinct processes have distinct seeds
        pid = os.getpid()
        new_seed = self.__diversify(pid) * seed
        # hash again to get a 32-byte string
        final_seed = hashlib.sha256(str(new_seed)).digest()
        # initialize state
        self.state = final_seed + '\x00'*(self.state_bytes - len(final_seed))
        # fill state with pseudorandom bytes
        # + proof-of-work, against bruteforce
        for i in range(10000):
            self.__update()

    def __print_state(self):
        print self.state.encode('hex')

    def __diversify(self, x):
        return pow(3, x, 65537) & 0xffff

    def __update(self):
        mask = encrypt(self.key, self.iv, self.state)
        self.state = xor(mask, self.state)

    def get_bytes(self, nbbytes):
        randbytes = self.state[-nbbytes:]
        self.__update()
        return randbytes


def main():
    prng = PRNG()
    plaintext = open(sys.argv[1]).read()
    key = prng.get_bytes(16)
    iv = ZEROBLOCK
    ciphertext = encrypt(key, iv, plaintext)
    print ciphertext.encode('hex')

if __name__ == '__main__':
    main()

The PRNG is seeded with

• a snapshot of the content of /proc, which is highly unpredictable on a typical Linux system.
• the “diversified” PID, which on a Linux system ranges from 1 (init) up to 32768 (see /proc/sys/kernel/pid_max)

These two elements are then multiplied together on the line new_seed = self.__diversify(pid) * seed. Reminder: for all x, we have x×0=0.

In the above PRNG, one can observe a function __diversify(), which doesn’t seem to add entropy, let alone to “diversify” the PID, but rather to deterministically map a PID x to the value (3^x mod 65537) mod 65536, since the AND mask 0xffff is equivalent to a reduction modulo 1+0xffff. Now, observe that pow(3, 32768, 65537) equals 65536, which is equivalent to 0 modulo 65536.

Bottom line: there is a PID, namely 32768, for which the key does not depend on the highly unpredictable content of /proc. With this PID, one obtained the key “622c4f56d20f0825e22751e0f29b38f5”. One could then decrypt the ciphertext, and notice that it looked like a gzip’d file stripped of its first bytes (1f 8b 08 08). The rest is left as an exercise :-)