Codegate 2018 예선 후기 + 간략한 풀이

2월 3일 오전 9시부터 4일 오전 9시까지 24시간동안 코드게이트 예선이 있었습니다. 원래는 딱히 팀도 못 구했고 요새 알고리즘 공부를 하느라 해킹쪽을 사실상 손 떼고 있는 상황이라 아예 관심을 끄고 있었는데 저희 과에서 대학생부로 출전하는 팀이 예선을 같이 해보자길래 어차피 할것도 없겠다 싶어서 한번 문제를 봤습니다. 전날 늦게 뻗어자고 또 점심 약속이 있어서 돌아다니고 오느라 저는 오후 5시쯤부터 대회를 시작했습니다.

다른 분야는 어차피 저보다 훨씬 잘하는 팀원들이 알아서 풀어줄테니 저는 암호학 문제로 바로 뛰어들었습니다.(아마 팀원들도 암호학 문제를 위해서 저보고 같이 하자고 했을 것입니다.) 하나는 TLS 통신 관련 문제(miro), 다른 하나는 RSA 문제(RSAbaby)였습니다.

miro의 경우, TLS 통신쪽은 아는게 없어서 대체 어느 부분이 공격 포인트인지 감을 잡을 수가 없었습니다. 결국 풀어내지 못했고 끝나고 나서야 안 사실인데, 서버 인증서의 N이 굉장히 쉽게 소인수분해가 가능해 그냥 그것을 이용해 통신을 들여다보면 되는 문제였습니다 ㅡ,.ㅡ.. pcap 파일에서 인증서를 추출하긴 했는데 N을 왜 소인수분해해볼 생각을 안했을까요ㅠㅠ 그래도 이번 기회에 무선 통신쪽을 접해봤으니 다음 번에 비슷한 문제가 나오면 조금 더 수월하게 풀 수 있을 것 같습니다.

RSAbaby의 경우, N, e, Cipher 외에도 g = d*(p-0xdeadbeef), h = (d+p)^(d-p)가 추가로 주어진 상황에서 평문을 찾아내는 문제였습니다. N을 소인수분해하거나 d를 찾아내면 되겠다 싶었지만, 맨 처음에는 대체 g와 h를 어떤 식으로 활용하라는건지 감이 전혀 오지 않았습니다. SCTF에 나왔던 문제와 비슷하게 d나 p의 partial bits를 알 때 복원하는 문제인건가, 혹시 g가 적절하게 소인수분해가 되지는 않을까, 뭐 온갖 시도를 다 해보았지만 전부 헛수고였고 그렇게 새벽 2시까지 허송세월을 하다가 갑자기 깨달음이 와서 문제를 풀어낼 수 있었습니다.

그 깨달음은 바로 덧셈, 뺄셈, 곱셈, XOR 연산 모두 상위 비트가 하위 비트에 영향을 줄 수 없는 연산이라는 것이었습니다. 그렇기 때문에 임의의 m에 대해, d, p, g, h의 하위 m비트를 각각 d_partial, p_partial, g_partial, h_partial이라고 하면 g_partial = d_partial(p_partial - 0xdeadbeef)과 h_partial = (d_partial+p_partial) ^ (d_partial-p_partial) 이 두 식이 모두 성립합니다. 이를 이용해 p와 d를 하위비트부터 복원하고, 이렇게 복원해낸 후보군들에 대해 직접 N을 p로 나눠보면서 올바른 p와 q를 찾아내어 메시지를 얻어낼 수 있습니다.

이 성질을 이용해 m = 2059일 때(N이 4096bit이니 p, q는 끽해야 2048~2050bit일 것입니다.)의 d_partial, p_partial 후보를 912개 건질 수 있었고 그 쌍 중에 어느 하나는 올바른 p일테니, 각각에 대해 N의 약수인지 확인했습니다. 풀이를 하는데 쓰인 코드는 아래와 같습니다.

https://github.com/blisstoner/Codegate-2018-quals/blob/master/RSAbaby.py

두 문제 다 못풀었으면 슬플뻔했는데 다행히 RSAbaby 한 문제를 풀어내서 체면치레는 했습니다. 오랜만에 해킹대회를 해보니까 또 나름대로 재밌네요. 코딩, 특히 PS는 짧은 시간내에 문제를 빠르게 풀어내야하니 굉장히 지치는데 해킹은 그런 느낌은 아니다보니 조금 더 여유롭고 좋은 것 같습니다. 물론 둘 중 어느 하나라도 지금보다 훨씬 더 잘 할 수 있게 된다면 바랄게 없겠네요 :)

본선은 저보다 잘하는 팀원들이 많아 제가 갈 수는 없지만, 나가서 다 때려부수고 와주면 좋겠습니당