Re: [CFRG] RSA blind signatures

Christopher Wood <caw@heapingbits.net> Wed, 24 February 2021 23:25 UTC

Return-Path: <caw@heapingbits.net>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id DCE553A1D52 for <cfrg@ietfa.amsl.com>; Wed, 24 Feb 2021 15:25:56 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.098
X-Spam-Level:
X-Spam-Status: No, score=-2.098 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, RCVD_IN_MSPIKE_H3=0.001, RCVD_IN_MSPIKE_WL=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=heapingbits.net header.b=VrWzymzm; dkim=pass (2048-bit key) header.d=messagingengine.com header.b=mDmGGta2
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id DiQ9RAkSKw1H for <cfrg@ietfa.amsl.com>; Wed, 24 Feb 2021 15:25:55 -0800 (PST)
Received: from out1-smtp.messagingengine.com (out1-smtp.messagingengine.com [66.111.4.25]) (using TLSv1.2 with cipher ADH-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 03AC83A1D4E for <cfrg@irtf.org>; Wed, 24 Feb 2021 15:25:54 -0800 (PST)
Received: from compute4.internal (compute4.nyi.internal [10.202.2.44]) by mailout.nyi.internal (Postfix) with ESMTP id 5EA2D5C00EF; Wed, 24 Feb 2021 18:25:54 -0500 (EST)
Received: from imap4 ([10.202.2.54]) by compute4.internal (MEProxy); Wed, 24 Feb 2021 18:25:54 -0500
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=heapingbits.net; h=mime-version:message-id:in-reply-to:references:date:from:to :cc:subject:content-type:content-transfer-encoding; s=fm3; bh=in bc+tV70Fcnqqvg6aomdacKCn9Z3d8pCVLOLrZ0DE4=; b=VrWzymzmgKfWeGfxc2 90QtH5pBoKwN3qkbjH78CxRKSU55ZxA/bnmmbz0mL9/WVCFS6PEGhKqLNl/M8rQT oWTgQcmzasO/JVXeSj4SfWy0l5gtViMlr5jSdxMfccMrKedKBOFbnYz3O5WtJCMJ msENpCtyIfUIPK3wDJjPwrhbCiiVujKQcl1XEHIAG2dWnxvS8j2Yl4L4lC6UPICc FvD9CYy5vpV1wHxUvSnr9V3wMNFEDB39NtFOQPogKsjS7j4ZNo6yx7CcyXyfKxIO NFSaXZ0VVx20JBizaCnk/Pqz1Seo//5tLShz96ajJ1f8iGAADpzKCzTJ8ojb+Elc j5Yw==
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:content-transfer-encoding:content-type :date:from:in-reply-to:message-id:mime-version:references :subject:to:x-me-proxy:x-me-proxy:x-me-sender:x-me-sender :x-sasl-enc; s=fm2; bh=inbc+tV70Fcnqqvg6aomdacKCn9Z3d8pCVLOLrZ0D E4=; b=mDmGGta2+g/5+RbKz0IP0J1X3OGqrkoX9NKez43QEBrdzqz45X6i92US4 8Z4SnElGPSgD3QhjYI8YaH8RabWJ6Q4te7hWKpSwuhczWqOgi/7aiRAozc0xCmu8 Gu+PdNYcjsdk5Qid4c8gqhMPfJSlKrXMb7WiUeQE1Uyi65TyIVV2fYR/4/Vd/5tx lcuzgIcouYzWZYOs+L9sZyQDHnKZh9DNH/HGRPNPNJVGC/sZesD4HBAxbU24OSw0 qFJmFohBZhnGrlLTmnTklQCiPARNK4CVV06AbD8RSJczbqQnjDskDgMITnyANxX0 MLYL8GZPaEu/JStWYUWnkoXfgAznQ==
X-ME-Sender: <xms:geA2YNQD2AxNTXYcwYjQ1m1B-eHn4DddK4n2jxMG_gS7EVOIzAi7Rg> <xme:geA2YGw10DKwle_I29gZ2mA-ELIuwwXE_WFYvjBP0hYNtyR1HPWx6-l1YY81yUzVC PzWExYgZIALJ17R32k>
X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeduledrkeekgddtkecutefuodetggdotefrodftvf curfhrohhfihhlvgemucfhrghsthforghilhdpqfgfvfdpuffrtefokffrpgfnqfghnecu uegrihhlohhuthemuceftddtnecusecvtfgvtghiphhivghnthhsucdlqddutddtmdenog fuuhhsphgvtghtffhomhgrihhnucdlgeelmdenucfjughrpefofgggkfgjfhffhffvufgt gfesthhqredtreerjeenucfhrhhomhepfdevhhhrihhsthhophhhvghrucghohhougdfuc eotggrfieshhgvrghpihhnghgsihhtshdrnhgvtheqnecuggftrfgrthhtvghrnheptdev feevfeejkeffffegudetudeuueehfedthfeuveetfeetleeuueegfeeilefgnecuffhomh grihhnpehgihhthhhusgdrtghomhdpthgrlhgvrhdrnhgvthdpihgvthhfrdhorhhgpdhg ihhthhhusgdrihhopdhirggtrhdrohhrghdpihhrthhfrdhorhhgnecuvehluhhsthgvrh fuihiivgeptdenucfrrghrrghmpehmrghilhhfrhhomheptggrfieshhgvrghpihhnghgs ihhtshdrnhgvth
X-ME-Proxy: <xmx:geA2YC0flpF_wiY7whPVV6vOefDmw729gQHLYoNTrXQljc_3B47PYg> <xmx:geA2YFAgTeVKvu18RYnsrLFoCNZr_-_20z4zsUEeRCv-ddx7czJSQg> <xmx:geA2YGhm4lKUOdCAuwN0zG_ZOMj4dNRDIUH_Bgf17j9LkXk__m8_hQ> <xmx:guA2YOIUhZ4GT87bI_dpMMIJUXW_5uBIjY-weJf8CYRXyhHk_kx36g>
Received: by mailuser.nyi.internal (Postfix, from userid 501) id B5C6016006B; Wed, 24 Feb 2021 18:25:53 -0500 (EST)
X-Mailer: MessagingEngine.com Webmail Interface
User-Agent: Cyrus-JMAP/3.5.0-alpha0-141-gf094924a34-fm-20210210.001-gf094924a
Mime-Version: 1.0
Message-Id: <c569e285-f592-45ed-9ce9-e68572b15b96@www.fastmail.com>
In-Reply-To: <19E2AA22-2B2B-4BCB-8171-B6386D39C616@gnunet.org>
References: <44983891-284f-4552-b4c7-bc432148d214@www.fastmail.com> <19E2AA22-2B2B-4BCB-8171-B6386D39C616@gnunet.org>
Date: Wed, 24 Feb 2021 15:25:18 -0800
From: "Christopher Wood" <caw@heapingbits.net>
To: "Jeff Burdges" <burdges@gnunet.org>
Cc: "IRTF CFRG" <cfrg@irtf.org>, Taler <taler@gnu.org>
Content-Type: text/plain;charset=utf-8
Content-Transfer-Encoding: quoted-printable
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/P8znYQRIGV6T5bmUUEYpgGGSzKY>
Subject: Re: [CFRG] RSA blind signatures
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Wed, 24 Feb 2021 23:25:57 -0000

Hi Jeff,

Thanks for the feedback! Please see inline below.

On Wed, Feb 24, 2021, at 12:03 AM, Jeff Burdges wrote:
> 
> It’s critically important the blinding factor r be a uniformly random 
> integer mod n, which I think deserves more emphasis than you give.  
> There is an easy deanonymization attack if r were say generated a 
> random integer mod 2^{floor(log2 n)}.  You hould emphasize that 
> random_integer should be instantiated with a CSPRNG and rejection 
> sampling, maybe even specify the rejection sampling algorithm starting 
> with shake or chacha.  

Indeed -- we can definitely sharpen the language here to emphasize the importance of this point:

   https://github.com/chris-wood/draft-wood-cfrg-blind-signatures/issues/55

> 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). 

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.)
2) One can basically replicate FDH with a zero-length salt, even though some APIs make it difficult to do so.

