[TLS] Re: [EXTERNAL] Consensus Call: -rfc8446bis PRs #1360

["D. J. Bernstein" <[e-mail]>]

Alicja Kario writes:
> We haven't actually performed
> an attack in which we extracted the private key.
  [ ... ]
> In practice, what we've shown is that the implementation is _likely_
> vulnerable to microarchitectural side-channel attacks.

The top of Appendix A of https://cr.yp.to/papers.html#safecurves
distinguishes "demo" ("an attack has been demonstrated") from
"vulnerability" ("analysis indicates that an attack should work"). The
Firefox entry in the list says "vulnerability". Actually carrying out an
attack would upgrade it to "demo".

> And I'm pretty sure that the implementation of Ed25519 in
> https://github.com/tlsfuzzer/python-ecdsa is also vulnerable to the
> same class of attacks because of the super-leaky implementation of
> arbitrary precision arithmetic it's using.

Indeed, one can't expect any cryptosystem to be able to survive the
timing leaks from Python integers!

But wait. EdDSA has another trick up its sleeve that might sometimes
save the day even in this horrifying situation. The EdDSA hash is
double-length, and an implementation designed for simplicity won't
reduce the hash mod the group order.

Here's why this matters for people evaluating attack costs. Remember
that, in ECDSA, by far the easiest timing variability to exploit is the
correlation between faster scalarmult and smaller nonces _mod the group
order_. If nonces _aren't_ reduced then what one instead expects to see
is a correlation between faster scalarmult and smaller double-length
nonces---which isn't useful per se for the attacker.

The Minerva team originally claimed to break ECDSA and EdDSA in
libgcrypt. Two days later the team withdrew the EdDSA part of this
claim. https://blog.cr.yp.to/20191024-eddsa.html traces how this boiled
down to EdDSA's double-length hash, and also quotes how I had predicted
this scenario five years earlier. Could it be that there's also no
reduction mod the group order in the python-ecdsa implementation?

To be clear, I assume that enough work will break libgcrypt---the nonce
length is just the simplest attack target, and we should be much more
proactive than just saying that the simplest attack doesn't work. The
same blog post says "We have to throw away variable-time crypto code
_without_ waiting for attacks to be demonstrated". But people who _are_
in the disaster scenario of deploying variable-time arithmetic will
still have EdDSA making attacks harder on average than ECDSA does.

---D. J. Bernstein