弱いRSAキーでパニックしないでください-PとQの世話をしてください

すでにLenstroyらによって公開されているプレプリント（ Habrに関する議論 ）は、公開鍵を使用した暗号システムのエントロピーの問題についてすでに見ているかもしれません。 Zakir Durumerik 、 Erik Wustrov 、 Alex Halderman 、 およびI （Nadia Heninger）は、同様の結果を明らかにするのを待っていました。 関係するすべてのメーカーに通知された後、記事全体を公開します。 その間、実際に何が起こっているのかについて、より完全な説明を提供したいと思います。



SSLのためにWebサイトで使用されるすべての公開キーの約0.4％をリモートで侵害することができました。 侵害されたすべてのキーは、予測可能な「乱数」を使用して誤って生成され、これも時々繰り返されました。 合計で、2種類の問題を区別できます。予測可能なランダム性で生成されたキーと、ランダム性の欠如により攻撃者が公開キーをすばやくファクタリングして秘密キーを取得できるこれらのキーのサブセットです。 攻撃者は秘密鍵を持っているため、Webサイトになりすまし、このWebサイトに向けられた暗号化されたトラフィックを解読できる可能性があります。 数時間で、この攻撃に対して脆弱なすべてのホストに対して公開鍵を分解し、秘密鍵を発行できるプログラムを開発しました。



ただし、問題は主にルーターやVPNなどの組み込みシステムに影響し、本格的なサーバーには当てはまらないため、パニックに陥らないでください。 （いずれにせよ、これは間違いなく、 New York Timesが示唆しているように、電子商取引の委任状を失う理由にはなりません）。 残念ながら、ほぼすべてのメーカーからこの問題のあるデバイスが見つかりました。データのすべてのキーの4.1％を表す約200,000台のデバイスが、キーの生成に低エントロピーを使用したと考えられます。 デバイスによって生成された脆弱なキーは、これらのデバイスのクラス全体が適切な分析による攻撃に対して脆弱であることを示唆しています。



すべてのメーカーに連絡する前に脆弱なデバイスの完全なリストは提供しませんが、すでに公開されている資料を使用すると、攻撃を簡単に再現できます。 そのため、現在、お使いのデバイスが脆弱かどうかを判断するWebサイトを作成中です。

心配しないでください。銀行の鍵はほとんどの場合安全です。

SSLはインターネット上のすべての大規模サイトで使用されていますが、分析結果が示すように、これらのキーはこの投稿で説明されている問題の影響を受けません。



では、どのシステムが危険にさらされていますか？ 脆弱なキーのほとんどは、ルーターやファイアウォールなどの組み込みシステムで生成および使用され、銀行のWebサイトや電子メールでは使用されませんでした。 脆弱なSSLキーの1つだけが証明機関によって署名され、既に期限が切れています。 また、重複キーを使用して署名された証明書をいくつか見つけました。 脆弱なデバイスによって生成されたものもあれば、故意に弱いとサイト所有者によって署名されたものもあり、良い説明を思い付かないものもあります。



誰もが、組み込みシステムにはエントロピーに問題があることを知っています。 ただし、これまでは、これらの問題がインターネットに接続されている実際のデバイスでどのように一般的であるかは明確ではありませんでした。

キー生成

Webサイトとネットワークコンピューターは、公開鍵暗号システムを使用して識別します。 さらに、クライアントが接続したいクライアントであることをクライアントに証明するために、サーバーがクライアントに証明書を提供する場合の識別のタイプについて説明します。 攻撃者が秘密キーを知っている場合、攻撃者は実際のシステムになりすますことができ、ほとんどの場合、クライアントとサーバー間のトラフィックを解読できます。



RSAは、これらの目的で最も一般的に使用される暗号システムです。 RSA暗号システム保護は、多数の因数分解に基づいて構築されています。 RSA公開鍵は、一対の整数で構成されます：オープン指数eと、2つの大きな素数pとqの積であるモジュールNです。 攻撃者がNをpおよびqに戻すことができる場合、公開鍵で暗号化されたテキストを解読することもできます。 ただし、最速の因数分解アルゴリズムを使用しても、1024ビットモジュールを因数分解することはできませんでした。



キーセキュリティの重要な部分は、キー生成段階でのランダム入力の存在です。 この入力に十分なエントロピーがない場合、攻撃者はそれらを推測することができ、したがって、数Nの苦痛な因数分解なしで秘密鍵を取得できます。



最新のコンピューターおよびサーバーでは、キー生成プログラムは、マウス、キーボード、ハードドライブ、ネットワークイベント、その他の予測不可能なソースなど、多くの物理ソース（ほとんどの場合オペレーティングシステムを使用）から取得したランダムな入力データを使用します。 ただし、ソースが少ない場合は、エントロピーが不足し、キーは攻撃に対して脆弱になる可能性があります。 強いエントロピーを収集し、その強度をテストすることは、長年にわたって多くの脆弱性を生み出した非常に複雑な問題です。

問題の2つのバージョン

この問題がどれほど一般的かを調査するために、すべてのIPv4アドレスをスキャンし、各SSL証明書とSSHキーのコピーを収集しました。 鍵と証明書の収集には1日もかかりませんでした。最初に標準のnmapを使用して対応する開いているポートを持つホストを見つけ、次に最適化されたプログラムを使用してこれらのホストをポーリングしました。 合計で、580万のSSL証明書と1,000万のSSHキーを収集しました。



発見したように、エントロピーの問題は、2つの異なるタイプの弱点につながります。

公開鍵が重複しています。

すべてのRSAキーの約1％が繰り返し検出されましたが、これはおそらくエントロピーの問題が原因です。 2つのデバイスが同じ公開キーを持っている場合、それらも同じ秘密キーを持っています。 実際、同じキーを持つすべてのデバイスは同じ位置にあります-攻撃者はこれらの最も弱いデバイスを侵害し、他のすべてのユーザーにキーを取得できます。 この問題については長い間知られていましたが、これまでのところ、公開された文献にそれがどれほど広まっているかを記録した人はいませんでした。



エントロピーの問題により59,000個のキーが繰り返されていることを手動で確認しました。これは、すべての証明書の約1％、またはすべての自己署名証明書の2.6％に相当します。 また、すべてのデバイスの4.6％（585,000証明書）がデフォルトでインストールされた証明書を使用していることもわかりました。 これらのデバイスは低エントロピーで生成されたキーを使用しませんでしたが、それらの秘密キーはすべてのモデルで同じであるため、同じ攻撃を受けます。 多数のサイトが適切な条件で重複キーを使用しているため、ユーザーに危険をもたらさないため、これらすべてのキーを手動でチェックしました。

ファクタリング可能な公開キー。

さらに驚くべきことに、エントロピーの問題により、特別なアクセスなしにリモート攻撃者がインターネットで使用されるすべてのRSAキーのかなりの部分をファクタリングできることがわかりました。 SSL証明書のすべてのRSAキーの0.4％を分解できました。 これを行うために、インターネット上のRSA公開キーからモジュールのすべてのペアの最大公約数（gcd）を計算しました。



1724の共通の要因を特定しました。これにより、24.816のSSLキーと2422のSSHのキーファクタリングのための301の共通の要因をファクタリングできました。 これは、SSLに使用されるRSAキーのほぼ0.5％の秘密キーを計算できたことを意味します。 さらに、計算の仕組みを説明します。

特定の脆弱なデバイス

組み込みシステムは、多くの場合、最初のブート時に暗号化キーを生成します。その場合、すべてのステータスは工場で事前に決定できます。 この研究で説明されているように、エントロピーでこのような問題を引き起こす可能性があるもの。



SSL証明書の情報を使用して、脆弱なキーを生成する傾向があるデバイスの種類を特定することができました。 おそらく、キーを分解できない他の多くのデバイスもありますが、それらはまだ弱いキーを生成する傾向があり、頑固な攻撃者によって侵害される可能性があります。 私たちが特定できた脆弱なデバイスの完全なリストは、業界のほとんどすべての大手メーカーを含む30社以上のメーカーで構成されています。 問題のあるデバイスの種類には、ファイアウォール、ルーター、VPNデバイス、リモートサーバー管理用のデバイス、プリンター、プロジェクター、VOIP電話などがあります。



