opencryptoki vulnerable to the Marvin Attack

[kkaarreell]

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

I've executed the test on RHEL-9, using opencryptoki opencryptoki-3.21.0, on a ICA token and openssl-3.0.7-18.el9_2 . I will attach the reproducer shortly. The testing and analysis has been executed using the marvin-toolkit.

The test summary:

tlsfuzzer analyse.py version 5 analysis
Sign test mean p-value: 0.1115, median p-value: 2.313e-15, min p-value: 2.419e-286
Friedman test (chisquare approximation) for all samples
p-value: 0.0
Worst pair: 0(header_only), 5(valid_0)
Mean of differences: 1.47574e+05s, 95% CI: -1.57720e+06s, 2.066035e+06s (±1.822e+06s)
Median of differences: -3.76000e-07s, 95% CI: -3.98000e-07s, -3.570000e-07s (±2.050e-08s)
Trimmed mean (5%) of differences: -5.02983e-07s, 95% CI: -2.09351e-06s, 9.483105e-07s (±1.521e-06s)
Trimmed mean (25%) of differences: -4.14615e-07s, 95% CI: -9.93803e-07s, 1.096255e-07s (±5.517e-07s)
Trimmed mean (45%) of differences: -3.74689e-07s, 95% CI: -3.96070e-07s, -3.536652e-07s (±2.120e-08s)
Trimean of differences: -6.80000e-07s, 95% CI: -4.63625e-06s, 2.836875e-06s (±3.737e-06s)
Layperson explanation: Definite side-channel detected, implementation is VULNERABLE
For detailed report see rsa2048_repeat/report.csv

According to Hubert Kario:

I can confirm that the layperson explanation is correct: there
is a detectable side-channel. Not only is the correctness of the
plaintext is leaking, the length of the message is leaking too.

That being said, the fact that no_header_with_payload_48 and
signature_padding_8 is similar to the valid_0 and valid_48 suggests
that there may be a bug in the depadding code...

I am attaching an archive with the report and will kindly ask tomato42 to provide more detailed explanation.

[kkaarreell]

reproducer.zip

The attached archive contain a C program gathering duration of RSA decryption and test.sh is a shell script doing a system setup and verifying the functionality. For the actual analysis I had:

1. On my laptop installed the marvin toolkit following the instructions and generated encrypted data using step0.sh, step1.sh and step2-alt.sh scripts. In the last script I have modified the command to

PYTHONPATH=tlsfuzzer ./marvin-venv/bin/python ./step2.py \
-c rsa2048/cert.pem -o rsa2048_repeat \
--repeat 2000000 --verbose \
no_structure no_padding=48 signature_padding=8 \
valid_repeated_byte_payload="246 0xff" \
valid_repeated_byte_payload="246 0x01" \
valid=48 header_only \
no_header_with_payload=48 zero_byte_in_padding="48 4" \
valid=0 valid=192 valid=246

2. I have copied the generated rsa2048_repeat/ciphers.bin and rsa2048/key.pem to my s390x test system
3. Then isolated CPU1 on a test system so I could dedicate this processor for the test script
4. Then imported key.pem to opencryptoki using p11sak import rsa private --slot $SLOT --pin $USER_PIN -L "marvinRSAkey" -F key.pem -a P
5. On a test system ran test.sh to do the setup
6. Executed the test (it took 3 days or so) with taskset --cpu-list 1 ./rsa_test -s $SLOT -p $USER_PIN -f ciphers.bin -o raw_times.csv -k marvinRSAkey
7. copied the gathered raw_times.csv to my laptop to rsa2048_repeat directory
8. started the analysis with

$ PYTHONPATH=tlsfuzzer marvin-venv/bin/python3 tlsfuzzer/tlsfuzzer/extract.py -l rsa2048_repeat/log.csv --raw-times rsa2048_repeat/raw_times.csv -o rsa2048_repeat/ --clock-frequency 1000
$ PYTHONPATH=tlsfuzzer marvin-venv/bin/python tlsfuzzer/tlsfuzzer/analysis.py -o rsa2048_repeat

