ASIS CTF 2013 - Reverse 200 - Masterpiece

Task:

file

Unfortunately I didn't manage to restore the flag completely during CTF, so this is after-party write-up.

We are provided with x86-64 binary. It prompts us to input flag to check whether it is correct. If the flag is correct program output congratulation message. We know that flag should start with "ASIS_" so let's input it. We can see that program prints "Congr" and then some garbage is printed. So it is obvious that the first word is "Congratulation" or some variation of it.

I wrote simple script that output all variants of next symbol assuming that there are 16 possibilities for each hexadecimal character.

#!/usr/bin/ruby1.9.1
require "open3"
start = ARGV[0]

def test_sym(start,sym,e)
 stdin,stdout,stderr = Open3.popen3("./bin_200")
 stdin.puts (start + sym + e)
 4.times do
  stdout.gets
 end
 str = stdout.gets
 mid = sym.length
 result = true
 (0..mid).each do |m|
  if not (("0".."9").to_a).index(str[start.length + m]).nil?
   result = false
  end
 end
 if result  
  print (sym + ": ")
  puts str
 end
end

last = "".rjust(37 - start.length - 1,"0")

(("0".."9").to_a + ("a".."f").to_a).each do |s|
 test_sym(start,s,last)
end

Which you can use like that (a bit buggy):

Unfortunately I got stuck after getting congratulation message that starts with "Congratulation! You ". That's where I stopped at the CTF while trying to guess further or see something in assembly code.

After CTF I have deeply read assembly code. Binary does the following: it creates 304 x 304 bytes matrix in a heap. Also allocates two 304 byte vectors in a heap. Quad(8-byte) words a used. So matrix and vectors has a size of 38 by 38 quad words. Further binary set all these memory to zero. Then values that are hardcoded in the binary are copied to the matrix diagonal as double and our input copied into the one of the vectors (each char converted to double). After that 7 threads are created. Each of them multiply part of the matrix by vector where our input is stored. So all what the threads overall do is multiply matrix by vector. The result is stored at another allocated vector. It is notable that matrix has only nonzero diagonal so multiplication of that matrix by vector can be substituted with diagonal vector component multiplication by components of the input vector. Then main thread joins other threads. And resulted values are being rounded and converted to chars and then printed as congratulation message.

In order to do something I firstly recovered double values that are stored in matrix diagonal. This can be done via gdb.

break *0x400C2F (this is the place in threads where calculation is made)
i b (to show available breakpoints)
cond 1 *(int*)($rbp - 0xc) == *(int*)($rbp - 0x10) (Where 1 is the number of 0x400c2f breakpoint from previous command. And condition is when i == j so we inspect element on diagonal.)
c or r to continue or run program
printf "i=%d, j=%d\n",*(int*)($rbp-0x10), *(int*)($rbp - 0xc) (to get i and j)
p $xmm2 (And look at the first field of the v2_double)

then continue to get other values. Or you can probably write gdb script to get those values.

After that it wasn't very obvious how to get the flag, because we don't know which character is correct in the congratulation message. However there is a way to get a flag. Initial double values from matrix diagonal are taken in such way that after multiplication they produce almost exact character ascii code. That means that in most cases only one value can be multiplied with initial value in matrix to get almost exact ascii code of congratulation message which is being rounded and printed. So we have to find such character that divided by initial value will give most exact value, e.g. 52.0000921412469 or 51.99992321 while others like 56.45 or so won't suffice. We have to search for those characters. I wrote script that will do that. Some values were omitted from k because they do not produce only one correct value, e.g. 0.33, 2 or 1 . They produce more values.

k = [1.97959,2.07143,1.20619,1.06931,1.86538,2.10909,1.07143,2.13462,2.07547,0.603774,1.61818,2.17647,2.08929,0.615385,1.03061,1.13402,2.32,2.02,1.12871,1.87037,1.88679,0.627451,2.18868,1.07216,2.02,0.615385,2.16,1.0404,0.647059]
message = ""
flag = ""
k.each do |gk|
  min = 47474747
  minc = 'x'
  (("a".."z").to_a + [" ",".","!","Y"]).each do |c|
    diff = (c.ord.to_f / gk - (c.ord / gk + 0.5).to_i).abs
    if diff < min
      min = diff
      minc = c
    end
  end
  puts "#{minc}: #{minc.ord.to_f / gk} - #{((minc.ord / gk + 0.5).to_i).chr}"
  message << minc
  flag << ((minc.ord / gk + 0.5).to_i).chr
end
puts message
puts flag 

which produces:

atulation You entered the lg!
18ae47b4557384ba22e6535a242c3 

So the whole congratulation message is "Congratulation! You entered the flag!"

And the flag is ASIS_18ae47b45d57384ba22e6535a2432ac3 which I cannot test.

P.S. You can restore other characters by knowing initial value on diagonal and assumed value, e.g. matrix[32][32] contains 2.0, but we know that resulting char should be "f" (part of the word "flag"). So we have to find digit of the flag at position 32 like that: ("f".ord.to_f / 2 + 0.5).to_i.chr.