Accounts sometimes generated differently from TestRPC

[danfinlay]

In some but not all cases, the mnemonic used to create & restore a vault in MetaMask is differing from the accounts generated in TestRPC.

MetaMask relies on eth-lightwallet, while testrpc has migrated to ethereumjs-wallet.

The currently reliable test case is:

• With mnemonic radar blur cabbage chef fix engine embark joy scheme fiction master release
• TestRPC's first account is 0xac39b311dceb2a4b2f5d8461c1cdaf756f4f7ae9
• Trezor's first account is 0xac39b311dceb2a4b2f5d8461c1cdaf756f4f7ae9.
• MetaMask's first account is: 0xe15D894BeCB0354c501AE69429B05143679F39e0.

Curious if @christianlundkvist or @axic might be able to help determine how this could be?

[axic]

Here's an independent BIP32 tool: https://bip32jp.github.io/english/

Entering the following mnemonic together with the path (from testrpc: m/44'/60'/0'/0/0) I get the following xprv: xprvA37Rc6NGfnAPFSTaonCV6jQLnqGbe4FBC8ERLSn5eFNQsaqTUXf5ZSvsm2KMtGNJavpBdYg4FZAmfmjyoDKKKHKRroe4kctjY3yyxVgtv2y

That is turned into an Ethereum address as follows:

$ helpeth -p xprvA37Rc6NGfnAPFSTaonCV6jQLnqGbe4FBC8ERLSn5eFNQsaqTUXf5ZSvsm2KMtGNJavpBdYg4FZAmfmjyoDKKKHKRroe4kctjY3yyxVgtv2y keyDetails
Address: 0xe15d894becb0354c501ae69429b05143679f39e0

This seems to match Metamask's.

Pluggin the same in to hdkey:

var HDKey = require('hdkey')
var hdkey = HDKey.fromExtendedKey("xprv9s21ZrQH143K2weTjKTSMXUM1qmfYo2iDQGPrzsbirKyf9Qn325C8DtapD8dwUL2PU8ciZ9hYVSL4Q9VkygWBosS8FMuX65QqxZQmBDYSEq")
var key = hdkey.derive("m/44'/60'/0'/0/0")
console.log(key.privateExtendedKey)

Gives: xprvA2xEQ2iTe9QB22rvf5cbfpUxEBmMdvc7stEFxLhiMXmdLrwLbqugPCHRZiRfEq2puC5vTgwyFneV38hppF8oTf9aoaUv7M8u2XvnACTe6r4

Which equals to 0xac39b311dceb2a4b2f5d8461c1cdaf756f4f7ae9

@jprichardson any idea?

[danfinlay]

Awesome, thanks for showing the steps!

[axic]

Actually I think it should be validated by a non-JS implementation, such as Trezor. I don't have mine here, but if anyone enters the above mnemonic + path they can retrieve the xprv.

[axic]

@flyswatter it is strange... I've actually recreated it with trezor-crypto, and the answer is 0xac39b311dceb2a4b2f5d8461c1cdaf756f4f7ae9 from there.

[danfinlay]

Whoah, this is an increasingly large schism. Could this come from slightly different dictionaries? (Sad to say I don't know much about this niche of crypto)

[coder5876]

Very mysterious, I haven't been able to replicate the derived keys from the hdkey tool in the BIP32 page. Will play around some more...

[axic]

From the mnemonic both Trezor and the bip39jp give the following xprv: xprv9s21ZrQH143K2weTjKTSMXUM1qmfYo2iDQGPrzsbirKyf9Qn325C8DtapD8dwUL2PU8ciZ9hYVSL4Q9VkygWBosS8FMuX65QqxZQmBDYSEq.

I would think the difference is handling the edge cases within the private key derivation method. When a step generates an invalid private key (i.e. not matching the curve requirements) a new one must be generated. I think there wasn't a proper specific way to do this (it was only suggested lately to BIP32) and these tools might implement a different handling.

[axic]

This is my Trezor code: https://gist.github.com/axic/72294f8b93cdd6e871de83c570d42444

@jhoenicke can you double check this please?

[axic]

@jhoenicke that's funny though, it was actually you suggesting this clarification and perhaps now here's an actual example?

See: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016-April/012611.html

[danfinlay]

Best thing about MetaMask's dev beta: Lots of real users on this software, finding those edge cases!

[coder5876]

@axic

The chance that this affects anyone is less than 10^-30

Hmm, seems pretty unlikely that we've accidentally stumbled upon something like this. I also tried a bunch of different derivations from the same master key xprv9s21ZrQH and they're all different between the web tool and hdkey.

[axic]

@christianlundkvist it could be that the very first derivation fails

[coder5876]

@axic

it could be that the very first derivation fails

Yes good point. Some more experimental results:

• Same derivation from web tool and hdkey : m/0, m/44', m/44'/60', m/44'/60'/0
• Different derivation: m/44'/60'/0'

[coder5876]

Using another random master key xprv9s21ZrQH143K3ohLDFV6VWyciSA1MA5vmuAE8k6hRFW57NtmPHaotXXm7h6UpM6LSXpKWC2TTkJuzxk3zczkrnZAPPu3kGx5F69z71yqQBr everything seems to match.

Ha, would be so fun if this really was a case of the hash being larger than the prime of the curve. I'm not sure how to dig into it and really test it so hopefully @jhoenicke can shed some light.

BTW I bet the website uses bitcore's HD key library (same as lightwallet/metamask uses).

[axic]

The website actually uses an its own ancient implementation based on CryptoJS. So another clue might be a wrong edge-case of HMAC.

[axic]

@christianlundkvist can you post here I (the private key) for each step when deriving m/44'/60'/0'? (I mean the internal steps within the derivation loop.)

[coder5876]

@axic I'm walking home from Starbucks right now, will post when I get home. We can basically narrow it down to a single derivation step m/44'/60' -> m/44'/60'/0'

[coder5876]

@axic So for m/44'/60' both implementations derive to

xprv9w29xFAdfTWFMXugTrP7x1X8c75gYKZFUEhGFqhbGxAwpJnWSo1QZUWPgr2XRKsdsdFPiKKaixbj1gZ2r63NS4EKUkjfii41gWKC5VU8gsh

If we choose this one as the master now and derive m/0' from that we get

xprv9zWvV2FbEX7W1R8ASQti8MXuQcrorfu2QrjyWfaXqKvaP53PvZaXrzKtHXLqD88fZasc9SK9PAy7zhXZeacvajriqyjmuvBq198K247gb4t

from the web tool and

xprv9zWvV2FbEX7VzS96sZG1dZ7MY2j4iFDB62kfuwU95q22omhL7EpQGutw9GyRa9tic3uRnCVZXMLApeDrKb9qJrrUKZzG5dDX29BZwLaTmGZ

from hdkey. Also m/1' is different:

xprv9zWvV2FbEX7W3hqanJaDm3bw9EUGDkEonKyg51wjciCTMrtUwTmUKn5J44AW5Kd6A8nQPW5UEdB2zxQ3TTQvSwi8jqod641XExeomECXtJF

from the web tool and

xprv9zWvV2FbEX7W2kgwuvMdoi4wVMQSUjaRiRFz1tfy7UMuxN5Yz8kEgSUKkYXjadjRrg3KZqtLB3PuWV1WNSbeYizcZrJ2iMDZ6QBBqHkvPfL

from hdkey. As mentioned above m/0 is the same for both:

xprv9zWvV2FStraXqUEBTezHenCmSkPMsgZYgXX4LEWxHLYL3N8d9dRaQF9Gu3yhUFTBt8JJNkLdCsh3p1RkZ63sAzSVKcyoxf1bf47skXPBXSZ

[axic]

@christianlundkvist I meant the internal loop (and not the resulting keys) of the derivation for that given path

[coder5876]

@axic What do you mean by "internal loop"? I don't know how to compute the internal key derivation steps for a given path, is that possible with hdkey?

[coder5876]

I guess this

https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki#private-parent-key--private-child-key

is implemented somewhere, but don't really have time to reimplement or dig around in the code right now.

[axic]

This doesn't seem to do the internal checks: https://github.com/bitpay/bitcore-lib/blob/master/lib/hdprivatekey.js#L163 (You're using bitcore-lib, correct?)

[coder5876]

@axic Interesting! And hdkey does:

    } catch (err) {
      // In case parse256(IL) >= n or ki == 0, one should proceed with the next value for i
      return this.derive(index + 1)
    }

