Closed ansiwen closed 6 months ago
I believe the non-constant part is entirely due to the computation of k
when not provided, which is mentioned by the documentation of sign
as a risk.
On master
, on a constant message and 5 random keys for P521, with k pre-computed with the same method as when not provided:
ops/s | Verify | Sign with pre-computed k | Sign without k |
---|---|---|---|
Key 1 | 175.7 | 1189.9 | 573.6 |
Key 2 | 175.8 | 1188.1 | 487.1 |
Key 3 | 175.4 | 1190.3 | 344.3 |
Key 4 | 174.7 | 1186.4 | 695.0 |
Key 5 | 173.8 | 1179.7 | 563.0 |
Std. dev. | 0.74 | 3.84 | 115.33 |
The computation of k
seems to take a huge part of the total spent time (compared to other curves, see below), though I don't have an intuition yet for why . I'll note that the low-level primitives for P521 are generated from a different fiat-crypto
algorithm (unsaturated solinas) than all other P-curves (word-by-word-montgomery). Maybe it's also worth to look into Digestif.SHA512
.
For comparison, here are the same measurements on P256 (excluding verify):
ops/s | Sign with pre-computed k | Sign without k |
---|---|---|
Key 1 | 8586.3 | 8388.4 |
Key 2 | 8593.2 | 8467.0 |
Key 3 | 8612.1 | 8377.6 |
Key 4 | 8604.4 | 8363.0 |
Key 5 | 8626.3 | 8392.4 |
Std. dev. | 14.13 | 36.13 |
I'll note that the low-level primitives for P521 are generated from a different fiat-crypto algorithm (unsaturated solinas) than all other P-curves (word-by-word-montgomery).
That is not the case, all of them are using word-by-word-montgomery. The unsaturated salinas is used by ed25519.
Maybe worth to measure how often do_sign
is called (which computes k
and is recursive)? Maybe worth to investigate #105 - maybe the K_gen gen ()
function (as well recursive) is called too often?
@ansiwen for what it is worth, please note that old mirage-crypto releases are unsupported. If you like to report an issue in the future, please test with the latest release.
That is not the case, all of them are using word-by-word-montgomery. The unsaturated salinas is used by ed25519.
Ah my bad, I looked into fiat-crypto
directly assuming we'd have reused these.
Maybe worth to measure how often do_sign is called (which computes k and is recursive)?
It will be useful to measure it just in case, but it probably is called once in all cases, or else it would fail when I pre-compute and pass k
(since again
stops after the first iteration if k
was passed).
Maybe worth to investigate https://github.com/mirage/mirage-crypto/issues/105 - maybe the K_gen gen () function (as well recursive) is called too often?
I'll try to continue to investigate, thanks for the ideas :)
@ansiwen for what it is worth, please note that old mirage-crypto releases are unsupported. If you like to report an issue in the future, please test with the latest release.
We did. That's why I added the reproduction of @Firobe, which was on master.
@hannesm Your idea was spot on :) See #230
With this, here's the distribution over the same sample of keys
ops/s | Sign without k |
---|---|
Key 1 | 1161 |
Key 2 | 1170 |
Key 3 | 1162 |
Key 4 | 1164 |
Key 5 | 1159 |
Std. dev. | 6.05 |
@Firobe Well done! Great work! Just for my understanding: the k is calculated deterministically from the key, or why was it constant over identical keys?
@ansiwen In classical ECDSA, k is chosen randomly from a good, uniform, unbiased random source. These characteristics are not always possible to have, and hard to test, so the RFC proposes a process to compute k deterministically from the key and the message instead (which is supposed to be indistiguishable from random from the PoV of an attacker).
This does mean the k is the same for each similar message, so it can be used to recover the key if there are other vulnerabilities (https://www.hertzbleed.com/2h2b.pdf). In practice to be truly secure, a k should be generated randomly if a good random source is available, and passed explicitly.
While doing performance measurements I noticed, that P-521 signatures are not constant-time, which I assume they should be. P-256 is not affected. I see the same behavior with and without the recent performance improvements for elliptic curves. However, I'm not using the latest mirage-crypto, but 0.10.7. Here the result of a simple test script, always signing the same message but generating a new key every two measurements:
@Firobe could reproduce the effect with a modified mirage-crypto benchmark: