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:
# Copyright (c) 2014 Nagravision SA, all rights reserved
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)
def xor(xs, ys):
return ''.join(chr(ord(x) ^ ord(y)) for x, y in zip(xs, ys))
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):
def __diversify(self, x):
return pow(3, x, 65537) & 0xffff
mask = encrypt(self.key, self.iv, self.state)
self.state = xor(mask, self.state)
def get_bytes(self, nbbytes):
randbytes = self.state[-nbbytes:]
prng = PRNG()
plaintext = open(sys.argv).read()
key = prng.get_bytes(16)
iv = ZEROBLOCK
ciphertext = encrypt(key, iv, plaintext)
if __name__ == '__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 (3x 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 :-)