Minerva attack on OpenSSL built without enable-ec_nistp_64_gcc_128

[GeorgePantelakis]

@tomato42 and I have tested OpenSSL built without the enable-ec_nistp_64_gcc_128 option on Configure 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.

We have verified that for P-256, this path uses the nistz256 implementation and calls the ecp_nistz256_points_mul() function. The test used OpenSSL from HEAD on 2024-04-12.

We found a side-channel in P-256 on non-determinist OpenSSL. 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.

The results for P-256 non-deterministic path. Skilling-Mack test p-value: 0. The sample tested has 507,469,447 observations.

The results for P-384 non-deterministic path. Skilling-Mack test p-value: 2.528827e-54. The sample tested has 518,259,886 observations.

The results for P-521 non-deterministic path. Skilling-Mack test p-value: 1.318966e-256. The sample tested has 518,253,832 observations.

[t8m]

@GeorgePantelakis I assume all these results were obtained with the nonce fixes from #24265

If you build with enable-ec_nistp_64_gcc_128 you should see the same leak on P-256 as it will also use the nistz256 implementation.

[GeorgePantelakis]

@t8m No because when we ran this we didn't even have the patch for deterministic, we only had the non-deterministic fixes. In general, it used the HEAD git checkout of 2024-04-12. The non-deterministic path, which was tested, was fixed then so it shouldn't show a signal, but it does. Anyway, we are currently running the test again with the changes from #24265. If there is a signal in the new results I will close it as fixed with the fixed results.

[nhorman]

ping, @GeorgePantelakis is there an update here with the fixes from #24265 ? Please update, otherwise I'll assume its fixed and close at the end of the 3.4 dev cycle (october 14)

[GeorgePantelakis]

Hello,

sorry for this late response. So for this with the fixes looks good, it took a great amount of time to gather the data and still, we cannot confirm the complete absence of side channels. What we have is that P-256 seems safe and for P-384 and P-521 there isn't a side channel bigger than 2ns for the first k-sizes. Also, the 512-513 step of P-521 seems to be less than 15ns. To confirm the absence of a side channel will take more time and data.

The results for P-256 non-deterministic path. The sample tested has 658,614,707 observations.

The results for P-384 non-deterministic path. The sample tested has 939,379,680 observations.

The results for P-384 non-deterministic path. The sample tested has 855,790,612 observations.

cc @tomato42

[nhorman]

@GeorgePantelakis thank you. So where does that leave us? My instinct is to call this particular issue resolved, and have you open a new issue if your further testing reveals additional timing leakage. Or would you prefer to leave this issue open until you complete the remaining testing? If the latter, do you have an estimate on when those results will be complete?

[GeorgePantelakis]

@nhorman I would suggest keeping it open at least over the weekend to run some final tests and if we got no luck or if we found no problem then we can close it.

[nhorman]

ACK, thank you