CVE-2020-25659 "fix" confirmed as insufficient

[tomato42]

Different comments around CVE-2020-25659 (like in #6167 and #5507) state that the fix is incomplete and documentation (https://cryptography.io/en/latest/limitations/#rsa-pkcs1-v1-5-constant-time-decryption) specifies that PKCS#1 v1.5 encryption padding is vulnerable to side-channel attacks.

I'm filing this issue with the evidence that this is a confirmed fact, not just an assertion based on code analysis.

While I've executed it with python3-cryptography-3.2.1-6.el8.x86_64, python36-3.6.8-38.module+el8.5.0+12207+5c5719bc.x86_64, and openssl-1.1.1k-10.el8_9 both the cryptography package has the CVE-2020-25659 fix and openssl has the CVE-2022-4304 fix.

The test was executed with 2048 bit RSA, with 100k repeats per probe, in a VM on a fairly noisy/busy 2.3GHz Icelake Xeon system.

The measured side channel is about 400ns, so it should be fairly easy to exploit even over remote network connections.

analysis.py summary:

tlsfuzzer analyse.py version 5 analysis
Sign test mean p-value: 0.3447, median p-value: 0.1886, min p-value: 2.459e-13
Friedman test (chisquare approximation) for all samples
p-value: 8.947806111025913e-27
Worst pair: 1(no_header_with_payload_48), 6(valid_48)
Mean of differences: -5.35165e-07s, 95% CI: -1.51931e-06s, 4.859572e-07s (±1.003e-06s)
Median of differences: -4.50001e-07s, 95% CI: -5.85012e-07s, -3.309875e-07s (±1.270e-07s)
Trimmed mean (5%) of differences: -5.91658e-07s, 95% CI: -9.38480e-07s, -2.549461e-07s (±3.418e-07s)
Trimmed mean (25%) of differences: -5.80887e-07s, 95% CI: -7.53559e-07s, -4.100913e-07s (±1.717e-07s)
Trimmed mean (45%) of differences: -4.75457e-07s, 95% CI: -6.04405e-07s, -3.463844e-07s (±1.290e-07s)
Trimean of differences: -6.01688e-07s, 95% CI: -8.09003e-07s, -3.924847e-07s (±2.083e-07s)

Results for comparisons between individual samples are in the report.csv

Graphical representation of the confidence intervals of the difference between different classes to class 0:

mapping numbers to classes is in legend.csv
explanation of the ciphertexts generated is in the step2.py script.

You can reproduce this results using the script and instructions in https://github.com/tomato42/marvin-toolkit/tree/master/example/pyca-cryptography

[reaperhulk]

Thanks for the analysis @tomato42 😄 Are your OpenSSL changes to expose useful constant time APIs available in the OpenSSL 3.2.0 beta?

[tiran]

Yes, Hubert's rsa_pkcs1_implicit_rejection feature is in OpenSSL 3.2. Even better, it is enabled by default.

OpenSSL 3.0 in CentOS 9 Stream and RHEL 9.3 have a backport of the feature. (And yes, the backport broke test_decrypt_invalid_decrypt).

[tomato42]

Yes, it has been merged to 3.2.0 branch before first alpha was released: openssl/openssl#13817

[reaperhulk]

We landed a skip for that test when handling the implicit rejection in 7e33b0e

We'll undoubtedly start shipping OpenSSL 3.2.0 in our wheels when it is final, and at least one distribution has already backported -- is there anything we should change in our documentation here?

[tomato42]

Maybe link from documentation also to this issue, so that it's clear that the statements in the documentation are backed by real data?

Technically, it could list that the API will be secure if used together with OpenSSL that implements implicit rejection, but then people really should stop using PKCS#1v1.5 so I'd rather not do that.

If you decide to fix it, I think a small rephrasing in that section would be good:

For this reason we recommend not implementing online protocols that use
RSA PKCS1 v1.5 decryption with cryptography – 
independent of this limitation, such protocols generally have poor
security properties due to their lack of forward security.

The problem is not online protocols, it's any kind of interface which the attacker can measure the timing of. Online contexts, as stated in first sentence, would be better. But then there are situations in which seemingly offline systems can be attacked too:
https://arstechnica.com/information-technology/2023/06/hackers-can-steal-cryptographic-keys-by-video-recording-connected-power-leds-60-feet-away/
or
https://arstechnica.com/information-technology/2013/12/new-attack-steals-e-mail-decryption-keys-by-capturing-computer-sounds/
(the same side-channels can be used to measure processing much more precisely, or in situations where the decryptions are performed in batch operations, e.g. an email client that decrypts messages right after downloading them)

[tomato42]

ah, I also wonder about the status of CVE-2020-25659 itself, it is marked as "fixed", but that's not a good reflection of reality... I think a new one my be a right approach...

[tomato42]

A CVE-2023-50782 has been assigned to track this issue.

[kelvin-j-li]

i saw this from cryptography milestones -- https://github.com/pyca/cryptography/milestone/44
Does any one know when release 42 will be available?

Thanks!

[alex]

Probably in 2-3 weeks.

…

On Mon, Jan 8, 2024 at 1:33 AM Kelvin J Li ***@***.***> wrote: i saw this from cryptography milestones -- https://github.com/pyca/cryptography/milestone/44 Does any one know when release 42 will be available? Thanks! — Reply to this email directly, view it on GitHub <#9785 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAAAGBDHJAHBRADKO5TLHYDYNOHMJAVCNFSM6AAAAAA6RKJ36KVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMYTQOBQGQ2DSOBZGE> . You are receiving this because you are subscribed to this thread.Message ID: ***@***.***>

-- All that is necessary for evil to succeed is for good people to do nothing.

[kelvin-j-li]

[like] Kelvin Li reacted to your message:

…

________________________________ From: Alex Gaynor ***@***.***> Sent: Monday, January 8, 2024 12:02:32 PM To: pyca/cryptography ***@***.***> Cc: Kelvin Li ***@***.***>; Comment ***@***.***> Subject: [EXTERNAL] Re: [pyca/cryptography] CVE-2020-25659 "fix" confirmed as insufficient (Issue #9785) CAUTION This email is from an external sender, be cautious with links and attachments. Probably in 2-3 weeks.

On Mon, Jan 8, 2024 at 1:33 AM Kelvin J Li ***@***.***> wrote: i saw this from cryptography milestones -- https://github.com/pyca/cryptography/milestone/44 Does any one know when release 42 will be available? Thanks! — Reply to this email directly, view it on GitHub <#9785 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAAAGBDHJAHBRADKO5TLHYDYNOHMJAVCNFSM6AAAAAA6RKJ36KVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMYTQOBQGQ2DSOBZGE> . You are receiving this because you are subscribed to this thread.Message ID: ***@***.***>

-- All that is necessary for evil to succeed is for good people to do nothing. — Reply to this email directly, view it on GitHub<#9785 (comment)>, or unsubscribe<https://github.com/notifications/unsubscribe-auth/ARJDXT4EUBG3JBXIYKIDP3TYNPN5RAVCNFSM6AAAAAA6RKJ36KVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMYTQOBQHA3DSNRZGM>. You are receiving this because you commented.Message ID: ***@***.***> STATEMENT OF CONFIDENTIALITY The information contained in this email message and any attachments may be confidential and legally privileged and is intended for the use of the addressee(s) only. If you are not an intended recipient, please: (1) notify me immediately by replying to this message; (2) do not use, disseminate, distribute or reproduce any part of the message or any attachment; and (3) destroy all copies of this message and any attachments.

[alex]

We're about to perform release 42.0, which will resolve this via upgrading our OpenSSL to 3.2.0.

Users who manually link against older OpenSSL's will still be impacted, but at some level that should be considered an issue with their OpenSSL.