원타임패드

이 기사의 리드 섹션에는 기사의 다른 부분에 포함되지 않은 정보가 포함되어 있습니다. 리드 개선을 도와주시기 바랍니다. (2023년 5월) (이 템플릿 메시지를 제거하는 방법과 시기에 대해 알아봅니다)

암호학에서 OTP(One-Time Pad)는 암호화 기법으로, 크래킹할 수는 없지만, 전송되는 메시지의 크기 이상의 단일 사용 사전 공유 키를 사용해야 합니다. 이 기법에서 평문은 임의 비밀 키(일회성 패드라고도 함)와 쌍을 이룹니다. 그런 다음 모듈식 덧셈을 사용하여 평문의 각 비트 또는 문자를 패드에서 해당 비트 또는 문자와 결합하여 암호화합니다.^[1]

다음과 같은 네 가지 조건이 충족되면 암호문을 해독하거나 해독할 수 없습니다.^[2][3]

1. 키는 적어도 일반 텍스트만큼 길어야 합니다.
2. Gregory Chaitin 정의에 따르면, 키는 무작위(가능한 모든 키 집합에 균일하게 분포되고 평문과 무관함)여야 하며, 하드웨어 난수 생성기와 같은 비알고리즘적이고 혼란스러운 소스에서 전체적으로 샘플링됩니다.^[4] 이러한 테스트는 엔트로피를 측정할 수 없으므로 OTP 키가 통계적 무작위성 테스트를 통과하기에는 충분하지 않으며, 엔트로피의 비트 수는 적어도 평문의 비트 수와 같아야 합니다. 예를 들어, 암호화 해시나 수학 함수(로그나 제곱근 등)를 사용하여 더 적은 수의 엔트로피로부터 키를 생성하는 것은 균일한 분배 요구사항을 깨뜨릴 것이므로 완벽한 비밀성을 제공하지 못할 것입니다.
3. 키는 전체 또는 부분적으로 재사용해서는 안 됩니다.
4. 키는 통신 당사자가 완전히 비밀로 해야 합니다.

완벽한 비밀성을 가진 암호는 OTP 키와 사실상 동일한 요구 사항을 가진 키를 사용해야 한다는 것이 수학적으로도 증명되었습니다.^[5] 일회용 암호의 디지털 버전은 중요한 외교 및 군사 통신을 위해 국가에서 사용되어 왔지만 안전한 키 배포의 문제로 인해 대부분의 응용 프로그램에서 사용할 수 없습니다.

1882년 프랭크 밀러에 의해 처음으로 ^[6][7]기술된 일회용 패드는 1917년에 다시 발명되었습니다. 1919년 7월 22일, 일회용 패드의 암호화에 사용되는 XOR 연산에 대한 미국 특허 1,310,719가 Gilbert Vernam에게 발행되었습니다.^[8] 그의 버넘 암호에서 파생된 이 시스템은 펀칭 테이프에서 읽은 키와 메시지를 결합한 암호였습니다. 원래 형태에서는 키 테이프가 루프였기 때문에 루프가 전체 사이클을 만들 때마다 재사용되었기 때문에 베르남의 시스템은 취약했습니다. 1회용은 나중에 조셉 모보르네가 키 테이프가 완전히 무작위적이라면 암호 분석이 불가능하다는 것을 인식했을 때 사용되었습니다.^[9]

이름의 "패드" 부분은 초기 구현에서 핵심 재료를 종이 패드로 배포하여 사용 후 현재의 상단 시트를 뜯고 파괴할 수 있도록 한 것에서 비롯되었습니다. 은폐를 위해 패드가 때때로 너무 작아서 그것을 사용하기 위해서는 강력한 돋보기가 필요했습니다. KGB는 손바닥이나 ^[10]호두 껍질에 들어갈 수 있는 크기의 패드를 사용했습니다.^[11] 보안을 강화하기 위해 일회용 패드를 인화성이 높은 니트로셀룰로오스 시트에 인쇄하여 사용 후 쉽게 태울 수 있도록 했습니다.

"버남 암호"라는 용어에 모호한 점이 있습니다. 왜냐하면 어떤 자료들은 "버남 암호"와 "일회용 패드"를 동의어로 사용하는 반면, 어떤 자료들은 추가 스트림 암호를 "버남 암호"로 언급하는데, 여기에는 암호학적으로 안전한 의사난수 생성기(CSPRNG)를 기반으로 한 것들도 포함됩니다.^[12]

역사

1882년 프랭크 밀러는 전신 보안을 위한 일회용 패드 시스템을 최초로 설명했습니다.^[7][13]

다음 1회용 패드 시스템은 전기식이었습니다. 1917년 (AT&T Corporation의) Gilbert Vernam은 텔레프린터 기술을 기반으로 한 암호를 발명하고^[14] 이후 1919년 (미국 특허 1,310,719) 특허를 받았습니다. 메시지의 각 문자는 펀칭된 종이 테이프 키의 문자와 전기적으로 결합되었습니다. 조셉 모보르네(당시 미 육군 대위이자 후에 신호군단장)는 키 테이프의 문자 순서가 완전히 무작위적일 수 있으며, 만약 그렇다면 암호 분석이 더 어려울 것이라는 것을 인식했습니다. 그들은 함께 최초의 일회용 테이프 시스템을 발명했습니다.^[12]

다음 개발은 종이 패드 시스템이었습니다. 외교관들은 기밀 유지와 전신 비용을 최소화하기 위해 오랫동안 코드와 암호를 사용했습니다. 코드의 경우 단어와 구문은 사전과 유사한 코드북을 사용하여 숫자 그룹(일반적으로 4자리 또는 5자리)으로 변환되었습니다. 보안을 강화하기 위해 비밀번호는 전송 전에 각 코드 그룹과 결합(보통 모듈식 덧셈)할 수 있으며 비밀번호는 주기적으로 변경됩니다(이를 초암호화라고 합니다). 1920년대 초, 그러한 체계들을 깨는데 관여했던 세 명의 독일 암호학자들(베르너 쿤제, 루돌프 쇼플러, 에리히 랑글로츠)은 만약 임의로 선택된 별도의 가산수를 모든 코드 그룹에 사용한다면 그것들은 결코 깨질 수 없다는 것을 깨달았습니다. 그들은 난수 그룹의 선으로 인쇄된 중복 종이 패드를 가지고 있었습니다. 각 페이지에는 일련 번호와 8줄이 있었습니다. 각 줄에는 6개의 5자리 숫자가 있었습니다. 페이지는 메시지를 인코딩하는 작업 시트로 사용된 후 삭제됩니다. 페이지의 일련 번호는 인코딩된 메시지와 함께 전송됩니다. 수신자는 절차를 되돌린 다음 페이지 복사본을 삭제합니다. 독일 외무부는 1923년까지 이 시스템을 가동시켰습니다.^[12]

별도의 개념은 1회 문자 패드를 사용하여 아래의 예제와 같이 직접 평문을 인코딩하는 것이었습니다. 레오 마크스(Leo Marks)는 제2차 세계 대전 당시 영국 특수 작전 집행부를 위해 이러한 시스템을 발명한 것에 대해 설명하지만, 당시에는 블레츨리 파크(Bletchley Park)와 같이 매우 구획화된 암호학의 세계에 이미 알려져 있다고 의심했습니다.^[15]

최종적인 발견은 1940년대 정보 이론가 클로드 섀넌에 의해 이루어졌는데, 그는 일회용 패드 시스템의 이론적 중요성을 인식하고 증명했습니다. 섀넌은 1945년에 기밀 보고서를 통해 그의 결과를 전달했고 1949년에 공개적으로 발표했습니다.^[5] 동시에 소련의 정보 이론가 블라디미르 코텔니코프는 독자적으로 일회성 패드의 절대적인 안전성을 입증했으며, 그의 결과는 1941년에 기밀로 남아있는 것으로 보이는 보고서를 통해 전달되었습니다.^[16]

예

앨리스가 메시지를 보내기를 원한다고 가정해 보겠습니다. hello 밥에게. 동일한 무작위 문자 시퀀스를 포함하는 두 장의 용지가 이전에 생성되어 양쪽 모두에게 안전하게 발행되었다고 가정합니다. 앨리스는 패드에서 사용하지 않는 페이지를 선택합니다. 이를 수행하는 방법은 일반적으로 "5월 1일 12번째 시트 사용" 또는 "다음 메시지를 위해 사용 가능한 다음 시트 사용"과 같이 사전에 준비됩니다.

선택한 시트의 자료가 이 메시지의 핵심입니다. 패드의 각 문자는 메시지의 한 문자와 미리 지정된 방식으로 결합됩니다. (예를 들어, 각 문자에 숫자 값을 할당하는 것은 일반적이지만 필수는 아닙니다. a 0입니다. b 1 등입니다.)

이 예에서 기술은 Vigenère 암호와 달리 모듈식 덧셈을 사용하여 키와 메시지를 결합하는 것입니다. 해당 메시지와 키 문자의 수치를 합산한 모듈로 26. 그래서, 만약 핵심 자료가 다음과 같이 시작한다면, XMCKL 그리고 메시지는 hello, 그러면 코딩은 다음과 같이 수행됩니다.

      hello message 7 (h) 4 (e) 11 (l) 11 (o) 14 (o) message + 23 (X) 12 (M) 2 (K) 11 (L) key = 30 16 13 2125 message + key = 4 (E) 16 (Q) 13 (N) 21 (V) 25 (Z) (message + key) mod 26 E Q N V Z → 암호문 

숫자가 25보다 크면 26을 뺀 나머지는 모듈식 산술 방식으로 계산됩니다. 이것은 단순히 계산이 Z를 "지나간다"는 것을 의미하며, 시퀀스는 A에서 다시 시작됩니다.

Bob에게 보낼 암호문은 다음과 같습니다. EQNVZ. Bob은 일치하는 키 페이지와 동일한 프로세스를 사용하지만, 반대로 평문을 얻기 위해 사용합니다. 여기서 키는 다시 모듈 연산을 사용하여 암호문에서 차감됩니다.

       EQ N V Z 암호문 4 (E) 16 (Q) 13 (N) 21 (V) 25 (Z) 암호문 - 23 (X) 12 (M) 2 (C) 10 (K) 11 (L) 키 = -19 4 (h) 4 (L) 11 (L) 14 (o) 암호문 – key (mod 26) hel lo → message 

위와 유사하게 숫자가 음수이면 26을 더해서 숫자를 0 이상으로 만듭니다.

그래서 밥은 앨리스의 평문인 메시지를 복구합니다. hello. Alice와 Bob 모두 사용 즉시 키시트를 파괴하여 재사용 및 암호에 대한 공격을 방지합니다. KGB는 종종 작은 플래시 종이에 인쇄된 일회용 패드를 발행했는데, 이 패드는 화학적으로 니트로셀룰로오스로 변환된 종이로 거의 즉시 연소되고 재가 남지 않습니다.^[17]

고전적인 일회용 스파이 행위는 실제 패드가 미세하고 쉽게 감춰진 종이, 날카로운 연필, 약간의 암산을 사용했습니다. 이 방법은 이제 데이터 파일을 입력(평문), 출력(암호문) 및 키 자료(필요한 랜덤 시퀀스)로 사용하여 소프트웨어 프로그램으로 구현할 수 있습니다. 배타적 또는 (XOR) 연산은 평문과 주요 요소를 결합하는 데 자주 사용되며, 컴퓨터에서 특히 매력적인데, 이는 일반적으로 기본 기계 명령어이기 때문에 매우 빠르기 때문입니다. 그러나 핵심 소재가 실제로는 무작위로 사용되고, 한 번만 사용되고, 반대 측에 알려지는 경우가 없으며, 사용 후 완전히 파괴된다는 것을 보장하기는 어렵습니다. 소프트웨어 일회용 패드 구현의 보조적인 부분들은 일반 텍스트의 안전한 취급/전송, 진정한 무작위 키, 그리고 키의 일회적인 사용이라는 현실적인 과제를 제시합니다.

