Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 25A16CFF for ; Sun, 8 Jul 2018 14:36:30 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-it0-f51.google.com (mail-it0-f51.google.com [209.85.214.51]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 5BEBEFC for ; Sun, 8 Jul 2018 14:36:29 +0000 (UTC) Received: by mail-it0-f51.google.com with SMTP id 188-v6so23130152ita.5 for ; Sun, 08 Jul 2018 07:36:29 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=blockstream.io; s=google; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=8bYjBPlFhYSokhUNeWnBLn7uHM1NN2NLLQc56TCn2as=; b=Dug/k8fD5B68Fhz9/IrtwDDmdQoAjvT3r+U5xsPv9UU5c/WyEvr5wbeIHqmrefR2Ps Na4ccg9hENEI66+aP5dttEojsKgsh9pvNFy4ycuH/XrROngCv1EmRxBckKQFXILgS5Jz jWsOv5asQwW6zeg6ZONw3YDHGpaztonoL5T4Y= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=8bYjBPlFhYSokhUNeWnBLn7uHM1NN2NLLQc56TCn2as=; b=UimvbNkwOTuFdkFIloDIlMdofPzEG7ELnvNS4AgpfFA5BinrnmWXBS1B2O8JPLFk+v KO18HR/KXhO5yFkebZnbCfbClKb/FOnBzTofvf/2QSB9xa4e5FvDNvBJbJzuhK+X0U7v uf7uGL/F0wDOjAeCmjdYuz7IeCGBwo6U9i5GkXB1mVCBI+ENho8OTzxrSCSOJDKRwhoi SIyEKHmUkREUKvOvEW9/BQ7RmZsWWbuyq7Vu6J0lPzei69At3icwK9xacK2MzMvwFnuy Z6utxAmf4lflrs7Y2t8rBX8YA4VAGi5iUMIh4IxVNx79ysSQWLOhNcOqNmh/gwi6W2UN RKIQ== X-Gm-Message-State: APt69E2bOVdz1gUxltAnF8xQB3dLuIbTB0Gph5q4IIao1Np9p2k9DFr6 617ZOSaq2durow/I1RLJ1FvhqBZGfUwuQIYf2xx52LHW X-Google-Smtp-Source: AAOMgpdA+kUv4GUyvsRtyxt81l9eFVfy8x2Fbr8iEvAWycIhM/N0cxxd7L98xeTsSNzbZ0rQS+fzTyU7hbTep1/PoOw= X-Received: by 2002:a24:7b97:: with SMTP id q145-v6mr13389868itc.79.1531060588649; Sun, 08 Jul 2018 07:36:28 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: From: "Russell O'Connor" Date: Sun, 8 Jul 2018 10:36:16 -0400 Message-ID: To: Gregory Maxwell Content-Type: multipart/alternative; boundary="00000000000084362d05707dd298" X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, HTML_MESSAGE, RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org Cc: Bitcoin Protocol Discussion Subject: Re: [bitcoin-dev] Schnorr signatures BIP X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 08 Jul 2018 14:36:30 -0000 --00000000000084362d05707dd298 Content-Type: text/plain; charset="UTF-8" On Fri, Jul 6, 2018 at 6:00 PM, Gregory Maxwell wrote: > On Fri, Jul 6, 2018 at 9:05 PM, Russell O'Connor via bitcoin-dev > wrote: > > If the inputs to hash were reordered as hash(bytes(dG) || bytes(x(R)) || > m) > > then there is an opportunity for SHA256 expander to be partially > prefilled > > for a fixed public key. This could provide a little benefit, especially > > when multiple signatures for a single public key need to be generated > and/or > > verified. If all things are otherwise equal, perhaps this alternate > order > > is better. > > There is a minor design preference to have message before nonce when > H() is a MD-style hash function. Say the attacker knows some weakness > in H and can find pairs of messages m and m' so that the compression > function results in the same midstate. He could then ask you to sign > m but get a signature that also works for m'. If the signer > controlled R value comes first, then this doesn't work. The pubkey > being where it is in the current design just follows from the idea > that it is just logically prepended on the message. I don't think the > pubkey is sufficiently attacker controlled that the above argument > would apply, so H(P || R.x || m) would be okay. > > BUT, the sha256 compression function reads 64 bytes at a time. PRM > would not let you precompute a whole compression function run, but > instead would just let you hardwire part of the expander in a pubkey > dependant way-- an optimization I'm pretty confident virtually no one > would use. (Hardwiring to a constant, yes. Hardwiring to a reused > dynamic value that comes in from the network, no) > Right. I readily admit my proposal has extremely marginal efficiency benefits. However, I didn't realize there is also an extremely marginal security benefit to placing the nonce in front of everything. Although these things are so marginal that it is perhaps a waste of time to even be considering them, I think I'd judge the extremely marginal security benefit to exceed the value of the extremely marginal efficiency gain. It's probably best to leave the nonce at the beginning after all. > If instead the hash function were defined as using 31 zeros then > P||R||m (or P || 31 zeros bytes || R || m, I'm not sure what would be > better), an entire midstate could be cached for different pubkeys. m > is often 32 bytes, sadly- - but the final compression run in that case > would only be the constant update with the length.... and > almost-all-zeros + constant length, is an easy optimization. (Bitcoin > core even has it for computing sha256(sha256())). > I did consider this, however the 31 bytes of zeros, plus the SHA256 padding means we would need to compress *three* blocks in general instead of the current proposal of just two blocks. This burden seems to exceed the benefit of maybe sometimes getting a slightly fast two-blocks-with-lots-of-zeros when public keys are reused. I wouldn't recommend it. There is an alternative of just dropping the SHA-256 length padding. This would still be secure in this context because the data is of fixed size. However, I doubt it is worth breaking the API of every SHA-256 library in existence to enable that. > [I'm not really sure if I was clear, so I'll try TLDRing it: I think > optimizing sha256 where part of the input is constant is realistic, > optimizing midstate reuse is realistic, optimizing where part is > reused is less realistic. If we insert padding, and put P first, we > can make it possible to midstate cache P, and the 'extra' compression > function run ends up with all constant input, so it could be made > faster.] > --00000000000084362d05707dd298 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable


On Fri, Jul 6, 2018 at 6:00 PM, Gregory Maxwell <greg@xiph.org> wrote:
On Fri, Jul 6, 2018 at 9:05 PM, Russell O'Connor via bitco= in-dev
<bitcoin-dev@lists.linuxfoundation.org> wrote:=
> If the inputs to hash were reordered as hash(bytes(dG) || bytes(x(R)) = || m)
> then there is an opportunity for SHA256 expander to be partially prefi= lled
> for a fixed public key.=C2=A0 This could provide a little benefit, esp= ecially
> when multiple signatures for a single public key need to be generated = and/or
> verified.=C2=A0 If all things are otherwise equal, perhaps this altern= ate order
> is better.

There is a minor design preference to have message before nonce when=
H() is a MD-style hash function.=C2=A0 Say the attacker knows some weakness=
in H and can find pairs of messages m and m' so that the compression function results in the same midstate.=C2=A0 He could then ask you to sign<= br> m but get a signature that also works for m'.=C2=A0 =C2=A0If the signer=
controlled R value comes first, then this doesn't work.=C2=A0 =C2=A0 Th= e pubkey
being where it is in the current design just follows from the idea
that it is just logically prepended on the message.=C2=A0 I don't think= the
pubkey is sufficiently attacker controlled that the above argument
would apply,=C2=A0 so H(P || R.x || m) would be okay.

BUT, the sha256 compression function reads 64 bytes at a time. PRM
would not let you precompute a whole compression function run, but
instead would just let you hardwire part of the expander in a pubkey
dependant way-- an optimization I'm pretty confident virtually no one would use.=C2=A0 (Hardwiring to a constant, yes. Hardwiring to a reused
dynamic value that comes in from the network, no)

=
Right.=C2=A0 I readily admit my proposal has extremely marginal = efficiency benefits. However, I didn't realize there is also an extreme= ly marginal security benefit to placing the nonce in front of everything.= =C2=A0 Although these things are so marginal that it is perhaps a waste of = time to even be considering them, I think I'd judge the extremely margi= nal security benefit to exceed the value of the extremely marginal efficien= cy gain.=C2=A0 It's probably best to leave the nonce at the beginning a= fter all.
=C2=A0
If instead the hash function were defined as using 31 zeros then
P||R||m (or P || 31 zeros bytes || R || m, I'm not sure what would be better), an entire midstate could be cached for different pubkeys. m
is often 32 bytes, sadly- - but the final compression run in that case
would only be the constant update with the length.... and
almost-all-zeros + constant length, is an easy optimization. (Bitcoin
core even has it for computing sha256(sha256())).

=
I did consider this, however the 31 bytes of zeros, plus the SHA= 256 padding means we would need to compress *three* blocks in general inste= ad of the current proposal of just two blocks.=C2=A0 This burden seems to e= xceed the benefit of maybe sometimes getting a slightly fast two-blocks-wit= h-lots-of-zeros when public keys are reused. I wouldn't recommend it.
There is an alternative of just dropping the SHA-256 length padding.= =C2=A0 This would still be secure in this context because the data is of fi= xed size.=C2=A0 However, I doubt it is worth breaking the API of every SHA-= 256 library in existence to enable that.
=C2=A0
[I'm not really sure if I was clear, so I'll try TLDRing it:=C2=A0 = I think
optimizing sha256 where part of the input is constant is realistic,
optimizing midstate reuse is realistic, optimizing where part is
reused is less realistic.=C2=A0 If we insert padding, and put P first, we can make it possible to midstate cache P,=C2=A0 and the 'extra' com= pression
function run ends up with all constant input, so it could be made
faster.]

--00000000000084362d05707dd298--