[Write-up] Tokyo Westerns CTF 2017 - rev500 Steganographer Revenge

It's a long time since I last wrote a writeup for reversing challenge! Since we(217) are the only team to solve this, and it's a great challenge, I decide to do so.This challenge was solved by me and my teammate +PZ Read.

0x01 Files

The challenge has two attached files, a x86_64 binary steganographer_revenge and an image file invitation.png. You can find this two files in my github repo.

The goal of solving this challenge is clear. The binary hide some data in the image(i.e. steganography), we need to reverse what the binary did and extract data from the given image.

The usage of binary is:

$ ./steganographer_revenge input.png output.png DATA

The binary needs libpng12.so.0 for parsing a png file, you can install it via apt (ubuntu 16.04) or compile from source.

0x02 Encode

The binary do lots of things, but after some analysis we have the outline:

1. convert input image's RGB into YUV
2. do Discrete Cosine Transform(?) on Y dimension, named it Y*
3. convert message data from 0/1 bits to -1/1, named it D
4. construct a constant matrix V with value -1/0/1
5. do scalar multiplication (details later) on V according to D, named U
6. calculate a linear combination of rows of U and assign to part of Y*
7. do inverse DCT(?) on Y*
8. convert YUV back to RGB and save to output image

Transform

I have a question mark in step 2 and 7 because, well,  we're still not sure what the transformation is(!). Since it's common to do DCT in image watermarking techniques, we guess it's DCT. But what it actually is doesn't matter. When we want to reverse step 7 and 8, only need to util the binary self to execute step 1 and 2 with output image as input. So forget whatever the transformation is and move to details of those vector operations of step 3 ~ 6.

Details

Use an example would be much clear. Let input data be one-byte string, 'A'.

step 3

Convert 'A' to binstring, '01000001', then we will have D = [-1,1,-1,-1,-1,-1,-1,1].

step 4

The matrix V is constructed as follows:

1. construct a constant array v with value -1/0/1
2. V[i] = [0] * i + v + [0] * (len(D) - i - 1) for i in range(len(D))

So the matrix V would have dimension len(D) x (len(v)+len(D)-1) and look like this:

     v 0 0 0 0 0 0 0
     0 v 0 0 0 0 0 0 
V =  0 0 v 0 0 0 0 0
     ...
     0 0 0 0 0 0 0 v

Notice that v is a vector but not a scalar.
We don't know how the array v is constructed, but its value and dimension are only affected by length of input data.
We found an important property of V, which will be described in 0x03 Decode.

step 5

This step is simple: U[i] = V[i] * D[i] for i in range(len(D)).

Since D=[-1,1,-1,-1,-1,-1,-1,1], then we have

     -v  0  0 0 0 0 0 0
      0  v  0 0 0 0 0 0 
U =   0  0 -v 0 0 0 0 0
      ...
      0  0  0 0 0 0 0 v

step 6

Let E = Σ U[i]*alpha[i] for i in range(len(D))

where alpha are some positive values calculated from Y* and U but not important when decoding.
E will be a floating array with length (len(v)+len(D)-1).

Finally, assign E to part of Y* and do the remained transformations.

0x03 Decode

Let's decode the message!
First extract the transformed Y* from the image. I put the dumped result in my repo named dump_y. And it's easy to extract E from Y*.

Property of V

We found that each rows in V is orthogonal. That is, for all i != j, V[i]．V[j] = 0.

With this property, decoding will be very easy. See again definition of E: Σ U[i]*alpha[i]

Calculate the dot product of E and V[j] acquires

V[j]．Σ U[i]*alpha[i]
= Σ(V[j]．U[i])*alpha[i]
= (V[j]．U[j])*alpha[j]
= D[j]*(V[j]．V[j])*alpha[j]
= D[j]*POSITIVE_NUMBER

Since alpha are positive values, the sign of dot product of E and V[j] equals to sign of D[j]! Which is our desired message.

All we need is guess the length of message (D), and dump corresponding v from memory to decode the message.

0x04 Get Flag

We dumped v vector according to different message length from memory. Then try the decode method and see which one is reasonable.
The correct input length is 280 (so len(D)=280*8), corresponding value of v also in my repo.

Decode script:

#!/usr/bin/env ruby
# encoding: ascii-8bit

N = 512
ystar = IO.binread('dump_y').split.map(&:to_f)
len = 280
value = IO.binread("values/280.dump").split.map(&:to_i) # vector v
e = []
N.times do |i|
  N.times do |j|
    e << ystar[i * N + j] if i + j >= N / 2
  end
end
result = ''
0.upto(8 * len - 1) do |i|
  sym = [0] * i + value + [0] * (len * 8 - 1 - i)
  # dot product < 0 ? 0 : 1
  result << (sym.zip(e[0, sym.size]).reduce(0.0) { |s, (a, b)| s + a * b } < 0 ? '0' : '1')
end
p result.scan(/.{8}/).map { |v| v.to_i(2)}.pack("C*")

Run it and wait for about 6 seconds can recover the original message:

Dear CTFers, We are holding Tokyo Westerns CTF 3rd 2017 from September 2nd to September 4th. This is a security competition hosted by Tokyo Westerns. We would like to invite you to this CTF. P.S. This is my present for you. TWCTF{Spr34d_Sp3ctrum_1s_m0r3_u53fu1_f0r_st3g4n0gr4phy}.

Flag: TWCTF{Spr34d_Sp3ctrum_1s_m0r3_u53fu1_f0r_st3g4n0gr4phy}