2023 암호분석경진대회에 참가하였고, 일반부 1등으로 대상(국방부장관상)을 수상하였다.
총평
해당 대회에 처음 참가하는 거라 금년도 문제의 상대적인 난이도는 평가할 수 없지만 딱 적당한 난이도가 아니었나 싶다. 총 6문제 중 1 ~ 4번 문제는 고등부 문제로 난이도가 대체로 평이했으며, 5 ~ 6번 문제는 푸는데 며칠씩 걸릴 정도로 어려웠다. 다만 금년도의 대상 경쟁은 치열했던 것 같다. 작년 대회에서 최우수상을 받은 고등학교 동기가 말하기를 자신들은 문제를 모두 풀지 못했다고 했는데, 올해는 우수상을 받은 팀에도 올솔이 있는 것 같았다. 아마 올솔을 한 팀들 사이에서는 보고서의 퀄리티 차이가 순위를 결정했을 것이다.
1번 문제
1번 문제는 적대적 AI 공격에 관한 문제이다.
첫번째 문제는 CIFAR10 데이터 혹은 ImageNet 데이터에 있는 이미지에 대한 PGD(Projected Gradient Descent) 기반의 Perturbation Attack을 수행하는 것이고, 두번째 문제는 교통표지판(STOP 신호, 속도제한 신호 표지판 등)에 대한 Patch Attack을 수행하는 것이다.
첫번째 문제인 PGD기반의 Perturbation Attack은 제시된 Python 라이브러리를 사용하여 간단하게 수행할 수 있다. 결과는 다음과 같다.
Patch Attack을 수행하기 위해서는 먼저 교통표지판에 대한 Classifier가 필요하다. 따라서 pre-trained ResNet-18을 GTSRB 데이터를 가지고 finetuning하여 교통표지판에 대한 Classifier를 만들었다. 그 다음 앞서 훈련한 Classifier와 GTSRB 데이터를 사용하여 Adversarial Patch를 생성하였다. Adversarial Patch는 다음의 함수를 최대화하도록 학습시켰다. 이는 구현의 편의성을 위해 Adversarial Patch 논문의 objective function에서 rotation 인자를 제거한 것이다.
생성된 Adversarial Patch는 다음과 같다.
이후 Adversarial Patch를 가지고 Patch Attack을 수행하면 두번째 문제를 해결할 수 있다.
2번 문제
2번 문제는 차분 분석에 관한 문제이다.
Z의 의미는 6-round SPECK-32/64 에 대한 입력(평문) 차분이 0x0040/0000 일 확률이다. 이를 이용하면 7-round-speck cipher의 어떠한 final round key에 대해서 옳은 키인지를 평가할 수 있는 점수의 수식을 구성할 수 있다. 그 이유는 다음과 같다.
입력(평문) 차분이 0x0040/0000 라고 생각해보자. 이 평문이 임의의 키로 암호화되었을 때, 어떠한 final round key로 이를 한 라운드 복호화하고, 그 결과값을 nerual distinguisher의 입력값으로 넣어주게 되면, 평문의 차분이 0x0040/0000일 확률 Z가 결과값으로 나올 것이다. 이를 final round key의 개별 점수라고 정의하자. 이 결과값은 약 75%의 정확도를 가지고 있기에, 이를 여러 번 반복하게 되면 충분히 의미있는 값을 계산해낼 수 있다.
이후 마지막 라운드 키에 대해 전수조사를 하며 모든 키에 대한 점수를 구한 다음 점수가 가장 높은 키를 구하는 방식으로 키 복구 공격을 수행할 수 있다.
3번 문제
3번 문제는 RSA에 관한 문제이다. 해당 문제에서는 암호문 C와 공개키 n에 대해서 RSA 복호화 연산을 반복해서 160번 수행하는 도중 개인키의 최하위 k개의 비트를 모두 0으로 셋팅하는 오류주입 공격이 수행된 상황이다. 160번의 복호화 연산과정에서의 오류주입 위치와 연산된 평문값이 주어졌을 때 개인키를 복구하는 것이 목표이다. 오류가 주입된 위치 간의 간격이 5 ~ 8 정도로 작다는 점을 이용해 개인키를 복구해 낼 수 있다. 문제를 보자마자 아이디어를 떠올려서 가장 빠르게 풀었던 문제이다.
4번 문제
4번 문제는 암호 알고리즘 구현 및 최적화에 관한 문제이다. 문제에서 명시된 블록 암호화 알고리즘을 SIMD(Single Instruction Multiple Data) 명령어 셋을 활용하여 고속 병렬 구현하면 된다.
5번 문제
5번 문제는 디지털 포렌식 문제이다. 총 4가지의 사진 파일이 제공되며, 사진들을 분석해서 최종적으로 유출된 도면을 찾아내야 한다. 5번 문제에 대한 나의 기여분은 0에 수렴한다. 이 문제를 풀어준 팀원들에게 감사함을 표한다.
6번 문제
6번 문제는 타원곡선 암호에 관한 문제이다.
6번 문제는 5번 문제와 더불어 수상여부를 결정하는 문제인 만큼 고난도의 문제였다. 해당 문제의 풀이를 수식없이 간략히 설명하기는 어려워, 본 글에서는 하나의 힌트만 제공하고자 한다. 풀이가 궁금한 사람들은 여기에서 별점을 먼저 누르고 보고서 및 코드를 다운받으면 된다.
힌트는 다음과 같다. 아래와 같이 전자서명을 수정하면 취약점을 해결할 수 있다.
후기
대회 감상(感想)을 말해보자면 문제를 풀면서는 재미있었고, 보고서를 작성하는 것은 꽤나 고역이었으며, 대상을 받은 순간은 미칠듯이 기뻤다. 대회 마감이 8월 말일이었고 대회 결과는 9월 26일에 나왔는데, 거의 한달동안 마음을 졸이며 아침마다 대회 사이트에 접속해서 공지를 확인했던 기억이 난다. 팀원들끼리 오늘은 무조건 결과가 나온다고 설레발을 몇번이나 쳤는지 모르겠다ㅋㅋㅋ.
글을 끝마치기 전에 팀원들한테 고맙다는 말을 다시 한번 전하고 싶다. 정말 네명중 어느 한명이라도 없었다면 대상을 수상하는 것은 불가능했을 것이다. 사랑한다 얘들아!
