1.- Introduction.
At quals  we hardly had time  to analyse rev500.  However, what we saw  was very
appealing : interesting code obfuscation, use of fpu and random numbers, and the
string “./MathIsHard” suggested  that the algorithm could be  interesting. So we
decided to give it another try with more time.

A brief initial analysis doesn’t bring a lot of information : The binary is a 32
bit ELF for FreeBSD  that listens for connections on port  2600. When we connect
to it we receive 5 dwords containing integers, all of them below 1000.





$ readelf -a ./rev
ELF Header:
  …
  Class:                             ELF32
  OS/ABI:                            UNIX - FreeBSD
  ABI Version:                       0
  Type:                              EXEC (Executable file)
  Machine:                           Intel 80386
  …

Relocation section ‘.rel.plt’ at offset 0×808 contains 43 entries:
 Offset     Info    Type            Sym.Value  Sym. Name
0804e0d4  00000507 R_386_JUMP_SLOT   00000000   random                         
0804e0d8  00000607 R_386_JUMP_SLOT   00000000   recv
0804e0f4  00000e07 R_386_JUMP_SLOT   00000000   socket
0804e0f8  00000f07 R_386_JUMP_SLOT   00000000   send
0804e0fc  00001107 R_386_JUMP_SLOT   00000000   accept
0804e108  00001507 R_386_JUMP_SLOT   00000000   bind
…

2.- Someone has shattered Rev500!

Soon after opening  the program on  IDA we realise  that the code  has suffered
some kind of obfuscation. All the code looks messed up and IDA analysis fails at
finding functions.   Furthermore, we  have  a  lot of   invalid cross references
that make difficult the flow analysis.

A more detailed study of the assembler makes us realise that the functions  have
been divided  in small  pieces and  that those  pieces have  been scattered  all
along the  binary. We  will call  each one  of those  pieces chunk.  Each chunk
executes a bit of the real binary and then calls the next one.

We will illustrate some of the concepts with this example :