Yes, I use the bitcore-lib. So that could very well be the reason. Let me console.log() those I:s

[axic]

I'm actually testing all this with Trezor (an extended version of the code I've posted above) which matches hdkey so far.

[coder5876]

@axic Doesn't look like it's failing at parse256(IL) >= n (I put a console.log where that error is) BTW IL is

<Buffer 47 9e 10 87 7e 33 8a 0d b9 00 7c 54 9d 1a b1 36 85 99 1b b1 38 47 25 41 71 32 06 e4 63 6b 73 b4>

[axic]

trezor:

data: 000062b830267819c737684672a04f93cbad7774093d7c365d375d3a1dda12e18280000000
chaincode: df6e092d15a9950147284bc90c5ee06e9aeff1c1e6e7ec48d22c0d1c4a004b68
hash: 479e10877e338a0db9007c549d1ab13685991bb138472541713206e4636b73b422d456e254b5c165b81ee6cfde1ee082be84d3d71a0bbfdfca6f96f4b82b4991

bitcore:

data 0062b830267819c737684672a04f93cbad7774093d7c365d375d3a1dda12e18280000000
chaincode df6e092d15a9950147284bc90c5ee06e9aeff1c1e6e7ec48d22c0d1c4a004b68
hash d79d4c0fb8f2d969292facc3e20b7e1e42e926477efecc8537d9c6040d9d25518582e50576be8a64ef0309fc64ff6af7eb513fc22110ea0ee9c5fe316f33c5bd

The data for private derivation is [0][address][derivation node]. It seems that bitcore drops the 00 from the private key coming form the previous step.

[coder5876]

@axic Ah! I've seen that kind of behavior before from bitcore (i.e. dropping leading zeros in private keys). Like here: https://github.com/bitpay/bitcore-lib/issues/47

[axic]

Well, it's sorted now. Someone just needs to fix it :)

@flyswatter I think you need to update that test 😉

[danfinlay]

I think I'm going to add it in a later PR, so I'm not waiting for the fixes. :)

Thanks a lot guys, was fun to watch :D

Just to clarify: Bitcore is used by eth-lightwallet, so that was the wrong one here? The correct key was 0xac39b311dceb2a4b2f5d8461c1cdaf756f4f7ae9?

[coder5876]

Just to clarify: Bitcore is used by eth-lightwallet, so that was the wrong one here?

That seems to be the case, yes.

[coder5876]

@flyswatter This should happen fairly frequently (like one time in 256) so if bit core changes behavior you might get people who all of a sudden can't get to their Ether because some of the derived addresses changed. The Ether won't be lost, but there probably needs to be some way to use the old algorithm to retrieve the other keys.

[axic]

@christianlundkvist actually, that chance is present for every derivation step and there are at least 5 steps (plus more if the step produced an invalid key) for the path used above.

[danfinlay]

So should we aim to expose the option to restore the bug at every layer of the stack, or simply offer an outdated build as a step in a recovery process?

I'm leaning towards the latter for simplicity.

On Sep 10, 2016, at 6:28 PM, Alex Beregszaszi notifications@github.com wrote:

@christianlundkvist actually, that chance is present for every derivation step and there are at least 5 steps (plus more if the step produced an invalid key) for the path used above.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub, or mute the thread.

[coder5876]

The latter sounds like a reasonable idea to me. On Sat, Sep 10, 2016 at 9:40 PM Dan Finlay notifications@github.com wrote:

So should we aim to expose the option to restore the bug at every layer of the stack, or simply offer an outdated build as a step in a recovery process?

I'm leaning towards the latter for simplicity.

On Sep 10, 2016, at 6:28 PM, Alex Beregszaszi notifications@github.com wrote:

@christianlundkvist actually, that chance is present for every derivation step and there are at least 5 steps (plus more if the step produced an invalid key) for the path used above.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub, or mute the thread.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/MetaMask/metamask-plugin/issues/640#issuecomment-246156347, or mute the thread https://github.com/notifications/unsubscribe-auth/AGktZR1xS86UKwX3pSdQGIuU4sEg9pfvks5qo1wYgaJpZM4J5yc0 .

[kumavis]

sounds like 1/256 chance * 5 derivation steps * 2,000 metamask users = 40 users with affected primary accounts ( also additional non-metamask lightwallet users )

[axic]

I've made a write up here: https://medium.com/@alexberegszaszi/6f3254cc5846

Let me know if something's incorrect!

[danfinlay]

Blocked by fixes to bitcore & eth-lightwallet.

[braydonf]

You can test with: https://github.com/bitpay/bitcore-lib/pull/97

[danfinlay]

@axic can you verify the probability of hitting this bug? We're preparing to launch our fix, and we want to prepare appropriately.

[danfinlay]

This has been resolved within MetaMask.