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

Jeff Burdges <burdges@gnunet.org> Thu, 29 April 2021 15:18 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 BA22B3A28B0 for <cfrg@ietfa.amsl.com>; Thu, 29 Apr 2021 08:18:36 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.232
X-Spam-Level:
X-Spam-Status: No, score=-1.232 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_BLOCKED=0.001, SPF_HELO_NONE=0.001, SPF_SOFTFAIL=0.665, URIBL_BLOCKED=0.001] autolearn=no 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 MDubHfm0Ty9G for <cfrg@ietfa.amsl.com>; Thu, 29 Apr 2021 08:18:32 -0700 (PDT)
Received: from vimdzmsp-nwas02.bluewin.ch (vimdzmsp-nwas02.bluewin.ch [195.186.228.50]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 07E0F3A28B7 for <cfrg@irtf.org>; Thu, 29 Apr 2021 08:18:31 -0700 (PDT)
Received: from [127.0.0.1] ([188.62.197.203]) by vimdzmsp-nwas02.bluewin.ch Swisscom AG with ESMTP id c8QplIklj4ojnc8Qulqk4F; Thu, 29 Apr 2021 17:18:28 +0200
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: <608A3846.5010206@gmail.com>
Date: Thu, 29 Apr 2021 17:18:22 +0200
Cc: Taler <taler@gnu.org>, CFRG <cfrg@irtf.org>
Content-Transfer-Encoding: quoted-printable
Message-Id: <CB8C5773-6D34-4662-AA62-6623CF22727C@gnunet.org>
References: <CAMr0u6njjMkmmAhFg3t+0EJOuh=q4towqi4j=hk9-russTbXDA@mail.gmail.com> <74CC6D18-B7B0-4FF8-A227-463434C250C9@gnunet.org> <20210428123303.efzpnhpqkcmg7op3@muon> <608A3846.5010206@gmail.com>
To: jcb62281@gmail.com
X-Mailer: Apple Mail (2.3608.120.23.2.4)
X-CMAE-Envelope: MS4xfE3n2/Vy5YZ5OKNciezhu4DWSBcyx33BPe6tMEcfcbEw5WGAhHLG4X5DWKQbuCdkGJEEPXepOS1iYwx9W07u83d837fZp4wZZKK3go7g0R5HTJfyANkf E2WtvjeEg2kcz9oSd2VtEKbqwZsuIEUKJij2wQpNspV63teG1su6URvITSAJvVmDqjnYa6t7sHI+fQzgtqhJ5dYi/oh8vRTjVRkgvO5hgQdmKHQQez9T5jiF
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/xNxwr5sTD_x5FF2fIniLTN7pp7g>
Subject: Re: [CFRG] [Taler] Call for adoption for draft-wood-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, 29 Apr 2021 15:18:37 -0000


> On 29 Apr 2021, at 06:38, Jacob Bachmeyer <jcb62281@gmail.com> 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