9
$\begingroup$

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.

$\endgroup$
15
$\begingroup$

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<N^{1/e}$, 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$.

$\endgroup$
10
$\begingroup$

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)$$

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – fgrieu Jan 24 at 11:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.