SCTF 2018 본선 후기

작년에 비교적 경쟁이 덜했던 암호학 부문에서 500만원을 후루룩 쩝쩝하고 올해도 내심 그런 행운이 있을 수 있지 않을까 살짝 기대를 했습니다. 대회 플랫폼이나 진행 및 시상 방식은 작년과 그대로였지만 단 하나 달라진게 있다면, 분야별 특별상을 받기 위해서는 해당 분야의 문제를 최소 3개 이상 풀어야 한다는 조건이 추가되었습니다. 합리적인 조건이라고 생각합니다.

1년간 알고리즘에 매진하느라 해킹쪽 공부는 학과공부를 따라갈 정도로만 하는 거랑 CTF 한 두개 나가본 것 빼고는 아예 건드리지 않았어서 별로 기대는 안했지만 그래도 암호학이랑 코딩 분야에서 어찌저찌 잘 비비면 장려상은 받을수도 있지 않을까 싶었습니다.

아침 10시부터 다음날 아침 10시까지 24시간 대회였고, 전날에 카카오 대회를 갔다오느라 굉장히 지쳐있는 상태로 R&D캠퍼스에 도착했습니다. 5개 분야중에 가장 노려볼만한게 암호학이었기 때문에 작년과 비슷하게 바로 암호학에 뛰어들었고, 암호학은 시작할 때 3문제에 오후 4시에 1문제가 추가로 공개되었습니다.

이상하게 꽤 오랫동안 암호학을 안했는데도 초반에는 문제가 굉장히 잘 풀렸습니다. nomeaning님이 압도적으로 1위를 차지하긴 했지만, 저도 오후 5시 반쯤에 3문제를 풀어내면서 암호학 2위, 전체 4-5위 정도에 도달했습니다. nomeaning님이 작년처럼 3등 이내에 든다는 가정 하에 남은 한 문제만 풀어내면 특별상을 받는게 확정되기 때문에 남은 문제를 풀려고 정말 고생을 했지만 결론적으로는 그 문제를 포함해서 오후 5시 반 이후 끝날 때 까지 아무런 문제를 추가로 풀지 못하며 순위가 수직하강했습니다. 오전 6시에 스코어가 프리징될 때 순위가 정확히 23등이었어서 마음은 비우고 있었습니다. 끝나고난 뒤 확인해보니 전체 26등, 암호학 부문 5등으로 마무리했네요. 

각 암호학 문제의 풀이를 간단하게 정리해보면 아래와 같습니다.

LCG (15 solve) - 식을 마구 정리하다보면 8번의 질의 내로 Modulus를 구할 수 있고, 이를 이용해 x와 y를 복원할 수 있습니다.

SaltyDSA (4 solve) - DSA에서 k값이 reuse될 경우 secret key x를 복원할 수 있는 취약점을 이용하는 문제로, md5에서 chosen-prefix에 대한 충돌쌍을 쉽게 찾을 수 있음을 이용해야 합니다. md5의 취약점을 이용해 DSA에서 k값을 reuse시키거나 leak하는 문제일 것이라고 예상은 했지만 적절한 md5 취약점을 찾지 못해서 해결하지 못한게 안타깝네요.

MQ (8 solve) - 입력을 All zero와 All zero에서 한 바이트만 0x01로 바꾼 총 52개를 넣어보면 Ax = B꼴의 연립방정식을 얻을 수 있습니다. 그러고나면 x를 쉽게 찾아낼 수 있습니다.

polyPKC (7 solve) - x^51 - 1 = (x-1)(x^2+x+1)(...)으로 변형이 되고 이는 곧 x-1이 P or Q의 배수일 가능성이 높음을 의미합니다. 일반성을 잃지않고 x를 P로 나눈 나머지가 1이라고 하면, 주어진 다항식의 계수의 합이 P의 배수임을 관찰 가능합니다.(사실 지금 머리가 꼬여서 이게 정확히 맞는건지 헷갈리는데 나중에 다시 확인 한 번 해봐야겠네요.) 아무튼 그래서 다항식의 계수의 합과 N의 gcd를 취해 N의 두 소인수를 찾아낼 수 있고, 이후엔 t의 후보 51개에 대해 확인을 해주면 됩니다.

올해도 카이스트에서 출제를 담당했고 작년과 마찬가지로 문제의 퀄리티 또한 매우 좋았습니다. 또 작년엔 문제의 디스크립션 혹은 조건 상의 간헐적인 오류가 조금 있었는데 올해는 그런 것이 많이 줄어들어서 좋았습니다. 진행 또한 매우 깔끔했고 인형뽑기 기계나 pc방에 있을법한 간식 보관함?같은 요소들도 보는 재미를 더해주었습니다. 인형 3개 뽑았어요ㅎㅎ 진행, 문제 수준, 대회 규모 등등 모두 만족스러운 대회였습니다. ICPC 이후로는 알고리즘 공부는 그만하고 다시 해킹쪽 공부를 해야겠습니다 ^_^

이틀동안 머리를 쥐어짜다보니 몸도 힘들고 정신적으로도 너무 피곤하네요. 개강이 얼마남지 않았지만 그때까지라도 쉬어야겠습니다ㅠㅠ

Write up : https://blog.encrypted.gg/636