[tomato42]

And a slightly more graphical representation of the results:

@opencryptoki will you assign a CVE for this, or should we ask for one?

[ifranzki]

@tomato42 How is the Marvin attack different to the RSA PKCS #1.5 timing attack we worked on some time ago (it was regarding the IBMCA provider back then)?

I wonder because I did spend quite an effort to harden Opencryptoki against those kind of timing attacks on RSA private key operations back then as well. See commits
1aba660 "ica: Support RSA blinding for private key performed via libica"
bf73a0d "common: Make rsa_parse_block() constant time for format 2"
365a200 "common: Make decode_eme_oaep() constant time"

@kkaarreell can you please check if those commits are part of the OpenCryptoki level you are using? They are all in the upstream 3.21.0 release.

[ngothan]

@ifranzki , i have checked and confirmed that those commits are part of the OpenCryptoki level @kkaarreell is using.

[kkaarreell]

@kkaarreell can you please check if those commits are part of the OpenCryptoki level you are using? They are all in the upstream 3.21.0 release.

Yes, these are present. I will also do the testing with opencryptoki-3.22.0 and post an update here later.

[tomato42]

@ifranzki it's the same attack. I don't know why it's visible despite those patches, likely something was still missed. Unfortunately, the best advice I have for figuring out where the leakage is coming from is to follow the approach documented in https://securitypitfalls.wordpress.com/2023/09/29/debugging-timing-side-channel-leaks/

[tomato42]

Actually, this is incorrect:

opencryptoki/usr/lib/common/mech_rsa.c

Lines 363 to 371 in 239fefc

	/*
	* since at this point the |msg_index| does not provide the signal
	* indicating if the padding check failed or not, we don't have to worry
	* about leaking the length of returned message, we still need to ensure
	* that we read contents of both buffers so that cache accesses don't leak
	* the value of |good|
	*/
	for (i = msg_index, j = 0; i < in_data_len && j < *out_data_len; i++, j++)
	out_data[j] = constant_time_select_8(ok, in_data[i], out_data[j]);

msg_index does not provide the signal in openssl code because openssl implements implicit rejection, without implicit rejection msg_index is sensitive and it must not be leaked!

You need to use algorithm from RSA_padding_check_PKCS1_type_2(), NOT from ossl_rsa_padding_check_PKCS1_type_2()

[ifranzki]

@kkaarreell Could you please give it a try with the commit from #732 ? This should apply clean on 3.21.0 as well.

[tomato42]

@ifranzki we have rather noisy s390x machines (no dedicated cores), running the test on a system without CPU overcommitting will provide actionable results much quicker

[kkaarreell]

@kkaarreell Could you please give it a try with the commit from #732 ? This should apply clean on 3.21.0 as well.

I've just configured two systems, one with opencryptoki-3.22.0 and another one with opencryptoki-3.22.0+patch from #732. It will take ~2 days to get measurements for ciphers.bin from the original report.

[ifranzki]

@ifranzki we have rather noisy s390x machines (no dedicated cores), running the test on a system without CPU overcommitting will provide actionable results much quicker

I will definitively setup the tests on one of my machine as well. However, this will take a bit time to setup and verify. Also I will be on vacation for the next 2 weeks, returning in the first week of January. So I won't be able to produce any measurements myself until then.

@kkaarreell Thanks for running it. Looking forward to see the results :-)

[kkaarreell]

I got lucky to get a bit faster systems. I have tested opencryptoki-3.22.0 and opencryptoki-3.22.0+patch on the same sample as I have used with opencryptoki-3.21.0.

For opencryptoki-3.22.0 the plot looks very similar to the one for opencryptoki-3.21.0.

For patched opencryptoki-3.22.0 the output is:

