ポスト量子暗号 – 新しいアルゴリズムは「60 分でなくなった」

私たちは PQC について書いてきました。 量子後暗号、数回前に。

いわゆる量子コンピューティングに関する過去数年間のメディアの興奮をすべて逃した場合は…

…これは (一部の専門家がおそらく無謀な単純化と見なすことをご容赦ください)、追跡できるコンピューティング デバイスを構築する方法です。 複数の可能な結果 同時に計算します。

細心の注意を払い、おそらく少し運が良ければ、考えられるすべての結果を試してテストすることなく、ある種のアルゴリズムを書き直して正しい答えを導き出すか、少なくとも多数の間違った答えを完全に破棄できることを意味します。一つずつ。

適切に強力で信頼性の高いものを実際に構築できると仮定すると、量子コンピューティング デバイスを使用して、XNUMX つの興味深い暗号解読の高速化が可能です。

• グローバーの量子探索アルゴリズム。 通常、ランダムに並べられた一連の回答を検索して、自分の回答がリストにあるかどうかを確認したい場合、最悪の場合、決定的な回答を得る前にリスト全体を掘り下げることを期待します。 たとえば、ドキュメントのスクランブルを解除するための 128 ビット AES 復号化キーを見つけたい場合は、可能なすべてのキーのリストを検索する必要があります。 000..001, ..2, ..3など、 FFF..FFF (16バイト分 FF)、問題を確実に完了するために。 つまり、2 つすべてを試すには予算が必要です。¹²⁸ 正しいキーを見つける前、または存在しないと判断する前に、可能性のあるキーを調べます。 しかし、グローバーのアルゴリズムは、大きくて十分に強力な量子コンピューターがあれば、同じ偉業を達成できると主張しています。 平方根 理論上はわずか 2 時間でコードを解読⁶⁴ 代わりに試みます。
• Shor の量子分解アルゴリズム。 現代のいくつかの暗号化アルゴリズムは、59 つの大きな素数を掛け合わせるとすぐに実行できるという事実に依存していますが、元の 87 つの数にそれらの積を元に戻すことはまったく不可能です。 この感覚をつかむために、ペンと紙を使って 5133×4171 を掛けてみてください。 取り出すのに 43 分ほどかかるかもしれませんが (答えは 97 です)、それほど難しくはありません。 今度は別の方法を試してください。 たとえば、600 を 600 つの因数に戻します。 もっと難しい！ (300×XNUMX です。) XNUMX 桁の数字でこれを行うことを想像してみてください。 大まかに言えば、ジャックポットに当たるか、答えがないことがわかるまで、XNUMX 桁の数字を可能な限り XNUMX 桁の素数で割ろうとすることになります。 ただし、Shor のアルゴリズムは、この問題を 対数 いつもの努力の。 したがって、2048 桁の 1024 進数の因数分解は、2047 ビット数の因数分解の XNUMX 倍ではなく、XNUMX ビット数の因数分解の XNUMX 倍の時間しかかからず、大幅な高速化を示します。

脅威に対抗する

グローバーのアルゴリズムによる脅威は、使用している数値を 256 乗してサイズを大きくするだけで対抗できます。つまり、暗号化ハッシュまたは対称暗号化キーのビット数を 512 倍にすることができます。 (言い換えれば、SHA-XNUMX が現時点で問題ないと思われる場合は、代わりに SHA-XNUMX を使用すると、PQC 耐性のある代替手段が提供されます。)

しかし、Shor のアルゴリズムはそう簡単に打ち負かすことはできません。

2048 ビットの公開鍵は、単純に 2 乗するだけでなく、指数関数的にサイズを大きくする必要があるため、2048×4096=2 ビットの鍵の代わりに、不可能なサイズ XNUMX の新しい鍵が必要になります。²⁰⁴⁸ ビット…

…または、Shor のアルゴリズムが適用されない、まったく新しい種類のポスト量子暗号化システムを採用する必要があります。

米国の標準化団体 NIST は、 PQC「競争」 遅い2017以来。

プロセスはすべての人に開かれており、すべての参加者を歓迎し、すべてのアルゴリズムを公開し、公開精査を単に可能というだけでなく、 積極的に奨励:

提案を求めます。 [2017-11-30 終了]. […] 新しい公開鍵暗号化標準は、世界中で利用可能で、政府の機密情報を保護できる、XNUMX つまたは複数の追加の未分類の公開デジタル署名、公開鍵暗号化、および鍵確立アルゴリズムを指定することを意図しています。量子コンピューターの出現後を含め、予見可能な未来まで。

XNUMX回の提出と議論の後、 NISTが発表、2022 年 07 月 05 日に、すぐに有効な「標準」と見なされる XNUMX つのアルゴリズムを選択したことを発表しました。 CRYSTALS-KYBER, CRYSTALS-Dilithium, FALCON, SPHINCS+.

