pwnable.kr collision

MD5 

Message-Digest algorithm 5

임의의 길이의 값을 입력받아서 128비트 길이의 해시값을 출력하는 알고리즘.
단방향 암호화로, 출력값에서 입력값을 복원하는 것은 일반적으로 불가능하다.

같은 입력값이면 항상 같은 출력값이 나온다.

 

흔히 패스워드 암호화에 많이 사용되며, 패스워드를 MD5로 해시해서 나온 값을 저장해둔다. 이 값만 봐서는 본래의 값을 알 수 없다. 패스워드를 제대로 입력했다면 같은 해시값이 튀어나올 것이기 때문에 본래의 키라는 것을 확인할 수는 있다.

 Hash Collision

해시 함수가 서로 다른 두 개의 입력값에 대해 동일한 출력값을 내는 상황.

문제

해시 충돌과 관련된 문제로 보인다. 

일단 주어진 서버에 접속한다.

ls -al 로 어떤 파일들이 있는지 확인해봤다. 보아하니 flag 파일에 내가 원하는 플래그가 있고, col을 한 번 실행해봐야 할 것 같다. col.c를 확인해서 어떤식의 코드인지 분석하고 pwntools를 활용하면 되지 않을까.

 

col 파일을 실행해봤다. 제대로 실행하려면 passcode를 함께 넘겨줘야하는 것 같다. 

col.c 파일에서 passcode를 알아내보자.

#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;
}

col 실행 시 인자가 두개 이상 넘겨지지 않으면 

"usage : ./col [passcode]\n"

가 출력되고, 

passcode의 길이는 20바이트여야 한다. 

char*는 배열의 시작 주소만 가지므로 char*의 크기는 4바이트가 되지만, strlen은 문자열의 길이를 리턴한다.

#include<stdio.h>
#include<string.h>

int main(){
const char *array[5] = {"swing", "30th", "kchabin"};

printf("%d\n", sizeof(array)); //20을 출력(4바이트*5) 
printf("%d\n", sizeof(array[0])); //4를 출력
printf("%d\n", strlen(array[0])); //5를 출력

}

근데 왜 4바이트씩 5인지는 잘 이해가 안된다. -> char* 배열은 문자열 시작 주소를 저장하기에 모든 배열의 크키가 4바이트이다. 

strlen 함수에 문자열 포인터를 넣으면 문자열의 길이가 반환된다. (null 문자 포함x)

 

int* ip = (int*) p; 는 포인터 형변환을 하였으므로 char* p에 들어있는 값을 5등분하겠다는 뜻이다.

 

char* 1바이트 4개를 int*로 변환하니까 argv가 조건 만족하면 20바이트. 

형변환을 통해 20바이트/4바이트 =5. 

반복문을 통해서 5등분한 값을 res에 모두 더한다. 

 

hashcode와 check_password 함수로 알아낸 passcode가 같아야 flag 파일 내용을 출력해주는 것으로 보인다. 

 

check_password 함수를 보면 인자를 char 형식으로 받아서 int로 바꾸는 것 같고, 

4바이트씩 5번 읽어 res에 더하는 것 같다.

총 20바이트 길이라는 것도 잊지 말자. 

 

passcode = hashcode 여야 하니까 

hashcode = 0x21DD09EC 

를 10진수로 바꿔봤는데 되게 큰 수가 나와서 이걸 단수힌 10진수로 바꾸는 게 답은 아닌 것 같고, 

 

합이 0x21DD09EC가 되도록 4바이트씩 5등분한 게 입력값이 되면 될 것 같다. 

 

0x21DD09EC 를 5로 나눈다. 

 

 

16바이트는 0x6c5cec8, 나머지 4바이트는 나머지인 4를 더한 0x6c5cecc로 채운다.

 0x6C5CEC8*4 + 0x06C5CECC = hashcode값

 

 

*엔디언(Endianess) : 컴퓨터의 메모리와 같은 1차원의 공간에 여러 개의 연속된 대상을 배열하는 방법

바이트를 배열하는 방법 - 바이트 순서(Byte Order)

 

빅 엔디언(big-endian) : 최상위 바이트(MSB - Most Significant Byte)부터 차례로 저장하는 방식

- 소프트웨어의 디버그를 편하게 해준다.

- 0x12345678 = 12 34 56 78

리틀 엔디언(little-endian) : 최하위 바이트(LSB - Least Significant Byte)부터 차례로 저장하는 방식

- 메모리에 저장된 값의 하위 바이트들만 사용할 때 별도의 계산이 필요없다.

- 32비트 숫자 0x2A = 2A 00 00 00 -> 앞의 두 바이트/한 바이트만 떼어내면 하위 16비트 또는 8비트를 바로 얻을 수 있다.

미들 엔디언(middle-endian) :  빅/리틀이 아니거나 둘을 모두 지원하는 것

 

./col `python -c 'print "\xc8\xce\xc5\x06"*4 + "\xcc\xce\xc5\x06"'`

 

리틀 엔디언 방식으로 써준다.

-c는 인자를 넘겨줄 때 사용하는 것이라고 한다. 

메타 문자 \x = 16진수 숫자와 일치 

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