VolgaCTF Qualifier 2020 - Export
This is the solution of the challenge “Export” given during the Volga CTF qualifier 2020. It consisted in a key recovery attack of a stream cipher which turn out to be the A5/2 cipher from GSM. Existing attacks applied to recover the secret key.
Description
We’ve got some algorithm from our friends, but we are not sure how secure it is. Can you take a look?
To prove it’s bad send us the recovered key in hex format like
|
|
|
|
Details
Points: 300
Category: crypto
Validations: 10
Solution
The server simply encrypts a message coming from us and return directly. The message is split in block of 115 bits and process one by one updating a frame number.
The cipher takes an unknown key of 64 bits. The frame number is 22 bits and incremented for each block. It uses 4 LFSRs for a total of a 82-bit state. The last LFSR is used to clock the three others and uses the majority function to decide which one will be updated. The structure of the cipher and the majority function made me think about the A5/1 cipher used in the GSM cellular telephone protocol I studied a long time ago during my studies.
However when comparing the output of the cipher.py file to the test vector of A5/1 algorithm it did not match. It turns out that it was the A5/2 algorithm which was similar but developped to be weaker and used for export. It makes the title of this challenge clear then. Then I figured out that Barkan, Biham and Keller developed an attack to recover the secret key of this algorithm. I even found a publicly available implementation of the attack online. The test vectors were the same expect that the key bits were swapped for each bytes:
|
|
So we would need to swap back the key once found. I compiled it
|
|
And then precompute tables for the attack
|
|
I waited a couple of hours and the precomputation was ready. The file main.cpp contains a test function which would perform the attack. It expects 3 blocks of 48 bytes of keystream with consecutive frame numbers. Then it will return the secret key. To have the keystream, I sent null bytes to the server and I got the following answer:
|
|
I arranged the result in my C file and launched the attack:
|
|
Then I restored the bits in the correct order:
|
|
And got the flag.
|
|