ASIS CTF 2013 - Reverse 75 - Serial Number

Task:

Enter the correct serial number file.

This task required more reversing skills to solve from the previous one. It's a pity I had no environment to run it, but that wasn't a problem. Firstly I found a place where the flag is printed. It can be done by looking at strings stored in binary and their usage.

Place where the flag printing begins

 Program prints "ASIS_" which is header of the flag so we have to get other flag characters. Next there are 32 similiar blocks of instructions which print flag characters by one. It looks like:

One character printing block

All characters use the value stored at the [rbp - 0x44] with some offset which can be both negative and positive. This block gets value stored at the [rbp - 0x44], moves it to the eax register, adds offset and sign-extends its lowest byte to the 4 bytes. Then puts that value into esi which is the part of rsi and will be the second argument to the c++ operator <<. Value will be printed.
We know that all flag characters are (assume lowercase) hexadecimal digits. So all we need is to find a value that is stored at the rbp - 0x44 . Since it uses only lowest byte we need to check just 256 options and check all constraints for printed characters (Their charachter codes must be between 48 and 57 or 97 and 102 which corresponds to hexadecimal digit sign in ascii ("0"..."9", "a" ... "f"). I wrote simple script to find a number that fullfils constraints:

def movsx(value,length=32)
  value
=begin
  ret_val = (value & 0xff).to_s(2).rjust(8,"0")
  sign_bit = ret_val[0]
  ret_val = ret_val.rjust(length,sign_bit)
  if sign_bit == "1"
    ret_val = invert(ret_val,length)
    -(ret_val.to_i(2))
  else
    ret_val.to_i(2)
  end
=end
end

def bad(value)
  if (value >= "0".ord && value <= "9".ord) || (value >= "a".ord && value <= "f".ord)
    return false
  end
  true
end

def invert(value,length=32)
  (value.each_char.map {|c| c == "0"? "1":"0" }.join.to_i(2) + 1).to_s(2)[0...length].rjust(length,"0")
end

(0..256).each do |tested_value|
  a1 = movsx(tested_value + 6)
  if bad(a1)
    next
  end
  a2 = movsx(tested_value - 36)
  if bad(a2)
    next
  end
  a3 = movsx(tested_value + 9)
  if bad(a3)
    next
  end
  a4 = movsx(tested_value - 41)
  if bad(a4)
    next
  end
  a5 = movsx(tested_value - 45)
  if bad(a5)
    next
  end
  a6 = movsx(tested_value - 43)
  if bad(a6)
    next
  end
  a7 = movsx(tested_value - 36)
  if bad(a7)
    next
  end
  a8 = movsx(tested_value + 6)
  if bad(a8)
    next
  end
  a9 = movsx(tested_value + 8)
  if bad(a9)
    next
  end
  a10 = movsx(tested_value - 36)
  if bad(a10)
    next
  end
  a11 = movsx(tested_value + 7)
  if bad(a11)
    next
  end
  a12 = movsx(tested_value + 6)
  if bad(a12)
    next
  end
  a13 = movsx(tested_value + 9)
  if bad(a13)
    next
  end
  a14 = movsx(tested_value - 37)
  if bad(a14)
    next
  end
  a15 = movsx(tested_value + 9)
  if bad(a15)
    next
  end
  a16 = movsx(tested_value + 9)
  if bad(a16)
    next
  end
  a17 = movsx(tested_value - 38)
  if bad(a17)
    next
  end
  a18 = movsx(tested_value + 9)
  if bad(a18)
    next
  end
  a19 = movsx(tested_value - 37)
  if bad(a19)
    next
  end
  a20 = movsx(tested_value + 9)
  if bad(a20)
    next
  end
  a21 = movsx(tested_value - 44)
  if bad(a21)
    next
  end
  a22 = movsx(tested_value + 5)
  if bad(a22)
    next
  end
  a23 = movsx(tested_value - 38)
  if bad(a23)
    next
  end
  a24 = movsx(tested_value - 45)
  if bad(a24)
    next
  end
  a25 = movsx(tested_value + 8)
  if bad(a25)
    next
  end
  a26 = movsx(tested_value + 7)
  if bad(a26)
    next
  end
  a27 = movsx(tested_value + 8)
  if bad(a27)
    next
  end
  a28 = movsx(tested_value + 4)
  if bad(a28)
    next
  end
  a29 = movsx(tested_value + 7)
  if bad(a29)
    next
  end
  a30 = movsx(tested_value - 37)
  if bad(a30)
    next
  end
  a31 = movsx(tested_value - 41)
  if bad(a31)
    next
  end
  a32 = movsx(tested_value - 42)
  if bad(a32)
    next
  end
  puts "New variant!"
  print a1.chr + a2.chr + a3.chr + a4.chr + a5.chr + a6.chr + a7.chr + a8.chr + a9.chr + a10.chr + a11.chr + a12.chr + a13.chr + a14.chr + a15.chr + a16.chr + a17.chr + a18.chr + a19.chr + a20.chr + a21.chr + a22.chr + a23.chr + a24.chr + a25.chr + a26.chr + a27.chr + a28.chr + a29.chr + a30.chr + a31.chr + a32.chr  
end

Which prints "c9f4029ce9dcf8ff7f8f1b70edead843". (Script contains comments with code that tried to simulate movsx behavior, but I probably messed up).
So the flag is "ASIS_c9f4029ce9dcf8ff7f8f1b70edead843"