Does RSA padding have to be unpredictable if the payload is? 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.
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).