0CTF 2018 Quals – zer0C5 (Crypto 785)

0ops Cipher 4, hope you enjoy it:)
zer0C4.zip
nc 202.120.7.220 1234

Summary: related-key attack on weakened variant of RC4

In this challenge we have a weakened version of RC4. It operations on permutation of values $0\ldots 31$. Moreover, $i$ is incremented in the beginning of the loop instead of the end.

We are given access to a related-key oracle. We can send any key delta and the server will return us the generated sequence using the key xored with our delta.
There is a well known paper “Weaknesses in the Key Scheduling Algorithm of RC4.” by Fluhrer, Mantin, Shamir. In Section 8 they describe a Related Key attack. And it actually works better if the key schedule is modified exactly as in the challenge.

The main idea is that we can recover the 16-byte key in layer of 16 bits, from LSBs of each key byte to MSBs. If LSBits of the key bytes form a special pattern, then the LSBits of the output sequence correlate with a special sequence.

It is slightly difficult because we have only 1500 queries of 512 deltas, that is $2^{19.5}$ deltas total. We can recover 4 LSBits of each key byte and then bruteforce the 16 MSBits locally.

With a good probability we get the key.

Full solution: https://gist.github.com/hellman/3faeb41275fb013407b503d69f332207

The flag: flag{Haha~~Do_y0u_3nj0y_ouR_stre4m_c1pher?}