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.
d@nny disc@ mc²@tqbf "programmer-brain impedance mismatch" is an incredibly pretentious way to say something incredibly simple. don't pretend like mathematics is some sort of fucking lost art only interpretable by the chosen divine messengers, that does not at all help anyone to understand how to process this in the future and only contributes to self-esteem issues
@tqbf reading posts like this is much more annoying than someone just telling me not to write my own crypto because they're not telling me i'm "programmer-brained" for something it's implied i would never have thought of myself