9
$\begingroup$

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...

$\endgroup$
2
  • $\begingroup$ "...one should never use a public/private key pair for both encryption and blind signature purposes together..." - Correct. Never use the same RSA keypair for encryption and signing. Even the Wikipedia article on Blind Signatures | Dangers states it. $\endgroup$
    – user10496
    Dec 18, 2017 at 4:43
  • $\begingroup$ Also see Usability of padding scheme in blinded RSA signature? The question and answer provides a padding scheme applied at the message author's side. The construction looks a little different than the one shown in your question. It looks more like @Ilmari's answer. $\endgroup$
    – user10496
    Dec 18, 2017 at 4:44

2 Answers 2

6
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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... $\endgroup$
    – Denis
    Dec 12, 2012 at 0:01
  • $\begingroup$ If you have knowledge of standardized formatting/padding function for RSA Blind Signatures, then could you visit Is there a standard padding/format for RSA Blind Signatures? $\endgroup$
    – user10496
    Dec 19, 2017 at 23:25
5
$\begingroup$

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$
$\endgroup$
8
  • 1
    $\begingroup$ 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. $\endgroup$ Dec 11, 2012 at 11:56
  • $\begingroup$ 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... $\endgroup$
    – Denis
    Dec 11, 2012 at 23:47
  • $\begingroup$ @Denis No the bank doesn't pad. The applicant pads before blinding. $\endgroup$ Dec 12, 2012 at 11:25
  • $\begingroup$ But in that case bank is open to "RSA blinding attack", please check en.wikipedia.org/wiki/Blind_signature#Dangers_of_blind_signing $\endgroup$
    – Denis
    Dec 12, 2012 at 23:12
  • $\begingroup$ @Denis Simply don't use the same key for blind signatures and encryption/normal signatures. $\endgroup$ Dec 13, 2012 at 8:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.