Public key cryptosystems like RSA are often taught by describing how they work at a high level. Even an algorithm textbook written by one of the inventors of RSA focuses more on exponentiation and how the decryption operation inverts ciphertext than on the underlying security details. However, all public key algorithms have various requirements that are not part of the basic primitive but are vital for security.
RSA requires the plaintext to be armored during encryption/signing and the result to be verified during decryption/verification. Unfortunately, this armoring is commonly called “padding”, which means some implementers think it functions like ordinary protocol padding. The interoperability principle (“be strict in what you send and lenient in what you accept”) is exactly opposite how public key crypto must be implemented. Padding cannot be ignored and if even one bit is out of place, the message is invalid. Failure to implement all the steps correctly could allow attackers to forge signatures, decrypt ciphertext, or even recover the private key.
I’ve written before about how failure to verify a signature result properly could result in forged signatures or recovery of the private key. This time, I’d like to explain an attack that shows why encryption armoring works differently than signature armoring.
Most RSA implementations use an optimization called the Chinese Remainder Theorem or CRT. With CRT, the implementation performs the exponentiation me mod n as two separate operations, me mod p and me mod q. The two parts are combined at the end. Since p and q are about half the size of n (which is p * q), this speeds up the exponentiation a lot because the multi-word numbers are smaller.
CRT can also be used to attack RSA. Consider an implementation that does not use any armoring. The encryption operation is simply the RSA primitive itself. A sender wants to send a message to three separate recipients. Thus, the sender calculates:
me mod A
me mod B
me mod C
The attacker can’t calculate the inverse of one of these encryptions directly because the eth root problem in each ring is difficult. However, because the message is the same for each recipient (but different ciphertexts), she can convert these operations into a group where the inverse operation is easy. To do this, she uses CRT to combine the three ciphertexts to get:
me mod A*B*C
Since m is smaller than each of A, B, and C, me is smaller than A*B*C if e=3. This means the attacker just has to calculate the cube root of the result, an operation that is easy in the monoid of integers modulo A*B*C. This is essentially an integer cube root, ordinary arithmetic. This shows why PKCS #1 armoring for encryption has always been randomized. It can be fatal to encrypt the same message multiple times, even to the same recipient. For signatures, it is more secure to randomize the padding as in RSASSA-PSS, but it is not yet fatal for legacy systems to continue to use PKCS #1 v1.5 signature padding, which is not randomized.
In public key crypto, padding is not an optional feature. It is a critical part of the cryptosystem security. The latest version of PKCS #1 (v2.1 as of this writing) should be used for both encryption/signing and decryption/verification. For new implementation, use the approaches that first appeared in v2.0 (RSAES-OAEP for encryption and RSASSA-PSS for signing). Failure to properly manage RSA armoring could allow attackers to forge signatures, decrypt ciphertext, or even recover your private key.
rdist 
Nate,
Great post, I’d never heard of this idea but I could see it coming up with sloppy implementations.
Two terminology issues though: the integers mod a composite N don’t form a field, they form a ring, since the elements which aren’t coprime to N will have no inverse. Since RSA only involves multiplication and not addition, though, the structure is a monoid. Also, RSA doesn’t rely on discrete logs being hard to compute but on eth roots being hard to compute. The difference is that in discrete-log systems like El Gamal we have X=a^b and know X and a, and want to find b. In RSA we have X=a^b and know X and b, and want to find a.
Joe, you are correct. I’ve edited the post for both your points. I couldn’t think of a good name for the “nth root problem”. I used your term “eth” since I didn’t want to confuse the RSA parameters n and e.
Also, I am using the term “field” a bit loosely in this post. Given that an attacker would have to be extremely unlucky to see a message not co-prime to the 6 non-trivial factors of A*B*C, they can treat it essentially as an integer root problem.
I would call that lucky.
A good followup to this would be a list of the functions from the common crypto libraries that do bare RSA encryption or signing operations without applying padding (ie those that expect the caller to pad). “If you’re calling one of these functions in your code, and you don’t know what RSA padding is, go get some expert help right now.”.
Unfortunately in some cases the libraries need to support raw RSA for broken standards that require it. From memory the German HBCI (Home Banking Computer Interface), among other weirdness, uses unpadded RSA for example, so any crypto library that doesn’t support this can’t be used to implement the HBCI spec (amusing, you have to carefully check for DES weak keys before you use your unpadded RSA encryption on them :-). Having said that, saying that no *sane* implementation should be doing this is certainly valid.
How can it be fatal to encrypt the same message (without padding) multiple times to the same recipient? Same message, same key, no padding == identical ciphertext, right?
Yes, you see the problem. This kind of mistake reveals information about the ciphertext because there is no randomized padding. This is somewhat like reusing an IV with CBC encryption — you can see patterns in the ciphertext just like ECB.
Also, see Coppersmith’s attack on low exponent RSA for how to recover plaintext when messages have differing padding that is predictable.