#2 Pwnable.kr : collision 문제풀이

collision

---

알아야 할 기본지식!

해시 충돌이란?

• 해시 함수가 서로 다른 두 개의 입력값에 대해 동일한 출력값을 내는 상황을 의미한다.
• 해시 함수가 무한한 가짓수의 입력값을 받아 유한한 가짓수의 출력값을 생성하는 경우, 비둘기집 원리에 의해 해시 충돌은 항상 존재한다.
• 해시 충돌은 해시 함수를 이용한 자료구조나 알고리즘의 효율성을 떨어뜨리며, 따라서 해시 함수는 해시 충돌이 자주 발생하지 않도록 구성되어야 한다. 
• 암호학적 해시 함수의 경우 해시 함수의 안전성을 깨뜨리는 충돌 공격이 가능할 수 있기 때문에 의도적인 해시 충돌을 만드는 것이 어렵도록 만들어야 한다.

---

Message-Digest algorithm 5 (MD5)

 

• 임의의 길이의 값을 입력받아서 128비트 길이의 해시값을 출력하는 알고리즘이다. 1991년 설계되었다.
• MD5는 단방향 암호화이기 때문에 출력값에서 입력값을 복원하는 것은 일반적으로 불가능하다. 같은 입력값이면 항상 같은 출력값이 나오고, 서로 다른 입력값에서 같은 출력값이 나올 확률은 극히 낮다(0은 아니며 발생할 수 있다.).
• 흔히 패스워드 암호화에 많이 사용되는데, 패스워드를 MD5로 해시해서 나온 값을 저장해 두는 것이다.
• 이렇게 하면 운영자나, 데이터를 무단으로 뜯어본 자도 이 값만 봐서는 본래의 값 자체는 알 수 없게 된다.
• 비밀번호를 정확하게 입력했다면 같은 해시값이 튀어나오므로, 본래의 키라는 것을 확인할 수는 있는 것이다.
• 단방향 암호화이기 때문에 MD5 해시값에서 원래의 데이터를 찾아내는것은 불가능하며(원문을 해시 계산 과정에서 비트 단위로 박살내버린다), 크래커들은 "같은 MD5를 갖는 문자열", 즉 "충돌"(Collision)을 찾아내는 데 주력한다.
• 어쨌든 MD5값이 같으면 같은 문자열이라고 판단하기 때문이며 이는 모든 단방향 암호화에 통용되는 기법이다.

---

1. ls -al을 확인해보니, col.c 가 핵심인듯 하다.

col@pwnable:~$ ls -al
total 36
drwxr-x---   5 root    col     4096 Oct 23  2016 .
drwxr-xr-x 116 root    root    4096 Nov 11  2021 ..
d---------   2 root    root    4096 Jun 12  2014 .bash_history
-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
dr-xr-xr-x   2 root    root    4096 Aug 20  2014 .irssi
drwxr-xr-x   2 root    root    4096 Oct 23  2016 .pwntools-cache

 

 

 

2. col.h를 열어서 코드를 분석 해보자.

vi col.h

• check_password()함수는 받은 인자를 int형 포인터로 형변환을 해서 for 문을 돌려준다.
• for 문을 돌리면서 4바이트씩 참조를 해 res에 값을 누적시키고 마지막에 res를 반환한다.
• 그리고 반환된 res와 hashcode 값(0x21DD09EC)과 동일하면, system("/bin/cat flag"); 가 실행된다.

 

 

 

3.이제 hashcode 값을 5로 나누어봤더니 0x6C5CEC8이 나오는데, 나머지가 4 이므로 ,

0x21DD09EC = 0x6C5CEC8*4 + 0x6C5CECC 이런식으로 해주면 될 것 같다.

 

 

 

4.Little Endian 방식이므로 2바이트씩 뒤집어서 입력해주면 성공!

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

 

 

 

5. 위에서 얻은 daddy! I just managed to create a hash collision :) 이 문구가 정답인듯 하다 맞는지 확인 해보자!

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