암호 분석 시도

위의 예를 계속하려면 Eve가 Alice의 암호문을 가로챈다고 가정합니다. EQNVZ. 만약 이브가 가능한 모든 열쇠를 시도했다면, 그녀는 그 열쇠를 발견했을 것입니다. XMCKL 일반 텍스트를 생성할 수 있습니다. hello, 하지만 그녀는 그 열쇠를 발견했을 것입니다. TQURI 일반 텍스트를 생성할 수 있습니다. later, 똑같이 그럴듯한 메시지:

    4 (E) 16 (Q) 13 (N) 21 (V) 25 (Z) 암호문 - 19 (T) 16 (Q) 20 (U) 17 (R) 8 (I) 가능 키 = -150 - 7 4 17 암호문-키 = 11 (l) 0 (a) 19 (t) 17 (r) 암호문-키 (mod 26) 

사실, 단순히 다른 키를 사용하는 것만으로 같은 수의 문자를 가진 어떤 메시지도 암호문에서 "암호 해독"할 수 있고, 암호문에는 이브가 암호문의 다양한 판독값 중에서 선택할 수 있는 정보가 없습니다.^[18]

키가 정말로 무작위적이지 않은 경우, 통계 분석을 사용하여 그럴듯한 키 중 "최소" 무작위를 결정할 수 있으며 따라서 올바른 키가 될 가능성이 더 높습니다. 키를 재사용하면 두 암호문 모두에서 감각적인 평문을 생성하는 유일한 키가 눈에 띄게 됩니다(일부 임의의 잘못된 키가 두 개의 감각적인 평문을 생성할 가능성은 매우 낮습니다).

완벽한 비밀

일회성 패드는 암호화된 메시지(즉, 암호문)가 암호 분석가에게 원본 메시지에 대한 정보를 제공하지 않는다는 점에서 "정보 이론적으로 안전"합니다(가능한 최대 길이의^{[note 1]} 메시지는 제외). 이것은 클로드 섀넌이 제2차 세계대전 중 처음 개발한 매우 강력한 보안 개념으로 수학적으로 거의 동시에 섀넌의 일회성 패드에도 사실임을 증명했습니다. 그의 결과는 1949년 벨 시스템 기술 저널에 발표되었습니다.^[19] 적절하게 사용하면 무한한 계산력을 가진 적들에 대해서도 이러한 의미에서 일회용 패드가 안전합니다.

Shannon은 정보 이론적 고찰을 통해 일회성 패드가 그가 완전한 비밀이라고 부르는 속성을 가지고 있다는 것을 증명했습니다. 즉 암호문 C는 평문에 대한 추가 정보를 전혀 제공하지 않습니다.^{[note 2]} 이것은 (직관적으로) 한 번만 사용되는 정말로 균일한 무작위 키가 주어지면, 암호문은 같은 길이의 임의의 평문으로 번역될 수 있고, 모든 것이 똑같이 가능하기 때문입니다. 따라서 평문 메시지 M의 선험적 확률은 해당 암호문이 주어진 평문 메시지 M의 선험적 확률과 같습니다.

기존의 대칭 암호 알고리즘은 치환과 전치의 복잡한 패턴을 사용합니다. 현재 사용 중인 이 중 가장 좋은 것은 암호화 중에 사용되는 키를 알지 못한 채 이러한 변환을 효율적으로 되돌릴 수 있는 암호 분석 절차가 있을 수 있는지 여부입니다. 비대칭 암호화 알고리즘은 정수 인수분해나 이산 로그와 같이 풀기 어려울 것으로 생각되는 수학 문제에 의존합니다. 그러나 이러한 문제들이 어렵다는 증거는 없으며, 수학적인 돌파구는 기존 시스템을 공격에 취약하게 만들 수 있습니다.^{[note 3]}

기존의 대칭 암호화와 달리 완벽한 비밀성을 제공하는 일회성 패드는 단순한 공격에도 무방비 상태입니다. 모든 키를 시도하면 모든 평문이 생성되며, 모두 실제 평문이 될 가능성이 동일합니다. 부분적으로 알려진 평문이라도 공격자가 나머지 메시지를 해독하는 데 필요한 키 부분에 대한 정보를 얻을 수 없기 때문에 단순 공격은 사용할 수 없습니다. 평문에서 알려진 부분들은 그들에 대응하는 키의 부분들만 드러낼 것이고, 그것들은 엄격하게 일대일로 대응할 것이고, 균일하게 무작위한 키의 비트들은 독립적일 것입니다.

Peter Shor 등은 양자 컴퓨터가 기존의 비대칭 암호 알고리즘의 보안이 좌우하는 몇 가지 문제를 해결하는 데 훨씬 더 빠르다는 것을 보여주었습니다. 이런 문제들의 난이도에 따라 달라지는 암호 알고리즘들은 충분히 강력한 양자 컴퓨터로 쓸모없게 될 것입니다. 그러나 완벽한 보안은 공격자의 계산 리소스에 대한 가정에 의존하지 않기 때문에 일회성 패드는 안전하게 유지됩니다. 양자 암호학과 양자 후 암호학은 양자 컴퓨터가 정보 보안에 미치는 영향을 연구하는 것을 포함합니다.

문제

Shannon의 보안 증명에도 불구하고 일회용 패드는 다음과 같은 사항이 필요하기 때문에 실제로는 심각한 단점이 있습니다.

