カリフォルニア大学サンディエゴ校とフランスINRIAの研究チームは、ハードウェアセキュリティモジュール(HSM)内に保存された1,024ビット鍵のRSA署名を、鍵を一切取り出すことなく偽造した。HSMは、機関型カストディアンが暗号鍵を保護するために使用する耐タンパ性デバイスの一種である。

研究チームは9月20日、IACR(国際暗号学研究協会)のCryptology ePrint Archiveに提出した論文でこの手法を詳述した。攻撃の実行には約2^32回の署名リクエスト(約40億回)と、およそ1,380CPUコア年の計算を要した。著者らは、この手法がパディングに依存する現代のRSA運用のほとんどに即時の脅威を与える可能性は低いと述べている。

この結果はビットコインやイーサリアムの解読ではない。ビットコインは楕円曲線デジタル署名アルゴリズム(ECDSA)で取引に署名し、その曲線はSchnorr署名もサポートする。イーサリアムおよびその他の主要ブロックチェーンのほとんども同じ楕円曲線方式を使用している。今回の研究の対象はRSA(Rivest-Shamir-Adleman暗号)であり、まったく異なる署名方式である。

研究者らは、秘密鍵を保存し要求に応じて署名する耐タンパ性デバイスであるハードウェアセキュリティモジュールに対してこの手法を実証した。攻撃を可能にするため、彼らはモジュールのFIPSモード(暗号モジュールに関する米国連邦情報処理標準の認証を受けた設定)を無効にして、整形されていない生の数値に署名するにし、独自のテスト鍵を使用した。その後、デバイスに約40億個の任意の数値への署名を求め、応答に数学的解析を加えて偽造署名を構築した。暗号研究者は、このような照会可能な標的を「オラクル」、つまり攻撃者の選択した入力に応答し、その応答に悪用可能なパターンが隠れていることがあるシステムと呼ぶ。言い換えれば、この結果は認証済みの設定が破られたことを示すものではなく、その設定を先に無効化することが前提であった。

この仕組みは、決して開かないがドアの下に差し込まれた白紙に何でも判を押してくれる金庫室に似ている。十分な回数の押印を要求すれば、自分で判を複製する方法を学べるということだ。

この発見は、鍵が実際にどのように保護されているかに対するストレステストである。BitGoによれば、機関型カストディアン事業者は、秘密鍵がデバイスの外に存在しないようにするためにハードウェアセキュリティモジュールを使用している。今回の実証では鍵はモジュールから一度も出ていない。それにもかかわらず、署名は偽造された。

デジタル署名の役割とは

ユーザーが取引を確認するたびに、ウォレットは保持者の秘密鍵でそれに署名する。このデジタル署名は、鍵の保持者が取引を承認したこと、および途中でメッセージが改ざんされていないことの証明となる。

RSAはその証明を構築する方法の一つで、1977年にRon Rivest、Leonard Adleman、Adi Shamir(頭字語の「S」)によって考案された。中核となる考え方は、2つの巨大な素数の掛け算は容易だが、その積を再び分解する作業(素因数分解と呼ばれる)は極めて困難であるというものだ。著者らは、RSAのセキュリティは一般にこの困難性に基づくと理解されているが、RSAの解読が素因数分解と同等であることは証明されたことがないと記している。注目すべきは、このチームは何も素因数分解していない点だ。

影響を受けるのは誰か

標準的なRSA署名はパディング(PKCS#1 v1.5やPSSなどの、演算前に行われるスクランブルおよび整形処理)を適用しており、パディング済みの署名は悪用可能なオラクルを生み出さない。鍵長もさらなる隔たりをもたらす。実証に使用されたのは1,024ビット鍵だが、米国の標準ガイダンス(NIST)は新しいRSA鍵に2,048ビットを最低限としている。著者らは、この攻撃が現代のRSA運用のほとんどに即時の運用上の脅威を与える可能性は低と述べている。論文はまだプレプリントであり、その主張は正式な査読を待つ段階にある。

意図的にこうしたオラクルを公開しているシステムも存在する。RSAベースのブラインド署名(Internet Engineering Task Force標準で規定された技法)は、サーバーがメッセージを見ることなく署名できるようにするもので、Privacy Passのある変種がこの仕組みを利用している。Cloudflareによれば、AppleはPrivacy Passのバージョンを使用しており、ユーザーはCAPTCHAなどのチェックを通過したことを、自身の正体を明かすことなく証明できる。ブラインド署名は暗号学の歴史にも深いルーツを持ち、David Chaumは1989年にDigiCashを設立した際にこの技法を使用した。

より大きな脅威は依然として量子コンピュータ

「RSAが破られた」という見出しには前例がある。2023年1月、中国の研究者らはRSAを脅かす量子手法を主張したが、実際に素因数分解したのは48ビットの数値のみであり、専門家はこれを退けた。今回は実際の1,024ビット鍵での実証だが、ただしオラクルほどの大きさの但し書きが付く。

著者らはこの結果を、ポスト量子移行、すなわち量子コンピュータに耐えうるよう設計された暗号への移行の過程でRSAから離れる根拠となる古典的証拠と位置づけている。この移行にはすでに具体的な節目がある。米国の標準化機構NISTは2024年8月に最初のポスト量子暗号標準を確定し、ベンダーや運用者に共通の移行目標を示した。

ビットコインにとっての量子の問題は楕円曲線署名に関するものだ。Caltechの研究者らは3月末に、Shorのアルゴリズム(これらの署名を脅かす手法)の実行には1万から2万量子ビット(ビットの量子版)で十分かもしれないと推定した。また、Googleは自社システムのポスト量子暗号への移行完了期限を2029年に設定している。

この記事はDecryptが最初に公開したものです:鍵を盗まずにRSA署名を偽造:暗号資産への影響。