Extended Attacks on ECDSA with Noisy Multiple Bit Nonce Leakages

It is well known that in ECDSA signatures, the secret key can be recovered if more than a certain number of tuples of random nonce partial information, corresponding message hash values, and signatures are leaked. There exist two established methods for recovering a secret key, namely lattice-based attack and Fourier analysis-based attack. When using the Fourier analysis-based attack, the number of signatures required for the attack can be evaluated through a precise calculation of the modular bias even if the leaked nonce contains errors. Previous works have focused on two cases: error-free cases and the case for the first MSB has errors among all of the nonce leakage. In this study, we extend the technique to the noisy multiple bits case to calculate the precise value of the modular bias for the case that multiple bits (say, l bits from MSB) have errors. Aranha et al. (ACM CCS 2020) introduced a linear programming problem with parameters to evaluate the number of signatures, time, and memory required for a Fourier analysis-based attack. They also employed a SageMath module to optimize the number of signatures and time required for the attack. Furthermore, we show by experiments that 131-bit ECDSA is vulnerable when the first MSB of the nonce is leaked without error and when 2 MSBs are leaked with an error rate 0.1 each, which implies that total error rate is about 0.19. We then show that the latter case requires less signatures to recover the secret key.