Topic: Deterministic wallets - page 13. (Read 48392 times)

It seems like it should be possible to compartmentalize the risk. Accidentally revealing one private key will compromise the entire branch but it should be possible to limit the damage to that branch without affecting others.

In general, deterministic wallets (a) make life easier while (b) increasing the security threat (e.g. decreasing overall security).  Before, if one private key was compromised, others were safe.  Now, the picture is not so clear.

And if the seed is compromised, all keys are thus compromised.

If all private keys are covered by the same master key, then the security situation is largely unchanged, and the threat model focuses on protecting the seed (rather than a wallet full of keys).

However, private keys are not necessarily all tied together.

I'm trying to understand the full implications of accidentally revealing a individual private key.

Suppose I gave Mt Gox the extended public key m/0/0. They would then be able to generate m/0/0/0...k themselves in order to send each future BTC withdrawal to a unique address without further interaction from me.

If I accidentally reveal private key m/0/1/42 this means they can generate all private keys in the m/0/1/0...k series as well.

What does that mean for other branches like m/1, m/2, etc?

Thanks for noticing this. I must admit that I never considered this scenario.

thanks for the advice.
I added the following warning to Electrum: https://github.com/spesmilo/electrum/commit/ad3be71ed7178881d8c0706588dfb3b3d573691d

(it is displayed before the password is requested)

The clients that offer type-2 deterministic wallets (like electrum and armory) should advise their users that sharing any private key from the derived chain (not the master private key, of course) MUST be avoided. Such a sharing of a private key could happen for example by funding your MtGox account with the "Redeem private key" option.

Recall the suggested computation of the key chains was this:
where S is a random seed.

The use scenario is that a "hot" machine (connected to the internet and potentially vulnerable) generates a chain of public keys, and for that purpose stores Master_public_key as well as S. In a reasonable threat model both values become available to an attacker because the "hot" machine is vulnerable. Since the serial numbers n and the type can be guessed, a single leaked private key will leak Master_private_key as well by a simple substraction in the finite field underlying secp256k1.

Conclusion: Users should be advised that ANY private key from the generated key chain is to be secured with the same security level as the master private key.

This seems to affect not only the implementation of deterministic wallets in electrum and armory but also the hierarchical deterministic wallets suggested in BIP 032:


Suppose the "hot" machine of some main business wants to be able to automatically generate extended public keys (Kn,cn). It needs to store (Kpar,cpar) to do that. Suppose it computes the corresponding extended secret key (kn,cn) on a "cold" machine and hands it to the business' subbranch numbered n, so that the subbranch can work independently. Now, if the information (Kpar,cpar) stored on the main business' "hot" machine leaks then the subbranch can obtatin the main business master private key kpar by these computations:

• I = HMAC-SHA512(Key=cpar, Data=Kpar || n)
• Split I into two 32-byte sequences, IL and IR
• kpar = IL^(-1)*kn (arithmetic in the finite field underlying secp256k1)

Conclusion: In a scenario where derived secret keys are handed over to subbranches, the derived public keys MUST not be generated on the fly on "hot" machines. Instead, even Kpar must be stored "cold". To some extend this contradicts the original idea of hierarchical deterministic wallets.

