NSAプレゼンテーションからのスライド
2013年、エドワードスノーデンのおかげで、 NSA文書がメディアに掲載されました。 その中には、プレゼンテーションからのぼやけたスライドがあります。これは、VPNトラフィックを解読するNSAの能力を示しています。 NSAには秘密のプレゼンテーションに横たわる理由がなかったので、専門家はこの情報を現代の公開鍵暗号システムの根本的な脆弱性の証拠とみなしました。
暗号の基礎とアルゴリズムの実装が再び改訂されました。 すぐに最初の仮定が現れました。 これらの最も可能性が高いのは、基本的な脆弱性がDiffie-Hellmanプロトコルの実用的な実装に潜んでいることでした 。 具体的には、DSA標準で推奨されているプロトコルの実装により、ユーザーはキーを生成するときに一意の大きなpモジュールを計算するのではなく、 標準の数値を使用することが推奨されます。
たとえば、 RFC 2409で推奨される素数は次のとおりです。
そのため、実際に起こりました。最近まで、Alexaリストの最も人気のあるHTTPSサイトの92％が2つの標準プライムを使用していました。 Diffie-Hellmanプロトコルは、SSH、VPN、SMTPS、IPsecなどのプロトコルで使用されるキーを生成するためにも使用されます。
これらの数は十分に大きい素数で安全と見なされました。 現在、ペンシルベニア大学（米国）、INRIA、CNRS、およびロレーヌ大学（フランス）の専門家は、そのようなすべての番号が安全ではないことを証明することができたため、NSAにはHTTPSトラフィックを解読する理論上の可能性があります。 暗号作成者は、暗号化キーを生成するときにモジュールpとして使用すると、特別に構築された大きな素数が「トラップドア」として機能し、キーの他の秘密コンポーネントを見つけ、その結果、秘密メッセージを解読できることを実際に実証しました。
一般的に言えば、1991年にデジタル署名アルゴリズム （DSA）標準が公開された直後、 pモジュールとして標準プライムを使用するユーザーの大きな標準グループの可能性は、そのような機会を提供し、実際にそのような慣行を促進しました。
DSAは、公開鍵を使用して電子署名を作成する暗号化アルゴリズムです。 署名は秘密に作成されますが、公に検証することができます。 このアルゴリズムは、有限体の対数を取る離散的な対数の計算の複雑さに基づいています。
従来のDSAベースの暗号化スキームは、Diffie-Hellman共有キー生成スキームです。 その暗号強度は、指数関数の計算上の複雑さの高さに基づいています。 専門家が示唆したように、離散対数計算アルゴリズムは非常に高い複雑さを持ち、これは最速の因数分解アルゴリズムの複雑さに匹敵します。
これは完全に真実ではないことが判明しました。 暗号学者が示したように、1024ビットキーの特定の数pを使用すると、完全に見える時間で離散対数を計算することができます。 研究者は、大学ネットワーク内の約3,000プロセッサコアのクラスタで2か月でこれを行いました（タスク中に実際のマシン数が変更されました）。
唯一の問題は、「標準」素数がそのような「抜け穴」であるかどうか、そしてそれらはどこから来たのかです。 理論的には、予備計算とプライムの編集に侵入者が関与する可能性があります。 そして、「何兆もの暗号化された接続」を解読する可能性についてのNSAの声明の意味を理解します。 NSAデータセンターの計算能力により、メッセージの解読には2か月もかかりません。
特別に選択されたモジュールpを標準に導入する可能性は、NSAがこのアイデアを実際に実装したことを意味しません。 NSAが使用するアルゴリズムを知らないと、現在使用されている素数が「良い」か「悪い」かを検証できません。 しかし、これが真実ならば、これは公の暗号化標準を弱体化しようとするNSAの最初の試みではありません。 「乱数」ジェネレーターDual_EC_DRBGのストーリーはまだメモリーから消去されていません-他のプログラムの中でも、RSA BSAFEおよびData Protection ManagerのデフォルトのRNGです。 Snowdenの文書が示したように、このジェネレーターは元々、予測可能な数値を生成するためにNSAが関与して設計されました。
特別に選択された素数による潜在的な「抜け穴」から保護するために、DSAは擬似乱数「シード値」の公開により、「仮想的にランダム」な方法で素数を選択する可能性を提供しました。 しかし、実際に誰も今この機会を利用していません。 すでに述べたように、大部分のサイトは、一般的な使用のために文書で提案されている標準的な素数でキーを生成します。
暗号化アルゴリズムの潜在的な脆弱性に対する最も簡単な防御は、1024ビットより長いキーを選択することです、と同著者は述べています。 彼らの計算によると、同じ「弱められた」素数を持つ2048ビットキーの計算には、1024ビットキーの計算よりも約1,600万倍時間がかかります。 SSL Pulseの調査によると、現在、長さ1024ビット以下のSSL交換キーを使用しているサイトの27.3％が占めています。
将来的には、研究者は、安全のために、すべての素数をシード値とともに公開する必要があると考えています。
一般に、信頼できるソースからのみ素数を取る必要があります。