openssl
Minerva attack in OpenSSL
@tomato42 and I have tested OpenSSL and we found that it may be vulnerable to a variant of the Minerva attack. We used statistical analysis to confirm the presence of side channels but we did not perform the Minerva attack against the implementation.
In the test scenario, we measure the time of signing of random messages using the EVP_DigestSign API (Init, Update, and Final) and then use the private key to extract the K value (nonce) from the signatures. Then based on the bit size of the extracted nonce we compare the signing time of full-sized nonces to signatures that used smaller nonces using statistical tests.
In our initial test, we found side-channels in curves P-256, P-364, and P-521. In these results we can see a clear leak: there is a dependency between the bit size of K and the size of the side channel. For initial testing, we used the master checkout from 2023-09-11.
The sample tested has 107,970,608 observations.
The sample tested has 43,179,504 observations.
The sample tested has 97,170,890 observations. The results for P-521 are notable due to the big "step" present between results for 512-bit and 513-bit nonces, which is over 250ns.
After long cooperation with the OpenSSL team, we have arrived at a patch that significantly reduces leakage for P-256 and P-384 signing operations.
For P-521, with the patch applied, the "step" of 25ns is still present between the 512-bit and 513-bit nonce, but no side channel in larger nonce sizes.
The sample tested has 58,312,456 observations.
One more thing, while we don't have evidence that it's immediately exploitable, as the selected nonce is created by OpenSSL internally, there is one rather contrived scenario where it is exploitable over the network with OpenSSL 3.2.0:
- the network-accessible service needs to sign verbatim attacker-controlled messages
- the service needs to use the newly added deterministic ECDSA implementation
this way the attacker will be able to determine if the deterministically selected nonce is short or not, and use that information for solving the Hidden Number Problem.
Given that most services like that will actually sign the attacker provided message with some kind of timestamp (think time-stamping protocol), or combine the attacker controlled data with server controlled data, in effect making the exact signed messages not repeatable, the attack against deterministic ECDSA is mostly theoretical.
related: https://github.com/openssl/openssl/pull/24317 https://github.com/openssl/openssl/issues/24252 https://github.com/openssl/openssl/issues/24253 https://github.com/openssl/openssl/issues/24254 https://github.com/openssl/openssl/issues/24274
In #24274 after the nonce generation fixes were merged you've confirmed that the side channel without enable-ec_nistp_64_gcc_128 cannot be confirmed. What is the situation with enable-ec_nistp_64_gcc_128 on x86_64? Is it side-channel free?
Hello @t8m, With the enable-ec_nistp_64_gcc_128 on x86_64 we have a confidence interval of less than 1 ns that the implementation is most likely not vulnerable to the Minerva attack for curves P-256, P-384, and P-521 in the non-deterministic path. We still have open issues for other architectures. Also with PR#24265 code the deterministic path is most likely not vulnerable on x86_64 for the same curves.
I assume all the other architectures with issues were tested with PR#24265 in place.
@t8m and @GeorgePantelakis looking at the history of this issue it looks like it has been patched. Can we close the issue?
@fwh-dc This specific issue has been patched but as said in https://github.com/openssl/openssl/issues/23860#issuecomment-2103073417 there are other issues related to this one (this was the first created) that are not yet fixed. Right now this issue serves as a tracker, but it is up to you if you want to close it or not.