Re: [CFRG] RSA blind signatures

Jeff Burdges <burdges@gnunet.org> Thu, 25 February 2021 06:45 UTC

Return-Path: <burdges@gnunet.org>
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 6CAA43A1422 for <cfrg@ietfa.amsl.com>; Wed, 24 Feb 2021 22:45:06 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.897
X-Spam-Level:
X-Spam-Status: No, score=-1.897 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_MSPIKE_H3=0.001, RCVD_IN_MSPIKE_WL=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
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 jxaUeUDGcrtn for <cfrg@ietfa.amsl.com>; Wed, 24 Feb 2021 22:45:03 -0800 (PST)
Received: from mail-out2.informatik.tu-muenchen.de (mail-out2.in.tum.de [131.159.0.36]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 6C9563A1421 for <cfrg@irtf.org>; Wed, 24 Feb 2021 22:45:03 -0800 (PST)
Received: from [127.0.0.1] (sam.net.in.tum.de [IPv6:2001:4ca0:2001:42:225:90ff:fe6b:d60]) by sam.net.in.tum.de (Postfix) with ESMTP id 814301C00D2; Thu, 25 Feb 2021 07:46:11 +0100 (CET)
Content-Type: text/plain; charset=utf-8
Mime-Version: 1.0 (Mac OS X Mail 13.4 \(3608.120.23.2.4\))
From: Jeff Burdges <burdges@gnunet.org>
In-Reply-To: <c569e285-f592-45ed-9ce9-e68572b15b96@www.fastmail.com>
Date: Thu, 25 Feb 2021 07:44:54 +0100
Cc: IRTF CFRG <cfrg@irtf.org>, Taler <taler@gnu.org>
Content-Transfer-Encoding: quoted-printable
Message-Id: <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>
To: Christopher Wood <caw@heapingbits.net>
X-Mailer: Apple Mail (2.3608.120.23.2.4)
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/KWB-38YTFwjcMQ9ww41Xcx064rw>
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 06:45:06 -0000


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

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

> 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? 

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.