Deterministic signatures are praised as the pinnacle of Elliptic Curve Cryptography.
ed25519 uses them. RFC 6979 spec describes them.
They eliminate the whole class of issues with “bad randomness”.

Turns out, with recent CVE in elliptic.js,
which allowed attackers to extract private keys, full determinism is not great.

• How signatures are made?
• Extracting keys using bad randomness
• Extracting keys using fault attacks
• Hedged signatures for the rescue
• Conclusion

How signatures are made?

Implementing digital signatures from scratch is simple,
i’ve described it in previous article: Learning fast elliptic-curve cryptography.

Signatures are usually either random or deterministic.
“Random” means using pair (d=privkey, m=message) would always generate new signature.
“Deterministic” means (d, m) would always generate the same signature.

Let’s recall their shortened formulas.

• inputs: d is a private key, m is a message to sign
• functions: rand produces secure randomness, hash creates cryptographic hash,
  combine is HMAC-DRBG
• operations: G × k is elliptic curve scalar multiplication with G=generator point, || is byte concatenation, ⋅ is multiplication, mod n is modular reduction n=curve order

ECDSA:

k = rand() // a: random
k = combine(d, m) // b: deterministic, RFC 6979
R = G × k
r = R.x mod n
s = k^-1 ⋅ (m + d⋅r) mod n
sig = r || s

Schnorr from BIP340:

A = G × d
t = d ^ hash(rand())
k = hash(t || A || m) mod n
R = G × k
e = hash(R || A || m) mod n
s = (k + e⋅d) mod n
sig = R || s

EdDSA ed25519 from RFC 8032:

h = hash(d)
d_ = h[0..32]
t = h[32..64]
A = G × d_
k = hash(t || m)
R = G × k
e = hash(R || A || m)
s = (k + e⋅d_) mod n
sig = R || s

Extracting keys using bad randomness

Before deterministic signatures became popular, signatures were produced with randomness.
Every time anyone signed anything, a random sequence of bytes k (also known as “nonce”) was generated.
Then, k was used to produce a signature:

However, “random generation of k” is non-trivial task.
In short, random k must always be unpredictable and not previously used.
This could be achieved using “cryptographically secure random” (CSPRNG).
Which means, for example, one could not have used JS Math.random() – a
whole different algorithm
was required.

What if randomness is predictable?

Methods like Math.random() are predictable.
If you knew state of user system before values are generated,
you could easily re-generate those. Predictab