"Fix" for CVE-2020-25658 confirmed as insufficient

[tomato42]

I've executed the scripts in the https://github.com/tomato42/marvin-toolkit/tree/master/example/python-rsa and have confirmed that the implementation of RSA decryption in python-rsa 4.9 is leaky, as predicted in issue #165.

I've executed the test with 10k repeats (note that step2-alt.sh by default generates 100k repeats) on a Ryzen 5600X CPU.

The results show a clear difference between valid and invalid ciphertexts. In other words, it is vulnerable to the Marvin Attack

summary data:

Sign test mean p-value: 0.2265, median p-value: 0.06723, min p-value: 6.156e-21
Friedman test (chisquare approximation) for all samples
p-value: 3.2244244003488133e-62
Worst pair: 3(no_structure), 6(valid_48)
Mean of differences: -4.87631e-06s, 95% CI: -7.78079e-06s, -1.817809e-06s (±2.981e-06s)
Median of differences: -1.76900e-06s, 95% CI: -2.15800e-06s, -1.380000e-06s (±3.890e-07s)
Trimmed mean (5%) of differences: -1.96580e-06s, 95% CI: -2.65470e-06s, -1.330388e-06s (±6.622e-07s)
Trimmed mean (25%) of differences: -1.62838e-06s, 95% CI: -1.95745e-06s, -1.240258e-06s (±3.586e-07s)
Trimmed mean (45%) of differences: -1.77149e-06s, 95% CI: -2.10967e-06s, -1.402567e-06s (±3.535e-07s)
Trimean of differences: -1.61550e-06s, 95% CI: -2.02775e-06s, -1.233438e-06s (±3.972e-07s)

legend for the graph:

ID,Name
0,header_only
1,no_header_with_payload_48
2,no_padding_48
3,no_structure
4,signature_padding_8
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

(explanations for the ciphertexts are in the step2.py file)

[eslerm]

The README acknowledges that timing attacks, like CVE-2020-25658, can never be fixed in a pure-Python implementation. Downstream users of python-rsa should be well aware that they are not safe from these attacks.

Security
Because of how Python internally stores numbers, it is very hard (if not impossible) to make a pure-Python program secure against timing attacks. This library is no exception, so use it with care. See https://securitypitfalls.wordpress.com/2018/08/03/constant-time-compare-in-python/ for more info.

Perhaps Red Hat's CNA can update the CVE to explain this.

Since this project has already addressed that CVE-2020-25658 is out of their projects scope to fix, with discussion and clear documentation, I am not sure what this issue is for.

[tomato42]

I am not sure what this issue is for.

To show that the documentation statements aren't simple assertions, but are backed by data.

[eslerm]

I believe we should respect the security scope of this pure-Python project. python-rsa would need to change the purpose of their project to fix CVE-2020-25658.

It would be nice if it is very hard (if not impossible) were changed to it is not possible for clarity.

Raising awareness of this CVE is important. Downstream projects are affected by CVE-2020-25658, and issues may need to be filed to make them aware. Ideally, this could cause a dependency shift away from pure-Python. Appreciate your bandit report.

[sybrenstuvel]

To show that the documentation statements aren't simple assertions, but are backed by data.

Much appreciated, thanks.