• 사소하지 않은 요구 사항인 의사 랜덤, 일회용 패드 값과 달리 진정한 랜덤입니다. 컴퓨터에서 난수 생성은 종종 어렵고, 의사 난수 생성기는 대부분의 응용 분야에서 속도와 유용성을 위해 자주 사용됩니다. 실제 난수 생성기는 존재하지만 일반적으로 더 느리고 더 전문적입니다.
• 최소한 메시지만큼 길어야 하는 일회성 패드 값을 안전하게 생성하고 교환합니다. 일회용 패드의 보안은 일회용 패드 교환의 보안에 달려 있기 때문에 중요합니다. 공격자가 일회성 패드 값을 가로챌 수 있는 경우 일회성 패드를 사용하여 보낸 메시지를 해독할 수 있습니다.^[18]
• 일회용 패드 값이 계속 비밀로 유지되고 올바르게 폐기되어 재사용(부분적 또는 전체적)을 방지할 수 있도록 세심한 처리가 필요합니다. 따라서 "일회용"입니다. 데이터 유지에 문제가 생기면 컴퓨터 매체를 완전히 지우는 것이 어려워질 수 있습니다.

일회용 패드는 현재 암호학에서 실제적인 문제를 거의 해결하지 못합니다. 고품질 암호는 널리 사용할 수 있으며 보안은 현재 큰 문제로 간주되지 않습니다.^[20] 이와 같은 암호는 적절하고 안전하게 생성, 배포 및 보관해야 하는 핵심 재료의 양이 훨씬 적기 때문에 일회용 패드보다 거의 항상 사용하기 쉽습니다.^[18] 또한 공개 키 암호화는 키 배포의 문제를 극복합니다.

참무작위

고품질 난수는 생성하기가 어렵습니다. 대부분의 프로그래밍 언어 라이브러리에 있는 난수 생성 함수는 암호화 사용에 적합하지 않습니다. /dev/random 및 많은 하드웨어 난수 생성기를 포함하여 정상적인 암호화 사용에 적합한 생성기라도 보안이 입증되지 않은 암호화 기능을 일부 사용할 수 있습니다. 순수 무작위성을 생성하는 기술의 한 예로 방사능 방출량을 측정하는 것이 있습니다.^[21]

