원 타임 패드

3. 작동 원리

원 타임 패드는 메시지의 각 문자를 키(패드)의 문자와 결합하여 암호화한다. 일반적으로 모듈러 덧셈 방식이 사용된다. 예를 들어, A=0, B=1, ..., Z=25와 같이 각 문자에 숫자 값을 할당한다. 메시지 문자와 키 문자에 해당하는 숫자를 더하고, 그 결과값을 26으로 나눈 나머지를 취한다. 만약 결과값이 25보다 크면, 26을 뺀 나머지를 사용한다. 이는 계산 결과가 "Z"를 넘어가면, "A"부터 다시 시작한다는 것을 의미한다.^[17]

복호화는 암호화의 반대 과정이다. 암호문 각 문자의 숫자에서 키 각 문자의 숫자를 뺀다. 만약 결과값이 음수이면 26을 더해 양수로 만든다. 앨리스와 밥은 사용 직후 키 시트를 즉시 파기하여 재사용 및 암호 해독을 방지한다.^[17]

3. 1. 예시

• 암호화

• 복호화

모듈러 덧셈을 사용하여 키와 메시지를 결합한다. 앨리스는 메시지의 각 문자에 해당하는 숫자와 키의 각 문자에 해당하는 숫자를 더한다. 그 후, 더한 값이 25보다 크면 26을 뺀 나머지 값을 사용한다. 이렇게 만들어진 암호문 `EQNVZ`를 밥에게 보낸다.

밥은 암호문의 각 문자에 해당하는 숫자에서 키의 각 문자에 해당하는 숫자를 뺀다. 만약 뺀 값이 음수이면, 26을 더하여 양수로 만든다. 이 과정을 통해 밥은 앨리스의 원래 메시지 `hello`를 복원한다.^[17]

4. 특징

원 타임 패드는 정보 이론적으로 완벽한 보안(Perfect Secrecy)을 제공하는 암호화 방식이다. 즉, 암호문은 평문에 대한 어떠한 정보도 제공하지 않는다.^[4] 이를 위해 다음과 같은 특징을 가진다.

• 키의 무작위성: 키는 메시지와 길이가 같아야 하며, 진정한 무작위성을 가져야 한다. 이는 의사 난수가 아닌, 예측 불가능한 난수여야 함을 의미한다.^[18]
• 일회성: 키는 단 한 번만 사용해야 한다.^[18] 키가 재사용될 경우, 암호의 보안이 깨질 수 있다. 베노나 프로젝트는 소련이 원 타임 패드의 키를 재사용하여 해독에 성공한 대표적인 사례이다.
• 안전한 관리: 키는 안전하게 생성, 교환, 그리고 폐기되어야 한다.^[18] 키가 노출되면 암호문은 해독될 수 있다.

5. 문제점

섀넌의 보안 증명에도 불구하고, 일회용 패드는 실제 사용에 있어 다음과 같은 심각한 문제점을 안고 있다.

• 진정한 난수 생성의 어려움: '의사 난수'가 아닌 진정한 난수를 생성해야 하는데, 이는 매우 어려운 문제이다. 컴퓨터에서 난수 생성은 종종 어렵고, 대부분의 응용 프로그램에서는 속도와 유용성 때문에 의사 난수 생성기가 자주 사용된다. 진짜 난수 생성기도 존재하지만, 일반적으로 더 느리고 특수하다. 순수한 무작위성을 생성하는 기술의 예로는 방사성 붕괴를 측정하는 것이 있다.^[24]
• 키 분배 문제: 일회용 패드 값의 안전한 생성 및 교환이 필요하며, 이는 메시지 길이 이상이어야 한다. 일회용 패드의 보안은 일회용 패드 교환의 보안에 달려 있기 때문에 중요하다. 공격자가 일회용 패드 값을 가로챌 수 있다면, 일회용 패드를 사용하여 전송된 메시지를 해독할 수 있다.^[18]
• 키 관리의 어려움: 일회용 패드 값이 계속 비밀로 유지되고 재사용(부분적 또는 전체)을 방지하기 위해 올바르게 폐기될 수 있도록 주의해야 한다. 이것이 "일회용"이라는 의미이다. 데이터 잔류 문제는 컴퓨터 매체를 완전히 지우는 것을 어렵게 만들 수 있다.
• 메시지 인증 부재: 전통적으로 사용되는 일회용 패드는 메시지 인증을 제공하지 않으며, 이로 인한 부재는 실제 시스템에서 보안 위협을 야기할 수 있다. 예를 들어, 공격자가 메시지의 특정 부분 내용을 알고 있다면, 그 부분에 해당하는 패드의 코드를 직접 파생할 수 있다. 그런 다음 공격자는 해당 텍스트를 정확히 동일한 길이의 다른 텍스트로 바꿀 수 있다. 공격자가 알고 있는 일회용 패드는 이 바이트 길이에 제한되며, 이는 메시지의 다른 내용이 유효하게 유지되려면 유지되어야 한다. 이는 평문이 반드시 알려지지 않은 가변성^[26]과는 다르다. 메시지를 알지 못해도 공격자는 수신자가 이를 감지할 수 없도록 일회용 패드로 전송된 메시지의 비트를 뒤집을 수도 있다. 유사성 때문에 일회용 패드에 대한 공격은 스트림 암호에 대한 공격과 유사하다.^[27]

