CODEGATE2023 final 리뷰

8/24~25일동안 대학부에서 PLUS 팀으로 코드게이트 대회를 치러 갔습니다. 본선 대회 중 의미 있는 성적이 나온 첫 대회인만큼, 리뷰를 남겨 그때의 심정을 오래 기억할 수 있게 하고자 합니다.

 

https://twitter.com/POSTECH_PLUS/status/1694908449992421620?s=20

 

8/24 오전 10시

대회가 시작하자마자 크립토 문제를 보러 갔습니다. 일반적으로...는 첫번째 자리에 위치한 문제가 가장 쉬운 경우가 많기에, the leakers를 잡고 문제 로직을 분석하기 시작했습니다. Step 1은 의도를 거의 바로 눈치채고 통과하는 솔버를 빠르게 만들었지만, Step 2에서 seed를 따로 안 건들고 힘으로 unknown bit를 알 수 있을 거란 근거 없는 믿음에 사로잡혀 삽질을 시작했습니다.

8/24 오후 5시

약 5시간의 삽질 끝에 위의 방식으로 step 2를 클리어하는 것은 불가능하다는 결론을 내렸습니다. analytic한 잡기술들을 섞어 시간을 압축해서 그뢰브너로 민다- 라는 사풀을 세워 쭉 밀었으나, 2125개의 unknown variable을 다 처리하는 것은 어떻게 해도 결국 불가능하다는 것을 깨닫고는 깔끔하게 포기 선언했습니다. 그럼 결국 8215개 중 앞이나 뒤쪽에 싹 몰려있는 숫자를 뽑는 seed를 찾는 문제를 해결해야 했는데, 일단 624개로는 불가능한 것이 분명하고, 그렇다고 뾰족하게 이를 잘 늘릴 수 있는 방법도 바로 떠오르지 않아 잠시 문제를 접어두기로 결정했습니다.

8/24 오후 6시

드디어 leakers에서 손을 떼고 다른 문제를 둘러보기 시작했으나, 7시간 동안 삽질해도 0솔이 박힌 것에 좀 멘탈이 나간 상태라 문제가 잘 눈에 들어오지 않았습니다. 그러던 중 옆에 성재 선배가 misc 분야의 cha's magic이 단순히 어떤 해시 함수 부수는 문제인데 해보실? 이라고 해서, 뇌를 비우고 바로 들어갔습니다. 문제의 내용은, 대충 아래의 해시 함수

def mysql_hash_password(password):
    nr = 1345345333
    add = 7
    nr2 = 0x12345671

    for c in password:
        if c == 32 or c == 9:
            continue
        nr ^= (((nr & 63) + add) * c)+ (nr << 8) & 0xFFFFFFFF
        nr2 = (nr2 + ((nr2 << 8) ^ nr)) & 0xFFFFFFFF
        add = (add + c) & 0xFFFFFFFF

    return "%08x%08x" % (nr & 0x7FFFFFFF,nr2 & 0x7FFFFFFF)

가 있고, 해시값이 b'chacha20', prefix와 suffix가 특정 문자열인 패스워드 2를 찾는 것이 목적입니다. 상당히 문제의 내용이 직관적이고, 머릿속으로 견적을 내보니 막 불가능한 수준까진 아닌 것 같아서 바로 이 문제에 빨대를 꼽았습니다. 일반적인 mitm으로는 조금 힘들수도 있겠다 싶어 우선 해시 함수의 현재 state, 즉 (nr, add, nr2) 쌍으로부터 이전의 state를 뽑는 역함수를 제작하고, 냅다 mitm을 박았습니다. 구체적으로, 가운데에서 만날 middle state의 add 값을 적당히 고정한 채 앞쪽, 뒤쪽에서 해당 add를 target으로 가는 바이트 array를 마구잡이로 모은 후, 그중에서 (nr, nr2) 값 충돌이 일어나는 것을 잡으면 될거야! 라는 전략으로 접근했습니다.

8/24 오후 9시

