Haeyul Blog

Dreamhack Crypto Diamond Roadmap

12 min read

0. 목표

Dreamhack에 있는 암호학 문제 중 다이아 이상 난이도를 풀 수 있는 실력을 만드는 것이 목표입니다.

단순히 문제 풀이 코드를 외우는 것이 아니라, 아래 순서로 학습합니다.

개념 이해 -> 취약한 구조 발견 -> 수식화 -> exploit 작성 -> write-up 정리

이 문서는 Dreamhack 암호학 문제를 풀기 위한 개인 학습 로드맵입니다.

1. Dreamhack Crypto 문제를 푸는 기본 순서

암호 문제를 보면 바로 코드를 짜지 말고 다음 순서로 봅니다.

  1. 암호화 식을 찾는다.
  2. 공격자가 아는 값을 정리한다.
  3. 모르는 값을 변수로 둔다.
  4. 식이 선형인지, 반복되는지, 작은 값이 있는지 확인한다.
  5. brute force 전에 수학적으로 줄일 수 있는지 본다.
  6. Python 또는 SageMath로 검증한다.
  7. exploit을 최소 코드로 만든다.
  8. 풀이 후 “왜 깨졌는지”를 한 문장으로 정리한다.

예시:

Affe!n 문제는 key가 random이지만,
평문 일부 cryptography를 알고 있고 암호화 식이 선형이라 key를 계산할 수 있었다.

2. 단계별 학습 순서

1단계: byte, modular arithmetic, Python exploit

목표는 암호 문제에서 가장 자주 나오는 숫자 계산에 익숙해지는 것입니다.

먼저 알아야 할 개념:

  • byte와 ASCII
  • hex, bytes 변환
  • modulo 연산
  • modular inverse
  • pow(a, -1, n)
  • int.from_bytes, to_bytes

대표 문제:

이 단계에서 얻어야 하는 감각:

c = a * p + b mod n

이런 식이 보이면 “선형식이니까 몇 개의 평문-암호문 쌍으로 key를 구할 수 있지 않을까?”를 먼저 떠올립니다.

2단계: 고전 암호와 known plaintext attack

목표는 단순한 암호가 왜 깨지는지 이해하는 것입니다.

먼저 알아야 할 개념:

  • Caesar cipher
  • Affine cipher
  • substitution cipher
  • frequency analysis
  • known plaintext attack
  • chosen plaintext attack

대표 문제:

  • Affe!n
  • No Sub Please
  • No Shift Please

풀이 관점:

암호화 구조가 너무 단순한가?
같은 key가 반복되는가?
평문 일부를 알고 있는가?
문자 빈도나 패턴이 남아 있는가?

3단계: 대칭키 암호와 블록 암호

목표는 AES/DES 자체를 구현하는 것이 아니라, 잘못 사용했을 때 어떤 문제가 생기는지 이해하는 것입니다.

먼저 알아야 할 개념:

  • block cipher
  • ECB, CBC, CTR
  • padding
  • IV
  • meet-in-the-middle attack
  • padding oracle

대표 문제:

  • Double DES
  • Textbook-CBC
  • Padding Miracle Attack

풀이 관점:

암호 알고리즘이 약한가?
아니면 사용 방식이 약한가?
IV가 고정되어 있는가?
padding error를 구분할 수 있는가?
중간 값을 기준으로 양쪽에서 만날 수 있는가?

4단계: RSA 기본기

Dreamhack 고난도 crypto를 풀려면 RSA는 반드시 편해야 합니다.

먼저 알아야 할 개념:

  • 소수
  • gcd
  • 확장 유클리드 알고리즘
  • 오일러 피 함수
  • RSA key generation
  • n = p * q
  • e, d
  • modular inverse

대표 문제:

  • Textbook-RSA
  • uncommon e
  • RSA Quartet

풀이 관점:

