ワンタイムパッド

上記の例を続けると、イブがアリスの暗号文を傍受したとしますEQNVZ。イブが考えられるすべての鍵を試した場合、鍵によってXMCKL平文が生成されることを発見するでしょうが、鍵によって平文が生成されるhelloこともまた発見するでしょう。これは同様にもっともらしいメッセージです。TQURIlater

 4 (E) 16 (Q) 13 (N) 21 (V) 25 (Z) 暗号文 − 19 (T) 16 (Q) 20 (U) 17 (R) 8 (I) 可能なキー = −15 0 −7 4 17 暗号文-鍵 = 11 (l) 0 (a) 19 (t) 4 (e) 17 (r) 暗号文-鍵 (mod 26)

実際、異なる鍵を使用するだけで、同じ文字数のどんなメッセージでも暗号文から「復号」することが可能であり、暗号文にはイブが暗号文のさまざまな可能な読み取りの中から選択できるような情報は含まれていません。^{[ 16 ]}

鍵が真にランダムでない場合、統計分析を用いて、考えられる鍵の中で最もランダム性が低い鍵、つまり正しい鍵である可能性が高い鍵を特定することが可能です。鍵が再利用された場合、その鍵は両方の暗号文から意味のある平文を生成する唯一の鍵となることが顕著にわかります（ランダムに生成された誤った鍵が2つの意味のある平文を生成する可能性は非常に低い）。

高品質の乱数を生成することは困難です。ほとんどのプログラミング言語ライブラリの乱数生成関数は暗号化には適していません。/dev/randomや多くのハードウェア乱数生成器など、通常の暗号化に適した生成器でさえ、安全性が証明されていない暗号化関数を使用している場合があります。純粋な乱数を生成する技術の一例として、放射性放出の測定があります。^{[ 19 ]}

特に、一度限りの使用が絶対に必要です。たとえば、${\displaystyle p_{1}}$そして${\displaystyle p_{2}}$これらは2つの異なる平文メッセージを表し、それぞれ共通の鍵で暗号化されている。${\displaystyle k}$すると、それぞれの暗号文は次のようになります。

${\displaystyle c_{1}=p_{1}\oplus k}$

${\displaystyle c_{2}=p_{2}\oplus k}$

どこ${\displaystyle \oplus }$XORを意味します。攻撃者が両方の暗号文を入手した場合${\displaystyle c_{1}}$そして${\displaystyle c_{2}}$、次に単純にXORを取る${\displaystyle c_{1}}$そして${\displaystyle c_{2}}$2つの平文のXOR演算結果を生成する${\displaystyle p_{1}\oplus p_{2}}$（これは、すべてのビットストリームをそれ自身とXOR演算すると、XORの 単位元である0が得られるためです。）${\displaystyle p_{1}\oplus p_{2}}$これは、実行中の鍵暗号と同等のものです。

両方の平文が自然言語（例えば英語やロシア語）であれば、それぞれヒューリスティック暗号解読によって解読される可能性が非常に高く、多少の曖昧さが生じる可能性もある。もちろん、長いメッセージは短いメッセージと重なる部分のみ解読でき、さらに単語やフレーズを補完することで少し解読できる場合もある。この脆弱性を悪用した最も有名な事例は、Venonaプロジェクトである。^{[ 20 ]}

パッドは、すべての共有秘密と同様に、安全に渡され、安全に保管されなければならず、パッドは少なくともメッセージと同じ長さでなければならないため、ワンタイムパッドを使用する意味はほとんどありません。パッドの代わりに平文を送信すればよいからです（両方とも同じサイズで、安全に送信する必要があるため）。^{[ 16 ]}ただし、非常に長いパッドが安全に送信されると（たとえば、ランダムなデータでいっぱいのコンピュータディスク）、メッセージのサイズの合計がパッドのサイズと等しくなるまで、将来の多数のメッセージに使用できます。量子鍵配送は、耐障害性量子コンピュータを前提として、この問題に対する解決策も提案しています。

