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:

fastcrypto.zip

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¹ 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²⁰, 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}