095. IND-CPA (Indistinguishability under CPA) — 암호학적 안전성 정의

핵심 인사이트 (3줄 요약)

본질: IND-CPA (Indistinguishability under Chosen Plaintext Attack)는 해커가 맘대로 평문을 암호화해 볼 수 있는 권한(CPA)을 가진 상태에서도, 주어진 암호문이 두 개의 평문 중 어느 것에서 유래했는지 50%의 확률을 넘어서 '구별'해 낼 수 없는 안전한 상태를 말한다.

가치: "우리 암호는 안전하다"는 추상적인 주장을 폐기하고, 해커와 방어자 간의 수학적 스무고개 게임을 통해 '의미론적 안전성 (Semantic Security)'을 수학적으로 증명(Provable Security)하는 현대 암호학의 필수 합격 기준선이다.

판단 포인트: IND-CPA를 통과하려면 똑같은 평문을 넣어도 매번 다른 암호문이 나와야 하므로(무작위성), 무작위 초기화 벡터(IV)가 없는 ECB 모드나 패딩(OAEP)이 없는 순수 RSA 암호는 무조건 탈락 품목으로 간주하여 실무에서 즉시 퇴출시켜야 한다.

Ⅰ. 개요 및 필요성

과거의 암호학은 "비밀번호를 푸는 데 100년이 걸리니까 안전하다"는 식의 계산적 복잡성에 의존했다. 하지만 해커가 비밀번호 전체를 복구하지 못하더라도, 암호문 껍데기만 보고 "이 메시지는 긍정이다/부정이다" 식의 힌트 1비트라도 눈치챌 수 있다면 그 암호는 과연 안전한 것일까?

이러한 의문에서 출발하여 1984년 골드바서(Goldwasser)와 미칼리(Micali)는 **'의미론적 안전성 (Semantic Security)'**이라는 개념을 정립했다. 즉, "해커가 평문의 길이를 제외하고는 암호문에서 단 1비트의 정보도 유추할 수 없어야 완벽한 암호"라는 것이다. 이 철학을 엄격하게 테스트하기 위해, 해커에게 막강한 권한(선택 평문 공격, CPA)을 쥐여주고도 암호문의 원본을 구별해 낼 확률이 정확히 동전 던지기(50%) 수준에 머무르는지 검증하는 수학적 게임 모델이 바로 IND-CPA다.

📢 섹션 요약 비유: 옛날엔 상자가 튼튼해서 안 부서지면 "안전하다"고 우겼다. 하지만 IND-CPA는 상자를 부수지 못하더라도, 안에 사과가 들었는지 포도가 들었는지 냄새나 흔들리는 소리로 아주 조금의 힌트라도 얻을 수 있다면 그 상자를 "뚫린 상자"로 깐깐하게 탈락시키는 심사 위원이다.

Ⅱ. 아키텍처 및 핵심 원리

IND-CPA는 암호 알고리즘의 방어력을 측정하기 위해 해커 (Adversary)와 심사위원 (Challenger) 간의 가상 스무고개 게임으로 진행된다.

[ IND-CPA 구별 불가능성 게임 규칙 ]

학습 (CPA 권한 부여): 해커는 심사위원의 암호 기계(오라클)에 마음대로 원하는 평문을 넣고 암호문을 뽑아보며 패턴을 학습한다.
도전 (Challenge): 해커가 길이가 같은 서로 다른 평문 $M_0$와 $M_1$을 만들어 심사위원에게 제출한다.
암호화 및 퀴즈: 심사위원은 무작위로 동전을 던져 하나($b \in {0, 1}$)를 선택한 뒤, 암호화된 덩어리 $C$를 해커에게 던져주며 "이게 0번 평문이게, 1번이게?"라고 묻는다.
결과 판정: 해커가 어떤 꼼수를 부리더라도 정답을 맞출 확률이 $\frac{1}{2} + \epsilon$ (여기서 $\epsilon$은 무시할 수 있을 만큼 아주 작은 값)에 불과하다면, 이 암호 알고리즘은 **IND-CPA 안전성을 확보(합격)**한 것이다.

┌──────────────────────────────────────────────────────────────┐
│       IND-CPA 게임 모델 시각화 (해커 vs 심사위원)            │
├──────────────────────────────────────────────────────────────┤
│                                                              │
│ [ 🕵️ 해커 (Adversary) ]             [ 🧑‍⚖️ 심사위원 (Challenger) ] │
│      │                                              │        │
│      ├── 1. M0 ("사과"), M1 ("바나나") 제출 ───────▶│        │
│      │                                              │        │
│      │                (심사위원: 무작위 동전 던지기 $b=0$ 선택) │        │
│      │                (선택된 M0 암호화 -> 암호문 C 생성)    │        │
│      │                                              │        │
│      │◀──── 2. 수수께끼 암호문 C ("X9@!K") 반환 ────┤        │
│      │                                              │        │
│ (수많은 암호문과 비교 분석)                         │        │
│      │                                              │        │
│      ├── 3. 해커의 정답 예측: "$b'=0$ 입니다!" ────▶│        │
│                                                              │
│ ★ 평가: $P(b = b') \approx \frac{1}{2}$ 이어야만 합격(안전)! │
└──────────────────────────────────────────────────────────────┘

이 게임은 해커에게 가장 유리한 상황(원하는 걸 다 암호화해 볼 수 있음)을 가정하고도, 수학적으로 힌트가 누출되지 않음을 증명하는 극단적 스트레스 테스트다.

📢 섹션 요약 비유: 해커 두 눈을 가리고 코카콜라($M_0$)와 펩시($M_1$) 중 하나를 컵에 따라준다. 해커가 화학 분석기를 돌리든 무슨 짓을 해도, 그게 코카인지 펩시인지 찍어서 맞출 확률이 반반(50%)밖에 안 될 때만 그 컵(알고리즘)이 완벽한 시크릿 컵으로 인정받는다.

Ⅲ. 비교 및 연결

어떤 암호가 IND-CPA를 통과할 수 있고, 어떤 암호가 광탈하는지 비교하면 핵심 기술이 드러난다.

암호화 방식 / 모드	결정론 여부	무작위성(Randomness) 주입 수단	IND-CPA 통과 여부
블록 암호 (ECB 모드)	결정론적 (Deterministic)	없음 (같은 평문 = 같은 암호문)	❌ 탈락 (해커가 즉시 구별)
블록 암호 (CBC / CTR)	확률론적 (Probabilistic)	무작위 IV (Initialization Vector) / Nonce	✅ 통과 (매번 다른 암호문)
순수 RSA 암호	결정론적 (Deterministic)	없음 ($M^e \pmod n$)	❌ 탈락
RSA-OAEP	확률론적 (Probabilistic)	평문에 무작위 난수 패딩 (OAEP) 추가	✅ 통과

IND-CPA를 통과하기 위한 절대 조건은 **확률적 암호화 (Probabilistic Encryption)**다. 암호화를 할 때마다 내부에 주사위(난수)를 굴려서 똑같은 "사과"를 넣어도 첫 번째는 "X9@!K", 두 번째는 "Z#19Q"처럼 완전히 다른 껍데기를 뒤집어써야만 해커를 50%의 늪에 빠뜨릴 수 있다.

📢 섹션 요약 비유: 결정론적 암호화(ECB)는 매번 똑같은 가면을 쓰는 도둑이다. 한 번만 얼굴을 보면 다음엔 바로 알아챈다. 반면 확률적 암호화(CBC+IV)는 나올 때마다 성형 수술로 얼굴을 바꾸는 스파이여서, 도저히 누군지 특정할 수 없다.

Ⅳ. 실무 적용 및 기술사 판단

실무 보안 아키텍처나 TLS 통신 채널을 설계할 때, 알고리즘의 이름표보다 중요한 것은 그 알고리즘이 구동되는 모드 (Mode of Operation)와 패딩 방식이다.

실무 판단 기준

ECB 모드 퇴출: 이미지나 정형 데이터를 암호화할 때 AES-256이라는 강력한 알고리즘을 쓰더라도, 운영 모드가 ECB라면 IND-CPA를 만족하지 못하므로 원본 패턴이 고스란히 노출된다. 무조건 CBC나 GCM 모드로 전환해야 한다.
IV (초기화 벡터) 재사용 금지: CBC 모드에서 IV를 난수로 생성하지 않고 고정값("0000...")으로 하드코딩하면, 무작위성이 사라져 다시 결정론적 암호(IND-CPA 탈락 상태)로 퇴화한다. IV는 매 통신마다 반드시 새롭게 굴린 난수여야 한다.
CCA 대비: IND-CPA는 해커가 '평문'을 맘대로 넣는 권한만 줬다. 실무에서는 해커가 '조작된 암호문'을 서버에 던져 반응을 살피는 더 악랄한 CCA (선택 암호문 공격)까지 방어해야 한다. 이를 위해 무결성 검증을 합친 인증 암호화 (AEAD, 예: AES-GCM) 도입이 필수적이다.

📢 섹션 요약 비유: 아무리 튼튼한 금고(AES 알고리즘)를 샀어도, 비밀번호를 '0000'(고정 IV)으로 설정해 두면 도둑이 한 번에 문을 연다. 금고의 철판 두께보다 자물쇠의 무작위성이 더 중요하다.

Ⅴ. 기대효과 및 결론

IND-CPA는 암호가 뚫리지 않음을 증명하는 '수학적 대헌장'이다. 이 게임 모델 덕분에 현대 암호학은 해커가 발전해도 방어력이 유지됨을 수학의 확률론에 근거하여 당당하게 증명(Provable Security)할 수 있게 되었다.

결론적으로, 완벽하게 구별 불가능하지 않다면 그것은 안전한 암호가 아니다. 어떤 혁신적인 양자 내성 암호 (PQC)가 새롭게 발명되더라도 이 IND-CPA (또는 IND-CCA) 스무고개 게임의 문턱을 넘지 못하면 국제 표준 (NIST)의 도장을 결코 받을 수 없다는 점을 명심해야 한다.

📢 섹션 요약 비유: IND-CPA는 국가대표 선발전의 **'기본 체력장'**이다. 이 체력장(구별 불가능성)을 통과하지 못한 선수는 아무리 화려한 기술(새로운 알고리즘 이름)을 자랑해도 올림픽(인터넷 표준) 무대에 나설 수 없다.

📌 관련 개념 맵

개념	연결 포인트
CPA (Chosen Plaintext Attack)	해커가 원하는 평문을 마음대로 암호화 기계에 넣어볼 수 있는 전제 공격 모델
의미론적 안전성 (Semantic Security)	암호문에서 평문에 대한 어떤 정보(길이 제외)도 얻을 수 없다는 철학 (IND-CPA와 동치)
IND-CCA (Indistinguishability under Chosen Ciphertext Attack)	CPA보다 한 단계 더 나아가 해커가 암호문을 복호화해 볼 권한까지 가진 상태에서의 안전성
확률적 암호화 (Probabilistic Encryption)	동일 평문에 매번 다른 암호문을 생성하기 위해 난수(IV, Nonce, Padding)를 사용하는 기법

📈 관련 키워드 및 발전 흐름도

암호 알고리즘 설계 및 단순 암호화 시도
    │
    ▼
선택 평문 공격 (CPA) 위협 대두
    │
    ▼
의미론적 안전성 (Semantic Security) 개념 정립
    │
    ▼
IND-CPA 게임 모델 확립 (50% 구별 불가능성 증명)
    │
    ▼
확률적 암호화 강제 (IV, Nonce, OAEP 패딩 도입)
    │
    ▼
더 강력한 공격(CCA)을 방어하기 위한 IND-CCA (AEAD, GCM) 로 진화

이 흐름도는 단순히 튼튼함을 주장하던 시대에서 벗어나, 해커에게 막강한 권한(CPA)을 주고도 확률적으로 안전함을 증명하는 게임 모델(IND-CPA)을 거쳐, 현대의 인증 암호화(AEAD)로 진화하는 궤적을 보여준다.

👶 어린이를 위한 3줄 비유 설명

암호학자들은 새로 만든 자물쇠가 진짜 튼튼한지 테스트하려고 해커랑 스무고개 게임을 해요.
상자 안에 딸기우유나 초코우유 중 하나를 몰래 넣어서 해커에게 주는데, 겉모습만 보고 100번 중에 51번이라도 정답을 맞추면 자물쇠는 불합격이에요.
힌트가 단 하나도 없어서 무조건 동전 던지기처럼 반반(50%) 확률로 찍을 수밖에 없는 자물쇠만 "IND-CPA 합격!" 도장을 받아요.