n이 너무 작은가?
p, q를 구할 수 있는가?
e가 이상한가?
같은 메시지가 여러 modulus로 암호화되었는가?
padding이 없는 textbook RSA인가?

RSA 문제에서는 먼저 아래 값을 정리합니다.

n, e, c
p, q를 알고 있는가?
phi(n)을 구할 수 있는가?
d = e^-1 mod phi(n)을 구할 수 있는가?

5단계: Diffie-Hellman과 discrete log

목표는 “거듭제곱 mod p” 형태를 보고 discrete log 문제인지 판단하는 것입니다.

먼저 알아야 할 개념:

  • primitive root
  • Diffie-Hellman
  • discrete logarithm
  • Baby-step Giant-step
  • Pohlig-Hellman
  • smooth order

대표 문제:

  • Textbook-DH
  • Hundre-d-log

풀이 관점:

p - 1이 작은 소인수로 잘 쪼개지는가?
generator의 order가 작은가?
비밀 exponent가 작거나 범위가 제한되어 있는가?

이 단계부터는 SageMath 사용이 거의 필수입니다.

6단계: Hash, MAC, Signature

목표는 hash와 signature가 “그냥 암호화”가 아니라는 것을 구분하는 것입니다.

먼저 알아야 할 개념:

  • hash collision
  • birthday attack
  • HMAC
  • DSA
  • nonce reuse
  • signature forgery

대표 문제:

  • 40 Birthdays
  • Textbook-HMAC
  • Textbook-DSA
  • Textbook-DSA2

풀이 관점:

nonce가 재사용되는가?
k가 작거나 예측 가능한가?
검증 로직이 수학적으로 잘못되어 있는가?
collision을 만들 수 있는가?

DSA/ECDSA는 nonce가 새면 private key가 새는 구조입니다.

7단계: Elliptic Curve Cryptography

다이아 이상 crypto에서는 ECC가 자주 벽이 됩니다.

먼저 알아야 할 개념:

  • elliptic curve group
  • point addition
  • scalar multiplication
  • ECDH
  • ECDSA
  • invalid curve attack
  • small subgroup attack

대표 문제:

  • Elliptic Curve Associativity
  • EC
  • Half-Hundre-d-log
  • Elliptic?

풀이 관점:

곡선 파라미터가 안전한가?
point validation을 하는가?
order가 작은 subgroup이 있는가?
scalar가 작거나 일부만 필요한가?

ECC 문제는 처음부터 공식 전체를 외우기보다, SageMath로 point 연산을 직접 찍어보는 방식이 빠릅니다.

8단계: Lattice와 Post-Quantum Crypto

다이아 이상으로 가려면 lattice 계열을 피하기 어렵습니다.

먼저 알아야 할 개념:

  • vector, matrix
  • lattice
  • LLL
  • subset sum
  • knapsack
  • Learning With Errors
  • small error

대표 문제:

  • Subset Sum Problem
  • Learning With No Subsets
  • Learning With Small Errors

풀이 관점:

작은 해를 찾아야 하는가?
에러가 작은가?
정수 관계를 lattice로 만들 수 있는가?
LLL을 쓰면 짧은 벡터가 답이 되는가?

이 단계에서는 Python만 고집하지 말고 SageMath를 기본 도구로 둡니다.

3. 다이아 이상 문제를 위한 풀이 루틴

고난도 문제는 바로 풀리지 않는 것이 정상입니다. 대신 매번 같은 방식으로 접근합니다.

1차 분석: 30분

  • 문제 코드 전체를 읽는다.
  • 입출력 형식을 확인한다.
  • 암호화 식을 수식으로 바꾼다.
  • 공격자가 아는 값과 모르는 값을 나눈다.

2차 공격 가설: 1시간

  • 작은 값이 있는지 본다.
  • 반복되는 값이 있는지 본다.
  • key 재사용이 있는지 본다.
  • randomness가 충분한지 본다.
  • oracle이 있는지 본다.
  • 수학적으로 역산 가능한지 본다.

