Distinguish between cipher-texts of text-book RSA and RSA/OAEP

Question

Is there is a possibility to identify from cipher-text that, this is been encrypted using a text-book RSA or RSA with OAEP padding. (By looking at the cipher-text only) ?

Answer 1

We can distinguish between ciphertext of textbook RSA and RSA/OAEP when textbook RSA is misused and insecure; or with knowledge of the private key.

With knowledge of the private key, we simply attempt RSA/OAEP decryption. If it succeeds, we bet for RSA/OAEP (and that will hold except for a vanishingly small proportion of possible plaintext); otherwise we know that's textbook RSA (with certainty, unless there's another option).

With knowledge of the private key, we can still succeed by exploiting weaknesses of textbook RSA; for example:

• If we can obtain ciphertexts for the same unknown plaintext enciphered twice, we can compare these ciphertexts. If they match, we bet for textbook RSA (and that will hold with overwhelming probability, unless the random number generator of RSA-OAEP is badly broken). If they differ, we know that's RSA/OAEP.
• With knowledge of the public key (assumed in this and the next two bullets), if we know / suppose that the plaintext is a name on the class roll, we try to encipher all names on the class roll (that requires the public key, but by assumption that's known to all), and compare each result to the actual ciphertext. If any match is found, we know with near certainty that's textbook RSA; otherwise, we bet for RSA/OAEP (with odds depending on how confident we are that the plaintext is a name on the class roll).
• As suggested in comment: if the ciphertext is an exact power of the public exponent $e$, we know for certain that's textbook RSA. Otherwise, we bet for RSA/OAEP (with odds depending on how likely it is that the plaintext $M$ is small enough that $M^e<N$).
• If we can obtain actual ciphertext for a single chosen plaintext, that allows a test.

Also, if we know or can find the size limit for the plaintext, that's also revealing: Textbook RSA usually can encipher messages up to $\lfloor\log_2(N)\rfloor$ bits or $\lfloor\log_2(N)/8\rfloor$ octets; while RSA-OEAP has a much lower limit, $\lceil\log_2(N)/8\rceil-2-2h$ octets, where $h$ is the hash size in octets ($h=32$ for SHA-256).

Answer 2

Not necessarily. Textbook RSA encryption can be seen as simply $m^e$ which is identified as RSAEP((n, e), m). Basically it consists of modular exponentiation of the message with the public exponent, in other words.

RSAEP, the RSA encryption primitive, is defined in PKCS#2.2 - the standard that defines RSAES-OAEP ("RSAES" is just RSA Encryption Scheme)

---

RSA-OAEP consists of RSAEP((n, e), EME-OAEP(n, M))) instead, where EME-OAEP(n, M) performs the padding. Here M is the input message as octet string and m is the padded message.

Now as m can be any value in textbook RSA, it follows that the result of m = RSAEP((n, e), M) is a strict subset of the input of textbook RSA. That means by definition that it is impossible to distinguish between textbook RSA and OAEP in all circumstances.

---

What you can do is to break textbook RSA using one of the many techniques listed here. If you manage to break it it cannot be RSA-OAEP, as that has been proven to be secure as long as the RSA promise holds. Note that there may be mistakes in the proof, but it general it should hold for the attack vectors against textbook RSA.

If you're unable to break the textbook RSA then you're basically out of luck.

---

I've left out numerous details for OAEP:

• I've left out the conversion from bytes to integer for the input value M (OS2IP);
• I've left out the Mask Generation Function and Hash configuration parameters;
• I've left out the possible label as input for OAEP padding (not used much);
• I've left out the encoding of the result of the modular exponentiation c to an octet string C using I2OSP.

If you're a purist you could say you can always distinguish between textbook RSA and OAEP as the first one operates on numbers and the other one operates on bytes / octet strings.

---

Next parts inspired by the answer of fgrieu

---

If you see multiple identical ciphertext then you are generally looking at textbook RSA. Textbook RSA is deterministic: it always returns the same ciphertext if you input the same message. The EME-OAEP padding is not-deterministc, it requires the random number generator and it's output should be indistinguishable from random - in the range [0, n) anyway. In general any IND_CPA secure cipher - including PKCS#1 v1.5 padding and RSA KEM - should be indeterministic.

Such calls to the random number generator could also be identified through timing attacks, which are a form of side channel attacks.

---

For the same reason it should not be possible to brute force OAEP, as an adversary doesn't know the random values, so he cannot compute the input to the modular exponentiation. For textbook RSA simple input messages could be brute forced by performing the modular exponentiation with the public key and comparing the result.

---

The two above methods do of course assume that OAEP uses a known-good random number generator.