충분히 middle에서 충돌이 일어날 만큼 데이터를 뽑았는데도(앞뒤에서 각각 해시 150억개 확보), 충돌이 일어나지 않아 슬슬 멘탈이 나가기 시작합니다. 단순히 운 문제는 아닌 것 같았기에 생성된 hash들의 modulo 256 값을 뜯어보니, 어째서인지 앞과 뒤에서 물리적으로 충돌이 날 수 없게 해시들이 생성되고 있었습니다. 구체적인 이유는 정확히 모르지만 (parameter 선택이 나빴을지도), 이것을 확인한 후 또 또 시간만 날린 꼴이 되버려 멘탈이 다시 나가버렸습니다.

8/24 오후 10시

멘탈도 추스릴 겸 밥도 좀 먹고, 편의점에서 이것저것 사러 나갔습니다. 그런데 가는 도중에 머릿속으로 시뮬레이션을 좀 해보니, c 값으로 b'\x00'을 도배했을 때 nr 값이 4를 주기로 유지가 된다는 것을 깨달았습니다. 이는 매우 중요한 성질인데, 왜냐하면 m1 =  A \x00 B \x00 C \x00 D\x00 ... 이런 식으로 생성된 패스워드와 m2 = m1 =  A \x00*5 B \x00*5 C \x00*5 D \x00*5 ... 로 생성된 패스워드가 있으면, hash(m1)의 nr값과 hash(m2)의 nr값이 일치하게 됩니다. 즉, 4바이트 브포로 타겟 nr값이 되는 m1 =  A \x00 B \x00 C \x00 D\x00 ... 을 먼저 찾은 후, 각 \x00를 \x00*5로 바꿔도 nr은 유지되고, nr2만 달라지게 됩니다. 이러면 용량 이슈, mitm에 붙는 logN 상수 이런것들 걱정 없이 훨씬 더 작은 계산 수준에서 브루트포싱이 가능해지고, 바로 이를 구현해서 시도해보았습니다.

8/24 오후 11시

구현을 마치고 바로 해시크랙을 실행해보았으나, nr은 잘찾아지는 반면 어째서인지 nr2는 잘 찾아지지 않았습니다. 이번에도 parameter 이슈로, nr2의 mod 4값이 항상 일정하게 유지되었기 때문입니다. 앞에서 비슷한 억까를 이미 당한게 있어 이번엔 원인을 빨리 찾아 고칠수 있었고, 적절한 parameter를 찾아 이를 해결한 후 launch했습니다.

8/24 오후 11시 30분

찾았습니다.

99 111 100 101 103 97 116 101 50 48 50 51 123 33 0 0 0 0 0 0 0 0 0 33 0 0 0 0 0 0 0 0 0 33 0 33 0 0 0 0 0 0 0 0 0 0 0 0 0 33 0 0 0 0 0 33 0 0 0 0 0 0 0 0 0 0 0 0 0 33 0 0 0 0 0 0 0 0 0 33 0 0 0 0 0 0 0 0 0 0 0 0 0 33 0 0 0 0 0 0 0 0 0 33 0 0 0 0 0 0 0 0 0 33 0 0 0 0 0 0 0 0 0 0 0 0 0 33 0 0 0 0 0 0 0 0 0 33 0 0 0 0 0 0 0 0 0 0 0 0 0 33 0 0 0 0 0 0 0 0 0 33 0 62 0 73 0 248 0 230 0 105 95 108 111 118 101 95 121 111 117 125
99 111 100 101 103 97 116 101 50 48 50 51 123 33 0 0 0 0 0 0 0 0 0 0 0 0 0 33 0 0 0 0 0 0 0 0 0 33 0 0 0 0 0 0 0 0 0 0 0 0 0 33 0 33 0 0 0 0 0 0 0 0 0 0 0 0 0 33 0 0 0 0 0 33 0 0 0 0 0 33 0 0 0 0 0 0 0 0 0 0 0 0 0 33 0 0 0 0 0 0 0 0 0 0 0 0 0 33 0 0 0 0 0 0 0 0 0 33 0 0 0 0 0 0 0 0 0 0 0 0 0 33 0 0 0 0 0 0 0 0 0 0 0 0 0 33 0 0 0 0 0 0 0 0 0 0 0 0 0 33 0 0 0 0 0 0 0 0 0 33 0 0 0 0 0 0 0 0 0 62 0 73 0 248 0 230 0 105 95 108 111 118 101 95 121 111 117 125

1코어로 약 10분만에 찾았습니다. 좀 운이 좋았던 것일수도 있지만, 다른 팀의 솔버와 비교해봤을때 그냥 효율적인 로직을 잘 찾아낸 것 같습니다.

codegate2023{Mysql_olD_P455woRD_I5_CoMPl373Ly_broK3N_702IFA6CA*-2=E-->6C0=5FF.}

 

일반부에서는 두 팀 정도 먼저 해결을 했고, 대학부에서는 퍼솔했습니다. 약 14시간만에 0솔단에서 벗어난 지라 상당히 격양된 감정으로 플래그를 제출했습니다. 내고 나니 2등이었어서 싱글벙글했지만, GoN 팀은 플래그 키핑일 확률 99%였고 1등과의 점수차는 상당히 벌어진 상태였기에 딱 3등만 하자는 목표로 대회에 임했습니다.

 

8/24시 오후 12시 30분~

다시 본업으로 돌아와 leaker를 잡았습니다. 보면서 seed를 복구하는 문제들(https://blog.encrypted.gg/1068 글을 많이 참조했습니다)의 라이트업을 보며 가능한 것과 불가능한 것들을 구분했고, 다시 견적을 내본 결과 이거 뒤쪽으로 숫자들 충분히 다 몰 수 있겠다고 확신했습니다. 하지만 어째서인지 시중의 seed 복구 함수들이 다 잘 작동이 되지 않았고, 결국 계속 끙끙대다 대회가 종료되었습니다. 끝나고 유일하게 해당 문제를 푼 soon_haari에게 솔루션을 물어봤는데, 앞에 0x8000? 이 붙어야 한다던가, 암튼 제약들이 더 까다롭게 붙어있었다고 합니다. 라이트업을 봐도 seed breaking이 슥 흝는 수준으로 이해될 것 같지 않아서, 따로 날을 잡고 제대로 공부를 해봐야 할 것 같습니다.

 

대회 외적인 말 말 말

• 저희와 무려 100점 차이로 4등을 하신 돌솥낙지비빔밥 팀이 있었는데, 무려 1인팀으로 저런 퍼포먼스를 내셔서 충격과 공포 그 자체였습니다. 카이스트 분이셔서, 저런 분이랑 포카전 맞상대를 해야한다는 점이 매우 슬픕니다. 살살 좀 해주십쇼..
• 대회장이 ㅈㄴ 추웠습니다. 미리 얘기를 들어서 외투를 하나 가져갔는데도 그걸 뜷고 한기가 들어옵니다. 다음번엔 어떻게 잘 개선이 됬으면 좋겠습니다.
• 대회 참여자분들에게 discord로 노래 신청을 받는데, 정말 다양한... 노래들이 흘러나왔습니다. 심지어 저희 팀 자리는 스피커 바로 앞자리라 어그로가 심하게 끌렸는데, 에어팟 끼고 소리 최대로 키워서 어떻게 잘 방어해냈습니다. 다음번에는 제가 좋아하는 노래들 도배해서 리벤지를 하든가 해야겠습니다.

후기

사실상 첫 코드게이트였음에도(작년에는 아예 생뉴비라 본선 못감) 나쁘지 않은 성적으로 잘 마무리해서 좋습니다. 1문제밖에 못 풀긴 했지만, 배점이 상당히 높았기에 1인분 정도는 잘 한 것 같습니다. 하지만 crypto 0솔은... 喝 喝 喝 ! ! ! 아직 부족함이 많다는 것을 느끼기에 충분했고, 좋은 동기부여가 될 것 같습니다. 그리고 경험 부족인진 몰라도, 현장에서 퍼포먼스가 좀 저하되는 느낌이 있는데, 루틴을 잘 만들든지 해서 어떻게 잘 개선할 방법을 찾아야 할 것 같습니다. 마지막으로 같이 뛰신 팀원분들과, 특히 캐리한 쿼티씨한테 감사를 전하며 글을 마치겠습니다. 

네임펜인듯