Re: [bitcoin-dev] RFC: Kicking BIP-322 (message signing) into motion

[Karl-Johan Alm via bitcoin-dev]

Hello,

I propose simplifying BIP-322 down to the single-proof case, and
removing some abstractions (e.g. the "actions"/"purposes" stuff):
https://github.com/bitcoin/bips/pull/903

Feedback welcome.

New version below:
```

BIP: 322
Layer: Applications
Title: Generic Signed Message Format
Author: Karl-Johan Alm 
Comments-Summary: No comments yet.
Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-0322
Status: Draft
Type: Standards Track
Created: 2018-09-10
License: CC0-1.0


== Abstract ==

A standard for interoperable generic signed messages based on the
Bitcoin Script format.

== Background ==

* Assume two actors, a prover P and a verifier V.
* P wants to prove that they own the private key
k associated with a given address A (which
in turn is derived from the pubkey kG).
* Let V generate a message M and hand this
to P.
* P generates a signature S by signing the
message M using k. Given S,
V can prove that P has the private key
associated with A.

The astute reader will notice that the above is missing a critical
part, namely the pubkey kG, without which the verifier
cannot actually verify the message. The current message signing
standard solves this via a cryptographic trick, wherein the signature
S above is a special "recoverable signature" type. Given
the message M and the signature S, it is
then possible to recover the pubkey kG. The system thus
derives the address for the pubkey kG, and if it does not
match A, the proof is deemed invalid.

While this is a neat trick, it unnecessarily restricts and complicates
the message signing mechanism; for instance, it is currently not
possible to sign a message for a P2SH address, because there is no
pubkey to recover from the resulting signature.

== Motivation ==

The current message signing standard only works for P2PKH (1...)
addresses. By extending it to use a Bitcoin Script based approach, it
could be made more generic without causing a too big burden on
implementers, who most likely have access to Bitcoin Script
interpreters already.

== Specification ==

A new structure SignatureProof is added, which is a
simple serializable scriptSig & witness container.

=== SignatureProof container ===

{|class="wikitable" style="text-align: center;"
|-
!Type
!Length
!Name
!Comment
|-
|VarInt||1-8||scriptsiglen||Number of bytes in scriptSig data
|-
|Uint8*||[scriptsiglen]||scriptsig||ScriptSig data
|-
|VarInt||1-8||witlen||Number of entries in witness stack
|-
|Uint8[]*||[witlen]||wit||Witness stack, as [witlen] uint8* vectors,
each one prepended with a varint of its size
|}

In some cases, the scriptsig or wit may be empty. If both are empty,
the proof is incomplete.

=== Result Codes ===

A verification call will return a result code according to the table below.

{|class="wikitable" style="text-align: center;"
|-
!Code
!Description
|-
|INCOMPLETE||Empty proof.
|-
|INCONCLUSIVE||The given proof was consensus-valid but policy-invalid.
|-
|VALID||The proof was valid.
|-
|INVALID||The proof was invalid
|-
|ERROR||An error was encountered
|}

== Signing and Verifying ==

If the challenge consists of an address is in the P2PKH (legacy)
format, sign using the legacy format (further information below).
Otherwise continue as stated below.

For both cases, generate a sighash based on the given scriptPubKey and
message as follows:

# Define the message pre-image as the sequence "Bitcoin Signed
Message:\n" concatenated with the message, encoded in UTF-8 using
Normalization Form Compatibility Decomposition (NFKD)
# Let sighash = sha256(sha256(scriptPubKey || pre-image))

A private key may be used directly to sign a message. In this case,
its P2WPKH bech32 address shall be derived, and used as the input.

=== Signing ===

The signature is generated as follows:

# Derive the private key privkey for the scriptPubKey; FAIL if not VALID
# Generate and return a signature sig with privkey=privkey, sighash=sighash

=== Verifying ===

Verify a proof, given a standard flags value, a script sig, an
optional witness, and a derived sighash as described above.

While omitted below, ERROR is returned if an unforeseen error occurs
at any point in the process. A concrete example of this is if a legacy
proof is given as input to a non-legacy address; the deserialization
of the proof will fail in this case, and this should result in an
ERROR result.

# Verify Script with flags=consensus flags (currently P2SH, DERSIG,
NULLDUMMY, CLTV, CSV, WITNESS), scriptSig=script sig,
scriptPubKey=scriptPubKey, witness=witness, and sighash=sighash
# Return INVALID if verification fails
# Verify Script with flags=standard flags (above plus STRICTENC,
MINIMALDATA, etc.), scriptSig=script sig, scriptPubKey=scriptPubKey,
witness=witness, and sighash=sighash
# Return VALID if verification succeeds, otherwise return INCONCLUSIVE

== Legacy format ==

The legacy format is restricted to the legacy P2PKH address format.

Any other input (i.e. non-P2PKH address format) must be signed using
the new format d

Re: [bitcoin-dev] Mitigating Differential Power Analysis in BIP-340

[Pieter Wuille via bitcoin-dev]

On Tuesday, March 24, 2020 6:00 AM, Lloyd Fournier via bitcoin-dev 
 wrote:

> Hi List,
>
> I felt this topic deserved it's own thread but it follows on from the mailing 
> list post [2] announcing a new PR [1] to change BIP-340 in several ways, 
> including adding random auxiliary data into the nonce derivation function. 
> Rather than hashing the randomness with the secret key and message etc, the 
> randomness is hashed then XOR'd (^) with the secret key and the result is 
> hashed like so to determine the secret nonce k:
>
> (1) k = H_derive( sec_key ^ H_aux(rand) || pub_key_x || message)
>
> The claim made in the mailing list post is that this is more secure against 
> "differential power analysis" (DPA) attacks than just doing the simpler and 
> more efficient:
>
> (2) k = H_derive(sec_key || rand || pub_key_x || message)
>
> The TL;DR here is that I don't think this is the case.

Hi Lloyd,

Thank you for looking into this. I very much agree we haven't given nearly 
enough justification for the use of a non-standard scheme here.

I'll try to summarize the discussion we had that led to this choice, but most 
of it is on https://github.com/sipa/bips/issues/195 if you want the details.

Let me first try to address what I think you're overlooking: in a BIP32/Taproot 
like scenario, the private key that goes into the signing algorithm functions 
as *both* secret and known to the attacker. That is to say, there is a master 
secret s, and signing key x that goes into the hash is x=s+a (mod n) for some 
value a that the attacker knows, and can modify (he cannot control it directly, 
but he may be able to grind it to have a structure he likes). I believe that 
means that feeding x to a hash directly itself is already a problem, regardless 
of what else goes into the hash - interactions between bits inside the hash 
operation that all come from x itself can leak bit-level information of x.  
XORing (or any other simple mix operation that does not expose bit-level 
information) into the private key before giving it to a hash function seems 
like it would address this.

That said, all these DPA issues are very hard to reason about, as it's hard to 
find a realistic attack model that both (a) leaks some information but (b) 
doesn't obviously leak the entire key immediately. In the reasoning above I 
assumed an attacker who can observe word-level Hamming weight aggregates of all 
variables in the algorithm (which seems to match what one of the papers 
observed), but not bit level information. It also assumes that somehow the 
computation of x itself is immune from leaks (something you pointed out in a 
previous e-mail, I noticed).

So really, all of this is trying to choose one alternative among a set of (when 
ignoring DPA) nearly equally good constructions. Note that randomness is useful 
for protection against fault attacks, but for that purpose it doesn't matter 
where in the hash it goes, or even that it's particularly strong randomness (a 
counter would also work). There are a number of other concerns we discussed in 
the linked thread:
* Efficiency (how many SHA256 transformations, including the ability for some 
to be precomputed)
* The risk that the randomness added is correlated with the private key in a 
way that cancels things out when they're naively XORed together.
* The risk of having a midstate in the hash function leak (without leaking the 
actual private key, but enough to predict nonces).
* The issue with public keys that are input to the signing algorithm which come 
directly from an attacker (which is the reason why pubkey goes into the nonce 
function too).

The solution we came up with (H(priv XOR H(aux) || pub || msg)) is the only 
that ticks most of the boxes - but a different prioritization may certainly 
lead to a different conclusion.

I'm happy for any input you may have here. In particular, the recent 
discussions around the interactions between anti-covert channel protection, 
randomness, and the ability to spot check hardware devices may mean we should 
revise the advice to consider not adding randomness unless such a anti-covert 
channel scheme is used.

Cheers,

--
Pieter

___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

[bitcoin-dev] Mitigating Differential Power Analysis in BIP-340

[Lloyd Fournier via bitcoin-dev]

Hi List,

I felt this topic deserved it's own thread but it follows on from the
mailing list post [2] announcing a new PR [1] to change BIP-340 in several
ways, including adding random auxiliary data into the nonce
derivation function. Rather than hashing the randomness with the secret key
and message etc, the randomness is hashed then XOR'd (^) with the secret
key and the result is hashed like so to determine the secret nonce k:

(1) k = H_derive( sec_key ^ H_aux(rand) || pub_key_x || message)

The claim made in the mailing list post is that this is more secure against
"differential power analysis" (DPA) attacks than just doing the simpler and
more efficient:

(2) k = H_derive(sec_key || rand || pub_key_x || message)

The TL;DR here is that I don't think this is the case.

There was no citation for this claim, so I did some digging and found two
papers that seemed like they might be the origin of the idea [3,4] (I had
no idea about these attacks before). A relatively easy to understand
explanation of DPA attacks against is in [3]:

The fundamental principle behind all DPA attacks is that at some point in
> an algorithm’s execution, a function f exists that combines a fixed secret
> value with a variable which an attacker knows. An attacker can form
> hypotheses about the fixed secret value, and compute the corresponding
> output values of f by using an appropriate leakage model, such as the
> Hamming Distance model. The attacker can then use the acquired power
> consumption traces to verify her hypotheses, by partitioning the
> acquisitions or using Pearson’s correlation coefficient. These side-channel
> analysis attacks are aided by knowledge of details of the implementation
> under attack. Moreover, these attacks can be used to validate hypotheses
> about implementation details. In subsequent sections, these side-channel
> analysis attacks are referred to as DPA attacks.


For example, in the original BIP-340 proposal the nonce derivation was
vulnerable to DPA attacks as it was derived simply by doing
H_derive(sec_key || message). Since, the message is known to the attacker
and variable (even if it is not controller by her), the SHA256 compression
function run on (sec_key || message) may leak information about sec_key. It
is crucial to understand that just hashing sec_key before passing it into
the H_derive does *not* fix the problem. Although the attacker would be
unable to find sec_key directly, they could learn H(sec_key) and with that
know all the inputs into H_derive and therefore get the value of the secret
nonce k and from there extract the secret key from any signature made with
this nonce derivation algorithm.

The key thing I want to argue with this post is that there is no advantage
of (1) over (2) against DPA attacks, at least not given my understanding of
these papers. The way the attack in [3] works is by assuming that
operations in the compression function leak the "hamming distance" [5] (HD)
between the static secret thing that is being combined with the variable
public thing. In practice the attack involves many particulars about SHA256
but that is, at a high level, the right way to simplify it I think. The way
the paper suggests to fix the problem is to mask the secret data with
secret randomness before each sensitive operation and then strip off the
secret randomness afterwards. This seems to be the inspiration for the
structure of updated BIP-340 (1), however I don't believe that it provides
any extra protection over (2). My argument is as follows:

Claim A: If the randomness used during signing is kept secret from the
attacker then (2) is secure against DPA.

Since SHA256 has 64-byte blocks the hash H_derive(sec_key || rand ||
pub_key_x || message) will be split up into two 64 byte blocks, one
containing secret data (sec_key || rand) and the other containing data
known to the attacker (pub_key_x || message). The compression function will
run on (sec_key || rand) but DPA will be useless here because the
HD(sec_key, rand) will contain no information about sec_key since rand is
also secret. The output of the compression function on the first block will
be secret but *variable* so the intermediate hash state will not reveal
useful information when compressed with the second block.

Then I thought perhaps (1) is more robust in the case where the randomness
is known by the attacker (maybe the attacker can physically modify the
chipset to control the rng). We'd have to assume that the sec_key ^
H_aux(rand) isn't vulnerable to DPA (the LHS is under the control of the
attacker) to be true. Even under this assumption it turned out not to be
the case:

Claim B: If the randomness used during signing is known to the attacker,
then (1) is not secure against DPA.

In (1)  there are 96 bytes to be hashed and therefore two SHA256 blocks:
(H_aux(sec_key) ^ rand || pub_key_x) and (message). During the first
compression function call the attacker gets the HD of:
HD( sec_key ^ H_aux(rand),  pub_key_x)
w

Re: [bitcoin-dev] Overview of anti-covert-channel signing techniques

[Dustin Dettmer via bitcoin-dev]

Hi Tim,

Hm, so what vectors is this supposed to mitigate? Leaking through the
> generated public keys? Anything else?


The main thing it’s protecting against is the stealing of your funds by
malicious hardware & software. There are some side benefits as well though.

 - What are you trying to achieve? You seem to describe how you get
> from the setup to the goal in four steps but I don't understand what
> the setup is or what the goal is. (What's a storage solution?)


“Storage solution” is however you’re storing bitcoins today. Could be 12
words on some paper plus a computer running electrum. Could be a Ledger +
computer. Point is this technique works regardless of how you’re storing
your bitcoin.

 - "all SW being compromised" do you mean "SW and HW compromised"? Note
> that SW and HW are parties in Pieter's writeup, not just abbreviations
> for software and hardware.


Yeah — if you split the SW party into two, “generator” and “validator” some
interesting and useful security properties emerge.

 - Where are the two stages? You mention four steps.


“Generator” and “validator”. The generator creates and passes on receiving
addresses and withdrawal transactions (while remaining offline). The
validator double checks everything the generator did..

It works best if the validator is written entirely independently of the
generator.

 - Where do you run the external software? On a second SW? Is this the
> second stage?


Yes

 - Do you use unhardened derivation?


It’s an open ended solution — it would work with a (presumably
non-trivial/random) unhardened derivation just fine.

 - What's a k commitment?


It is one of the proposed solutions presented (collected?) by Peter in this
thread. As I understand it k is used to generate R in the signature. By
committing to some k value the hardware wallet can’t “sneak out” your
private key(s) in the R value.

Best,
Dustin

>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Overview of anti-covert-channel signing techniques

[Tim Ruffing via bitcoin-dev]

Hi Dustin,

That sounds interesting but I can't follow your email to be honest.

On Mon, 2020-03-23 at 07:38 -0700, Dustin Dettmer via bitcoin-dev
wrote:
> This mitigates, I believe, all leak vectors besides k/R hacking and
> prechosen entropy.

Hm, so what vectors is this supposed to mitigate? Leaking through the
generated public keys? Anything else?

Here are a few questions:
 - What are you trying to achieve? You seem to describe how you get
from the setup to the goal in four steps but I don't understand what
the setup is or what the goal is. (What's a storage solution?)
 - "all SW being compromised" do you mean "SW and HW compromised"? Note
that SW and HW are parties in Pieter's writeup, not just abbreviations
for software and hardware. 
 - Where are the two stages? You mention four steps.
 - Where do you run the external software? On a second SW? Is this the
second stage?
 - Do you use unhardened derivation?
 - What's a k commitment?


Best,
Tim


___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] RFC: Deterministic Entropy From BIP32 Keychains

[Tim Ruffing via bitcoin-dev]

I think your proposal is simply to use BIP32 for all derivations and
the observation that you can work with derived keys with the
corresponding suffixes of the path. I believe that this is a good idea.

But I don't think that simply writing a standard will help. It's just
one step. If all your wallets support incompatible formats, we should
work on fixing this because that's the root of the issue. Otherwise you
end up converting keys back and forth manually (as Chris pointed out),
and this can't be the goal. 

But then you need to reach out to wallet devs explicitly and get them
involved in creating the standard. Otherwise they won't use it. That's
a hard process, and it's even harder to make sure that the resulting
proposal isn't way too complex because everyone brings their special
case to the table. 

Tim 

On Sun, 2020-03-22 at 11:58 +, Ethan Kosakovsky via bitcoin-dev
wrote:
> I have completely revised the wording of this proposal I hope to be
> clearer in explaining the motivation and methodology.
> 
> https://gist.github.com/ethankosakovsky/268c52f018b94bea29a6e809381c05d6
> 
> Ethan
> 
> ‐‐‐ Original Message ‐‐‐
> On Friday, March 20, 2020 4:44 PM, Ethan Kosakovsky via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
> 
> > I would like to present a proposal for discussion and peer review.
> > It aims to solve the problem of "too many seeds and too many
> > backups" due to the many reasons stipulated in the proposal text.
> > 
> > https://gist.githubusercontent.com/ethankosakovsky/f7d148f588d14e0bb4f70bb6afc509d0/raw/6da51e837b0e1f1b2b21f3d4cbc2c5a87969ffd5/bip-entropy-from-bip32.mediawiki
> > 
> > 
> > BIP:
> > Title: Deterministic Entropy From BIP32 Keychains
> > Author: Ethan Kosakovsky ethankosakov...@protonmail.com
> > Comments-Summary: No comments yet.
> > Comments-URI:
> > Status: Proposed
> > Type: Standards Track
> > Created: 2020-03-20
> > License: BSD-2-Clause
> > OPL
> > 
> > 
> > ==Abstract==
> > 
> > This proposal provides a way to derive entropy from a HD keychain
> > path in order to deterministically derive the initial entropy used
> > to create keychain mnemonics and seeds.
> > 
> > ==Motivation==
> > 
> > BIP32 uses some initial entropy as a seed to deterministically
> > derive a BIP32 root for hierarchical deterministic keychains. BIP39
> > introduced a method of encoding initial entropy into a mnemonic
> > phrase which is used as input to a one way hash function in order
> > to deterministically derive a BIP32 seed. The motivation behind
> > mnemonic phrases was to make it easier for humans to backup and
> > store offline. There are also other variations of this theme.
> > 
> > The initial motivation of BIP32 was to make handling of large
> > numbers of private keys easier to manage and backup, since you only
> > need one BIP32 seed to cover all possible keys in the keychain. In
> > practice however, due to various wallet implementations and
> > security models, the average user may be faced with the need to
> > handle an ever growing number of seeds/mnemonics. This is due to
> > incompatible wallet standards, hardware wallets (HWW), seed formats
> > and standards, as well as, the need to used a mix of hot and cold
> > wallets depending on the application and environment.
> > 
> > Examples would span wallets on mobile phones, online servers
> > running protocols like Join Market or Lightning, and the difference
> > between Electrum and BIP39 mnemonic seed formats. The reference
> > implementation of Bitcoin Core uses BIP32, while other
> > cryptocurrencies like Monero use different mnemonic encoding
> > schemes.
> > 
> > We must also consider the different variety of physical backups
> > including paper, metal and other physical storage devices, as well
> > as the potentially splitting backups across different geographical
> > locations. This complexity may result in less care being taken with
> > subsequently generated seeds for new wallets need to be stored and
> > it ultimately results in less security. In reality, the idea of
> > having "one seed for all" has proven to be more difficult in
> > practice than originally thought.
> > 
> > Since all these derivation schemes are deterministic based on some
> > initial entropy, this proposal aims to solve the above problems by
> > detailing a way to deterministically derive the initial entropy
> > used for new root keychains using a single BIP32 style "master root
> > key". This will allow one root key or mnemonic to derive any
> > variety of different root keychains in whatever format is required
> > (like BIP32 and BIP39 etc).
> > 
> > ==Specification==
> > 
> > Input starts with a BIP32 seed. Derivation scheme uses the format
> > `m/83696968'/type'/index'` where `type` is the final seed type, and
> > `index` in the key index of the hardened child private key.
> > 
> > type
> > 
> > bits
> > 
> > output
> > 
> > 0
> > 
> > 128
> > 
> > 12 word BIP39 mnemonic
> > 
> > 1
> > 
> > 256
> > 
> > 24 word BIP3

