デスクトップコンピュータ10年、シングルコア量子暗号アルゴリズムを1時間で解読、暗号学者「突然すぎる」

将来の量子コンピューターは、現代の暗号をすぐに破ってしまう可能性があります。したがって、数学者や暗号学者は、量子コンピューター攻撃に対抗する適切な新しい暗号化アルゴリズムを探してきました。既存の暗号アルゴリズムに対する量子コンピュータ攻撃に対抗できるこの新世代の暗号アルゴリズムは、「ポスト量子暗号 (PQC、ポスト量子暗号)」アルゴリズムと呼ばれます。

しかし最近、ベルギーのルーヴェン大学の研究者らは、有望な PQC 暗号化アルゴリズムがわずか 1 時間で完全に解読できることを発見しました (一部のバージョンはわずか 4 分で解読できる)。問題は、この記録はハイエンド コンピューターによって樹立されたものではなく、10 年前の CPU を搭載し、シングル コアで動作するデスクトップ コンピューターによって樹立されたということです。研究者らは、今回の驚くべき失敗は、ポスト量子暗号が採用される前に乗り越えなければならない多くのハードルを浮き彫りにしていると述べている。

論文リンク: https://eprint.iacr.org/2022/975

理論的には、量子コンピューターは、従来のコンピューターでは解決するのに多大な時間がかかる問題を迅速に解決できます。たとえば、現代の暗号化は、大きな数の因数分解など、複雑な数学的問題を処理する際に古典的なコンピューターが直面する極めて困難な点に大きく依存しています。そして、量子コンピューターは原理的には、この暗号化技術を即座に解読できるアルゴリズムを実行できる可能性がある。

この脅威に対抗するために、世界中の暗号学者は 20 年をかけてポスト量子暗号化アルゴリズムを設計してきました。これらのアルゴリズムは、量子コンピューターでも古典コンピューターでも解決するのが難しい新しい数学的問題に基づいています。

米国国立標準技術研究所 (NIST) などの機関の研究者は、何年にもわたって、どの PQC アルゴリズムが世界が採用できる新しい標準となるべきかを研究してきました。同庁は2016年にPQCアルゴリズムの候補を探していると発表し、2017年には82件の提案を受け取った。その後、3 ラウンドのレビューを経て、NIST は間もなく標準となる 4 つのアルゴリズムと、候補として次のラウンドのレビューに入るさらに 4 つのアルゴリズムを発表しました。

レビューはまだ終わっていません。候補の 1 つがダウンし、10 年前のデスクトップによって侵害されました。このアルゴリズムは SIKE (Supersingular Isogeny Key Encapsulation) と呼ばれ、Microsoft、Amazon、Cloudflare などの企業によって研究されています。ミシガン大学（アナーバー）の暗号学者クリストファー・パイカート氏は、「この攻撃はあまりにも突然に行われたので、特効薬（非常に有効な解決策）だった。」と述べた。何？

SIKE は、楕円曲線を含む PQC アルゴリズムのファミリーです。 「楕円曲線は数学者たちの長い間研究対象でした」とNISTの数学者ダスティン・ムーディは言う。 「これらは、y^2 = x^3 Ax B のような方程式で記述されます。A と B は数値です。たとえば、楕円曲線は y^2 = x^3 3x 2 になります。」

1985 年に、「数学者たちは、現在広く普及している楕円曲線を含む暗号システムを作成する方法を考え出した」とムーディ氏は述べました。 「しかし、これらの楕円曲線暗号システムは、量子コンピューターからの攻撃に対して脆弱です。」

2010 年頃、研究者たちは、暗号化で楕円曲線を使用する新しい方法を発見しました。この新しいアイデアは、量子コンピューターによる攻撃に対して脆弱ではないと考えられています。

この新しい方法は、楕円曲線上の 2 つの点を追加して、楕円曲線上の別の点を取得する方法の問題に基づいています。アルゴリズムの名前にある「アイソジェニー」とは、相同性、つまり加法則を維持するある楕円曲線から別の楕円曲線へのマッピングを意味します。

「このマッピングを十分に複雑にすると、データ暗号化の課題は、2 つの楕円曲線が与えられた場合、それらの間の相同性を見つけるのが難しくなるということです」と研究共同者は述べています。著者のトーマス・デクル氏は、ベルギーのルーヴェン大学の数学暗号学者です。

SIKE は、Super Singular Homology Diffie-Hellman (SIDH) 鍵交換プロトコルに基づく相同ベースの暗号化形式です。 「SIDH/SIKE は、最も初期の実用的なオリジンベースの暗号化プロトコルの 1 つです」と Decru 氏は述べています。

SIKE の弱点の 1 つは、これです。SIKE が機能するためには、追加情報、つまり補助ツイスト ポイントを一般に提供する必要があります。 「敵対者はしばらくの間、この追加情報を悪用しようとしてきたが、SIKEを倒すためにそれを利用することに成功していない」とムーディ氏は述べた。 「しかし、この新しい論文は方法を見つけ、かなり高度な数学的手法を使用しています。」

新しい攻撃を説明するために、Decru 氏は、楕円曲線は 1 次元のオブジェクトですが、数学では楕円曲線は 2 次元またはその他の次元のオブジェクトとして視覚化できると述べました。これらの一般化されたオブジェクト間のホモログを作成することもできます。

25 年前の定理を適用することにより、新しい攻撃は SIKE によって公開された追加情報を使用して 2 次元の相同性を構築します。この相同性を使用して、SIKE がメッセージを暗号化するために使用するキーを再構築できます。

「私にとって最も驚いたのは、この攻撃がどこからともなく突然発生したように見えたことです」とメリーランド大学カレッジパーク校の暗号学者ジョナサン・カッツ氏は語った。同氏は新たな研究には関与していないが、「SIKEに弱点があることを示すこれまでの結果はほとんどなかったが、この結果は完全な鍵を発見したため、突然SIKEに完全に破壊的な攻撃を与えた。そして、それは非常に早く発見された」と述べた。

10 年以上にわたって攻撃され、4 分で解読された

#上記の新しい攻撃方法に基づくアルゴリズムを使用して、研究者らは次のことを発見しました。 10 年前の CPU (Intel Xeon CPU E5-2630v2) を搭載したデスクトップ コンピュータは、特定の SIKE アルゴリズムによって保護されたキーを見つけるのに少なくとも 4 分しかかかりません。このブレークスルーは NIST の量子セキュリティ レベル 1 に到達すると考えられています。標準の SIKE アルゴリズムもわずか 62 分しかかかりませんでした。これらの実験は CPU の 1 つのコアで実行されます。

# 「通常、暗号システムに対する重大な攻撃は、そのシステムが提案された直後、またはそのシステムが最初にみんなの注目を集め始めたときに発生します。 「SIDH が最初に提案されて以来、SIDH/SIKE については多くの研究が行われてきました。時間が経つにつれて、攻撃は徐々に強くなるか、システムを著しく弱体化させます。しかし、この攻撃では何の前触れもなく、暗号システムは突然完全に破られました。」とパイカート氏は述べています。

研究者は 10 年以上にわたって SIKE をテストしてきましたが、SIKE は標準の 1 つとして選ばれていませんでした。理由は、新しすぎて十分に研究されていないのではないかという懸念です。オークランド大学の数学者スティーブン・ガルブレイス氏は、「人々はSIKEが大規模な攻撃の危険にさらされているのではないかと心配していましたが、その判断は正しかったことが分かりました。では、なぜこれまでSIKEの脆弱性が検出されなかったのでしょうか?」と述べています。ガルブレイス氏は、新たな攻撃が「非常に高度な数学を適用している」ことが重要な理由だと考えている。 Katz 氏もこれに同意し、「PQC の基礎となる数学と、必要な暗号化の知識の両方を持っている人は、世界中で 50 人もいないのではないかと思います。」

さらに、PQC スタートアップの Sandbox も次のように述べています。 AQ の未確認動物学者デイビッド ジョセフはかつて次のように述べています。「同一起源問題は、実装と理論の両方の観点から見ても『非常に難しい』ので、その根本的な欠陥が後で発見される可能性が高くなります。」 #さらに、「NIST が数ラウンドのスクリーニング レビューを実施する前に、分析に利用できる PQC アルゴリズムが多数あるため、研究努力が薄れてしまうことにも注意する必要があります。そして、数ラウンドのスクリーニングの後、研究者は次のことに集中することができました。」小さなアルゴリズムのセットです」とジョセフ氏は語った。

SIKE の発明者の 1 人であり、カナダのウォータールー大学教授である David Jao 氏は次のように述べています。「この新しい結果は素晴らしい成果だと思います。最高の賞賛です。最初は、SIKE が数学的に非常にエレガントなスキームだったため、解読されたのが残念でした。"

