095. IND-CPA (Indistinguishability under CPA)

⚠️ 이 문서는 "어떤 암호가 안전하다"는 뜬구름 잡는 소리를 집어치우고, 암호학계에서 수학자와 해커 간에 벌어지는 극악의 스무고개 게임을 통해 자물쇠의 방어력을 수학적으로 증명(Provable Security)해 내는 절대 기준점인 IND-CPA를 다룹니다.

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

  1. 본질: IND-CPA는 암호 시스템이 CPA(선택 평문 공격) 상황을 견뎌내면서, 해커가 두 개의 암호문 중 어느 것이 자신이 보낸 평문에서 나온 것인지 50%의 확률(찍기)을 넘어서 '구별(Indistinguishability)'할 수 없는 상태를 의미한다.
  2. 가치: "우리 암호는 안 뚫려요"라는 마케팅 용어를 배제하고, 해커가 암호 기계를 맘대로 주무를 수 있는 무제한의 권력을 줘도 수학적으로 힌트를 1비트도 얻어갈 수 없음을 증명하는 현대 암호학의 최소 합격 기준선(Baseline)이다.
  3. 융합: 이 상태(IND-CPA)를 달성하지 못하는 암호(예: 무작위 IV가 없는 ECB 모드나 패딩 없는 순정 RSA)는 결함품으로 간주되어 인터넷 표준(TLS)에 절대로 이름을 올릴 수 없으며 전량 폐기된다.

Ⅰ. 개요 및 탄생 배경 (Context & Necessity)

1980년대까지 암호학자들은 "내 자물쇠(암호)는 풀기 졸라게 힘드니까 안전해!"라고 주장했다. 하지만 한 천재 수학자가 물었다. "비밀번호 전체를 푸는 건 힘들겠지만, 암호문 껍데기만 보고도 안에 든 게 '남자'인지 '여자'인지, 혹은 1비트라도 힌트를 눈치챌 수 있다면 그건 안전한 건가?"

1984년 골드바서(Goldwasser)와 미칼리(Micali)는 **'의미론적 안전성(Semantic Security)'**이라는 위대한 개념을 제안했다. **"완벽한 암호란, 해커가 평문의 길이를 제외하고는 암호문으로부터 단 1비트의 정보(힌트)도 유추할 수 없는 것"**이다. 이 철학을 현실의 스무고개 게임(해커 vs 방어자) 모델로 구현하여, 이 게임에서 해커가 이길 확률이 딱 절반(동전 던지기 수준)이면 "이 암호는 안전하다!"고 인증서 도장을 쾅 찍어주는 테스트가 바로 IND-CPA (선택 평문 공격 하에서의 구별 불가능성) 게임이다.

📢 섹션 요약 비유: 옛날엔 상자가 안 부서지면 "안전하다"고 우겼습니다. IND-CPA는 상자 안에 사과가 들었는지 포도가 들었는지 냄새, 무게, 흔들림 소리로 조금이라도 힌트를 얻을 수 있다면 그 상자는 "뚫린 상자(실패)"라고 엄격하게 탈락시키는 깐깐한 심사 위원입니다.

Ⅱ. IND-CPA 증명 게임: 해커(Adversary) vs 오라클(Challenger)

암호가 IND-CPA 조건을 만족하는지 테스트하기 위해, 암호학계는 가상의 게임을 진행한다. (이 게임에서 해커가 50%보다 높은 확률로 정답을 맞히면 암호는 쓰레기통으로 간다.)

🎮 [ IND-CPA 스무고개 게임 규칙 ]

  1. 학습 단계 (해커의 권력 남용): 해커(Adversary)는 100만 번이고 1,000만 번이고 암호 기계(오라클)에 자기가 원하는 평문(예: "사과", "바나나")을 찔러 넣고 암호문을 받아본다. (이것이 CPA, 선택 평문 공격 권한을 부여한 것이다.)
  2. 문제 출제 (도전장 던지기): 해커가 심사위원(Challenger)에게, 내용이 다르지만 길이가 똑같은 두 개의 평문 $M_0$와 $M_1$을 만들어 던져준다. (예: "나는 너를 사랑해", "나는 너를 미워해")
  3. 심사위원의 트릭 (암호화): 심사위원은 동전을 던져(0 또는 1) 둘 중 하나만 무작위로 고른다 (예: $M_0$ "사랑해" 당첨). 그리고 심사위원이 이걸 암호화해서 나온 덩어리 $C$ (암호문)를 해커에게 던져주며 묻는다. "자, 내가 던진 게 0번이게, 1번이게?"
  4. 해커의 몸부림과 최종 판결 (구별 테스트): 해커는 또다시 기계를 마구 돌려보면서(CPA) 심사위원이 준 암호문 $C$를 분석한다. 그리고 대답한다. "이건 0번이다!"
    • 판결: 만약 해커가 동전 던지기 확률(50%)을 아주 조금이라도 넘어서서 정답을 맞힌다면, 그 암호는 힌트를 질질 흘린 것이므로 **IND-CPA 실패(탈락)**다. 해커가 아무리 용을 써도 50% 확률로 찍는 수밖에 없다면 그 암호는 **IND-CPA 합격(안전)**이다.
