pbctf 2023 후기

2월 18일, perfect blue가 주최하는 pbctf를 PLUS 소속으로 치뤘다. 역시 그 이름값만큼 문제들의 난이도가 쉽지 않으면서도, 우아하고 좋은 문제들이 많았다고 생각한다. 조금 아쉬웠던 점은 CTF의 플랫폼으로, 흰 배경에 흰 글자를 작성하는 카멜레온식 플랫폼 때문에 Notification이나 Rule 등을 읽는게 불편했다.(근데 이거 다른 사람들은 또 잘 보이신다고 한다. 로컬 환경에 뭔가 충돌이 있었던 것 같다.) 그래도 가장 중요한 Challenge와 Scoreboard는 정상적으로 보여서 다행.

 

흰 것은 종이요 흰 것은 글씨라

 

난 원래 대깨로 crypto밖에 할줄 모르기에 그쪽 문제들만 집중적으로 파봤고, 최종적으로 Blocky(143 solves), My ECC Service(32 solves), My ECC Service 2(11 solves)를 해결하였다. 개인적으로 Blocky - 4가 solve수만 보면 My ECC Service 2보다 더 쉬웠던 것 같은데, 하필 Block 공부가 전혀 되있지 않은 상태라 갈피를 잡지를 못했던 게 아쉬웠다. 이번 학기에는 꼭 Block 암호 숙련도를 높여야겠다.

 

다음은 각 문제들에 대한 Writeup이다. 못 푼 것들은 추후에 다시 풀어보고 기입하도록 하겠다.

 

[ Blocky ] - 143 solves

1. 분석

Cipher, GF, task 파일이 주어지며, 각 파일들에는 다음 기능들이 구현되어있다.

• GF - element가 GF(0) ~ GF(242)로 정의된, mod $x^5 + 2x + 1 $에서 돌아가는 Field이다.
• Cipher - BlockCipher라는 Class가 있다. 이 Class는 총 9개의 블럭을 받아서, GF의 element들로 구성된 SBOX와 연산들로 이 블럭들을 마구마구 섞어 encrypt, decrypt한다. Blocky에서는 크게 중요하게 사용되는 부분은 없고, Blocky 4, 5에서는 조금 더 깊게 분석을 해야 할 것이다. 아직은 이걸 분석할 능력이 없고, 적어도 Blocky에선 사용될 일이 없으니 일단 넘어가자.
• task - main을 분석하면, E키와 D키로부터 임의의 블럭을 encrypt, decrypt한 결과를 알 수 있다. 이때 decrypt해서 'gimmeflag'라는 글자를 띄우면 FLAG를 출력해주고, 당연하게도 gimmeflag를 encrypt하려고 시도할 경우 사전에 막힌다.

2. 풀이

task를 잘 관찰해보면, D키 입력 후 작동되는 코드에

pt = unpad(dec)
if pt == b'gimmeflag':
    with open('flag', 'r') as f:
        flag = f.read()
        print(flag)

라는 말이 있다. 즉, decrypt된 구문에 [ gimmeflag + 적당히 padding된 무언가 ]가 들어가도 gimmeflag가 나온다! 이를 활용해 Encrypt input으로 'gimmeflag' + '\x09' * 9 + get_mac('gimmeflag' + '\x09' * 9)을 넣어주었고, 나온 encrypt된 output들 중 앞 27비트를 Decrypt input으로 넣어주면서 FLAG를 따냈다.

pbctf{actually_I_made_the_same_mistake_in_CODEGATE_Finals}

 

[ My ECC Service, My ECC Service 2 ] - 32 solves, 11 solves

rbtree님의 문제이다. My ECC Service, My ECC Service 2 모두 singular elliptic curve에서 발생하는 취약점을 공략하는 문제로, https://rbtree.blog/posts/2020-04-18-singular-elliptic-curve/ 에서 공략법을 알 수 있었다. 개인적으로 두 문제는 풀이는 크게 차이가 나지 않지만, My ECC Service 2로 넘어갈 때 discrete_log의 구현이 강제되면서 난이도가 다소 올랐다고 생각한다.