非常に長いワンタイムパッドキーを配布するのは不便で、通常は重大なセキュリティリスクを伴います。^{[ 2 ]}パッドは基本的に暗号化キーですが、現代の暗号のキーとは異なり、非常に長くなければならず、人間が記憶するのは非常に困難です。サムドライブ、DVD-R、またはパーソナルデジタルオーディオプレーヤーなどのストレージメディアを使用して、非常に大きなワンタイムパッドを疑われない方法で場所から場所へ持ち運ぶことができますが、パッドを物理的に輸送する必要があることは、現代の公開鍵暗号システムのキーネゴシエーションプロトコルと比較すると負担です。このようなメディアは、物理的に破壊する（焼却するなど）以外の方法では確実に安全に消去することはできません。ワン タイムパッドデータでいっぱいの 4.7 GB の DVD-R を1 mm ² (0.0016平方インチ)の粒子に細断すると、各粒子に 4メガビットを超えるデータが残ります。さらに、転送中に情報が漏洩するリスク（例えば、スリがパッドを盗み、コピーして交換するなど）は、 AESのような暗号方式で情報が漏洩する可能性よりも、実際にははるかに高いと考えられます。最後に、ワンタイムパッドの鍵素材を管理するために必要な労力は、通信参加者が多い大規模なネットワークでは非常に非効率的です。必要なパッドの数は、メッセージを自由に交換するユーザー数の二乗に比例して増加します。2人間の通信やスター型ネットワークトポロジーの場合は、この問題はそれほど深刻ではありません。   

鍵マテリアルは使用後に安全に廃棄されなければならず、鍵マテリアルが再利用されないこと、および送信されたメッセージが保護されることを保証する必要があります。^{[ 2 ]}鍵マテリアルはエンドポイント間で転送され、メッセージが送信または受信されるまで存続する必要があるため、保護対象の一時的な平文よりもフォレンジック復元に対して脆弱になる可能性があります（データの残留の可能性のため）。

従来使用されてきたワンタイムパッドはメッセージ認証を提供しないため、実際のシステムではセキュリティ上の脅威となる可能性があります。たとえば、メッセージに「明日午後3時30分にジェーンと会おう」という内容が含まれていることを知っている攻撃者は、既知の2つの要素（暗号化されたテキストと既知の平文）からパッドの対応するコードを直接導き出すことができます。攻撃者は、そのテキストを「午後3時30分の会議はキャンセルされました。家にいてください」など、まったく同じ長さの別のテキストに置き換えることができます。攻撃者がワンタイムパッドについて知っている情報は、このバイト長に限定されており、メッセージの他の内容が有効であるためには、このバイト長を維持する必要があります。これは、平文が必ずしも既知ではない可塑性^{[ 21 ]}とは異なります。攻撃者は、メッセージを知らなくても、ワンタイムパッドで送信されたメッセージのビットを反転させることができ、受信者はそれを検出できません。類似点があるため、ワンタイムパッドに対する攻撃は、ストリーム暗号に対する攻撃と似ています。^{[ 22 ]}

このような攻撃を防ぐための標準的な手法として、メッセージ認証コードの使用などが挙げられますが、これらはワンタイムパッドシステムと併用することで、可変長パディングやロシアンコピュレーションといった古典的な手法と同様に、OTP自体が持つような完全なセキュリティは持ち合わせていません。ユニバーサルハッシュは、任意のセキュリティ境界までメッセージを認証する方法を提供します（つまり、任意のp > 0に対して、十分に大きなハッシュ値を用いることで、計算能力に制限のない攻撃者であっても、偽造に成功する確率はp未満になります）。しかし、この方法ではパッドから追加のランダムデータを使用する必要があり、また、これらの手法の中には、コンピュータなしでシステムを実装する可能性を排除するものもあります。

実装が比較的容易であること、そして完全な秘密保持が期待できることから、ワンタイムパッドは暗号学を学ぶ学生の間で非常に人気が高い。特に、コースで最初に紹介され実装されるアルゴリズムであることが多いためだ。しかし、このような「最初の」実装では、情報理論的セキュリティの要件が1つ以上の点で満たされないことが多い。

• パッドは、1つまたは複数の小さな値をより長い「ワンタイムパッド」に展開する何らかのアルゴリズムによって生成されます。これは、平方根の小数展開のような安全性の低い基本的な数学演算から、複雑で暗号的に安全な擬似乱数生成器（CSPRNG）まで、すべてのアルゴリズムに等しく適用されます。これらの実装はいずれもワンタイムパッドではなく、定義上ストリーム暗号です。すべてのワンタイムパッドは、ハードウェア乱数生成器など、非アルゴリズム的なプロセスによって生成されなければなりません。
• ワンタイムパッドは、情報理論的に安全でない方法で交換されます。ワンタイムパッドが配信のために情報理論的に安全でないアルゴリズムで暗号化されている場合、暗号システムの安全性は、安全でない配信メカニズムの安全性に依存します。ワンタイムパッドの一般的な欠陥のある配信メカニズムは、パッドの暗号化に共通鍵暗号方式を使用し、共通鍵の配信に非共通暗号方式を使用する標準的なハイブリッド暗号システムです。ワンタイムパッドの配信に一般的な安全な方法は、量子鍵配送、スニーカーネットまたは宅配便サービス、またはデッドドロップです。
• この実装には、ワンタイムMACのような無条件に安全な認証メカニズムは含まれていません。
• パッドは再利用される（例えば、Venonaプロジェクトで利用された）。 ^{[ 23 ]}
• パッドは使用後すぐに破損するわけではありません。

問題点はあるものの、ワンタイムパッドには実用的な魅力が残っている。架空のスパイ活動のような状況では、ワンタイムパッドは鉛筆と紙だけで暗号化と復号化を手作業で計算できるため、有用となる可能性がある。他のほとんどの高品質暗号は、コンピュータなしでは全く実用的ではない。しかし、現代社会では、コンピュータ（携帯電話に組み込まれているものなど）が非常に普及しているため、従来の暗号化を実行できるコンピュータ（例えば、隠蔽された暗号化ソフトウェアを実行できる携帯電話）を所有していても、通常は疑われることはないだろう。

• ワンタイムパッドは、理論的に完全な秘密性を備えた最適な暗号システムである。^{[ 17 ]}
• ワンタイムパッドは、コンピュータの助けを借りずに、当事者の一方または両方がすべての作業を手作業で行う必要がある、最も実用的な暗号化方法の1つです。このため、コンピュータが普及する以前の時代には重要であり、コンピュータの所持が違法または不利な場合、あるいは信頼できるコンピュータが利用できない状況では、現在でも有用である可能性があります。
• 使い捨てパッドは、安全な環境にいる2者が互いに離れ、それぞれ別の安全な環境から完全な秘密保持のもとで通信する必要がある状況において実用的です。
• ワンタイムパッドはスーパー暗号化に使用できます。^{[ 24 ]}
• 量子鍵配送で最も一般的に使用されるアルゴリズムはワンタイムパッドです。^{[ 25 ]}
• ワンタイムパッドはストリーム暗号によって模倣される。^{[ 22 ]}
• ナンバーズステーションは、ワンタイムパッドで暗号化されたメッセージを送信することが多い。^{[ 2 ]}

量子暗号におけるワンタイムパッドの一般的な用途は、量子鍵配送（QKD）との組み合わせです。QKDは、長い共有秘密鍵を安全かつ効率的に配布する方法を提供するため、通常ワンタイムパッドと関連付けられます（実用的な量子ネットワークハードウェアが存在することを前提としています）。QKDアルゴリズムは、量子力学システムの特性を利用して、2者が共有の一様ランダムな文字列に合意できるようにします。BB84などのQKDアルゴリズムは、敵対者が鍵情報を傍受しようとしたかどうかを判断することもでき、比較的少ないメッセージ交換と比較的低い計算オーバーヘッドで共有秘密鍵に合意することを可能にします。大まかに言うと、これらの方式は、量子状態が破壊的に測定される方法を利用して秘密を交換し、改ざんを検出することで機能します。オリジナルのBB84論文では、QKDを介して配布される鍵を用いたワンタイムパッドは、完全に安全な暗号化方式であることが証明されました。^{[ 25 ]}ただし、この結果は、QKD スキームが実際に正しく実装されていることを前提としています。実際の QKD システムに対する攻撃は存在します。たとえば、多くのシステムは、実際的な制約のために、鍵のビットごとに単一の光子 (または目的の量子状態にある他のオブジェクト) を送信しません。攻撃者は、メッセージに関連付けられた光子の一部を傍受して測定し、鍵に関する情報 (つまり、パッドに関する情報の漏洩) を取得すると同時に、同じ鍵のビットに対応する未測定の光子を転送することができます。^{[ 26 ]} QKD とワンタイムパッドを組み合わせることで、鍵の再利用の要件を緩和することもできます。1982 年に、BennettとBrassard は、QKD プロトコルが、攻撃者が交換された鍵を傍受しようとしていることを検出しない場合、完全な秘密性を維持しながら鍵を安全に再利用できることを示しました。^{[ 27 ]}

ワンタイムパッドはポスト量子暗号の一例である。なぜなら、完全な秘匿性とは、攻撃者の計算能力に依存しないセキュリティの定義だからである。したがって、量子コンピュータを持つ攻撃者であっても、ワンタイムパッドで暗号化されたメッセージについて、従来のコンピュータを持つ攻撃者よりも多くの情報を得ることはできない。

