깨지는 암호의 해부학

쿠쿡 안녕하세요 

오늘은 암호학에 대해서 알아보겠습니다!

(2026-06-23에 진행한 UNKNOWN 세미나 내용)

---

대칭 비대칭 해시

3대 암호 프리미티브

대칭키

• 키 1개를 양쪽이 공유
• 빠름(AES-NI, GB/s급)
• 대량 본문 암호화
• 약점: 키 분배

→ 합의된 세션키로 본문 암호화 (빠름, 대량 데이터)

비대칭키

• 공개키/개인키 쌍
• 느림(수백~수천 배)
• RSA, ECDH, ECDSA
• 키 교환 서명
• 사전 공유 없이 채널 개설

→ 사전 공유 없이 세션키 합의(느림, 핸드셰이크 1회)

해시

• 키 없음
• 일방향, 충졸 저항
• 무결성, 지문, 커밋
• 해시 ≠ 인증

→ 인증서 서명,메시지 무결성을 전 과정에서 보증

블록 암호 운영 모드

ECB

• 블록 독립 암호화
• 단순, 병렬
• 동일 입력 = 동일 출력 → 패턴 노출(펭귄)
• 실무 금지

CBC

• 직전 암호문과 XOR 연쇄, 패턴 숨김, 직렬, IV 예측 위험,패딩 필요
  → 패딩 오라클의 무대

CTR

• 카운터 암호화 → 키스트림 XOR, 병렬, 랜덤 엑세스 패딩 불필요, nonce 재사용
  → 키스트림 재사용

GCM

• CTR + GHASH 인증 → AEAD(인증형 암호), 기밀성+무결성, 사실상 TLS 표준, nonce 재사용에 극도로 취약

CTR·GCM nonce 재사용 — 키스트림 소거

공개키

• RSA(IFP) · ECC/ECDSA(ECDLP)
• 공개키 안전성은 인수분해(RSA), 이산로그(ECC) 난해성 가정에 의존하며, 이 가정은 양자 알고리즘(Shor)에 의해 붕괴됨

# --- RSA: 어려움의 근거 = 인수분해(IFP) ---
n = p * q           # p,q는 큰 소수 (공개: n, e)
phi = (p-1)*(q-1)   # p,q 알아야 계산 가능
d = pow(e, -1, phi) # 개인키 = e의 역원 (phi 필요!)
c = pow(m, e, n)    # 암호화 (정방향: 쉬움)
m = pow(c, d, n)    # 복호화 (d 알면 쉬움)
# 공격자는 n만 안다 -> n을 p,q로 쪼개야 phi,d가 나온다

# --- ECC/ECDSA: 어려움의 근거 = 이산로그(ECDLP) ---
Q = d * G           # 점 G를 d번 더함 (정방향: 쉬움)
# 역방향: Q와 G를 알아도 d를 구하기가 어렵다 = ECDLP
# ECDSA는 이 위에 서명을 얹는다 (nonce k 재사용=개인키 누출!)

공개키 일방향성

한 방향(곱셉,스칼라곱)은 쉽고 역방향(인수분해,이산로그)은 어려움

→ 이 난이도 격차가 공개키의 안정성이며, 양자 Shor가 그 격차를 무너뜨림

무결성·인증 도구 — MAC · HMAC · AEAD

• 암호화(기밀성)만으론 부족
• ‘변조 불가’까지 가야 안전함
• MAC
  • 비밀키로 태그를 생성, 검증
  • 키 없이는 유효한 메시지, 태그를 위조 불가
    → 무결성 + 송신자 인증
• HMAC
  • 해시를 이중으로 감싼 표준 MAC
  • 이 중첩이 length-extension을 차단
• AEAD
  • 기밀성, 무결성, 인증을 한 연산

무결성, 인증은 비밀키 태그(MAC)로 해시와 구분하고, AEAD가 암호화와 인증을 하나로 묶음

위협 모델과 오라클 — IND-CPA/CCA · 오라클

• IND-CPA (선택평문공격 하 구별불가능성)
  • 암호화 오라클이 있어도 두 평문의 암호문을 구별 못 해야 안전. 결정론적(같은 평문→같은 암호문)이면 탈락 → ECB
• IND-CCA (선택암호문공격 하 구별불가능성)
  • CPA에 더해 복호화 오라클(챌린지암호문 제외)까지 허용 · 패딩 오라클·비트플리핑이 여기 · 실전 기준선
• 오라클 (oracle)
  • 공격자가 질의할 수 있는 블랙박스로, 비밀에 의존하는 1비트(유효/무효·시간차·에러종류)를 누설. 반복 질의로 키 없이 비밀 복원

패딩 오라클

CBC + PKCS#7

• 블록을 사슬로 엮는 운용 모드와 마지막 블록을 채우는 패딩 규칙
• 키 없이 ‘이전 블록 조작 → 패딩 검사 결과 관찰’만으로 평문이 복원됨

PKCS#7 패딩

규칙: 한 블록을 채우려고 N칸이 모자라면 그 N칸을 전부 ‘값 N’로 채움

→ 바이트에 부족한 부분이 없으면 한 블록을 더 붙임
패딩이 없으면 받는 쪽이 어디까지가 진짜 데이터인지 알 수 없기 때문

