실제 시험 문제 10

이 글에서 익힐 것

• CPA의 P가 Plaintext, CCA의 C가 Ciphertext임을 권한과 연결한다.

• encryption oracle과 decryption oracle의 입·출력을 정확히 적는다.

• 두 게임의 공통 challenge 구조와 차이점을 구분한다.

• 왜 CCA 공격자가 더 강하고 IND-CCA 보안이 더 어려운 목표인지 설명한다.

• IND-CPA 안전하지만 IND-CCA에는 취약할 수 있는 malleability 직관을 이해한다.

먼저 되짚을 기초

• Encryption oracle

  공격자가 평문 m을 선택해 넣으면 c=Enc(k,m)를 돌려준다.

  내가 원하는 입력이 어떻게 암호화되는지 관찰할 수 있는가?

• Decryption oracle

  공격자가 암호문 c를 선택해 넣으면 m=Dec(k,c)를 돌려준다.

  내가 만든 또는 변형한 암호문을 시스템이 어떻게 해석하는지 관찰할 수 있는가?

• Challenge

  공격자가 같은 길이 m₀,m₁을 내면 challenger가 무작위 b를 골라 c*=Enc(m_b)를 준다.

  암호문이 어느 후보 메시지인지 구별할 수 있는가?

개념부터 차근차근

• CPA는 Chosen-Plaintext Attack이다. 공격자가 평문을 선택하고 그 암호문을 받아볼 수 있다.

• 공격자는 encryption oracle에 m을 넣어 Enc(k,m)를 관찰한다. 공개키 암호에서는 public key로 누구나 암호화할 수 있으므로 이 권한은 자연스럽다.

• 공격자는 학습 결과를 바탕으로 같은 길이의 m₀,m₁을 고르고 challenge c*=Enc(m_b)를 받는다.

• b를 동전 던지기보다 유의미하게 잘 맞히지 못하면 IND-CPA secure다.

• 확률적 암호화 또는 매번 새로운 nonce/randomness가 중요한 이유도 같은 평문을 암호화할 때 결과가 항상 같으면 encryption oracle로 비교해 challenge를 쉽게 알아낼 수 있기 때문이다.

개념부터 차근차근

• CCA는 Chosen-Ciphertext Attack이다. 공격자가 암호문을 선택하고 복호화 결과를 받아볼 수 있다.

• CCA 공격자는 일반적으로 CPA에서 가능한 정보에 더해 decryption oracle까지 이용한다.

• challenge c*=Enc(m_b)를 받은 후에도 IND-CCA2에서는 c*와 정확히 같지 않은 다른 암호문을 복호화해 볼 수 있다.

• c* 자체를 요청하는 것은 금지된다. 그러나 c*를 변형한 암호문을 물어볼 수 있으므로 변조 가능성(malleability)과 오류 반응을 악용하는 공격까지 견뎌야 한다.

• 이 강한 권한에도 b를 구별하지 못해야 IND-CCA secure다.

헷갈리는 개념 비교하기

• Criterion

  공격자가 선택하는 것

  IND-CPA

  Plaintext m

  IND-CCA

  Ciphertext c

• Criterion

  핵심 oracle

  IND-CPA

  Encryption oracle Enc(·)

  IND-CCA

  Decryption oracle Dec(·), 보통 encryption 능력도 포함

• Criterion

  oracle 응답

  IND-CPA

  선택한 평문의 ciphertext

  IND-CCA

  선택한 암호문의 plaintext

• Criterion

  challenge 공통점

  IND-CPA

  c*=Enc(m_b)를 보고 b 추측

  IND-CCA

  같은 challenge에서 b 추측

• Criterion

  핵심 금지

  IND-CPA

  게임 규칙에 따른 challenge의 자명한 재현을 막는 조건

  IND-CCA

  challenge c* 자체를 decryption oracle에 제출 금지

• Criterion

  공격자 강도

  IND-CPA

  상대적으로 약함

  IND-CCA

  복호화 반응까지 이용하므로 더 강함

• Criterion

  보안 요구

  IND-CPA

  선택 평문 관찰에도 기밀성

  IND-CCA

  능동적 암호문 변형·복호화 질의에도 기밀성

Easy analogy

왜 그런지 이해하기

• 능력 집합 관점에서 CCA 공격자는 CPA 공격자가 할 수 있는 관찰에 복호화 질의라는 추가 능력을 가진다.

• 따라서 어떤 암호가 더 강한 CCA 공격자에게도 안전하다면, 더 약한 CPA 공격자에게도 안전해야 한다: IND-CCA ⇒ IND-CPA.

• 반대는 일반적으로 성립하지 않는다. 선택 평문 공격에는 안전하지만 조작한 암호문에 대한 복호화 반응에서 정보가 새는 방식이 있을 수 있다.

• 즉, '공격 모델이 강하다'와 '암호가 강하다'를 혼동하면 안 된다. CCA가 강한 공격 모델이고, IND-CCA secure는 더 높은 보안 등급이다.

Same and different

문제를 푸는 순서

1. 1단계: 약어를 풀어 P=Plaintext, C=Ciphertext를 표시한다.

2. 2단계: CPA의 encryption oracle 입·출력을 한 문장으로 쓴다.

3. 3단계: CCA의 decryption oracle 입·출력을 한 문장으로 쓴다.

4. 4단계: CCA에서는 challenge ciphertext 자체 질의가 금지된다고 덧붙인다.

5. 5단계: CCA가 더 강한 공격자 모델이며 IND-CCA가 더 강한 보안 목표라고 결론 낸다.

스스로 확인하기

• 공격자가 'AAAA'를 암호화해 달라고 요청한다면 CPA와 CCA 중 어느 권한인가?

  chosen plaintext를 encryption oracle에 넣는 CPA 권한이다.

• 공격자가 조작한 암호문 0xABCD를 복호화해 달라고 한다면?

  chosen ciphertext를 decryption oracle에 넣는 CCA 권한이다.

• IND-CCA secure이면 IND-CPA secure인가?

  그렇다. 더 강한 공격 모델을 견디면 더 약한 모델도 견딘다.

• IND-CPA secure이면 반드시 IND-CCA secure인가?

  아니다. 복호화 oracle이나 암호문 변형을 이용한 공격에는 취약할 수 있다.

설명의 근거

• Gedächtnisprotokoll Computersystemsicherheit WS2025_26.md, Krypto / Angreifermodelle, 2-(b), 2 Punkte.

• Übung 1 Lösung, p.11-12 — CPA encryption oracle, CCA decryption oracle 및 challenge 예외.

• Übung 2 Lösung, p.1-2 — CBC Padding Oracle을 CCA의 직관적 사례로 연결.

이 문제가 어려운 이유

짧은 문제 문장 ‘IND-CCA(Chosen Ciphertext Attack)와 IND-CPA(Chosen Plaintext Attack)의 차이를 설명하라.’ 안에 정의, 조건, 처리 순서가 압축되어 있습니다. 아래 예시에서는 이를 한 단계씩 펼쳐 확인합니다.