The same problem occurs in elliptic curve DSA, which is just the DSA construction implemented on the elliptic curve discrete log.
What's also true is that if part of the nonce is predictable (or leaked), DSA falls apart --- albeit over more than just a couple signatures. With tens of bits leaked, you might needs hundreds of thousands of signatures.
How would you ever leak part of a nonce over thousands of signatures? One easy way is to generate a nonce that appears cryptographically random, but doesn't fill the modulus. For instance: a 128 bit random number sure seems strong, but if it's filling a cryptographic parameter that's meant to be 256 bits long, fully 128 bits of that parameter are predictably zero.
Here, though, you have a predictable nonce bit leak that can occur purely by accident even given a reasonably sound implementation!
Deterministic nonces are a good idea, but they don't necessarily prevent biases. Generally speaking, for (EC)DSA/Schnorr in a group of cardinality n, using a nonce of the form k=F_x(m) (where m is the message and x the public key) is safe if F is chosen as a Z/nZ-valued PRF; but if you use a PRF with values in bitstrings of the same length as n, the attack in the paper does apply.
So RFC 6979 is fine, but k=HMAC-SHA-256(x,m) is not a secure choice for 256-bit elliptic curves over random base fields.
It's common to see implementations want to remove debiasing steps too. E.g. I've seen several implementations of "derandomized DSA" for Bitcoin (e.g. javascript tools, hardware wallets, etc. We obviously do this right in Bitcoin core) that do not re-roll if the result is over the order, they just take it mod the order.
Complaining to the implementers has just resulted in <whine>thats more complicated, mod is fine</white> And, indeed, for secp256k1 the differences is 1 part in 10^38, so its not likely of practical importance; unless you can assume an attack that can extract an _awful_ lot of signatures from you.
I expect the same behaviours are common for different parameters where it's not such a small bias.
When the base field is pseudo-Mersenne, taking mods is actually fine, since the statistical distance to uniform of the resulting distribution is O(2^{-λ}) at the λ-bit security level. In other words, an attack that exploits the bias is at least as costly as breaking the discrete log problem directly, and therefore not a security concern. So I wouldn't worry about implementations of secp256k1 that do it like that (although it would be simpler and less "leaky" to just use the non-reduced 256-bit MAC value as the nonce; of course, anything shorter than 256 bits would be a huge problem).
But careful approaches like RFC 6979 are very important for curves over random fields, like the Brainpool parameters.
[By the way, a more regular contributor of this site suggested that it would be appropriate for me to mention that I'm one of the authors of the OP.]
I know I'm probably going to only understand some tiny fraction of what I read
in this paper, but I'm sure going to have fun trying.
BTW, you might want to add "[pdf]" to the title. It seems the automated
pdf detection and title editing missed this submission for some reason,
so I reported it to hn@ycombinator.
Neat! I only saw it done with 2-3 variable predictable leading bits before.
A Schnorr-style signature with a deterministic nonce, like djb's EdDSA/Ed25519, is probably a better way to go these days, since the patents expired...!
(1) Shows attacks on ECDSA where there is a one bit of bias on the nonce. These should work equally well on Schnorr signatures of their various forms, including EdDSA (though EdDSA proscribes a particular nonce generation scheme which should hopefully not result in observable biases, other standards proscribe similar schemes for ECDSA users, e.g. RFC6967). If it turns out that the hash functions used for deterministic dsa in these systems are biased, this attack crops back up.
(It's not news that biased RNGs can result in these attacks; the interesting part is that they were able to actually perform an attack on a non-toy curve, with only a one bit bias. Past attacks were mostly theory, and also needed more bias.)
(2) Some unusual curves can have an optimization which common implementations might take which results in biased nonces. These curves are not widely used on the Internet. I'm doubtful you've ever heard of them (except Bitcoin's curve, which is a GLV curve, but I'm relatively confident _no one_ is using the endomorphism in signing). They also give advice on avoiding that weakness.
(3) One way of avoiding the weakness while still using the optimization is to decompose a uniform number instead of using two random numbers, they show an argument for a power attack against a candidate constant time decomposition algorithm. Again, moot if you're not using the optimization.
Every DSA signature requires a random nonce/key k. If k is predictable, DSA falls apart. We demonstrate that here:
http://cryptopals.com/sets/6/challenges/43/
The same problem occurs in elliptic curve DSA, which is just the DSA construction implemented on the elliptic curve discrete log.
What's also true is that if part of the nonce is predictable (or leaked), DSA falls apart --- albeit over more than just a couple signatures. With tens of bits leaked, you might needs hundreds of thousands of signatures.
How would you ever leak part of a nonce over thousands of signatures? One easy way is to generate a nonce that appears cryptographically random, but doesn't fill the modulus. For instance: a 128 bit random number sure seems strong, but if it's filling a cryptographic parameter that's meant to be 256 bits long, fully 128 bits of that parameter are predictably zero.
Here, though, you have a predictable nonce bit leak that can occur purely by accident even given a reasonably sound implementation!