BouncyCastle vulnerable to a timing variant of Bleichenbacher called Marvin Attack

[tomato42]

(As I've sent to the security mailing list three emails, last one over 2 weeks ago, and haven't received anything but automated reply that the email was received, I'm making the issue public here. What follows after the question is a verbatim copy of the last email.)

Question: Should I ask for CVE assignment for it?

I've tested both PKCS#1 v1.5 and OAEP API and verified that both provide
a clear side-channel signal useful in Bleichenbacher-like attacks.

Since my previous emails have received nothing but an automated reply
for over a week, I'll be making this issue in BouncyCastle public in
two weeks (on 6th of November) if that doesn't change.

I've tested bcprov-jdk18on-17.jar on OpenJDK 1.8.0_372 from ArchLinux on
an AMD Ryzen 5 5600X CPU. I did not perform any special tuning to
make the noise smaller.

I've used the test harnesses in attachment to run the test data generated
by the step2-alt.sh and step2-oaep-alt.sh from
https://github.com/tomato42/marvin-toolkit/
(though I did test just 2048 bit keys, not the 1024 and 4096 generated by
them too).
Both of them accept 3 parameters: a path to a RSA PKCS#8 DER key, path to
a file with concatenation of RSA ciphertexts (they both assume those are 256
bytes long), and an output csv file where timing of the processing will be
written. See the examples/pyca-cryptography in the above repo on how to
process that csv file further.

For both padding modes the Friedman test p-value is smaller than what
a double precision floating point number can represent (i.e. it's reported
as 0).
That's in spite of using just 10k and 100k sample size for pkcs1 and oaep
test respectively.

Which means the timing signal is extremely strong and definitely exploitable
over the network.

Looking more closely at the results, it's clear that the PKCS#1 interface
leaks timing data through raising of an exception, and the OAEP interface leaks timing data through the bit size of the decrypted value (EM in PKCS#1
nomenclature). Though those are very imprecise results, additional
side-channels may be present.

See the Marvin paper for suggestions how to fix this:
https://people.redhat.com/~hkario/marvin/
A bit more information is also present in the draft specifying the
RSA implicit rejection mechanism I'm working to standardise:
https://github.com/tomato42/marvin-ietf

See step2.py for explanation of the meaning of the probes, the legend for
pkcs1.png is as follows:

ID,Name
0,header_only
1,no_header_with_payload_48
2,no_padding_48
3,no_structure
4,signature_padding_0
5,valid_0
6,valid_48
7,valid_192
8,valid_246
9,valid_repeated_byte_payload_246_1
10,valid_repeated_byte_payload_246_255
11,zero_byte_in_padding_48_4

for oaep.png is as follows:

ID,Name
0,no_padding_48
1,no_structure
2,signature_padding_0
3,too_short_payload_0_1
4,too_short_payload_0_3
5,too_short_payload_0_7
6,too_short_payload_0_15
7,valid_0
8,valid_repeated_byte_payload_245_0

pairwise sign test and Wilcoxon signed rank test results are in the csv files:
oaep.csv
pkcs1.csv

Code:
OAEPDecryption.txt
PKCS1Decryption.txt

[dghgit]

Apologies about the delay in responding, we only check the address every couple of weeks and it gets more than its fair share of spam. We've found your original emails though with the attachment. Taking a look.

[dghgit]

We've done an initial pass.

If you're up for it, we're interested in following this up by looking at what our TLS API is doing.

While the figures around the examples are interesting, the issues related to exception throwing on javax.crypto.Cipher are well known, and it's a function of the JCE API rather than the BC provider, which in this case is simply following the documented API.

The BCJSSE provider does attempt to work around things already, but it's quite likely with better analysis we could find a way of doing that better as well. We will try and put something together for collecting timing data using your tools and be back in touch.

[tomato42]

It's possible to fix it by not raising an exception, see the implicit rejection (a.k.a. Marvin workaround) documented in the Marvin paper, implemented by OpenSSL, NSS, and proposed in https://datatracker.ietf.org/doc/draft-kario-rsa-guidance/ (I'll be presenting it for CFRG adoption on IETF 118 this Thursday)

For testing TLS you can use either the regular script or the one that expects implicit rejection

[dghgit]

Yes, we arrived at that conclusion a while ago - I think with the JSSE we're probably going to need to provide a custom "something" to do it though. Our JSSE provider is used with other JCE providers as well so we'll still need to make sure we can still accommodate them as well. First, collect some numbers though, can't flatten a curve we haven't measured.

