Usability of padding scheme in blinded RSA signature?

Question

In Wikipedia's article on Blind signature, in the section Dangers of blind signing which describes RSA blinding attack one reads the following

This attack works because in this blind signature scheme the signer signs the message directly. By contrast, in an unblinded signature scheme the signer would typically use a padding scheme (e.g. by instead signing the result of a cryptographic hash function applied to the message, instead of signing the message itself), however since the signer does not know the actual message, any padding scheme would produce an incorrect value when unblinded.

Could someone please explain the meaning of the part I emphasized?

Answer 1

In the blind RSA signature scheme the blinding of a message $m$ (to be blindly signed) is multiplicative with value $r^e$, where you ensure that $r$ is invertible modulo $N$.

So if the sender receives the signed blinded message back from the signer, he can unblind by multiplying with $r^{-1}$, yielding $s\equiv m^d \pmod N$ which is a valid (textbook) RSA signature for $m$.

Padding by the sender

Note, that $m$ could also be the result of any padding method for RSA signatures, which however needs to be applied by the sender before blinding. By denoting this padding as $f$ we can simply consider the blinded message to be $m'\equiv f(m)r^e \pmod N$ (which clearly can be unblinded after blind signing).

Padding by the signer

Denoting the blinded message which is sent to the signer as $m'\equiv mr^e \pmod N$, then padding by the signer means that the signer changes the blinded message $m'\equiv mr^e \pmod N$ to some $m''$ before signing. Padding methods for RSA signatures hash the original message (possibly with some parameters), padd the hash value to some certain format and the result is then interpreted as an element in $Z_N$, which is then exponentiated with the private signing exponent $d$.

Observe that in doing so the signer padds an already blinded message and denote this padded blinded message as $m''=f(m')=f(mr^e)$. If such a padding to the message $m'$ received by the signer is applied by the signer, then the signature obtained by the sender for $m''$ will be $s' \equiv (f(mr^e))^d \pmod N$ and then unblinding, i.e., computing $s'\cdot r^{-1} \equiv (f(mr^e))^d\cdot r^{-1} \pmod N$, will yield some element from $Z_N$ which is clearly not a valid signature $m^d\pmod N$ for the message $m$ the sender wants to be signed (for padding functions $f$ we assume to be applied, i.e., involving hashing. Clearly, if $f$ is the identity function then it works, but that is no padding).

Answer 2

Answer by DrLecter looks incorrect. Afaik almost all RSA padding schemes have been deprecated. I believe unblinded RSA would use PSS padding today, but as I explained in https://crypto.stackexchange.com/a/60728/764 any padding like PSS that directly takes randomness from the signer trivially violates blindness.

In fact, blind RSA requires a full domain hash (FDH) for padding, which PSS, etc. do not provide. If you even truncate the padding to floor(log N), like PSS does I think, then you leak like 1/6th or 12th bit deanonymizing information per signature. If leave many bits determined like some older ones, then your blind signature scheme becomes worthless.

You can implement FDH easily: Frist, create a stream cipher S from the message hash. Second, run a loop that pull ceiling(log N) bit number r from S and repeats until r < N. In other words our stream cipher's block counter keeps increasing. Your loop terminates quickly because N should lie roughly half way between powers of two, but obviously you might explore tricks like avoiding N below say 1.3 * 2^floor(log N) or only looping on the top 256 bits of N.

There are way to incorporate randomness from the signer if you want to try to resurrect some shadow of PSS because we verify the padding when verifying the signature.

If you believe RSA-KTI, then there are no forgery attacks. I'd incorporate the signer's public key N into the message hash anyways though, because doing so costs you nothing and prevents amortizing attacks on RSA-KTI across many RSA keys.