Malleability of ECDSA (and DSA) signatures, JWTs, etc.

This blog posts explains that ECDSA and DSA signatures are malleable, that JWTs can be malleable as well and how this can be used to bypass some broken implementations of JWT deny lists (for revocation of JWTs or anti-replay protection).

Covered here:

• we will describe ECDSA (and DSA) signature malleability (without delving very deeply into the mathematical considerations);
• we will explain how this leads to malleability of ECDSA JWTs;
• we will see how the malleability of JWTs may have a security impact on some strategies for revocation (or replay protection) of JWTs;
• we will see other examples of JWT malleability (assuming that the JWT parser is lenient);
• we will see that many JWT parser are actually lenient;
• we will discuss shortly malleability of other types of tokens or cryptographic material.

Table of content

Malleability of ECDSA signatures

An ECDSA signature (or a DSA signature) is a pair of two integer numbers (r, s) modulo n (or, if you prefer in {0, 1, …, n-1}) where n is some constant. It turns out that if we are given a valid signature (r, s), we can derive a second signature (r, n - s) which is valid for the same message.

In other words, if an attacker has a valid signature, it can create a second valid signature for the same message^[1] without having access to the private key (malleability of ECDSA signatures).

This malleability is usually not a problem but this might become an issue, if your application makes some invalid assumptions about ECDSA signatures: if a raw signed message (or its hash) is used to identify a session/transaction, ECDSA malleability can be used to generate an alternative representation of the same session/transaction.

ECDSA and DSA signature are malleable. Schnorr signatures or EdDSA signatures are not impacted.

G = (0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296,
     0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5)

n = 0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551

Malleability of ECDSA JWTs

This can for example happen when using JWTs with ECDSA signatures (ES256, ES384, ES512).

For example, if we take an ECDSA JWT (newlines inserted for presentation purpose):

eyJ0eXAiOiJKV1QiLCJhbGciOiJFUzI1NiJ9
.
eyJuYW1lIjoiSm9obiJ9
.
cM-VjwN4FZvtPz2M9R1xX1lI9VgYi2v-5b3GKhH-m1k2V9Gyz3KJtTj5-1ycjAwJ-WKQpmGQYgVzvaXKxHX3Qw

the final segment (cM-VjwN4FZvtPz2M9R1xX1lI9VgYi2v-5b3GKhH-m1k2V9Gyz3KJtTj5-1ycjAwJ-WKQpmGQYgVzvaXKxHX3Qw) is an encoding the two integers (r, s). An attacker can easily compute the alternative signature (r, (- s) mod n):

import base64

def decode_b64u(value: str) -> bytes:
    missing_padding = len(value) % 4
    return base64.urlsafe_b64decode(value + missing_padding * "=")

def change_token_signature(token: str) -> str:
    """
    Compute the alternative ECDSA (ES256) JWT from an existing one
    using ECDSA malleability.
    """

    header, body, signature = token.split(".")

    raw_signature: bytes = decode_b64u(signature)

    assert len(raw_signature) == 64
    raw_r: bytes = raw_signature[0:32]
    raw_s: bytes = raw_signature[32:64]

    s: int = int.from_bytes(raw_s, byteorder="big")

    # For P-256 (ES256):
    n = 0xFFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551

    # This is the crux of the operation. Pretty simpvele, right?
    s2: int = n - s

    raw_s2: bytes = s2.to_bytes(length=32, byteorder="big")
    raw_signature2: bytes = raw_r + raw_s2
    signature2 = (
        base64.urlsafe_b64encode(raw_signature2).decode("ASCII").replace("=", "")
    )
    return header + "." + body + "." + signature2

import json
from joserfc import jwt, jwk
import jwt as pyjwt

def generate_jwt():
    key = jwk.JWKRegistry.generate_key("EC", "P-256")
    claims = {
        "name": "John~~~~~~~~~~~~"
    }
    token = jwt.encode({"alg": alg}, claims, key)
    public_key = jwk.JWKRegistry.import_key(key.as_dict(private=False))
    return (public_key, token)

public_key, token = generate_jwt(alg="ES256")

print("Public key JWK:")
print(json.dumps(public_key.as_dict(private=False)))
print("")

print("Public key PEM:")
print(public_key.as_pem().decode("UTF-8"))
print("")

print("Original JWT:")
print(token)
print("")

token2 = change_token_signature(token)
print("JWT modified with signature malleability:")
print(token2)
print("")

{
    "crv": "P-256",
    "x": "kbBetSJO3jD2bfCLEJcF71So7UQqzt_hXRlmD8qbxY4",
    "y": "8nrX0Q7k1MAV6n97vhFwJ9vRBM1uIHMA_oZfOb2piKI",
    "kty": "EC"
}

