本文へスキップ
ecdsa.com

隠れ数問題

秘密値の数ビットを明かすノイズを含んだ多数の線形関係から、その秘密値を復元する格子の問題で、ECDSA や DSA の nonce のわずかな偏りや漏洩を、秘密鍵の完全な復元に結び付けます。
別表記HNPlattice attackbiased nonce attack

ECDSA の各署名からは s·k = z + r·d (mod n) が得られます。すべての k の上位ビットがゼロであると分かっている場合や、サイドチャネルを通じて漏洩する場合、各署名は秘密鍵 d に関する近似的な線形方程式になります。十分な数の署名があれば、(r, s, z) の組から構成した行列に格子縮約(LLL または BKZ)を適用することで d が求まります。これは Boneh と Venkatesan(1996年)の隠れ数問題であり、Howgrave-Graham と Smart(2001年)、Nguyen と Shparlinski(2002年)が DSA に応用しました。

署名あたり数ビットの漏洩でも数百から数千の署名があれば十分であり、最近の手法では 1 ビット未満の漏洩でも攻撃が成立します。記録されている事例には、Minerva(2019年、スマートカードとライブラリにおけるビット長のタイミング漏洩)、TPM-Fail(2019年、Intel のファームウェア TPM と STMicroelectronics の TPM)、LadderLeak(2020年)、そして 2019年の研究『Biased Nonce Sense』があります。この研究では、短い nonce を使った実際の Bitcoin と Ethereum の署名から鍵が復元されました。

対策は次のとおりです。nonce を全範囲から一様に生成する(RFC 6979 による決定的な生成、またはヘッジ付き)、nonce のビット長を明かさない定数時間のコードで計算する、そして nonce の漏洩が報告されたら、見た目だけのバグではなく鍵の危殆化として扱うことです。

規格と参考文献

すべての用語