5
$\begingroup$

I'm working on a RSA blinded signature scheme. RSA Blind signatures are discussed in Chaum's original paper and other places like wikipedia.

The descriptions of RSA blind signatures are straight forward, but they seem to use the original message rather than a formatted or padded message. According to Rabin (1979) we should be using at least H(m).

My question is, is there a standard covering RSA Blind Signatures we should be using? Is there an accepted way to format the message when used in a RSA Blind Signature scheme?

I know the question has some open ends, like security goals being under specified. But we are looking for something that provides intractability of signature-forgery and enjoys some interoperability. I'd like to say we want all the security properties detailed by Bernstein in RSA signatures and Rabin–Williams signatures: the state of the art, but I won't go that far.


Related, here are two questions that explain how to provide a padding function at the author (as opposed to the signer). Both appear to be ad hoc methods.

$\endgroup$
  • 1
    $\begingroup$ Unlikely! I'd just build a full-domain hash out of SHAKE256 with double-length reduction to be safe from modulo bias. Say your modulus has 2048 bits; for message $m$ and blinding factor $r$, use blinded message $m' = r^e h \bmod n$ where $h$ is some integer interpretation of SHAKE256-4096(m). Make sure to include all information you care about in the input to SHAKE256, and maybe add an application label for domain separation just for good measure. $\endgroup$ – Squeamish Ossifrage Dec 19 '17 at 23:41
  • $\begingroup$ Thanks @SqueamishOssifrage. Since I can't seem to find a standard I'm guessing I may have traveled down the wrong path. What is the modern equivalent to a blind signature? What should be used nowadays? $\endgroup$ – user10496 Dec 19 '17 at 23:52
  • $\begingroup$ Depends on what you're trying to do. What are you trying to do? Maybe blind signatures are what you need, maybe not. There just aren't a lot of widespread applications out there that use them, so I don't think they're standardized anywhere. Want an interoperable standard? If you have an application that warrants interoperable standardization, you could be the one to write the RFC for the IETF on it! If it's practically justified, there's probably a cryptographer who can help with the details, because everyone thinks blind signatures are pretty cool. $\endgroup$ – Squeamish Ossifrage Dec 19 '17 at 23:56
  • $\begingroup$ @SqueamishOssifrage - There are two instance problems. First, I help with a free/open source crypto library. A generalized blind signature scheme would make a good addition. Second, there's a fellow asking for a scheme. I don't know the exact details of the request, but the cryptographic primitive was selected. I've also seen similar requests for other libraries, like Botan and OpenSSL. $\endgroup$ – user10496 Dec 20 '17 at 0:30
1
$\begingroup$

There are random oracle model security proofs for RSA-PSS and RSA-FDH. There are standards for RSA-PSS but it requires randomness from the signer and thus does not work for blind signatures. RSA-FDH works with blinding.

RSA-FDH might appear in some standard somewhere, but honestly "full domain hash" is kinda self explanatory to a cryptographer. As an FDH example see https://git.gnunet.org/gnunet.git/tree/src/util/crypto_kdf.c#n113 for the RSA code in https://git.gnunet.org/gnunet.git/tree/src/util/crypto_rsa.c used in GNU Taler.

There is afaik no standard for blind signatures per se, but you must use a full domain hash for both the message and the blinding factor, well formally the blinding factor is a FD-PRF, but that's the same code.

If you use too small a hash function for the message, then an adversary can factor message hashes, find enough colliding factors, and forge messages. Or worse since even the basic signature scheme security proof requires FDH. All the security proofs that protect against such "one more forgery" attacks require both FDH and the non-standard RSA-KTI "known target inversion" assumption.

If you do not use a FD-PRF for the blinding factor then you'll leak enough information with each message that an adversary can deanonymize you after well under 100 messages.

I'll emphasize: If you have a 2048 bit RSA key n then your domain for the hash is [0,n) so you must generate a 2048 bit number r, test if it is less than n, and repeat if not. You do not have an FDH if you merely generate one 2048 bit or 2027 bit number and use it directly. RSA is not forgiving about this because an RSA modulus lands roughly half way between powers of two, unlike say elliptic curve group orders which are chosen very close to a power of two.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy