Summary

The implementation of RSA decryption with PKCS#1 v1.5 padding is vulnerable to a timing variant of the Bleichenabcher attack called the Marvin Attack.

Details

The timing of the openssl_private_decrypt() function depends on there being a message returned or not, that can be used as an oracle in a Bleichenbacher style attack. That in turn will allow decryption of captured ciphertexts or forging signatures using the key used in the decryption API.

Running PHP 8.2.12 with OpenSSL 3.1.4 on Archlinux.

By executing a test with 100k measurement per probe on an AMD Ryzen 5 5600X, with no special configuration, I've got the following statistically significant result:

Sign test mean p-value: 0.3491, median p-value: 0.266, min p-value: 2.097e-14
Friedman test (chisquare approximation) for all samples
p-value: 4.725229447597475e-40
Worst pair: 3(no_structure), 7(valid_192)
Mean of differences: 2.50389e-07s, 95% CI: -1.19522e-07s, 5.698823e-07s (±3.447e-07s)
Median of differences: 6.00000e-08s, 95% CI: 4.00000e-08s, 7.000000e-08s (±1.500e-08s)
Trimmed mean (5%) of differences: 8.20218e-08s, 95% CI: 4.41569e-08s, 1.135944e-07s (±3.472e-08s)
Trimmed mean (25%) of differences: 6.99484e-08s, 95% CI: 3.93115e-08s, 9.622458e-08s (±2.846e-08s)
Trimmed mean (45%) of differences: 5.62543e-08s, 95% CI: 3.89805e-08s, 7.136500e-08s (±1.619e-08s)
Trimean of differences: 7.22500e-08s, 95% CI: 4.50000e-08s, 9.200000e-08s (±2.350e-08s)
Layperson explanation: Definite side-channel detected, implementation is VULNERABLE

confidence intervals for the differences between samples:

legend to 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

probes are explained in the step2.py script in the marvin-toolkit repo

PoC

To reproduce the result, use the marvin-toolkit.

Execute the step0.sh, step1.sh and step2-alt.sh (you may want to comment out generation of ciphertexts for 1024 and 4096 bit keys in the step2-alt.sh file).

After that, execute the reproducer capturing the timing of the ciphertexts:

<?php

$privateKeyPath = 'rsa2048/pkcs8.pem';
$ciphertextPath = 'rsa2048_repeat/ciphers.bin';
$ciphertextSize = 256;
$timesPath = 'rsa2048_repeat/raw_times.csv';

$privateKey = openssl_pkey_get_private(file_get_contents($privateKeyPath), '');

if ($privateKey === false) {
    die('Failed to load private key');
}

$ciphertextHandle = fopen($ciphertextPath, 'rb');

if ($ciphertextHandle === false) {
    die('Failed to open ciphertext file');
}

$timesPath = fopen($timesPath, 'wt');

if ($timesPath === false) {
    die("Can't open output file");
}

if (!fwrite($timesPath, "raw_times\n")) {
    die("Can't write to output file");
}

while (!feof($ciphertextHandle)) {

    $encryptedData = fread($ciphertextHandle, $ciphertextSize);
    $decryptedData = null;

    $timeBefore = hrtime(true);

    $result = openssl_private_decrypt($encryptedData, $decryptedData, $privateKey);

    $timeAfter = hrtime(true);
    $timeDiff = $timeAfter - $timeBefore;
    if (!fwrite($timesPath, "{$timeDiff}\n")) {
        die("can't write to file");
    }

}

openssl_pkey_free($privateKey);
?>

Then extract the results based on order they've been executed:

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

(we specify clock frequency as 1000MHz as the script above is using ns resolution clock)

and run analysis:

PYTHONPATH=tlsfuzzer marvin-venv/bin/python3 tlsfuzzer/tlsfuzzer/analysis.py --verbose -o rsa2048_repeat

Detailed information about generated files is present in the tlsfuzzer documentation. Therein are also instructions to improve quality of gathered data (useful for proving absence of a side-channel, as that requires collection of much larger sample sizes)

Impact

All users of the RSA decryption API using it with the PKCS#1 v1.5 padding will be vulnerable to timing attacks.