Resolving an Apparent Key-Dependent Timing Side-Channel in Bouncy Castle ML-DSA-65 Signing: A Pre-Registered Discrimination

デジタルセキュリティの世界において、最も強力な鍵とは、解錠に最も時間がかかる鍵であることが多い。何十年もの間、数学者たちはデータを安全に保つために複雑な問題に依存した暗号システムを設計してきた。コンピュータがより強力になり、量子コンピュータの到来が予見される中で、科学者たちは、将来のそれらのマシンでさえも破ることのできない新しい鍵を構築するために競争している。最も有望な新しい設計の一つは、ML-DSAと呼ばれるものである。これは、契約書や証明書における手書きの署名の電子的な同等物である、デジタル署名を作成するための手法である。これらの署名は、メッセージが特定の人物から送られたものであり、改ざんされていないことを証明する。

しかし、これらの数学的な鍵とともに、新しい種類の危険性が浮上している。それは数学自体の欠陥ではなく、コンピュータ上で数学がどのように実行されるかという方法における欠陥である。これはタイミング・サイドチャネル攻撃として知られている。金庫が正しい組み合わせを入力されたときにわずかに大きくカチッという音がしたり、ドアが正しい鍵を使ったときに開くまでにわずかな時間長くかかったりすることを想像してみてほしい。もし攻撃者がこれらの極めて微細な時間の差を極限の精度で測定できれば、秘密の鍵を推測できる可能性がある。新しいML-DSAシステムのために、設計者は安全装置を組み込んだ。そのプロセスには多くの試行錯誤が含まれている。コンピュータは署名を生成しようとし、それが有効かどうかをチェックし、もし有効でなければ、それを捨ててやり直す。試行回数がランダムに変化するため、メッセージに署名するのにかかる総時間も変化する。このランダム性は、秘密の鍵を隠し、特定の遅延が鍵によるものなのか、単なる不運によるものなのかを判別不可能にすることを目的としている。

アルパン・シャルマという研究者が、最近、Bouncy Castleと呼ばれる人気のあるソフトウェアライブラリにおいて、この安全装置が意図通りに機能しているかどうかを調査した。このライブラリは、ソフトウェアのアップデートからセキュアなウェブ接続に至るまで、あらゆるものを保護するために広く使用されている。シャルマが最初にデータを調べたとき、彼はリーク（漏洩）のように見えるものを見つけた。20種類の異なる秘密の鍵を用いてメッセージに署名するのにかかる時間を比較したところ、一部の鍵が一貫して他の鍵よりも長くかかることが分かった。その差はわずか約1.35パーセントであったが、セキュリティの世界では、たとえ極めて小さな一貫した差であっても、秘密が明らかになっている信号となり得る。問題は、この差が真の脆弱性、つまり秘密の鍵が時間に影響を与えることを許してしまうコードの欠陥なのか、それともランダムなシステムの性質によって引き起こされた統計的な錯覚なのかということであった。

これに答えるため、シャルマは単純な推測や素早いテストには頼らなかった。彼は、ノイズからシグナルを分離するために、厳格に計画された実験を設計した。彼の手法の核心は、単に最終的な時間を見るのではなく、コンピュータがすべての署名に対して実際にどのような作業を行ったかを見ることだった。彼は、コンピュータが有効な署名を見つけるまでに何回試行し失敗しなければならなかったかを正確に記録するツールを構築した。これは極めて重要である。なぜなら、メッセージに署名するのにかかる時間は、コンピュータが何度やり直さなければならないかに直接結びついているからである。もしある鍵が、より少ない試行回数で済む「幸運な」メッセージのセットを受け取った場合、その鍵は、鍵が異なっているからではなく、その日の数学的処理が容易であったために早く終了することになる。

シャルマは大規模なキャンペーンを実施し、20個の各鍵に対して120万件以上の署名を生成した。そして、要求された正確な作業量に基づいて署名をグループ化した。彼はシンプルな問いを投げかけた。もし二つの署名が全く同じ回数のリトライを必要とし、全く同じステップを経由したとしても、使用された鍵によってかかる時間に違いが生じるのか？ その答えは明確に「ノー」であった。リトライの回数を考慮に入れると、鍵による時間の差は消失した。残った微小な変動は、コンピュータのプロセッサやメモリの自然でランダムなゆらぎによって説明できるほど小さかった。

この研究は、特定のコンピュータやソフトウェアがメモリにロードされる方法による偶然の結果ではないことを確実にするために、さらに踏み込んだ。シャルマは、新しい鍵と新しいメッセージのセットを用いて実験を繰り返した。また、コンピュータがデータを処理する順序をシャッフルするコントロールテストも行った。もしタイミングの差が秘密の鍵によって引き起こされているのであれば、鍵の順序は関係なくなる。もし差がコンピュータのメモリ内のデータの配置によって引き起こされているのであれば、順序によって結果が変わるはずである。実験の結果、タイミングの差は鍵に従うのではなく、メモリレイアウトに従うことが示された。これにより、見かけ上のリークはコードのセキュリティの欠陥ではなく、コンピュータの環境によるアーティファクト（人工的な現象）であることが確認された。

研究はまた、データによってわずかに異なると分かっているコードの一部についても調査した。ソフトウェアはプロセス中に数値のサイズをチェックしており、もし数値が大きすぎる場合は、リストの残りのチェックを即座に停止する。これは時間を節約するための標準的な最適化であるが、これはコンピュータがある入力に対して他の入力よりも早く停止する可能性があることを意味する。シャルマはこのショートカットの影響を測定し、それが約1ナノ秒の遅延しか寄与していないことを発見した。これは10億分の1秒という時間スケールであり、攻撃者が現実的に測定したり、鍵を盗むために利用したりできる閾値をはるかに下回っている。

これらの知見は、異なるセキュリティレベルで使用される小型および大型のバージョンを含む、これら新しいデジタル署名規格の全ファミリーに適用された。どのケースにおいても、結果は同じであった。ソフトウェアの実装はクリーンであった。見かけ上のタイミングの差は、秘密の鍵が漏洩している兆候ではなかった。むしろ、それらは、まさにそれらの鍵を保護するために作業量を変化させるように設計されたシステムの自然な結果であった。研究は、Bouncy Castleライブラリがこの特定の種類の攻撃に対して安全であることを結論づけた。最初に警戒を呼び起こした1.35パーセントの時間的広がりは、単に20個の異なる鍵がランダムな分布から20個の異なるサンプルを抽出した音、すなわちセキュリティ侵害ではなく統計的なエコーであった。

この調査は、システムが安全であることを証明することがいかに困難であるかを思い起こさせるものである。過去には、研究者はタイミングの差の最初の兆候を見て、脆弱性と宣言して止まってしまうことがあったかもしれない。この研究は、複雑でランダム化されたシステムにおいては、最初の兆候がしばしばシステムがその役割を果たしている姿に過ぎないことを示している。作業内容を注意深く測定し、環境を制御することで、研究者は真のリークと統計的な錯覚を区別することができた。結果として、新しいデジタル署名は堅牢であることが確認された。そして、その速度のランダムな変動はバグではなく、一つの特徴である。これらの署名によって安全を保っている何百万ものデバイスにとって、メッセージは明確である。鍵はしっかりと閉まっており、鍵を回すのにかかる時間は、その内部にある秘密について何も教えてはくれない。