Sign test mean p-value: 0.4112, median p-value: 0.3854, min p-value: 0.004687
Friedman test (chisquare approximation) for all samples
p-value: 0.12235861390351627
Worst pair: 7(valid_192), 11(zero_byte_in_padding_48_4)
Mean of differences: -1.92932e-06s, 95% CI: -4.07071e-06s, 8.186660e-08s (±2.076e-06s)
Median of differences: -3.50000e-08s, 95% CI: -6.00000e-08s, -1.000000e-08s (±2.500e-08s)
Trimmed mean (5%) of differences: -6.31178e-07s, 95% CI: -1.87028e-06s, 4.500907e-07s (±1.160e-06s)
Trimmed mean (25%) of differences: -2.26465e-07s, 95% CI: -5.51312e-07s, 6.229295e-08s (±3.068e-07s)
Trimmed mean (45%) of differences: -4.01787e-08s, 95% CI: -6.82642e-08s, -1.224179e-08s (±2.801e-08s)
Trimean of differences: -4.88562e-07s, 95% CI: -1.50156e-06s, 3.625000e-07s (±9.320e-07s)
Layperson explanation: Large confidence intervals detected, collecting more data necessary. Side channel leakege smaller than 2.801e-08s is possible
For detailed report see rsa2048_repeat.opencryptoki-3.22.0.patched/report.csv

This is an improvement, at the same time we need to do the analysis with 10x bigger sample to test with <1e-8s resolution. I will continue with the testing in upcomming days and weeks. :-)

[ifranzki]

How many samples have that been? 2000000 like in your instructions above?

[kkaarreell]

How many samples have that been? 2000000 like in your instructions above?

Yes. This is the value used in the script, it uses 12 different configurations for each "iteration" so in the end we have 12x2000000 encrypted messages.

[ifranzki]

I have finished my own run with 2000000 iterations with the patched opencryptoki-3.22.0 on a IBM z16 LPAR.
Similar plot as your run with the patched opencryptoki-3.22.0, just the times are a bit smaller.

Sign test mean p-value: 0.4299, median p-value: 0.4406, min p-value: 0.001031
Friedman test (chisquare approximation) for all samples
p-value: 0.10336440656922456
Worst pair: 7(valid_192), 9(valid_repeated_byte_payload_246_1)
Mean of differences: -1.06932e-06s, 95% CI: -3.91868e-06s, 3.296294e-08s (±1.976e-06s)
Median of differences: -6.00000e-09s, 95% CI: -1.50000e-08s, 2.000000e-09s (±8.500e-09s)
Trimmed mean (5%) of differences: -1.25569e-08s, 95% CI: -2.15190e-08s, -3.643718e-09s (±8.938e-09s)
Trimmed mean (25%) of differences: -9.13687e-09s, 95% CI: -1.50167e-08s, -1.675896e-09s (±6.670e-09s)
Trimmed mean (45%) of differences: -7.83098e-09s, 95% CI: -1.55907e-08s, 1.884900e-10s (±7.890e-09s)
Trimean of differences: -8.50000e-09s, 95% CI: -1.52500e-08s, -1.250000e-09s (±7.000e-09s)
Layperson explanation: Large confidence intervals detected, collecting more data necessary. Side channel leakege smaller than 6.670e-09s is possible
For detailed report see rsa2048_repeat/report.csv

[tomato42]

5 times better results (smaller CI) when running on more quiet system is expected. Karel would have to run 18 times larger sample to get similar confidence interval

While 6.6ns is quite good, I would recommend to get it to the 1ns range, which will require about 36 times as much data (around 72 million total), before saying it's "definitely fixed"

Remember to generate new set of ciphertexts for every run, and use the combine.py script from tlsfuzzer to combine them before running analysis.py, see timing analysis chapter in the tlsfuzzer documentation.

[kkaarreell]

I was testing on ICA token. Is dealing with other type of tokens different codewise? Should we test them separately? I can test swtoken but I am not sure it makes sense.

[ifranzki]

I was measuring on ICA token, too.

