Can deterministic ECDSA be protected against fault attacks?

Question

In a paper by Barenghi and Pelosi, it was described that fault attacks could be used to derive the secret key when using deterministic ECDSA as described in RFC6979 by @Thomas_Pornin

Deterministic (EC)DSA. The purpose of the attacker in this case is to recover the value of the secret key $d$, from the values of the correct signature $(r, s)$ and the erroneous one $(\tilde r, \tilde s)$. The attacker is able to build the following simultaneous equation set on $\mathbb{Z}^*_q$ in the unknowns $d$ and $k$:

$$ \left\{ \begin{align} s &\equiv_q (\texttt{H}(\texttt{msg})+d \cdot r) \cdot k^{-1} \\ \tilde s &\equiv_q (\texttt{H}(\texttt{msg})+d \cdot \tilde r) \cdot k^{-1} \end{align} \right. $$

and solve it for

$$ \left\{ \begin{align} d &\equiv_q \textstyle \frac{(s - \tilde s) \cdot \texttt{H}(\texttt{msg})}{r \cdot \tilde s - \tilde r \cdot s} \\ k &\equiv_q s^{-1} \cdot (\texttt{H}(\texttt{msg})+d \cdot r) \end{align} \right. $$

The amount of computation required to derive the secret key is negligible, and it is possible, in case an unreliable fault injection technique is being used, to confirm whether the correct values of $d$ and $k$ have been extracted deriving the deterministic $k$ corresponding to the $d$ via the procedure specified in [9], and checking it against the one obtained from the simultaneous equations.

Can deterministic ECDSA be protected against such fault attacks?

Answer 1

As already said by fgrieu in his answer, this is possible.

There are multiple ways to protect deterministic ECDSA against fault attacks, but these ways will depend on your fault model.

If you consider only a single fault model, then any construct requiring the attacker to perform two faults to achieve his goal will be an acceptable countermeasure... On the other side if you consider the attacker is ubiquitous and can perform faults of her choosing at any point in time at any location of the chip, then you most likely won't find any way to counter her. It is a common assumption, backed by practical experiment that performing two localized faults on the same computation is hard, even more so if the value of the fault is important.

So, how could you deal with single faults in deterministic ECDSA?

Well you could do as fgrieu says and do the verification process, but then a second fault in the very last step could simply trigger the verification to output "true" instead of "false", yet you would be in another fault model, where the attacker can do two faults... Now, there are other ways which would render the second fault even harder for the attacker:

The first way is described by Thomas Pornin himself in RFC6979 section 3.6 (emphasis mine):

Additional data may be added to the input of HMAC, concatenated after bits2octets(H(m)):

     K = HMAC_K(V || 0x00 || int2octets(x) || bits2octets(h1) || k')

A use case may be a protocol that requires a non-deterministic signature algorithm on a system that does not have access to a high-quality random source. It suffices that the additional data k' is non-repeating (e.g., a signature counter or a monotonic clock) to ensure "random-looking" signatures are indistinguishable, in a cryptographic way, from plain (EC)DSA signatures.
In [SP800-90A] terminology, k' is the "additional input" that can be set as a parameter when generating pseudorandom bits. This variant can be thought of as a "strengthening" of the randomness of the source of the additional data k'.

This is the way chosen by XEdDSA, used in Signal, to prevent faults to have an impact on its security. It allows for both the additional security of deterministic ECDSA against biased random sources, still appears perfectly compliant with ECDSA, and will be effective against fault attacks as described in the XEdDSA document. But then you don't get the determinism of the signatures anymore, sadly.

A second way to achieve this same goal might be to sign twice the same data and compare the output of both, if they match to proceed, otherwise there was a fault or multiple unsynchronized faults in the computations. This has the benefit, especially for EdDSA, to not bear the cost of a complete verification, since verification is a way more costly operation there (it also more costly for ECDSA). But still renders the process twice as slow.

A third possibility would be to use so-called "infective" countermeasures as introduced for RSA so that a fault in any part of the final computation would randomize the faulted output. Here is a recent paper (published for FDTC 2017) featuring such a countermeasure for EdDSA. Such a countermeasure would typically combine two different implementations of the same hash in a way that allows recovering the correct value if both output the same data, but would otherwise give nothing of interest. But it is very "local": it might not protect against faults occurring at other steps of the signature process.

I personally like adding back randomness into deterministic ECDSA, which I find both elegant since it's indistinguishable from standard ECDSA and efficient since it bears almost no cost in practice, unlike many other ways.

PS: by the way, Barenghi and Pelosi say that EdDSA shows a structural resistance against these kinds of attacks, but this is actually not the case since it's still possible to obtain sufficiently secret material to mimic valid signatures in a way that only the secret key's owner can detect.

Answer 2

Yes, ECDSA (including deterministic) can be protected against fault attacks. An idea is to check any computed signature (by the verifier's algorithm) before releasing the signature (and not releasing anything if the verification fails; perhaps, zeroing the key and declaring the device faulty or under attack).

That's a pretty general technique applicable to many signature schemes. It was already taught by Dan Boneh, Richard A. DeMillo, Richard J. Lipton, On the importance of checking cryptographic protocols for faults, in proceedings of Eurocrypt 1997.

In the case of (EC)DSA, and as noted in the above article, that countermeasure is rather expensive: it more than doubles the cost of signing.

Less expensive countermeasures are possible; see Lery's excellent answer.

Answer 3

Perhaps checking that r which is the x value of the point on the curve is in fact corresponding to the y value which could be kept from the point scalar multiplication based on the y^2=x^3+ax+b equation would also be a method. It is much faster than signature verification.