Pages:
Author

Topic: Proposal: Base58 encoded HD Wallet root key with optional encryption (Read 21003 times)

newbie
Activity: 13
Merit: 16
Is anyone still working on this?
newbie
Activity: 39
Merit: 0
So, is this proposal stable enough now to turn into a formal BIP?  Is this in progress already? I would like to add a second implementation of this, as part of my bip32utils package.

Finally, would it be too much of a stretch to be able to use this encoding as way to export an extended private key from inside the hierarchy, instead of at the root?  It would fit in the "64 byte root key" encoding.
member
Activity: 98
Merit: 10
I think the false positive rate of the bloom filter is a bit too high for comfort.

Unfortunately, it's already fully optimized for two inserted elements.

The 16-bit filters will offer better password checking, and they will also have a high enough false positive rate to frustrate attackers.
staff
Activity: 4284
Merit: 8808
The two 16-bit hashes is fine by me. It would remove a bit of functionality, but 99% of use cases probably just want two passwords.
If you really want more than two, you could search for either a seed or set of passwords (if the seed is fixed by prior use, since password searching is strictly slower) resulting in check value sharing.

I'm not sure how valuable the blockchain scan is, since what you'd do there is extract all addresses seen in the blockchain into a bloom filter ... one which fits in L3 cache can have a low enough false positive rate to be effective.
member
Activity: 116
Merit: 10
The bloom basically gives us 2 things, an easy way to detect typo's and in the event of a brute-force attack, it yields a significant number of false positives which all require a full scan of the blockchain, which I thought was a nice trade-off for the lower number of entropy bits.

If that first feature is somehow not effective enough, we could either tweak the bloom arguments or move to the 16 bit method that gmaxwell proposed.
member
Activity: 98
Merit: 10
Agreed. The bloom filter does not perform as well as expected.

The two 16-bit hashes is fine by me. It would remove a bit of functionality, but 99% of use cases probably just want two passwords.
staff
Activity: 4284
Merit: 8808
I did a simple empirical test of the false positive rate, mostly to check to see how much rejecting results with too many bits set improved things, and because I'm too lazy to check the math. I found much lower performance than expected:


#include
#include
#include /*random()*/
#include

uint32_t toflt(uint64_t x)
{
  int i;
  uint32_t result=0;
  for(i=0;i<11;i++)
  {
    result |= 1U<<(x&31);
    x>>=5;
  }
  return result;
}

int chkflt(uint32_t flt, uint64_t x)
{
  int i;
  uint32_t flt2=0;
  int result=1;
  for(i=0;i<11;i++)
  {
    if (!((1U<<(x&31))&flt)){
      result=0;
      break;
    }
    flt2 |= 1U<<(x&31);
    x>>=5;
  }
  if (__builtin_popcount(flt&(~flt2))>11)return 0;
  return result;
}

int main(int argc, char **argv)
{
  int i;
  uint64_t total=0;
  uint64_t fp=0;
  (void)argc;
  (void)argv;
  assert(RAND_MAX == 2147483647);
  for(i=0;i<9973;i++)
  {
    int j;
    uint64_t x;
    uint64_t y;
    uint32_t flt;
    x = ((uint64_t)random()<<24)^random();
    y = ((uint64_t)random()<<24)^random();
    flt = toflt(x)|toflt(y);
    for(j=0;j<1021;j++){
      uint64_t x2;
      int match;
      x2 = ((uint64_t)random()<<24)^random();
      match = chkflt(flt,x2);
      if (x2==x || x2==y){
        if(!match){
          printf("Something bad happened.\n");
          exit(1);
        } else {
          continue;
        }
      }
      total++;
      fp+=match;
    }
  }
  printf("%llu false positives out of %llu tests.\n",(long long unsigned)fp,(long long unsigned)total);
  return 0;
}


Which yields 7508 false positives out of 10182433 tests or 8148 with the too-many test disabled.

I think thats an unacceptably high failure rate.  The one of two 16 bit check values approach gets me 289 with the same sequence. (I could argue that the 16 bit check is too lossy too, considering that someone might get the password wrong, use the result to generate public keys, then later be able to recover the funds— but I think on the balance the denyability feature is pretty good.)

What am I screwing up here? A copy using /dev/urandom instead of random() gets the same results, so it's not just random() having some odd correlations or a low period.
member
Activity: 116
Merit: 10
member
Activity: 98
Merit: 10
I'll send this proposal off to riplin:

4. Calculate "preH" = PBKDF2-HMAC-SHA512(key = salt, msg = passphrase, iterations = 10000, output_len = 64)
5. Calculate "strongH" = KDF(msg = preH[0:32], salt = preH[0:32], output_len = 64) This step can be outsourced to a 3rd party, if desired.
6. Calculate "H" = PBKDF2-HMAC-SHA512(msg = preH, salt = strongH, iterations = 1, output_len = len(root_key) + 32)


I've generated the relevant test vectors as well.

member
Activity: 98
Merit: 10

Quote
Even in the way we have it set up now, if an attacker can get their hands on strongH as well as the encrypted wallet, they can skip the first 8192 rounds of PBKDF2, hence the last 2048 rounds. Basically just extra safety against a dictionary attack on both strongH and the wallet.

The structure I gave has the same property.  Smiley   If you have StrongH and the encrypted wallet you still need the whole output of the initial KDF, which means you need to know or guess the password and grind the initial KDF.