6. 활용

원 타임 패드는 컴퓨터 사용이 어렵거나 보안 유지가 극히 중요한 특수 환경에서 유용하게 활용된다.

• 스파이 통신 및 군사 작전: 스파이 통신이나 군사 작전과 같이 컴퓨터를 사용하기 어려운 환경에서 유용하다. 암호화 및 복호화 과정을 연필과 종이만으로도 수행할 수 있기 때문이다.
• 미소 핫라인 (1963년): 1963년 설치된 미국과 소련 간의 핫라인(미소 핫라인)에서 양국 간 암호화 기술 노출을 피하기 위해 사용되었다.^[11]
• 슈퍼 암호화(Superencipherment): 기존 암호 시스템의 보안 강화를 위해 사용될 수 있다. 1920년대 초 독일 암호학자들이 개발하였으며, 암호표를 사용해 숫자로 변환된 메시지에 비밀 숫자를 더하는 방식이다. 독일 외무부에서 1923년부터 사용되었다.^[11]
• 양자 키 분배(Quantum Key Distribution, QKD): 양자 암호 프로토콜 (예: BB84)과 결합하여, 사전에 비밀 정보를 공유하지 않고도 안전한 통신을 가능하게 한다.
• 기타:
• 숫자 방송은 종종 원 타임 패드로 암호화된 메시지를 보내는 경우가 있다.^[2]
• 통신량과 동일한 길이의 난수열을 사용하고, 날짜별로 1회 사용한 난수표는 폐기하는 방식으로, 환자표나 코드북은 공지된 것을 사용해도 된다는 장점이 있다.^[2]

• 키 자료 관리: 키 자료는 안전하게 전달, 보관 및 폐기되어야 한다. 그렇지 않으면 키 자료 재사용으로 인해 메시지가 위험에 노출될 수 있다.^[2]
• 메시지 인증 부재: 원 타임 패드는 메시지 인증 기능을 제공하지 않아 보안 위협이 발생할 수 있다. 공격자가 메시지 내용을 일부 안다면, 해당 부분을 변경하여 위조 메시지를 만들 수 있다.

6. 1. 양자 암호와의 관계

7. 한계점 및 보완

원 타임 패드는 이론적으로 완벽한 보안을 제공하지만, 실제 사용에는 몇 가지 한계점이 존재한다.

• 난수 생성 및 전달: 방대한 양의 진정한 난수를 만들고 안전하게 전달하는 과정은 어렵고 비용이 많이 든다. 특히 적대적인 환경에서는 더욱 그렇다.
• 관리 문제: 난수표를 안전하게 보관하고 올바른 순서대로 사용하는 것은 어려우며, 분실, 탈취, 손상의 위험도 있다.
• 재사용 위험: 난수표는 한 번만 사용해야 하지만, 현실적인 제약으로 재사용될 위험이 있다.
• 인적 오류: 암호화 및 해독 과정에서 사람의 실수로 오류가 발생할 수 있다.

• 난수 생성기: 물리적 난수 생성기나 암호학적으로 안전한 의사 난수 생성기를 사용하여 난수 생성을 효율적으로 할 수 있다.
• 안전한 통신 채널: 양자 암호 통신과 같이 도청이 불가능한 통신 채널을 사용하여 난수표를 전달할 수 있다.
• 관리 시스템: 난수표를 디지털화하여 안전하게 보관하고 자동으로 관리하는 시스템을 구축할 수 있다.
• 교육 및 훈련: 통신원에게 난수표 사용법을 철저히 교육하고 훈련하여 인적 오류를 줄일 수 있다.

7. 1. 베노나 프로젝트

참조