ワンタイムパッドは、1900 年代初頭から特別な状況で使用されてきました。1923 年に、ドイツの外交機関によって外交通信に使用されました。^{[ 28 ]}ワイマール共和国の外交局は、1920 年頃からこの方法を使用し始めました。1920 年代に 2 件の政治的な理由でメッセージを公開したイギリスによるソ連の貧弱な暗号の解読( ARCOS 事件) により、ソ連は 1930 年頃までに何らかの目的でワンタイムパッドを採用するようになったようです。KGBのスパイも、最近では鉛筆と紙のワンタイムパッドを使用していたことが知られています。例としては、 1950 年代にニューヨーク市で逮捕され有罪判決を受けたルドルフ・アベル大佐や、1960 年代初頭にイギリスでスパイとして逮捕され有罪判決を受けた「クローガー夫妻」(つまり、モリスとロナ・コーエン) が挙げられます。どちらも物理的なワンタイムパッドを所持していました。

多くの国が機密性の高い通信にワンタイムパッドシステムを使用してきた。レオ・マークスは、イギリス特殊作戦執行部が第二次世界大戦中に事務所間の通信を暗号化するためにワンタイムパッドを使用していたと報告している。海外のエージェントとの通信に使用するワンタイムパッドは戦争末期に導入された。^{[ 12 ]}イギリスのワンタイムテープ暗号機には、RockexやNoreenなどがある。ドイツのシュタージ・シュプラッハ・マシンもワンタイムテープを使用することができ、東ドイツ、ロシア、さらにはキューバも暗号化されたメッセージをエージェントに送信するために使用していた。^{[ 29 ]}

第二次世界大戦中の音声スクランブラーSIGSALYも、一種のワンタイムシステムでした。信号の一端でノイズを加え、もう一端でノイズを除去しました。ノイズは、独自のペアで製造された大型シェラックレコードの形でチャネルの両端に分配されました。開始同期と長期的な位相ドリフトの両方の問題が発生し、システムが使用される前に解決する必要がありました。^{[ 30 ]}

1962年のキューバ危機後に1963年に開設されたモスクワとワシントンDC間のホットラインは、商用ワンタイムテープシステムで保護されたテレプリンターを使用していた。各国はメッセージを暗号化するために使用するキーイングテープを用意し、相手国の大使館を経由して送信した。この場合のOTPのユニークな利点は、どちらの国もより機密性の高い暗号化方法を相手国に開示する必要がなかったことである。^{[ 31 ]}

アメリカ陸軍特殊部隊はベトナムでワンタイムパッドを使用した。ワンタイムパッドと連続波無線伝送（モールス信号の搬送波）を用いたモールス信号により、秘密性と信頼性の高い通信の両方を実現した。^{[ 32 ]}

1988年から、アフリカ民族会議（ANC）は、南アフリカ国外のANC指導者と国内の工作員との間の安全な通信システムの一部として、ディスクベースのワンタイムパッドを使用していた。これは、南アフリカ国内に抵抗ネットワークを構築することに成功した作戦「Vula」 [ ^{33 ]の}一環であった。ディスク上の乱数は使用後に消去された。ベルギー人客室乗務員が運び屋としてパッドディスクを運んだ。ディスクはかなり早く使い切られたため、新しいディスクを定期的に補充する必要があった。このシステムの問題点の1つは、安全なデータストレージには使用できなかったことである。後にVulaは、この問題を解決するためにブックコードで鍵付けされたストリーム暗号を追加した。^{[ 34 ]}

関連する概念として、ワンタイムコードがあります。これは一度だけ使用される信号で、例えば「任務完了」を表す「アルファ」、「任務失敗」を表す「ブラボー」、あるいは「フランス領北アフリカへの連合軍の侵攻」を表す「トーチ」 ^{[ 35 ]}などは、いかなる意味でも「解読」することはできません。メッセージを理解するには、多くの場合、繰り返しの「深さ」やトラフィック分析といった追加情報が必要になります。しかし、このような戦略は（実際の工作員や野球のコーチによってよく使われますが）^{[ 36 ]}、重要な意味では暗号化ワンタイムパッドではありません。

少なくとも1970年代まで、米国国家安全保障局（NSA）は、汎用および特殊用途の両方のさまざまな手動ワンタイムパッドを製造しており、1972会計年度には86,000枚のワンタイムパッドが製造された。特殊用途パッドは、NSAが「プロフォーマ」システムと呼ぶもの向けに製造されたもので、「すべてのメッセージテキストの基本的な枠組み、形式、またはフォーマットは同一またはほぼ同じであり、メッセージごとに同じ種類の情報が同じ順序で提示され、数値などの特定の値のみが各メッセージで変化する」システムである。例としては、核ミサイル発射メッセージや無線方向探知報告（COMUS）などが挙げられる。^{[ 37 ]： pp.16-18}

汎用パッドは、ランダムな文字の単純なリスト（DIANA）や数字のみのリスト（CALYPSO）、秘密工作員向けの小型パッド（MICKEY MOUSE）、そして密度は低いものの短いメッセージをより迅速に暗号化できるように設計されたパッドなど、いくつかの形式で製造されました。例えば、ORIONは、片面に50行の平文アルファベット、もう片面に対応するランダムな暗号文の文字が並んでいました。カーボン紙の上にシートを置き、カーボン面を上にすると、片面の各行の文字を丸で囲むことができ、カーボン紙によってもう片面の対応する文字が丸で囲まれます。このように、ORIONシート1枚で最大50文字のメッセージを迅速に暗号化または復号化することができました。ORIONパッドの製造には両面を正確に位置合わせして印刷する必要があり、これは困難な作業であったため、NSAは25行のアルファベットとランダムな文字がペアになった別のパッド形式であるMEDEAに切り替えました。（図については、Commons:Category:NSA one-time padsを参照してください。）

NSAはまた、「CIAと特殊部隊の中央本部が、現場の個々のパッド保持者との間でやり取りされる多数の個別のワンタイムパッドメッセージを効率的に処理できるように」自動化システムを構築した。^{[ 37 ]： pp.21-26}

第二次世界大戦中から1950年代にかけて、米国はワンタイムテープシステムを広く利用した。ワンタイムテープで保護された回線は、機密性を提供するだけでなく、トラフィックがないときでも継続的に動作し、トラフィック分析から保護した。1955年、NSAは約166万ロールのワンタイムテープを製造した。各ロールは直径8インチ、10万文字、166分間持続し、製造コストは4.55ドルだった。1972年までに製造されたロールはわずか5万5000ロールで、ワンタイムテープはSIGTOTなどのローターマシン、そして後にシフトレジスタに基づく電子機器に置き換えられた。^{[ 37 ]： pp.39-44} NSAは、 1957年に電子暗号ベースのKW-26が導入されるまで、 5-UCOやSIGTOTなどのワンタイムテープシステムが諜報トラフィックに使用されていたと説明している。 ^{[ 38 ]}

ワンタイムパッドは、正しく生成および使用すれば完全な機密性を提供するが、小さなミスでも暗号解読に成功してしまう可能性がある。

• 1944年から1945年にかけて、アメリカ陸軍の信号情報部は、ドイツ外務省が高レベルの通信に使用していたワンタイムパッドシステム（コードネームGEE）を解読することに成功した。^{[ 39 ]} GEEは、パッドが十分にランダムではなかったため安全ではなかった。パッドを生成するために使用された機械は予測可能な出力を生成した。
• 1945年、米国はキャンベラとモスクワ間の通信が、まず暗号帳を用いて暗号化され、その後ワンタイムパッドを用いて暗号化されていることを発見した。しかし、使用されたワンタイムパッドは、モスクワがワシントンD.C.とモスクワ間の通信に使用していたものと同じだった。さらに、キャンベラとモスクワ間の通信の中には、既知の英国政府文書が含まれていたため、暗号化されたメッセージの一部が解読されることになった。
• ワンタイムパッドは、ソ連の諜報機関が工作員や工作員の管制官との秘密通信に使用していた。分析によると、これらのパッドはタイピストが実際のタイプライターを使って生成していた。この方法は、特定の都合の良いキーシーケンスが頻繁に含まれる可能性が高くなるため、真の意味でのランダム性はない。しかし、タイピストが規則に従っていなかったため、パッドはある程度予測不可能であり、タイピストによって異なるパターンのパッドが生成されたことから、この方法は概ね効果的であった。使用されたキー素材のコピーがなければ、生成方法の欠陥やキーの再利用以外に、暗号解読の望みはほとんどなかった。1940年代後半から、米国と英国の諜報機関は、第二次世界大戦中にソ連がモスクワに向けて使用していたワンタイムパッド通信の一部を、キー素材の生成と配布におけるミスを突いて解読することに成功した。1941年末から1942年初頭にかけて、モスクワ近郊にドイツ軍が展開していたため、モスクワセンターの職員がやや慌てており、その期間中に同じキー素材のコピーを複数作成したという説がある。この数十年にわたる取り組みは最終的にVENONAというコードネームが付けられ（以前はBRIDEという名前だった）、かなりの量の情報が得られた。それでも、傍受されたメッセージのうち、完全にまたは部分的に解読されたのはごくわずかだった（数十万のうち数千だけ）。^{[ 23 ]}