ECDSAに対する4-list sum algorithmを用いた攻撃の評価

楕円曲線を用いたデジタル署名アルゴリズム（ECDSA）はSSL/TLS やBitcoin など非常に広い分野で使用されている．ECDSA の署名時に一度だけ用いられるランダムな値であるnonce のエラー付き上位ビットが署名，ハッシュ値と共に複数組漏洩した場合の攻撃方法が提案されている．Aranha らはACMCCS2020 で上位 1 ビットがエラー付きで漏洩しいてる192-bit のECDSA に対して，フーリエ解析ベース攻撃を行い，秘密鍵の復元に成功している．Aranha らはフーリエ解析ベース攻撃でのrange reduction に4-list sum algorithm を用いている．彼らは和の分布の一様性を仮定して見積もりなどを行っていたが，実際には一様ではないため，必要な署名数を過小に評価していた．本研究では，和の分布を正確に導出した上で，その分布を組み込んだアルゴリズムの提案を行う．さらに，nonce の上位 2 ビットがエラー率 0.111434 で漏洩している場合は，上位1 ビットがエラー無しで漏洩している場合と秘密鍵を復元するのに必要となる署名数が同程度であることを指摘し，実際に，131-bit ECDSA の秘密鍵の復元ができることを示す．

Elliptic Curve Digital Signature Algorithm (ECDSA) is used in a vast range of applications, including SSL/TLS and Bitcoin. Several methods have been proposed to attack the case where the MSBs of the nonce in an ECDSA signature, contain errors and are compromised along with the signature and hash value. Aranha et al. successfully recovered a 192-bit ECDSA secret key from the MSB with an error by using Fourier analysis based attack. In their Fourier analysis-based attack, Aranha et al. used a 4-list sum algorithm for collision search. They assumed that the distribution of the sums was uniform, but in fact, it was not, resulting in an underestimation of the number of required signatures. In this study, we derive the exact distribution of the sum and propose an algorithm that incorporates the distribution. Furthermore, we point out that the number of signatures required to recover the secret key when the upper two bits of the nonce are compromised with an error rate of 0.111434 is comparable to that when the upper 1 bits are compromised without error. We then show that it is possible to recover the secret key of a 131-bit ECDSA.