Good thinking. However, H must be PBKDF2-HMAC-SHA512 with >= 1 round, so that we can produce an H of arbitrary length. I'm down for this change.
staff
Activity: 4284
Merit: 8808
The false positive rate with two keys in the filter is about 1 in 40,000. A bit better than the false positive rate of two 16-bit filters, which is about 1 in 33,000 (if my reasoning is correct).
Sounds good. Yes, it would be ~1/65536*2.  I was about to suggest something where you need N of M of even smaller checksums and then realized that the bloom filter is basically the limit case of that.   If you don't want to support more than two values, you could specify having more than 11 extra 1s is also regarded as a false match.   E.g. if this key only sets 8 ones and there are 20 set in the filter (including these) then then also regard it as a false positive (because there is no possible single second value which would result in more than 11 bits being set).

Quote
Even in the way we have it set up now, if an attacker can get their hands on strongH as well as the encrypted wallet, they can skip the first 8192 rounds of PBKDF2, hence the last 2048 rounds. Basically just extra safety against a dictionary attack on both strongH and the wallet.
The structure I gave has the same property.  Smiley   If you have StrongH and the encrypted wallet you still need the whole output of the initial KDF, which means you need to know or guess the password and grind the initial KDF.
member
Activity: 98
Merit: 10
Snazzy approach to denyablity. I certantly like it better than what some other people have done.

Do you have any number on the false positive rate for the no-specified second key?  How does it compare to "two 16 bit check values, ordered randomly"? Presumably its better when there is no second key or where you've done some brute force search to find two that share their bloom bits?

The false positive rate with two keys in the filter is about 1 in 40,000. A bit better than the false positive rate of two 16-bit filters, which is about 1 in 33,000 (if my reasoning is correct).

You *could* avoid inserting a second key, but we required a second key in the spec so that all users have plausible deniability. E.g. "We see there are more than 11 bits in your bloom filter. A user with nothing to hide would have no second password, so you must be hiding something!"


Is there an advantage I'm not seeing to this approach instead of

preH=PBKDF2-HMAC-SHA512(salt,passphrase)
strongH=KDF(preH[first 256 bits])
H = HMAC-SHA512(preH,strongH)


Even in the way we have it set up now, if an attacker can get their hands on strongH as well as the encrypted wallet, they can skip the first 8192 rounds of PBKDF2, hence the last 2048 rounds. Basically just extra safety against a dictionary attack on both strongH and the wallet.

I just figured it was more likely for a compromised delegatee to leak preH/postH and not the encrypted wallet (since the delegatee doesn't necessarily know encrypted wallet), so I suggested protecting more against leaking preH/postH than against leaking preH/postH *and* the encrypted wallet.
staff
Activity: 4284
Merit: 8808
Quote
4. Calculate "preH" = PBKDF2-HMAC-SHA512(key = salt, msg = passphrase, iterations = 213, output_len = 64)
5. Calculate "strongH" = KDF(msg = preH, salt = preH, output_len = 64) This step can be outsourced to a 3rd party, if desired.
6. Calculate "postH" = PBKDF2-HMAC-SHA512(key = passphrase, msg = salt, iterations = 210, output_len = 64)

Is there an advantage I'm not seeing to this approach instead of

preH=PBKDF2-HMAC-SHA512(salt,passphrase)
strongH=KDF(preH[first 256 bits])
H = HMAC-SHA512(preH,strongH)

?

This construction seems simpler and faster—or, more importantly, would allow moving the computation budget from postH into preH where it could add more strength against dictionary attack by the delegatee.

staff
Activity: 4284
Merit: 8808
Snazzy approach to denyablity. I certantly like it better than what some other people have done.

Do you have any number on the false positive rate for the no-specified second key?  How does it compare to "two 16 bit check values, ordered randomly"? Presumably its better when there is no second key or where you've done some brute force search to find two that share their bloom bits?
member
Activity: 116
Merit: 10
Changed the preH and postH calculation, updated the test vectors.
member
Activity: 98
Merit: 10
Suggestion: Replace all instances of bare HMAC-SHA512 with PBKDF2-HMAC-SHA512, like so.

Code:
preH = PBKDF2-HMAC-SHA512(salt, passphrase, 8192, 64)
strongH = hash_function(preH, preH, 64)
postH = PBKDF2-HMAC-SHA512(passphrase, salt, 1024, 64)
H = PBKDF2-HMAC-SHA512(postH, strongH, 1024, len(root_key) + 32)

A tiny bit of extra computational time (a few seconds on a slow ARM, a few milliseconds on a PC; small compared to the time spent on strongH), but offers a lot of extra protection in the event preH is compromised. Also makes the code a bit more consistent.
member
Activity: 116
Merit: 10
Updated wording of parts of the spec.
member
Activity: 116
Merit: 10
No. Due to how BIP32 works, that's not possible. The initial key in BIP32 is not derived using ECC, but is generated using HMAC-SHA512. So the same trick as used in BIP38 is not possible.
member
Activity: 118
Merit: 10
Please excuse my ignorance, but does this spec allow for the "intermediate code" that BIP38 uses?  Ie. would it be possible for a third party to generate you a passphrase-protected HD wallet, with them having no knowledge of the passphrase?

The question might already be answered in the spec but I couldn't spot it.

Thanks
member
Activity: 98
Merit: 10
Updated reference implementation. Now supports newest spec, as well as secondary "fake" passwords.

https://github.com/wyager/Encrypted-HD-wallet
Pages:
Jump to: