HSCTF 2015: Revenge of Cooley-Tukey Writeup

This was a fun little challenge that used a discrete transform algorithm as a custom encryption scheme. It required some basic knowledge on Fourier-related transforms to solve.

The problem was given as:

Keith found a file encrypt.txt on his computer which contains a series of numbers: 1653.0 0.13916760914832338 58.72838425104149 -29.800988375644806 -64.39696961966996 77.24677622083472 29.83855931789015 -62.70175235211251 42.999999999999986 65.1382409674247 -21.49541356738255 -67.39554551772046 54.396969619669974 40.92032042100787 -39.07153000154913 -15.546218972937488 65.0 He also found a hint at the end of the file: Non-crypto related algorithm used for encryption Something related to FFT. Is it DCT or DST? Don’t know which one… Help Keith find out what algorithm is used and decrypt the message to find the flag

Determining the Transform Algorithm

We were given that the encryption transformation algorithm was either a Discrete Cosine Transform(DCT) or a Discrete Sine Transform(DST). We can reverse both of these with their inverse transform, so the only question left is whether to use IDCT or IDST.

For this we can turn to the number of points given as a clue. An unpadded fast cosine transformation requires the number of sample points to be one greater than a power of two, while an unpadded fast sine transformation requires the number of sample points to be a power of two as well as requiring the first sample point to be zero.

We are given sample points, the first of which is . Since we can easily implement IDCT. DST is unlikely to have been used because and our first sample point is not .

Now that we know which transformation algorithm to use, all that’s left is to write a program to perform the transformations with various normalizations and types.

Implementing the Algorithm

I initially opted to do this using Python and the SciPY FFTPack.

from scipy.fftpack import idct
import numpy as np

x = np.array([1653.0,0.13916760914832338,58.72838425104149,-29.800988375644806,-64.39696961966996,77.24677622083472,29.83855931789015,-62.70175235211251,42.999999999999986,65.1382409674247,-21.49541356738255,-67.39554551772046,54.396969619669974,40.92032042100787,-39.07153000154913,-15.546218972937488,65.0])

print idct(x, type=1)
print idct(x, type=1, norm='ortho')
print idct(x, type=2)
print idct(x, type=2, norm='ortho')
print idct(x, type=3)
print idct(x, type=3, norm='ortho')

However upon running the program spat back an error:

“Orthonormalization not yet supported for IDCT-I”

None of the other results were in the ascii range, so I would need a more extensive library to use. For this I switched over to Java and the Apache Commons Math Library

Now that I had the extensibility needed to implement other normalizations I tested different ones and it turns out that the proper algorithm was IDCT-I with standard normalization. The values were then rounded and the results converted to letters using their ascii values.

Doing this in Java:

import org.apache.commons.math3.transform.TransformType;
import org.apache.commons.math3.transform.FastCosineTransformer;
import org.apache.commons.math3.transform.DctNormalization;


public class FFT {
    public static void main(String[] args) {
        
        double[] values = new double[]{1653.0,0.13916760914832338,58.72838425104149,-29.800988375644806,-64.39696961966996,77.24677622083472,29.83855931789015,-62.70175235211251,42.999999999999986,65.1382409674247,-21.49541356738255,-67.39554551772046,54.396969619669974,40.92032042100787,-39.07153000154913,-15.546218972937488, 65.0 };
        FastCosineTransformer transformer = new FastCosineTransformer(DctNormalization.STANDARD_DCT_I);
        double[]  solve  = transformer.transform(values, TransformType.INVERSE);
        for (int i = 0; i < solve.length; i++){
            System.out.print((char)Math.floor(solve[i] + 0.5));
        }
    }

}

Running this gives us our flag:

thegoodol'fourier