Gold collapsing. Bitcoin UP.

[cypherdoc]

The solution is for the community to demand that bitcoin hardware and software wallets use deterministic signatures, for example following RFC6979.  When RFC6979 is used, the k-value used for producing the ECDSA signature is derived deterministically from the message and the private key.  This has the benefit of

   (1) eliminating the need for a RNG when producing signatures (and thus the risk of using a flawed RNG)
   (2) making software/hardware audits much simpler (just load test private keys and make sure the signatures match what's expected [it's very difficult to audit a RNG, on the other hand])

Adding deterministic signatures is not a significant software project either.  Basically, rather than calling a random number generator when selecting k:

   k = random256bits()
 
we pass the private key and the message to an RFC6979 library function instead:

   k = rfc6979(privkey, message)

This rest of the code remains unchanged.  

Was not aware of RFC6979, thank you for sharing. Has any wallet software started to move in this direction or implemented this approach?

It seems this will work well for an existing HD wallet, where no new private keys need to be generated. However most wallet software needs to be able to create new wallets and still require the ability to generate cryptographically random numbers in order to create new private keys or a new HD seed. So the problem of wallet software requiring true random numbers still exists.

It could even be argued that RFC6979 might make wallet developers less aware on how to obtain true random numbers since RFC6979 "fixed" the problem, and as a result generate weak HD seeds. I remember for Armory there was a discussion last summer that resulted in more entropy being added to HD seed generation, I am sure most wallet software is not as paranoid and could still be weak here even with RFC6979. Weak HD seed generation is much more of an issue than moderately weak k value generation IMHO.

BTW, Not sure if the need for RFC6979 in general is more of a statement on how hard it is to produce true random numbers, or if this is more of a statement on the state of software engineering today.

it is certainly a trend.  Trezor has it implemented.

[cypherdoc]

The solution is for the community to demand that bitcoin hardware and software wallets use deterministic signatures, for example following RFC6979.  When RFC6979 is used, the k-value used for producing the ECDSA signature is derived deterministically from the message and the private key.  This has the benefit of

   (1) eliminating the need for a RNG when producing signatures (and thus the risk of using a flawed RNG)
   (2) making software/hardware audits much simpler (just load test private keys and make sure the signatures match what's expected [it's very difficult to audit a RNG, on the other hand])

Adding deterministic signatures is not a significant software project either.  Basically, rather than calling a random number generator when selecting k:

   k = random256bits()
 
we pass the private key and the message to an RFC6979 library function instead:

   k = rfc6979(privkey, message)

This rest of the code remains unchanged.  

Was not aware of RFC6979, thank you for sharing. Has any wallet software started to move in this direction or implemented this approach?

It seems this will work well for an existing HD wallet, where no new private keys need to be generated. However most wallet software needs to be able to create new wallets and still require the ability to generate cryptographically random numbers in order to create new private keys or a new HD seed. So the problem of wallet software requiring true random numbers still exists.

It could even be argued that RFC6979 might make wallet developers less aware on how to obtain true random numbers since RFC6979 "fixed" the problem, and as a result generate weak HD seeds. I remember for Armory there was a discussion last summer that resulted in more entropy being added to HD seed generation, I am sure most wallet software is not as paranoid and could still be weak here even with RFC6979. Weak HD seed generation is much more of an issue than moderately weak k value generation IMHO.

BTW, Not sure if the need for RFC6979 in general is more of a statement on how hard it is to produce true random numbers, or if this is more of a statement on the state of software engineering today.

what is somewhat circular for me is that, for a given computer, if you have a problem generating enough entropy for RNG for k values, then you probably have an equally hard problem generating enough entropy for privkeys, as i assume their source of entropy is equivalent.  therefore the HMAC of the message + privkey is also insecure.

btw, perhaps someone can clarify for me.  the privkey is simply a random number btwn 1 and 2²⁵⁶.  what's to stop me from self declaring that i will pick the number 75% of the way to 2²⁵⁶ as my privkey?  the chances of a pure RNG generating that same # is infinitesimal.  therefore, it should be safe.

[smooth]

what is somewhat circular for me is that, for a given computer, if you have a problem generating enough entropy for RNG for k values, then you probably have an equally hard problem generating enough entropy for privkeys, as i assume their source of entropy is equivalent.

Not necessarily. Generation of private keys is a rare event, especially with HD wallets. You need a k value for each tranasction.

what's to stop me from self declaring that i will pick the number 75% of the way to 2²⁵⁶ as my privkey?  the chances of a pure RNG generating that same # is infinitesimal.  therefore, it should be safe.

Nothing, although that's sort like of a brain wallet, and subject to the same flaws. If someone searches through the list of clever but simple methods of picking a key, they will find yours.

[NewLiberty]

I picked up a bunch of these hexadecimal dice back when they were still being made.
They were a hit at the Bitcoin conventions and meetups.
Still have some even.

[rocks]

what's to stop me from self declaring that i will pick the number 75% of the way to 2²⁵⁶ as my privkey?  the chances of a pure RNG generating that same # is infinitesimal.  therefore, it should be safe.

Nothing, although that's sort like of a brain wallet, and subject to the same flaws. If someone searches through the list of clever but simple methods of picking a key, they will find yours.

Exactly, to make this method secure you'd have to randomly select 75.29379857239479209348238048023740720340% of the way to 2^256, which is the same as just banging out 256 bits of entropy on your keyboard (which may not even be that random depending on how you type, dice would be much better)

what is somewhat circular for me is that, for a given computer, if you have a problem generating enough entropy for RNG for k values, then you probably have an equally hard problem generating enough entropy for privkeys, as i assume their source of entropy is equivalent.

Not necessarily. Generation of private keys is a rare event, especially with HD wallets. You need a k value for each tranasction.

The issue with HD wallet seed key generation is even though it happens once, EVERYTHING rests on having true entropy during it's generation, especially for a wallet that may live for decades (which many HD wallets will). However at the same time generating HD seeds or private keys can be done when a machine and wallet software first start when there is the LEAST amount of entropy in a given machine.

For example lets assume someone decides to use a Ubuntu 14.4 VM image pre-configured to run bitcoind automatically. That person starts the VM, logs into a ssh shell, and then issues a bitcoind command to create a new wallet. This a logical user flow, but it also means the system has very little entropy. In this case everything about the system configuration is known ahead of time (it is a pre-configured VM image with known virtual hardware) and the user inputted a minimal amount of new information to capture (even the bitcoind command is known and can be easily guessed). About the only random information the user adds is their personal id/pw, but those might be quite weak because the user figures they are running on a secure home network. In this situation that machine has very little true entropy to use in private key or HD wallet generation. At the same time that key might have a lifetime of decades, during which an attacker can try combinations.

That is why it is important that the random number generator captures as much entropy from as many sources as possible. However most rnd functions do not do so by default and the cryptographically secure methods can vary from OS, i.e. a developer has to find the right function calls for linux, windows, etc.

This is why some people roll dice to generate the seed key for their core wallets, since it is the only way to be absolutely sure. I am positive that right now there probably are several individuals trying combinations on known (to them) weak setups trying to guess HD seeds or private keys.

[justusranvier]

It seems like there is a market for a device which will generate 256 bits of entropy once and save it forever.

256 bits of entropy should be enough to last a lifetime (except if any of it gets compromised).

[cbeast]

If you create a HD wallet that ONLY creates multisig transactions, would that prevent addresses from being reused?

[justusranvier]

If you create a HD wallet that ONLY creates multisig transactions, would that prevent addresses from being reused?

What does multisig have to do with address reuse?

[cbeast]

If you create a HD wallet that ONLY creates multisig transactions, would that prevent addresses from being reused?

What does multisig have to do with address reuse?

HD wallets reuse addresses when people send multiple payments to them. I think that is a weakness. Isn't there another bitcoin payment for where this is not possible, like multisig?

[NewLiberty]

If you create a HD wallet that ONLY creates multisig transactions, would that prevent addresses from being reused?

What does multisig have to do with address reuse?

HD wallets reuse addresses when people send multiple payments to them. I think that is a weakness. Isn't there another bitcoin payment for where this is not possible, like multisig?

The RIGHT way to do it would be Stealth Addresses.
This way you can publish a permanent address and it is not tracked to the address in the block chain by anyone except its owner, and the addresses in the block chain is not reused, preventing a Johoe grab.
It solves both problems simultaneously, but the address bigger (so the QR takes smaller squares, etc).

Monero does it automatically from the start, with all transactions, it is not really possible to NOT use a stealth address, all wallets use them. 
In Bitcoin, it is sort of possible to do stealth addresses, but it is not user friendly at all, and so it is considered experimental.

Here is how:
http://sx.dyne.org/stealth.html

[smooth]

In Bitcoin, it is sort of possible to do stealth addresses, but it is not user friendly at all, and so it is considered experimental.

Here is how:
http://sx.dyne.org/stealth.html

Or you can just use dark wallet (also somewhat experimental though).

[HeliKopterBen]

The problem is that human thoughts and actions are invariably patterned, not random.  Even when someone attempts to be random, they often revert back to patterned thoughts and actions.  RNGs are unfortunately programmed by humans and therefore subject to possibly being patterned in some way.  For large sums of money, it is still advisable to use multiple sources of objective external entropy such as die rolls combined with mouse movements.

[cypherdoc]

For example lets assume someone decides to use a Ubuntu 14.4 VM image pre-configured to run bitcoind automatically. That person starts the VM, logs into a ssh shell, and then issues a bitcoind command to create a new wallet. This a logical user flow, but it also means the system has very little entropy. In this case everything about the system configuration is known ahead of time (it is a pre-configured VM image with known virtual hardware) and the user inputted a minimal amount of new information to capture (even the bitcoind command is known and can be easily guessed). About the only random information the user adds is their personal id/pw, but those might be quite weak because the user figures they are running on a secure home network. In this situation that machine has very little true entropy to use in private key or HD wallet generation. At the same time that key might have a lifetime of decades, during which an attacker can try combinations.

i find this fascinating.  so you're saying that even with a perfect RNG, which is software based afaik, unless it has an excellent source of randomness (such as mouse movement, static off embedded chips, etc) it won't generate truly random privkeys?

how does Armory then create secure deterministic wallets then?  how would one generate the required entropy from the old offline pc's used to install such a program?  the usual method is to just install Armory and go right to wallet creation.

[cypherdoc]

Producing additional ECDSA signatures (additional outbound TXs) from that address has no meaningful effect on security either, provided the k-values used in signature generation remain unknown. As an example, the address 12WRnQR85ZUT7dhmaHBNL5dde2QLYieW6v presently holds $24,000,000 of bitcoins and has made multiple outgoing transactions.  For each outgoing transaction from this address, we can inspect the signatures and determine the R values.  This doesn't help us "hack" the address to any meaningful extent except in the case where the signatures were produced incorrectly (for example, by using a low-entropy k-value).

Peter, this is quite helpful and i learned something here which i'd like to verify.  so, it is not really R that needs to be random, but in fact k that is used to calculate R, correct?  that's b/c (x₁, y₁)=kG where R=x₁ (mod N).   

furthermore, k not only has to be random, but it has to remain "unknown", correct?

[cypherdoc]

out of curiosity to the security experts here.

which do you consider more secure, Armory or Trezor?

[Peter R]

Producing additional ECDSA signatures (additional outbound TXs) from that address has no meaningful effect on security either, provided the k-values used in signature generation remain unknown. As an example, the address 12WRnQR85ZUT7dhmaHBNL5dde2QLYieW6v presently holds $24,000,000 of bitcoins and has made multiple outgoing transactions.  For each outgoing transaction from this address, we can inspect the signatures and determine the R values.  This doesn't help us "hack" the address to any meaningful extent except in the case where the signatures were produced incorrectly (for example, by using a low-entropy k-value).

Peter, this is quite helpful and i learned something here which i'd like to verify.  so, it is not really R that needs to be random, but in fact k that is used to calculate R, correct?  that's b/c (x₁, y₁)=kG where R=x₁ (mod N).   

furthermore, k not only has to be random, but it has to remain "unknown", correct?

75% correct: k is indeed used to calculate R and it's the variable the software has control over. 

But k doesn't have to be random; it just has to be secret (remain unknown) and unique per message¹.  This is why RFC6979 works: k is deterministic but remains secret so long as the private key remains secret.  And it's guaranteed to be unique per message because it's the hash of some mix of the private key and the message (assuming SHA2 collisions are infeasible). 

¹The "unique-per-message" requirement is in fact so that k remains secret, since it's possible to algebraically solve for k (and also the private key) if two unique messages are signed with the same k value. 

[rocks]

Producing additional ECDSA signatures (additional outbound TXs) from that address has no meaningful effect on security either, provided the k-values used in signature generation remain unknown. As an example, the address 12WRnQR85ZUT7dhmaHBNL5dde2QLYieW6v presently holds $24,000,000 of bitcoins and has made multiple outgoing transactions.  For each outgoing transaction from this address, we can inspect the signatures and determine the R values.  This doesn't help us "hack" the address to any meaningful extent except in the case where the signatures were produced incorrectly (for example, by using a low-entropy k-value).

Peter, this is quite helpful and i learned something here which i'd like to verify.  so, it is not really R that needs to be random, but in fact k that is used to calculate R, correct?  that's b/c (x₁, y₁)=kG where R=x₁ (mod N).  

furthermore, k not only has to be random, but it has to remain "unknown", correct?

Yes you have that correct. It is k that needs to be protected because once you know the k value used in a signature you can calculate the private key from the signature and public key.

The issue with using the same R value (which is derived from the same k value) in two different signatures is that it then becomes possible to calculate the k value used using both signatures, and once you have the k value you can calculate the private key.

Do read this link if you are interested in the topic. It explains all of the math required to understand ECDSA and DSA, but in an understandable manner and also covers the question above well.

http://kakaroto.homelinux.net/2012/01/how-the-ecdsa-algorithm-works/

Edit: looks like Peter beat me in replying by ~1min. The reason why the RFC6979 approach works is because you are guaranteed to use a different k value for each different message (due to hashing the key & message). The only time RFC6979 would repeat a k value is if the message was exactly the same, in which case you are not producing two separate signature but just repeating the same one done before.

