Re: [CFRG] RSA blind signatures

[Christopher Wood <[e-mail]>]

On Wed, Feb 24, 2021, at 10:44 PM, Jeff Burdges wrote:
> 
> 
> > On 25 Feb 2021, at 00:25, Christopher Wood <[e-mail]> wrote:
> >> If I recall, RSA-PSS depends upon signer randomness for its security 
> >> arguments.  As such, one should ideally not base an RSA blind signature 
> >> off PSS but instead specify a full domain hash (FDH).  
> > 
> > Is this a useful distinction? Blind RSA in general requires randomness for it to be useful (as you carefully point out above). 
> 
> That’s randomness by the token holder.  I’m taking about randomness 
> held by the issuer.

Perhaps I'm missing something, but my point was the following: Clients, who actually encode messages -- either via FDH or PSS -- require randomness to blind their message sent to the server. Servers (issuers), in contrast, deterministically sign the blinded message sent to them. (They hopefully also include some variant of blinding to mitigate obvious side channels, but that's an implementation detail.)
 
> Bellare and Rogaway suggested PSS over FDH because PSS provides a 
> tighter security argument than FDH, due to the signer providing 
> randomness, i.e. purely a provable security reason.
> https://web.cs.ucdavis.edu/~rogaway/papers/exact.pdf
> 

Indeed. This, along with availability, is primarily what led to PSS in this case. 

> > In any case, the rationale for PSS was two-fold:
> > 
> > 1) It's widely supported in libraries. (To my knowledge FDH is not widely supported... yet.)
> 
> We verify RSA blind signatures roughly three times in a typical token 
> deployment, once by the user after token issuance as part of the 
> signing algorithm, once by the merchant upon tokens being spent, and 
> once by the exchange upon tokens finally being redeemed.  As the signer 
> code must change, only the merchant code justifies a gymnastics for 
> support of existing libraries.
> 
> > 2) One can basically replicate FDH with a zero-length salt, even though some APIs make it difficult to do so.
> 
> Is a zero length salt secure?  It’s likely "less" secure than an FDH’s 
> rejection sampling, but do we know if a security proof exists or if it 
> de facto becomes roughly PKCS#1 v1.5 like? 

I'm not an expert, and I'm certainly not advocating for it, but 2019/1268 [1] seems to suggest it's safe.

Best,
Chris

[1] https://eprint.iacr.org/2019/1268.pdf

> We cannot abuse the salt to perform rejection sampling since presumably 
> the three components in PSS’ output, maskedDB, H, and bc all avoid the 
> high bit, which gets set like 1/3rd of the time.
> 
> Jeff
> 
> p.s.  An FDH consumes the input message using hash function with 
> extensible output, like shake, blake2x, ad hoc hash plus stream cipher 
> constructions, or strobe https://strobe.sourceforge.io and then 
> produces first the low order log_2 n + 1 - k output bits L where k = 
> 128 or 256, and then it produces the high k output bits H using 
> rejection sampling, i.e. loop until (H || L) < n.  It’s probably fine 
> if the whole output were rejection sampled all at once, slightly slower 
> but the performance loss sounds minor given the arithmetic.  
> 
> 
> 
>