1. 분석

challenge 파일에서 유저가 할 수 있는 것을 관찰하면, 다음 3가지 행동이 가능하다.

• input G - service.gen() 값을 받아온다.
• input V - service.verify(payload) 를 받아온다. 이때 service의 BASE_POINT를 바꿀 수 있다.
• input P - 다음 service.gen()이 뭔지 예측에 성공하면, FLAG를 출력한다!

2. 풀이

여기서 딱 봐도 수상해보이는 녀석이 뭐냐고 물어보면, 지나가는 생명과 학생을 아무나 붙잡고 물어봐도 V라고 대답할 것이다. 하지만 결국 BASE_POINT를 임의로 정해도 그게 곡선 위에 없으면 망하는거 아닌가? 라는 생각에 도달했을 때쯤, 문제에서 ECC의 계수 b가 정해지지 않았다는 것을 깨달았다! 즉, BASE_POINT를 새로 지정하면서, 우리는 타원곡선의 b 값도 마음대로 정해버릴 수 있다. 심지어 a는 -3로 값이 고정되어있고, 이를 통해 b를 2 or -2로 지정하면 $ 4a^3 + 27b^2 = 0 $ 이 되면서, 매우 취약한 singular curve가 되어버린다! singular elliptic curve에서 ECDLP를 푸는 건 비교적 쉬운 문제이며, 이를 풀면 service.gen()에 사용되는 NonceGenerator의 state 값을 직접 알아낼 수 있기 때문에 그 다음 service.gen()을 알아낼 수 있고, FLAG를 알아낼 수 있다.

 

singular elliptic curve에서 ECDLP를 푸는 문제는 위의 rbtree님의 블로그에 그 방법이 잘 나와있다. $x^2 \equiv a \pmod{p}$ 인 $x$가 존재할 경우 sagemath에 있는 discrete_log 함수를 사용하면 되지만, 그렇지 않을 경우 $ x + y \sqrt{a} $를 대상으로 하는 discrete log 함수를 직접 짜야 한다. 아쉽게도 이 문제에서는 저런 $x$가 존재하지 않는 경우에 속하고, discrete log 함수를 직접 구현할 필요가 있었다. 만약 $ x + y \sqrt{a} $의 order가 smooth하지 않을 경우 discrete log함수에 사용되는 Pohlig–Hellman algorithm이 잘 작동되지 않을 수 있는데, 다행히 각 MOD 값들에서 order가 모두 MOD+1이고, 이것이 모두 smooth한 값들로 설계가 되어있어서 비교적 쉽게 discrete log 함수를 구현할 수 있었다. (저게 order가 mod+1이 되는 이유는 정확히는 모르겠다. 나중에 따로 증명을 해보든가 해야할 것 같다.)

구현된 녀석: https://gist.github.com/porocycle/7e57a89795ef06f7e39ec9589997ee63

pbctf 2023 - My ECC Service 2

 

[ Blocky 4 ]

[ Blocky 5 ]

[ remake ]

아직 풀지 못한 것들. 숙제 스택에 남겨두자.

 

비교적 푼 문제수가 적었음에도 불구하고, 최종적으로 우리 팀은 세계 10등이라는 꽤 좋은 성적으로 대회를 마무리했다. qwerty씨가 유일하게 flipjump 시리즈를 모두 풀면서 무쌍을 찍어버렸고, crypto 쪽에서도 나름대로 쏠쏠하게 지원사격을 해주어서 꽤 좋은 퍼포먼스가 나온 것 같다. 이번에 신입생들 + 재야의 고수 선배들이 많이 복귀하면서 다시 화력이 좋아질 기미가 보이는데, 더 좋은 퍼포먼스가 나올 수 있길 기대한다.