Re: [CFRG] RSA blind signatures

Christopher Wood <caw@heapingbits.net> Thu, 25 February 2021 12:32 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 C53693A17EF for <cfrg@ietfa.amsl.com>; Thu, 25 Feb 2021 04:32:39 -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=zpEot6pq; dkim=pass (2048-bit key) header.d=messagingengine.com header.b=amf1VHEe
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 rVd7WpARbjvA for <cfrg@ietfa.amsl.com>; Thu, 25 Feb 2021 04:32:38 -0800 (PST)
Received: from out5-smtp.messagingengine.com (out5-smtp.messagingengine.com [66.111.4.29]) (using TLSv1.2 with cipher ADH-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 0448A3A16A7 for <cfrg@irtf.org>; Thu, 25 Feb 2021 04:32:37 -0800 (PST)
Received: from compute4.internal (compute4.nyi.internal [10.202.2.44]) by mailout.nyi.internal (Postfix) with ESMTP id CDA0F5C00FE; Thu, 25 Feb 2021 07:32:36 -0500 (EST)
Received: from imap4 ([10.202.2.54]) by compute4.internal (MEProxy); Thu, 25 Feb 2021 07:32:36 -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=SF ez/CCEQktGG4FXMvtpetRpg7EDYtcO0sO9QLwzYpY=; b=zpEot6pqCV8N7HtqjC Kfv/1zvopkIPr7iDsHw8H9vDiipxeQsD6u7xNGaf6xyaL5frkyS5BeI3WzlOqB8f OUkvmMWhxMUT1hG/0c0eg/CWzRnAgLcbanI42p87qnqRYzqAX9vM+UWtlYMjdAFP xftio9WqQg44TvNLAFM1Zv35pt6+VsyOyty3ChE+9uL1HJkWVHMa6ADqi3BvawrC Ujb8xCsTc/XaPFL8m+hLXi/et54AGR3OlopNox4tQtcFrpOTlTd32WbpBLPrbwo5 RmYpCT+fHmdiVZqIPpkFYEXxIzPISnGcjS4xoekr98dpXmZu1afsruBWG4HbtOL/ PomA==
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=SFez/CCEQktGG4FXMvtpetRpg7EDYtcO0sO9QLwzY pY=; b=amf1VHEedGDAmJEPZqUeHh4H22pORz7pNo+p+hydtiavJMbaSPuQGmFIg 9nn2d+w9F4//iUPQgRKEg3leCDi2peCJ9bUpiOybbNa3nrXIJGAzq2DoFw+jm5id JFUg39iwrAxgGrl0x+FHd1DKTwcDxeDFPKHNHv1WGmOl5BmmzWObrJ/OY5HqUipp 09cW3ZLRNE86LJGHRCCxQIZ+z4hmZQwUq+bvx3hGPWdPA0EfrnZ+sCDblXbZQoqL I+tBQgcCr6zYqUoJFKlpFx6Ojgz3s61n44YIaqvYj3tc3Lb7qALCZrXQ0XuSH+tn ULFPrSVX8HHHTyxQ28pBXA/naU6iQ==
X-ME-Sender: <xms:45g3YJdvJ0PDlOIAz4ZFZAbYDkVcsmjlPgnuvn0EadRTtMLPH9MLRg> <xme:45g3YHNJNh_YAhz8Q5zzvBvlag5rdcvIrQd3iucr_V_PJgyyRE0iCo7lEPyO88jbh 6Un_gjE3ZbubcTCtgw>
X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeduledrkeelgdegvdcutefuodetggdotefrodftvf curfhrohhfihhlvgemucfhrghsthforghilhdpqfgfvfdpuffrtefokffrpgfnqfghnecu uegrihhlohhuthemuceftddtnecusecvtfgvtghiphhivghnthhsucdlqddutddtmdenuc fjughrpefofgggkfgjfhffhffvufgtgfesthhqredtreerjeenucfhrhhomhepfdevhhhr ihhsthhophhhvghrucghohhougdfuceotggrfieshhgvrghpihhnghgsihhtshdrnhgvth eqnecuggftrfgrthhtvghrnhepteekudelvefhgeeigeetteejuefhueekueelkedtudei hfdtgfeghedttdevudelnecuffhomhgrihhnpehutggurghvihhsrdgvughupdhirggtrh drohhrghdpshhouhhrtggvfhhorhhgvgdrihhonecuvehluhhsthgvrhfuihiivgeptden ucfrrghrrghmpehmrghilhhfrhhomheptggrfieshhgvrghpihhnghgsihhtshdrnhgvth
X-ME-Proxy: <xmx:45g3YCjwfncQk0pEVy2H4nEudSVmmmeCjiGlN6hy63IOP9ebmZIa6A> <xmx:45g3YC-dk0YPfq4JQRamIntGrkgtP-ISJsLdTQR-WzTpUQLxdCu50A> <xmx:45g3YFvrqZH6nkwFB-snbAIAtv8v_nI-SrdEA0Y7HHit92tcgVTVUA> <xmx:5Jg3YD3qmvQvYbIAGrExptgB6iVKOfetYtOxRspzpFEkzh0k2OW7AQ>
Received: by mailuser.nyi.internal (Postfix, from userid 501) id E92AA1600AB; Thu, 25 Feb 2021 07:32:35 -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: <dd81152b-8007-4d3c-932c-db7b87fd759e@www.fastmail.com>
In-Reply-To: <A40CA8AA-CE6B-4361-9AF1-EEE0D927F97E@gnunet.org>
References: <44983891-284f-4552-b4c7-bc432148d214@www.fastmail.com> <19E2AA22-2B2B-4BCB-8171-B6386D39C616@gnunet.org> <c569e285-f592-45ed-9ce9-e68572b15b96@www.fastmail.com> <A40CA8AA-CE6B-4361-9AF1-EEE0D927F97E@gnunet.org>
Date: Thu, 25 Feb 2021 04:32:14 -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/wR8IojsOar_4SYZxTu7KufPkWhY>
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: Thu, 25 Feb 2021 12:32:40 -0000

On Wed, Feb 24, 2021, at 10:44 PM, Jeff Burdges wrote:
> 
> 
> > On 25 Feb 2021, at 00:25, Christopher Wood <caw@heapingbits.net> 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.  
> 
> 
> 
>