RSA blind signatures in practice

Hi I have a problem with moving my blind signature implementation from educational (textbook RSA) to more practical (padded RSA) side.

David Chaums paper gives a following figure:

$r$ - blinding factor

$e$, $d$ - public & private exponent

$Blinded\ message = Message \cdot r^{e}$

$Signature\ of\ a\ Blinded\ message = Blinded\ message^{d} = (Message \cdot r^{e})^{d} = Message^{d} \cdot r^{ed} = Message^{d} \cdot r\ (\bmod\ N)$

now to unblind a blinded message we should remove the blinding factor:

$Unblinded\ signature = Signature\ of\ a\ Blinded\ message \cdot r^{-1} = Message^{d} \cdot r\ \cdot r^{-1} = Message^{d}\ (\bmod\ N)$

It is clear that real-world RSA implementation shouldn't use plain textbook for encryption or signature purposes as it is vulnerable to a range of attacks. To overcome these attacks a textbook must be armoured with "padding", prior encryption or signature operation.

Now, as far as I understood (in simple English): a "padding" process "changes" the plain text prior encryption to make it more durable to known attacks.

Mathematically speaking, the whole process would look like:

$Signature\ of\ a\ Blinded\ message = pad(Message \cdot r^{e})^{d} (\bmod N)$

In other words "padding" destroys blind signature, because there is no such "$unpad$" function that would satisfy the following equation:

$unpad(pad(Message \cdot r^{e})^{d})\ (\bmod N) = (Message \cdot r^{e})^{d}$

So this means blind signatures can not be used with padding.

Question Am I correct that using blind signatures in practice, one should never use a public/private key pair for both encryption and blind signature purposes together, and to actually use a blind signature that person is obligated operate on a plain textbook making the whole process vulnerable to a range of attacks?

EDIT

As far as I understood the whole process, there are two sides A - Applicant, B - Bank. For example Applicant creates a token that represents 10\$with serial number AH43S, then Applicant blinds the token with random R so that the Bank is not able to discover token's serial number. Then applicant sends blinded token to Bank, and asks it to sign with 10\$ key. Now Bank needs to pad a blinded version of token, to prevent any attacks on it's key, and after the blinded token is padded there is no way to unblind it...

The padding is applied on the bank side(side that signs the message), am I correct? And if so, it would break blinding factor presented by the side that asked to sign a token...

-

2 Answers

The answer is correct, you don't need to unpad the message. When/if you verify the signature, simply check that $(\text{signature})^e == \text{pad}(\text{message})$

Regarding the padding scheme, you can just use a full domain hash.

Here's how you implement a full domain hash: $$\mathrm{cycles} = \frac{\text{(RSA key length)}}{\text{(SHA digest length)} \times 8} + 1$$ (e.g., RSA key length = 1024bits and SHA digest length = 20bytes) $$\mathrm{FDH}(M) = \mathrm{SHA1}(M || 0) \mathbin\Vert \mathrm{SHA1}(M || 1) \mathbin\Vert \ldots \mathbin\Vert \mathrm{SHA1}(M || \mathrm{cycles}-1)$$

where $||$ denotes concatenation

-
I don't need to unpad a message, the problem is that the padding is applied by the signer, to prevent fraud, and when the signer pads the blind signature, he destroys it... –  Denis Dec 12 '12 at 0:01

I'm not really familiar with blind signature schemes, so please take the following with a grain of salt, but what you describe looks like a really funny way to apply padding. Normally, one would pad the message (using a suitable padding scheme like RSA-PSS) before the first RSA operation, i.e.

• $\text{padded message = pad(message)}$
• $\text{blinded message = padded message} \cdot r^e \pmod N$
• $\text{blinded signature = blinded message}^d = \text{padded message}^d \cdot r \pmod N$
• $\text{signature = blinded signature} \cdot r^{-1} = \text{padded message}^d \pmod N$
-
The main difference between blind and normal signatures is that the adversary creates the padding for a blind signature. So I'd prefer some kind of deterministic padding (such as FDH), since it reduces the freedom of the attacker. –  CodesInChaos Dec 11 '12 at 11:56
As far as I understood the whole process, there are two sides A - Applicant, B - Bank. For example Applicant creates a token that represents 10\$with serial number AH43S, then Applicant blinds the token with random R so that the Bank is not able to discover token's serial number. Then applicant sends blinded token to Bank, and asks it to sign with 10\$ key. Now Bank needs to pad a blinded version of token, to prevent any attacks on it's key, and after the blinded token is padded there is no way to unblind it... –  Denis Dec 11 '12 at 23:47
@Denis No the bank doesn't pad. The applicant pads before blinding. –  CodesInChaos Dec 12 '12 at 11:25
But in that case bank is open to "RSA blinding attack", please check en.wikipedia.org/wiki/Blind_signature#Dangers_of_blind_signing –  Denis Dec 12 '12 at 23:12
@Denis Simply don't use the same key for blind signatures and encryption/normal signatures. –  CodesInChaos Dec 13 '12 at 8:43