Crypto++ vulnerable to the Marvin Attack

[tomato42]

Crypto++ Issue Report

I've verified that the Crypto++ is vulnerable to the Marvin Attack—a timing variant of the well-known Bleichenbacher attack.

I've executed the test on ArchLinux, using crypto++ 8.9.0 from the Arch repository. The reproducer is available in the marvin-toolkit repository. It was compiled with a simple g++ -o time_decrypt -lcryptopp time_decrypt.cpp.

When executed on AMD Ryzen 5 5600X, I'm able to detect a side-channel signal when performing decryption with PKCS#1 v1.5 padding. The results are statistically significant with just few hundred measurement pairs, but below I'm showing results of a run with 100k repeats to show the size of the side-channel more clearly.

The test summary:

Sign test mean p-value: 0.2339, median p-value: 4.255e-12, min p-value: 3.18e-88
Friedman test (chisquare approximation) for all samples
p-value: 0.0
Worst pair: 1(no_header_with_payload_48), 5(valid_0)
Mean of differences: 3.61457e-07s, 95% CI: 2.63026e-07s, 4.577243e-07s (±9.735e-08s)
Median of differences: 4.80000e-07s, 95% CI: 4.30000e-07s, 5.200001e-07s (±4.500e-08s)
Trimmed mean (5%) of differences: 3.84809e-07s, 95% CI: 3.26061e-07s, 4.382825e-07s (±5.611e-08s)
Trimmed mean (25%) of differences: 4.82399e-07s, 95% CI: 4.37442e-07s, 5.255875e-07s (±4.407e-08s)
Trimmed mean (45%) of differences: 4.77529e-07s, 95% CI: 4.31482e-07s, 5.214141e-07s (±4.497e-08s)
Trimean of differences: 4.63125e-07s, 95% CI: 4.07500e-07s, 5.025002e-07s (±4.750e-08s)
Layperson explanation: Definite side-channel detected, implementation is VULNERABLE

legend:

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

Explanation for the ciphertexts is in the step2.py file.

As can be read from the graph, there's a clear difference between valid (probes 5, 6, and 7) and invalid ciphertexts. Moreover, the probe 2 is significantly different from others, which suggests a side-channel leakage in the numerical library (the last multiplication to apply deblinder, the last Montgormery reduction, or conversion of the arbitrary precision integer to a byte string), which means that that all padding modes that use the same RSADP() primitive will be similarly vulnerable, that means RSA-OAEP too.

(side note: I'm not a C++ programmer, so any help to make the reproducer cleaner, and command-line configurable, like the ones for openssl, pyca-cryptography, etc. will be really appreciated)

[tomato42]

@noloader any progress on this?