실제 시험 문제 09

이 문제가 어려운 이유

처음 보면 IND, CCA, oracle, challenge라는 낯선 단어가 한꺼번에 등장한다. 그러나 시험 문제의 본질은 '공격자에게 어떤 능력을 주고도 비밀을 구별하지 못하게 해야 하는가?' 한 문장이다. 먼저 암호화 실험을 게임으로 이해하면 암기할 항목이 줄어든다.

이 글에서 익힐 것

• 암호화 스키마 Gen·Enc·Dec의 역할을 설명한다.

• 공격자 모델이 공격 기법 하나가 아니라 공격자에게 허용된 능력의 목록임을 이해한다.

• oracle, challenge, indistinguishability advantage의 뜻을 안다.

• IND-CCA 게임을 시간 순서대로 재현한다.

• challenge ciphertext 복호화 금지 규칙이 왜 필요한지 설명한다.

개념부터 차근차근

• 암호화 스키마 Π=(Gen, Enc, Dec)

  Gen은 키를 생성하고, Enc는 키와 평문 m을 받아 암호문 c를 만들며, Dec는 키와 암호문 c를 받아 평문을 복원한다. 대칭 암호라면 같은 비밀키를 쓰고, 공개키 암호라면 Enc에는 public key, Dec에는 private key를 쓴다. 정상 사용에서는 Dec(sk, Enc(pk,m))=m이어야 한다.

• 공격자 모델(Angreifermodell)

  암호가 안전하다는 말은 공격자가 무엇을 할 수 있는지를 정하지 않으면 의미가 없다. 암호문만 볼 수 있는 공격자와, 서버에 조작한 암호문을 보내 복호화 결과의 단서를 얻는 공격자는 능력이 다르다. 공격자 모델은 공격자에게 주는 자료·질의 권한·금지사항·승리 조건을 정확히 정한 실험이다.

• Oracle은 질문에 답해 주는 검은 상자

  공격자는 내부 키를 보지 못하지만 입력을 넣고 결과를 받을 수 있다. Encryption oracle Enc_k(·)에는 평문을 넣고 암호문을 받고, decryption oracle Dec_k(·)에는 암호문을 넣고 평문을 받는다. 현실에서는 로그인 서버, 스마트카드, API 또는 오류 메시지가 oracle처럼 행동할 수 있다.

• IND는 indistinguishability, 즉 구별 불가능성

  공격자가 직접 고른 같은 길이의 두 메시지 m₀,m₁ 중 하나가 암호화된다. 암호문을 보고 어느 쪽인지 유의미하게 더 잘 맞히지 못하면 두 메시지의 암호화가 구별 불가능하다고 한다. 무작위 추측 성공률은 1/2이며, 안전한 스키마에서는 효율적인 공격자의 추가 이득 advantage가 무시할 만큼 작아야 한다.

• CCA는 Chosen-Ciphertext Attack

  공격자가 스스로 암호문을 만들어 복호화 oracle에 질문할 수 있다는 뜻이다. 단순히 우연히 얻은 암호문을 보는 것이 아니라 공격 목적에 맞게 변형하거나 새 암호문을 선택하고 그 복호화 결과를 학습한다.

단계별로 따라가기

1. 0. Setup

   Challenger가 보안 파라미터에 따라 키를 만든다. 공격자는 키의 비밀 부분을 알지 못한다. 공개키 암호라면 public key는 당연히 받는다.

2. 1. 학습 질의

   공격자는 자신이 고른 암호문 c를 decryption oracle에 보내 Dec(c)를 받을 수 있다. adaptive CCA에서는 이전 답을 보고 다음 질의를 바꿀 수 있다.

3. 2. 후보 메시지 제출

   공격자는 같은 길이의 두 평문 m₀와 m₁을 제출한다. 길이를 같게 제한하는 이유는 암호문 길이만 보고 답을 알아내는 사소한 누출을 시험에서 제외하기 위해서다.

4. 3. Challenge 생성

   Challenger가 비밀 bit b∈{0,1}를 무작위로 고르고 c*=Enc(m_b)를 공격자에게 준다. 공격자의 목표는 b를 맞히는 것이다.

5. 4. Challenge 이후 질의

   IND-CCA2에서는 공격자가 계속 다른 암호문을 복호화 oracle에 질의할 수 있다. 단, 정확히 c* 자체는 질의할 수 없다. 보통 c*와 관련된 암호문을 조작해 묻는 것은 허용되므로 암호문의 malleability까지 견뎌야 한다.

6. 5. 추측

   공격자가 b'를 출력한다. b'=b일 확률이 1/2보다 무시할 수 없을 만큼 높지 않다면 그 스키마를 IND-CCA secure라고 한다.

왜 그런지 이해하기

Real world bridge padding oracle

• CBC 서버가 공격자가 보낸 암호문을 복호화한 뒤 'padding valid'와 'padding invalid'를 다른 오류·시간으로 구별해 준다고 하자.

• 서버가 전체 평문을 직접 돌려주지는 않아도 이 한 비트 반응이 제한된 decryption oracle 역할을 한다.

• 공격자는 이전 암호문 블록의 바이트를 체계적으로 바꾸고 oracle 반응을 관찰해 평문을 바이트 단위로 복원할 수 있다.

• 이것이 adaptive chosen-ciphertext attack의 현실적 직관이다. 정식 IND-CCA game의 oracle은 더 강하게 전체 복호화 결과를 주는 이상화된 모델이며, 그 강한 모델에서도 안전함을 목표로 한다.

헷갈리는 개념 비교하기

• CCA1(lunchtime/non-adaptive after challenge): challenge를 받기 전에는 복호화 질의를 할 수 있지만 challenge 이후에는 못 한다.

• CCA2(adaptive CCA): challenge 이후에도 c* 이외의 암호문에 질의할 수 있다. 일반적으로 IND-CCA라고 하면 강한 IND-CCA2를 뜻하는 경우가 많고, 강의 해설도 이를 gold standard로 다룬다.

• 시험 2점 답안에서는 이 구분까지 필수는 아니지만, challenge 자체 금지와 decryption oracle은 반드시 써야 한다.

문제를 푸는 순서

1. 1단계: CCA를 '공격자가 선택한 암호문을 복호화해 보는 능력'이라고 해석한다.

2. 2단계: decryption oracle이라는 핵심 권한을 적는다.

3. 3단계: 같은 길이 m₀,m₁ 중 하나의 challenge c*=Enc(m_b)를 받는다고 적는다.

4. 4단계: c* 자체의 복호화 질의는 금지된다고 적는다.

5. 5단계: 목표는 b를, 즉 어느 메시지가 암호화됐는지 1/2보다 유의미하게 잘 맞히는 것이라고 마무리한다.

스스로 확인하기

• IND-CCA 공격자가 oracle에 넣는 입력은 plaintext인가 ciphertext인가?

  ciphertext이며 복호화 결과를 받는다.

• 왜 m₀와 m₁의 길이를 같게 하는가?

  길이 누출만 보고 challenge를 구별하는 사소한 승리를 제외하기 위해서다.

• challenge c*를 그대로 복호화 요청할 수 있는가?

  없다. 다른 암호문에 대한 질의는 모델에 따라 허용된다.

• 무작위 추측의 성공률은?

  1/2이다. 안전한 스키마에서는 그보다 유의미한 추가 이득을 얻지 못해야 한다.

설명의 근거

• Gedächtnisprotokoll Computersystemsicherheit WS2025_26.md, Krypto / Angreifermodelle, 2-(a), 2 Punkte — 복기 원문.

• Übung 1 Lösung, p.11-12 — Gen/Enc/Dec, CPA·CCA oracle, challenge ciphertext 예외, IND-CCA2.

• Übung 2 Lösung, p.1-2 — CBC Padding Oracle을 adaptive chosen-ciphertext attack의 현실 사례로 설명.