선택-일반 텍스트 공격

Chosen-plaintext attack

선택된-일반 텍스트 공격(CPA)은 공격자가 임의의 일반 텍스트에 대한 암호문을 얻을 수 있다고 가정하는 암호 분석을 위한 공격 모델이다.[1] 공격의 목표는 암호화 방식의 보안을 떨어뜨리는 정보를 얻는 것이다.[2]

현대의 암호는 선택된-플레인 텍스트 공격 하에서 암호문 식별 불가능성으로도 알려진 의미적 보안을 제공하는 것을 목표로 하고 있으며, 따라서 설계상으로는 올바르게 구현될 경우 일반적으로 선택된-플레인 텍스트 공격에 대해 면역이 된다.

소개

선택된 일반 텍스트 공격에서 상대방은 임의의 일반 텍스트 메시지의 암호문을 요구할 수 있다(적응적으로). 이것은 적수가 블랙박스로 보이는 암호화 오라클과 상호작용을 할 수 있게 함으로써 공식화된다. 공격자의 목표는 비밀 암호키의 전부 또는 일부를 공개하는 것이다.

공격자가 주어진 일반 텍스트에 대한 암호문을 얻을 수 있다는 것은 실제로 실현 불가능한 것처럼 보일 수 있다. 그러나, 현대 암호화는 소프트웨어 또는 하드웨어에서 구현되며 다양한 범위의 애플리케이션에 사용된다. 많은 경우, 선택된 일반 텍스트 공격은 종종 매우 실현 가능하다(실무 중 참조). 선택된-일반 텍스트 공격은 암호화 키가 공개되어 공격자가 선택한 모든 일반 텍스트를 암호화할 수 있는 공개 키 암호화의 맥락에서 매우 중요해진다.

다른 형태

선택된 일반 텍스트 공격에는 두 가지 형태가 있다.

  • 상대방은 해당 암호문을 보기 전에 모든 일반 텍스트를 선택하는 배치 선택-일반 텍스트 공격. 이것은 종종 자격이 없을 때 "초젠-플레인텍스트 공격"에 의해 의도된 의미를 갖는다.
  • 적수가 일부 일반 텍스트에 대한 암호문을 본 후 추가 일반 텍스트의 암호문을 요청할 수 있는 CPA2(적응적 선택-일반 텍스트 공격).

공격의 일반적 방법

일반 일괄 선택-플레인텍스트 공격은 다음과[failed verification] 같이 수행된다.

  1. 공격자는 n개의 일반 텍스트를 선택할 수 있다. (이 매개변수 n은 공격 모델의 일부로 지정되며, 경계될 수도 있고 경계되지 않을 수도 있다.)
  2. 그런 다음 공격자는 이러한 n개의 일반 텍스트를 암호화 오라클로 전송한다.
  3. 그런 다음 암호화 오라클은 공격자의 일반 텍스트를 암호화하여 공격자에게 다시 전송한다.
  4. 공격자는 공격자가 각 일반 텍스트에 해당하는 암호 텍스트를 알 수 있도록 오라클에서 n개의 암호 텍스트를 다시 수신한다.
  5. 공격자는 플레인텍스트-시퍼텍스트 쌍에 기초해, 오라클이 플레인텍스트를 인코딩하는 데 사용하는 키를 추출해 시도할 수 있다. 이러한 유형의 공격의 공격자는 자신의 필요에 맞게 일반 텍스트를 자유롭게 조작할 수 있기 때문에 공격 복잡성이 줄어들 수 있다.

위의 상황의 다음 확장을 고려한다. 마지막 단계 이후,

  1. 상대는 두 개의 일반 텍스트를 출력한다. m0 그리고 m1.
  2. 조금 b 무작위 , 에서 균일하게 선택된다
  3. 상대방은 에 대한 암호화를 수신한다. m및 수신한 일반 텍스트를 "수정"하려고 시도하고, 비트를 출력한다b. b'.

