Thomas H. Ptacek(a) Ruhr strikes again.
(b) This is one of the all-time great cryptography footguns: not filling the ECDSA modulus.
Couldn't be any more thrilled.
Sean's writeup of the mechanics of this attack in his Cryptopals set 8 is *so good*.
The big thing here is is a programmer-brain impedance mismatch.
You need a cryptographically random 521 bit modulus, to work P-521. Your libraries easily generate 512-bit moduli. 512 bits seems essentially as cryptographically unguessable as 521 bits. If these were like, AES keys, the distinction would not matter.
But it matters a fuckload in asymmetric cryptography, because 521-512 leaves 9 bits biased to 0, which over a collection of signatures lets you set up a linear algebra problem to recover the secret key.
I don't keep up with any of this literature but last time I checked there was like an academic arms race to see just how few bits of bias you'd need to solve for a private key, and the 1-bit barrier was broken a long time ago.
Also: this is the bug Alex wrote an exploit for in the Hiring Post I wrote at Matasano.
The unstoppable Kelby Ludwig wrote an IPython notebook that works through examples from Boneh's Hidden Number Problem paper, is a good overview, and will steer you around some comprehension pitfalls:
https://github.com/kelbyludwig/notebooks/blob/master/The%20Hidden%20Number%20Problem.ipynb
Clemens@tqbf Related work that does the same thing with a side-channel exposed by smartcards: https://minerva.crocs.fi.muni.cz/
We're all sure our ECDSA signatures can't be measured or are constant time in the length of the modulus, right?
lambdafu@tqbf 1-bit barrier was broken using Bleichenbacher FFT, with a lot of signatures. For crypto, best lattice break is Albrecht/Heninger "On Bounded Distance Decoding with Predicate: Breaking the Lattice Barrier for the Hidden Number Problem", which was just improved by Gao, Wang, Hu, He "Attacking ECDSA with Nonce Leakage by Lattice Sieving: Bridging the Gap with Fourier Analysis-based Attacks". The latter is pre-print only so far, but reports lattice attack with sub-1-bit leak for 160bit ECDSA.