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

Current PKCS#1 v1.5 decryption code:

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.

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

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

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

Thanks for the quick reply.

Hi @tomato42

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

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

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

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.

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.

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

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 ;-)

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

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

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

I'm quite sure that the code in dae8ce0 does not fix it.

Hi,
We have the same issue as highlighted by Snyk. What should be the right solution for it?

Hi,
We have the same issue as highlighted by Snyk. What should be the right solution for it?

audit your code for use of rsa decryption—if you don't use it you're not vulnerable; it's a false positive
propose fixes to this library to fix it—though that's unlikely to be successful in the end, as I wrote above
modify code you depend on so that it uses libraries that do provide side-channel free behaviour for RSA decryption

Thanks @tomato42

I checked our code, and we don't use the rsa library directly. But it is used indirectly from tls and jwt libraries. We use Django
I am not too experienced in python, to fix/monkey patch the library. But will give it a shot :)
I think this is what I can try and do.

How did you end up resolving this issue for you?

Thanks @tomato42

I checked our code, and we don't use the rsa library directly. But it is used indirectly from tls and jwt libraries. We use Django

tls? You mean this https://pypi.org/project/tls/#description ??

I don't see jwt using python-rsa, unless we're not talking about https://github.com/GehirnInc/python-jwt

I am not too experienced in python, to fix/monkey patch the library. But will give it a shot :)

I would advise against monkey-patching this code, writing side-channel secure cryptographic code is hard, you really should have any changes around it audited by a cryptographer

How did you end up resolving this issue for you?

I'm not using python-rsa, I just noticed that it's vulnerable and widely used

Thanks @tomato42

I checked our code, and we don't use the rsa library directly. But it is used indirectly from tls and jwt libraries. We use Django

tls? You mean this https://pypi.org/project/tls/#description ??

Yes, by https in Django for the servers

I don't see jwt using python-rsa, unless we're not talking about https://github.com/GehirnInc/python-jwt

Let me check once again.

I am not too experienced in python, to fix/monkey patch the library. But will give it a shot :)

I would advise against monkey-patching this code, writing side-channel secure cryptographic code is hard, you really should have any changes around it audited by a cryptographer

Okay. Will do that for sure.

How did you end up resolving this issue for you?

I'm not using python-rsa, I just noticed that it's vulnerable and widely used

Ah. I see.

@sybrenstuvel Thanks for the fix! Could you please release a new version?
For me it was also picked up by a vulnerability scan (Anchore). Many people would benefit/save time by not having to deal with this vulnerability (even to research what it is). So it would be quite appreciated, I think. :) Thanks in advance :)

@attila123 #165 (comment)

@tomato42 thanks. Then it is quite misleading to have this issue closed.

Hi,
Could someone please clarify then if this issue was addressed ? :)

Thanks in advance !

@NicoleG25 This is definitely not addressed. Why: the supposed fix dae8ce0 was committed on Nov 15, 2020, but the latest release of this library is 4.6 released at Jun 12, 2020 (see https://pypi.org/project/rsa/#history).

I am not a security expert, but as @tomato42 's #165 (comment) above: "I'm quite sure that the code in dae8ce0 does not fix it."

Good news is that at least google-auth does not use this problematic decrypt method (see above), so it can be considered false-positive in my use-case.

Version 4.7 has just been released to pypi.

Issue still being flagged in scanning for version 4.7

What does that mean @dalesit ?

I can’t say if @dalesit mean the same thing, but here’s what I’m getting from Gitlab Dependency Scanning (gemnasium-python)

Info about the fixed version was never added into the gemnasium vulnerability database https://gitlab.com/gitlab-org/security-products/gemnasium-db/-/blob/master/pypi/rsa/CVE-2020-25658.yml#L11

Morning, just to note that the potential vuln has raised it's head again, with rsa:4.9 being reported as being vulnerable

CVE-2020-25658 has been updated with: -

This vulnerability has been modified since it was last analyzed by the NVD. It is awaiting reanalysis which may result in further changes to the information provided.

Sonatype

Not sure if there's anything that can be done, apart from to be aware ?

@davidhay1969

There are two solutions:

Don't use RSA PKCS#1 v1.5 padding for encryption and decryption (though even if you do implement OAEP I'm afraid that python-rsa is likely vulnerable to Manger's attack just by virtue of using python's big integer arithmetic)
don't use python-rsa for RSA decryption (though note CVE-2020-25657 and CVE-2020-25659, and that proper fix for both of them needs openssl/openssl#13817, which at the moment is master only, targetting openssl-3.2.0; other libraries may have similar issues, I haven't looked at other python libraries)