[cypherdoc]

Producing additional ECDSA signatures (additional outbound TXs) from that address has no meaningful effect on security either, provided the k-values used in signature generation remain unknown. As an example, the address 12WRnQR85ZUT7dhmaHBNL5dde2QLYieW6v presently holds $24,000,000 of bitcoins and has made multiple outgoing transactions.  For each outgoing transaction from this address, we can inspect the signatures and determine the R values.  This doesn't help us "hack" the address to any meaningful extent except in the case where the signatures were produced incorrectly (for example, by using a low-entropy k-value).

Peter, this is quite helpful and i learned something here which i'd like to verify.  so, it is not really R that needs to be random, but in fact k that is used to calculate R, correct?  that's b/c (x₁, y₁)=kG where R=x₁ (mod N).  

furthermore, k not only has to be random, but it has to remain "unknown", correct?

75% correct: k is indeed used to calculate R and it's the variable the software has control over.  

But k doesn't have to be random; it just has to be secret (remain unknown) and unique per message¹.  This is why RFC6979 works: k is deterministic but remains secret so long as the private key remains secret.  And it's guaranteed to be unique per message because it's the hash of some mix of the private key and the message (assuming SHA2 collisions are infeasible).  

¹The "unique-per-message" requirement is in fact so that k remains secret, since it's possible to algebraically solve for k (and also the private key) if two unique messages are signed with the same k value.  

is it fair to say that when generating repeated deterministic k's when reusing the same address for tx's, that in fact the k is NOT random since both of the HMAC components are the same (privkey) or similarly structured (tx) ?   i may be using HMAC incorrectly but i mean --> k=hash (tx+privkey).

[rocks]

For example lets assume someone decides to use a Ubuntu 14.4 VM image pre-configured to run bitcoind automatically. That person starts the VM, logs into a ssh shell, and then issues a bitcoind command to create a new wallet. This a logical user flow, but it also means the system has very little entropy. In this case everything about the system configuration is known ahead of time (it is a pre-configured VM image with known virtual hardware) and the user inputted a minimal amount of new information to capture (even the bitcoind command is known and can be easily guessed). About the only random information the user adds is their personal id/pw, but those might be quite weak because the user figures they are running on a secure home network. In this situation that machine has very little true entropy to use in private key or HD wallet generation. At the same time that key might have a lifetime of decades, during which an attacker can try combinations.

i find this fascinating.  so you're saying that even with a perfect RNG, which is software based afaik, unless it has an excellent source of randomness (such as mouse movement, static off embedded chips, etc) it won't generate truly random privkeys?

how does Armory then create secure deterministic wallets then?  how would one generate the required entropy from the old offline pc's used to install such a program?  the usual method is to just install Armory and go right to wallet creation.

I am by no means an expert on this topic, most of what I learned came from a discussion in the Armory section which resulting in Armory changing/improving it's sources of entropy. (It's original method was probably good enough, but they were trying to further strengthen it) So the following is mostly from what I took away from following that discussion.

Even if a VM configuration is fully known and static, there can be enough entropy generated during boot time but it needs to be carefully captured and a programmer needs to know the right calls to do this. These sources can include: the current time/date, the MAC address generated by VMWare or kvm (which is not fully random), the I/O performance of the underlying storage system which can effect various orderings to the boot sequence, the times of service start initiations and completions, etc.

In a limited environment where bitcoind automatically starts as a service on boot in a known VM configuration and creates a new wallet.dat file before a user even tries to login, it is necessary to capture every possible source of entropy.

The only reason I brought this up is even though RFC6979 looks to be a great solution for safe generation of k values, wallet software still needs to correctly generate crytographically random numbers for wallet generation, which is arguably even more important.

[cypherdoc]

what is "constant time"?

Improved signing security

For 0.10 the security of signing against unusual attacks has been improved by making the signatures constant time and deterministic.

This change is a result of switching signing to use libsecp256k1 instead of OpenSSL. Libsecp256k1 is a cryptographic library optimized for the curve Bitcoin uses which was created by Bitcoin Core developer Pieter Wuille.

There exist attacks[1] against most ECC implementations where an attacker on shared virtual machine hardware could extract a private key if they could cause a target to sign using the same key hundreds of times. While using shared hosts and reusing keys are inadvisable for other reasons, it's a better practice to avoid the exposure.

OpenSSL has code in their source repository for derandomization and reduction in timing leaks, and we've eagerly wanted to use it for a long time but this functionality has still not made its way into a released version of OpenSSL. Libsecp256k1 achieves significantly stronger protection: As far as we're aware this is the only deployed implementation of constant time signing for the curve Bitcoin uses and we have reason to believe that libsecp256k1 is better tested and more thoroughly reviewed than the implementation in OpenSSL.

[1] https://eprint.iacr.org/2014/161.pdf