Known Flaws in RSA, and How to Fix Them

CS 463 Lecture, Dr. Lawlor

Flaw: Prime Generation

The prime numbers p and q need to be truly unpredictable, not just random looking. This means calling a deterministic random number generator like "rand" is completely insufficient--consider there are only 4 billion possible values that can be passed to srand().

Back in 1996, this was a known flaw in the then wildly popular web browser Netscape.

The fix: make sure your implementation is using a good random number source like /dev/random or CryptGenRandom (but don't use Dual_EC_DRBG).

Flaw: Side Channel (Timing, Heat, etc) Attacks

Each operation used in RSA encryption is a slow multi-precision operation, so it's easier to measure the time taken to do each sub-multiplication in an exponentiation (compared to, for example, the sub-clockcycle time to do the carry bits in a normal addition). This is bad, because tons of operations have data-dependent timing--for example, decrypting data (m=c^d mod n) means looking at each bit of your private key, and choosing to include a multiple of c. This sort of attack can be extremely high precision when coming from a different VM on the same cloud server.

Possible fixes:

Use a fixed amount of time and energy: start a timer, do the encryption, then do similar but useless work until the timer expires. *Then* send the result on.
Use an algorithm that does the same amount of work for any input, such as Montgomery multiplication.

Flaw: Message Enumeration

Recall that:
To encrypt a message m into ciphertext c, use the public key e: c = m^e mod n
To decrypt ciphertext c back into the message m, use your private key d: m=c^d mod n

Theoretically, you need the private key to decrypt the message. However, anybody can check if a possible message m encrypts to the intercepted ciphertext c, because anybody can encrypt a message for you. In other words, public key "encryption" works more like a hash function, where anybody can check if the hashes match.

Secret key ciphers don't have this flaw, because you need the key to encrypt.

The fix is to pad each message with random data--the exact analog of using a salted hash for passwords. 256 bits is enough to make an attacker's search space entirely infeasible. Some follow this with a weak encryption scheme, like the hash-based one round Feistel used in OAEP, to ensure that a partial break won't reveal anything valuable (it also messes up multiplicative structure, below).

Flaw: Multiplicative Structure

Since RSA is based on simple exponentiation, encrypting (or decrypting) the product of two messages gives the product of the two ciphertexts:
c = m^e mod n
c' = m'^e mod n
c * c' = m^e * m'^e= (m * m')^e mod n

There are enough ways to exploit this that you should never encrypt or sign a raw message, only a carefully packaged message.

For encryption, see the previous fix OAEP.

For signing, several options exist, but the most popular signing scheme is the hash based RSASSA-PKCS1-v1.5. This boils down to signing a binary value consisting of:

The constant 16 bits 0x0001
Padding bytes of value 0xff (to get up to size n)
Spacer byte of value 0x00
A binary hash algorithm identifier (DER)
And then the binary hash (of your choice).