위의 실험을 실행한 후 다음과 같은 경우, 암호는 선택된 일반 텍스트 공격 하에서 암호화를 구별할 수 없다. n=1[failed verification] 상대가 정확하게 추측할 수 없음(b=b'확률은 1/2보다 훨씬 더 높다.[3]

예

다음 예는 다른 보안 정의를 충족하는 일부 암호가 선택된 일반 텍스트 공격과 함께 어떻게 끊어질 수 있는지를 보여준다.

카이사르 암호

카이사르 암호에 대한 다음의 공격은 비밀키의 완전한 회복을 가능하게 한다.

  1. 상대방이 다음과 같은 메시지를 보낸다고 가정해 보십시오. Attack at dawn,
  2. 그리고 신탁이 돌아오다. Nggnpx ng qnja.
  3. 그러면 상대는 당신이 카이사르 암호를 해독하는 것과 같은 방법으로 열쇠를 되찾기 위해 끝까지 노력할 수 있다. 상대방은 대체 → , → 등을 추론할 수 있었다. 이로써 적군은 13이 카이사르 암호에 사용된 열쇠라는 판단을 내리게 될 것이다.

더 복잡하거나 복잡한 암호화 방법론을 사용할 경우 암호 해독 방법은 더 자원이 많이 소모되지만, 핵심 개념은 여전히 비교적 동일하다.

일회용 패드

다음의 일회용 패드에 대한 공격은 비밀키를 완전히 복구할 수 있게 한다. 메시지 길이 및 키 길이가 다음과 같다고 가정하십시오. n.

  1. 상대는 다음과 같이 구성된 끈을 보낸다. n 신탁에 영점을 찍다
  2. 오라클은 0의 문자열로 키의 비트 배타적 또는 배타적 키를 반환한다.
  3. 신탁이 돌려준 끈이 비밀키다.

일회용 패드는 이론적으로 안전한 암호 시스템의 예로서 사용되지만, 이 보안은 CPA 보안보다 약한 보안 정의에 따라 유지될 뿐이다. CPA 보안의 공식 정의에 따르면 암호화 오라클에는 상태가 없기 때문이다. 이 취약성은 모든 실제 구현에는 적용되지 않을 수 있다. 키 재사용을 피할 경우 1회용 패드를 여전히 안전하게 만들 수 있다("1회용" 패드"라는 이름을 사용함).

실제로

제2차 세계 대전에서 미국 해군 암호 분석가들은 일본이 "AF"라고 불리는 곳을 공격할 계획이라는 것을 발견했다. 그들은 "AF"가 미드웨이 섬일 수 있다고 믿었다. 왜냐하면 하와이 제도의 다른 곳에는 "A"로 시작하는 암호어들이 있었기 때문이다. 그들은 'AF'가 '미드웨이 아일랜드'에 해당한다는 가설을 증명하기 위해 미드웨이 주둔 미군에게 보급품 부족에 대한 간단한 문자 메시지를 보내줄 것을 요청했다. 일제는 이 메시지를 가로채 즉시 상부에 'AF'가 수심이 부족하다고 보고해 해군의 가설을 확인하고 전투 승리를 위해 병력을 배치할 수 있도록 했다.[3][4]

또한 제2차 세계 대전 동안, Blletchley Park의 연합군 코드브레이커들은 때때로 영국 공군에 독일 해군 시스템의 격자 참조에 어떠한 약어나 대안도 없는 위치에 기뢰를 깔아달라고 요청하곤 했다. 기뢰를 본 독일인들이 에니그마 기계를 이용해 지뢰에 대한 경고 메시지와 지뢰 제거 후 '전부 명확한' 메시지를 암호화해 동맹국들에게 독일 해군의 에니그마를 깨뜨릴 수 있는 충분한 정보를 제공해주길 바라는 것이었다. 알려진 평문을 심는 이러한 과정을 정원 가꾸기라고 불렀다.[5] 또한 연합군 코드브레이커들은 이중첩자 후안 푸졸 가르시아가 보낸 메시지를 제작하는데 도움을 주었는데, 이중첩자 후안 푸졸 가르시아가 마드리드에서 암호화된 무선 보고서를 수작업으로 해독하고 나서 베를린으로 전송하기 위해 에니그마 기계로 다시 암호화했다.[6] 이것은 코드브레이커들이 원문을 제공하면서 두 번째 레그에 사용된 코드를 해독하는데 도움을 주었다.[7]

현대에는 대칭 암호를 깨기 위해 선택된-일반 텍스트 공격(CPA)이 종종 사용된다. CPA-secure로 간주되려면 대칭 암호는 선택된 일반 텍스트 공격에 취약하지 않아야 한다. 따라서 대칭 암호 구현자는 공격자가 자신의 암호를 해독하고 관련 개선을 시도하는 방법을 이해하는 것이 중요하다.

선택한 일부 일반 텍스트 공격의 경우 공격자가 일반 텍스트의 일부만 선택할 필요가 있을 수 있으며, 이러한 공격은 일반 텍스트 주입 공격이라고 한다.

기타 공격과의 관계

선택된 일반 텍스트 공격은 알려진 일반 텍스트 공격보다 더 강력하다. 공격자가 특정 용어나 패턴이 자연스럽게 나타나기를 기다릴 필요 없이 직접 대상을 지정할 수 있기 때문에 암호 분석과 관련된 데이터의 수집이 더 빠를 수 있기 때문이다. 따라서 선택된 일반 텍스트 공격을 방지하는 모든 암호는 알려진 일반 텍스트와 암호 텍스트 전용 공격에도 안전하다.

그러나 선택된 일반 텍스트 공격은 공격자가 임의의 암호문들의 일반 텍스트를 얻을 수 있는 선택된 암호문 공격보다 덜 강력하다. CCA 공격자는 때때로 CPA 보안 시스템을 파괴할 수 있다.[3] 예를 들어, 엘 가말 암호는 선택된 일반 텍스트 공격에 대해 안전하지만, 무조건 악성이기 때문에 선택된 암호 텍스트 공격에 취약하다.

참조

  1. ^ Ross Anderson, 보안 엔지니어링: 신뢰할 수 있는 분산 시스템 구축 가이드. 초판(2001년): http://www.cl.cam.ac.uk/~rja14/book.properties
  2. ^ Barrera, John Fredy; Vargas, Carlos; Tebaldi, Myrian; Torroba, Roberto (2010-10-15). "Chosen-plaintext attack on a joint transform correlator encrypting system". Optics Communications. 283 (20): 3917–3921. Bibcode:2010OptCo.283.3917B. doi:10.1016/j.optcom.2010.06.009. ISSN 0030-4018.
  3. ^ a b c Katz, Jonathan; Lindell, Yehuda (2007). Introduction to Modern Cryptography: Principles and Protocols. Boca Raton: Chapman and Hall/CRC. ISBN 978-1584885511. OCLC 893721520.
  4. ^ Weadon, Patrick D. "How Cryptology enabled the United States to turn the tide in the Pacific War". www.navy.mil. US Navy. Archived from the original on 2015-01-31. Retrieved 2015-02-19.
  5. ^ Morris, Christopher (1993), "Navy Ultra's Poor Relations", in Hinsley, F.H.; Stripp, Alan (eds.), Codebreakers: The inside story of Bletchley Park, Oxford: Oxford University Press, p. 235, ISBN 978-0-19-280132-6
  6. ^ Kelly, Jon (27 January 2011). "The piece of paper that fooled Hitler". BBC. Retrieved 1 January 2012. The Nazis believed Pujol, whom they code named Alaric Arabel, was one of their prize assets
  7. ^ 수병 (2004년). "가르보가 무선 통신으로 독일군에 의해 부여된 첫 번째 코드는 현재 독일 서킷에서 사용되고 있는 것과 동일한 코드로 밝혀졌다.