[pwnable] pwnable.kr collision (hash function, hash collision, md5 hash collision)
Problem
Daddy told me about cool MD5 hash collision today.
I wanna do something like that too!
ssh col@pwnable.kr -p2222 (pw:guest)
- Hash Function
- 해시 함수는 입력된 데이터를 고정된 길이의 출력 값(해시 값)으로 변환하는 함수
- 해시 함수는 암호학에서 중요한 역할을 하며, 주로 데이터 무결성 검사나 디지털 서명 등에 사용됨
- MD5
- Message-Digest Algorithm 5의 약자로, 128비트 길이의 해시 값을 생성하는 해시 함수.
- MD5는 한때 많이 사용되었지만, 해시 충돌 문제로 인해 현재는 안전하지 않은 알고리즘으로 간주
- Hash Collision
- 해시 충돌이란 서로 다른 입력값이 동일한 해시 값을 생성하는 현상을 의미.
- 해시 함수의 이상적인 특성은 서로 다른 입력값이 서로 다른 해시 값을 생성하는 것이지만, 해시 함수는 고정된 길이의 출력을 제공하므로 충분히 큰 입력 집합에서는 같은 해시 값이 생성되는 경우가 발생할 수밖에 없음.
- MD5 충돌의 문제점
- 두 개의 서로 다른 입력값을 사용해 동일한 MD5 해시 값을 생성할 수 있음.
- 이를 통해 악의적인 사용자는 파일을 위조하여, 원본 파일과 동일한 MD5 해시를 가지도록 만들 수 있음
- 이로 인해 MD5를 기반으로 한 무결성 검사 및 인증 시스템의 보안이 위험에 처하게 됨.
- 예시
- 해시 충돌은 예를 들어 어떤 사용자가 두 개의 파일을 만들어서, 파일의 내용은 다르지만 MD5 해시 값이 동일하도록 조작할 수 있다는 것을 의미.
- 이로 인해 원본 파일과 악성 파일이 같은 해시 값을 가지게 되어, 파일 무결성을 체크하는 시스템에서 이를 구별할 수 없게 됨
Exploration
col 파일을 통해 flag 값을 읽어들이는 것으로 확인
col@pwnable:~$ ls -lahr
total 36K
drwxr-xr-x 2 root root 4.0K Oct 23 2016 .pwntools-cache
dr-xr-xr-x 2 root root 4.0K Aug 20 2014 .irssi
-r--r----- 1 col_pwn col_pwn 52 Jun 11 2014 flag
-rw-r--r-- 1 root root 555 Jun 12 2014 col.c
-r-sr-x--- 1 col_pwn col 7.2K Jun 11 2014 col
d--------- 2 root root 4.0K Jun 12 2014 .bash_history
drwxr-xr-x 116 root root 4.0K Oct 30 2023 ..
drwxr-x--- 5 root col 4.0K Oct 23 2016 .
col.c 파일을 살펴보면
먼저 passcode를 입력받고 길이가 20byte인지 확인한다.
20byte 가 맞으면 check_password로 값을 변환하고 hashcode와 값이 같으면 flag를 출력한다.
#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;
}
check_password 함수를 좀 더 살펴보자.
passcode 문자열을 정수형 포인터로 type casting 한 뒤 4byte 씩 읽어와서 res에 합산하고 반환한다.
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;
}
포인터변수는 4바이트(리틀엔디안)기 때문에 (x86_64 비트 운영체제는 기본적으로 리틀엔디안을 사용)
$ uname -m
x86_64
res = ip[0] + ip[1] + ip[2] + ip[3] + ip[4]
정리해보면 0x21DD09EC를 5번에 나누어서 입력값에 넣어야한다.
0x21DD09EC / 5 = 0x6C5CEC8
하지만
0x6C5CEC8 * 5 = 0x21DD09E8 로 hashcode와 0x4가 차이난다.
결론은...
0x6C5CEC8 * 4 + 0x6C5CECC 이렇게 프로그램에 입력값으로 넣어줘야 한다.
Solution
일단 0x6C5CEC8, 0x6C5CECC 헥스값을 리틀엔디안으로 변환해준다.
import struct
def to_little_endian(value):
# 4바이트 (32비트) 값을 리틀 엔디안 바이트로 변환
little_endian_bytes = struct.pack('<I', value)
return little_endian_bytes
value = 0x6C5CEC8
result1 = to_little_endian(value)
print("리틀 엔디안 변환 결과 (바이트):", result1)
print("리틀 엔디안 변환 결과 (16진수):", result1.hex())
value = 0x6C5CECC
result2 = to_little_endian(value)
print("리틀 엔디안 변환 결과 (바이트):", result2)
print("리틀 엔디안 변환 결과 (16진수):", result2.hex())
리틀 엔디안 변환 결과 (바이트): b'\xc8\xce\xc5\x06'
리틀 엔디안 변환 결과 (16진수): c8cec506
리틀 엔디안 변환 결과 (바이트): b'\xcc\xce\xc5\x06'
리틀 엔디안 변환 결과 (16진수): cccec506
결과를 합해서 col 바이너리의 인풋으로 입력한다.
col@pwnable:~$ ./col `python -c 'print "\xc8\xce\xc5\x06" * 4 + "\xcc\xce\xc5\x06"'`
daddy! I just managed to create a hash collision :)트러블슈팅
직접 문자열을 합해서 넣으면 이스케이프 문자 자체를 문자열로 인식해서 실제 바이트로 변환되지 않아 20 byte로 인식이 안된다.
$ ./col \xc8\xce\xc5\x06\xc8\xce\xc5\x06\xc8\xce\xc5\x06\xc8\xce\xc5\x06\xcc\xce\xc5\x06
passcode length should be 20 bytes
파이썬의 문자열 처리
파이썬에서 문자열 리터럴을 작성할 때, '\xNN'과 같은 형식은 이스케이프 시퀀스로 인식되어, 해당하는 값을 바이트 단위로 변환한다.
예를 들어, "\xc8\xce\xc5\x06"는 파이썬에서 실제로 4바이트의 값으로 변환된다.
- \xc8는 200 (10진수)
- \xce는 206 (10진수)
- \xc5는 197 (10진수)
- \x06는 6 (10진수)
따라서, 파이썬에서 print("\xc8\xce\xc5\x06")라고 하면, 이 문자열은 실제로 네 개의 바이트 값으로 변환되어 출력된다.
그리고 쉘은 자체적으로 이스케이프 시퀀스를 해석하지 않으므로, 이스케이프 시퀀스를 처리하려면 파이썬 같은 언어를 사용해야한다.
print함수로 이스케이프값을 출력하면 주어진 문자열을 실제 바이트 단위로 출력하게 되어, 쉘에서 그 값이 그대로 프로그램에 전달(stdout)된다.