.text:0804AB7A                 db 6Dh
.text:0804AB7B                 db 0A3h
.text:0804AB7C
.text:0804AB7C ; =============== S U B R O U T I N E ==========================
.text:0804AB7C
.text:0804AB7C
.text:0804AB7C sub_804AB7C     proc near        ; CODE XREF: sub_804B2F8+1085p
.text:0804AB7C                 pop     eax
.text:0804AB7D                 pop     eax
.text:0804AB7E                 add     esp, 10h
.text:0804AB81                 mov     [ebx], eax
.text:0804AB83                 mov     eax, [ebp-14h]
.text:0804AB86                 mov     eax, [eax]
.text:0804AB88                 mov     eax, [eax+10h]
.text:0804AB8B                 push    ebx
.text:0804AB8C                 mov     ebx, 8049A4Dh
.text:0804AB91                 call    ebx ; sub_8049A4D
.text:0804AB91 sub_804AB7C     endp ; sp-analysis failed
.text:0804AB91
.text:0804AB91 ; —————————————————————————
.text:0804AB93                 db 0D3h ; Ë
.text:0804AB94                 db  5Bh ; [





As we can see,  each chunk begins with  some code that fixes  the stack/register
modifications that  where made  in the  previous chunk  jump. Those  are the two
initial red pop eax in the example.  Then we have some instructions of the  real
program, and then we have a jump to the next chunk( The last three red lines  on
the example ). We  illustrate the generic structure of a chunk in the following
figure :

         /============\   <-- chunk_ini
         | PRE_CHUNK  |
         |============| ^ <-- chunk_data
         |            | |
         |   DATA     | | <== data_size
         |   ...      | |
         |            | |
         |============| v
         | POST_CHUNK |
         \============/   <-- chunk_end  

There are 4 possible variations of post/prechunks :

         /=================================================\
         |  Post_chunk                     Next Pre_chunk  |
         |-------------------------------------------------|
         |  Push Reg                       Pop Reg         |
         |  Mov  Reg,                      Pop Reg         |
         |  Call Reg                                       |
         |-------------------------------------------------|
         |  Pushf                          Popf            |
         |  Stc                                            |
         |  Jb                                             |
         |-------------------------------------------------|
         |  Push                     Not needed            |
         |  Ret                                            |
         |-------------------------------------------------|
         |  Jmp                      Not needed            |
         \=================================================/

This  layer of  obfuscation made  the death  listing analysis  of the  code very
tedious as there were a lot of  invalid cross references. Making the analysis of
the execution  flow difficult  . An in-depth  look at the  actual DATA  of those
chunks showed  us that inside  them there was a  normal c program  compiled with
gcc. We noticed this analysing the calling convention and the stack frames.

In that moment we decided that the fastest approach was to create a program that
reconstructed the binary  to its original state. That program  had to do several
tasks :

 *  Create a  graph with  all the  chunks  of each  function. The  data and  the
 relationships between  them. * Pack  this information together. *  Relocate all
 the calls as its origin relative addr has changed with the code movement. * Get
 all the functions that were called in order to analyse them too. * Relocate the
 calls to  other functions as  the destination addr  has changed too  during the
 binary reconstruction.

The tool we utilized for this  process was radare ( http://radare.nopcode.org/ )
as  their ability  to  be scripted  with  lua  and python  provided  us all  the
functionality we needed and speeded the development.

The output of the program was more or less like :





    [+] Analysing function at 8049891                                          
    [i] Chunk with 2 transitions @ 80495FD
    [i] Chunk with 2 transitions @ 804C38C
    [i] Cached at the end to : 74. Final :124, offset: -51
    [i] Patching short conditional jump with : 50
    [i] Cached at the end to : 46. Final :129, offset: -84
    [i] Patching short conditional jump with : 83
    New function : 41 => 804BCBD
    New function : 57 => 804992B
    New function : 82 => 804C3D0
    New function : 104 => 80493A7
    …
    [+] Analysing function at 804B871
    [+] Analysing function at 804992B
    [i] Chunk with 2 transitions @ 804CFB8
    [i] Chunk with 2 transitions @ 804D813
    [i] Patching conditional jump with : 12
                     current_data_size : 104
                     initial_data_size : 66
    [i] Patching short conditional jump with : 12
    [+] Analysing function at 804BCBD
    [i] Chunk with 2 transitions @ 804CFB8
    [!] Chunk with 2 transitions @ 804D813
    [i] Patching conditional jump with : 12
                     current_data_size : 136
                     initial_data_size : 98
    [i] Patching short conditional jump with : 12
    …
    [+] New segment at 81466E0
    [+] Reloc’ing function [129] from : 8049891 to 81466E0 [5]
    [+] Reloc’ing function [163] from : 80493A7 to 8146770 [5]
    [+] Reloc’ing function [311] from : 804C3D0 to 8146820 [11]
    [+] Reloc’ing function [24] from : 804B871 to 8146960 [0]
    [+] Reloc’ing function [116] from : 804992B to 8146980 [2]
    [+] Reloc’ing function [148] from : 804BCBD to 8146A00 [4]
    [+] Realocing references to : 804BCBD[8146A00]
    [+] Reloc found at 8146709. Patching : 754
    [+] Reloc found at 8146725. Patching : 726
    [+] Reloc found at 8146709. Patching : 754
    ..
    [+] 6 functions have been copied!




And Done!

3.- When the port number, 2600, makes sense!

The result of our pre-process was a file that could not be executed but that had
all their  functions recreated.  That allowed  us to  analyse it  with hexrays,a
wonderful piece  of software, that makes  the life of the  reverser easier!. The
decompiling  of  the program  was  perfect,  so  we  could begin  reversing  its
functionality.

We  skipped  the  creation  of  the  server  and  the  code  that  accepted  new
connections, as that code was similar to other kenshoto services.

So we  begin analysing the  routine that  handles new connections.  It initially
receives 16 bytes from the client and performs the following checks on them :





if ( (_DWORD)recv_buffer_DWORD_1 == do_bswap(‘RIFF’) )                     

{
  if ( recv_buffer_DWORD_3 == do_bswap(‘WAVE’) )

  {
    if ( recv_buffer_DWORD_2 <= 25000 )
    {

      if ( recv_buffer_DWORD_2 > 3 )
      {




The program is expecting a header of a WAVE file, and the next parts of the code
makes  us  suspect   that  we  will   need  more  information   on  the  format.
This link  http://groovit.disjunkt.com/analog/wave/wave.pdf turned  out to  be a
good help for the following analysis.

The next lines of the program searched the fmt and data chunks of the WAVE  file
and processed some checks on it  : Minimum and maximum sample rate,  Format=PCM,
block align=2, and bits per sample = 1.

After those  checks the  fun begins.  The program  creates 800  structures of  4
dwords each  one. And   it stores  its  index   + 200  on the   first one.  Then
the samples of   our wave  file  are  divided in   5 parts.  Each  part,  one by
one, is passed along with the 800 structures to the main processing function.

Each of the 800 structures that has been created are like this :

         /============\
         |  Ind.+200  |  ( 0..1000)
         |============|
         |   FIELD 2  |  Unknown
         |============|
         |   FIELD 3  |  Unknown
         |============|
         |   FIELD 4  |  Unknown
         \============/ 

The “main processing functions” does :

  1  ) It creates  a  copy of the wave headers and data  for each structure, and
  stores its pointer on FIELD4.

  2 )  Creates a discrete sinus of frequency  FIELD 1. With the  same length and
  sample  rate of our file.  This sinus  is stored on the wave  data copy of our
  file  that we made on 1), overwriting its content.

  The formula used to calculate the sin is :

     Sample[i] = 32767 * sin( 2 * pi * freq * i / samples_per_seq )

     Where i = 0 … #SamplesOfOurWave

  3 ) Then it multiplies this sinus with one of the 5 parts of our wave, sample
  by sample, and stores the sum off it on field 2 and 3. This looks like it cal-
  culates the energy of our signal on the frequency freq.

     double FIELD_2_3 = 0;
     for( i=0; i<#SampleOfOurWave/5; i++ )
     	FIELD_2_3 += DiscreteSin[i] * PartOfOurSignal[i];

With all  this information,  the 800  structures will  look like  that after the
processing function ( that we have named Spectral Analysis ) :

         /============\
         |    Freq    |  ( 0..1000)
         |============|
         | Energy of  |
         | our signal |
         | on Freq    |
         |============|
         |  Sin(Freq) |
         \============/ 

Now we can already understand what the last part of the main routine does :





 nSamples_div_5 = v8 / 5;
 ind2 = 0;

 while ( ind2 <= 4 )
 {
    ind = ind2 * nSamples_div_5;

    spectralAnalysis(&pFMT_chunk, SinStructures, 800, ind2 * nSamples_div_5,     
                      nSamples_div_5);

    *(_DWORD *)(4 * ind2++ + 0×804E1A0) =
                      SinStructures[4 * search_max_IND(SinStructures, 800)];

  }
  if ( !memcmp(&final_cmp_buffer, &random_numbers, 0×14u) )

  {
     do_send(s, keyfile, *(_DWORD *)&sz_keyfile);

  }




For each of  the 5 parts  of our signal/wave,  it  calculates its  energy on the
frequencies  200..1000.  Then  it searches  in  all those  800
structures for the highest number and  stores the frequency number on an  array.
So what the program does is to search for the frequency with the  highest energy
for each of the 5 subparts of the  wave and store it on an array. This  array of
5 numbers is  then  compared with  the  5  random  numbers  that we  received at
the beginning. If they match we receive the key as reward  

The solution  that we  used  in  order  to  pass the   challenge is  a
program that  receives 5  numbers and  return a  wave wich   contains 5 diferent
discrete sinus.  As  a   sinus of  a frequency  f, will  have f  as  its maximum
frequency :).

================================================================================

We provide an example implementation in python :

#!/usr/bin/python
import struct
import socket
import math

def makeSin( freq, number_samples, samples_per_seq ) :
    data = ”
    for i in range(0,number_samples):
        data += struct.pack(‘h’, 1000*math.sin( 2*freq*i*math.pi/samples_per_seq ))
    return data

# print ”’Rev 500”’

Host = ‘127.0.0.1‘
Port = 2600

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)

s.connect((Host, Port))
chunk = s.recv(4*5)

print struct.unpack_from(‘LLLLL’, chunk)

if chunk == ”:
    print ‘Error receiving data\n’

number_samples  = 5000
samples_per_sec = 4000

header_fmt  = struct.pack(‘L’, 0×20746d66 )   # fmt
header_fmt += struct.pack(‘L’, 16 )           # size   = 16
header_fmt += struct.pack(‘h’, 1  )           # format = pcm
header_fmt += struct.pack(‘h’, 1  )           # n. Chanels. unused
header_fmt += struct.pack(‘L’, samples_per_sec )
header_fmt += struct.pack(‘L’, 1  )           # Avg. Bytes Sec. unused
header_fmt += struct.pack(‘h’, 2  )           # block align. Bytes/sample*channel
header_fmt += struct.pack(‘h’, 16 )           # bits_per_sample

size_header_data = number_samples * 2
frequencies = struct.unpack_from(‘LLLLL’, chunk)
header_data  = struct.pack(‘L’, 0×61746164       )   # data
header_data += struct.pack(‘L’, size_header_data )
header_data += makeSin( frequencies[0], number_samples/5, samples_per_sec)
header_data += makeSin( frequencies[1], number_samples/5, samples_per_sec)
header_data += makeSin( frequencies[2], number_samples/5, samples_per_sec)
header_data += makeSin( frequencies[3], number_samples/5, samples_per_sec)
header_data += makeSin( frequencies[4], number_samples/5, samples_per_sec)

size = len(header_fmt) + len(header_data) + 4

header  = struct.pack(’<L’, 0×46464952 )  # RIFF
header += struct.pack(’<L’, size )        # size
header += struct.pack(’<L’, 0×45564157 )  # WAVE

s.send( header)
s.send( header_fmt)
s.send( header_data )

file = header + header_fmt + header_data
print s.recv(1024)