Mini private key, PBKDF2 rounding

[ThePiachu]

There are two formats of mini private keys, one is based on SHA-256, other on PBKDF2. In the instructions for decoding the second one,
https://en.bitcoin.it/wiki/Mini_private_key_format#Example_with_PBKDF2
we read:

"The iteration count is determined as follows: 2 ^ (n/4) rounded to the nearest integer, where n is the second byte."

Does the rounding refer to the value of (n/4), or 2 ^ (n/4)? For example, for n=9, we have:

n/4=9/4=2.25
2^(n/4)=2^(9/4)=4.75682846

If we round the result of the second equation, we get 5, but if we round the result of the first equation, we get:

2^2=4

Moreover, should the division by 4 should be carried out arithmetically (rounding the number to nearest integer, with 0.5 being rounded up), or by a logical shift (the number is rounded down).

Where should one apply rounding for calculating the proper PBKDF2-encoded mini private key?

[DeathAndTaxes]

Very good question.  For people who might make keys I guess the safe thing is to keep n divisible by 4 but it does need an explicit clarification.

I am looking to launch BitCardz in the coming months and have considered the safer/stronger PBKDF2 format but the lack of support means I likely will use SHA-256 method.

[ThePiachu]

Personally, I'd bit shift n, as it seems the "programmers'" way to go.

[DeathAndTaxes]

Personally, I'd bit shift n, as it seems the "programmers'" way to go.

I think you are right but assumptions in protocols can be dangerous.  Even if you are right the next developer might not be.  It should be clearly indicated and include an example where n % 4 != 0.

[ThePiachu]

Hmm, most of the Wiki on the topic seems to be written by Casascius, best discuss the details with him...

[Ean]

If you're going to round (n / 4) I don't see any point of having the division at all.

And the problem with numbers ending in .5 only affects 205, 206 and 207 (if I calculated it right, but it can be some kind of rounding error). The highest accepted number now, accorsing to the wiki, is 64.

[casascius]

The minikey as I have implemented it and used it is always SHA256.

If someone is interested in PBKDF2, please edit the proposal to conform to how you're using it, since you'll be the first.  The developers have expressed an interest in favoring SHA256 over SHA1 (if SHA1 is used, they're likely to never accept it into the mainline client).  I would also prefer that PBKDF2 be signaled by an initial letter of "P" instead of "S" (which will avoid lots of ambiguities during troubleshooting - it will help make it obvious to a human troubleshooter which algorithm to use, which is otherwise impossible to compute just by looking.)

Also please ensure that any implementation does not require that a website operator spend too much CPU time to check a key.  Keep in mind the possibility of a user doing a DoS attack by attempting to redeem lots of bogus minikeys, if those minikeys were encoded to call for a large amount of CPU time to compute.  There needs to be a hard limit on iterations (possibly one that could be scaled up).

To clarify my intent with the rounding, it is 2 ^ (n/4) computed in floating point, then rounded to the nearest integer where 0.5 rounds up, so 5 is the answer.  This likewise hasn't been set in stone.  If you notice something is ambiguous, just change it to something that's not.  Perhaps it might be better to simply calculate this, and alter the proposal so a simple lookup table of integers is used, rather than a formula that will confuse future users.  That will also keep floating point calculations out of the algorithm, which I suppose is bad style if anything.  Remember, nobody is using these yet, so it's safe to blaze the trail.

[ThePiachu]

Okay, so I propose the following:

The minikey encoded with PBKDF2 should:
-Consists of 22, 26, or 30 alphanumeric characters from the base58 alphabet used in Bitcoin
-Start with the letter "P" to distinguish itself from SHA-256 encoding
-When SHA-256 hashed with the appended "?" at the end, the first byte must be 0x01
-The second byte of the hash determines the iteration count that will be passed into the PBKDF2 function. The iteration count is determined as follows:
    * 2 ^ (n>>2), where n is the second byte.
-The second byte must be lower than 0x30, giving maximum of 16384 iterations
-The salt string is "Satoshi Nakamoto"

Does this sound acceptable?

[Ean]

(n>>2)

I can't see the point of this. Why not just use (n) without division/shift?

[ThePiachu]

Creating new keys is 4 times as easy, as you need not hit as low a number (48 instead of 12)?

[DeathAndTaxes]

(n>>2)

I can't see the point of this. Why not just use (n) without division/shift?

It could be done but it would make bulk generation (for something like physical bitcoins, or offline wallets) even more difficult.

The reason is creation of minikeys can only be done by brute force.  It is already somewhat computationally significant.

1) You take a random mini key add ? and hash it.  If first byte is not 0x01 discard it.  So it will take 256 hashes to generate one potentially good key.
2) Now you look at the second byte.  With 4 possible values you can set precision you want w/ only 256/4 = 64 attempts (each requiring 256 attempts).  

Thus to make 1 valid minikey would require
n/4 method 256*(256/4) = requires average 16,384 hashes
full n method 255*256 = requires on average 65,536 hashes.

Still that might be ok.  For bulk generation 16,384 hashes per potential key is already too heavy so am now convinced I will be using SHA-256 method.  For someone generating a handful of keys the 65K requirement wouldn't be a burden.  OpenCL code even on a mid range CPU can do 2M to 10M hashes per second.

[casascius]

Okay, so I propose the following:

The minikey encoded with PBKDF2 should:
-Consists of 22, 26, or 30 alphanumeric characters from the base58 alphabet used in Bitcoin
-Start with the letter "P" to distinguish itself from SHA-256 encoding
-When SHA-256 hashed with the appended "?" at the end, the first byte must be 0x01
-The second byte of the hash determines the iteration count that will be passed into the PBKDF2 function. The iteration count is determined as follows:U
    * 2 ^ (n>>2), where n is the second byte.
-The second byte must be lower than 0x30, giving maximum of 16384 iterations
-The salt string is "Satoshi Nakamoto"

Does this sound acceptable?

Recommended changes:

1.  pbkdf2 use HMAC based on sha256 not sha1.

[gmaxwell]

Recommended changes:
1.  pbkdf2 use HMAC based on sha256 not sha1.

Absolutely.

I'm not superkeen on the weird salt string. We really don't need any more mystic Satoshi worship around here. Just make it something boring like "pbkdf2minikey".

The iteration count function should also not allow stupidly small values 2^((n>>2)+13) would be more reasonable.  This should speed up generation for most sane cases, as it will avoid values tuning up to be too weak to be usable.

[Ean]

It could be done but it would make bulk generation (for something like physical bitcoins, or offline wallets) even more difficult.

The reason is creation of minikeys can only be done by brute force.  It is already somewhat computationally significant.

1) You take a random mini key add ? and hash it.  If first byte is not 0x01 discard it.  So it will take 256 hashes to generate one potentially good key.
2) Now you look at the second byte.  With 4 possible values you can set precision you want w/ only 256/4 = 64 attempts (each requiring 256 attempts).  

Thus to make 1 valid minikey would require
n/4 method 256*(256/4) = requires average 16,384 hashes
full n method 255*256 = requires on average 65,536 hashes.

Still that might be ok.  For bulk generation 16,384 hashes per potential key is already too heavy so am now convinced I will be using SHA-256 method.  For someone generating a handful of keys the 65K requirement wouldn't be a burden.  OpenCL code even on a mid range CPU can do 2M to 10M hashes per second.

If you are going to disgard two bits, why not disgard the two most significant (n & 0x3F)?

[ThePiachu]

Same complexity, similar results.