Sexy Pandalog

Osu, Tatakae, Sexy Pandas blog

 

June 9, 2008

Reversing 500 writeup!

Filed under: Blogroll, CTF, prequals, writeups — at 10:39 pm
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)

6 Comments »

  1. Awesome job :D Looking fordward for more solutions like this one :D

    Comment by wzzx — June 9, 2008 @ 10:48 pm

  2. Wonderful analysis! Love that ascii-art xD

    Comment by Tora — June 9, 2008 @ 11:55 pm

  3. absolutely awesome!

    beat’em in vegas =)

    Comment by pof — June 10, 2008 @ 12:21 am

  4. :)
    cool!

    Comment by sionics — June 10, 2008 @ 1:37 am

  5. Holy shit! Hats off to you :D

    Comment by parki — June 10, 2008 @ 9:03 am

  6. 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

Comments RSS

Leave a comment

Valid XHTML 1.0 Valid CSS 2