특히 1회 사용이 절대적으로 필요합니다. 예를 들어, $p{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\$ 및 $p{\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\$가 두 개의 별개의 평문 메시지를 나타내고$$ 각각 공통 키 $k{\displaystyle }$ ${\displaystyle k}$에 의해 암호화되면$$각각의 암호문은 다음과 같이 제공됩니다.

${\displaystyle c_{1}=p_{1}\opluxk}$

${\displaystyle c_{2}=p_{2}\opluxk}$

$여기서$⊕ ${\displaystyle$\opplus}은(는) XOR을 의미합니다. If an attacker were to have both ciphertexts ${\displaystyle c_{1}}$ and ${\displaystyle c_{2}}$, then simply taking the XOR of ${\displaystyle c_{1}}$ and ${\displaystyle c_{2}}$ yields the XOR of the two plaintexts ${\displaystyle p_{1}\oplus p_{2}}$. (이는 공통 $키$ k ${\displaystyle$ k$}$의 XOR을 사용하면 0의 비트스트림이 일정하게 생성되기 때문입니다.) p ${\displaystyle 1_{}}$ ⊕ p 2 {\$displaystyle p_{1}\opplus$p_{2}}는 실행 중인 키 암호와 동등합니다.

두 평문이 모두 자연어(예: 영어 또는 러시아어)인 경우, 각각은 몇 가지 모호성을 가지고 휴리스틱 암호 분석을 통해 복구될 가능성이 매우 높습니다. 물론, 더 짧은 메시지와 겹치는 부분에 대해서만 더 긴 메시지가 깨질 수 있고, 단어나 구를 완성함으로써 더 많은 메시지가 될 수 있습니다. 이 취약성의 가장 유명한 악용은 Venona 프로젝트에서 발생했습니다.^[22]

키분포

모든 공유된 비밀과 마찬가지로 패드를 전달하고 안전하게 유지해야 하며, 적어도 메시지만큼의 길이를 가져야 하기 때문에 패드 대신 일반 텍스트를 간단히 전송할 수 있으므로 일회성 패딩을 사용하는 것은 의미가 없는 경우가 많습니다(둘 다 동일한 크기일 수 있고 안전하게 전송해야 함).^[18] 그러나 매우 긴 패드가 안전하게 전송되면(예: 랜덤 데이터로 가득 찬 컴퓨터 디스크), 메시지 크기의 합이 패드 크기와 동일해질 때까지 향후 수많은 메시지에 사용할 수 있습니다. 양자 키 분배는 또한 고장에 강한 양자 컴퓨터를 가정하여 이 문제에 대한 해결책을 제시합니다.

매우 긴 일회용 패드 키를 배포하는 것은 불편하고 일반적으로 상당한 보안 위험을 초래합니다.^[2] 패드는 본질적으로 암호키이지만 현대 암호키와는 달리 길이가 엄청나게 길고 인간이 기억하기에는 너무 어려운 것임에 틀림없습니다. 엄지 드라이브, DVD-Rs 또는 개인용 디지털 오디오 플레이어와 같은 저장 매체를 사용하여 의심스럽지 않은 방식으로 매우 큰 1회용 패드를 장소에서 장소로 운반할 수 있지만, 최신 공개 키 암호 시스템의 주요 협상 프로토콜과 비교할 때 패드를 물리적으로 운반해야 하는 것은 부담이 됩니다. 이러한 매체는 물리적 파괴(예: 소각)가 없는 한 어떠한 방법으로도 안전하게 지워질 수 없습니다. 1회 패드 데이터로 가득 찬 4.7GB DVD-R은 1mm²(0.0016 sqin) 크기의 입자로 파쇄되면 각 입자에 4메가비트 이상의 데이터를 남깁니다.^{[citation needed]} 또한 운송 중에 발생하는 손상 위험(예: 소매치기가 패드를 스와이핑, 복사 및 교체)은 AES와 같은 암호가 손상될 가능성보다 실제적으로 훨씬 더 클 수 있습니다. 마지막으로, 일회용 패드 키 자료를 관리하는 데 필요한 노력은 대규모 통신 네트워크에서 매우 심하게 확장됩니다. 즉, 필요한 패드 수는 자유롭게 메시지를 교환하는 사용자 수의 제곱에 따라 증가합니다. 두 사람 사이의 통신 또는 스타 네트워크 토폴로지의 경우 이는 덜 문제가 됩니다.

키 자료는 사용 후 안전하게 폐기해야 하며, 키 자료가 재사용되지 않도록 하고 발송된 메시지를 보호해야 합니다.^[2] 핵심 자료는 한 엔드포인트에서 다른 엔드포인트로 전송되어야 하며 메시지가 전송되거나 수신될 때까지 지속되기 때문에 데이터가 남아 있을 수 있기 때문에 보호하는 일시적인 평문보다 포렌식 복구에 더 취약할 수 있습니다.

인증

전통적으로 사용되는 것처럼 일회용 패드는 메시지 인증을 제공하지 않으며, 메시지가 부족할 경우 실제 시스템에서 보안 위협이 될 수 있습니다. 예를 들어, 메시지에 "내일 오후 3시 30분에 제인과 나를 만나다"라는 내용이 포함되어 있음을 알고 있는 공격자는 알려진 두 요소(암호화된 텍스트와 알려진 평문)에서 직접 패드의 해당 코드를 도출할 수 있습니다. 그런 다음 공격자는 해당 텍스트를 "삼십 회의가 취소되었습니다, 집에 머무르십시오"와 같이 정확히 동일한 길이의 다른 텍스트로 대체할 수 있습니다. 공격자가 1회용 패드에 대해 아는 것은 이 바이트 길이로 제한되며, 이 바이트 길이는 메시지의 다른 내용이 유효하게 유지되도록 유지되어야 합니다. 이것은 평문이 반드시 알려져 있지 않은 가단성과는^[23] 다릅니다. 공격자는 메시지를 알지 못한 채 일회성 패드로 전송된 메시지의 비트를 뒤집을 수도 있으며 수신자가 이를 감지할 수 없습니다. 유사성 때문에 일회성 패드에 대한 공격은 스트림 암호에 대한 공격과 유사합니다.^[24]

메시지 인증 코드 사용과 같은 이를 방지하기 위한 표준 기술은 가변 길이 패딩이나 러시아어 코플레이션과 같은 고전적인 방법과 마찬가지로 일회성 패드 시스템과 함께 사용할 수 있지만 모두 OTP 자체가 가지고 있는 완벽한 보안이 부족합니다. 범용 해시는 임의의 보안 경계까지 메시지를 인증할 수 있는 방법을 제공합니다(즉, 임의의 p > 0의 경우, 충분히 큰 해시는 계산에 제한되지 않은 공격자의 위변조 성공 가능성도 p 미만임을 보장합니다). 그러나 이는 패드의 추가 랜덤 데이터를 사용합니다. 그리고 이러한 기술 중 일부는 컴퓨터 없이 시스템을 구현할 수 있는 가능성을 제거합니다.

공통 구현 오류

구현이 비교적 단순하고 완벽한 비밀 보장을 약속하기 때문에 원타임 패드는 특히 강좌 중에 처음으로 제시되고 구현되는 알고리즘이기 때문에 암호학에 대해 배우는 학생들 사이에서 높은 인기를 누리고 있습니다. 이러한 "최초" 구현은 종종 한 가지 이상의 방법으로 정보 이론적 보안에 대한 요구사항을 위반합니다.

• 패드는 하나 이상의 작은 값을 더 긴 "일회성 패드"로 확장하는 알고리즘을 통해 생성됩니다. 이는 제곱근 십진법 확장과 같은 불안정한 기본 수학 연산부터 복잡하고 암호학적으로 안전한 의사 난수 생성기(CSPRNG)에 이르기까지 모든 알고리즘에 동일하게 적용됩니다. 이러한 구현 중 어느 것도 일회용 패드가 아니라 정의에 따라 스트림 암호입니다. 모든 일회성 패드는 하드웨어 난수 생성기와 같은 비알고리즘 프로세스에 의해 생성되어야 합니다.
• 패드는 비정보 이론적으로 안전한 방법을 사용하여 교환됩니다. 일회성 패드가 전달을 위해 비정보 이론적으로 안전한 알고리즘으로 암호화될 경우 암호 시스템의 보안은 안전하지 않은 전달 메커니즘만큼만 안전합니다. 일회성 패드의 일반적인 결함 전달 메커니즘은 패드 암호화를 위한 대칭 키 암호화와 대칭 키 전달을 위한 비대칭 암호화에 의존하는 표준 하이브리드 암호 시스템입니다. 일회용 패드 배송을 위한 일반적인 보안 방법은 양자 키 배포, 스니커넷 또는 택배 서비스 또는 데드 드롭입니다.
• 구현에는 일회성 MAC과 같이 무조건 안전한 인증 메커니즘이 적용되지 않습니다.
• 패드는 재사용됩니다(예를 들어 Venona 프로젝트 중에 이용됨).^[25]
• 패드는 사용 후 바로 파괴되지 않습니다.

사용하다

적용가능성

문제에도 불구하고 일회용 패드는 실용적인 관심을 유지합니다. 일부 가상 스파이 상황에서 일회용 패드는 연필과 종이만 있으면 손으로 암호화 및 복호화를 계산할 수 있기 때문에 유용할 수 있습니다. 다른 거의 모든 고품질 암호는 컴퓨터 없이는 완전히 비현실적입니다. 그러나 현대 세계에서 컴퓨터(휴대전화에 내장된 컴퓨터와 같은)는 매우 도처에 존재하기 때문에 기존 암호화를 수행하기에 적합한 컴퓨터(예를 들어 은폐된 암호 소프트웨어를 실행할 수 있는 전화)를 소유하고 있는 것은 보통 의심을 끌지 않습니다.

• 일회성 패드는 이론적으로 완벽한 비밀성을 갖춘 최적의 암호 시스템입니다.^[19]
• 일회용 패드는 컴퓨터의 도움 없이 한 쪽 또는 양쪽이 모든 작업을 손으로 해야 하는 가장 실용적인 암호화 방법 중 하나입니다. 이는 컴퓨터 이전 시대에 중요한 역할을 했으며, 컴퓨터 소유가 불법적이거나 유죄 판결을 받는 상황이나 신뢰할 수 있는 컴퓨터를 사용할 수 없는 상황에서도 여전히 유용할 수 있습니다.
• 일회용 패드는 보안 환경에 있는 두 당사자가 서로에게서 출발하여 두 개의 분리된 보안 환경에서 완벽한 기밀성으로 통신할 수 있어야 하는 상황에서 실용적입니다.
• 원타임 패드는 초암호화에 사용할 수 있습니다.^[26]
• 양자키 분포와 가장 일반적으로 연관되는 알고리즘은 일회용 패드입니다.^[27]
• 일회용 패드는 스트림 암호로 모방됩니다.^[24]
• 번호 스테이션은 종종 일회용 패드로 암호화된 메시지를 보냅니다.^[2]

양자 및 양자 후 암호학

양자 암호학에서 일회용 패드는 양자 키 분배(QKD)와 관련하여 일반적으로 사용되고 있습니다. QKD는 일반적으로 일회용 패드와 관련이 있는데, 이는 긴 공유 비밀 키를 안전하고 효율적으로 분배할 수 있는 방법을 제공하기 때문입니다(실제적인 양자 네트워킹 하드웨어의 존재를 가정함). QKD 알고리즘은 양자 역학 시스템의 속성을 사용하여 두 당사자가 공유되고 균일한 무작위 문자열에 대해 합의하도록 합니다. BB84와 같은 QKD에 대한 알고리즘은 또한 적대적인 당사자가 키 자료를 가로채려고 시도했는지 여부를 결정할 수 있으며, 상대적으로 적은 메시지 교환과 상대적으로 낮은 계산 오버헤드로 공유 비밀 키를 합의할 수 있습니다. 높은 수준에서 이 계획은 비밀을 교환하고 변조를 탐지하기 위해 양자 상태를 측정하는 파괴적인 방법을 활용하여 작동합니다. 원본 BB84 논문에서 키가 QKD를 통해 배포되는 일회용 패드가 완벽하게 안전한 암호화 체계임이 입증되었습니다.^[27] 그러나 이 결과는 실제로 올바르게 구현되고 있는 QKD 체계에 달려 있습니다. 실제 QKD 시스템에 대한 공격이 존재합니다. 예를 들어, 많은 시스템은 현실적인 제한 때문에 키의 비트당 단일 광자(또는 원하는 양자 상태의 다른 물체)를 전송하지 않으며, 공격자는 메시지와 연관된 일부 광자를 가로채고 측정하여 키에 대한 정보를 얻을 수 있습니다(즉, 패드에 대한 정보 유출). 키의 동일한 비트에 해당하는 측정되지 않은 광자를 통과하는 동안.^[28] 일회용 패드에 QKD를 결합하면 키 재사용에 대한 요구 사항도 완화될 수 있습니다. 1982년, 베넷과 브래사드는 QKD 프로토콜이 상대가 교환된 키를 가로채려고 시도하는 것을 감지하지 못할 경우, 완벽한 비밀을 유지하면서 키를 안전하게 재사용할 수 있다는 것을 보여주었습니다.^[29]

원타임패드의 양자 아날로그도 존재하는데, 이는 완전한 비밀을 가진 일방향 양자 채널을 따라 양자 상태를 교환하는 데 사용될 수 있으며, 이는 양자 컴퓨팅에서 때때로 사용됩니다. 단방향 양자 채널을 따라 n-큐비트 양자 상태를 교환하기 위해서는 적어도 2n개의 고전 비트의 공유 비밀이 필요하다는 것을 알 수 있습니다(아날로그에 의해 n비트의 키가 완벽한 비밀로 n비트 메시지를 교환하는 데 필요하다는 결과). 2000년에 제안된 계획은 이 한계를 달성합니다. 이 양자 일회용 패드를 구현하는 한 가지 방법은 2n 비트 키를 n개의 비트 쌍으로 나누는 것입니다. 상태를 암호화하기 위해 키의 각 비트 쌍 i에 대해 X 게이트를 해당 상태의 큐비트 i에 적용하고 해당 상태의 첫 번째 비트가 1인 경우에만 적용하고 해당 상태의 큐비트 i에 Z 게이트를 적용합니다. X와 Z는 그들 자신의 역이기 때문에 복호화는 이 변환을 다시 적용하는 것을 포함합니다. 이것은 양자 환경에서 완벽하게 비밀이라는 것을 보여줄 수 있습니다.^[30]

일회성 패드는 양자 후 암호화의 한 예인데, 완전한 비밀 유지는 상대의 계산 자원에 의존하지 않는 보안의 정의이기 때문입니다. 따라서 양자 컴퓨터를 가진 적수는 고전 컴퓨터를 가진 적수보다 한 번의 타임패드로 암호화된 메시지에 대한 더 많은 정보를 얻을 수 없을 것입니다.

역사적 용도

일회용 패드는 1900년대 초부터 특별한 상황에서 사용되었습니다. 1923년, 그들은 독일 외교 기관에 의해 외교 통신을 위해 고용되었습니다.^[31] 바이마르 공화국 외교부는 1920년경부터 이 방법을 사용하기 시작했습니다. 1920년대에 두 가지 예에서 정치적인 이유로 메시지가 공개되면서 영국에 의한 빈약한 소련 암호화의 붕괴(ARCOS 사례)는 1930년경 소련이 어떤 목적을 위해 일회용 패드를 채택하게 된 것으로 보입니다. KGB 간첩들도 최근에는 연필과 종이 일회용 패드를 사용한 것으로 알려졌습니다. 1950년대 뉴욕에서 체포되어 유죄판결을 받은 루돌프 아벨 대령과 1960년대 초 영국에서 간첩 혐의로 체포되어 유죄판결을 받은 '크로거스'(즉 모리스와 로나 코헨)가 그 예입니다. 둘 다 소지품에 일회용 패드가 있는 상태로 발견되었습니다.

많은 국가에서 민감한 트래픽을 위해 일회용 패드 시스템을 사용했습니다. 레오 마크스(Leo Marks)는 영국 특수 작전 집행부가 제2차 세계 대전에서 사무실 간의 트래픽을 암호화하기 위해 일회용 패드를 사용했다고 보고했습니다. 해외 에이전트와 함께 사용할 수 있는 일회용 패드는 전쟁 후반에 도입되었습니다.^[15] 영국의 일회용 테이프 암호기로는 록스와 노린이 있습니다. 독일의 Stasi Sprach Machine은 동독, 러시아, 그리고 심지어 쿠바까지 그들의 에이전트에게 암호화된 메시지를 보낼 때 사용했던 한 번의 테이프를 사용할 수 있었습니다.^[32]

제2차 세계 대전의 음성 스크램블러 SIGSALY도 일회성 시스템의 한 형태였습니다. 한쪽 끝에서 신호에 노이즈를 추가하고 다른 쪽 끝에서 제거했습니다. 노이즈는 고유 쌍으로 제조된 대형 쉘락 레코드 형태로 채널 끝단에 분배되었습니다. 시스템을 사용하기 전에 발생하고 해결해야 하는 시작 동기화 및 보다 장기적인 위상 드리프트 문제가 있었습니다.^[33]

1962년 쿠바 미사일 위기 이후 1963년에 설립된 모스크바-워싱턴 D.C. 간 핫라인은 상업용 일회용 테이프 시스템으로 보호되는 텔레프린터를 사용했습니다. 각 국가는 메시지를 인코딩하는 데 사용되는 키 테이프를 준비하여 상대국 대사관을 통해 전달했습니다. 이 경우 OTP의 독특한 장점은 어느 나라도 상대에게 더 민감한 암호화 방법을 공개할 필요가 없다는 것이었습니다.^[34]

미국 육군 특수부대는 베트남에서 일회용 패드를 사용했습니다. 일회성 패드와 연속파 무선 전송(모스 코드의 반송파)이 있는 모스 코드를 사용함으로써, 그들은 비밀과 신뢰할 수 있는 통신을 모두 달성했습니다.^[35]

1988년부터 ANC(African National Congress)는 남아프리카 공화국 내 저항 네트워크를 구축하기 위한 성공적인 노력인 ^[36]불라 작전의 일환으로 남아프리카 공화국 외부의 ANC 지도자들과 국가 내 운영자들 간의 보안 통신 시스템의 일부로 디스크 기반 일회용 패드를 사용했습니다. 디스크의 난수는 사용 후 지워졌습니다. 벨기에 승무원이 패드 디스크를 가져오는 택배 기사 역할을 했습니다. 새 디스크가 상당히 빨리 사용되었기 때문에 정기적인 재공급이 필요했습니다. 시스템의 한 가지 문제는 보안 데이터 저장에 사용할 수 없다는 것이었습니다. 나중에 불라는 이 문제를 해결하기 위해 책 코드로 키를 매긴 스트림 암호를 추가했습니다.^[37]

관련 개념은 일회성 코드로, 한 번만 사용되는 신호입니다. 예를 들어 "미션 완료"를 의미하는 "알파", "미션 실패"를 의미하는 "브라보" 또는 "프랑스 북부 아프리카 연합 침공"^[38]을 의미하는 "토치"는 단어의 합리적인 의미에서 "복호화"될 수 없습니다. 메시지를 이해하려면 추가 정보, 종종 반복의 '깊이' 또는 트래픽 분석이 필요합니다. 그러나 이러한 전략은 (실제 운영자와 야구 코치가 자주 사용하지만)^{[citation needed]} 의미 있는 의미에서 암호화된 일회용 패드가 아닙니다.

NSA

적어도 1970년대에 미국 국가안보국(NSA)은 1972 회계연도에 86,000개의 일회용 패드를 생산하여 범용 및 전문화된 다양한 수동 일회용 패드를 생산했습니다. NSA가 "모든 메시지 텍스트의 기본 프레임워크, 형식 또는 형식이 거의 동일하며, 동일한 종류의 정보, 메시지 후 메시지가 동일한 순서로 표시되고, 각 메시지에 따라 숫자와 같은 특정 값만 변경되는" "프로포마" 시스템을 위해 특수 목적 패드가 제작되었습니다. 핵 발사 메시지와 무선 방향 탐지 보고서(COMUS)가 그 예입니다.^{[39]: pp. 16–18}

범용 패드는 다양한 형식으로 제작되었으며, 랜덤 문자(DIANA) 또는 그냥 숫자(CALYPSO)의 간단한 목록, 비밀 요원을 위한 작은 패드(MICKEY MUSE), 짧은 메시지를 보다 신속하게 인코딩할 수 있도록 설계된 패드입니다. 한 예로 ORION은 한 면에는 평문 알파벳 50줄이, 다른 면에는 해당하는 임의의 암호문 문자가 있었습니다. 탄소를 위로 향하게 하여 탄소 종이 위에 시트를 올려 놓으면, 한 쪽 면에 한 줄씩 한 글자씩 동그라미를 칠 수 있고 다른 면에 해당하는 글자가 탄소 종이에 동그라미를 칠 수 있습니다. 따라서 하나의 ORION 시트는 최대 50자 길이의 메시지를 빠르게 인코딩하거나 디코딩할 수 있습니다. ORION 패드를 생산하기 위해서는 양쪽을 정확한 등록으로 인쇄해야 했고, 이는 어려운 과정이었기 때문에 NSA는 다른 패드 형식인 MEDEA로 전환했고, 25개의 짝을 이룬 알파벳 행과 임의의 문자를 사용했습니다. (공통사항 참조:카테고리:NSA 삽화용 일회용 패드)

NSA는 또한 "중앙정보국(CIA)과 특수부대의 중앙 집중 본부"를 위한 자동화된 시스템을 구축하여 현장에 있는 개별 패드 홀더 간의 많은 별개의 일회성 패드 메시지를 효율적으로 처리할 수 있도록 했습니다.^{[39]: pp. 21–26}

제2차 세계 대전과 1950년대에 미국은 일회용 테이프 시스템을 광범위하게 사용했습니다. 기밀성을 제공할 뿐만 아니라 트래픽이 없는 경우에도 일회용 테이프로 보호된 회로가 지속적으로 작동하여 트래픽 분석으로부터 보호할 수 있었습니다. 1955년 NSA는 약 166만 롤의 1회용 테이프를 생산했습니다. 각각의 롤은 지름이 8인치였고, 10만 개의 문자를 포함했으며, 166분 동안 지속되었으며 제작 비용은 4.55달러였습니다. 1972년까지 55,000개의 롤만 생산되었는데, 일회용 테이프가 SIGTOT와 같은 로터 기계로 대체되었고, 나중에는 시프트 레지스터에 기반한 전자 장치로 대체되었기 때문입니다.^{[39]: pp. 39–44} NSA는 5-UCO와 SIGTOT와 같은 일회성 테이프 시스템을 1957년 전자 암호 기반의 KW-26이 도입되기 전까지 정보 트래픽에 사용하는 것으로 설명하고 있습니다.^[40]

착취물

일회용 패드가 생성되고 적절하게 사용될 경우 완벽한 보안을 제공하지만, 작은 실수는 성공적인 암호 분석으로 이어질 수 있습니다.

• 1944-1945년, 미국 육군의 신호 정보국은 독일 외무부가 GEE라는 코드명의 높은 수준의 트래픽을 위해 사용한 일회성 패드 시스템을 해결할 수 있었습니다.^[41] GEE는 패드가 충분히 무작위적이지 않았기 때문에 불안정했습니다. 패드를 생성하는 데 사용된 기계가 예측 가능한 출력을 생성했기 때문입니다.
• 1945년 미국은 캔버라-모스크바 메시지가 코드북을 사용하여 암호화된 후 일회용 패드를 사용한다는 것을 발견했습니다. 그러나 사용된 일회용 패드는 모스크바가 워싱턴 D.C.를 위해 사용한 것과 동일한 것이었습니다.–모스크바 메시지. 캔버라-모스크바 메시지 중 일부가 알려진 영국 정부 문서를 포함하고 있다는 사실과 결합하여 암호화된 메시지 중 일부가 깨질 수 있었습니다.^{[citation needed]}
• 소련 정보기관은 요원 및 요원 통제관과 비밀리에 연락하기 위해 일회용 패드를 사용했습니다. 분석 결과 이 패드들은 타이피스트들이 실제 타자기를 사용하여 만든 것으로 나타났습니다. 이 방법은 패드가 특정 편리한 키 시퀀스를 더 자주 포함할 가능성이 높기 때문에 실제로는 무작위적이지 않습니다. 타이피스트들이 규칙을 따르지 않았고, 다른 타이피스트들이 다른 패턴의 패드를 생성했기 때문에 패드가 여전히 다소 예측할 수 없었기 때문에 이것은 일반적으로 효과적인 것으로 증명되었습니다. 사용된 키 자료의 복사본이 없다면, 생성 방법의 일부 결함이나 키의 재사용만이 암호 분석의 많은 희망을 제공했습니다. 1940년대 후반부터 미국과 영국의 정보기관들은 제2차 세계대전 동안 모스크바로 가는 소련의 1회용 패드 트래픽의 일부를 중단할 수 있었는데, 이는 핵심 자료를 생성하고 배포하는 과정에서 발생한 오류 때문이었습니다. 한 가지 제안은 모스크바 센터 직원들이 1941년 말과 1942년 초에 모스크바 외곽에서 독일군의 주둔으로 인해 다소 서두르고 있었고, 그들은 그 기간 동안 동일한 핵심 자료를 한 부 이상 생산했다는 것입니다. 수십 년에 걸친 이러한 노력은 마침내 VENONA(브라이드는 이전 이름이었습니다)라는 암호화된 이름으로, 상당한 양의 정보를 생산했습니다. 그럼에도, 감청된 메시지의 일부만 완전히 또는 부분적으로 해독되었습니다(수십만 개 중 몇천 개).^[25]
• 미국이 사용하는 일회용 테이프 시스템은 메시지의 비트와 일회용 테이프를 결합하기 위해 전기 기계 믹서를 사용했습니다. 이 혼합기들은 암호화 장비로부터 어느 정도 떨어진 곳에서 상대가 감지할 수 있는 상당한 전자기 에너지를 방출했습니다. 제2차 세계 대전 중 Bell Labs에서 처음 발견한 이 효과를 통해 전송되는 메시지의 평문을 차단하고 복구할 수 있습니다. 이 취약성 코드는 Tempest입니다.^{[39]: pp. 89 ff}

참고 항목

메모들

참고문헌

더보기

외부 링크

• 암호 기계와 암호학에 관한 예제와 이미지를 포함한 One-Time Pad의 상세한 설명과 이력
• OTP 취약점에 대한 논의가 포함된 FreeS/WAN 용어집 항목