"しかし、新しい発見は単に科学の仕組みを反映しています。当時は誰もが大丈夫だと思っていたシステムを思いつき、それを分析した結果、誰かがその弱点を発見した。弱点を見つけるのに10年以上かかったのは異例だが、それ以外はこの問題はそうではない通常の科学の進歩の範囲を超えています」とデビッド・ジャオ氏は付け加えた。

Jao 氏の見解では、SIKE はまだ広く導入されていないため、現在クラックされているのは良いことだと考えています。

SIKE がクラックされた場合、それは何を意味しますか?

SIKE は、今年クラックされた 2 番目の NIST PQC 候補アルゴリズムです。今年2月、チューリッヒのIBM Researchの暗号学者ウォード・ベレンス氏は、NISTの第3回審査に参加しているレインボーアルゴリズムを自分のラップトップを使って解読できる可能性があることを明らかにした。 「これは、すべての PQC オプションにはさらなる研究が必要であることを示唆しています」とカッツ氏は述べた。

しかしムーディ氏は、SIKEは解読されたものの、CSIDHやSQIsignなどの相同性に基づく他の暗号システムは解読されていないと指摘し、「相同性に基づく暗号は死んだものだと考える人もいるかもしれないが、これは事実とは程遠く、相同性ベースの暗号化にはまだ研究すべきことがたくさんあると思います」とデクルー氏は語った。

さらに、この新しい研究は NIST の PQC 研究のレベルを反映していない可能性があります。 Decru が指摘したように、NIST が受け取った 82 件の提案の中で、SIKE は唯一の相同性ベースの暗号システムであり、同様に、Rainbow は、それらの提案の中で唯一の多変量アルゴリズムでした。

NIST によって「標準」として採用されたアルゴリズム、または第 4 回の審査に入っているアルゴリズムは、暗号学者によって長い間研究および分析されてきた数学的アイデアに基づいている、とガルブレイス氏は述べました。 「それは、それらが安全であることを保証するものではありません。それは、単に、より長い間攻撃に耐えることを意味するだけです。」ムーディ氏もこれに同意し、「常に驚くべきことが発見されます。暗号システムを解読するための画期的な結果が得られます。どのような暗号システムについても、絶対的なものはありません。」セキュリティの保証。最も言えることは、多くの賢明な人々が多くの研究を行った結果、誰も暗号システムの抜け穴を発見できなかったということです。」

「私たちのプログラムは、次のことを可能にするように設計されています。」攻撃と亀裂に対応します」とムーディ氏は語った。 「私たちはあらゆる評価ラウンドでそれらを観察してきました。それが安全性への信頼を得る唯一の方法です。」ガルブレイス氏も同意し、このような研究は「効果を上げている」と指摘した。

それにもかかわらず、「Rainbow と SIKE の両方の終焉により、NIST のポスト量子標準化プロセスから生まれる勝者のためのバックアップ計画の必要性について、より多くの人が真剣に考えるようになると思います。 」とデクルは言った。 「数学的な概念やスキームのみに依存するのは危険すぎるかもしれません。これは NIST 自身の考えでもあります。彼らの主なスキームはおそらく格子暗号 (格子ベース) に基づいていますが、選択を準備するために非格子暗号スキームを望んでいます。」

Decru 氏は、他の研究者が SIDH/SIKE の新しいバージョンの開発を開始しており、これによりこの新しいタイプの攻撃を防ぐことができると考えていると述べました。 「攻撃がエスカレートし、人々がSIDH/SIKEにパッチを適用しようとしたため、何が起こるか予想していました」とDecru氏は語った。

要約すると、この新たな攻撃の出発点は、「暗号化とはまったく関係のない」定理であり、「暗号化を理解するために純粋に数学的な基礎研究を行うことの重要性を明らかにしている」ことが判明しました。暗号システム」とガルブレイス氏は語った。

デクル氏もこれに同意し、「数学では、すべてがすぐに当てはまるわけではありません。現実の状況にはほとんど当てはまらないものもあります。しかし、これは、私たちが適用すべきではないという意味ではありません」と述べています。研究によって、これらのより曖昧な問題が解決されるようにしましょう。」

以上がデスクトップコンピュータ10年、シングルコア量子暗号アルゴリズムを1時間で解読、暗号学者「突然すぎる」の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。