_[1] 간행물 One-Time Pad Springer Nature Switzerland 2023
_[2] 웹사이트 Intro to Numbers Stations http://www.numbers-s[...] 2014-09-13
_[3] 웹사이트 One-Time Pad (OTP) http://www.cryptomus[...] Cryptomuseum.com 2014-03-17
_[4] 논문 Communication Theory of Secrecy Systems https://www.cs.virgi[...]
_[5] Wikisource Telegraphic Code to Insure Privacy and Secrecy in the Transmission of Telegrams 1882
_[6] 논문 Frank Miller: Inventor of the One-Time Pad https://academiccomm[...]
_[7] 웹사이트 'Secret signaling system patent' on Google.Com https://patents.goog[...] 2016-02-03
_[8] 서적 The Codebreakers Macmillan
_[9] 웹사이트 One-Time-Pad (Vernam's Cipher) Frequently Asked Questions, with photo http://www.ranum.com[...] 2006-05-12
_[10] 웹사이트 Chiffriergerätebau : One-Time-Pad, with photo https://www.cipherma[...] 2006-07-24
_[11] 서적 The Codebreakers Macmillan
_[12] 뉴스 Codebook Shows an Encryption Form Dates Back to Telegraphs https://www.nytimes.[...] 2011-07-25
_[13] 논문 One-time-pad cipher algorithm based on confusion mapping and DNA storage technology 2021-01-20
_[14] 서적 Between Silk and Cyanide: a Codemaker's Story, 1941–1945 https://archive.org/[...] HarperCollins
_[15] 논문 Quantum cryptography and V A Kotel'nikov's one-time key and sampling theorems http://www.turpion.o[...] 2006-02-22
_[16] arXiv Private Quantum Channels and the Cost of Randomizing Quantum Information 2000-03-27
_[17] 서적 Spycraft: The Secret History of the CIA's Spytechs, from Communism to al-Qaeda https://archive.org/[...] Dutton
_[18] 웹사이트 One-Time Pads http://www.schneier.[...]
_[19] 문서 The actual length of a plaintext message can hidden by the addition of extraneous parts, called [[Padding (cryptography)|padding]]. For instance, a 21-character ciphertext could conceal a 5-character message with some padding convention (e.g. "-PADDING- HELLO -XYZ-") as much as an actual 21-character message: an observer can thus only deduce the maximum possible length of the significant text, not its exact length.
_[20] 논문 Communication Theory of Secrecy Systems http://www3.alcatel-[...] 2011-12-21
_[21] 문서 That is to say, the "'''information gain'''" or [[Kullback–Leibler divergence]] of the plaintext message from the ciphertext message is zero.
_[22] 문서 Most asymmetric encryption algorithms rely on the facts that the best known algorithms for prime factorization and computing discrete logarithms are superpolynomial time. There is a strong belief that these problems are not solvable by a Turing machine in time that scales polynomially with input length, rendering them difficult (hopefully, prohibitively so) to be broken via cryptographic attacks. However, this has not been proven.
_[23] 서적 The Block Cipher Companion https://books.google[...] Springer Science & Business Media 2017-07-26
_[24] 서적 The Code Book https://archive.org/[...] Anchor Books
_[25] 뉴스 The Translations and KGB Cryptographic Systems http://www.nsa.gov/a[...] National Security Agency 2009-05-03
_[26] 서적 Information Theoretic Security: Third International Conference, ICITS 2008, Calgary, Canada, August 10–13, 2008, Proceedings https://books.google[...] Springer Science & Business Media
_[27] 웹사이트 Attacks on Stream Ciphers and The One Time Pad - Course overview and stream ciphers https://www.coursera[...] 2022-03-21
_[28] 문서 A "way to combine multiple block algorithms" so that "a cryptanalyst must break both algorithms" in §15.8 of ''Applied Cryptography, Second Edition: Protocols, Algorithms, and Source Code in C'' by Bruce Schneier. Wiley Computer Publishing, John Wiley & Sons, Inc.
_[29] 논문 Quantum cryptography: Public key distribution and coin tossing 1984
_[30] 논문 Generalized beam-splitting attack in quantum cryptography with dim coherent states https://www.scienced[...] 1999-10-01
_[31] 논문 Quantum Cryptography II: How to re-use a one-time pad safely even if P=NP 2014
_[32] 서적 The Codebreakers Macmillan
_[33] 뉴스 Stasi Sprach Morse Machine http://www.numbers-s[...] The Numbers Stations Research and Information Center 2015-03-01
_[34] 웹사이트 National Security Agency {{!}} Central Security Service > About Us > Cryptologic Heritage > Historical Figures and Publications > Publications > WWII > Sigsaly Story https://www.nsa.gov/[...] 2022-03-27
_[35] 서적 The Codebreakers Macmillan
_[36] 논문 Cryptology during the French and American Wars in Vietnam https://eprint.iacr.[...] 2020-04-14
_[37] 웹사이트 Operation Vula: a secret Dutch network against apartheid http://www.radioneth[...] 1999-09-09
_[38] 논문 Talking to Vula: The Story of the Secret Underground Communications Network of Operation Vula http://www.anc.org.z[...] 2014-08-24
_[39] 서적 The Secret Wireless War – The story of MI6 Communications 1939-1945 UPSO Ltd
_[40] 웹사이트 What do all those hand signals mean? Inside the hidden language of baseball and softball https://www.wausauda[...] 2024-06-14
_[41] 서적 A History of U.S. Communications Security; the David G. Boak Lectures, Vol. I https://www.governme[...] U.S. National Security Agency 1973-07
_[42] 웹사이트 Securing Record Communications: The TSEC/KW-26 http://www.nsa.gov/p[...] NSA 2006-05-12
_[43] 간행물 Enigma's Security: What the Germans Really Knew
_[44] 뉴스 The Venona Translations http://www.nsa.gov/a[...] National Security Agency 2009-05-03
_[45] 간행물 Communication Theory of Secrecy Systems
_[46] 간행물 One-Time Pad https://doi.org/10.1[...] Springer Nature Switzerland 2023-09-12