CVE-2020-25658 - Bleichenbacher-style timing oracle in PKCS#1 v1.5 decryption code

[tomato42]

Current PKCS#1 v1.5 decryption code:

python-rsa/rsa/pkcs1.py

Lines 246 to 267 in 6f59ff0

	blocksize = common.byte_size(priv_key.n)
	encrypted = transform.bytes2int(crypto)
	decrypted = priv_key.blinded_decrypt(encrypted)
	cleartext = transform.int2bytes(decrypted, blocksize)
	# Detect leading zeroes in the crypto. These are not reflected in the
	# encrypted value (as leading zeroes do not influence the value of an
	# integer). This fixes CVE-2020-13757.
	if len(crypto) > blocksize:
	raise DecryptionError('Decryption failed')
	# If we can't find the cleartext marker, decryption failed.
	if cleartext[0:2] != b'\x00\x02':
	raise DecryptionError('Decryption failed')
	# Find the 00 separator between the padding and the message
	try:
	sep_idx = cleartext.index(b'\x00', 2)
	except ValueError:
	raise DecryptionError('Decryption failed')
	return cleartext[sep_idx + 1:]

performs the checks on the decrypted value in turn, aborting as soon as first error is found, it also raises an exception in case of errors. This likely provides enough of a timing side channel to mount a Bleichenbacher style attack.

While it's unlikely that a completely side-channel free implementation is possible (see https://securitypitfalls.wordpress.com/2018/08/03/constant-time-compare-in-python/ ), it should be possible to minimise the side-channel by making at least the execution path the same irrespective of previous checks and by providing an API that returns a randomly generated secret in case of error (instead of leaking the timing side-channel by rising an exception) for uses that decrypted value directly as an input to a hash or use it as a symmetric key.

[tomato42]

The code is basically unchanged for at least 10 years:

python-rsa/rsa/pkcs1.py

Lines 120 to 135 in 3f8c551

	blocksize = common.byte_size(priv_key['n'])
	encrypted = transform.bytes2int(crypto)
	decrypted = core.decrypt_int(encrypted, priv_key['d'], priv_key['n'])
	cleartext = transform.int2bytes(decrypted, blocksize)
	# If we can't find the cleartext marker, decryption failed.
	if cleartext[0:2] != '\x00\x02':
	raise ValueError('Decryption failed')
	# Find the 00 separator between the padding and the message
	try:
	sep_idx = cleartext.index('\x00', 2)
	except ValueError:
	raise ValueError('Decryption failed')
	return cleartext[sep_idx+1:]

so we can be reasonably sure that all released versions since 2.1 (the first version that included RSA decryption API) are vulnerable

[ran-isenberg]

Hey guys, this seems like a critical security issue. We've been working with python-jose which depends on this repo.
Our security scanner, Snyk, tagged this repo with a high level risk security issue.
Is somebody working on this?
Thanks in advance

[tomato42]

1. it's not critical, it's medium severity, though we would need to calculate CVSS to be sure. That being said, I haven't seen any Bleichenbacher CVEs scored high, let alone critical
2. python-jose depends on python-rsa, but it will not use it if better libraries are available, you should use python-jose with pyca/cryptography, then python-rsa code will be unused and unexploitable
3. nobody is working on this; we've decided with Sybren to make it public specifically so that somebody else could start the work on this

[ran-isenberg]

Thanks for the quick reply.

[avishayil]

Hi @tomato42

1. it's not critical, it's medium severity, though we would need to calculate CVSS to be sure. That being said, I haven't seen any Bleichenbacher CVEs scored high, let alone critical
2. python-jose depends on python-rsa, but it will not use it if better libraries are available, you should use python-jose with pyca/cryptography, then python-rsa code will be unused and unexploitable
3. nobody is working on this; we've decided with Sybren to make it public specifically so that somebody else could start the work on this

Snyk apparently calculated the score here, see here: https://app.snyk.io/vuln/SNYK-PYTHON-RSA-1038401

[tomato42]

For one, as it's timing based, so it's harder to exploit than issues like https://nvd.nist.gov/vuln/detail/CVE-2017-13098 (https://snyk.io/vuln/SNYK-JAVA-ORGBOUNCYCASTLE-32031)
or any of the other issues listed on https://robotattack.org/ page. It also allows exactly the same kind of attack as ROBOT, so impact to confidentiality or integrity should be similar as those issues.

So I don't think that rating is consistent with other similar issues.

[sybrenstuvel]

Thanks for the report & the interest, people, it's much appreciated.

