Protecting ecmult_gen against side-channel attacks: the big picture

[real-or-random]

We use ecmult_gen to compute point multiplications $nG$ with the generator. This is used for computing public keys and for computing public nonces generation in ECDSA and Schnorr signatures. One of our security goals here is to protect against side-channel leakage.

Attacker model

In the following, I assume an attacker that is able to observe the computation of $nG$ for a fixed $n$ many many times, say $q >> 1$ times. We assume that the observation of a handful of operations does not help the attacker. (If those observations leak too much information, we're lost anyway.) The attacker does not have further capabilities, e.g., it cannot read or write our memory directly.

Current situation

Besides having constant-time code, we currently use these secondary techniques as an additional defense against physical side channel attacks in ecmult_gen when computing $nG$.

• Synthetic nonces: This is only possible when computing nonces because this randomizes $n$ itself.
  Even if all other inputs to signing are the same, we'll get additional fresh randomness (or a counter) from the caller every time, and use a difference secret nonce $n$ in every invocation of a signing function. Here, our attacker won't learn anything.
• Random scalar blinding: We compute $nG$ as $(n-b)G + bG$ for a random scalar $b$, where $b$ and $bG$ are stored in the context upon context randomization (see https://github.com/bitcoin-core/secp256k1/blob/55f8bc99dce8846e0da99b92e52353c8cf893287/src/ecmult_gen_impl.h)
  This means that an attacker that observes the computation $q$ times will observe a single computation of $bG$ and $q$ computations of $(n-b)G$. Since the single observation does not help the attacker, the attacker will at most learn $n-b$, which alone is independent of $n$.
  (Here we need to assume that the attacker can't learn $n$ from observing the scalar addition $n-b$ but again, we're anyway lost if the attacker can learn something meaningful from scalar operations because we'll always need to do scalar operations involving the secret key. We also need to assume that the attacker does not compromise us at any point and learns $b$, or that the attacker has chosen the seed to generate $b$.)
  • Projective blinding: To randomize the projection (gej to ge), we also randomize the z-coordinate of $bG$:
    

    secp256k1/src/ecmult_gen_impl.h

    Lines 114 to 116 in 55f8bc9

    	/* Randomize the projection to defend against multiplier sidechannels.
    	Do this before our own call to secp256k1_ecmult_gen below. */
    	secp256k1_gej_rescale(&ctx->initial, &s);

    
    But as $bG$ itself, this is only updated upon context randomization.
• (NUMS blinding in the precomputation: This is only defense in depth to avoid exceptional cases in the addition law, and it's not relevant to this discussion.)

As a simple conclusion, synthetic nonces are a stronger defense against the kind of attackers considered in this issue. However, we currently use them only for Schnorr signatures but not for ECDSA.

In light of the above, I list some ideas in the following that we could look into. I'll first focus techniques that randomize $n$ itself. I'll indicate what I think in the headings.

Suggestions (ignoring context rerandomization)

Introduce synthetic nonces for ECDSA signing (I want this)

This involves a change to the nonce generation function, and it would be a good idea to switch to a function similar to the one used for Schnorr signatures (see also #757). Synthetic nonces will protect the nonce computation sufficiently. This is a rather simple change and it avoids all the issues with writeable contexts. I think this is almost a no-brainer.

Randomizing $n$ even if it's a signing key (I think I want this)

However, synthetic nonces only protect the nonce computation. But what if $n$ is a signing key? I wrote above that randomizing $n$ is possible. That's not entirely true. With randomness (or a counter) available, we could derive a "one-time" $b$ and still compute $nG$ as $(n-b)G + bG$. The obvious drawback is that this requires two ecmult_gen calls. This sounds bad but I tend to think some of our users may want to pay that additional computation for additional security. Do you think that's reasonable idea?

Suggestions for context rerandomization

Moreover, there have been thoughts and discussions here (#780) and elsewhere (rust-bitcoin/rust-secp256k1#388) about rerandomizing the context after every signature.

Against attackers as sketched above, rerandomization won't help. (As described above, the ecmult_gen is protected even if $b$ stays constant). But if we make the attacker more powerful, and assume it can learn something from observing the scalar addition $n-b$ over and over, then rerandomizing the context (and thus $b$) is a good idea.

Recommend context rerandomization at least between any two computations that derive public keys from secret keys (I want this)

As outlined above, those computations are harder to protect because we can't cheaply randomize $n$ as in synthetic nonces.

Recommend context rerandomization after every signing operation (Not sure if I want this)

If my analysis here is correct, then there's no reason to do this. Synthetic nonces provide the same protection and are simpler. (But on the other hand, defense in depth is a thing...)

Automatic rerandomization

Once we're willing to do larger API changes, we should really implement some form of automatic rerandomization (#780). But I think this further down the road.