Good luck with the presentation.

[tomato42]

I think with the JSSE we're probably going to need to provide a custom "something" to do it though

I'm not super familiar with how provider infrastructure in Java works, but isn't it the case that you can either provide a way to do raw RSA operations (i.e. the RSADP() primitive from PKCS#1), or full operations (i.e the complete PKCS#1 v1.5 decryption)?

(I'm genuinely asking. If there are interfaces where implicit rejection won't work, I'd really like to know about them.)

[dghgit]

So we think, with a "little bending of the rules" we can do this. We can provide raw RSA, but we need to stay mindful of the fact that we're also trying to make it possible for people to certify things, which really rules out raw RSA as a solution, with FIPS and Common Criteria providing developer access to raw RSA is frowned upon, the expectation is that you provide access to full operations only, so as attractive as it is, raw RSA isn't really going to cut it.

We're pretty sure we can still take advantage of implicit rejection though - for example the Java cipher class has an unwrap() method on it which takes a string for the algorithm of the key you want back. @peterdettman pointed out yesterday we could have some special algorithm names which could be used to flag that implicit rejection is acceptable and that exception throwing is not expected, so something like

Cipher rsaCipher = Cipher.getInstance("RSA/NONE/PKCS1Encoding", "BC");

rsaCipher.init(Cipher.UNWRAP_MODE, rsaPrivateKey);

Key secret = rsaCipher.unwrap(encapsulation, "TlsPremasterSecret", Cipher.SECRET_KEY);

Could be used to flag to the provider that "I don't want to see an exception", alternately there's also:

Cipher rsaCipher = Cipher.getInstance("RSA/ImplicitRejection/PKCS1Encoding", "BC");

which could be used to flag the "I don't want to see an exception" mode.

We'll probably need to try a few things and see what works best. Sometimes what looks great in theory doesn't always work well in practice... but there's options.

[tomato42]

For FIPS, the PKCS#1 v1.5 will not be allowed at all after end of this year, which is like 6 weeks. So I'm not entirely sure how it's relevant...

For implicit rejection to actually help users of the library, it needs to be the default behaviour.
The legacy depadding may be available for debugging, but it should be documented as inherently insecure.

Also, it's not just about TLS, it affects everything that can use encryption with PKCS#1 v1.5 padding: CMS, JWT, XMLencryption, etc.

[dghgit]

Yes, although keep in mind it is PKCS#1.5 encryption they're disallowing and as it's been turned into a soft transition for FIPS 140-2 modules, I've a feeling there may be a bit of a delay on even that being realized fully.

Fully aware it's not just applicable to TLS, have to start somewhere though.

[tomato42]

When will you assign a CVE to this issue?

[dghgit]

CVE's are not free. We will, and do, raise them when appropriate however the issues with the Cipher API in Java are well documented, and while the numbers are interesting, we haven't come up with anything solid. Our TLS API already incorporates some counter measures and the numbers above are not for our TLS API. We have not found anything which has required the allocation of a CVE.

That's not to say we're not interested in moving to more of the code base making use of what's documented in the RFC that's currently in draft, we big fans of dealing with possible issues early, however that's not even a standard at the moment, and while worthy of investigation is clearly not something we can deploy.

And no, not ever throwing an exception is not an option, we could add a new implementation to do this, but people have being using javax.crypto.Cipher for over 20 years now and there are millions of lines of code relying on this behavior. For all those people the suggested fix is likely to cause other security issues as at that point it will appear the Cipher API has worked but it will be doing so in an application which is not designed to cope with the change in behavior.

[tomato42]

CVEs are also the best tool we have to inform users that they are using vulnerable software.
And while I do empathise with having to deal with bad APIs, attackers don't really care why a particular leakage is there, just if it is there.

[dghgit]

On a slightly different note, I'll be at the first half of IETF 119 Brisbane, 2024. Is the RFC draft going to be presented again there as a lead up to a vote?

[tomato42]

I don't think so. There was a general consensus for the draft adoption by the CFRG at IETF 118. I don't think it will be ready for WGLC by IETF 119, so I'm not sure which vote you mean...
If I'll attend IETF 119, it will be remotely.

[tomato42]

the numbers above are not for our TLS API.

The offer to run the test against pure BouncyCastle TLS stack still stands. Provide instructions similar to what I have for other implementations, e.g. go, and I'll run the test against it.

[dghgit]

Sure, we'll put something together. You'll just need to give us a few days, we're flat out dealing with certification work at the moment.