2人の数学者が単一PCで1時間でSIKE耐量子暗号を破る

2022年8月、NISTが最終的にRSAとDiffie-Hellmanを置き換える4つの耐量子暗号アルゴリズムを選定してから数週間後、KUルーヴェンのコンピュータセキュリティ・産業暗号グループの研究者らは「An Efficient Key Recovery Attack on SIDH」を発表した。これは複雑な数学と単一の従来型PCを用いて約1時間でSIKEで保護された取引を守る鍵を復元する手法である。論文の著者であるWouter CastryckとThomas Decruは、Microsoftからの5万ドルの報奨金の対象となった。

SIKE — Supersingular Isogeny Key Encapsulation — は、NISTが潜在的なバックアップとして推進した4つの追加アルゴリズムの1つであり、超特異同種写像グラフに秘密を符号化することで量子コンピュータに耐性があると考えられており、その構成は長らくエレガントに困難と見なされてきた。新たな攻撃は、その基盤プロトコルであるSIDH（Supersingular Isogeny Diffie-Hellman）が、数学者Ernst Kaniが1997年に証明した定理であるglue-and-split、および2000年のHowe、Leprévost、Poonenによるツールに、既知のGPST適応攻撃を基盤として組み合わせることで脆弱であることを示した。

その重要性は即座に明らかになった。SIKEは標準化の競争から事実上脱落する可能性が高く、一方NISTが標準として選定した4つのアルゴリズムは完全に異なる数学に基づいており、影響を受けなかった。ウォータールー大学の教授でSIKEの共同発明者であるDavid Jaoは、この弱点を「明らかに大きな打撃」と呼び、攻撃を「本当に予想外」と述べた。

SIDHは常に既知の同種写像次数を持つ補助点を伴って提供されていた。1997年の定理（glue-and-split）は、その設計上の利便性を鍵復元の機械に変えた。

この攻撃は、1997年以来ずっと目の前に隠れていた四半世紀前の数学を再利用した。

量子コンピュータは必要なかった — SIKEが設計された脅威である — 必要なのは1つのコアと1時間だけだった。

欠陥は構造的だった。補助点と既知の同種写像次数がプロトコルの設計に組み込まれていた。

この結果は、発表から数日以内に政府の標準化競争の順位を変えた。

プロトコルに設計された利便性は潜在的な脆弱性である。スキームが使いやすさのために公開する補助データは、まさに攻撃者が必要とする手がかりとなり得る。

NISTの代替候補であったSIKEは事実上検討対象から排除された。すでに選定されていた4つの耐量子標準は異なる数学に依拠しており、影響を受けなかった。研究者らはMicrosoftの5万ドルの報奨金を受け取る立場にあり、SIKEの共同発明者であるDavid Jaoは攻撃の深刻さを公に認めた。