I'd like to add to this thread the simple explanation why the crypto behind deterministic wallets is sound, i.e. why it's safe to assume that an attacker who only looks at public data (that's sent over the bitcoin network and stored in the blockchain) doesn't have an advantage if the participants use deterministic wallets instead of the regular random-independent wallets. As discussed here, obviously if an attacker obtains the master private key and random seed then he can generate new keys, unlike the case of random-independent wallets, but the focus here is about an attack without access to the secret data.

Since with type-2 deterministic wallet the public keys are generated independently of the master private key, using key homomorphism, it's enough to say why signing transactions with pseudorandom private keys and revealing the signatures is safe from related-key attacks. The only assumption needed is that PRFs (pseudorandom functions) exist, which is a more conservative assumption than PKE exists. In other words it should be safer to assume that sha256 is pseudorandom than that elliptic curves give public-key encryption, though admittedly elliptic curves are used in bitcoin just for digital signatures and not PKE.

So assuming that the hash function h(x)=hash(type|seed|x) is a PRF, a PPT (probabilistic poly time) adversary who's given r_i=h(i) for i=1,2,...,n=poly(security parameter) cannot distinguish them from R_i that are truly random. Now suppose (sk_i,pk_i)=keygen(r_i) and the signatures sgn_i=sign_sk_i(msg_i) are published along with the msg_i, and a PPT adversary A1 can create a signature sgn' for a new msg' so that verify_pk_j(msg',sgn') is true for some j<=n with a non-negligible advantage compared to the case where the keys were generated with keygen(R_i) randomly. This means that there exists another PPT adversary A2 who can distinguish between pseudorandom r_i=h(i) and random R_i sequences with non-negligible probability, simply by taking his input sequence t_i and creating (sk_i,pk_i)=keygen(t_i) and signing sgn_i=sign_sk_i(msg_i), and then simulating A1 by giving it the msg_i and sgn_i signatures and testing whether A1 successfully signs some new msg''. Therefore A2 is a PPT distinguisher and the hash function isn't a PRF, QED by contradiction.

In more simple words, this proof just says that for any efficient computation that you do on peudorandom input, the output of this computation is computationally indistinguishable from that output that you'd get in case you did the computation on truly random data. In this particular case it might seem to be a little confusing because the attacker A1 isn't supposed to be able to efficiently compute a signature for a new message. So it's a proof by contradiction, saying that if such a miraculous A1 actually existed, then we could use it to distinguish between pseudorandom input and random input. Our entire computation is efficient, because the keygen algorithm and the signing algorithm (when we now the secret keys) and the verification algorithm are efficient.

That was a generic argument why pseudorandom keys are safe from related-key attacks, it has nothing to do with bitcoin wallets. However, in the context of bitcoin the optimal behavior of signing only once with each key is also true for deterministic wallets, meaning that an adversary has less than 10 minutes on average to try to attack, under the (even more conservative) assumption that the address hash is a one-way function.

So the bottom line is this: let's say that you have a 10 megabytes file f1 that contains truly random data, and another file f2 that was created by taking 256 truly random bits as a seed and creating the 10 megabytes file f2=(sha256(seed|1),sha256(seed|2),sha256(seed|3),...). If you agree that it's infeasible to tell which file is f1 and which is f2, then a deterministic wallet is right for you. If you disagree, then stick with a random-independent wallet. If you're unsure, then go with a deterministic wallet, it's cryptographically sound and it's much safer/easier in terms of backups.

I like the visual appeal of Armory. The general design, the logo, the name.

Actually, they are.  Sipa has a test branch implementing the deterministic wallets I described above (the HMAC version)... though it will probably a little while before it gets fully tested and merged.   Once that happens, I will add support to Armory for it.

Good work eto.  I think deterministic wallets should be considered for the reference implementation as well.

Mila,

Look at Armory.  It provides exactly what you describe:  keep the full wallet somewhere else (maybe not even touching the internet), create a watching-only copy of it (no private keys), and use that on your website to distribute addresses.  There is no JSON-RPC interface to it (yet!), but I could help you produce a straightforward script along the lines of "getAnotherAddress.py" that will read your watching-only wallet fie, and return the next unused address.

If you want more information, see the presentation on my webpage:  Using Offline Wallets in Armory.  That doesn't show you exactly what to press, but it explains how the process works.  Please PM me if you want help setting it up

This is one of the reasons I created watching-only wallets -- risk-free webservers.  I hope you get some benefit out of it!

I'm interested in deterministic wallets especially how to generate pools of addresses
with the parameter range from-to
I want to have addresses generated on the server side (and not saving the private keys there), offering users unique addresses (tipping jar/donations, sales, etc) while not exposing the public keys to any network.
I found bitaddress script has some limited support for deterministic wallets but I can't use it effectively yet.

I picked a sub-optimal construction, and wished I had talked to gmaxwell and sipa before I commmitted myself to it, because I like theirs better.  However, there's nothing wrong with what I did, it's just that it can be a little slow, and theirs has some nice properties (like random access).  I will be adding support for their method in Armory and deprecating mine (eventually).  Until then, here is both algorithms:

Let the root address be considered keyIndex=0, C be the chaincode, and O be the order of the elliptic curve group:

Mine:
M = doubleSHA256(PublicKey(i)) XOR C
PrivKey(i+1) = (PrivKey(i) * M) mod O


gmaxwell and sipa use HMAC construction; || represents concatenation
PrivKey(n) = SHA256( C || SHA256(C || PubKey(0) || n) )

so how do u get priv/pub keypairs out of the root key/Bitcoin address?

The QR code is the exact same data, but in a QR code.  The primary goal was that you could use the paper backup as both a backup, and a means to transfer a wallet to your smartphone, just by scanning it (there are currently no Bitcoin apps that leverage my wallet format, but I'm getting help to work on one, now).  But it would also be useful if you have a webcam setup for scanning QR codes -- it'll pick up the exact same letters as shown on the page, and you can just copy the text into the "paper backup import" dialog.

For anyone in this thread who has no idea what I'm talking about, the paper backup looks like this:

what does the QR code represent?

The "root key" is a Bitcoin address that serves as the "root node" of the deterministic wallet.  All other addresses are based on it.  The chaincode is another 32-byte number that helps you get from PrivKey(i) to PrivKey(i+1) or PubKey(i) to PubKey(i+1).    In order to have "type 2" deterministic wallets, you will need to be multiply the priv/pub keys by a number... so the chaincode is used to create that number.

As described by gmaxwell, you could easily use lots of different chaincodes to create different address "branches".  Right now, in Armory, there is only one chaincode per wallet.  But you could could add multiple chaincodes to create multiple "branches" that would then appear unrelated -- i.e. you could give someone a watching-only wallet with the first chaincode, another person with a different chaincode but same root public key -- they'll generate two completely different address chains even though they both have the same root public key.  You can generate all private keys in both, but the two people will not be able to generate or even recognize addresses on the other branch.

so this paper backup i generated from Armory consists of a Root Key and a Chain Code.  is the Root Key the same as the Master Private Key discussed here earlier?  whats the Chain Code and where is the Seed?

I agree. If an attacker has access to your system and you don't notice it, he can continue to download new copies of the wallet and if you do notice it, you can generate a new wallet and transfer your money over. So the ability of current wallets to unsteal themselves only applies if:

• The attacker waits rather than stealing your wallet's current contents.
• You unknowingly/accidentally fix the hole he/she used to break into your computer.
• You use up ~100 addresses before the attacker notices he/she no longer has access to your machine.

In high-security scenarios, a better alternative than a set of pregenerated addresses would be to simply create entirely new wallets from time to time. Whether these are deterministic or not makes no difference at that point.

At the same time for normal users a deterministic wallet makes it much easier to protect against a whole range of data loss scenarios. It's much easier to have secure, long-term backups if you don't have to constantly update the backed-up data. As long as it is implemented well, it should be just as secure against theft and much more secure against loss.

If someone steals your wallet, they get all your old addresses and the next 100, but no more.  When you start using addresses, the key pool keeps getting refilled with random addresses based on the random number generator on your computer.  The attacker will generate different (and thus useless) addresses.   Therefore, if someone steals your wallet, it "unsteals" itself after you go through 100 addresses.

Since the point of deterministic wallets is to produce the same sequences of addresses every time, the attacker will always generate the exact same addresses until the end of time.  They have permanently stolen your wallet, and could wait years before executing an attack, if they knew you were going to keep using it.

However, I'm of the opinion that this is basically irrelevant.  The severity of attacks on both types are not much different, and many cases they are the same -- because if the attacker has access to your system to steal it, they can install a process to continue stealing your wallet.  I firmly believe that users' not having sufficient backups is a tremendously more significant risk to their wallets.  As such, deterministic wallets are superior since they only require one backup at time of creation.