2024 암호분석경진대회 후기

연구실 선배와 취미삼아 참가한 2024 암호분석경진대회 에서 대상(1등) 을 수상했다.

시상식까지 끝났으니 풀이를 공개한다.

문제 및 답안 전체 Github

1번

문제 풀이

LFSR 관련 기초지식 및 딥러닝을 이용해서 LFSR 시계열 출력의 주기를 예측하는 문제.

재미가 없어보여서 마감일 하루 전에 시작해서 급하게 끝냈다… 문제에서 어떤 것을 원하는지 모르겠어서 적당히 FFT 랑 LSTM 으로 구색만 갖춰서 냄.

Berlekamp-Massey 알고리즘 등 생각해본 것은 많았는데 결국 한건 별로 없다.

2번

문제 풀이

Side channel attack 의 일종인 power analysis 를 수행하는 문제.

AES 암호화의 S-Box 부분을 Differencial Power Analysis 테크닉으로 공격하는 문제이다. 공격 타겟이 AES 첫 round의 S-Box 라는 것은 주어진 전체 파형 1개 샘플을 보고 찾아도 되고, 모든곳을 다 공격해보고 correlation 이 높게 나오는 부분을 찾아내도 된다. 출제에서 의도한 부분은 전자일 것 같은데, 실제로 문제를 풀 때는 후자의 방식으로 했다.

공격 코드를 짤 때는 이 자료 가 제일 유용했다.

내가 뭘 잘못했는지는 모르겠지만, DPA 공격으로는 16개 키 블록 중 12개만 제대로 찾아지고, 나머지 4개 블록 (32비트) 는 제대로 된 결과가 나오지 않았다. \(2^{32}\) 개 AES 키를 시도해 보는 것은 현대 컴퓨터로 충분히 가능하므로, 간단한 brute-force 공격 코드를 OpenMP 로 병렬화해 작성해서 문제 풀이를 마무리했다.

이번 대회에서 내가 가장 재미있게 본 문제.

3번

문제 풀이

연구실 선배 희훈이형이 해결한 문제. IDA 를 쓰면 쉽게 풀수 있다고 하지만… 유료라서 사용을 못 했고, 무료인 기드라를 사용했다. 기드라 설치 및 적응하는데 삽질한 것만 빼면 무난히 해결한 것 같다.

4번

문제 풀이

타원곡선을 이용한 암호인 ECDSA 구현체의 취약점을 분석하는 문제.

암호화에 salt 역할로 사용하는 \(k\) 값이 무작위가 아니라 해시와 개인키의 조합으로 이루어졌다는 것을 발견하는 것이 문제의 앞쪽 절반. 이를 이용해 32바이트 비밀키 중 16바이트를 알아낼 수 있다. 나머지 16바이트를 알아내기 위해서는 타원곡선 암호화 식을 정리한 뒤 확장 유클리드 알고리즘을 조금 변형해 적용하면 된다. 이렇게 알고리즘을 잘 적용하는 것이 문제의 뒤쪽 절반

5번

문제 풀이

연구실 선배 희훈이형이 해결한 문제. 딥러닝 논문 열심히 읽고 적당히 구현한 것 같다.

6번

문제 풀이

연구실 선배 희훈이형이 해결한 문제. 암호보다는 CPU 인트럭션 개수 줄이는 최적화 문제이다.

운좋게 연구실 전문분야가 가장 어려운 6번 문제로 나와서 전체 1등을 할 수 있었던 것 같다.

• contest