# How does PKCS 1.5 solve the insecureness of Textbook RSA?

As we know, Textbook RSA is not enough safe to use because of the following issues;

• Guessable plaintext problem

• Small $$e$$ issue

I want to know how PKCS 1.5 solved these problems.

PKCS#1 v1.5 describes a method (formally known as RSAES-PKCS1-v1_5) that turns textbook RSA into a (heuristically) secure encryption scheme for small messages (PKCS#1 v1.5 also describes a signature scheme, which the question and this answer do not consider).

For a $$k$$-byte ($$8k-7$$ to $$8k$$-bit) public modulus part of public key $$(N,e)$$, the message to be encrypted $$M$$ is a $$\mathrm{mLen}$$-byte bytestring with $$\mathrm{mLen}\le k-11$$. Message $$M$$ is turned into $$\mathrm{EM}=\mathtt{0x00}\mathbin\|\mathtt{0x02}\mathbin\|\mathrm{PS}\mathbin\|\mathtt{0x00}\mathbin\|M$$, where $$\mathrm{PS}$$ is drawn as a $$k-\mathrm{mLen}-3$$-byte bytestring consisting of fresh near-uniformly-random non-zero bytes. Then (with big-endian conversion between bytestring and integer left implicit) the ciphertext is $$C\gets\mathrm{EM}^e\bmod N$$. That's textbook RSA encryption of $$\mathrm{EM}$$.

While plaintext $$M$$ might still be easily guessable, verifying such guess becomes much harder. A brute-force method becomes: try all the possible $$\mathrm{PS}$$ and compute the corresponding $$C$$, until one matches. That strategy requires $$255^{k-\mathrm{mLen}-3}/2$$ try on average (for each possible $$M$$). That's next to $$2^{63}$$ at least, and growing by a factor of $$255$$ for each byte of message capacity that we remove. That's believed to solve the guessable plaintext problem; but we have no formal proof that it does.

Thanks to $$\mathtt{0x02}$$ at the second byte of $$\mathrm{EM}$$, it holds that $$\mathrm{EM}>2^{8k-15}$$. It follows that for $$e\ge3$$, $$\mathrm{EM}^e\gg N^2$$ for all practical $$k$$, and that's more than enough to solve a number of small $$e$$ issues :

• any known extension of the $$e^\text{th}$$ root attack (in this attack against textbook RSA, where $$C\gets M^e\bmod N$$, it is used that for $$M, we can compute back $$M$$ from $$C$$ as $$M\gets\sqrt[e]C$$ )
• Coppersmith's Short Pad Attack (which extends the Franklin-Reiter related messages attack to random padding).

RSAES-PKCS1-v1_5 also practically thwarts Hastad's broadcast attack. In this attack against textbook RSA, sending the same message to at least $$e$$ recipients allows decryption. The random $$\mathrm{PS}$$ makes $$\mathrm{EM}$$ for the same $$M$$ potentially different. Even for $$e=3$$, $$\mathrm{PS}$$ at the 8-byte minimum, and $$2^{36}$$ recipients of the same message $$M$$, probability that $$e$$ padded messages $$\mathrm{EM}$$ are identical is lower than one in a million, if I got the math right.

However, many RSAES-PKCS1-v1_5 implementations are vulnerable when used with small $$e$$, such as $$e=3$$. That's because implementations often check that the first two bytes of $$C^d\bmod N$$ are $$\mathtt{0x00}\mathbin\|\mathtt{0x02}$$, and/or parse what follows in order to find the first $$\mathtt{0x00}$$, indicating the start of $$M$$ and allowing recovery of $$\mathrm{mLen}$$. When the result of such check is made available in a way leaking where the failure occurred (by a detailed error code, or timing, or some other side channel) to adversaries able to submit cryptograms for decryption, then Bleichenbacher's padding oracle attack applies. It turns a moderate number of queries to a decrypting entity into an RSA private-key operation for arbitrary argument, allowing decryption of one message, or computing one signature if the same key is used for encryption and signature.

That's not a fatality, though: RSAES-PKCS1-v1_5 padding can be checked in constant time, with a single error code regardless of the particular failure. Another possible strategy is to not check the left 10 bytes; or when $$\mathrm{mLen}$$ is known in advance, make no padding check and simply extract $$M$$ as the rightmost $$\mathrm{mLen}$$ bytes of $$C^d\bmod N$$.

The Structure of PKCS#1 v1.5 as follows;

The message $$m$$ is padded to

x = 0x00 || 0x02 || r || 0x00 || m


and the ciphertext calculated as $$c=x^e\bmod N$$ not by $$m^e\bmod N$$, where $$r$$ is a random string.

• Cube root attack cannot be applied since the padding guarantees that messages are not short.

• The random $$r$$ make the encryption probabilistic so that guessing the message $$x$$ has a very small probability. Two encryptions of a message $$\operatorname{Enc}_{k_{pub}}(m_1) \neq \operatorname{Enc}_{k_{pub}}(m_1)$$ due to randomization.

• Also, the padding scheme prohibits the malleability property of RSA, that is

$$\operatorname{Enc}_{k_{pub}}(2) \cdot c = \operatorname{Enc}_{k_{pub}}(2) \cdot \operatorname{Enc}_{k_{pub}}(m) = \operatorname{Enc}_{k_{pub}}(2\cdot m)$$

• It is guessing the padded message x that has a small probability. Independently: there's more than a single small e issue, only one is covered by this answer.
– fgrieu
Jan 24, 2019 at 11:02