Bitcoin Forum
December 06, 2016, 08:01:58 PM *
News: Latest stable version of Bitcoin Core: 0.13.1  [Torrent].
 
   Home   Help Search Donate Login Register  
Pages: [1]
  Print  
Author Topic: Mini private key, PBKDF2 rounding  (Read 1671 times)
ThePiachu
Sr. Member
****
Offline Offline

Activity: 442



View Profile WWW
January 12, 2012, 11:31:46 AM
 #1

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?

1HWbVLhxj7bhewhyapMZpyhqWAeAhJd51E
My Bitcoin Calculator:
http://tpbitcalc.appspot.com/
1481054518
Hero Member
*
Offline Offline

Posts: 1481054518

View Profile Personal Message (Offline)

Ignore
1481054518
Reply with quote  #2

1481054518
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1481054518
Hero Member
*
Offline Offline

Posts: 1481054518

View Profile Personal Message (Offline)

Ignore
1481054518
Reply with quote  #2

1481054518
Report to moderator
1481054518
Hero Member
*
Offline Offline

Posts: 1481054518

View Profile Personal Message (Offline)

Ignore
1481054518
Reply with quote  #2

1481054518
Report to moderator
DeathAndTaxes
Donator
Legendary
*
Offline Offline

Activity: 1218


Gerald Davis


View Profile
January 12, 2012, 02:10:54 PM
 #2

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
Sr. Member
****
Offline Offline

Activity: 442



View Profile WWW
January 12, 2012, 02:21:03 PM
 #3

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

1HWbVLhxj7bhewhyapMZpyhqWAeAhJd51E
My Bitcoin Calculator:
http://tpbitcalc.appspot.com/
DeathAndTaxes
Donator
Legendary
*
Offline Offline

Activity: 1218


Gerald Davis


View Profile
January 12, 2012, 02:23:15 PM
 #4

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
Sr. Member
****
Offline Offline

Activity: 442



View Profile WWW
January 12, 2012, 02:28:43 PM
 #5

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

1HWbVLhxj7bhewhyapMZpyhqWAeAhJd51E
My Bitcoin Calculator:
http://tpbitcalc.appspot.com/
Ean
Full Member
***
Offline Offline

Activity: 199



View Profile
January 12, 2012, 03:06:04 PM
 #6

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.

Quote from: Douglas Adams
The World Wide Web is the only thing I know of whose shortened form takes three times longer to say than what it's short for
casascius
Mike Caldwell
VIP
Legendary
*
Offline Offline

Activity: 1344


The Casascius 1oz 10BTC Silver Round (w/ Gold B)


View Profile WWW
January 12, 2012, 03:07:53 PM
 #7

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.

Companies claiming they got hacked and lost your coins sounds like fraud so perfect it could be called fashionable.  I never believe them.  If I ever experience the misfortune of a real intrusion, I declare I have been honest about the way I have managed the keys in Casascius Coins.  I maintain no ability to recover or reproduce the keys, not even under limitless duress or total intrusion.  Remember that trusting strangers with your coins without any recourse is, as a matter of principle, not a best practice.  Don't keep coins online. Use paper wallets instead.
ThePiachu
Sr. Member
****
Offline Offline

Activity: 442



View Profile WWW
January 12, 2012, 04:51:24 PM
 #8

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?

1HWbVLhxj7bhewhyapMZpyhqWAeAhJd51E
My Bitcoin Calculator:
http://tpbitcalc.appspot.com/
Ean
Full Member
***
Offline Offline

Activity: 199



View Profile
January 12, 2012, 04:58:40 PM
 #9

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

Quote from: Douglas Adams
The World Wide Web is the only thing I know of whose shortened form takes three times longer to say than what it's short for
ThePiachu
Sr. Member
****
Offline Offline

Activity: 442



View Profile WWW
January 12, 2012, 05:06:22 PM
 #10

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

1HWbVLhxj7bhewhyapMZpyhqWAeAhJd51E
My Bitcoin Calculator:
http://tpbitcalc.appspot.com/
DeathAndTaxes
Donator
Legendary
*
Offline Offline

Activity: 1218


Gerald Davis


View Profile
January 12, 2012, 05:08:37 PM
 #11

(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
Mike Caldwell
VIP
Legendary
*
Offline Offline

Activity: 1344


The Casascius 1oz 10BTC Silver Round (w/ Gold B)


View Profile WWW
January 12, 2012, 05:22:12 PM
 #12

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.

Companies claiming they got hacked and lost your coins sounds like fraud so perfect it could be called fashionable.  I never believe them.  If I ever experience the misfortune of a real intrusion, I declare I have been honest about the way I have managed the keys in Casascius Coins.  I maintain no ability to recover or reproduce the keys, not even under limitless duress or total intrusion.  Remember that trusting strangers with your coins without any recourse is, as a matter of principle, not a best practice.  Don't keep coins online. Use paper wallets instead.
gmaxwell
Moderator
Legendary
*
qt
Online Online

Activity: 2030



View Profile
January 12, 2012, 06:29:33 PM
 #13

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
Full Member
***
Offline Offline

Activity: 199



View Profile
January 12, 2012, 06:50:28 PM
 #14

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

Quote from: Douglas Adams
The World Wide Web is the only thing I know of whose shortened form takes three times longer to say than what it's short for
ThePiachu
Sr. Member
****
Offline Offline

Activity: 442



View Profile WWW
January 14, 2012, 11:05:39 PM
 #15

Same complexity, similar results.

1HWbVLhxj7bhewhyapMZpyhqWAeAhJd51E
My Bitcoin Calculator:
http://tpbitcalc.appspot.com/
Pages: [1]
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!