# Break RSA without padding using a rainbow table attack

We are using RSA without OAEP, with a relatively small input domain.

Lets assume we have John and Bob connected on a line, and we are eavesdropping them. Bob first sends John his public key (e,n), then John encrypts his message m and sends it on the line encrypted. When we eavesdrop the line we get his encrypted message, for example 3211 4431 9938 ... (I'm using a low modulo just for the example)

Me as the attacker can make a rainbow table of encryption of each number from 0 to n, and then decrypt John's message using the table I created.

1. Am I correct?
2. When we use any padding technique, we are preventing this attack (right?), by inserting random bits into the message, but how the decryptor (Bob) can 'remove' those random bits if he doesn't know them.
• If you can build a rainbow table for modulus of size 2048, you don't need to worry about OAEP at all. For short messages, yes there is a danger for the TextBook RSA. Padding is crucial to see probabilistic encrption. Oct 9, 2021 at 11:24
• Oct 9, 2021 at 12:49
• @kelalaka I don't see how textbook RSA would be problematic from building a rainbow table for a specific public key. It all depends on the input domain though, and if you only have one message it would take as long as brute forcing the message in the first place. Other ways of attacking textbook RSA can be found here Oct 9, 2021 at 18:52
• @MaartenBodewes for each public key and modulus, can you build a rainbow table for the message sizes upto 2048? For short messages, yes, possible. My point was, if you can reach for the modulus size of the table, you can break the modulus :) Oct 9, 2021 at 18:56
• Yes, you can disable this attack if you add enough random bits. You can use any kind of encoding for this, actually PKCS#1 has a pretty simple encoding: bytes valued 01..FF and 00 as ending byte value (with the strong disadvantage that it requires getting a range from a PRNG of course) but any other reversible encoding will do. After you are able to identify the random bits, you can simply ignore them and return the message. Of course, there are other attacks such as padding attacks possible on PKCS#1 and OAEP, I guess that requires additional study. Oct 9, 2021 at 20:06

Actual attacks can't work this way though. In RSA as practiced it's impossible to build a large-enough dictionary, as it would take too much time to build (proportional to the modulus $$n$$, which is typically at least 2048-bit nowadays). However, if Alice encrypted a message known to belong to a small set (such as the names on the class roll) directly with textbook RSA $$m\mapsto c:=m^e\bmod n$$, then it is possible to decrypt $$c$$ by encrypting each possible message and testing which matches $$c$$. A sequential search of the $$m$$ in the class roll will do: a dictionary of the corresponding $$c$$ is only useful if there are several messages (and RSA is not practically used by breaking messages into small chunks, as in the question).
2. Random encryption padding solves this problem, by reversibly turning a message $$m$$ into a sufficiently random-like message representative $$\widetilde m\in[0,n)$$. Then textbook RSA can be safely applied to $$\widetilde m$$, per the RSA assumption: for proper public key $$(n,e)$$ and random $$x\in[0,n)$$, it's hard to find $$x$$ from $$x^e\bmod n$$.
The big picture is there is a convention between Alice and Bob about which bits of $$\widetilde m$$ are padding (some of which random) added by Alice, that should be removed by Bob. That simplified description is quite close to the deprecated padding technique in RSAES-PKCS1-v1_5. The modern RSAES-OAEP has extra steps so all except (at most) 8 bits of $$\widetilde m$$ appear random even when $$m$$ is not (which is obtained by a reversible symmetric cryptographic transformation after applying random padding, which diffuse the randomness), but the idea remains.
• I think the padding must be on the MSB's so that when 3 is used as the public exponent the $\sqrt[3]{c}$ can't be found. Oct 10, 2021 at 7:37