3차 구현: 1시간

  • exploit을 가장 작은 코드로 만든다.
  • toy example로 먼저 검증한다.
  • 실제 output에 적용한다.

4차 정리: 20분

풀이 후 반드시 아래 4줄을 기록합니다.

깨진 이유:
필요한 개념:
핵심 식:
다음에 비슷한 문제를 보면 확인할 것:

4. 문제 풀이 노트 템플릿

각 문제를 풀 때는 아래 형식으로 Quartz에 남깁니다.

## 0. 문제 요약
 
## 1. 주어진 파일
 
## 2. 암호화 구조
 
## 3. 공격자가 아는 값
 
## 4. 취약점
 
## 5. 핵심 수식
 
## 6. exploit
 
## 7. 실행 결과
 
## 8. 배운 점

풀이를 못 했더라도 2. 암호화 구조와 3. 공격자가 아는 값까지는 반드시 적습니다.

이 두 개가 쌓이면 나중에 같은 유형을 더 빨리 알아볼 수 있습니다.

5. 8주 학습 계획

1주차: 수론과 Python crypto 도구

  • 정수론 노트 복습
  • gcd, xgcd, modular inverse 직접 구현
  • bytes/int 변환 연습
  • Affe!n write-up 완성

2주차: 고전 암호와 대칭키 사용 실수

  • Affine, Caesar, substitution 정리
  • ECB/CBC/CTR 차이 정리
  • Double DES, Textbook-CBC 풀이

3주차: Padding oracle과 block cipher attack

  • PKCS#7 padding 정리
  • oracle attack 흐름 정리
  • Padding Miracle Attack 풀이

4주차: RSA 기본기

  • RSA key generation 직접 구현
  • Textbook-RSA, uncommon e, RSA Quartet 풀이

5주차: DH와 discrete log

  • BSGS 구현
  • Pohlig-Hellman 개념 정리
  • Textbook-DH, Hundre-d-log 풀이

6주차: Hash, MAC, Signature

  • birthday attack 실습
  • DSA nonce reuse 정리
  • 40 Birthdays, Textbook-DSA, Textbook-DSA2 풀이

7주차: ECC

  • SageMath로 point addition 실습
  • ECDH/ECDSA 정리
  • EC, Half-Hundre-d-log, Elliptic? 풀이

8주차: Lattice와 PQC 입문

  • LLL 예제 실습
  • subset sum lattice 변환 정리
  • Subset Sum Problem, Learning With Small Errors 풀이

6. 다이아 이상 문제를 풀기 전에 체크할 것

아래 질문에 대부분 답할 수 있으면 고난도 crypto를 풀 준비가 된 것입니다.

  • RSA에서 n, e, c만 보고 가능한 공격 후보를 떠올릴 수 있는가?
  • p - 1이 smooth할 때 discrete log 공격을 떠올릴 수 있는가?
  • DSA/ECDSA에서 nonce 재사용이 왜 위험한지 수식으로 설명할 수 있는가?
  • CBC padding oracle exploit을 직접 작성할 수 있는가?
  • SageMath에서 finite field, matrix, elliptic curve를 다룰 수 있는가?
  • LLL을 언제 써야 하는지 감이 있는가?
  • 문제 코드를 수식으로 바꾸는 습관이 있는가?

7. 참고할 Dreamhack 자료

8. 핵심 정리

다이아 이상 crypto 문제는 어려운 공식을 많이 외워서 푸는 것이 아닙니다.

문제 코드를 보고 다음 질문을 빠르게 하는 사람이 풉니다.

이 암호는 어떤 수학 구조를 쓰는가?
그 구조에서 반복되거나 작은 값이 있는가?
공격자가 아는 값으로 미지수를 줄일 수 있는가?

결국 목표는 이것입니다.

코드 -> 수식 -> 취약점 -> exploit

Graph View