From: "Russell O'Connor" <roconnor@blockstream•io>
To: Gregory Maxwell <greg@xiph•org>
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists•linuxfoundation.org>
Subject: Re: [bitcoin-dev] Schnorr signatures BIP
Date: Sun, 8 Jul 2018 10:36:16 -0400 [thread overview]
Message-ID: <CAMZUoKnCkUybwMh_X3GksDW-zJ0NtfUsqfxC2sRgxpNiHFpBTQ@mail.gmail.com> (raw)
In-Reply-To: <CAAS2fgTM+8mORcgjGdQxGxMkXjW7NOqByZwD1_VEad80ofVObA@mail.gmail.com>
[-- Attachment #1: Type: text/plain, Size: 3707 bytes --]
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 bitcoin-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
> 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.]
>
[-- Attachment #2: Type: text/html, Size: 4672 bytes --]
next prev parent reply other threads:[~2018-07-08 14:36 UTC|newest]
Thread overview: 31+ messages / expand[flat|nested] mbox.gz Atom feed top
2018-07-06 18:08 Pieter Wuille
2018-07-06 21:05 ` Russell O'Connor
2018-07-06 22:00 ` Gregory Maxwell
2018-07-06 22:01 ` Gregory Maxwell
2018-07-08 14:36 ` Russell O'Connor [this message]
2018-07-14 15:42 ` Sjors Provoost
2018-07-14 21:20 ` Pieter Wuille
2018-08-04 12:22 ` Russell O'Connor
2018-08-05 14:33 ` Russell O'Connor
2018-08-06 8:39 ` Anthony Towns
2018-08-06 14:00 ` Russell O'Connor
2018-08-06 21:12 ` Tim Ruffing
2018-08-12 16:37 ` Andrew Poelstra
2018-08-29 12:09 ` Erik Aronesty
2018-09-03 0:05 ` Andrew Poelstra
2018-09-05 12:26 ` Erik Aronesty
2018-09-05 13:05 ` Andrew Poelstra
2018-09-05 13:14 ` Erik Aronesty
2018-09-05 15:35 ` Gregory Maxwell
2018-09-11 16:34 ` Erik Aronesty
2018-09-11 17:00 ` Gregory Maxwell
2018-09-11 17:20 ` Erik Aronesty
2018-09-11 17:27 ` Gregory Maxwell
2018-09-11 17:37 ` Erik Aronesty
2018-09-11 17:51 ` Gregory Maxwell
2018-09-11 18:30 ` Erik Aronesty
2018-09-13 18:46 ` Andrew Poelstra
2018-09-13 20:20 ` Erik Aronesty
2018-09-14 14:38 ` Andrew Poelstra
2018-09-20 21:12 ` Russell O'Connor
2018-07-07 2:47 Артём Литвинович
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=CAMZUoKnCkUybwMh_X3GksDW-zJ0NtfUsqfxC2sRgxpNiHFpBTQ@mail.gmail.com \
--to=roconnor@blockstream$(echo .)io \
--cc=bitcoin-dev@lists$(echo .)linuxfoundation.org \
--cc=greg@xiph$(echo .)org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox