Whitehat Contest 2022 본선 Crypto writeup

11월 치뤄진 2022년 Whitehat Contest 본선에는 Crypto 카테고리에 Integration Bee라는 제목의 1문제가 출제되었다.

 

문제 제목에 포함된 Integration이라는 단어로 유추하건데, integration attack을 이용하는 문제일 것을 짐작할 수 있으니 알아두고 넘어가자.

문제에 제시된 cipher를 확인하면 경험적으로 내지는 약간의 구글링을 통해 4-round PRINCE cipher임을 알 수 있다. 또한, 64회의 chosen plaintext encryption oracle을 제공하므로, 총 64쌍의 plaintext-ciphertext 쌍을 계산할 수 있다.

이는 4bit nibble을 사용하는 PRINCE cipher에 대해 integration attack을 하기에 충분한 oracle 횟수임을 추측할 수 있다.

 

약간의 구글링을 거치면, integration attack을 이용하여 round-reduce PRINCE cipher에 대한 key recovery attack을 구현하는 논문을 발견할 수 있다. 여기에는 다양한 round 수의 PRINCE cipher에 대한 공격 방법을 제시하는데, 4round PRINCE cipher의 경우 권장 160쌍, 최소 32쌍의 plaintext-ciphertext 쌍을 사용해야하는 공격 방법이 상세히 설명되어있다. 이를 그대로 구현하면 되는데, 이때 인터넷에 공개되어있는 구현체를 참고하면 빠르고 정확하게 구현할 수 있다.

 

본 문제의 풀이에서는 $k_1\oplus k_0^\prime$ 복구에 2개의 active nibble set(총 32쌍), $k_1$ 복구에 2개의 active nibble set(총 32쌍)을 사용하였다. 논문에 제시된 권장량보다 한참 적은 양이지만, 256번의 local test에서 약 60%의 확률로 $k_1\oplus k_0^\prime$ 복구에 성공함을 확인하여 충분히 시도 가능한 수치라 생각하여 풀이를 강행하였다.

 

또한 $k_1$을 복구한 후 $k_0$를 복구하기 위해 $k_0$의 최상위 비트값을 알아야 하는데, 0으로 가정하여 성공 확률이 절반으로 감소한 솔루션을 작성하였다.

 

작성된 솔루션은 여기에서 확인 가능하며, 약 10회 정도의 솔루션 실행 후에 아래와 같이 flag를 획득하였다.