Re: [bitcoin-dev] Block solving slowdown question/poll

[ZmnSCPxj via bitcoin-dev]

Good morning Andrew,


> > Hi, noob question here: Is there a long-term plan for if the block reward 
> > drops
> > too low to ensure the security of the network?
> >
> > IIUC miners only make profit from block rewards and transaction fees, and 
> > once
> > the block reward drop to zero we're merely hoping that transaction fees will
> > keep mining expensive enough to stop a state actor or someone from buying
> > enough hash power to attack the network. If that's the case, should we start
> > making plans now to change the protocol to allow an adjustable block reward?
> >
> > Here's a half-baked idea I had of how that could work: Since the block 
> > reward
> > dilutes the value of the currency bitcoin holders have an incentive to keep 
> > the
> > reward low. However, since the block reward is also (partly) what 
> > incentivizes
> > mining, bitcoin holders also have an incentive to keep the reward high 
> > enough
> > to keep the network secure. So if bitcoin holders were able to vote to 
> > decide
> > the block reward they "should", hypothetically, reliably choose a value that
> > balances these two concerns.

They already do so, via an implicit "field", known as the transaction fee.
This is "implicit" since it is only the difference of the sum of all inputs 
with the sum of all outputs, but any Bitcoin HODLer spending their coins always 
need to make this decision.

This makes the vote for how much security is needed to be costly to the voter, 
which is appropriate: you pay for your security.

This mechanism is the same mechanism as well that is the long-term plan for the 
lowered block rewards in the future, and is already the best known idea to 
tackle this problem as well.


Regards,
ZmnSCPxj
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev