Bag of keys vs BIP32

[gmaxwell]

My point is that previously the core devs have suggested an intention to migrate from bag-of-keys to heirarchical deterministic wallets.  The argument, AIUI, is that it simplifies backup, but such a decision would seem to negate the argument given in this thread that Bitcoin is largely safe from ECDSA attacks as long as we avoid address reuse.

It doesn't. This is a spurious claim. (and in Bitcoin-QT we would normally use the type-1 'private' derivation, for primary addresses)

[Roy Badami]

My point is that previously the core devs have suggested an intention to migrate from bag-of-keys to heirarchical deterministic wallets.  The argument, AIUI, is that it simplifies backup, but such a decision would seem to negate the argument given in this thread that Bitcoin is largely safe from ECDSA attacks as long as we avoid address reuse.

It doesn't. This is a spurious claim. (and in Bitcoin-QT we would normally use the type-1 'private' derivation, for primary addresses)

Ah, OK, looking at BIP 32 again, I see the security of the new private derivation is fairly evidently dependent only on the security of HMAC-SHA512, and we have much bigger problems than HD wallets if the SHA-2 family of hash functions has been broken (which I think is highly unlikely).  I'd have to think a bit harder about the implications for the public derivation - maybe it's still safe if no extended public keys have been revealed?

Anyway, sorry to have been propagating FUD (although pesonally I prefer bag-of-keys for other reasons).

roy

[gmaxwell]

Ah, OK, looking at BIP 32 again, I see the security of the new private derivation is fairly evidently dependent only on the security of HMAC-SHA512, and we have much bigger problems than HD wallets if the SHA-2 family of hash functions has been broken (which I think is highly unlikely).  I'd have to think a bit harder about the implications for the public derivation - maybe it's still safe if no extended public keys have been revealed?

Anyway, sorry to have been propagating FUD (although personally I prefer bag-of-keys for other reasons).

Right. Private depends only on HMAC-SHA512 and so does public so long as the extended public key isn't released.  (if signing, adding an unknown value, and signing with the new key breaks security then all ECDSA must be broken, because for any two unrelated signatures there exist an unknown value added to one private key that makes it the same as another).

I agree that more entropy is better, but we have to think about security holistically.  Bag of keys is not superior if the difficulty in backing it up forces you into less secure practices.  Likewise, if your funds are lost to you it doesn't really matter to you if they were lost because of the difficulty in making backups or because of a thief performing a complicated attack (though there are some differences in systemic risk, I think they are small here: Backup mistakes tend to happen randomly while a thief could hit everyone at once).

Though I'm responsible for the existence of the public derivation, its not my favorite where its special properties are not important... DSA itself has security which is not reducible to any simple statement about the hardness of the DLP.  Though several experienced minds have looked at our public derivation and believe it is solid and that problems seem unlikely, since the security of DSA itself does not have the strongest theoretical grounds I don't think that anyone can make you any promises about the non-existence of "related signature attacks" in the public derivation for an attacker that knows the extended public key. But the security of the private derivation should be very good (and public, if the extended key is not known), considering weak RNG exposure perhaps better than bag of keys, and certainly better when considering data loss risk.

Thank you so much for taking the time to (re)review the BIP and consider the security. Having more eyes on it is part of how it becomes secure.

[Roy Badami]

[Thank you so much for taking the time to (re)review the BIP and consider the security. Having more eyes on it is part of how it becomes secure.

I'm not sure my opinion here counts for much here (I'm no cryptologist - just an IT professional with a basic working knowledge of the field).  But thank you so much for taking the time to give me a detailed response.

As for my preference for bag of keys - I should perhaps amplify.  Mainly, it's that I have a dislike for secrets that must be kept forever - particularly if they're going to be kept on a machine that is online.  I therefore think that private keys should come with an expiry date, after which the wallet should sweep them into new addresses, and it seems to me that this process would be better as a continuous process rather than having to wholesale throw away the root of your HD wallet and move all your coins at once.

The reason I'm against indefinite key lifetimes is mainly because the security consequences of this requirement are counter-intuitive to the average user.  The fact that someone might find a backup you made years ago, with a passphrase that was compromised (because you used the same password in multiple contexts) probably doesn't concern you, because you take security much more seriously now and have long since changed your passphrase to something strong and specific to that purpose, and you assume you're therefore safe.

Whilst there's nothing we can do to completely protect users from the falacy that changing their passphrase mitigates against a passphrase compromise in the same way it does with regular login passwords, limiting key lifetime at least limits the window of opportunity in which such compromises are exploitable.

Backups are of course important.... but I think people at least find the requirement intuitive...

roy

[gmaxwell]

I've split the thread since we've gone offtopic:

As for my preference for bag of keys - I should perhaps amplify.
[...]
The reason I'm against indefinite key lifetimes is mainly because the security consequences of this requirement are counter-intuitive to the average user.
[...]
Backups are of course important.... but I think people at least find the requirement intuitive...

Key management is super-duper important, and also super hard and I certainly agree with the usefulness of finite key lifetimes.

What I've found is that backups are only intuitive if you must backup every time you get a new address (and only then). This unworkable unless you constantly reuse a small number of addresses, and the reuse is itself both bad key management and devastating for privacy.  As soon as you introduce the keypool people are completely confused by the backup requirements, and we get the worst of all worlds: Constant reuse (hurting privacy and preventing old keys from aging out), and missed backups resulting in coin loss.

I think using BIP32 use isn't completely incompatible with good key management though.  E.g. the backup UI could present an option to "Expire old keys after verifying backup" which would create a new additional master seed and save that in the backup.   If you want to be more elaborate, it could automatically make a new master seed right before your backup if the last one was generated more than three months ago... and then have a UI option that lets you switch how old the backups you want to still be good (e.g. which master key its using for new addresses)— it could even have an option to move any remaining funds to new keys.

The important thing here is that it decouples usage patterns from key management. E.g. making 100 txn today shouldn't make your backup expire right away, and then you don't make 100 over the next two years and it doesn't expire.

Whilst there's nothing we can do to completely protect users from the falacy that changing their passphrase mitigates against a passphrase compromise

The above rotation ideas could be triggered by passphrase change, by default. If coupled with a feature to automatically move funds to new addresses it would actually protect users from that falacy.. by making it true.