Using RSA Securely in 2022

If you can somehow avoid using RSA (i.e. using Elliptic Curve Cryptography instead), then don’t use RSA at all. Then you can skip this blog post entirely and all is right in the world.

If you can’t avoid RSA, and you’re encrypting messages, at least make sure you’re not encrypting messages with RSA directly. (RSA signatures are significantly less scary than RSA encryption.) Also, don’t use the same RSA keypair for both operations.

If you’re still reading, then I assume one of two things is true:

1. You’re implementing RSA encryption and/or signatures, because you can’t avoid this algorithm in your system requirements.
2. You’re just curious about what I’m going to recommend.

For people in camp 1, I’m also going to assume you have a straightforward use-case for RSA cryptography. Blind signatures, etc. are out of scope for this blog post.

Minimize Protocol Variance

Every RSA keypair consists of a single secret key and a single public key.

Many cryptography libraries represent the public key as the public exponent and modulus (, ), and the secret key as… well, it’s complicated.

All other configuration (hash function, padding mode, etc.) are left up to the poor protocol designer to figure out. This isn’t ever specified at a low level, and most high-level cryptography APIs end up being leaky abstractions of the low-level RSA implementation.

Stop making this mistake.

Soatok’s Recommendation

Every RSA keypair must be represented as all of the following:

Any time you change any of these configuration parameters, it MUST be used with a new asymmetric key-pair. The new key MUST NOT be used with the same raw key bytes as any previous key.

If the API you’re designing doesn’t support this strictness, you’ll inevitably fall into the trap of in-band negotiation.

JSON Web Signatures (JWS) almost got this right with distinguishing between RS256 and PS256 (both are RSA, but with different paddings), but unfortunately it was built atop the JWT standards which maximizes in-band negotiation.

In short, you should end up with an intermediary API that looks like this.

type RSAKeyPair = {
    sk: RSASecretKey;
    pk: RSAPublicKey;
}

interface RSASecretKey {
    // Don't need modulus size; it's inferred from p, q
    constructor(
        d: Buffer, // private exponent
        n: Buffer, // public modulus
        op: SecretKeyOps,
        e: number, // public exponent
        padding: RSAPadding,
        hashAlgo: string,
        engine?: CryptoBackend = null
    );

    static generate(
        engine?: CryptoBackend = null
    ): RSASecretKey;

    decrypt(ciphertext: Buffer): CryptoKey;

    sign(msg: Buffer): Buffer;

    derivePublicKey(): RSAPublicKey;
}

interface RSAPublicKey {
    constructor(
        n: Buffer,
        e: number,
        op: PublicKeyOps,
        padding: RSAPadding,
        hashAlgo: string,
        engine?: CryptoBackend = null
    );
    
    encrypt(symKey: CryptoKey): Buffer;
    
    verify(msg: Buffer, sig: Buffer): boolean;
}

enum SecretKeyOps {
    DECRYPT,
    SIGN
}

enum PublicKeyOps {
    ENCRYPT,
    VERIFY
}

enum RSAPadding {
    PKCS1_V15,
    OAEP,      // only with encrypt/decrypt
    PSS,       // only with sign/verify
    NONE       // only for KEM-DEM encryption
}

None of the cryptographic parameters are optional or have default values. Callers MUST be explicit.

The actual implementation of this API will need to perform runtime checks (e.g. you’re not trying to encrypt with PSS padding) beyond what’s sketched out here.

Usability is Essential

Security at the expense of usability comes at the expense of security.

Avi Douglen

Any cryptography feature that another human might one day use should be easy to use, hard to misuse, and secure by default. Any departure from these tenets in the design or specification phase will result in a security vulnerability.

The API that I sketched out above might seem unwieldy, but you’re never going to expose this mid-level API to your users. Instead, you will abstract this complexity away in a strictly-versioned protocol, like so:

interface UsableRSA {
    constructor(version: RSAProtocol)