Thanks @tomato42 appreciate the assist - I think python-rsa is being pulled in by the Kubernetes project, specifically their Python client, so I've raised CVE-2020-25658 and python-rsa #2053 there ....

Put it this way, it's the inclusion of kubernetes-client/python` from PyPi which is then throwing up the CVE, Sonatype scan etc.

Thanks again, my friend, you rule 🙇

There are two solutions:

This is correct! We have a couple of open PRs with PKCS#1 v2.0+ functionality, including OAEP, but they haven't seen much activity lately. If you're interested in bringing python-rsa up-to-date and increasing it's security, it would be great if you could take a look!

#207
#204
#126 For this one, note that I have my own local branch implementation of OAEP to be compatible with my PSS PR (above).

Pardon me if I am not understanding the status here, but is CVE-2020-25658 able to be remediated or not? I am trying to get my arms around all of the collateral and comments on this (not only github, but several other sites as well), but can't seem to get there. I have a NEW CVE alert that just today popped up out of the blue on a few of my AWS Linux2 servers. (CVE-2020-25658 that is). I have been trying to follow the threads on how to remediate, but can't gain any traction. Can someone shed some light please? Not sure what package or fix my be the correct one to mitigate this particular CVE. Thanks!

the solution to CVE-2020-25658 is not to use python-rsa pkcs1.decrypt()

WHAAAAAAAAAAAAAAAAAAAAAAT ?!!?!?!?!?!?

:-)

so. seriously. I shouldn't use it at all? How do I change that package on my production AWS EC2 linux boxes?

@jevbrowser, dae8ce0 attempts to mitigate Bleichenbacher-style timing attacks.

The README.md (6f59ff0) and mitigation-patch (dae8ce0) suggest that pure-Python cannot prevent such timing attacks. (the pkcs1 docs even say they are intrinsically vulnerable to timing attacks)

@sybrenstuvel, renaming this issue to mitigate Bleichenbacher-style timing attack or similar might be more clear.

Since your README states that timing attacks are a known issue to pure-Python projects, you may want to push back on the CVE assignment (by talking to your CNA--Red Hat). LXD's security policy is a good example for defining what qualifies as a security issue, if that's something you're interested in.

The addition of the statement that the code is intrinsically insecure against side channels was the result of the CVE, not predating it.

Also, you're linking pycryptodome docs, not python-rsa docs...

oh, sorry @tomato42 I misunderstood what you said about pkcs1 🙏

Having the statement in the README because of the report is great. Users need to be aware of the risk. There are a lot of downstream projects that should be wary (:fire::fox_face:). CVEs unfortunately have the double role of communication tool and credit of work. I'm really grateful that issues in python are pointed out so that we can improve.

I don't believe this CVE assignment makes sense today as a communication tool. The issue is not something that can be fixed with pure-Python and the risk is communicated near the top of the README.

Perhaps this is a broader vulnerability in Python?

I don't believe this CVE assignment makes sense today as a communication tool.

respectfully disagree, while seeing the CVE report may be a false positive (if your code doesn't use pkcs1.decrypt()), it's not something you'll know unless you go and check for that. I wish it would be possible to mark some APIs as inherently unsafe and have stuff like pylint flag any use of them, but we don't live in such a world...

Perhaps this is a broader vulnerability in Python?

Not really, Python provides generic numerical library, not a cryptographic numerical library. At no point did Python promise that int provides side-channel secure numerical operations.

It's an application bug, like if it was using == with bytes when comparing secret data, instead of hmac.compare_digest.

Now, would it be nice to be able to write side-channel secure code from python? sure, but that's a whole another problem (if you're interested in that, I suggest looking into exposing mpn_* interfaces in gmpy)

Thanks for clarifying.

This project is explicitly pure-Python, so I could see this issue as outside the projects security scope. On the other hand, it's helpful to tag downstreams that are affected by a CVE.

In either case, it should be clear that timing attacks are not prevented with dae8ce0 and a Fix is not expected.

As I've said above, the existing fix doesn't remove the side channel, see issue #230

	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:]

	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:]