Pwnable.kr - Collision

— Written by — 10 min read

collision

One of my objective in 2020 is to level up in Reverse Engineering. Since I am starting from zero I got few people recommend http://pwnable.kr which appear to have a reasonable curve of difficulty making it ideal for learning.

If you have other recommandations for good ressources to learn and practices Reverse Engineering feels free to let me know below in a comment or contact me ;)

That being said, here is my write-up for the second challenge of pwnable.kr: Collision.

Let’s go!


Challenge Description

Collision

Daddy told me about cool MD5 hash collision today.
I wanna do something like that too!

ssh col@pwnable.kr -p2222 (pw:guest)

This gives us an SSH access to a box with a hint that this challenge seems to be about MD5 Collision.

Hash Collision

In order to get the right context, here is a definition of Hash Collision:

A Hash Collision Attack is an attempt to find two input strings of a hash function that produce the same hash result. Because hash functions have infinite input length and a predefined output length, there is inevitably going to be the possibility of two different inputs that produce the same output hash. If two separate inputs produce the same hash output, it is called a collision. This collision can then be exploited by any application that compares two hashes together – such as password hashes, file integrity checks, etc.

https://privacycanada.net/hash-functions/hash-collision-attack/

Test & Analysis

Once connected on the box we find both a col bin and its source code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
[hg8@archbook ~]$ ssh [email protected] -p2222
[email protected]'s password:
____ __ __ ____ ____ ____ _ ___ __ _ ____
| \| |__| || \ / || \ | | / _] | |/ ]| \
| o ) | | || _ || o || o )| | / [_ | ' / | D )
| _/| | | || | || || || |___ | _] | \ | /
| | | ` ' || | || _ || O || || [_ __ | \| \
| | \ / | | || | || || || || || . || . \
|__| \_/\_/ |__|__||__|__||_____||_____||_____||__||__|\_||__|\_|

Last login: Sun Jul 5 13:05:36 2020 from 10.10.10.10
col@pwnable:~$ ls -l
total 16
-r-sr-x--- 1 col_pwn col 7341 Jun 11 2014 col
-rw-r--r-- 1 root root 555 Jun 12 2014 col.c
-r--r----- 1 col_pwn col_pwn 52 Jun 11 2014 flag
col@pwnable:~$

Let’s pull everything to work on it locally:

1
[hg8@archbook ~]$ scp -P2222 [email protected]:col.c .

The programs takes a 20 bytes long passcode and do some kind of check on it:

1
2
3
4
5
[hg8@archbook ~]$ ./col A
passcode length should be 20 bytes

[hg8@archbook ~]$ ./col AAAAAAAAAAAAAAAAAAAA
wrong passcode.

Dynamic Analysis

I always like to start off with Dynamic Analysis in order to get a quick understanding of what the program is doing “behind the hood”.

To do so I will use GDB with the excellent GEF plugin to help in the task.

First let’s open the executable, set a break point to main function, give a 20 char string as argument and see what’s going on:

1
2
3
4
5
6
[hg8@archbook ~]$ gdb col
GNU gdb (GDB) 9.2

gef➤ break main
Breakpoint 1 at 0x11b7
gef➤ r "AAAAAAAAAAAAAAAAAAAA"

The program immediately break and we get a bunch of informations:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
Breakpoint 1, 0x00005555555551b7 in main ()
[ Legend: Modified register | Code | Heap | Stack | String ]
──────────────────────────────────────────────────────────────────────────────────────────────── registers ────
$rax : 0x00005555555551b3 → <main+0> push rbp
$rbx : 0x0
$rcx : 0x00007ffff7fae5780x00007ffff7fb09600x0000000000000000
$rdx : 0x00007fffffffe1b00x00007fffffffe496"USER=hg8"
$rsp : 0x00007fffffffe0a00x0000555555555260 → <__libc_csu_init+0> endbr64
$rbp : 0x00007fffffffe0a00x0000555555555260 → <__libc_csu_init+0> endbr64
$rsi : 0x00007fffffffe1980x00007fffffffe45d"/home/hg8/pwnable.kr/collision/col"
$rdi : 0x2
$rip : 0x00005555555551b7 → <main+4> sub rsp, 0x10
$r8 : 0x0
$r9 : 0x00007ffff7fe22c0 → <_dl_fini+0> endbr64
$r10 : 0x0
$r11 : 0x0
$r12 : 0x0000555555555070 → <_start+0> endbr64
$r13 : 0x0
$r14 : 0x0
$r15 : 0x0
$eflags: [ZERO carry PARITY adjust sign trap INTERRUPT direction overflow resume virtualx86 identification]
$cs: 0x0033 $ss: 0x002b $ds: 0x0000 $es: 0x0000 $fs: 0x0000 $gs: 0x0000
──────────────────────────────────────────────────────────────────────────────────────────────────── stack ────
0x00007fffffffe0a0│+0x0000: 0x0000555555555260 → <__libc_csu_init+0> endbr64 ← $rsp, $rbp
0x00007fffffffe0a8│+0x0008: 0x00007ffff7e15002 → <__libc_start_main+242> mov edi, eax
0x00007fffffffe0b0│+0x0010: 0x00007fffffffe1980x00007fffffffe45d"/home/hg8/pwnable.kr/collision/col"
0x00007fffffffe0b8│+0x0018: 0x0000000200000000
0x00007fffffffe0c0│+0x0020: 0x00005555555551b3 → <main+0> push rbp
0x00007fffffffe0c8│+0x0028: 0x00007ffff7e14afd → <init_cacheinfo+301> mov rbp, rax
0x00007fffffffe0d0│+0x0030: 0x0000000000000000
0x00007fffffffe0d8│+0x0038: 0xa7393fcc1a757ccd
────────────────────────────────────────────────────────────────────────────────────────────── code:x86:64 ────
0x5555555551b2 <check_password+73> ret
0x5555555551b3 <main+0> push rbp
0x5555555551b4 <main+1> mov rbp, rsp
0x5555555551b7 <main+4> sub rsp, 0x10
0x5555555551bb <main+8> mov DWORD PTR [rbp-0x4], edi
0x5555555551be <main+11> mov QWORD PTR [rbp-0x10], rsi
0x5555555551c2 <main+15> cmp DWORD PTR [rbp-0x4], 0x1
0x5555555551c6 <main+19> jg 0x5555555551ea <main+55>
0x5555555551c8 <main+21> mov rax, QWORD PTR [rbp-0x10]
────────────────────────────────────────────────────────────────────────────────────────────────── threads ────
[#0] Id 1, Name: "col", stopped 0x5555555551b7 in main (), reason: BREAKPOINT
──────────────────────────────────────────────────────────────────────────────────────────────────── trace ────
[#0] 0x5555555551b7 → main()
───────────────────────────────────────────────────────────────────────────────────────────────────────────────

We notice a function called check_password, that’s very probably where the magic happen. Let’s use ni to jump a bunch of time until we arrive to the said function:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
gef➤  ni
0x0000555555555224 in main ()
[ Legend: Modified register | Code | Heap | Stack | String ]
──────────────────────────────────────────────────────────────────────────────────────────────── registers ────
$rax : 0x00007fffffffe481"AAAAAAAAAAAAAAAAAAAA"
$rbx : 0x0
$rcx : 0x1
$rdx : 0x00007fffffffe481"AAAAAAAAAAAAAAAAAAAA"
$rsp : 0x00007fffffffe0900x00007fffffffe1980x00007fffffffe45d"/home/hugo/pwnable.kr/collision/col"
$rbp : 0x00007fffffffe0a00x0000555555555260 → <__libc_csu_init+0> endbr64
$rsi : 0x00007fffffffe1980x00007fffffffe45d"/home/hg8/pwnable.kr/collision/col"
$rdi : 0x00007fffffffe481"AAAAAAAAAAAAAAAAAAAA"
$rip : 0x0000555555555224 → <main+113> call 0x555555555169 <check_password>
$r8 : 0x0
$r9 : 0x00007ffff7fe22c0 → <_dl_fini+0> endbr64
$r10 : 0x000055555555442f0x73006e656c727473 ("strlen"?)
$r11 : 0x00007ffff7f504a0 → <__strlen_avx2+0> endbr64
$r12 : 0x0000555555555070 → <_start+0> endbr64
$r13 : 0x0
$r14 : 0x0
$r15 : 0x0
$eflags: [zero carry PARITY ADJUST sign trap INTERRUPT direction overflow resume virtualx86 identification]
$cs: 0x0033 $ss: 0x002b $ds: 0x0000 $es: 0x0000 $fs: 0x0000 $gs: 0x0000
──────────────────────────────────────────────────────────────────────────────────────────────────── stack ────
0x00007fffffffe090│+0x0000: 0x00007fffffffe1980x00007fffffffe45d"/home/hugo/pwnable.kr/collision/col" ← $rsp
0x00007fffffffe098│+0x0008: 0x0000000200000000
0x00007fffffffe0a0│+0x0010: 0x0000555555555260 → <__libc_csu_init+0> endbr64 ← $rbp
0x00007fffffffe0a8│+0x0018: 0x00007ffff7e15002 → <__libc_start_main+242> mov edi, eax
0x00007fffffffe0b0│+0x0020: 0x00007fffffffe1980x00007fffffffe45d"/home/hugo/pwnable.kr/collision/col"
0x00007fffffffe0b8│+0x0028: 0x0000000200000000
0x00007fffffffe0c0│+0x0030: 0x00005555555551b3 → <main+0> push rbp
0x00007fffffffe0c8│+0x0038: 0x00007ffff7e14afd → <init_cacheinfo+301> mov rbp, rax
────────────────────────────────────────────────────────────────────────────────────────────── code:x86:64 ────
0x555555555219 <main+102> lock add rax, 0x8
0x55555555521e <main+107> mov rax, QWORD PTR [rax]
0x555555555221 <main+110> mov rdi, rax
0x555555555224 <main+113> call 0x555555555169 <check_password>
0x555555555169 <check_password+0> push rbp
0x55555555516a <check_password+1> mov rbp, rsp
0x55555555516d <check_password+4> mov QWORD PTR [rbp-0x18], rdi
0x555555555171 <check_password+8> mov rax, QWORD PTR [rbp-0x18]
0x555555555175 <check_password+12> mov QWORD PTR [rbp-0x8], rax
0x555555555179 <check_password+16> mov DWORD PTR [rbp-0xc], 0x0
────────────────────────────────────────────────────────────────────────────────────── arguments (guessed) ────
check_password (
$rdi = 0x00007fffffffe481"AAAAAAAAAAAAAAAAAAAA",
$rsi = 0x00007fffffffe1980x00007fffffffe45d"/home/hg8/pwnable.kr/collision/col",
$rdx = 0x00007fffffffe481"AAAAAAAAAAAAAAAAAAAA"
)
────────────────────────────────────────────────────────────────────────────────────────────────── threads ────
[#0] Id 1, Name: "col", stopped 0x555555555224 in main (), reason: SINGLE STEP
──────────────────────────────────────────────────────────────────────────────────────────────────── trace ────
[#0] 0x555555555224 → main()
──────────────────

We can see that our password got set in $rdi and $rdx registers. At this point I put up a breakpoint on check_password function but doesn’t quite understood what exactly was going on (except some loop and calculations).
Let’s continue to see what happen in main once check_password return something:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
0x0000555555555229 in main ()
[ Legend: Modified register | Code | Heap | Stack | String ]
──────────────────────────────────────────────────────────────────────────────────────────────── registers ────
$rax : 0x46464645
$rbx : 0x0
$rcx : 0x1
$rdx : 0x10
$rsp : 0x00007fffffffe0900x00007fffffffe1980x00007fffffffe45d"/home/hugo/pwnable.kr/collision/col"
$rbp : 0x00007fffffffe0a00x0000555555555260 → <__libc_csu_init+0> endbr64
$rsi : 0x00007fffffffe1980x00007fffffffe45d"/home/hg8/pwnable.kr/collision/col"
$rdi : 0x00007fffffffe481"AAAAAAAAAAAAAAAAAAAA"
$rip : 0x0000555555555229 → <main+118> mov rdx, QWORD PTR [rip+0x2e18] # 0x555555558048 <hashcode>
$r8 : 0x0
$r9 : 0x00007ffff7fe22c0 → <_dl_fini+0> endbr64
$r10 : 0x000055555555442f0x73006e656c727473 ("strlen"?)
$r11 : 0x00007ffff7f504a0 → <__strlen_avx2+0> endbr64
$r12 : 0x0000555555555070 → <_start+0> endbr64
$r13 : 0x0
$r14 : 0x0
$r15 : 0x0
$eflags: [zero carry parity adjust sign trap INTERRUPT direction overflow resume virtualx86 identification]
$cs: 0x0033 $ss: 0x002b $ds: 0x0000 $es: 0x0000 $fs: 0x0000 $gs: 0x0000
──────────────────────────────────────────────────────────────────────────────────────────────────── stack ────
0x00007fffffffe090│+0x0000: 0x00007fffffffe1980x00007fffffffe45d"/home/hg8/pwnable.kr/collision/col" ← $rsp
0x00007fffffffe098│+0x0008: 0x0000000200000000
0x00007fffffffe0a0│+0x0010: 0x0000555555555260 → <__libc_csu_init+0> endbr64 ← $rbp
0x00007fffffffe0a8│+0x0018: 0x00007ffff7e15002 → <__libc_start_main+242> mov edi, eax
0x00007fffffffe0b0│+0x0020: 0x00007fffffffe1980x00007fffffffe45d"/home/hg8/pwnable.kr/collision/col"
0x00007fffffffe0b8│+0x0028: 0x0000000200000000
0x00007fffffffe0c0│+0x0030: 0x00005555555551b3 → <main+0> push rbp
0x00007fffffffe0c8│+0x0038: 0x00007ffff7e14afd → <init_cacheinfo+301> mov rbp, rax
────────────────────────────────────────────────────────────────────────────────────────────── code:x86:64 ────
0x55555555521e <main+107> mov rax, QWORD PTR [rax]
0x555555555221 <main+110> mov rdi, rax
0x555555555224 <main+113> call 0x555555555169 <check_password>
0x555555555229 <main+118> mov rdx, QWORD PTR [rip+0x2e18] # 0x555555558048 <hashcode>
0x555555555230 <main+125> cmp rax, rdx
0x555555555233 <main+128> jne 0x55555555524d <main+154>
0x555555555235 <main+130> lea rdi, [rip+0xe07] # 0x555555556043
0x55555555523c <main+137> mov eax, 0x0
0x555555555241 <main+142> call 0x555555555050 <system@plt>
────────────────────────────────────────────────────────────────────────────────────────────────── threads ────
[#0] Id 1, Name: "col", stopped 0x555555555229 in main (), reason: SINGLE STEP
──────────────────────────────────────────────────────────────────────────────────────────────────── trace ────
[#0] 0x555555555229 → main()
───────────────────────────────────────────────────────────────────────────────────────────────────────────────
gef➤

The returns value get stored in $rax :

1
0x5555555551ac <check_password+67> mov    eax, DWORD PTR [rbp-0xc]

Then a comparaison between the returned value of check_password and 0x21dd09ec is being done:

1
0x555555555229 <main+118>   mov  rdx, QWORD PTR [rip+0x2e18]   # 0x555555558048 <hashcode>
1
$rdx   : 0x21dd09ec

Let’s edit the value we have in $rax to match 0x21dd09ec (568134124):

1
2
3
gef➤  print $rax
$2 = 0x46464645
gef➤ set $rax=568134124

We continue the execution and we can see the bin trying to display the flag:

1
2
3
4
5
6
gef➤  c
Continuing.
[Detaching after vfork from child process 986]
/bin/cat: flag: No such file or directory
[Inferior 1 (process 916) exited normally]
gef➤

Alright! We now understood the big picture of what’s going on behind the hood and what kind of check is being made by the bin. Let’s now take a look at the source code to find a proper way to exploit the check_password function without using a debugger.

Source Code Analysis

Let’s a take a look at the source now:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <stdio.h>
#include <string.h>
unsigned long hashcode = 0x21DD09EC;
unsigned long check_password(const char* p){
int* ip = (int*)p;
int i;
int res=0;
for(i=0; i<5; i++){
res += ip[i];
}
return res;
}

int main(int argc, char* argv[]){
if(argc<2){
printf("usage : %s [passcode]\n", argv[0]);
return 0;
}
if(strlen(argv[1]) != 20){
printf("passcode length should be 20 bytes\n");
return 0;
}

if(hashcode == check_password( argv[1] )){
system("/bin/cat flag");
return 0;
}
else
printf("wrong passcode.\n");
return 0;
}

Let’s break things down. First the check of our password:

1
2
3
4
5
6
7
unsigned long hashcode = 0x21DD09EC;
[...]

if(hashcode == check_password( argv[1] )){
system("/bin/cat flag");
return 0;
}

The function check_password() take our password as argument and should return 0x21DD09EC in order to have the flag displayed. In decimal this gives:

1
2
>>> int("0x21DD09EC", 16)
568134124

Let’s now focus on the check_password() function since the magic is happening here.
We know it needs to returns 568134124 in order to pass the check and displays the flag.

1
2
3
4
5
6
7
8
9
unsigned long check_password(const char* p){
int* ip = (int*)p;
int i;
int res=0;
for(i=0; i<5; i++){
res += ip[i];
}
return res;
}

The function is quite short but no so straightforward.

Let’s decompose line by line to understand what’s going on.

  1. The char pointer passed as parameter is cast to an int pointer: (int*)p;. ip is an array of pointers starting with the pointer to p.
    Example: char* p = "ABCD" = "\\x41\\x42\\x43\\x44", int* ip = 0x44434241

  2. The char array is iterated 4 bytes at a time (4 * 5 = 20 bytes of the passcode), then summed up into res.

    1
    2
    3
    for(i=0; i<5; i++){
    res += ip[i];
    }
  3. The sum results get returned.

Exploitation

Manual exploitation

So we understood we need our passcode 5 parts sum to be equal to 0x21DD09EC. Now it’s math time!

1
2
3
4
5
6
7
8
9
10
11
12
>>> 0x21DD09EC
568134124
>>> 568134124 / 5
113626824
>>> 568134124 - 4 * 113626824
113626828
>>> 4 * 113626824 + 113626828
568134124
>>> hex(113626824)
'0x6c5cec8'
>>> hex(113626828)
'0x6c5cecc'

Alright, we have all the 4 parts of our password. Since we are working with C, integers are stored in little-endian format. Therefore the byte order of the integers need to be reversed.

Using Python this gives:

1
2
3
[hg8@archbook ~]$ python -c 'print "\xc8\xce\xc5\x06" * 4 + "\xcc\xce\xc5\x06"'

[hg8@archbook ~]$

Nothing gets printed since those are non-printable chars.

Let’s now use it to solve the challenge:

1
2
col@pwnable:~$ ./col $(python -c 'print "\xc8\xce\xc5\x06" * 4 + "\xcc\xce\xc5\x06"')
daddy! I just managed to create a hash collision :)

Using pwntools

A simple challenge like this one is a good occasion to try our hand on pwntools which can probably comes very useful in the future for more complex challenges.

Pwntools is a CTF framework and exploit development library. Written in Python, it is designed for rapid prototyping and development, and intended to make exploit writing as simple as possible.

After installing the tool let’s create a simple script to solve the challenge.

First let’s connect to the server:

1
2
3
from pwn import *

server = ssh('col', 'pwnable.kr', 2222, 'guest')

Pop a shell and run ./col process with our payload as argument. Here we use the very useful pack function from pwnlib in order to convert our hex values to little endian:

1
shell = server.process(['./col', p32(0x6c5cec8) * 4 + p32(0x6c5cecc)])

After closing the connection and printing the result the final script looks like this:

1
2
3
4
5
6
7
8
9
10
11
#!/usr/bin/env python

from pwn import *

server = ssh('col', 'pwnable.kr', 2222, 'guest')
shell = server.process(['./col', p32(0x6c5cec8) * 4 + p32(0x6c5cecc)])
result = shell.recvall()
shell.close()
server.close()

print("Flag: {}".format(result.decode("utf-8")))

Running it:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
[hg8@archbook ~]$ python pwntools-exp.py
[+] Connecting to pwnable.kr on port 2222: Done
[*] [email protected]:
Distro Ubuntu 16.04
OS: linux
Arch: amd64
Version: 4.4.179
ASLR: Enabled
[+] Starting remote process './col' on pwnable.kr: pid 82641
[+] Receiving all data: Done (52B)
[*] Stopped remote process 'col' on pwnable.kr (pid 82641)
[*] Closed connection to 'pwnable.kr'

Flag: daddy! I just managed to create a hash collision :)

That’s it folks! As always do not hesitate to contact me for any questions or feedbacks!

See you next time ;)

-hg8



CTFpwnableToddler's Bottle
, , ,