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?

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:

k = rand()

However, “random generation of k” is non-trivial task. In short, k must always be unpredictable and not previously used. This could be achieved using “cryptographically secure random” (CSPRNG).

What if randomness is predictable?

Methods like Math.random() are predictable - in JS, CSPRNG getRandomValues should be used instead. Think of predictable generators as fn(currTime): if you know state (currTime) before values are generated, you could easily re-generate those. Predictable nonce k allows an attacker to extract private key from the signature, which happened with Sony PS3:

d = (r^-1)(s⋅k-m) mod n

What if randomness is reused?

Reusing random nonce k allows attacker to extract private keys from two distinct signatures:

s = (k^-1)⋅(m+r⋅d) mod n
s1-s2 == k^-1⋅(m1-m2)
k(s1-s2) == m1-m2 // mul both by k
k = ((s1-s2)^-1)⋅(m1-m2) // mul both by (s1-s2)^-1
s1 = (k^-1)(m1+r⋅d)
r⋅d == s1⋅k-m1
d = (r^-1)⋅(s1⋅k-m1) // mul both by r^-1
// where r, s1, s2 are r, s from sigs 1, 2;
// all operations are mod n

After that, people invented and popularized deterministic signatures.

Extracting keys using fault attacks

Deterministic signatures guard against bad randomness. They produce k from private key d and message m:

k = combine(d, m)

Note: RFC 6979 uses HMAC-DRBG for combine, but if it was created later, it could have used simpler HKDF instead.

On the other hand, determinism makes them vulnerable to fault injection attacks. If something wrong happens during combine, resulting in duplicate nonce k getting produced for two distinct inputs, then it’s just as bad as “bad randomness” was.

Let’s illustrate how RFC6979 fault injection could look in JS:

k_bytes = combine_hmac_drbg(d, m)
k = num(k_bytes)
R = G.multiply(k) // imagine mul expects num
r = mod(R.x, n)
s = mod(inv(k) * mod(m + d⋅r, n), n)
// the buggy function which converts JS Uint8Array to bigint
const num = (u8a) => BigInt('0x' + [...u8a].map(b => b.toString(16)).join(''))
// num(Uint8Array([1, 2, 15, 16, 255]))
// expected: "01020f10ff", actual: "102f10ff"

In this example, num generates identical outputs for distinct inputs [1, 1, 30] and [17, 30]. All attacker needs to do is convincing a user to sign two distinct specifically manipulated messages. Those would produce signatures with identical k, which means an attacker would be able to extract private key from them. In a real world, there are all kinds of places where a subtle bug can happen. Type-to-other-type conversion methods; byte fiddling routines, etc.

Another kind of fault attack is a “hardware error”. Attacker utilizes physical access to hardware (for example, to CPU, or a smart card), and induces interference into device behavior. This could be done using a voltage spike, a laser, or something else. The result is the same: an error during sig generation.

Hedged signatures for the rescue

Hedged (“noisy” / “extra entropy”) signatures combine both approaches. They generate k deterministically, then incorporate randomness into it.

Let’s add hedged signatures to RFC 6979:

rnd = rand()
k_bytes = combine_hmac_drbg(d, m, rnd)
k = num(k_bytes)

Randomness is incorporated into DRBG, and is then fed into hash.

What if fault attack happens in a hedged sig?

The generated randomness would still produce new random valid signature, without leaking k:

rnd = rand()
k_bytes = combine_hmac_drbg(d, m, rnd)
k = num(k_bytes)
// still OK: combine() would've failed for (d, m) but is saved by `rnd`

What if bad randomness is used in a hedged sig?

What if nonce is reused in a hedged sig?

The deterministic part would still produce new random valid signature, also without leaking k:

rnd = 000000000...
k_bytes = combine_hmac_drbg(d, m, rnd)
k = num(k_bytes)
// still OK: combine() would've failed for `rnd` but is saved by (d, m)

So, to break hedged signatures, an attacker would need to break both randomness generator and inject a fault into generation process.

Hedged signatures would be different every time. This is not a big deal: testing and auditability are solveable. While testing fully random signatures was complicated in the past, hedged signatures are simpler: to verify something against a pre-generated set of vectors, you have to explicitly specify randomness, instead of fetching it from CSPRNG. It is also possible to generate entropy from some seed, which makes the scheme auditable, albeit less secure than purely random.

What about adoption?

Disadvantages

There are a few cons of using hedging:

  • DJB mentioned in the blog post it’s possible to exfiltrate information.
    • In his scheme, attacker has access to secret data and is able to modify entropy generation
    • It can be argued that when an attacker already has access to secret data, it’s already “too late”
    • It’s also not enough for entropy generator to “just hash secret + entropy and check” in ECDSA, it must also do elliptic curve scalar multiplication; making the whole thing more complex
    • Industry argues risk from this is smaller than risks from pure determinism
  • Some folks argued about increased chance of fingerprinting
    • An offline device can fingerprint all signatures by inserting particular bit sequence somewhere in r / s
    • For example, a device can insert its 8-byte ID as first 8 bytes of “r”: “cafecafe…”
    • However, just grinding through first 2 bytes would need to produce 65536 signatures, on average (256*256)
    • Embedded device, such as offline signer, commonly have 35MHz CPU, which are slow and can’t produce this much sigs in a small period
    • In JS library, only ~5K signatures per sec can be produced on a high-end device
  • Some ZK protocols rely on determinism

Conclusion

Using hedged signatures would add security against all kinds of bugs in signature generation process. After all, we can never be certain if there is a bug.

I’ve created noble cryptography in 2019 to improve security of JS ecosystem. noble-curves implement hedged ECDSA, XEdDSA and BIP340. Feel free to copy the logic, use and re-distribute the code. Check out micro-eth-signer and btc-signer which have support for hedged signatures.