-----BEGIN PUBLIC KEY-----
MFkwEwYHKoZIzj0CAQYIKoZIzj0DAQcDQgAEkbBetSJO3jD2bfCLEJcF71So7UQq
zt/hXRlmD8qbxY7yetfRDuTUwBXqf3u+EXAn29EEzW4gcwD+hl85vamIog==
-----END PUBLIC KEY-----

eyJ0eXAiOiJKV1QiLCJhbGciOiJFUzI1NiJ9
.
eyJuYW1lIjoiSm9obiJ9
.
cM-VjwN4FZvtPz2M9R1xX1lI9VgYi2v-5b3GKhH-m1k2V9Gyz3KJtTj5-1ycjAwJ-WKQpmGQYgVzvaXKxHX3Qw

eyJ0eXAiOiJKV1QiLCJhbGciOiJFUzI1NiJ9
.
eyJuYW1lIjoiSm9obiJ9
.
cM-VjwN4FZvtPz2M9R1xX1lI9VgYi2v-5b3GKhH-m1nJqC5MMI12S8cGBKNjc_P1w4RqB0WHPH9__CT4N-0uDg

jwt.decode(token, public_key)
jwt.decode(token2, public_key)

Impact of JWT malleability

The malleability of JWTs might be an issue for example if the raw token value (or its hash) is used to build a deny list (revocation list, replay protection).

A typical (BROKEN!) implementation would work as follows:

• Token revocation: hash the token and store the hash^[2] in some database (with suitable expiration).
• Token revocation check: hash the token and check the hash is present in the database.

Such an implementation appears very reasonable and quite safe. What could possibly go wrong? It does not feel like we rolled our own crypto.

However, an attacker in possession of a revoked ECDSA JWT can derive a new valid (not revoked) JWT (for the same claims) and bypass the deny list.

This does not invalidate any security guarantees of JWTs. Because the signature segment of the JWT is not protected (🐔🥚), it is not especially surprising that it may be malleable. Such an application of JWTs makes false assumptions about JWTs.

This mistake is very easy to make however (and I actually made the this mistake myself 🤦).

We will illustrate that such an implementation might be found in the wild with two examples.

OWASP Cheat Sheet

The OWASP JWT Cheat Sheet used to recommend a revocation list based on hashed JWTs:

/**
* Handle the revocation of the token (logout).
* Use a DB in order to allow multiple instances to check for revoked token
* and allow cleanup at centralized DB level.
*/
public class TokenRevoker {

    /** DB Connection */
    @Resource("jdbc/storeDS")
    private DataSource storeDS;

    /**
    * Verify if a digest encoded in HEX of the ciphered token is present
    * in the revocation table
    *
    * @param jwtInHex Token encoded in HEX
    * @return Presence flag
    * @throws Exception If any issue occur during communication with DB
    */
    public boolean isTokenRevoked(String jwtInHex) throws Exception {
        boolean tokenIsPresent = false;
        if (jwtInHex != null && !jwtInHex.trim().isEmpty()) {
            //Decode the ciphered token
            byte[] cipheredToken = DatatypeConverter.parseHexBinary(jwtInHex);

            //Compute a SHA256 of the ciphered token
            MessageDigest digest = MessageDigest.getInstance("SHA-256");
            byte[] cipheredTokenDigest = digest.digest(cipheredToken);
            String jwtTokenDigestInHex = DatatypeConverter.printHexBinary(cipheredTokenDigest);

            //Search token digest in HEX in DB
            try (Connection con = this.storeDS.getConnection()) {
                String query = "select jwt_token_digest from revoked_token where jwt_token_digest = ?";
                try (PreparedStatement pStatement = con.prepareStatement(query)) {
                    pStatement.setString(1, jwtTokenDigestInHex);
                    try (ResultSet rSet = pStatement.executeQuery()) {
                        tokenIsPresent = rSet.next();
                    }
                }
            }
        }

        return tokenIsPresent;
    }