通知するまでデバイス名はリストしませんが、以下にいくつか例を示します。



ファイアウォールX ：

SSLデータの52.055ホスト

同一のキーを持つ6.730

分解可能なキーを使用した12.880



ユーザーレベルルーターY ：

SSLデータの26.952ホスト

9.345と同一のキー

因数分解可能なキーを使用した4.792



企業向けのリモートアクセスソリューションZ

SSLデータの1.648ホスト

同じキーで24

因数分解可能なキーで0

これはどうして起こるのでしょうか？

エントロピーの問題が、簡単に因数分解できる重要な問題にどのようにつながるかは完全には明らかではありません。 今、私たちは、より好奇心itive盛な読者にこれが起こる理由を説明します。



プログラマがRSA用のモジュールを生成する方法は次のとおりです。

prgn.seed(seed)

p = prgn.generate_random_prime()

q = generate_random_prime()

N = p*q





擬似乱数ジェネレーターの粒度に予測可能な値がある場合、いくつかの異なるデバイスが同じNモジュールを持つことができますが、良い擬似乱数ジェネレーターが共通の同じ係数で2つの異なるNモジュールを生成できるとは考えていません。



ただし、一部の実装では、セキュリティを強化するという考えで、素数pとqの生成の間に余分なランダム性も追加されます。

prgn.seed(seed)

p = prgn.generate_random_prime()

prgn.add_randomness(bits)

q = generate_random_prime()

N = p*q





最初のグレインが貧弱なエントロピーで生成された場合、これは、複数のデバイスが同じ因子pと異なる因子qで構成される異なるモジュールを持つという事実につながる可能性があります。 したがって、GCDを使用して両方のモジュールを分解できます：p = gcd（N1、N2）。



OpenSSLでのRSA鍵生成は次のように機能します。エントロピープールからのランダムビットを使用して素数pとqを生成するたびに、現在の秒数がプールに追加されます。 すべてではありませんが、多くの脆弱なキーは、OpenSSLとOpenSSHを使用して生成され、OpenSSLを使用してRSAキーを生成します。

すべてのキーペアのGCD計算

モジュールN1とN2の RSAペアに同じ係数がある場合、gcdを使用して両方のモジュールを単純に因数分解できます。 デスクトップコンピューターでは、2つの1024 RSAモジュールのgcd計算操作に約17マイクロ秒かかります。



数学の傾向がある人のために、このアイデアを使用して多数のキーを因数分解する方法を説明します。



鍵分解の簡単なアプローチには、RSAモジュールの各ペアのgcdの計算が含まれます。 しかし、これらの計算にかかる時間を見積もると、デスクトップコンピューターで約24年かかります。



代わりに、2005年にJournal of Algorithmsで公開されたDan Bursteinのアイデアを使用します。これにより、整数のグループを素数に分解でき、わずか数時間でPythonの実装を使用して計算を実行できます。 このアルゴリズムは大きな秘密ではありません。公開された多数の作品がアルゴリズムの改善に取り組みました。



この問題の主な数学的レビューは、次の式を使用して、他のすべてのモジュールと一緒にモジュールN1の gcdを計算できることです。

gcd(N1, N2 ... Nm) = gcd(N1, (N1 * N2 * ... Nm mod N1^2)/N1)





大きな問題は、この方程式の誤算を迅速に行う方法です。この計算の最初のステップは、すべてのキーの積である729百万桁の数字を見つけることです。 シングルコアプロセッサでは18時間ですべてのSSLデータを分解でき、4コアプロセッサでは4時間でSSHデータを分解できました。

おわりに

これはもちろん問題ですが、普通のユーザーが心配すべき問題ではありません。 ただし、組み込みシステムのメーカーには多くの作業が必要であり、一部のシステム管理者が懸念する必要があります。 これは、セキュリティ分野の人々への目覚めの呼びかけとして、また、すべての人の前に脆弱性が隠されていることのすべてを思い出させてくれるはずです。