新たな攻撃により潜在的な暗号化アルゴリズムが簡単に破壊される

Apr 14, 2023

ダン・グッディン、アルス・テクニカ

量子コンピューター時代のデータ保護を目的とした米国政府の継続的なキャンペーンにおいて、従来型の 1 台のコンピューターを使用して第 4 ラウンドの候補を完全に破った新たな強力な攻撃は、次世代の暗号化アルゴリズムの標準化に伴うリスクを浮き彫りにしました。

この記事は元々、テクノロジー ニュース、テクノロジー ポリシー分析、レビューなどの信頼できる情報源である Ars Technica に掲載されました。 Ars は WIRED の親会社であるコンデナストが所有しています。

先月、米国国立標準技術研究所 (NIST) は、量子からの攻撃に耐えることができない RSA、Diffie-Hellman、楕円曲線 Diffie-Hellman などのアルゴリズムに代わる 4 つのポスト量子コンピューティング暗号化アルゴリズムを選択しました。コンピューター。

同様の動きで、NIST はさらなるテストを保留中の潜在的な代替アルゴリズムとして 4 つの追加アルゴリズムを提案し、そのうちの 1 つ以上がポスト量子の世界で適切な暗号化代替手段になる可能性があることを期待しています。 新しい攻撃は、後者の 4 つの追加アルゴリズムの 1 つである SIKE を破壊します。 この攻撃は、NIST によって承認された標準として選択された 4 つの PQC アルゴリズムには影響を与えません。これらのアルゴリズムはすべて、SIKE とはまったく異なる数学的手法に依存しています。

SIKE (Supersingular isogeny key encapsulation の略) は、ルーヴェン大学のコンピューター セキュリティおよび産業暗号化グループの研究者によって週末に発表された研究結果のおかげで、現在は実用化されていない可能性があります。 「SIDH に対する効率的なキー回復攻撃 (暫定版)」と題されたこの論文では、複雑な数学と 1 台の従来型 PC を使用して、SIKE で保護されたトランザクションを保護する暗号化キーを回復する手法について説明しています。 プロセス全体に必要な時間はわずか 1 時間程度です。 この偉業により、研究者のワウター・カストリック氏とトーマス・デクル氏はNISTから5万ドルの報奨金を受け取る資格がある。

「新たに明らかになった弱点は、明らかにSIKEにとって大きな打撃だ」とウォータールー大学教授でSIKEの共同発明者であるデイビッド・ジャオ氏は電子メールで書いた。 「その攻撃は本当に予想外だった。」

1970 年代の公開キー暗号化の出現は、会ったことのない当事者間でも、敵が解読できない暗号化されたマテリアルを安全に取引できるようにするため、大きな進歩でした。 公開キー暗号化は非対称キーに依存しており、メッセージの復号化には 1 つの秘密キーが使用され、暗号化には別の公開キーが使用されます。 ユーザーは自分の公開鍵を広く利用できるようにします。 秘密鍵が秘密のままである限り、スキームは安全なままです。

実際には、公開キー暗号化は扱いにくいことが多いため、多くのシステムはキーのカプセル化メカニズムに依存しています。これにより、これまで会ったことのない当事者が、インターネットなどの公開媒体を介して対称キーに共同で同意することができます。 対称鍵アルゴリズムとは対照的に、現在使用されている鍵のカプセル化メカニズムは、量子コンピューターによって簡単に破られます。 SIKE は、新たな攻撃が行われる前は、超特異点アイソジェニー グラフとして知られる複雑な数学的構造を使用することで、このような脆弱性を回避すると考えられていました。

SIKE の基礎となるのは、SIDH (Supersingular isogeny Diffie-Hellman の略) と呼ばれるプロトコルです。 週末に発表された研究論文は、SIDHが1997年に数学者のエルンスト・カニによって開発された「接着分割」として知られる定理や、同じく数学者のエヴェレット・W・ハウ、フランク・レプレヴォスト、ビョルンによって考案されたツールに対してどのように脆弱であるかを示している。新しい技術は、2016 年の論文で説明された GPST 適応型攻撃として知られるものに基づいています。 最新の攻撃の背後にある数学は、数学者以外のほとんどの人には理解できないことが保証されています。 ほぼこれに近いものを次に示します。

