Subject: [CFRG] I-D Action: draft-irtf-cfrg-rsa-blind-signatures-02.txt

From: [email-masked]
Date: Mon, 02 Aug 2021 08:43:12 -0700

A New Internet-Draft is available from the on-line Internet-Drafts directories.
This draft is a work item of the Crypto Forum RG of the IRTF.

        Title           : RSA Blind Signatures
        Authors         : Frank Denis
                          Frederic Jacobs
                          Christopher A. Wood
	Filename        : draft-irtf-cfrg-rsa-blind-signatures-02.txt
	Pages           : 16
	Date            : 2021-08-02

Abstract:
   This document specifies the RSA-based blind signature scheme with
   appendix (RSA-BSSA).  RSA blind signatures were first introduced by
   Chaum for untraceable payments [Chaum83].  It extends RSA-PSS
   encoding specified in [RFC8017] to enable blind signature support.

Discussion Venues

   This note is to be removed before publishing as an RFC.

   Source for this draft and an issue tracker can be found at
   https://github.com/chris-wood/draft-wood-cfrg-blind-signatures.

The IETF datatracker status page for this draft is:
https://datatracker.ietf.org/doc/draft-irtf-cfrg-rsa-blind-signatures/

There is also an htmlized version available at:
https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-rsa-blind-signatures-02

A diff from the previous version is available at:
https://www.ietf.org/rfcdiff?url2=draft-irtf-cfrg-rsa-blind-signatures-02

Internet-Drafts are also available by anonymous FTP at:
ftp://ftp.ietf.org/internet-drafts/

---

From: "Christopher Wood" <[email-masked]>
Date: Mon, 02 Aug 2021 08:48:49 -0700

As of now, there are no more outstanding issues against this draft. The editors think this version is feature complete and would welcome additional review. Please send any and all feedback either here on the list or as an issue:

   https://github.com/cfrg/draft-irtf-cfrg-blind-signatures/issues

Chairs, please let us know if anything else is needed for a review from the Crypto Review Panel.

Thanks,
Chris

On Mon, Aug 2, 2021, at 8:43 AM, [email-masked] wrote:
> _______________________________________________
> CFRG mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>

---

From: Ian Goldberg <[email-masked]>
Date: Mon, 2 Aug 2021 13:29:12 -0400

>    https://github.com/cfrg/draft-irtf-cfrg-blind-signatures/issues

In 8.6, should "Signers can enforce concurrent sessions" be "Signers can
enforce a limit on concurrent sessions"?

---

From: "Christopher Wood" <[email-masked]>
Date: Mon, 02 Aug 2021 12:23:57 -0700

> enforce a limit on concurrent sessions"?

Yep, thanks!

   https://github.com/cfrg/draft-irtf-cfrg-blind-signatures/pull/88

Best,
Chris

---

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Fri, 6 Aug 2021 13:01:32 +0300

Dear CFRG,

As we discussed during the meeting, Alexey, Nick and I will be happy to
have some reviews from the CFRG participants.

Any volunteers to review the draft?

https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-rsa-blind-signatures

Regards,
Stanislav

On Mon, 2 Aug 2021 at 22:25, Christopher Wood <[email-masked]> wrote:

> > > As of now, there are no more outstanding issues against this draft.
> The editors think this version is feature complete and would welcome
> additional review. Please send any and all feedback either here on the list
> or as an issue:
> > >

---

From: Scott Hendrickson <[email-masked]>
Date: Fri, 6 Aug 2021 06:42:43 -0700

Having used blind signatures in multiple applications, I’m happy to review
the draft.

---

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Sun, 8 Aug 2021 10:38:24 +0300

Thanks a lot, Scott, that would be great!

---

From: "Salz, Rich" <[email-masked]>
Date: Mon, 9 Aug 2021 15:27:41 +0000

I read the draft.

I liked the rationale/motivation in the Introduction.

I kept getting thrown by the asymmetry between “OS2IP” and “I2OSP” – shouldn’t that latter be “IP2OS” ? (Yes know 8017/PKCS1.5 is at fault)

Maybe use the half-open “[m,n)” notation as well?

The rest of the doc is just swell.  I like the comparison to other schemes. I thought “no duh” when reading the post-quantum section and wonder if it’s worth removing or reducing to one sentence.

---

From: Ian Goldberg <[email-masked]>
Date: Wed, 18 Aug 2021 17:49:21 -0400

> enforce a limit on concurrent sessions"?

Here are more notes.  I did not check the test vectors.

1:

