On Monday, 9 September 2024 14:49:08 CEST, D. J. Bernstein wrote:
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".
Ah, ok, I've just misunderstood nomenclature. The meaning is correct.
But then you may also want to add
https://github.com/openssl/openssl/issues/23860#issuecomment-2103073417
(while upstream OpenSSL have decided not to call it a vulnerability,
it's because they consider local side-channels outside of their threat
model and we didn't try to exploit a side channel in the single-digt
nanosecond range as that's very unlikely to be possible outside of pretty
specific scenarios)
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.
That's the difference, my team and I aren't interested in showing attacks,
we're interested in showing absence of any signal that can be used
for performing timing-based attacks.
If there's no correlation between the secret scalar used (be its bit length
or Hamming weight) and the time to make a signature, then it's very likely
that the implementation is actually constant time. Which automatically
makes
large swaths of attacks impossible and others (EM, power) significantly
harder.
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.
yeah, I don't follow how leaking high order bits of `r` doesn't lead to an
attack when knowing a value of it for a particular signature would allow
extraction of the private value (`s`)...
will need to read that blog post, quick skim shows to me that it should
explain it enough for it to "click" for me
Could it be that there's also no
reduction mod the group order in the python-ecdsa implementation?
if you mean reduction mod curve order before scalar multiplication, then
yes, it does do that:
https://github.com/tlsfuzzer/python-ecdsa/blob/4096fa01715929e08b97e73f3173aee9d57f2a3f/src/ecdsa/ellipticcurve.py#L1584-L1586
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.
That's precisely what we're working on and what I've also wrote
in the preface to the Marvin attack :)
The problem is convincing maintainers that this is something that they
should
work on...
--
Regards,
Alicja (nee Hubert) Kario
Principal Quality Engineer, RHEL Crypto team
Web: www.cz.redhat.com
Red Hat Czech s.r.o., Purkyňova 115, 612 00, Brno, Czech Republic
_______________________________________________
TLS mailing list -- tls@ietf.org
To unsubscribe send an email to tls-le...@ietf.org
