[bitcoin-dev] BIP 340 updates: even pubkeys, more secure nonce generation

[bitcoin-dev] BIP 340 updates: even pubkeys, more secure nonce generation

[Pieter Wuille]

Hello list,

Despite saying earlier that I expected no further semantical changes
to BIP 340-342, I've just opened
https://github.com/bitcoin/bips/pull/893 to make a number of small
changes that I believe are still worth making.

1. Even public keys

Only one change affects the validation rules: the Y coordinate of
32-byte public keys is changed from implicitly square to implicitly
even. This makes signing slightly faster (in the microsecond range),
though also verification negligibly slower (in the nanosecond range).
It also simplifies integration with existing key generation
infrastructure. For example BIP32 produces public keys with known
even/oddness, but squaredness would need to be computed separately.
Similar arguments hold for PSBT and probably many other things.

Note that the Y coordinate of the internal R point in the signature
remains implicitly square: for R the squaredness gives an actual
performance gain at validation time, but this is not true for public
keys. Conversely, for public keys integration with existing
infrastructure matters, but R points are purely internal.

This affects BIP 340 and 341.

2. Nonce generation

All other semantical changes are around more secure nonce generation
in BIP 340, dealing with various failure cases:

* Since the public key signed for is included in the signature
challenge hash, implementers will likely be eager to use precomputed
values for these (otherwise an additional EC multiplication is
necessary at signing time). If that public key data happens to be
gathered from untrusted sources, it can lead to trivial leakage of the
private key - something that Greg Maxwell started a discussion about
on the moderncrypto curves list:
https://moderncrypto.org/mail-archive/curves/2020/001012.html. We
believe it should therefore be best practice to include the public key
also in the nonce generation, which largely mitigates this problem.

* To protect against fault injection attacks it is recommended to
include actual signing-time randomness into the nonce generation
process. This was mentioned already, but the update elaborates much
more about this, and integrates this randomness into the standard
signing process.

* To protect against differential power analysis, a different way of
mixing in this randomness is used (masking the private key completely
with randomness before continuing, rather than hashing them together,
which is known in the literature to be vulnerable to DPA in some
scenarios).

3. New tagged hash tags

To make sure that any code written for the earlier BIP text fails
consistently, the tags used in the tagged hashes in BIP 340 are
changed as well.

What do people think?

-- 
Pieter

[bitcoin-dev] Fwd: BIP 340 updates: even pubkeys, more secure nonce generation

