セマンティックセキュリティ

暗号学において、意味的に安全な暗号システムとは、暗号文から平文に関するごくわずかな情報しか抽出できない暗号システムである。具体的には、あるメッセージの暗号文（任意のメッセージ分布から抽出）とメッセージの長さが与えられた場合、確率的多項式時間アルゴリズム（PPTA）は、メッセージ長のみにアクセスでき（暗号文にはアクセスできない）他のすべてのPPTAよりも無視できないほど高い確率で、メッセージの部分的な情報を特定できない。[ 1 ]この概念は、シャノンの完全秘匿性の概念に相当する計算複雑性である。完全秘匿性とは、暗号文が平文に関する情報を全く明らかにしないことを意味し、意味的に安全な暗号システムは、明らかにされた情報が抽出不可能であることを意味する。[ 2 ] [ 3 ] : 378–381 メートル{\displaystyle m}

歴史

セマンティックセキュリティの概念は、1982年にゴールドワッサーとミカリによって初めて提唱されました。 [ 1 ] [ 4 ] しかし、彼らが最初に提案した定義では、実用的な暗号システムのセキュリティを証明するための直接的な手段がありませんでした。ゴールドワッサーとミカリはその後、セマンティックセキュリティが、選択平文攻撃下における暗号文識別不能性と呼ばれる別のセキュリティ定義と同等であることを実証しました。[ 5 ] この後者の定義は、実用的な暗号システムのセキュリティ証明を容易にするため、セマンティックセキュリティの当初の定義よりも一般的になっています。

対称鍵暗号

対称鍵アルゴリズム暗号システムの場合、攻撃者は暗号文から平文に関する情報を一切計算できないようにする必要があります。これは、同じ長さの2つの平文とそれぞれの2つの暗号文が与えられたとしても、攻撃者がどちらの暗号文がどちらの平文に属するかを判断できないという状況を想定しています。

公開鍵暗号

非対称鍵暗号アルゴリズム暗号システムが意味的に安全であるためには、計算量が制限された攻撃者が、暗号文と対応する公開暗号鍵のみを与えられた場合、メッセージ（平文）に関する重要な情報を導き出すことが不可能でなければなりません。意味的安全性は、「受動的」攻撃者、すなわち任意の公開鍵と平文を用いて暗号文を生成・観測する攻撃者のみを考慮します。他のセキュリティ定義とは異なり、意味的安全性は、攻撃者が選択された暗号文の復号を要求できる選択暗号文攻撃（CCA）を考慮しません。また、意味的に安全な暗号化方式の多くは、選択暗号文攻撃に対して明らかに安全ではありません。したがって、意味的安全性は現在、汎用暗号化方式を保護するための不十分な条件と考えられています。

選択平文攻撃下における識別不可能性（IND-CPA）は、一般的に次のような実験によって定義される。[ 6 ]

  1. を実行するとランダムなペアが生成されます。（pけ、sけ）{\displaystyle (pk,sk)}Gen（1n）{\displaystyle \mathrm {Gen} (1^{n})}
  2. 確率的多項式時間制限付き攻撃者に公開鍵が与えられ、攻撃者はそれを使用して任意の数の暗号文を生成できます（多項式制限内）。pけ{\displaystyle pk}
  3. 攻撃者は 2 つの等しい長さのメッセージを生成し、公開鍵とともにチャレンジ オラクルへ送信します。メートル0{\displaystyle m_{0}}メートル1{\displaystyle m_{1}}
  4. チャレンジ オラクルでは、公平なコインを投げて (ランダム ビットを選択して) メッセージの 1 つを選択し、公開キーを使用してメッセージを暗号化し、結果として得られたチャレンジ暗号文を攻撃者に返します。b∈{0、1}{\displaystyle b\in \{0,1\}}メートルb{\displaystyle m_{b}}c{\displaystyle c}

敵対者がオラクルによって2つのメッセージのうちどちらが選択されたかを（ランダム推測の成功率よりも大幅に高い確率で）判別できない場合、基礎となる暗号システムはIND-CPA（したがって選択平文攻撃に対して意味的に安全）である。この定義の派生として、選択暗号文攻撃および適応型選択暗号文攻撃（IND-CCA、IND-CCA2） における識別不能性が定義される。1/2{\displaystyle 1/2}

上記のゲームでは、敵対者が公開暗号化キーを所有しているため、意味的に安全な暗号化方式は、定義により確率的であり、ランダム性の要素を備えている必要があります。そうでない場合、敵対者は、 と の決定論的暗号化を計算し、これらの暗号化を返された暗号文と比較して、オラクルの選択を推測することができます。 メートル0{\displaystyle m_{0}}メートル1{\displaystyle m_{1}}c{\displaystyle c}

セマンティックセキュリティにおけるランダム性の役割

ランダム性は暗号において重要な役割を果たし、攻撃者が暗号文のパターンを検出することを防ぎます。意味的に安全な暗号システムでは、同じ平文を複数回暗号化すると、異なる暗号文が生成されます。[ 7 ]

暗号化が予測可能な、あるいは弱いランダム性に依存している場合、解読が容易になります。[ 8 ]ランダム性が弱いと、攻撃者が解析できるパターンが生成され、秘密鍵の復元やメッセージの復号化が可能になる可能性があります。そのため、暗号システムはセキュリティを維持するために、強力かつ予測不可能なランダム値を使用する必要があります。[ 9 ]

ランダム性が重要な理由

強力なランダム性は次のような場合に重要です。

過去のランダム性の失敗

ランダム性の弱さが原因で、攻撃者が暗号を解読できる暗号化障害がいくつか発生しました。

Debian OpenSSL の脆弱性 (2008)

DebianのOpenSSLのエラーによりエントロピー収集が削除され、予測可能な少数の鍵が生成されました。攻撃者はSSH鍵とTLS鍵を推測し、不正アクセスを許す可能性があります。[ 12 ]

ソニー PlayStation 3 ECDSA 障害 (2011)

ソニーのPlayStation 3は、楕円曲線デジタル署名アルゴリズム（ECDSA）を悪用し、暗号署名で一度だけ使用される乱数であるナンスを複数の署名で再利用していました。ECDSAはセキュリティのために固有のナンスに依存しているため、攻撃者はソニーの秘密署名鍵を盗用し、不正なソフトウェアに署名することができました。[ 13 ]

ROCAの脆弱性（2017年）

インフィニオンのRSA鍵生成における欠陥により、攻撃者が効率的に因数分解できる弱い鍵が生成されました。この脆弱性はスマートカードとトラステッド・プラットフォーム・モジュール（TPM）に影響を与え、広範囲にわたる鍵の交換が必要となりました。[ 14 ]

強力なランダム性を確保する方法

このような障害を防ぐために、暗号システムは予測不可能な高品質の乱数値を生成する必要がある。[ 15 ]

暗号的に安全な擬似乱数生成器（CSPRNG）の使用

CSPRNGは、攻撃に耐性のある安全な乱数を提供します。一般的な例としては、以下のようなものがあります。

  • /dev/random と /dev/urandom (Unix)
  • Windows 暗号生成ランダム
  • NIST承認のDRBG（決定論的乱数ビット生成器）[ 15 ]

エントロピー収集

安全なランダム性には、次のような高エントロピー ソースが必要です。

  • ハードウェアベースのジェネレータ（例：Intel RDRAND）[ 16 ]
  • キーストロークのタイミングなどの物理的な情報源[ 16 ]
  • HSMやTPMなどの専用セキュリティハードウェア[ 16 ]

ランダム性のない決定論的暗号化の回避

一部の暗号化方式では、セキュリティを維持するために追加のランダム性が必要になります。

  • OAEPパディングを用いたRSAは、決定論的な暗号化を防ぐためにランダム性を導入する。[ 17 ]
  • AES-GCMとElGamalの固有のノンスは、同じメッセージを複数回暗号化しても異なる暗号文が生成されることを保証します。[ 17 ]

ランダム性のテストと監査

ランダム性の品質を検証するために、暗号実装では以下の手順を実行する必要があります。

意味的に安全な暗号化アルゴリズムには、Goldwasser-Micali、ElGamal、Paillierなどがあります。これらの方式は、その意味的安全性が何らかの難しい数学的問題（例えば、Decisional Diffie-Hellman問題やQuadratic Residuosity Problem ）を解くことに帰着するため、証明可能的に安全であると考えられています。RSAなどの意味的に安全でないアルゴリズムは、最適非対称暗号化パディング（OAEP）などのランダム暗号化パディング方式を用いることで（より強い仮定の下で）意味的に安全になります。

参考文献

  1. ^ a b S. GoldwasserとS. Micali、「確率的暗号化と部分的な情報をすべて秘密に保つメンタルポーカーのプレイ方法」、Annual ACM Symposium on Theory of Computing、1982 年。
  2. ^シャノン、クロード (1949). 「秘密システムの通信理論」.ベルシステム技術ジャーナル. 28 (4): 656– 715. doi : 10.1002/j.1538-7305.1949.tb00928.x . hdl : 10338.dmlcz/119717 .
  3. ^ Goldreich, Oded.暗号の基礎：第2巻、基本アプリケーション。第2巻。ケンブリッジ大学出版局、2004年。
  4. ^ Goldwasser, Shafi; Micali, Silvio (1984-04-01). 「確率的暗号化」 . Journal of Computer and System Sciences . 28 (2): 270– 299. doi : 10.1016/0022-0000(84)90070-9 . ISSN 0022-0000 . 
  5. ^ S. GoldwasserとS. Micali、「確率的暗号化」、Journal of Computer and System Sciences、28:270-299、1984年。
  6. ^カッツ、ジョナサン、リンデル、イェフダ (2007). 『現代暗号入門：原理とプロトコル』 チャップマン・アンド・ホール/CRC. ISBN 978-1584885511。
  7. ^ Menezes, Alfred; Van Oorschot, Paul C.; Vanstone, Scott (1996). Handbook of Applied Cryptography . CRC Press.
  8. ^ Menezes, Alfred; Van Oorschot, Paul C.; Vanstone, Scott (1996). Handbook of Applied Cryptography . CRC Press.
  9. ^カッツ、ジョナサン、リンデル、イェフダ (2007). 『現代暗号入門：原理とプロトコル』 チャップマン・アンド・ホール/CRC. ISBN 978-1584885511。
  10. ^カッツ、ジョナサン、リンデル、イェフダ (2007). 『現代暗号入門：原理とプロトコル』 チャップマン・アンド・ホール/CRC. ISBN 978-1584885511。
  11. ^ a bカッツ、ジョナサン、リンデル、イェフダ (2007). 『現代暗号入門：原理とプロトコル』 チャップマン・アンド・ホール/CRC. ISBN 978-1584885511。
  12. ^ Bello, Luciano (2008-05-13). 「Debian OpenSSL 予測可能乱数ジェネレータ」 . Debian セキュリティアドバイザリ.
  13. ^ Schneier, Bruce (2011年1月6日). 「Sony PS3のセキュリティが破られる」 . Schneier on Security.
  14. ^ 「ROCA：Infineon TPMおよびセキュアエレメントRSA脆弱性ガイダンス」国立サイバーセキュリティセンター。2017年10月17日。
  15. ^ a b「決定論的乱数ビット生成器を用いた乱数生成に関する勧告」アメリカ国立標準技術研究所（NIST）。2012年6月11日。
  16. ^ a b c d「ランダムビット生成に使用されるエントロピーソースに関する推奨事項」。米国国立標準技術研究所（NIST）。2018年1月10日。
  17. ^ a b「整数因数分解暗号を用いたペアワイズ鍵確立に関する勧告」アメリカ国立標準技術研究所（NIST）。2019年5月23日。
  18. ^ 「暗号化アプリケーション用乱数および疑似乱数ジェネレータの統計テストスイート」アメリカ国立標準技術研究所（NIST）2010年4月1日。
  19. ^ 「暗号化モジュールのセキュリティ要件」アメリカ国立標準技術研究所（NIST）。2002年5月25日。
「 https://en.wikipedia.org/w/index.php?title=Semantic_security&oldid=1320675828」から取得