Re: [CFRG] Call for adoption for draft-wood-cfrg-rsa-blind-signatures

I previously raised an objection to PSS padding in blind RSA over both confusion concerns as well as absence of security arguments.  I agree with Mihir Bellare that Blind RSA with PSS padding and rejection sampled aka FDH blinding factors looks secure, but actually technically nobody yet made this claim concrete.  Anyways..

We need a strong clarification that blinding factors should be rejection sampled from the RSA group, meaning same bit width and rejection if they exceed the modulus.  I’ve some GCD test in GNU Taler’s code but that’s unnecessary since n - phi(n) = pq - (p-1)(q-1) = p + q -1 << n. 

Implementations that produce produce blinding factors using floor(log_2 n) bits provide no appreciable anonymity.  It’s a trivial attack:  An exchange computes isig[i] / rsig[j] for all issued signatures isig[i] and all redeemed signatures rsig[j].  Anytime i and j correspond then isig[i] / rsig[j] gives a blinding factor, so if blinding factors leak half a bit of entropy, then the exchange deanonymizes the user after only a few spent coins, usually only one transaction.

Implementations that produce blinding factors using the PSS code deanonymize users with only one coin!  I’d say blinding factors are the most important part of the document.

It’s obviously simplest if one spells out an FDH once and then reuses it for both the signature and blinding factor, so it’s better if a draft provides this option.  I’d imagine GNU Taler would continue using this approach, meaning RSA-FDH should see deployment eventually.  

I also accept Christopher Wood’s argument that reusing existing RSA-PSS verification code provides value too.

In short, fix the blinding factors, make a big deal about them, and maybe support RSA-FDH and RSA-PSS variants. 

Best,
Jeff

> On 25 Feb 2021, at 17:38, Mihir Bellare <mihir@eng.ucsd.edu> wrote:
> On Wed, Feb 24, 2021 at 10:45 PM Jeff Burdges <burdges@gnunet.org> wrote:
> 
> > 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.
> 
> The proofs for RSA-FDH and RSA-PSS as normal signatures are from the one-wayness assumption on RSA. As you say, the reduction for RSA-PSS is tight, and that for RSA-FDH is not. The proof for Blind-RSA-FDH is from the One-More Discrete Log (OMDL) problem, and this would also be the case for Blind-RSA-PSS. I have not done the latter proof in detail, so this is just a guess, but I don't see a difference in tightness between the two. So from the point of view of tightness of security arguments, my guess is that Blind-RSA-FDH and Blind-RSA-PSS are about the same. I understand of course that there may be many other factors and reasons to prefer one over the other.
> 
> PSS, when used as a normal signature, can be de-randomized in the usual way of deriving the randomness by hashing the secret signing key and the message, but this does not seem to apply in the blind case.
> 
> Mihir

> 
> On 18 Mar 2021, at 10:21, Stanislav V. Smyshlyaev <smyshsv@gmail.com> wrote:
> 
> Dear CFRG participants,
> As a follow-up to the discussion at the recent CFRG meeting, this email commences a 3-week call for adoption for "RSA Blind Signatures" draft (draft-wood-cfrg-rsa-blind-signatures-00) that will end on April 9th 2021:
> 
> https://datatracker.ietf.org/doc/draft-wood-cfrg-rsa-blind-signatures/
> 
> Please give your views on whether this document should be adopted as a CFRG draft, and if so, whether you'd be willing to help work on it/review it. Please reply to this email (or in exceptional circumstances you can email CFRG chairs directly at cfrg-chairs@ietf.org).
> 
> Thank you,
> Stanislav (for the chairs)
> _______________________________________________
> CFRG mailing list
> CFRG@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg