Show Posts
adaseb,
Your math is more or less within the right order of magnitude, but is missing a few things.
First, you need SHA512, not SHA256.
Next, for each seed you try, you need to check its "checksum" with HMAC-SHA512, so that's 2x SHA512's, not one.
1 in 256 of the seeds you try will pass the checksum step above, and with these you'll need to run PBKDF2-HMAC-SHA512 with 2048 iterations (and each iteration requires 2x SHA512's) to get the xprv. This means on average, you'll need another 16x SHA512's per seed tried (so your initial estimate was 18x too small).
Once you have a potential xprv, you still need to check if it's in use. This means deriving a bunch of private keys from the xprv (let's say we derive 30ish keys on both the internal and external chains, using both BIP32 and BIP44 style paths). Now we're looking at 120+ EC operations per seed which passes the checksum step (on average 1 EC operation for every 2 seeds you initially try). There is also another HMAC-SHA512, SHA256, and RIPEMD operation per address that's generated.
Finally, we need a whole bunch of CAMs to look up (in parallel) these addresses in the UTXO set (which has about 43M entries today). I'm not sure how big CAMs get these days, but I can say that a 43M-entry cam is at least 10x or 20x bigger than anything commonly used in networking gear.
We can shift some things around a bit (generate fewer private keys/addresses, but search in the every-address-every-used set which is 10x bigger), but it remains a daunting task.
Of course, if we have this theoretical hardware mentioned above that can do silly-fast EC operations, it makes a lot more sense to just choose a public key visible on the blockchain which has a large UTXO value and attack it directly (which would take only on the order of 2^128 EC operations). In any case, it seems pretty likely it would take longer than current the age of the universe to succeed--personally I'm not that patient.
So yes, "12 worded seeds [are] really secure from Brute force".
Your math is more or less within the right order of magnitude, but is missing a few things.
First, you need SHA512, not SHA256.
Next, for each seed you try, you need to check its "checksum" with HMAC-SHA512, so that's 2x SHA512's, not one.
1 in 256 of the seeds you try will pass the checksum step above, and with these you'll need to run PBKDF2-HMAC-SHA512 with 2048 iterations (and each iteration requires 2x SHA512's) to get the xprv. This means on average, you'll need another 16x SHA512's per seed tried (so your initial estimate was 18x too small).
Once you have a potential xprv, you still need to check if it's in use. This means deriving a bunch of private keys from the xprv (let's say we derive 30ish keys on both the internal and external chains, using both BIP32 and BIP44 style paths). Now we're looking at 120+ EC operations per seed which passes the checksum step (on average 1 EC operation for every 2 seeds you initially try). There is also another HMAC-SHA512, SHA256, and RIPEMD operation per address that's generated.
Finally, we need a whole bunch of CAMs to look up (in parallel) these addresses in the UTXO set (which has about 43M entries today). I'm not sure how big CAMs get these days, but I can say that a 43M-entry cam is at least 10x or 20x bigger than anything commonly used in networking gear.
We can shift some things around a bit (generate fewer private keys/addresses, but search in the every-address-every-used set which is 10x bigger), but it remains a daunting task.
Of course, if we have this theoretical hardware mentioned above that can do silly-fast EC operations, it makes a lot more sense to just choose a public key visible on the blockchain which has a large UTXO value and attack it directly (which would take only on the order of 2^128 EC operations). In any case, it seems pretty likely it would take longer than current the age of the universe to succeed--personally I'm not that patient.
So yes, "12 worded seeds [are] really secure from Brute force".
Your Explanation is excellent. And I still have one question. Since it has a very little chance to have the same seed, I think it could be used for one UUID variant? Do you have any idea about it?