"secret keys entities" -> "secret keys to entities"
"are doubled" -> "is doubled"

8.1:

There's a MUST here, but the thing that MUST be included just says "such
as RSA blinding".  First, "RSA blinding" should have a reference so that
implementers know exactly what they MUST implement (especially since
this document itself might at first glance appear to be that), but the
larger question is what does "MUST implement an X such as Y" actually
mean?  It's OK to implement X if you do it in a manner other than Y?
What if you do it in a really bad manner?

8.2:

"is that signer" -> "is that the signer"

8.6:

"Signers can enforce concurrent sessions, though the limit
(approximately 256) for reasonably secure elliptic curve groups is small
enough to make large-scale signature generation prohibitive.": this
sentence makes it sound as though, if you keep concurrency to less than
256, you're safe.  That's not (as I understand it) the case.  The paper
shows a very fast attack for 256 using its new [PolytimeROS] attack, but
the original subexponential [Wagner02] attack works for much smaller
levels of parallelism: for 15 parallel sessions, the attack runs in
~2^55 time (says [FPS20]), which is much lower than the desired security
parameter.  Even Clause Blind Schnorr just multiplies the complexity by
2^15 (for 15 parallel sessions), so ~2^70, which is still a far cry from
the desired 2^128 security level.

10.2:

The [WM99] entry is missing authors, date, URL.

[BLS-Proposal], [PolytimeROS], [RemoteTiming] are missing dates

-- 
Ian Goldberg
Canada Research Chair in Privacy Enhancing Technologies
Professor, Cheriton School of Computer Science
University of Waterloo

---

From: Chelsea Komlo <[email-masked]>
Date: Mon, 30 Aug 2021 03:00:15 +0000

Here are some high-level notes and one specific recommendation.

I recommend adding to Section 8.6 a discussion of U-Prove [1] and how the broader goals of this draft (use of blind signatures to address the shortcomings of VOPRFs) relate to the design of U-Prove.

I also recommend including a short discussion of practical/desired extensions to Privacy Pass and how/if these extensions can be accommodated by Blind RSA. For example, including public metadata such as expiration timestamps, etc.

Section 5.1.1

"The blinding factor r must be randomly chosen from a uniform distribution. This is typically done via rejection sampling."

Is this not implied by the function random_integer_uniform?

Best,

Chelsea

[1] https://www.microsoft.com/en-us/research/project/u-prove/

________________________________
From: CFRG <[email-masked]> on behalf of Stanislav V. Smyshlyaev <[email-masked]>
Sent: Thursday, August 5, 2021 10:01:32 PM
To: CFRG
Cc: [email-masked]
Subject: Re: [CFRG] I-D Action: draft-irtf-cfrg-rsa-blind-signatures-02.txt

Dear CFRG,

As we discussed during the meeting, Alexey, Nick and I will be happy to have some reviews from the CFRG participants.

Regards,
Stanislav

On Mon, 2 Aug 2021 at 22:25, Christopher Wood <[email-masked]<mailto:[email-masked]>> wrote:

Yep, thanks!

Best,
Chris

_______________________________________________
CFRG mailing list
[email-masked]<mailto:[email-masked]>
https://www.irtf.org/mailman/listinfo/cfrg

---

From: Jeff Burdges <[email-masked]>
Date: Mon, 30 Aug 2021 12:17:37 +0200

I wonder if the underlying RSA scheme should be called roughly RSA-PDH or something, where PHD = partial domain hash, because the security does not come via the same argument as in PSS.

> On 30 Aug 2021, at 05:00, Chelsea Komlo <[email-masked]> wrote:
> Section 5.1.1
> 

In principle yes, but their desire to use PSS as a “partial domain hash” worried some of us that people would reuse the PSS “hasher” for the blinding factor, which instantly breaks the anonymity.  We’ve enough cases in elliptic curves where being full domain does not mater, ala ECDSA, that people do fuck this up in blind RSA.  I suggested finding more specific language for this reason.  

Jeff

---

From: "Christopher Wood" <[email-masked]>
Date: Mon, 30 Aug 2021 06:29:25 -0700

(-list)

On Mon, Aug 30, 2021, at 3:17 AM, Jeff Burdges wrote:
> 
> I wonder if the underlying RSA scheme should be called roughly RSA-PDH 
> or something, where PHD = partial domain hash, because the security 
> does not come via the same argument as in PSS.

Can you please elaborate on this? PSS _is_ the encoding scheme used in this draft, so I don't see why we'd change the name of the encoding scheme here. 

