It is just "firstAddedValue" multiplied by base point G.
Edit: some more complex example:
path: "0/SHA-256('bitcointalk.org')/5321992/SHA-256('coinlatte')"
masterPrivateKey: 1c4f3bbd6703e3eb65040b37669046da93009b024aad0cef1b3cc57157e388ec
masterPublicKey: 02 a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c540c5bd
firstAddedData:
a34b99f2 2c790c4e 36b2b3c2 c35a36db
06226e41 c692fc82 b8b56ac1 c540c5bd
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
masterPrivateKey: 1c4f3bbd6703e3eb65040b37669046da93009b024aad0cef1b3cc57157e388ec
firstAddedValue: db26845476a175bd67c1e2b96812ea4aaa772f401fd23edabb98155e53d6b612
firstPrivateKey: f775c011dda559a8ccc5edf0cea331253d77ca426a7f4bc9d6d4dacfabba3efe
masterPublicKey: 02 a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c540c5bd
firstAddedPoint: 02 b87ef5ad03264ef973f7f1a710397f2aa365dd7c48514550aee83ac9c2cb4183
firstDerivedKey: 02 1dbe25ac1b430b911bda0f22d11c65a6e0fcc4861ac2a56ae8e8db27fd82ebd5
SHA-256("bitcointalk.org"): f245bd5620ee79314f48d9e9641a5406bd03745f6ac516e2801ef6ccbfe40ced
secondAddedData:
1dbe25ac 1b430b91 1bda0f22 d11c65a6
e0fcc486 1ac2a56a e8e8db27 fd82ebd5
f245bd56 20ee7931 4f48d9e9 641a5406
bd03745f 6ac516e2 801ef6cc bfe40ced
firstPrivateKey: f775c011dda559a8ccc5edf0cea331253d77ca426a7f4bc9d6d4dacfabba3efe
secondAddedValue: 96c14d3fdf2e9864881489162888d20822e9a8737d922975d2846566fc7efa0c
secondPrivateKeyNegative: 8e370d51bcd3f20d54da7706f72c032ea5b295cf38c8d503e986e1a9d802f7c9
secondPrivateKey: 71c8f2ae432c0df2ab2588f908d3fcd014fc4717767fcb37d64b7ce2f8334978
firstDerivedKey: 02 1dbe25ac1b430b911bda0f22d11c65a6e0fcc4861ac2a56ae8e8db27fd82ebd5
secondAddedPoint: 02 258b3ca9f770ef770667979d25619331ced43781f0b5e910fca03048631e7fdd
secondPublicKey: 03 3bd31277f4501c0a3ec6cba83d320f2991060ca6b9709e256537d221b33f499a
secondDerivedKey: 02 3bd31277f4501c0a3ec6cba83d320f2991060ca6b9709e256537d221b33f499a
hexNonce(5321992): 0000000000000000000000000000000000000000000000000000000000513508
thirdAddedData:
3bd31277 f4501c0a 3ec6cba8 3d320f29
91060ca6 b9709e25 6537d221 b33f499a
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00513508
secondPrivateKey: 71c8f2ae432c0df2ab2588f908d3fcd014fc4717767fcb37d64b7ce2f8334978
thirdAddedValue: c18d4399f29d74188d9abb1224b419898a41396426b34bf1d1f74e70284c0dba
thirdPrivateKey: 3356364835c9820b38c0440b2d88165ae48ea394edea76ede8706cc6504915f1
secondDerivedKey: 02 3bd31277f4501c0a3ec6cba83d320f2991060ca6b9709e256537d221b33f499a
thirdAddedPoint: 03 431bb4ae33a5ca7fc2f0394b09d2c6882ae6077eb861e3cb8c4be700a0ff8f71
thirdDerivedKey: 02 099f41117ea008c165847e75483d34384a9f36c2afe81176f38e58c512d2a70e
SHA-256("coinlatte"): 314870494d3a9136ba0a67ceb33534cbd438e982105d20cc076204c6fc99594d
fourthAddedData:
099f4111 7ea008c1 65847e75 483d3438
4a9f36c2 afe81176 f38e58c5 12d2a70e
31487049 4d3a9136 ba0a67ce b33534cb
d438e982 105d20cc 076204c6 fc99594d
thirdPrivateKey: 3356364835c9820b38c0440b2d88165ae48ea394edea76ede8706cc6504915f1
fourthAddedValue: a1cd9ea8dc605f136011a8e597329edb259e6758aec9f8772e1ae84780d62679
fourthPrivateKeyNegative: d523d4f11229e11e98d1ecf0c4bab5360a2d0aed9cb46f65168b550dd11f3c6a
fourthPrivateKey: 2adc2b0eedd61ee1672e130f3b454ac8b081d1f9129430d6a947097eff1704d7
thirdDerivedKey: 02 099f41117ea008c165847e75483d34384a9f36c2afe81176f38e58c512d2a70e
fourthAddedPoint: 02 fc6cc7b860bfb2612aca72cca75892e9601457c41641c3fc54741e16a13999d1
fourthPublicKey: 03 4467102eac1316de0875b25c9990bb8ad61aa8860e4a42f74ff11734a0fb6ed6
fourthDerivedKey: 02 4467102eac1316de0875b25c9990bb8ad61aa8860e4a42f74ff11734a0fb6ed6
So, if I calculated everything correctly, then for "masterPrivateKey" of 1c4f3bbd6703e3eb65040b37669046da93009b024aad0cef1b3cc57157e388ec and with "0/SHA-256('bitcointalk.org')/5321992/SHA-256('coinlatte')" path, we should get 02 4467102eac1316de0875b25c9990bb8ad61aa8860e4a42f74ff11734a0fb6ed6 public key and 2adc2b0eedd61ee1672e130f3b454ac8b081d1f9129430d6a947097eff1704d7 private key.
Topic: Is this HD wallet secure? (Read 145 times)
I get you now at this point except for firstAddedPoint.
So that one has to be a starting value, but where does that come from?
So that one has to be a starting value, but where does that come from?
Code:
$ hexdump -Cv key.bin
00000000 a3 4b 99 f2 2c 79 0c 4e 36 b2 b3 c2 c3 5a 36 db |.K..,y.N6....Z6.|
00000010 06 22 6e 41 c6 92 fc 82 b8 b5 6a c1 c5 40 c5 bd |."nA......j..@..|
00000020 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................|
00000030 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................|
00000040
$ sha256sum key.bin
db26845476a175bd67c1e2b96812ea4aaa772f401fd23edabb98155e53d6b612 key.bin
00000000 a3 4b 99 f2 2c 79 0c 4e 36 b2 b3 c2 c3 5a 36 db |.K..,y.N6....Z6.|
00000010 06 22 6e 41 c6 92 fc 82 b8 b5 6a c1 c5 40 c5 bd |."nA......j..@..|
00000020 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................|
00000030 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................|
00000040
$ sha256sum key.bin
db26845476a175bd67c1e2b96812ea4aaa772f401fd23edabb98155e53d6b612 key.bin
Then, ECDSA operations needs to be done here:
firstAddedValue: db26845476a175bd67c1e2b96812ea4aaa772f401fd23edabb98155e53d6b612
firstAddedPoint: 02 b87ef5ad03264ef973f7f1a710397f2aa365dd7c48514550aee83ac9c2cb4183
masterPublicKey: 02 a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c540c5bd
firstDerivedKey: 02 1dbe25ac1b430b911bda0f22d11c65a6e0fcc4861ac2a56ae8e8db27fd82ebd5
So, "firstDerivedKey" is just ECDSA sum of points "masterPublicKey" and "firstAddedPoint". It starts with "02", then fine, we have it. If it would start with "03", then we would negate it and get point with identical X value, just with reversed Y value.
Quote
And second, the message length of SHA256 is 512 bits, this means that SHA256 actually hashes blocks of 512 bits at once - but of course spits out a 256-bit result - so if you just start from "0" and someone breaks a couple rounds of SHA256 for one of these inputs, then theoretically that can be used to break those rounds for all other [M N] combinations with different nonces as well, and that's because if an input isn't a multiple of 512 bits it's extended by a one bit followed by a bunch of zero bits to extend it to a multiple of 512. So from SHA256's point of view, the first couple child keys are dangerously close to M with no nonce at all!
Why? Any hashed message is always 512-bits aligned, you have 256-bit public key and 256-bit nonce. Then, the second block in SHA-256 always looks like this:80000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000200
But as you don't know the offset of the master public key if you received only derived public key, you have no idea what SHA-256 output you should start with when trying to reverse it.
I guess you can disregard that part of my quote because I wrongly assumed the nonce is also getting hashes along with the master private key (right? I still don't think I fully get this. I reason we take the hash of the master private key concatenated with the nonce, and adding (arithmetic) it to the MPK itself
)How are we getting FirstAddedValue and SecondAddedValue for example? FirstAddedValue doesn't look like it's the sum of Master Public Key and FirstHashedData, assuming that the line of zeros below it is not part of the hash.
Quote
If I am understanding you correctly, you are taking the master public key (I'll just call it M) and a nonce N, and concatenate them together like this: [M N]
That is correct.Quote
and hashing it all with SHA256 to get the child key?
Hashing is used just to get a number that is then added to this master public key. I could just increment my master public key, but then everyone would be able to link all of those addresses together, so that is why hashing is used, to get some deterministic offset from this master public key.Quote
First it is trivial to derive the child key several numbers apart, so that the security of all of the keys depends on how well you safeguard the master private key.
If you have master public key, then it is trivial to derive other public keys that are deeper in the tree. But finding private keys is impossible (as far as I know), because you only know that master public key and the offset from this key if you know the nonce. Also, going to previous public keys in the tree seems to be impossible.Quote
By contrast, a BIP32 HD wallet has several different layers of "nonces" (paths actually) so it would be slightly harder to find some child key if the master private key was compromised, assuming you used a non-standard derivation path.
In my scheme, you always just derive child keys from public keys, it is possible to create any path you want. So, you can just have one master public key and increment your nonce, but you can also do it in a different way and create paths like "15/32/5/7". Just take 15th (starting from zero) public key, derive 32th public key from it, then 5th key from this key and finally the 7th key from this key.Quote
You can mitigate this by using a random 256-bit nonce
Nonce cannot be random, because the whole wallet have to be deterministic. You need to get nonce somehow, you can use a hash of something as a nonce, but then you need that data. So, for example if you use a hash of username, you have to know that username to derive keys properly. But if you use hash of some data as a nonce, you have to make sure that this data is unique (usernames have to be unique).Quote
or even ditch it all together and just SHA256 M to get the first key, SHA256 it again to get the next one and so on
Getting any key should be as fast as possible. So, if some user has 1,000,000 th key, it should not be forced to calculate SHA-256 1,000,000 times, just once.Quote
And second, the message length of SHA256 is 512 bits, this means that SHA256 actually hashes blocks of 512 bits at once - but of course spits out a 256-bit result - so if you just start from "0" and someone breaks a couple rounds of SHA256 for one of these inputs, then theoretically that can be used to break those rounds for all other [M N] combinations with different nonces as well, and that's because if an input isn't a multiple of 512 bits it's extended by a one bit followed by a bunch of zero bits to extend it to a multiple of 512. So from SHA256's point of view, the first couple child keys are dangerously close to M with no nonce at all!
Why? Any hashed message is always 512-bits aligned, you have 256-bit public key and 256-bit nonce. Then, the second block in SHA-256 always looks like this:80000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000200
But as you don't know the offset of the master public key if you received only derived public key, you have no idea what SHA-256 output you should start with when trying to reverse it.
If I am understanding you correctly, you are taking the master public key (I'll just call it M) and a nonce N, and concatenate them together like this: [M N] and hashing it all with SHA256 to get the child key?
If so, I don't like this approach for two reasons: First it is trivial to derive the child key several numbers apart, so that the security of all of the keys depends on how well you safeguard the master private key. If that is compromised then someone can easily generate the first couple nonces pretty rapidly (as well as being able to generate any arbitrary nonce). By contrast, a BIP32 HD wallet has several different layers of "nonces" (paths actually) so it would be slightly harder to find some child key if the master private key was compromised, assuming you used a non-standard derivation path.
You can mitigate this by using a random 256-bit nonce or even ditch it all together and just SHA256 M to get the first key, SHA256 it again to get the next one and so on.
And second, the message length of SHA256 is 512 bits, this means that SHA256 actually hashes blocks of 512 bits at once - but of course spits out a 256-bit result - so if you just start from "0" and someone breaks a couple rounds of SHA256 for one of these inputs, then theoretically that can be used to break those rounds for all other [M N] combinations with different nonces as well, and that's because if an input isn't a multiple of 512 bits it's extended by a one bit followed by a bunch of zero bits to extend it to a multiple of 512. So from SHA256's point of view, the first couple child keys are dangerously close to M with no nonce at all!
If so, I don't like this approach for two reasons: First it is trivial to derive the child key several numbers apart, so that the security of all of the keys depends on how well you safeguard the master private key. If that is compromised then someone can easily generate the first couple nonces pretty rapidly (as well as being able to generate any arbitrary nonce). By contrast, a BIP32 HD wallet has several different layers of "nonces" (paths actually) so it would be slightly harder to find some child key if the master private key was compromised, assuming you used a non-standard derivation path.
You can mitigate this by using a random 256-bit nonce or even ditch it all together and just SHA256 M to get the first key, SHA256 it again to get the next one and so on.
And second, the message length of SHA256 is 512 bits, this means that SHA256 actually hashes blocks of 512 bits at once - but of course spits out a 256-bit result - so if you just start from "0" and someone breaks a couple rounds of SHA256 for one of these inputs, then theoretically that can be used to break those rounds for all other [M N] combinations with different nonces as well, and that's because if an input isn't a multiple of 512 bits it's extended by a one bit followed by a bunch of zero bits to extend it to a multiple of 512. So from SHA256's point of view, the first couple child keys are dangerously close to M with no nonce at all!
I know about BIP 32, but I tried to do things in a simpler way and wonder if such design is secure enough.
First, we start with some master key, in this example we use output from executing SHA-256 on empty string, in real application it would be generated randomly in any secure way, for example as it is done by OpenSSL. Because if we use it directly, we would have some public key starting with "03" prefix, so we negate the result to get all public keys starting with "02", so we can make them all 256-bit. The same we can do for every public key if we ever get "03" prefix.
sha256empty: e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855
masterPrivateKey: 1c4f3bbd6703e3eb65040b37669046da93009b024aad0cef1b3cc57157e388ec
masterPublicKey: 02 a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c540c5bd
Then, if we want to get some keys from this master public key, we simply need to add some known number to it. To generate such number, we combine this 256-bit public key with 256-bit nonce and execute SHA-256 on it.
firstHashedData:
a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c540c5bd
0000000000000000000000000000000000000000000000000000000000000000
firstAddedValue: db26845476a175bd67c1e2b96812ea4aaa772f401fd23edabb98155e53d6b612
firstPrivateKey: f775c011dda559a8ccc5edf0cea331253d77ca426a7f4bc9d6d4dacfabba3efe
firstDerivedKey: 02 1dbe25ac1b430b911bda0f22d11c65a6e0fcc4861ac2a56ae8e8db27fd82ebd5
secondHashedData:
a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c540c5bd
0000000000000000000000000000000000000000000000000000000000000001
secondAddedValue: 6dbcfbb893a11df2abbcf8997c10da5dcf8d14a19eca8510002188bce19d7ee4
secondPrivateKey: 8a0c3775faa501de10c103d0e2a12138628dafa3e97791ff1b5e4e2e398107d0
secondDerivedKey: 02 7367ad233c2e83f265a4751219e5ff3c4d3719e0d6f3e37147ecb011441e1749
To make it more convenient, instead of incrementing nonce, we could also place some hash of SHA-256 here, for example if we have unique usernames, we could take the hash of this username (or hash of any other meaningful data). Thoughts?
First, we start with some master key, in this example we use output from executing SHA-256 on empty string, in real application it would be generated randomly in any secure way, for example as it is done by OpenSSL. Because if we use it directly, we would have some public key starting with "03" prefix, so we negate the result to get all public keys starting with "02", so we can make them all 256-bit. The same we can do for every public key if we ever get "03" prefix.
sha256empty: e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855
masterPrivateKey: 1c4f3bbd6703e3eb65040b37669046da93009b024aad0cef1b3cc57157e388ec
masterPublicKey: 02 a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c540c5bd
Then, if we want to get some keys from this master public key, we simply need to add some known number to it. To generate such number, we combine this 256-bit public key with 256-bit nonce and execute SHA-256 on it.
firstHashedData:
a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c540c5bd
0000000000000000000000000000000000000000000000000000000000000000
firstAddedValue: db26845476a175bd67c1e2b96812ea4aaa772f401fd23edabb98155e53d6b612
firstPrivateKey: f775c011dda559a8ccc5edf0cea331253d77ca426a7f4bc9d6d4dacfabba3efe
firstDerivedKey: 02 1dbe25ac1b430b911bda0f22d11c65a6e0fcc4861ac2a56ae8e8db27fd82ebd5
secondHashedData:
a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c540c5bd
0000000000000000000000000000000000000000000000000000000000000001
secondAddedValue: 6dbcfbb893a11df2abbcf8997c10da5dcf8d14a19eca8510002188bce19d7ee4
secondPrivateKey: 8a0c3775faa501de10c103d0e2a12138628dafa3e97791ff1b5e4e2e398107d0
secondDerivedKey: 02 7367ad233c2e83f265a4751219e5ff3c4d3719e0d6f3e37147ecb011441e1749
To make it more convenient, instead of incrementing nonce, we could also place some hash of SHA-256 here, for example if we have unique usernames, we could take the hash of this username (or hash of any other meaningful data). Thoughts?
Jump to: