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
![:)](rev500_files/icon_smile.gif)
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)
Awesome job
Looking fordward for more solutions like this one ![:D](rev500_files/icon_biggrin.gif)
Comment by wzzx — June 9, 2008 @ 10:48 pm
Wonderful analysis! Love that ascii-art xD
Comment by Tora — June 9, 2008 @ 11:55 pm
absolutely awesome!
beat’em in vegas =)
Comment by pof — June 10, 2008 @ 12:21 am
cool!
Comment by sionics — June 10, 2008 @ 1:37 am
Holy shit! Hats off to you![:D](rev500_files/icon_biggrin.gif)
Comment by parki — June 10, 2008 @ 9:03 am
Amazing!! Just brilliant!! Yo tambien me quito el sombrero ante los sexy pandas with gambas. You guys are going to kick ass in Las Vegas, oh yeah baby!!
Comment by Juan A Naranjo — June 10, 2008 @ 12:39 pm