[문제풀이] reversing.kr - CRC1

일단 문제풀이를 바로 시작해보겠다. 

이 문제는 보는 바와 같이 시작부터 사람을 도발한다.

영리하다고 생각하면 도전해보라는..!! 

(멋드러지게 문제를 격파하고 싶었지만 참 구질구질하게 풀어냈다ㅠㅠ)

해당 로직을 파악하는 건 그리 어렵지 않았다. 

흐름을 간단히 설명하자면, 

하나의 긴 문자열에서 순차적으로 문자를 추출해서 CRC 값의 최하위 바이트 값과 XOR 연산을 한 뒤 이를 인덱스로 하여 CRC 테이블의 값을 가져오고 이를 기존 CRC 값에 쉬프트 연산한 값으로 XOR 연산해준다.  

말이 좀 주저리 주저리하네.. ㅡㅡ ...

어째든 아래와 같은 코드가 될 수 있다.  

unsigned __int64 CRC() { byte index = 0; unsigned __int64 crc = 0; for (int i = 0; i <= strlen(Strings); i++) { index = (Strings[i] ^ (crc & 0xff)) & 0xff; crc = ((unsigned __int64)crc >> 8ULL); crc ^= CRCTable[index]; } return crc; }

여기에서 crc 변수는 생성되는 값이고, CRCTable 은 미리 생성된 int64 형 값이다. 

Strings은 CRC 알고리즘이 무결성을 확보하기 위한 주체라고 보면 된다. 

즉 Strings 변수에 포함된 문자열에 따라 CRC 값이 변경된다. 

이 문제는 최종 CRC 값과 문자열이 주어지며 이를 역연산해서 원래 삽입된 문자를 찾아내는 것이다. 

문제에서 내가 입력한 값이 0x00, 0x10, 0x20, 0x30, 0x40, 0x50, 0x60, 0x70 번째에 입력되며 변경된 문자열을 통해 CRC 값을 생성하고 해당 값을 비교하게 된다. 

처음에는 어떻게 역연산이 가능할 지 몰라서 고민했다. 

그러다 검색의 유혹을 뿌리치지 못하고 구글의 도움을 얻었다. 

그래서 역연산까지 방법을 얻었지만 브루트포씽의 범위가 굉장히 넓어 다시 한번 깊은 고민에 빠졌다. 

해서 이미 문제를 푸신 분께 약간의 자문을 얻어 실마리를 얻었다. 

그 때 당시에는 힌트를 들어도 아무것도 떠오르는 게 없었는데 시간이 지나니 뭔가 하나 떠오르기 시작했다.

참 희안하게도 시간이 지나면 뭔가 떠오른다. 

그리고 문제를 풀면 그렇게 애먹었는데도 아 이리 간단했구나 싶다.

이제 한문제 남았다 !!

참고하고 도움을 얻은 사이트는 아래에 별도로 표기해놓겠다. 

References

[1] crc 알고리즘과 취약점, http://anch0vy.tistory.com/60

[2] Reversing.kr CRC1, http://blog.naver.com/wlstngus0504/220606858247