Proposal: Base58 encoded HD Wallet root key with optional encryption

[niniyo]

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

[1715162113]

1715162113

[1715162113]

1715162113

[1715162113]

1715162113

[1715162113]

1715162113

[1715162113]

1715162113

[riplin]

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.

[riplin]

Updated wording of parts of the spec.

[wyager]

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.

[riplin]

Changed the preH and postH calculation, updated the test vectors.

[gmaxwell]

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?

[gmaxwell]

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.

[wyager]

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.

[gmaxwell]

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).

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.     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.

[wyager]

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.     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.

[wyager]

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.

[riplin]

Updated.

[gmaxwell]

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 <stdio.h>
#include <stdint.h>
#include <stdlib.h> /*random()*/
#include <assert.h>

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.

[wyager]

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.

[riplin]

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.

[gmaxwell]

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.

[wyager]

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.

[Johnathan]

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.

[sjors]

Is anyone still working on this?