The code in question (which is affected by the fix in #732) is used by both, the soft token and the ICA token. So without the fix you should see the same leaks on the soft token, but the fix fixes both, the ICA and the soft token.

The other tokens (CCA, EP11) are secure key tokens and the complete RSA decrypt operation (including unpadding) is performed inside the crypto cards. So this is out of scope for Opencryptoki.

[tomato42]

The other tokens (CCA, EP11) are secure key tokens and the complete RSA decrypt operation (including unpadding) is performed inside the crypto cards. So this is out of scope for Opencryptoki.

No. You still have to pass the error and returned byte array in constant time, if you don't then opencryptoki will create a side-channel. That's part of the CVE-2023-5992 in OpenSC

[ifranzki]

No. You still have to pass the error and returned byte array in constant time, if you don't then opencryptoki will create a side-channel.

Right, I am aware about this and the opencryptoki code does it that way.

[tomato42]

Have you tested it?

[ifranzki]

Yes, I did run dudect (https://github.com/oreparaz/dudect) based tests against it, comparing the timing of an invalid padding versus a valid padding.

[tomato42]

I wouldn't trust dudect to detect small side channels: oreparaz/dudect#27

[kkaarreell]

I have done analysis on a bigger sample (11 samples each of size 12x2000000 combined), gathered on two test systems.

tlsfuzzer analyse.py version 5 analysis
Sign test mean p-value: 0.2427, median p-value: 0.06112, min p-value: 5.523e-07
Friedman test (chisquare approximation) for all samples
p-value: 9.524010056385803e-12
Worst pair: 7(valid_192), 8(valid_246)
Mean of differences: -1.61442e-07s, 95% CI: -5.42176e-07s, 1.792164e-07s (±3.607e-07s)
Median of differences: -7.00000e-09s, 95% CI: -9.00000e-09s, -3.000000e-09s (±3.000e-09s)
Trimmed mean (5%) of differences: -8.14882e-08s, 95% CI: -2.83508e-07s, 7.536090e-08s (±1.794e-07s)
Trimmed mean (25%) of differences: -1.03683e-08s, 95% CI: -1.49502e-08s, -3.354730e-09s (±5.798e-09s)
Trimmed mean (45%) of differences: -7.08725e-09s, 95% CI: -9.71596e-09s, -3.070455e-09s (±3.323e-09s)
Trimean of differences: -1.30000e-08s, 95% CI: -2.20000e-08s, 1.000000e-09s (±1.150e-08s)
Layperson explanation: Definite side-channel detected, implementation is VULNERABLE

[ifranzki]

I have merged PR #732 for now.
The changes in that PR make the leak definitely much smaller than it was before, although there still seems to be a leak.
Merging the PR has close this issue, but since there seems to be still a leak, I am keeping this open until fully resolved.

[ifranzki]

I have implemented implicit rejection in PR #737. With this the following was measured using data produced by tlsfuzzer/scripts/marvin-ciphertext-generator.py (3200000 iterations) with the ICA token:

tlsfuzzer analyse.py version 5 analysis
Sign test mean p-value: 0.5395, median p-value: 0.544, min p-value: 0.01027
Friedman test (chisquare approximation) for all samples
p-value: 0.8372095610456612
Worst pair: 17(well formed with very long synthethic PMS), 18(zero byte in eight byte of padding)
Mean of differences: 6.81161e-08s, 95% CI: -2.07887e-08s, 2.316728e-07s (±1.262e-07s)
Median of differences: -5.76900e-10s, 95% CI: -1.34610e-09s, 0.000000e+00s (±6.731e-10s)
Trimmed mean (5%) of differences: -9.59478e-10s, 95% CI: -1.82256e-09s, 3.193121e-12s (±9.129e-10s)
Trimmed mean (25%) of differences: -6.79969e-10s, 95% CI: -1.42794e-09s, 6.169134e-12s (±7.171e-10s)
Trimmed mean (45%) of differences: -6.41603e-10s, 95% CI: -1.45346e-09s, 3.892648e-11s (±7.462e-10s)
Trimean of differences: -7.21125e-10s, 95% CI: -1.39425e-09s, 0.000000e+00s (±6.971e-10s)
Layperson explanation: Implementation most likely not providing a timing side-channel signal
For detailed report see /data/rsa2048_repeat/report.csv

[tomato42]

What's the CVE number for this?

[p4zuu]

What's the CVE number for this?

CVE-2024-0914 has been allocated.