Does RSA padding have to be unpredictable if the payload is?

Question

I'm trying to understand the precise requirements on padding when using RSA for encryption.

Suppose Alice uses RSA to encrypt a payload $M$ that cannot be guessed (say, a random nonce): Alice send $\mathrm{RSA}_{B_{pub}}(\mathrm{pad}(\mathtt{?}) || M)$ to Bob, with a padding procedure to be determined. Assume reasonable sizes, say a 1024-bit RSA key and a 256-bit payload. Alice may send the same payload $M$ to multiple recipients, encrypted with each recipient's private key. Only a recipient must be able to recover $M$. But it's ok if an external observer can tell that Alice sent the same $M$ to Bob and Charlie (sent as $\mathrm{RSA}_{B_{pub}}(\mathrm{pad}(\mathtt{?}) || M)$ and $\mathrm{RSA}_{C_{pub}}(\mathrm{pad}(\mathtt{?}) || M)$ respectively)¹.

With no padding, this is broken: the plaintext can be reconstructed from $e$ ciphertexts. In general, RSA padding must be random and not recoverable without knowing the private key, if only because otherwise the attacker could verify a guess of the payload; but here I assume the payload is unguessable. So what are the requirements on padding in this scenario?

• Is it ok to use a deterministic padding function that depends only the recipient, say $\mathrm{pad}(B) = \mathrm{SHA256}(B_{pub})$?
• Is it ok to use a predictable padding function, say by incrementing global counter for each recipient (assume Alice does have a reliable monotonic counter)?
• Is it ok to use random padding that is leaked? In other words, in this scenario, is the mere fact that the attacker knows the padding a problem?

¹ _{What prompted this line of thought was a message $M$ that was a single-use symmetric encryption key; the long message encrypted with that symmetric key would be identical for all recipients anyway.}

Answer 1

From what I understand, you consider a scenario in which a fixed, random-looking message $M$ is sent to multiple recipients, encrypted using RSA with some padding (this is called the "broadcast RSA" setting).

Moreover, you consider affine paddings, in the sense that you apply the RSA function to an element of $\mathbb{Z}_N$ of the form $a_i M + b_i$ for some values $a_i, b_i$ depending on the recipient which may be known in part or in full by the adversary (in fact, we even have $a_i = 1$ in the cases you consider, but that doesn't really matter).

In that case, expanding a bit on fgrieu's answer:

• No, it is not OK to use a public deterministic padding that depends on the recipient, even if the padded message is as long as the modulus. This type of padding is broken in the broadcast setting by a generalization due to Håstad of the simple CRT attack alluded to by fgrieu.

• For the same reason, a predictable padding function will not do, nor indeed any affine padding where the values $a_i, b_i$ are known by the adversary.

• Even using such a padding where the $b_i$'s are randomized can be dangerous. For example, a padding of the form $R_i \| M$ (with $R_i$ chosen at random for each recipient and long enough so that the padded message is as long as the modulus) can be attacked in the broadcast setting if $M$ is relatively long: see this paper (the attack is admittedly rather theoretical, but still).

• This survey on RSA attacks by Boneh is over 10 years old already, but always good reading (you're especially interested in §4).

Generally speaking, I wouldn't recommend using an affine or polynomial padding function for any new application except for interoperability reasons; and I would especially advise against using a custom affine padding that "looks strong enough" (unless you want to make cryptanalysts happy by providing them with a fresh new target :-).

A better idea (which is essentially what Thomas Pornin suggested in the earlier discussion) is using RSA-KEM (RFC 5990): for each recipient, pick a random element $R_i$ in $\mathbb{Z}_N$, and send $C_i = R_i^e \mod N$ to the $i$-th recipient, together with the encryption of $M$ (with your favorite block cipher) under a key derived from $R_i$.

Other options include paddings like RSA-OAEP (part of PKCS#1 v2.1).

Answer 2

The simplest and strongest security proofs for RSA-based cryptosystems are when the padded message is random-like on $Z_n$. None of the proposed scheme does that.

At the very least, it is prudent and customary that the bit size of the padded message approach the bit size of the public modulus $n$. With 256-bit $M$, padding as $\mathrm{SHA256}(B_{pub})||M$ gives 512 bits, and this is trivially breakable by cube root extraction for public exponent 3 and 1537-bit modulus or more. More sophisticated attacks work for a wider range of RSA keys.

Thus, without provision for a minimum width, and with allowance for low public exponent, we can answer "no" to the first question.

On the other hand, I know no attack when padding as $C||\mathrm{SHA256}(B_{pub})||M$ where $C$ is a public arbitrary constant of 513 bits less than the modulus (and not influencing the key generation process), and $M$ is a 256-bit random. My answer becomes "It might be secure, but we have no proof".

I take the second question as replacing $\mathrm{SHA256}(B_{pub})$ with an incremental identifier of the receiver. My answer is basically the same, with slightly less confidence.

Update: as pointed by Mehdi Tibouchi in another answer, the above schemes are insecure in the broadcast RSA setting considered in the question (at least, unless the public exponent exceeds the number of recipients), see this Håstad attack. Sorry for missing this one. Again, this shows the superiority of methods with a security proof.

The safest is With a random padding, we expand $M$ as $Rnd||M$ where $Rnd$ is secret, randomly generated for each message, and with 257 bits less than the modulus; we do NOT get a direct reduction to the basic RSA problem, because the rightmost portion $M$ is shared between multiple destinations.

If we are short on randomness beside $M$, we can elect for a user-dependent deterministic random-like padding function expanding $M$ to the full modulus, e.g. generated by a Mask Generation Function as $\mathrm{MGF}(B_{pub}||M)||M$. We keep a tight security proof reduction to the above. Of course, there is the issue that identical $M$ to the same user cause identical cryptograms.

In the third question, we are padding as $Rnd||M$ where $Rnd$ is public, randomly generated for each message, with 257 bits less than the modulus. This one seems solid, though I see no security reduction to the usual statement of the RSA problem also succumbs to the attack pointed by Mehdi Tibouchi.