reversing.kr CRC1

CRC 알고리즘 연산방법이 왜 그런건가 끙끙 거리다가 그냥 받아드리니 마음이 편해졌다.

CRC 테이블을 생성했을 때, CRC-32 알고리즘 기준으로 설명을 해보자면 CRC-32 초기값은 0xFFFFFFFF 이다.

이 때, 내가 입력한 문자열이 "abcd1234" 라면

첫번째 문자를 CRC-32 값(현재 0xFFFFFFFF)의 최하위 바이트와 xor 을 한다. 

그럼 0x61 ^ 0xFF = 0x61 이고 이 값이 CRC-32 의 테이블 인덱스 값이 된다.

해당 값이 0xAABBCCDD 라고 가정한다면,

새로운 CRC-32 값은 (기존의 CRC-32 값 ( 현재는 0xFFFFFFFF ) <<  8) ^ ( 직전에 구한 테이블 값 (0xAABBCCDD)) 가 된다. 

즉 0x554433DD 

이제 그 다음은 b 에 대해서

CRC-32 값 최하위 바이트 DD 와 b(0x62) 를 연산하면 0xBF 이다

0xBF의 테이블 값이 0x11223344 라고 가정한다면,

새로운 CRC-32 값은 0x4433DD00( 0x554433DD << 8 을 한 값이다.) ^ 0x11223344

0x5511EE44

이것을 문자열 끝까지 반복하는 알고리즘이다.

이제 문제를 IDA를 사용하여 확인해보면

GUI 윈도우 프로그램인데, WinMain을 보면 sub_401070을 호출하고 있다. 이 함수를 분석을 해야한다.

해당 함수를 HexRay 기능을 사용하여 보면 아래와 같다.

이 코드가 전부이고 문자를 여덟개만 받는다. 그 문자열을 256바이트짜리 문자에 0 , 8 , 16 ... 간격으로 넣는데 난 처음에 테이블에다가 넣는다고 착각했는데 사실 이 친구는 CRC 검사를 할 대상 문자열이다.

이 문자열을 대상으로 CRC 값을 생성해내고, 기준값과 검사해서 아니면 Wrong 맞으면 Correct 인데 우리는 CRC 값을 조작해내는게 아니라 기준 CRC 값을 생성해내는 문자열을 알아내는게 문제이다.

이 과정에서 역연산과 연산을 사용하여 문자열을 찾아내면 된다. 문제를 해결하는 키포인트는 결국에는 브루트 포싱이라는 것 그렇다면 n^8 인데 어마어마한 연산량이기 때문에 쉽지 않다.

그렇기 때문에 역연산과 연산을 사용하여 저 시간복잡도를 줄일 수가 있다. 대충 (n^4) * (n^4) 으로 줄일 수 있고 여기에 각종알고리즘을 적절히 사용하면 속도를 더 끌어 올릴 수 있다.

문제에 대한 풀이 코드는 https://github.com/ChaeHanul/reversing.kr/tree/master/CRC1

참조한 글

위키 순환 중복 검사  :  https://ko.wikipedia.org/wiki/%EC%88%9C%ED%99%98_%EC%A4%91%EB%B3%B5_%EA%B2%80%EC%82%AC

 CRC 알고리즘과 취약점 - anch0vy : http://anch0vy.tistory.com/60

CRC 역연산 : http://blog.naver.com/PostView.nhn?blogId=yheekeun&logNo=220729688458

그리고 문제해결에 결정적인 단서를 받은 

reversingkr-CRC1 : http://kyhkyh.tistory.com/entry/reversingkr-CRC1

브루트포싱 해야된다고 쐐기를 박아주셔서 삽질할 시간을 줄여주셨다.

이것보다 CRC2는 훠얼씬 어렵다는데 무서워서 못 풀겠다.