> At this point, one could specify the blinding factor be produced by 
> applying the FDH to system randomness.  This is what I did for Taler’s 
> blind RSA signatures: https://taler.net/en/
> 
> Initially I wanted to point you to the RSA-FDH-VRF in 
> https://datatracker.ietf.org/doc/draft-irtf-cfrg-vrf/ except..  
> Actually the RSA-FDH-VRF draft does not properly specify the FDH 
> either, but only points to https://tools.ietf.org/html/rfc8017 which 
> does not specify the FDH.
> 
> An FDH is a pretty easy notion but people get this wrong.  Also, there 
> might be interoperability advantages in specifying it more fully. 

Quite true! Perhaps a more clean specification of FDH would address (1) above?

Best,
Chris

> p.s.  I think one should not deploy RSA-FDH-VRF but instead work 
> through all the tricks to make Rabin-Williams deterministic.  It’s not 
> too hard but not as easy as RSA-FDH-VRF.  I’ve no looked at wether 
> Rabin-Williams could be adopted to blind signatures, but I think some 
> issues arose beyond what one alters for a Rabin-Williams VRF. 
> 
> 
> 
> 
> 
> > On 23 Feb 2021, at 18:37, Christopher Wood <caw@heapingbits.net> wrote:
> > 
> > There are a growing number of use cases where we need something like VOPRFs but with public verifiability [1,2]. Given the results in 2020/945 [3], it seems prudent to try and fill the gap with something we know is reasonably safe. To that end, here's a draft describing RSA-based blind signatures:
> > 
> >   https://chris-wood.github.io/draft-wood-cfrg-blind-signatures/draft-wood-cfrg-rsa-blind-signatures.html
> > 
> > (I missed the deadline yesterday, so apologies for not having an actual datatracker draft to point at.)
> > 
> > Obviously, something better than RSA (in terms of bandwidth and overall messages) would be great. But it's not clear what that is right now.
> > 
> > Time permitting, I'd like to request some time on the agenda to present this to the group at IETF 110.
> > 
> > Thanks,
> > Chris
> > 
> > [1] https://github.com/ietf-wg-privacypass/base-drafts/issues/40
> > [2] https://github.com/privacycg/private-click-measurement/issues/27
> > [3] https://eprint.iacr.org/2020/945.pdf
> > 
> > _______________________________________________
> > CFRG mailing list
> > CFRG@irtf.org
> > https://www.irtf.org/mailman/listinfo/cfrg
> 
>