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

From: Eric Rescorla <[email-masked]>
Date: Tue, 27 Apr 2021 09:44:51 -0700

I haven't studied this draft in detail, but I believe that it would be good
for this WG to work on blind signatures, as they are a primitive with a lot
of applicability.

In general, I'd probably be more inclined to select blind BLS for new
applications, but there are certainly going to be a lot of settings in
which people don't have pairing code, and in those cases, it seems like
this draft would be valuable.

-Ekr

On Thu, Mar 25, 2021 at 8:47 AM Steven Valdez <svaldez=
[email-masked]> wrote:

> I think it would be useful to have this work adopted and eventually
> standardized, various protocols/APIs seem to be building on blind signature
> style schemes, and having a draft here would help in trying to unify or at
> least provide guidance for how to use blind signatures in a more consistent
> manner. In the PrivacyPass space, this sort of scheme might be useful for
> some of the use cases that need public verifiability, where there's
> currently still a gap on how PrivacyPass implements public verifiability.
>
> Generally supportive of this draft, and would be happy to help give
> feedback on it.
>
> -Steven
>
>
> On Thu, Mar 18, 2021 at 5:21 AM Stanislav V. Smyshlyaev <[email-masked]>
> 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 [email-masked]).
>>
>> Thank you,
>> Stanislav (for the chairs)
>> _______________________________________________
>> CFRG mailing list
>> [email-masked]
>> https://www.irtf.org/mailman/listinfo/cfrg
>>
>
>
> --
>
> Steven Valdez |  Chrome Privacy Sandbox |  [email-masked] |
> 210-692-4742 <(210)%20692-4742>
> _______________________________________________
> CFRG mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>

---

From: Jeff Burdges <[email-masked]>
Date: Tue, 27 Apr 2021 20:28:27 +0200

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 <[email-masked]> wrote:
> On Wed, Feb 24, 2021 at 10:45 PM Jeff Burdges <[email-masked]> 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 <[email-masked]> 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:
> 
> 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 [email-masked]).
> 
> Thank you,

---

From: "Martin Thomson" <[email-masked]>
Date: Wed, 28 Apr 2021 08:26:32 +1000

Ekr covered my views on this also.

I am not sure that this is the ideal design, but I find being able to use existing PSS verifiers to be appealing.

On Wed, Apr 28, 2021, at 02:44, Eric Rescorla wrote:
> I haven't studied this draft in detail, but I believe that it would be 
> good for this WG to work on blind signatures, as they are a primitive 
> with a lot of applicability.
> 
> On Thu, Mar 25, 2021 at 8:47 AM Steven Valdez 
> <svaldez=[email-masked]> wrote:
> > I think it would be useful to have this work adopted and eventually standardized, various protocols/APIs seem to be building on blind signature style schemes, and having a draft here would help in trying to unify or at least provide guidance for how to use blind signatures in a more consistent manner. In the PrivacyPass space, this sort of scheme might be useful for some of the use cases that need public verifiability, where there's currently still a gap on how PrivacyPass implements public verifiability.
> > 
> > Generally supportive of this draft, and would be happy to help give feedback on it.
> > 
> > -Steven
> > 
> > 
> > On Thu, Mar 18, 2021 at 5:21 AM Stanislav V. Smyshlyaev <[email-masked]> wrote:
> >> Dear CFRG participants,
> > Steven Valdez |	 Chrome Privacy Sandbox |	 [email-masked] |	 210-692-4742 <tel:(210)%20692-4742>
> [email-masked] <mailto:CFRG%40irtf.org>

---

From: "Riad S. Wahby" <[email-masked]>
Date: Wed, 28 Apr 2021 08:33:03 -0400

Jeff Burdges <[email-masked]> wrote:
> 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.

As an alternative to rejection sampling, why not sample log2(n)+128
bits, interpret as an integer, and reduce mod n? That gives a result
statistically close to uniform mod n without a loop.

Or log2(n)+256 bits, if that feels better :)

Agreed that the GCD test is superfluous. The chance of getting a "bad"
value is morally equivalent to the chance of guessing a factor of n.

Cheers,

-=rsw

---

From: Jeff Burdges <[email-masked]>
Date: Thu, 29 Apr 2021 17:18:22 +0200

> On 29 Apr 2021, at 06:38, Jacob Bachmeyer <[email-masked]> wrote:
> What are the consequences of using a "bad" value?

You inherently perform the GCD test when computing the modular multiplicative inverse.  
https://en.wikipedia.org/wiki/Modular_multiplicative_inverse#Extended_Euclidean_algorithm

You could compute m (r^{-1})^e mod N when initially blinding and use sigma * r mod N when unblinding.  In this form, if r turns out not to be invertible then I guess you pick another r in a loop, but it’s fine if your code just panics. 

or

You could compute m r^e mod N when initially blinding and use sigma * r^{-1} mod N when unblinding.  In this form, if r turns out to not be invertible then it’s fine if your code just panics and the user looses their money.  

I’ve now forgotten if I was clever enough to use the first form in Taler or if I stupidly computed r^{-1} twice.

> Does the GCD test itself cause a timing leak or is it completed in constant time?

It's a computation that should only happen once, but yes leaking even one bit sucks.  I’m unsure about the one-off leakage characteristics of RSA implementations. 

It’s likely you withdraw many coins at once so you batch inversion helps enormously, especially with one throw away element probably.  Again this favors the m (r^{-1})^e mod N form.

Jeff