RSA Security 5.2.2 manual Stream Ciphers, Timing Attacks and Blinding

Security Considerations

Stream Ciphers

A stream cipher (such as the RC4 cipher) will create a stream of pseudo-random bytes based on the secret key; this is known as the key stream. To encrypt, you XOR the plaintext with the key stream, byte by byte. The XOR operation has the property that the ciphertext XORed with the same key stream decrypts, restoring the plaintext. This also means that an XOR operation between the plaintext and the ciphertext will reproduce the key stream. Hence, knowing or guessing part of the plaintext allows an attacker to determine the corresponding part of the key stream. This still will not enable the attacker to deduce the entire key or any more of the key stream, but this does pose a threat if the same key is used in two different messages.

The same key always produces the same key stream. Therefore, if two messages use the same key, knowing part of the key stream in one message means knowing the same part of the key stream in the second message. An attacker can thus determine some of the plaintext in the second message. That is why you should never use the same stream cipher key twice.

Incidentally, this attack does not work on block ciphers. Knowledge of part of the plaintext does not automatically grant to the attacker knowledge of the key.

Another stream cipher attack involves a dictionary of key streams. Suppose you had kept the key size to 40 bits. An attacker could create a dictionary of the first eight bytes of the key stream from every possible 40-bit (5-byte) key. Then, the attacker “decrypts” the first eight bytes of an intercepted message with each possible key stream, until one produces a reasonable result. The key that generated the stream that worked is the right one.

To thwart this attack, you can implement salting. Design the application to use an 80- bit (10-byte) key, but send 40 bits in the clear. That 40 bits in the clear is known as a salt. For example, in an email application, encrypt the message using the RC4 cipher with a 10-byte key. Then encrypt the first five bytes of the key using the recipient’s RSA public key. Now the RSA digital envelope consists of the public-key-encrypted five secret bytes, five salt bytes sent in the clear and the RC4-encrypted message. In this way, the attacker’s dictionary is rendered useless. That dictionary is valid for 40- bit keys, but the message used an 80-bit key. Still, only 40 bits are kept secret. A dictionary of 80-bit key streams is not feasible — it would require 280 entries. That is about 1.2 · 1024, or 1.2 times one trillion times one trillion.

Timing Attacks and Blinding

If the time it takes to execute a cryptographic operation varies based on the input

C h a p t e r 3 C r y p t o g r a p h y 9 5