How about this approach, would that be a proper fix for this issue?

def decrypt(crypto: bytes, priv_key: key.PrivateKey) -> bytes:
    blocksize = common.byte_size(priv_key.n)
    encrypted = transform.bytes2int(crypto)
    decrypted = priv_key.blinded_decrypt(encrypted)
    cleartext = transform.int2bytes(decrypted, blocksize)

    # Detect leading zeroes in the crypto. These are not reflected in the
    # encrypted value (as leading zeroes do not influence the value of an
    # integer). This fixes CVE-2020-13757.
    crypto_len_bad = len(crypto) > blocksize

    # If we can't find the cleartext marker, decryption failed.
    cleartext_marker_bad = not compare_digest(cleartext[:2], b'\x00\x02')

    # Find the 00 separator between the padding and the message
    try:
        sep_idx = cleartext.index(b'\x00', 2)
    except ValueError:
        sep_idx = -1
    sep_idx_bad = sep_idx < 0

    anything_bad = crypto_len_bad | cleartext_marker_bad | sep_idx_bad
    if anything_bad:
        raise DecryptionError('Decryption failed')

    return cleartext[sep_idx + 1:]

The weakest spot here I think is the call to cleartext.index(b'\x00', 2). I'm open to any suggestions as to how to get rid of it and replace it with something constant-time.

[tomato42]

Thanks for the report & the interest, people, it's much appreciated.

How about this approach, would that be a proper fix for this issue?

def decrypt(crypto: bytes, priv_key: key.PrivateKey) -> bytes:
    blocksize = common.byte_size(priv_key.n)
    encrypted = transform.bytes2int(crypto)
    decrypted = priv_key.blinded_decrypt(encrypted)
    cleartext = transform.int2bytes(decrypted, blocksize)

    # Detect leading zeroes in the crypto. These are not reflected in the
    # encrypted value (as leading zeroes do not influence the value of an
    # integer). This fixes CVE-2020-13757.
    crypto_len_bad = len(crypto) > blocksize

    # If we can't find the cleartext marker, decryption failed.
    cleartext_marker_bad = not compare_digest(cleartext[:2], b'\x00\x02')

    # Find the 00 separator between the padding and the message
    try:
        sep_idx = cleartext.index(b'\x00', 2)
    except ValueError:
        sep_idx = -1
    sep_idx_bad = sep_idx < 0

    anything_bad = crypto_len_bad | cleartext_marker_bad | sep_idx_bad
    if anything_bad:
        # raise DecryptionError('Decryption failed')
        return cleartext[sep_idx + 1:]

    return cleartext[sep_idx + 1:]

The weakest spot here I think is the call to cleartext.index(b'\x00', 2). I'm open to any suggestions as to how to get rid of it and replace it with something constant-time.

the fact that cleartext.index() raises an exception will likely leak enough information to still mount an attack, using cleartext.find() would be better, but realistically, we need to traverse the whole cleartext reading each byte, as I'm quite sure cleartext.find() will exit the faster the earlier it finds the null byte

second, in case of failure we definitely can't return part of cleartext

[sybrenstuvel]

How about using before, separator, after = cleartext[:2].partition(b'\x00')? We can then inspect len(before) to test for correctness, and if correct, return after instead of cleartext[sep_idx+1:]. This should cause a copy of each byte, either into before or after, and the following correctness test is just a single integer comparison.

second, in case of failure we definitely can't return part of cleartext

Oh geesh, that shouldn't have been in here. The exception was just disabled to make it possible to do a timing test, and certainly won't be in the final code ;-)

[tomato42]

How about using before, separator, after = cleartext[:2].partition(b'\x00')? We can then inspect len(before) to test for correctness, and if correct, return after instead of cleartext[sep_idx+1:]. This should cause a copy of each byte, either into before or after, and the following correctness test is just a single integer comparison.

yes, that does make for nice and clean code, but again, I don't expect it to have any better timing characteristic than cleartext.find()

for example of code that attempts side-channel free behaviour see here: https://github.com/openssl/openssl/blob/d8701e25239dc3d0c9d871e53873f592420f71d0/crypto/rsa/rsa_pk1.c#L170-L278

[sybrenstuvel]

Yeah, I made something similar, but looping over each byte and doing some operations there is much slower than what we have now.

[tomato42]

from my previous work on this, I've noticed that subscripting strings and arrays is very expensive (like cleartext[i]), it's much faster to do for i, b in enumerate(cleartext); but yes, it won't be near as fast as native code