• 복호화 후 떼어내기
  • 끝에서 N바이트가 전부 N이면 패딩 → N칸을 떼어냄

CBC 복호화 구조

• 키 없이 이전 블록 조작 → 패딩 검사 관찰만으로 평문이 샘
  → 흘러나온 1비트가 오라클

패딩 오라클

• 공격자는 암호화가 아니라 복호화, 패딩검사 단계에 개입함
  → 자신의 쿠키를 변조해 반복 전송

손으로 풀어보기

패딩 1바이트 복구

 

1. 서버가 OK를 준 조작 바이트

guess = 0x50

 

2. 목표 패딩 0x01 유도 성공

조작 평문 끝 = 0x01

 

3. 중간값 = guess ⊕ 0x01

0x50 ⊕ 0x01 = 0x51 ( = D_K(C)[15], 키 없이 얻음 )

 

4. 진짜 직전 블록 바이트

C(i−1)[15] = 0x10

 

5. 평문 = 중간값 ⊕ C(i−1)[15]

0x51 ⊕ 0x10 = 0x41 = 'A'

서버 내부 처리 순서

1️⃣ 복호화함
암호문 쿠키를 받아 블록 전체를 복호화해 조작된 평문 P'_i[0]~P'_i[15]를 만듦

2️⃣ 패딩 검사함
마지막 바이트가 0x01이면 패딩 길이 1로 해석하고 [15]만 검사한다. 0x02면 [14],[15]를 봄

3️⃣ 패딩 제거 후 다음 단계
패딩이 맞으면 그 바이트들을 제거하고, 남은 평문을 쿠키/JSON/세션 데이터로 넘김

4️⃣ 내용 검증에서 실패
쿠키 구조, JSON, 세션 ID, 권한 검증에서 실패할 수 있다. 이 실패가 패딩 실패와 구별되면
힌트가 됨

Bleichenbacher

RSA PKCS#1 v1.5 패딩 구조

RSA 평문 앞에 붙는 고정 포맷(00 02 PS 00 M). 서버가 복호화 후 이 포맷의 적합성(OK/FAIL)을 노출하면, 그 1비트가 Bleichenbacher 오라클이 됨

방어

오라클 방어의 핵심 = 내부 실패 이유가 달라도 밖에서는 모두 같은 실패로 보이게 만들기

1. AEAD 사용
   암호화와 인증을 한 번에 처리
   AAD·암호문이 바뀌면 태그 검증 실패
   → 복호화 결과 자체를 보여주지 않음
2. Encrypt-then-MAC
3. 복호화 전에 MAC부터 확인
   MAC 실패 = 동일한 실패 응답
   → 패딩 오류가 밖으로 새지 않음
4. 프로토콜 교체
5. static RSA KEX 제거 → (EC)DHE·KEM
   TLS 1.3처럼 RSA 복호화 오라클 제거
   → 공격할 분기 자체를 없앰
6. 상수시간 에러 처리
7. 실패해도 같은 시간·같은 응답
   랜덤 PMS로 계속 진행
   → 타이밍·분기 차이를 0에 가깝게

ECDSA nonce 재사용

ECDSA 서명식

• k 노출 시 개인키 d 복구
• ECDSA 서명은 매번 비밀 일회용 값 k(nonce)로 R=kG를 만들고, r과 메시지 해시 z를 개인키 d로 묶어 s를 생성함
• k가 노출되면 d = (s·k − z)/r로 개인키가 즉시 복구됨

동일 k → 개인키 d 복구 (두 서명식의 차)

• 동일한 k를 두 번 사용하면 두 서명의 r이 같아진다. 미지수 k, d 두 개에 식 s₁, s₂ 두 개 — 연립방정식이 성립함
• 두 식을 빼면 k, 대입하면 d가 구해짐

타이밍 공격

memcmp의 함정

• 조기 종료(early-exit) 비교: strcmp/memcmp는 첫 불일치 바이트에서 즉시 반환함
  반환 시점이 일치한 접두 길이를 노출하므로, 응답 시간으로 비밀을 한 바이트씩 복원할 수 있음

상수시간 4원칙

1. if(secret) 금지
2. 나쁜 예: 비밀값에 따라 if/else로 갈라짐
   대신: 양쪽을 모두 계산하고 마스크로 결과만 선택
3. 첫 불일치에서 멈추지 않기
4. 나쁜 예: memcmp처럼 틀린 순간 return
   대신: 끝까지 돌며 diff |= a ^ b 누적 후 마지막에 판정
5. table[secret] 금지
6. 나쁜 예: 비밀값으로 배열 인덱싱
   대신: 전체 순회·마스크 선택 또는 AES-NI 같은 검증된 경로 사용
7. 직접 구현 최소화
8. 비밀 비교: hmac.compare_digest /
   CRYPTO_memcmp / sodium_memcmp
   큰 암호 구조: 검증된 라이브러리에 맡김

→ 상수시간의 핵심은 항상 빠르게가 아니라 비밀값이 달라도 공격자 눈에는 같은 시간 같은 접근으로 보이게 하는 것

---

내용이 생각보다 많이 어려워서 이해는 다 하지 못했지만.....

암호학이 어떤 건지 조금 알게 된 것 같습니다....!

세미나 내용은 다음에 계속됩니다.....