最初のXNUMXつ （CRYSTALS-KYBER) と呼ばれるものとして使用されます 鍵合意メカニズム (KEM) では、公開通信チャネルの両端が、セッションに相当するデータを秘密裏に交換するための XNUMX 回限りの秘密暗号化キーを安全に作成します。 （簡単に言えば： スヌーパーはキャベツの千切りを手に入れるだけなので、会話を盗聴することはできません.)

他の XNUMX つのアルゴリズムは、 デジタル署名、これにより、最後に取得したデータが、送信者がもう一方に入力したものと正確に一致することを確認できるため、改ざんを防ぎ、完全性を保証できます. （簡単に言えば： 誰かがデータを破損したりいじったりしようとすると、.)

より多くのアルゴリズムが必要

新しい標準の発表と同時に、NIST は次のことも発表しました。 第四ラウンド 可能な代替 KEM として、さらに XNUMX つのアルゴリズムを提案します。 (この記事の執筆時点では、既に XNUMX つの承認済みデジタル署名アルゴリズムから選択できますが、公式の KEM は XNUMX つだけであることを忘れないでください。)

これらが： BIKE, Classic McEliece, HQC & SIKE.

興味深いことに、 McEliece アルゴリズム 1970 年代に、NIST のコンテストがすでに始まっていた 2019 年に亡くなったアメリカの暗号学者 Robert Mc Eliece によって発明されました。

しかし、当時人気のあった代替アルゴリズムである Diffie-Hellman-Merkle アルゴリズム (DHM、または単に DH) と比較して、膨大な量のキー マテリアルが必要だったため、普及することはありませんでした。

残念ながら、XNUMX つのラウンド XNUMX アルゴリズムの XNUMX つ、つまり SIKE、ひびが入ったようです。

と題された脳ねじれ論文で SIDH に対する効率的なキー回復攻撃 (暫定版)、ベルギーの暗号学者 Wouter Castryk と Thomas Decru は、SIKE アルゴリズムに致命的な打撃を与えたようです。

ご参考までに、SIKE は 超特異アイソジェニー キーのカプセル化、およびSIDHはの略です 超特異アイソジェニー Diffie-Hellman、特定の用途 SIKEアルゴリズム これにより、通信チャネルの両端が DHM のような「クリプトダンス」を実行して一連の公開データを交換し、各端がプライベートな値を導出して XNUMX 回限りの秘密の暗号化キーとして使用できるようにします。

ここでは、攻撃について説明するつもりはありません。 この論文が主張していること、つまり次のことを繰り返します。

非常に大まかに言えば、ここでの入力には、キー確立クリプトダンスの参加者の XNUMX 人によって提供された公開データと、プロセスで使用される事前に決定された (したがって公に知られている) パラメータが含まれます。

しかし、抽出された出力 (と呼ばれる情報) アイソジェニ φ 上記) は、プロセスの決して明らかにされない部分、いわゆる秘密鍵であると想定されています。

言い換えれば、鍵のセットアップ中に公然と交換されたデータなどの公開情報だけから、暗号学者は参加者の XNUMX 人の秘密鍵を回復できると主張します。

そして、いったん私の秘密鍵を知ってしまうと、簡単に検出されずに私になりすますことができるため、暗号化プロセスは破られます。

どうやら、キー クラッキング アルゴリズムは、通常のラップトップで見られるような処理能力を備えた単一の CPU コアを使用して、その作業を行うのに約 XNUMX 時間かかります。

これは、NIST の暗号化セキュリティの基本グレードであるレベル 1 を満たすように構成されている場合、SIKE アルゴリズムに反します。

何をするか？

何もない！

（それは朗報です。）

論文の著者が示唆するように、彼らの結果はまだ暫定的なものであることに注意した後、 「現在の状況では、公的に生成されたベースカーブのSIDHは完全に破られているようです。」

（それは悪いニュースです。）

ただし、SIKE アルゴリズムがまだ正式に承認されていないことを考えると、この特定の攻撃を阻止するように適応させるか (作成者が可能性を認めている可能性があります)、単に完全に削除することができます。

最終的に SIKE に何が起こっても、これは、独自の暗号化アルゴリズムを発明しようとすることが危険に満ちている理由を思い起こさせるものです。

これは、独自の暗号化システムが必要な理由の明確な例でもあります。 アルゴリズム自体の機密性に依存する セキュリティを維持することは、2022年にはまったく受け入れられません.

SIKE などの PQC アルゴリズムが、公開精査の対象となるように具体的に開示されたにもかかわらず、XNUMX 年以上にわたって世界中の専門家による説得と精査に耐えていたとしたら…

…なら、自作の非表示の暗号化アルゴリズムが実際に公開されたときにどれだけうまく機能するかを自問する必要はありません!

---