Minerva attack on power PC architecture

[GeorgePantelakis]

@tomato42 and I have tested OpenSSL in power PC architecture 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 a side-channel in P-364 curve. The P-256 and P-521 curves are, most likely, safe. 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 the non-deterministic path of the code:

Results for P-256. Skilling-Mack test p-value: 1.676327e-01. The sample tested has 583,024,459 observations.

Results for P-384. Skilling-Mack test p-value: 1.802425e-74. The sample tested has 615,444,376 observations.

Results for P-521. Skilling-Mack test p-value: 8.632069e-01. The sample tested has 485,866,172 observations.

For the deterministic path of the code:

Results for P-256. Skilling-Mack test p-value: 7.604963e-02. The sample tested has 388,704,249 observations.

Results for P-384. Skilling-Mack test p-value: 1.201069e-15. The sample tested has 323,911,655 observations.

Results for P-521. Skilling-Mack test p-value: 4.801629e-01. The sample tested has 550,642,703 observations.

[gcwilson]

Hi @t8m. Thanks to you, @tomato42, and @GeorgePantelakis for this issue. Jaroslav Reznik brought this matter to our attention. So some questions. Are you looking for help from the IBM PPC crypto team? Is this problem specific to the new P-384 implementation? Do have already have recommendations on how we should modify the ppc64/ppc64le code? How can we test for this problem in house?

[tomato42]

Are you looking for help from the IBM PPC crypto team?

yes, we don't have resources to fix it ourselves

Is this problem specific to the new P-384 implementation?

Probably, George will be able to say if any particular method is being called or not if you tell him what to look for

Do have already have recommendations on how we should modify the ppc64/ppc64le code?

No. Though at this point, the most likely reason for this leakage is a short-circuit in the scalar multiplication loop

How can we test for this problem in house?

You'll need to contact George for a the test harness and instructions how to execute it.

[gcwilson]

Hi @GeorgePantelakis. Can you help with some of the questions above? Is the matter all contained to the new P-384 implementation? How can we obtain the test harness?

[davidben]

While not an exact match, valgrind's rules for uninitialized memory are very close to the constant-time computational model. For BoringSSL, we've found it very valuable for flagging non-constant-time code. It takes a bit of work, marking the right data is "secret" (uninitialized) and then "declassifying" (marking initialized) the right data at the right points. But it may help you all pinpoint the problem.

[GeorgePantelakis]

Hello @gcwilson. Sorry for the big delay. To answer some of the questions. I do not know if it is the new implementation, we used the code for HEAD on 2024-04-16. As @tomato42 said if you tell me a specific function, I can search if it is called. Now for the test harness, sure, we will create tomorrow a toolkit so you can easily test it yourself. If there is anything else feel free to ask.

[beldmit]

@davidben could you please provide more details?

[davidben]

Sure. Just tell valgrind that the secret data is "uninitialized". Then when you intentionally branch on or otherwise reveal data that is now public, you need to mark it "initialized" first.
https://boringssl.googlesource.com/boringssl/+/6ab7c1482bf4cdc91c87bc512aaf68ffb18975ec/crypto/internal.h#568

Valgrind will then do data flow analysis and flag when you index or branch based on "uninitialized" memory.

[glengillman]

Thank you. Glen Gillman On May 8, 2024, at 11:50 AM, David Benjamin ***@***.***> wrote:  Sure. Just tell valgrind that the secret data is "uninitialized". Then when you intentionally branch on or otherwise reveal data that is now public, you need to mark it "initialized" first. https://boringssl.googlesource.com/boringssl/+/6ab7c1482bf4cdc91c87bc512aaf68ffb18975ec/crypto/internal.h#568 Valgrind will then do data flow analysis and flag when you index or branch based on "uninitialized" memory. — Reply to this email directly, view it on GitHub<#24253 (comment)>, or unsubscribe<https://github.com/notifications/unsubscribe-auth/AG6FQAFITXZMNWAWTFQ7MULZBJJVJAVCNFSM6AAAAABGWW2EAGVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDCMBRGAYDCMRTGQ>. You are receiving this because you are subscribed to this thread.Message ID: ***@***.***>

[beldmit]

Just tell valgrind that the secret data is "uninitialized". Then when you intentionally branch on or otherwise reveal data that is now public, you need to mark it "initialized" first.

Nice trick!

[GeorgePantelakis]

@gcwilson, we have created a toolkit for Minerva. For now, it has only OpenSSL in it. You can find it at https://github.com/GeorgePantelakis/minerva-toolkit. For any questions or issues feel free to reach us.