Thanks,
Chris

> In principle yes, but their desire to use PSS as a “partial domain 
> hash” worried some of us that people would reuse the PSS “hasher” for 
> the blinding factor, which instantly breaks the anonymity.  We’ve 
> enough cases in elliptic curves where being full domain does not mater, 
> ala ECDSA, that people do fuck this up in blind RSA.  I suggested 
> finding more specific language for this reason.  
> 
> Jeff
> 
>

---

From: "Christopher Wood" <[email-masked]>
Date: Mon, 30 Aug 2021 06:30:21 -0700

Oops -- I meant to -list to keep the thread focused. Sorry about that!

On Mon, Aug 30, 2021, at 6:29 AM, Christopher Wood wrote:
> Can you please elaborate on this? PSS _is_ the encoding scheme used in 
> this draft, so I don't see why we'd change the name of the encoding 
> scheme here. 
> 
> Thanks,
> Chris
>

---

From: "Christopher Wood" <[email-masked]>
Date: Mon, 30 Aug 2021 06:58:22 -0700

Thanks for the feedback, Chelsea! Please see inline below.

On Sun, Aug 29, 2021, at 8:00 PM, Chelsea Komlo wrote:
>  
> I recommend adding to Section 8.6 a discussion of U-Prove [1] and how 
> the broader goals of this draft (use of blind signatures to address the 
> shortcomings of VOPRFs) relate to the design of U-Prove. 

I filed this to track the suggestion: https://github.com/cfrg/draft-irtf-cfrg-blind-signatures/issues/95

> I also recommend including a short discussion of practical/desired 
> extensions to Privacy Pass and how/if these extensions can be 
> accommodated by Blind RSA. For example, including public metadata such 
> as expiration timestamps, etc. 

I filed this to noting how blind RSA could satisfy public verifiability for Privacy Pass: https://github.com/cfrg/draft-irtf-cfrg-blind-signatures/issues/96. 

I don't think we should touch on features not supported by the draft (such as partially blind signature support), as that list is likely extensive. 

> Section 5.1.1
>
> "The blinding factor r must be randomly chosen from a uniform 
> distribution. This is typically done via rejection sampling."
> 

It is, though as Jeff said, we added this note for additional clarity. 

Best,
Chris

---

From: Jeff Burdges <[email-masked]>
Date: Mon, 30 Aug 2021 16:40:07 +0200

> On 30 Aug 2021, at 15:29, Christopher Wood <[email-masked]> wrote:

PSS originates from a specific security argument.  As we discussed with Mihir here, your RSA should be secure, but it’s security has no connection with the security argument behind PSS.  It actually an RO security argument for RSA-FDH plus Mihir's observation that less than FDH works.

Although you support PSS verifiers, your scheme is closer to RSA-FDH from a provable security perspective.  And blind signing is inherently almost totally different from PSS signing of course. 

I think PRIMITIVE-PROOFREASON is a quite unusual naming scheme though, so likely others here have opinions.  :)  The actual reason for saying RSA-PDH is just so that people do not miss-read the document, but maybe that’s overkill.  I donno..

Best,
Jeff

---

From: Scott Hendrickson <[email-masked]>
Date: Mon, 30 Aug 2021 08:29:48 -0700

Just closing the loop.

I had a few minor comments that we closed out here:
https://github.com/cfrg/draft-irtf-cfrg-blind-signatures/pull/94

Best,
Scott

On Sun, Aug 8, 2021 at 12:38 AM Stanislav V. Smyshlyaev <[email-masked]>
wrote:

>> Having used blind signatures in multiple applications, I’m happy to
>> review the draft.
>>

---

From: Watson Ladd <[email-masked]>
Date: Tue, 31 Aug 2021 17:10:04 -0400

Salute omnes,

I've taken a look at the draft. First I think  that the section on
randomized vs deterministic signatures is a bit confusing. The server
never sees the unblinded message, so it's not possible to use the salt
as a subliminal channel. The draft also says that applications using a
deterministic salt should take into account the security
considerations but doesn't say what the security considerations that
should be taken into account are.

In the section discussing related protocols one of the big advantages
of RSA over alternatives, namely verification speed, is given short
shrift.  In cases such as privacy pass where issuance is gated by an
expensive verification, but verification must be exposed, expensive
verification is a liability. RSA verification can be as small as three
multiprecision multiplications: very hard to do much better.

I have also not verified the test vectors.

Sincerely,
Watson

--
Astra mortemque praestare gradatim