    encrypt(message: Buffer, pk: RSAPublicKey): Buffer
    decrypt(ciphertext: Buffer, sk: RSASecretKey): Buffer

    sign(msg: Buffer, sk: RSASecretKey): Buffer
    verify(msg: Buffer, pk: RSAPublicKey, sig: Buffer): Buffer

    async generate_keypair(): Promise<RSAKeyPair>

    async load_secret_key(path: string|FilesystemPath): Promise<RSASecretKey>
    async load_public_key(path: string|FilesystemPath): Promise<RSAPublicKey>

    async save_public_key(
       pk: RSAPublicKey
       path: string|FilesystemPath
    ): Promise<boolean>

    async save_secret_key(
       sk: RSASecretKey
       path: string|FilesystemPath
    ): Promise<boolean>
}

enum RSAProtocol {
    VERSION_1 = "v1", // Legacy
    VERSION_2 = "v2", // Intermediate
    VERSION_3 = "v3", // Modern
}

const RSAProtocolMap = {
    /* Legacy compatibility: */
    RSAProtocol.VERSION_1: {
        encryptPad: RSAPadding.PKCS1_V15,
        signPad: RSAPadding.PKCS1_V15,
        hashAlg: 'sha1',
        encryptModulusSize: 2048,
        signModulusSize: 2048,
        e: 3
    },

    /* Acceptable: */
    RSAProtocol.VERSION_2: {
        encryptPad: RSAPadding.OAEP,
        signPad: RSAPadding.PSS,
        hashAlg: 'sha256',
        encryptModulusSize: 2048,
        signModulusSize: 2048,
        e: 65537
    },

    /* The new hotness: */
    RSAProtocol.VERSION_3: {
        encryptPad: RSAPadding.NONE, // KEM-DEM
        signPad: RSAPadding.PSS,
        hashAlg: 'sha384',
        /* These two are different just to allow strict checks on the public
           key modulus size to mechanize misuse resistance.
           Which is larger is an arbitrary decision I made: */
        encryptModulusSize: 4096,
        signModulusSize: 3072,
        e: 65537
    },
}

Now all user needs to decide is whether or not they’re doing v1, v2, or v3, and then manage their keypairs (which SHOULD be serialized with the version and operation they were intended for), and then use the respective keypair objects to perform the operation they need.

In the “new hotness” version, the intention of different key sizes is to allow you to mechanize the enforcement of never reusing an encryption key for signing, or vice versa.

encryptV3(msg: Buffer, pk: RSAPublicKey): Buffer {
    if (pk.getModulusSize() !== 4096) {
        throw new Error("Invalid key size for encrypt")
    }
    if (pk.getPublicExponent() !== 65537) {
        throw new Error("Invalid public exponent")
    }
    
    // Do RSA-KEM here
    // Do AES-GCM here
}

signV3(msg: Buffer, sk: RSASecretKey): Buffer {
    if (sk.getModulusSize() !== 3072) {
        throw new Error("Invalid key size for sign")
    }
    if (sk.getPublicExponent() !== 65537) {
        throw new Error("Invalid public exponent")
    }
    // Sign message
}

This separation of high-level and low-level concerns will prevent a user from accidentally encrypting with a secret key, or using a weird padding mode, or setting their public exponent to 1.

Don’t YOLO Your Key Parameters

It’s common for me to spot, in the wild, some system that deals with RSA keys (e.g. SSH public keys) and asserts that the modulus () is at least a 2048 bit number.

However, nothing prevents me from passing an RSA keypair to these systems, because almost nobody thinks to validate the public exponent too.

This isn’t a problem exclusive to RSA. Many ECC designs expect uncompressed public keys and utterly fail to ensure the coordinates provided are actually a solution for the curve equation. (Seriously, just use compressed points. The patent expired in 2018.)

Which Public Exponents Should We Permit?

Strictly speaking, any odd number coprime to is a valid choice for , but you might want to limit your choices.

In textbook RSA (read: unpadded), if your plaintext message raised to the power of didn’t wrap the modulus, you could just take the nth root of an RSA ciphertext to decrypt it.

If you’re worried about this risk for encryption (e.g. because you’re using unpadded RSA for a KEM-DEM design), set to be sufficiently large to guarantee the modulus is wrapped (i.e. no matter what is).

Note:

If you’re doing RSA signatures, and you’re worried about a low public exponent because of Bleichenbacher’s 2006 attack, you’re focusing on the wrong problem. The real issue is parsing the RSA signature message at all.

Instead, generate what you expect the signature to look like, then compare it with the provided signature. In constant time. See also: Imperial Violet, Thomas Ptacek.

However, you don’t want your public exponent to be too large, or else you’ll create a performance bottleneck (which is certainly a Denial of Service attack vector).

Many RSA implementations use a Double and Add algorithm for modular exponentiation under the hood, for performance reasons. (However, especially for signing, it’s recommended to use a Montgomery Ladder for constant-time exponentiation modulo N instead of a naive Double and Add modulo N algorithm.)

Therefore, the most efficient choices to use for public exponent are the usually ones with the minimum number of additions. Fermat numbers are an attractive choice here.

const E_ALLOWLIST = [3, 5, 17, 257, 65537];

The public exponent should be asserted at runtime whenever a public key is loaded into memory, but never configurable by the end user or from the network. Fail closed.

Update: Hanno Böck suggests enforcing e = 65537 instead of leaving it loose. If you don’t have some reason to not do this (e.g. hardware keys that use a different public exponent), be as strict as possible. He also suggests requiring the public modulus to be 2048, 3072, or 4096 bits.

Avoiding Side-Channels

If you ever have to ask yourself if the library you’re depending on to provide the RSA primitives uses constant-time big integer arithmetic, the answer is probably, “No.” (Notable exception: BearSSL.)

Instead, most cryptography libraries implement masking (often also called “blinding“), which isn’t a proven mechanism for preventing side-channel leakage, and requires a reliable source of randomness at runtime. (This latter requirement isn’t a big deal for high-level applications, but might be thorny for embedded systems development.)

At this point, you have to choose your own adventure.

Implementing optimized, constant-time big integer arithmetic in low-level cryptography libraries isn’t an exercise for the faint of heart. Blinding/masking is easier to pull off, but is insufficient for Power Analysis attacks. (You need a Montgomery Ladder to mitigate those.)

Tests Rule Everything Around Me

Your testing framework (e.g. unit tests) should cover the behavior for accidental misuse.

Every test-driven development (TDD) evangelist on the Internet probably just screamed, “Well DUH!” at their screen, but this is a nugget of wisdom that’s lost on the authors of cryptography standards.

Whenever someone designs a new cryptographic primitive, they’re expected to publish some test vectors / known answer tests (KATs). This is usually a set of public inputs and outputs for a given primitive, in order to aid implementors in knowing that their implementation is correct.

There are two problems with most KATs, however:

1. They almost never include KATs that should result in a failure.
2. They often use the same patterns (010203...) and starting positions for multiple test inputs (key, nonce, plaintext, aad), which means the KATs won’t catch someone screwing up their parameter orders.

If you’re designing a cryptography protocol in 2022, regardless of whether it uses RSA, you should avoid both pitfalls.

Include negative tests that are expected to fail. Use distinct inputs for at least some of your test cases.

If the KATs all pass, and the developer’s implementation fails an audit that they could have caught, your KATs need to be improved.

Further Considerations

Above, I’ve outlined some of the considerations you need to keep in mind when working with RSA, but it’s possible I’ve overlooked a few that might be relevant to your application.

Elliptic Curve Cryptography, despite having more complicated math, is comparatively simpler to work with (especially if you use Curve25519).

Finally, both RSA and ECC will be susceptible to quantum computers one day. The intermediary step to a world of post-quantum cryptography may require a hybrid solution, but that debate hasn’t been settled.

Header art: @JohisArt, @loviesophiee