    /**
     * Add a digest encoded in HEX of the ciphered token to the revocation token table
     *
     * @param jwtInHex Token encoded in HEX
     * @throws Exception If any issue occur during communication with DB
     */
    public void revokeToken(String jwtInHex) throws Exception {
        if (jwtInHex != null && !jwtInHex.trim().isEmpty()) {
            //Decode the ciphered token
            byte[] cipheredToken = DatatypeConverter.parseHexBinary(jwtInHex);

            //Compute a SHA256 of the ciphered token
            MessageDigest digest = MessageDigest.getInstance("SHA-256");
            byte[] cipheredTokenDigest = digest.digest(cipheredToken);
            String jwtTokenDigestInHex = DatatypeConverter.printHexBinary(cipheredTokenDigest);

            //Check if the token digest in HEX is already in the DB and add it if it is absent
            if (!this.isTokenRevoked(jwtInHex)) {
                try (Connection con = this.storeDS.getConnection()) {
                    String query = "insert into revoked_token(jwt_token_digest) values(?)";
                    int insertedRecordCount;
                    try (PreparedStatement pStatement = con.prepareStatement(query)) {
                        pStatement.setString(1, jwtTokenDigestInHex);
                        insertedRecordCount = pStatement.executeUpdate();
                    }
                    if (insertedRecordCount != 1) {
                        throw new IllegalStateException("Number of inserted record is invalid," +
                        " 1 expected but is " + insertedRecordCount);
                    }
                }
            }

        }
    }
}

SuperTokens

The following snippet was recommended by SuperTokens blog post "Revoking Access with a JWT Blacklist/Deny List", also available on a GitHub repository builds a token revocation list based on the raw token value:

// JWT middleware
const authenticateToken = async (request, response, next) => {
    const authHeader = request.headers["authorization"];
    const token = authHeader && authHeader.split(" ")[1];

    // token provided?
    if (token == null) {
        return response.status(401).send({
            message: "No token provided",
        });
    }

    // token in deny list?
    const inDenyList = await redisClient.get(`bl_${token}`);
    if (inDenyList) {
        return response.status(401).send({
            message: "JWT Rejected",
        });
    }

    // token valid?
    jwt.verify(token, JWT_SECRET, (error, user) => {
        if (error) {
            return response.status(401).send({
            status: "error",
            message: error.message,
            });
        }

        request.userId = user.username;
        request.tokenExp = user.exp;
        request.token = token;

        next();
    });
};

app.post("/logout", authenticateToken, async (request, response) => {
    const { userId, token, tokenExp } = request;

    const token_key = `bl_${token}`;
    await redisClient.set(token_key, token);
    redisClient.expireAt(token_key, tokenExp);

    return response.status(200).send("Token invalidated");
});

Malleability through lenient JWT parsing

Even if you do not use ECDSA, your JWT might end up being malleable if the JWT parser is lenient in its processing of the tokens. Depending on the JWT parser implementation, the following mechanisms might be used to introduce malleability:

• implementation accepts plain base64 characters;
• implementation accepts padding characters;
• implementation accepts invalid trailing bits.

In all cases, the impact of a lenient JWT parser implementation are the same as for ECDSA signature malleability: an attacker can derive malformed-but-accepted JWTs from an existing (revoked) JWT and bypass the deny list.

Additional sources of malleability

Plain base64 characters

Base64 exist in two variants:

• plain base64;
• urlsafe base64.

They differ only in the two final characters if their alphabets:

BASE64_DIGITS = string.ascii_uppercase + string.ascii_lowercase + string.digits + "+/"
BASE64_URL_DIGITS = string.ascii_uppercase + string.ascii_lowercase + string.digits + "-_"

JWT/JOSE uses the second variant. However some implementation accept sets of digits. This could be used by an attacker to generate an alternative representation of a JWT:

def change_token_b64(token: str) -> Optional[str]:
    header, body, signature = token.split(".")
    signature2 = signature.replace("-", "+").replace("_", "/")
    if signature == signature2:
        return None
    return ".".join([header, body, signature2])

Base64 padding

Base 64 encoding normally included zero, one or two padding characters (=). The JOSE ecosystem uses base64 url encoding without those padding characters:

Base64url Encoding Base64 encoding using the URL- and filename-safe character set defined in Section 5 of RFC 4648 [RFC4648], with all trailing '=' characters omitted (as permitted by Section 3.2) and without the inclusion of any line breaks, whitespace, or other additional characters. Note that the base64url encoding of the empty octet sequence is the empty string. (See Appendix C for notes on implementing base64url encoding without padding.)

Some implementation accept padding characters. This could be used by an attacker to generate an alternative representation of a JWT:

token3 = token + "=="

Trailing bits

Base64 encoding represent 6 bits per digit. This means that the final bits of the base64 string may not represent an actual bit of data. These bits are supposed to be set to 0. However, an attacker could replace some of these bits with ones leading to a different base64 string. If the decoder does not verify that the trailing bits are set to 0, this second base64 representation might be accepted as valid.

According to RFC 4648:

When fewer than 24 input bits are available in an input group, bits with value zero are added (on the right) to form an integral number of 6-bit groups.

This could be used by an attacker to generate an alternative representation of a JWT:

def change_token_tweak_digit(token: str) -> str:
    last_digit = token[-1]
    signature = token.split(".")[2]
    for alt_last_digit in BASE64_URL_DIGITS:
        if last_digit != alt_last_digit:
            res = token[:-1] + alt_last_digit
            alt_signature = res.split(".")[2]
            if decode_b64u(alt_signature) == decode_b64u(signature):
                return res

    return None

Input              |      X      |
Input byres (dec)  |     88      |
Bits:              | 010110   00 |
Groups (bin)       | 010110 | 00   ????
Groups (filled)    | 010110 | 00   0000
Groups (dec)       |     22 |         0
Groups (digit)     |      W |         A

Input              |      X      |
Input byres (dec)  |     88      |
Bits               | 010110   00 |
Groups (bin)       | 010110 | 00   ????
Groups (filled)    | 010110 | 00   1010
Groups (dec)       |     22 |        10
Groups (digit)     |      W |         K

A lenient JWT parser will decode both these encodings
to the same string "X":

~~~python
import base64
assert base64.urlsafe_b64decode("WA==") == b"X"
assert base64.urlsafe_b64decode("WK==") == b"X"
~~~

Malleability in different JWT implementations

I tested different JWT implementations and all of them were found to be lenient in their parsing of JWTs.

"R" means that the malformed token is rejected (strict parsing) and "A" means that it is accepted (lenient parsing).

While lenient JWT parsing is arguably not a vulnerability, I would suggest implementing strict parsing anyway:

• it might prevent JWT malleability in practice (when ECDSA it not used) which might limit the impact of an erroneous deny list implementation;
• there is no compelling argument for lenient parsing.

Resolutions for ECDSA and JWT malleability

ECDSA itself can be resolved by enforcing that on of the two possible values for s is used (eg. low-S normalization). This method was used for Bitcoin transactions (BIP 146: Dealing with signature encoding malleability).

However, JWTs may be malleable through other (implementation-dependent) mechanisms. In general, the application should avoid using a token raw value (or its hash) for denying access: an attacker can use malleability to bypass the restriction. Using the token raw value for positive access allow-list should be safe.

For JWTs, the recommended approach for a revocation list is to use the combination of the jti claim (token ID) and iss claim (issuer). Depending on the application, other claims might be more suitable.

For issuer-maintained JWT/JOSE (or CWT/COSE) revocation lists, Token Status List (TSL) should be used.

Other types of tokens and cryptographic identities should usually be assumed to be malleable as well and should therefore not be used directly for deny lists:

• X.509 certificates;
• ASN.1 public keys (?);
• CWT (COSE);
• etc.

Some exceptions:

• JWK thumbprints.

Conclusion

• ECDSA signatures and DSA signatures are malleable.
• ECDSA JWT tokens are malleable because of that.
• Many JWT parsers are lenient, which introduces additional vector of malleability.
• But it should be expected that the signature segment of JWTs is malleable. That is not really surprising.
• Beware of token (JWT or other) malleability when building deny lists, the deny list should use only parts of the message which are covered by the MAC or signature.
• In particular, the MAC/signature field of a token is not protected (🐔🥚).
• For deny lists of JWTs (or CWTs), use typically want to use the jti and iss claims.
• For issuer-maintained revocation lists of JWTs (or CWTs), use Token Status List (TSL).

Appendix, base64 parsing

Base64 in Python

In Python, the base64 parsing implemented in the base64 module is lenient by default. The base64.b64decode function can be support strict parsing since Python 3.15 with:

b64decode(data, altchars=b'-_', padded=False, validate=True, canonical=True)

Explanations:

• altchars=b'-_' required for urlsafe base64
• padded=False (available since Python 3.15), required if padding characters (=) are not used;
• validate=True (available since Python 3.15), for rejecting unexpected characters;
• canonical=True (available since Python 3.15), for rejecting non-zero trailing bits.

Base64 in Golang

Base 64 in encoding/base64 accepts invalid trailing bits by default.. The .Strict() call enabled validation of the trailing bits.

output, err := base64.RawURLEncoding.WithPadding(base64.NoPadding).Strict().DecodeString(input)

References

Malleability in Bitcoin transactions:

• ECDSA malleability in bitcoin
• BIP 62: Dealing with malleability
• BIP 66: Strict DER signatures
• BIP 146: Dealing with signature encoding malleability

Base64 malleability:

• Base64 Malleability in Practice
• Base64 is Malleable!
• TIL that Base64 is malleable

Bug reports:

• JSON_Web_Token_for_Java_Cheat_Sheet revocation method is vulnerable to JWT malleability
• lenient JWT parsing (leading to JWT malleability, in cpp-jwt
• Security: strict base64url decoding (reject non-base64url alphabet, embedded '=', non-canonical trailing bits), in libjwt