Post
Topic
Board Development & Technical Discussion
Re: Password-protected private key export format
by
casascius
on 10/08/2011, 19:56:16 UTC
The difference between an 8 byte salt and a 4 byte salt isn't 4 bytes, and it isn't a factor of 2.  It is a factor of over 4 billion.  It is the difference between "Got a minute?" and "Sometime after the end of the universe".

In reality, it is probably not that big of a deal.  Precomputing AES tables isn't a trivial task, and even 4 or 5 bits of salt is probably enough to make it impractical for well beyond the potential lifetime of one of these protected keys.

But cryptosystems are designed with defense in depth for very good reasons.  When a weakness in one part is discovered, it is usually not a catastrophe because we have added redundant security measures.

So, the question is:  Is saving a few keystrokes, maybe several times per year for maybe a couple billion users, worth the slight risk that an AES break won't be "phew, gotta upgrade", but instead be "All your addresses are belong to us"?  I would vote for the extra keystrokes, but that might just be me.

By the way, this is a nifty idea.  One thought that came to mind was embedding metadata into the key itself using DER.  Since these keys are not usable on the network, they should maybe not be assigned a key version prefix.

I think this argument sort of sidesteps the purpose of salt however.  The salt is not secret - it's coded plainly into the encrypted key and freely available to an attacker - so beyond a certain point, it doesn't really matter how many bits it is.  The whole point of salt if I understand correctly is just to make it infeasible to crack a whole batch at the same time with the same effort (such as with a pre-generated rainbow table), forcing the attacker to concentrate on cracking one key at a time.  If I am right, then the salt needs only enough bits so as to be unlikely to collide with other codes that might be acquired by the same attacker and cracked within the same batch.

EDIT: I would even recommend that fewer bits went into the password check.  Like, maybe as few as 8.  This will make it even more expensive to brute force passwords, as it will result in an enormous number of false positives that can only be checked by doing a time-consuming EC multiply (to derive the bitcoin address) and a database lookup (to see if there are any coins at that address, only to find there are none).  In the event of a typo, even with 8 bits, still a >99% chance it will still be caught.  The password check as it stands is probably just a gift to an attacker.