# Does the exact distribution of padding bytes in PKCSv1.5 type 1 matter?

[Disclaimer: I am fully aware PKCSv1.5 is horrible and should die (though tell that to the TLS v1.2 specification). I am asking this question for my own edification.]

PKCSv1.5 encryption padding (as seen for instance in RFC 3447) formats the RSA message representative as

EM = 0x00 || 0x02 || PS || 0x00 || M

Where PS is at least 11 bytes taken from $[1...255]$ (i.e., no zero bytes are allowed). In most implementations I have seen, this is done by rejection sampling, i.e. the RNG is sampled repeatedly and bytes consisting of $\texttt{0x00}$ are skipped.

My question is the following: if PS is generated from a non-uniform distribution, are there any security issues that arise? As a concrete example, take PS to be the output of a CSPRNG but whenever the RNG outputs a $\texttt{0x00}$, instead of resampling the RNG just take $\texttt{0x01}$ as the output instead. So $\texttt{0x01}$ bytes will appear twice as often as normal. Yet this statistical abnormality in the padding does not seem to lead to any practical attack I am aware of.

References to any attacks in this line are welcome. For example if the padding bytes are derived using a LCRNG, does that cause any problem? (It certainly seems like a horrible idea, but again I'm not aware of any specific attack.)

## 1 Answer

In practice this should be okay. The reason the padding needs to be random is that if the padding can be guessed then the attacker can start encrypting candidate plaintexts (correctly formatted with the padding) under the public key and observe if the output matches the target ciphertext. Of course if the attacker finds a match then they have recovered the plaintext.

If the padding is 11 bytes of purely random padding that can take any value in $[1, 255]$ this means the attacker will have to do $255^{11} \approx 2^{88}$ encryptions for every candidate plaintext they want to check, which is clearly computationally intractable.

By sampling in the range $[0, 255]$ and replacing $\tt{0x00}$ with $\tt{0x01}$ you still have $255^{11}$ possible paddings but there are now some bytes that are more likely to occur than others (e.g. the first byte is more likely to be $\tt{0x01}$ than $\tt{0x02}$) so the attacker could optimize the order in which they check encryptions of padding / plaintext combinations.

If you are deriving padding bytes via a LCRNG this can lead to much worse results since there are ways to predict the output of a LCRNG. This in turn would reveal the padding to the attacker and instead of $255^{11}$ guesses per candidate plaintext they would only need $1$. In a sense when the padding is known the scheme degenerates to textbook RSA, and as such carries with it the same issues.