「この攻撃は、SIDH に補助点があり、秘密の等質性の程度が既知であるという事実を悪用しています」とオークランド大学の数学教授で GPST 適応攻撃の「G」である Steven Galbraith 氏は短い記事で説明しました。新たな攻撃について。 「SIDH の補助ポイントは常に迷惑であり、潜在的な弱点であり、フォールト攻撃、GPST 適応攻撃、ねじれポイント攻撃などに悪用されてきました。」

ローレン・グッド

ローレン・グッド

ジュリアン・チョッカトゥ

ウィル・ナイト

数学を理解することよりも重要なことは、IEEE 会員でメリーランド大学コンピューターサイエンス学部教授のジョナサン・カッツ氏は電子メールで次のように書いている。「この攻撃は完全に古典的であり、量子コンピューターをまったく必要としない」。

SIKE は、今年無効化された NIST 指定の PQC 候補としては 2 番目です。 Cryptomathicによると、IBMのポスドク研究員であるWard Beullens氏は2月、安全性を備えた暗号署名スキームであるRainbowを破った研究を発表し、「有限体上で多変量2次方程式の大規模系を解く問題の難しさに依存している」という。

NIST の PQC 交換キャンペーンは 5 年間実施されています。 簡単な歴史は次のとおりです。

第3ラウンド中にレインボーが落ちたが、SIKEは第4ラウンドまで勝ち上がった。

カッツ氏はこう続けた。

おそらくこれが、古典的なアルゴリズムを使用して完全に破られる前に、NIST 審査プロセスの第 3 ラウンドまで進んだスキームの過去 6 か月で 2 番目の例であることは、おそらく少し懸念されることです。 (以前の例は、2 月に破られた Rainbow です。) 4 つの PQC スキームのうち 3 つは、正確な難易度がよく理解されていない比較的新しい仮定に依存しているため、最新の攻撃が示しているのは、おそらくまだ慎重/保守的である必要があるということです。標準化プロセスが進むにつれて。

私は SIKE の共同発明者である Jao 氏に、開発の比較的後期段階になって初めてこの弱点が明らかになった理由を尋ねました。 彼の答えは洞察力に富んでいました。 彼は言った：

この攻撃に 1990 年代から 2000 年代に発表された数学が使用されているのは事実です。 ある意味、この攻撃には新しい数学は必要ありません。 それはいつでも気づくことができたでしょう。 この攻撃の予期せぬ側面の 1 つは、種数 2 の曲線を使用して楕円曲線 (種数 1 の曲線) を攻撃することです。 2 種類の曲線間の関係はまったく予想外です。 私が言いたいことを説明する例を挙げると、数十年にわたり、種数 2 曲線に基づくアプローチを使用しようとした人も含め、人々は正楕円曲線暗号を攻撃しようとしてきました。 これらの試みはどれも成功していません。 したがって、同質遺伝子の領域で成功しようとするこの試みは、予想外の展開となる。

一般に、数学文献には出版されているものの、暗号学者にはよく理解されていない奥深い数学がたくさんあります。 私は、暗号学の研究をしているものの、数学については必要以上に理解していない多くの研究者のカテゴリーに自分自身を分類しています。 したがって、既存の理論数学がこれらの新しい暗号システムに適用できることを認識している人だけが必要な場合もあります。 それがここで起こったのです。

NIST に提出された SIKE のバージョンでは、単一のステップでキーを生成しました。 SIKE の可能な変形は、2 つのステップを踏むように構築できます。 Jao 氏は、この後者の亜種は、この破損を引き起こす数学的影響を受けにくい可能性があると述べています。 しかし今のところ、少なくとも現在の運営においては、SIKE は死んでいる。 残り3名の候補者の日程は現時点では不明。

このストーリーは元々 Ars Technica に掲載されました。