[Russell O'Connor]

[-- Attachment #1: Type: text/plain, Size: 2058 bytes --]

On Sun, Feb 23, 2020 at 11:26 PM Pieter Wuille via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

>
> 2. Nonce generation
>
> All other semantical changes are around more secure nonce generation
> in BIP 340, dealing with various failure cases:
>
> * To protect against fault injection attacks it is recommended to
> include actual signing-time randomness into the nonce generation
> process. This was mentioned already, but the update elaborates much
> more about this, and integrates this randomness into the standard
> signing process.
>

I do worry that standardizing on a non-deterministic nonce generation
scheme makes the problem of private key exfiltration a much bigger concern
in the application of hardware signing devices.
While sorely imperfect, with a deterministic nonce scheme, we at least have
the option of spot checking hardware devices to see if they are producing
signatures in accordance with their specified nonce scheme.  But short of
providing some kind of certificate, we won't be able to do such checks
against hardware devices that use the proposed synthetic nonce. (Question:
can a hardware device safely output the random value 'a' it used its
"certificate"?  AFAIU 'a' is not considered secret data; it just needs to
be not under attacker control.  Should hardware wallets be encouraged to
return this value?)

The best way to mitigate this is to use the Nonce exfiltration protection
mentioned; however there are no references on how to do this.  Ideally we'd
standardize this Nonce exfiltration protection scheme within this synthetic
nonce scheme.  However, I don't think it is worth holding this BIP up on
that; it seems reasonable to introduce a new section to this BIP addressing
that problem in the future.  Maybe instead we can get references to more
information about this Nonce exfiltration protection that is mentioned?

Really I just want to do whatever we reasonably can do to avoid a world
where we end up providing hardware signing devices with a hard to detect
underhanded communications channel.

[-- Attachment #2: Type: text/html, Size: 2544 bytes --]

Re: [bitcoin-dev] BIP 340 updates: even pubkeys, more secure nonce generation

[Lloyd Fournier]

[-- Attachment #1: Type: text/plain, Size: 4813 bytes --]

Hi Pieter,

Let me put change (1) into my own words. We are already computing affine
coordinates since we store public keys as the affine x-coordinate. It is
faster to compute is_even(y) than is_quadratic_residue(y) so we get a speed
up here during keypair generation. In the verification algorithm, we do the
following for the public key  x_only => affine + negate if not is_even(y)
=> jacobian. The minor slowdown in verification comes from the extra
evenness check and possible negation which we didn't have to be done in the
previous version. This seems like a reasonable change if it makes things
easier for existing code bases and infrastructure.

With change (2), I feel like including this auxiliary random data is
overkill for the spec. For me, the main point of the spec is the
verification algorithm which actually affects consensus. Providing a note
that non-deterministic signatures are preferable in many cases and here's
exactly how you should do that (hash then xor with private key) is
valuable. In the end, people will want several variations of the signing
algorithm anyway (e.g. pass in public key with secret key) so I think
specifying the most minimal way to produce a signature securely is the most
useful thing for this document.

I feel similarly about hashing the public key to get the nonce. A note in
the alternative signing section that "if you pass the public key into
`sign` along with the secret key then you should do hash(bytes(d) ||
bytes(P) || m)" would suffice for me.

Despite only being included in the alternative signing section, I it would
be nice to have a few of test vectors for these alternative methods anyway.
Perhaps they even deserve their own BIP?

Cheers,

LL


On Mon, Feb 24, 2020 at 3:26 PM Pieter Wuille via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Hello list,
>
> Despite saying earlier that I expected no further semantical changes
> to BIP 340-342, I've just opened
> https://github.com/bitcoin/bips/pull/893 to make a number of small
> changes that I believe are still worth making.
>
> 1. Even public keys
>
> Only one change affects the validation rules: the Y coordinate of
> 32-byte public keys is changed from implicitly square to implicitly
> even. This makes signing slightly faster (in the microsecond range),
> though also verification negligibly slower (in the nanosecond range).
> It also simplifies integration with existing key generation
> infrastructure. For example BIP32 produces public keys with known
> even/oddness, but squaredness would need to be computed separately.
> Similar arguments hold for PSBT and probably many other things.
>
> Note that the Y coordinate of the internal R point in the signature
> remains implicitly square: for R the squaredness gives an actual
> performance gain at validation time, but this is not true for public
> keys. Conversely, for public keys integration with existing
> infrastructure matters, but R points are purely internal.
>
> This affects BIP 340 and 341.
>
> 2. Nonce generation
>
> All other semantical changes are around more secure nonce generation
> in BIP 340, dealing with various failure cases:
>
> * Since the public key signed for is included in the signature
> challenge hash, implementers will likely be eager to use precomputed
> values for these (otherwise an additional EC multiplication is
> necessary at signing time). If that public key data happens to be
> gathered from untrusted sources, it can lead to trivial leakage of the
> private key - something that Greg Maxwell started a discussion about
> on the moderncrypto curves list:
> https://moderncrypto.org/mail-archive/curves/2020/001012.html. We
> believe it should therefore be best practice to include the public key
> also in the nonce generation, which largely mitigates this problem.
>
> * To protect against fault injection attacks it is recommended to
> include actual signing-time randomness into the nonce generation
> process. This was mentioned already, but the update elaborates much
> more about this, and integrates this randomness into the standard
> signing process.
>
> * To protect against differential power analysis, a different way of
> mixing in this randomness is used (masking the private key completely
> with randomness before continuing, rather than hashing them together,
> which is known in the literature to be vulnerable to DPA in some
> scenarios).
>
> 3. New tagged hash tags
>
> To make sure that any code written for the earlier BIP text fails
> consistently, the tags used in the tagged hashes in BIP 340 are
> changed as well.
>
> What do people think?
>
> --
> Pieter
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

[-- Attachment #2: Type: text/html, Size: 5910 bytes --]

Re: [bitcoin-dev] BIP 340 updates: even pubkeys, more secure nonce generation

[Jonas Nick]

> Let me put change (1) into my own words.

Correct, except that the speedup from is_even(y) over is_quadratic_residue(y)
affects signing and not keypair generation.

> With change (2), I feel like including this auxiliary random data is overkill
> for the spec. [...] I feel similarly about hashing the public key to get the
> nonce.

It's not clear why removing these features from the spec would be an improvement.
The BIP follows a more reasonable approach: it specifies a reasonably secure
signing algorithm and provides the rationale behind the design choices. This
allows anyone to optimize for their use case if they choose to do so.
Importantly, "reasonably secure" includes misuse resistance which would be
violated if the pubkey was not input to the nonce generation function.

> Perhaps they even deserve their own BIP?

Yes, a standard for nonce exfiltration protection and MuSig would be important
for compatibility across wallets.


On 2/26/20 4:20 AM, Lloyd Fournier via bitcoin-dev wrote:
> Hi Pieter,
> 
> Let me put change (1) into my own words. We are already computing affine
> coordinates since we store public keys as the affine x-coordinate. It is
> faster to compute is_even(y) than is_quadratic_residue(y) so we get a speed
> up here during keypair generation. In the verification algorithm, we do the
> following for the public key  x_only => affine + negate if not is_even(y)
> => jacobian. The minor slowdown in verification comes from the extra
> evenness check and possible negation which we didn't have to be done in the
> previous version. This seems like a reasonable change if it makes things
> easier for existing code bases and infrastructure.
> 
> With change (2), I feel like including this auxiliary random data is
> overkill for the spec. For me, the main point of the spec is the
> verification algorithm which actually affects consensus. Providing a note
> that non-deterministic signatures are preferable in many cases and here's
> exactly how you should do that (hash then xor with private key) is
> valuable. In the end, people will want several variations of the signing
> algorithm anyway (e.g. pass in public key with secret key) so I think
> specifying the most minimal way to produce a signature securely is the most
> useful thing for this document.
> 
> I feel similarly about hashing the public key to get the nonce. A note in
> the alternative signing section that "if you pass the public key into
> `sign` along with the secret key then you should do hash(bytes(d) ||
> bytes(P) || m)" would suffice for me.
> 
> Despite only being included in the alternative signing section, I it would
> be nice to have a few of test vectors for these alternative methods anyway.
> Perhaps they even deserve their own BIP?
> 
> Cheers,
> 
> LL
> 
> 
> On Mon, Feb 24, 2020 at 3:26 PM Pieter Wuille via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
> 
>> Hello list,
>>
>> Despite saying earlier that I expected no further semantical changes
>> to BIP 340-342, I've just opened
>> https://github.com/bitcoin/bips/pull/893 to make a number of small
>> changes that I believe are still worth making.
>>
>> 1. Even public keys
>>
>> Only one change affects the validation rules: the Y coordinate of
>> 32-byte public keys is changed from implicitly square to implicitly
>> even. This makes signing slightly faster (in the microsecond range),
>> though also verification negligibly slower (in the nanosecond range).
>> It also simplifies integration with existing key generation
>> infrastructure. For example BIP32 produces public keys with known
>> even/oddness, but squaredness would need to be computed separately.
>> Similar arguments hold for PSBT and probably many other things.
>>
>> Note that the Y coordinate of the internal R point in the signature
>> remains implicitly square: for R the squaredness gives an actual
>> performance gain at validation time, but this is not true for public
>> keys. Conversely, for public keys integration with existing
>> infrastructure matters, but R points are purely internal.
>>
>> This affects BIP 340 and 341.
>>
>> 2. Nonce generation
>>
>> All other semantical changes are around more secure nonce generation
>> in BIP 340, dealing with various failure cases:
>>
>> * Since the public key signed for is included in the signature
>> challenge hash, implementers will likely be eager to use precomputed
>> values for these (otherwise an additional EC multiplication is
>> necessary at signing time). If that public key data happens to be
>> gathered from untrusted sources, it can lead to trivial leakage of the
>> private key - something that Greg Maxwell started a discussion about
>> on the moderncrypto curves list:
>> https://moderncrypto.org/mail-archive/curves/2020/001012.html. We
>> believe it should therefore be best practice to include the public key
>> also in the nonce generation, which largely mitigates this problem.
>>
>> * To protect against fault injection attacks it is recommended to
>> include actual signing-time randomness into the nonce generation
>> process. This was mentioned already, but the update elaborates much
>> more about this, and integrates this randomness into the standard
>> signing process.
>>
>> * To protect against differential power analysis, a different way of
>> mixing in this randomness is used (masking the private key completely
>> with randomness before continuing, rather than hashing them together,
>> which is known in the literature to be vulnerable to DPA in some
>> scenarios).
>>
>> 3. New tagged hash tags
>>
>> To make sure that any code written for the earlier BIP text fails
>> consistently, the tags used in the tagged hashes in BIP 340 are
>> changed as well.
>>
>> What do people think?
>>
>> --
>> Pieter
>> _______________________________________________
>> bitcoin-dev mailing list
>> bitcoin-dev@lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>>
> 
> 
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> 

Re: [bitcoin-dev] BIP 340 updates: even pubkeys, more secure nonce generation

[Lloyd Fournier]

[-- Attachment #1: Type: text/plain, Size: 7307 bytes --]

> Correct, except that the speedup from is_even(y) over
is_quadratic_residue(y) affects signing and not keypair generation.

Isn't this the same thing since in the spec it generates the public key in
the signing algorithm? If you pre-generate public key and pass it in there
would be no speedup to signing that I can see.

> It's not clear why removing these features from the spec would be an
improvement.

It could just be me but "here's the most minimal signing algorithm, you can
add things in these ways to make it more robust  in some settings" is more
intuitive than "here's the most robust signing algorithm, you can remove
these things in these ways if they don't apply to your setting". I see your
point that if it is likely to be misused then maybe the latter is
preferable.

LL

On Thu, Feb 27, 2020 at 2:33 AM Jonas Nick <jonasdnick@gmail.com> wrote:

> > Let me put change (1) into my own words.
>
> Correct, except that the speedup from is_even(y) over
> is_quadratic_residue(y)
> affects signing and not keypair generation.
>
> > With change (2), I feel like including this auxiliary random data is
> overkill
> > for the spec. [...] I feel similarly about hashing the public key to get
> the
> > nonce.
>
> It's not clear why removing these features from the spec would be an
> improvement.
> The BIP follows a more reasonable approach: it specifies a reasonably
> secure
> signing algorithm and provides the rationale behind the design choices.
> This
> allows anyone to optimize for their use case if they choose to do so.
> Importantly, "reasonably secure" includes misuse resistance which would be
> violated if the pubkey was not input to the nonce generation function.
>
> > Perhaps they even deserve their own BIP?
>
> Yes, a standard for nonce exfiltration protection and MuSig would be
> important
> for compatibility across wallets.
>
>
> On 2/26/20 4:20 AM, Lloyd Fournier via bitcoin-dev wrote:
> > Hi Pieter,
> >
> > Let me put change (1) into my own words. We are already computing affine
> > coordinates since we store public keys as the affine x-coordinate. It is
> > faster to compute is_even(y) than is_quadratic_residue(y) so we get a
> speed
> > up here during keypair generation. In the verification algorithm, we do
> the
> > following for the public key  x_only => affine + negate if not is_even(y)
> > => jacobian. The minor slowdown in verification comes from the extra
> > evenness check and possible negation which we didn't have to be done in
> the
> > previous version. This seems like a reasonable change if it makes things
> > easier for existing code bases and infrastructure.
> >
> > With change (2), I feel like including this auxiliary random data is
> > overkill for the spec. For me, the main point of the spec is the
> > verification algorithm which actually affects consensus. Providing a note
> > that non-deterministic signatures are preferable in many cases and here's
> > exactly how you should do that (hash then xor with private key) is
> > valuable. In the end, people will want several variations of the signing
> > algorithm anyway (e.g. pass in public key with secret key) so I think
> > specifying the most minimal way to produce a signature securely is the
> most
> > useful thing for this document.
> >
> > I feel similarly about hashing the public key to get the nonce. A note in
> > the alternative signing section that "if you pass the public key into
> > `sign` along with the secret key then you should do hash(bytes(d) ||
> > bytes(P) || m)" would suffice for me.
> >
> > Despite only being included in the alternative signing section, I it
> would
> > be nice to have a few of test vectors for these alternative methods
> anyway.
> > Perhaps they even deserve their own BIP?
> >
> > Cheers,
> >
> > LL
> >
> >
> > On Mon, Feb 24, 2020 at 3:26 PM Pieter Wuille via bitcoin-dev <
> > bitcoin-dev@lists.linuxfoundation.org> wrote:
> >
> >> Hello list,
> >>
> >> Despite saying earlier that I expected no further semantical changes
> >> to BIP 340-342, I've just opened
> >> https://github.com/bitcoin/bips/pull/893 to make a number of small
> >> changes that I believe are still worth making.
> >>
> >> 1. Even public keys
> >>
> >> Only one change affects the validation rules: the Y coordinate of
> >> 32-byte public keys is changed from implicitly square to implicitly
> >> even. This makes signing slightly faster (in the microsecond range),
> >> though also verification negligibly slower (in the nanosecond range).
> >> It also simplifies integration with existing key generation
> >> infrastructure. For example BIP32 produces public keys with known
> >> even/oddness, but squaredness would need to be computed separately.
> >> Similar arguments hold for PSBT and probably many other things.
> >>
> >> Note that the Y coordinate of the internal R point in the signature
> >> remains implicitly square: for R the squaredness gives an actual
> >> performance gain at validation time, but this is not true for public
> >> keys. Conversely, for public keys integration with existing
> >> infrastructure matters, but R points are purely internal.
> >>
> >> This affects BIP 340 and 341.
> >>
> >> 2. Nonce generation
> >>
> >> All other semantical changes are around more secure nonce generation
> >> in BIP 340, dealing with various failure cases:
> >>
> >> * Since the public key signed for is included in the signature
> >> challenge hash, implementers will likely be eager to use precomputed
> >> values for these (otherwise an additional EC multiplication is
> >> necessary at signing time). If that public key data happens to be
> >> gathered from untrusted sources, it can lead to trivial leakage of the
> >> private key - something that Greg Maxwell started a discussion about
> >> on the moderncrypto curves list:
> >> https://moderncrypto.org/mail-archive/curves/2020/001012.html. We
> >> believe it should therefore be best practice to include the public key
> >> also in the nonce generation, which largely mitigates this problem.
> >>
> >> * To protect against fault injection attacks it is recommended to
> >> include actual signing-time randomness into the nonce generation
> >> process. This was mentioned already, but the update elaborates much
> >> more about this, and integrates this randomness into the standard
> >> signing process.
> >>
> >> * To protect against differential power analysis, a different way of
> >> mixing in this randomness is used (masking the private key completely
> >> with randomness before continuing, rather than hashing them together,
> >> which is known in the literature to be vulnerable to DPA in some
> >> scenarios).
> >>
> >> 3. New tagged hash tags
> >>
> >> To make sure that any code written for the earlier BIP text fails
> >> consistently, the tags used in the tagged hashes in BIP 340 are
> >> changed as well.
> >>
> >> What do people think?
> >>
> >> --
> >> Pieter
> >> _______________________________________________
> >> bitcoin-dev mailing list
> >> bitcoin-dev@lists.linuxfoundation.org
> >> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> >>
> >
> >
> > _______________________________________________
> > bitcoin-dev mailing list
> > bitcoin-dev@lists.linuxfoundation.org
> > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> >
>

[-- Attachment #2: Type: text/html, Size: 9442 bytes --]

Re: [bitcoin-dev] BIP 340 updates: even pubkeys, more secure nonce generation

[Lloyd Fournier]

[-- Attachment #1: Type: text/plain, Size: 795 bytes --]

* To protect against differential power analysis, a different way of
> mixing in this randomness is used (masking the private key completely
> with randomness before continuing, rather than hashing them together,
> which is known in the literature to be vulnerable to DPA in some
> scenarios).
>

I think citation for this would improve the spec.

I haven't studied these attacks but it seems to me that every hardware
wallet would be vulnerable to them while doing key derivation. If the
attacker can get side channel information from hashes in nonce derivation
then they can surely get side channel information from hashes in HD key
derivation. It should actually be easier since the master seed is hashed
for anything the hardware device needs to do including signing.

is this the case?

LL

[-- Attachment #2: Type: text/html, Size: 1126 bytes --]

Re: [bitcoin-dev] Fwd: BIP 340 updates: even pubkeys, more secure nonce generation

[Marko]

That is an interesting point. Does the same concern apply to anti nonce
covert channel protocols? In those, the host would mix in a random nonce
of its own. The process is still deterministic and can be checked during
signing, but unless the host persists the nonce contributions it
provides, one can't check how the nonce was computed for past
signatures. I am unsure how desirable this property would be in
practice, though. I am guessing not that desirable, but it would be good
to hear other opinions.

See

https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-February/017655.html


and

https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-February/017663.html

Best, Marko