┌──────────────────────────────────────────────────────────────────────────┐
│           IND-CPA 테스트 (구별 불가능성 게임) 흐름도 시각화              │
├──────────────────────────────────────────────────────────────────────────┤
│                                                                          │
│ [ 🕵️ 해커 ]                                  [ 🧑‍⚖️ 심사위원 ]          │
│      │                                              │                    │
│      ├── 1. M0 ("사과"), M1 ("바나나") 던짐 ────▶│                       │
│      │                                              │                    │
│      │               (심사위원: 동전 뒤집기 0! "사과" 선택) │            │
│      │               (비밀키로 암호화 진행 -> "X9@!K" 나옴)│             │
│      │                                              │                    │
│      │◀──── 2. 수수께끼 암호문 C ("X9@!K") 던짐 ──┤                      │
│      │                                              │                    │
│  (뇌 굴리기: 방금 쟤가 사과를 섞었을까 바나나를 섞었을까?)       │       │
│      │                                              │                    │
│      ├── 3. 해커의 정답: "내 생각엔 0번 사과야!" ───▶│                   │
│                                                                          │
│ ★ 평가 결과: 해커가 맞출 확률이 50.0001%라도 되면 이 암호는 쓰레기통행!  │
└──────────────────────────────────────────────────────────────────────────┘

[다이어그램 해설] 이 게임은 암호학의 가장 무서운 진실을 보여준다. 만약 자물쇠가 **ECB 모드(똑같은 걸 넣으면 똑같은 게 나옴)**라면? 해커는 1번 학습 단계에서 미리 기계에 "사과"를 넣어보고 "X9@!K"가 나오는 걸 공책에 적어놨을 것이다. 2단계에서 심사위원이 "X9@!K"를 주면, 해커는 공책을 보고 100% 정답을 맞혀버린다. 따라서 ECB 모드는 IND-CPA 탈락이다! (절대 쓰면 안 되는 이유가 증명됨)

  • 📢 섹션 요약 비유: 해커 두 눈을 가리고 심사위원이 코카콜라(M0)와 펩시(M1) 중 하나를 컵(암호화)에 따라줍니다. 해커가 냄새를 맡든 기계를 돌리든 무슨 짓을 해도, 그게 코카인지 펩시인지 찍어서 맞출 확률이 50%(반반)밖에 안 되어야만 그 컵(암호 알고리즘)이 완벽한 시크릿 컵으로 인정받습니다.

Ⅲ. IND-CPA 합격의 절대 조건: 무작위성 (Randomization)

자물쇠가 IND-CPA라는 혹독한 게임에서 50% 찍기를 강제하려면, 심사위원(알고리즘)이 암호화를 할 때마다 무조건 주사위(난수)를 굴려서 결과를 다르게 뱉어내야 한다.

이것을 암호학에서는 **확률적 암호화 (Probabilistic Encryption)**라고 부른다.

  • CBC 모드나 CTR 모드: 암호화를 시작할 때 무작위 IV(초기화 벡터)나 Nonce를 집어넣는다. 따라서 심사위원이 "사과"를 암호화해도 이번엔 "X9@!K"가 나오고, 다음번에 또 "사과"를 암호화하면 "Z#19Q"가 나온다. 해커는 헷갈려서 정답을 찍을 수밖에 없다 $\rightarrow$ IND-CPA 합격!
  • RSA 암호: $M^e \pmod n$ 공식 그대로 돌리면 무조건 답이 똑같다(결정론적). IND-CPA 탈락. 그래서 RSA를 실무에 쓸 때는 평문에 쓸데없는 무작위 난수를 떡칠하는 OAEP 패딩을 억지로 붙여서 확률론적 암호로 탈바꿈시켜야만 IND-CPA 합격 도장을 받을 수 있다.

Ⅳ. 결론

"완벽하게 구별 불가능하지 않다면, 안전한 암호가 아니다." IND-CPA는 암호학자들이 자물쇠의 안전성을 논할 때 감정이나 경험을 배제하고 수학적인 증거(확률)로 승부하는 현대 보안 공학의 대헌장이다. 어떤 신기술 암호(양자 내성 암호 등)가 새로 나오더라도, 이 스무고개 게임(IND-CPA)의 문턱을 넘지 못하면 결코 인터넷 표준 문서(RFC)에 단 한 줄도 이름을 올릴 수 없다.

📌 관련 개념 맵

  • 전제 공격 모델: CPA (선택 평문 공격 - 해커가 맘대로 평문을 찔러보는 권한)
  • 상위 (더 빡센) 기준: IND-CCA (선택 암호문 공격 하의 구별 불가능성)
  • 합격을 위한 핵심 기술: IV (초기화 벡터), Nonce, 난수 기반 패딩(OAEP)
  • 탈락하는 안티패턴: 결정론적(Deterministic) 암호화 (예: ECB 모드, 순정 RSA)

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

  1. 암호학자들은 새로 만든 자물쇠가 튼튼한지 테스트하기 위해 해커랑 스무고개 게임을 해요.
  2. 상자 안에 딸기우유나 초코우유 중 하나를 몰래 넣어서 해커에게 던져주는데, 해커가 겉모습만 보고 무슨 우유인지 100번 중에 51번이라도 맞추면 그 자물쇠는 불합격 처리돼요.
  3. 무조건 동전 던지기처럼 반반(50%) 확률로 찍을 수밖에 없을 만큼 힌트를 하나도 안 주는 자물쇠만 "IND-CPA 합격!" 도장을 받고 세상에 출시될 수 있답니다.