# 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).