Rating:

# Challenge description

> Here you have some modern encryption software. Actually, it’s even too modern for your hardware.
>
> Try to find out how to decode the WAV file with a secret message:
>
> fastcrypto.zip

# Analysis

The zip file contains three files. An encrypted wav file, a public key (consisting of N and O) and the python code used for encryption.

The python script asks for a seed (0 <= seed <= 2^16) and a power a power (2 <= power <= 16).

These values are used in conjuction with the public key to generate a stream of bytes.

At each iteration the 8 least significant bits of the state are the next byte of the stream. The entered seed is the initial state, and the state transition is defined as state = state ** power % N. The first O bytes of the stream are discarded, and the rest was used to XOR encrypt the WAV file.

# Solution

The used seed and power are unknown, but luckily the search space for this is only of size 2^16 * 2^4 = 2^20, which is bruteforceable. The task now becomes searching for a combination (seed, power) which generated the correct bytestream to decrypt the first 4 bytes of the encrypted WAV file to 0x52 0x49 0x46 0x46 which are the magic bytes of WAV files.

However, the testing of each combination is very slow (2-3s each in C) and should be sped up a little to finish in a reasonable time.

The first thing to notice is that the state transition can be more efficiently expressed as state = pow(state, power, N), which makes sure the intermediate results are considered modulo N as well. This is obviously better than calculating the actual power, and then reducing it with %N.

The second observation to make is that discarding the first O iterations is doing the same as transforming the state like state = state ** (power ** O) % N.
The factor power ** O is independant of the seed, and only needs to be calculated for every value of power.

Doing this speeds up the calculations to 0.5-1s per combination.

The last optimisation is possible because N is easily factorable (sage solves this near instantly), so Euler's Theorem can be applied: state = state ** (power ** O) % N = state ** (power ** O % phi(N)) % N. Using the python power notation, this becomes: state = pow(state, pow(power, O, phi(N)), N).

Doing this speeds the process up to <10ms per iteration.

Original writeup (https://github.com/VandorpeDavid/CTFWriteups/tree/master/2019/CyBRICS-quals/fast_crypto).