Dreamhack invitational brief writeup & 후기

RSA lsle

512bit인 $p, q$의 128lsb를 마음대로 입력할 수 있고 ciphertext를 골라서 decrypt된 결과의 하위 129번째 bit를 출력해주는 상황이다.

$(2^i)^e \ enc \ (mod \ n)$을 입력하면 $2^i \ target \ (mod \ n)$ 에 대한 정보를 얻을 수 있다.
즉, $2^i \ target - kn$ 의 한 비트를 얻는 것이고 $mod \ 2^{128}$ 상에서의 값만 신경쓰면 되기 때문에 $n \ (mod \ 2^{128})$이 최대한 작아야 하고, 따라서 $p, q$의 lsb를 1로 설정해 주었다.

1024bit인 $target$을 128bit인 $r_i$ 8개로 표현할 수 있다.

위와 같이 128개의 암호문을 차례로 보내면 129~2번째 비트를 알 수 있다. 여기서 1번째 비트는 0 또는 1 (1/2의 확률)로 무작위로 정해야 한다.

여기까지 하고 꽤 오랜 시간을 고민하다 아이디어가 생각났다.

이라 하면 우리는 $r$의 하위 128bit를 알아내야 한다.

이렇게 설정하면 oracle을 이용하여 $target'$의 하위 128bit를 leak할 수 있고 $r_1$은 이미 아는 값이므로 $r$의 하위 128bit, 즉, $r_2$를 leak할 수 있다.

같은 방식으로 나머지 $r_i$ 들도 구해주면 온전한 $target$을 구할 수 있다.

XOR Disaster

v = v ^ (v >> k)
v = (v ^ (v << k)) & ((1 << 256) - 1)
v = v ^ random_value

위의 코드가 랜덤한 순서로 나열된 32개의 함수가 있고 이들은 8bit를 return한다.
이 함수들에 들어가는 인자가 256bit크기의 flag인 상황이다.

중간중간에 v &= 2^256-1 가 있는 것을 보고 $GF(2^{256})$상에서의 연산임을 알 수 있었고 xor과 shift연간이 모두 linear함을 알 수 있었다.

따라서 flag를 256개의 변수로 취급하면 32개의 함수에서 8bit를 반환하므로 $32*8 = 256$ 개의 식을 얻을 수 있다. solve_right하면 끝

후기

대면으로 ctf본선에 처음 참여해 보았다. 네임드 해커들을 실물로 보는 것이 신기했고 대회장 시설이 생각보다 너무 좋았던 것도 신기했다.

전날 과제 이슈로 아침엔 정신을 못 차렸다. 대회장 음악이 생각보다 커서 점심 이후로 에어팟 끼고 제대로 집중하기 시작했고 대회 시작 6시간만에 RSA lsle를, 4시간 뒤에 XOR Disaster을 풀었다. web3문제는 좀 보려다가 지금 체급으론 어림없을 것 같은 강한 느낌이 들어서 빠르게 손절했다.

참가자 리스트를 보고 꼴등만 하지 말자는 마인드로 임했는데 운이 좋게도 8등으로 대회를 마무리했다. 솔직히 상금(50만원)도 타고 10등 안에 들어서 기분이 굉장히 좋았다 😚😚

내 위에 CyKor 형님들 세 분이 각각 포너블, 웹, 크립토 분야 문제를 다 푸신 것을 보고 대단하다고 다시금 느꼈다. (특히 포너블은 대회 종료 10분?즈음 전에 퍼블 내셨는데 미친 끈기인 것 같다..)

크립토가 비교적 솔버가 적어서 2문제를 풀고도 10등 안에 들 수 있었던 것 같다.

아쉬운점

• 순위권(상금권?)에 들고 의욕이 식어서 다른 문제 열심히 건드리지 않은 것
• 리버싱 문제(The tail cannot wag the dog) 진작에 제대로 볼걸..
• web3를 제대로 공부하자