# Fast Crypto

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:

From the description we can see that is this a crypto challenge with some custom
rolled encryption. Lets take a look at what we have inside `fastcrypto.zip`

.

```
$ unzip fastcrypto.zip
Archive: ../fastcrypto.zip
inflating: cryptor.py
inflating: enc.wav
inflating: public.key
```

We have `enc.wav`

the encrypted data, `cryptor.py`

the cipher, and `public.key`

an RSA public key in JSON format.

Taking a closer look at `cryptor.py`

we can see a few interesting things:

```
def get_next(a, power, N):
b = a ** power % N
return b, b % 256
```

Which is an incredibly inefficient^{1} RSA computation, you can do much better
with modular exponentiation via `pow(a, power, N)`

.

Finally, the encryption algorithm:

```
# calculate offset
for _ in range(key['O']):
seed = get_next(seed, power, key['N'])[0]
with Path(sys.argv[2]).open('wb') as w:
for i in tqdm(range(len(data))):
seed, bt = get_next(seed, power, key['N'])
w.write(bytes([data[i] ^ bt]))
```

Instead of actually using RSA, this algorithm uses RSA as a random number
generator and uses the least significant byte of each step as a key byte.
Since we know the output file is a WAV file we know what that the first 4 bytes
are `RIFF`

in ASCII, which we can use to determine that the first 4 bytes of
the key stream are `14CA0F02`

!

The script also prompts the user for some input on the `seed`

value for the RNG
and which `power`

to use, but we can think of these as our private key! The
seed is a 16-bit integer and the power is between 2 and 16 so the number of
possible keys is roughly 2^{20}, which is small enough that we can
brute force it!

At this point I go and write the brute forcer in Julia since it is almost as fast as C but has easy constructs for parallelism. To get an idea of how long the brute force will take we will benchmark different implementations of the offset computation for each possible power.

```
samples = 30
println("original code ported")
@btime for power in 2:16
state = rand(Int16)
for _ in 1:O
state = (state^power) % N
end
end samples=samples
println("looped powermod")
@btime for power in 2:16
state = rand(Int16)
for _ in 1:O
state = powermod(state, power, N)
end
end samples=samples
println("powermod with powering offset")
@btime for power in 2:16
state = rand(Int16)
state = powermod(state, BigInt(power)^O, N)
end samples=samples
println("powermod with precomputed offset powers")
offset = collect(map(x -> BigInt(x)^O, 1:16))
@btime for power in 2:16
state = rand(Int16)
state = powermod(state, $offset[power], N)
end samples=samples
```

Which has following results:

```
original code ported
2.708 s (4089858 allocations: 487.64 MiB)
looped powermod
1.758 s (3745181 allocations: 121.70 MiB)
powermod with powering offset
684.417 ms (194 allocations: 1.17 MiB)
powermod with precomputed offset powers
656.555 ms (105 allocations: 1023.28 KiB)
```

Taking the final result as an estimate for each seed we can make the estimate that it will take about 12 hours to complete on a single core which is small enough that we could finish it before the CTF ends.

This is the brute forcing routine. `tfilter`

is a helper function for a threaded
calling of the key checker and progress monitoring.
The full source can be seen here.

```
function find_keys(range)
offset = collect(map(x -> BigInt(x)^O, 1:16))
tfilter(range, v -> !isnothing(v)) do seed
for power in 2:16
state = powermod(seed, offset[power], N)
state = powermod(state, power, N)
if state & 0xff != 0x14 continue end
state = powermod(state, power, N)
if state & 0xff != 0xca continue end
state = powermod(state, power, N)
if state & 0xff != 0x0f continue end
state = powermod(state, power, N)
if state & 0xff != 0x02 continue end
return seed, power
end
return nothing
end
end
```

Now with this in hand we can throw a ton of CPUs at it and find the key! If you watch diligently it will come out at around 7%, but after an about an hour on a machine with 48 threads we exhaused the search space!

We found that `seed`

is 4485 and `power`

is 7.
Now all we need to do is throw them into the `cryptor.py`

.

```
$ python3 cryptor.py enc.wav dec.wav
Input seed value (int16): 4485
Input power value (2-16): 7
100%...
```

At last we can listen to `dec.wav`

and hear:

the flag is cybrics{blum_blum_crypto}

- When done this way it computes
`a ** power`

first, then computes the remainder which consumes an exponential amount of memory. ^