20 BTC bounty: Javascript implementation of BIP 38 [claimed]

[casascius]

I would like to offer a 20 BTC bounty for the following: a Javascript implementation of BIP 38 private key decryption, released with an open source license, so anybody can use it on their own web sites.

BIP 38: https://en.bitcoin.it/wiki/BIP_0038

I have already written functioning reference code in C#, the flow can be taken verbatim, you may freely take or incorporate any part of the code.  This code will run under Windows .NET, as well as under Linux and Mac OS X using Mono.  Although the ability to create intermediate codes and addresses would be nice and won't be much work beyond the decryption part, the bounty can be collected in full with just the ability to decrypt all variants of BIP38-encrypted private key.

That reference code I wrote: https://github.com/casascius/Bitcoin-Address-Utility

The UI can be minimal, just two text boxes, one to take the private key and the other to take the passphrase.  When you click a button, the page should either decrypt the private key into some element on the screen, or report that the encrypted private key is invalid (e.g. fails base58 checksum or formatting rules), or that the passphrase is incorrect (if the key is well-formatted but the decryption with the provided passphrase fails to produce a bitcoin address matching the embedded address checksum)

I actually anticipate that this won't be too difficult, and would do it myself other than I think it'll get done sooner if I post a bounty.

The winning solution needs to properly handle the compressed private key flag, as well as the variants of encryption that include and exclude the elliptic curve multiplication step as well as the flag that turns on the presence of a sequence number.

If I were doing it, I'd probably start with much of the code and/or the same dependencies that are used in bitaddress.org, so the basics of handling bitcoin addresses, private keys, base58, elliptic curve points, etc. are already taken care of.  Add scrypt and AES, and perhaps support for decompressing EC points if that's not already there.

The GOAL is so that others who currently accept unencrypted private keys, can easily switch to accepting encrypted private keys as well, just by dropping in a couple of .js files and letting the client browser do all the decryption.

[paybitcoin]

This might be an issue since there is not an official library for scrypt ported to js...

http://stackoverflow.com/questions/7617169/scrypt-implementation-in-javascript (lol, that question was for a Bitcoin-related project also, Tenebrix...)

here maybe, but it looks like it needs some work: https://github.com/cheongwy/node-scrypt-js

---
Whoever wants to pick this up, can also look at my code here https://github.com/notespace/bip38-cracker/blob/master/main.c even though it is a quite hacked together and ONLY works with the EC-multiplied version of BIP 38, not all of them. It does correctly decode keys though. Not sure it will help that much though for a js port...

[bitvientiane]

the bounty can be collected in full with just the ability to decrypt any variant of BIP38-encrypted private key.

The winning solution needs to properly handle the compressed private key flag, as well as the variants of encryption that include and exclude the elliptic curve multiplication step as well as the flag that turns on the presence of a sequence number.

The second section seems to imply you meant every instead of any right?

[FiloSottile]

Seems cool! Starting research it now...

[bitvientiane]

here maybe, but it looks like it needs some work: https://github.com/cheongwy/node-scrypt-js

That one only works for node and uses a lot of external modules. I'm trying to follow the coding style and let it work in the browser but it doesn't look too hopeful with my coding skills.

[casascius]

Yes, decryption of every mode must be supported.  Clarified OP.

In practice, I don't imagine that being the hardest part, especially if you are following my C# code as a template.

[bitvientiane]

I finally have a scrypt implementation in pure javascript that passes all test vectors at http://www.ietf.org/id/draft-josefsson-scrypt-kdf-01.txt. I won't release it now because I plan to go for the bounty. If I somehow abandon that I will put it up on github.

[bitvientiane]

Test vectors

No compression, no EC multiply
Test 1:
Passphrase: TestingOneTwoThree
Encrypted: 6PRVWUbkzzsbcVac2qwfssoUJAN1Xhrg6bNk8J7Nzm5H7kxEbn2Nh2ZoGg
Unencrypted (WIF): 5KN7MzqK5wt2TP1fQCYyHBtDrXdJuXbUzm4A9rKAteGu3Qi5CVR
Unencrypted (hex): CBF4B9F70470856BB4F40F80B87EDB90865997FFEE6DF315AB166D713AF433A5


Result by decryptbip38.js:

Encrypted key: 6PRVWUbkzzsbcVac2qwfssoUJAN1Xhrg6bNk8J7Nzm5H7kxEbn2Nh2ZoGg
Passphrase: TestingOneTwoThree
Private key: cbf4b9f70470856bb4f40f80b87edb90865997ffee6df315ab166d713af433a5


Now for the EC version. Shouldn't be much harder.

[bitvientiane]

Can someone provide the ownersalt used for these test vectors? It appears to be missing or I'm misunderstanding something. I need to test the process until the intermediate code.

EC multiply, no compression
Test 1:
Passphrase: TestingOneTwoThree
Passphrase code: passphrasepxFy57B9v8HtUsszJYKReoNDV6VHjUSGt8EVJmux9n1J3Ltf1gRxyDGXqnf9qm
Encrypted key: 6PfQu77ygVyJLZjfvMLyhLMQbYnu5uguoJJ4kMCLqWwPEdfpwANVS76gTX
Bitcoin address: 1PE6TQi6HTVNz5DLwB1LcpMBALubfuN2z2
Unencrypted private key (WIF): 5K4caxezwjGCGfnoPTZ8tMcJBLB7Jvyjv4xxeacadhq8nLisLR2
Unencrypted private key (hex): A43A940577F4E97F5C4D39EB14FF083A98187C64EA7C99EF7CE460833959A519
Test 2:
Passphrase: Satoshi
Passphrase code: passphraseoRDGAXTWzbp72eVbtUDdn1rwpgPUGjNZEc6CGBo8i5EC1FPW8wcnLdq4ThKzAS
Encrypted key: 6PfLGnQs6VZnrNpmVKfjotbnQuaJK4KZoPFrAjx1JMJUa1Ft8gnf5WxfKd
Bitcoin address: 1CqzrtZC6mXSAhoxtFwVjz8LtwLJjDYU3V
Unencrypted private key (WIF): 5KJ51SgxWaAYR13zd9ReMhJpwrcX47xTJh2D3fGPG9CM8vkv5sH
Unencrypted private key (hex): C2C8036DF268F498099350718C4A3EF3984D2BE84618C2650F5171DCC5EB660A

[paybitcoin]

The ownersalt is encoded plaintext in the encrypted key and is handled like an IV. Casascius changed BIP 38 since I last looked at it (boo!) and now it seems to be called ownerentropy (which can be 8 random bytes or derived from a 4-byte random number + lot and sequence #.)

Encrypted Key = base58(0x01 0x43 + flagbyte (1 byte) + addresshash (4 bytes) + ownerentropy (8 bytes) + encryptedpart1[0...7] (8 bytes) + encryptedpart2 (8 bytes)).

Actually looking further into the spec it seems like my BIP 38 cracker is now incompatible with the spec with the addition of prefactor and hashing it with ownersalt to get passfactor.

[bitvientiane]

So do you figure those test vectors are invalid now?

[casascius]

The test vectors are still valid.

I did make a recent change but then required both modes to be supported. A bit flag enables that change. It allows someone ordering a batch of paper wallets to ensure his intermediate codes aren't reused by building a batch(lot) and sequence number into the salt. Meanwhile the sha256 step allows the sequence number to be incremented without repeating the scrypt - essential for mobile phone performance generating a batch of codes.

The test vectors don't have that flag but I will add one with the flag when I get a chance.

[scintill]

I finally have a scrypt implementation in pure javascript that passes all test vectors at http://www.ietf.org/id/draft-josefsson-scrypt-kdf-01.txt. I won't release it now because I plan to go for the bounty. If I somehow abandon that I will put it up on github.

Curious, have you got even the last case with N=1048576?  Mine is crashing the Chrome tab it lives in, and even nodejs (message about running out of memory).  (With the smaller N-values BIP38 needs it works though.)

[casascius]

Here is a test vector for the version with the lot and sequence number.  The Wiki seems to be down otherwise I'd update it.  The Greek characters should also help test for support of UTF-8, which I intend to specify as the required encoding for non-ASCII characters.

Passphrase: MOΛΩN ΛABE
Intermediate code: passphrased3z9rQJHSyBkNBwTRPkUGNVEVrUAcfAXDyRU1V28ie6hNFbqDwbFBvsTK7yWVK
Encrypted private key: 6PgGWtx25kUg8QWvwuJAgorN6k9FbE25rv5dMRwu5SKMnfpfVe5mar2ngH
Private key hex: CA2759AA4ADB0F96C414F36ABEB8DB59342985BE9FA50FAAC228C8E7D90E3006
Unencrypted private key (WIF): 5KMKKuUmAkiNbA3DazMQiLfDq47qs8MAEThm4yL8R2PhV1ov33D
Bitcoin address: 1Lurmih3KruL4xDB5FmHof38yawNtP9oGf
Confirmation code: cfrm38V8G4qq2ywYEFfWLD5Cc6msj9UwsG2Mj4Z6QdGJAFQpdatZLavkgRd1i4iBMdRngDqDs51

[bitvientiane]

I finally have a scrypt implementation in pure javascript that passes all test vectors at http://www.ietf.org/id/draft-josefsson-scrypt-kdf-01.txt. I won't release it now because I plan to go for the bounty. If I somehow abandon that I will put it up on github.

Curious, have you got even the last case with N=1048576?  Mine is crashing the Chrome tab it lives in, and even nodejs (message about running out of memory).  (With the smaller N-values BIP38 needs it works though.)

Crashes for me too. I think I could possibly get it to work but I'm not going to bother since the BIP38 stuff works.

How far along are you on the whole thing?

[casascius]

I added two test vectors to the wiki page.

I wouldn't worry so much if N=1048576 fails due to resource constraints, it won't be used.

[scintill]

Crashes for me too. I think I could possibly get it to work but I'm not going to bother since the BIP38 stuff works.

How far along are you on the whole thing?

I think I'm done now.  I implemented the lot/sequence number last night, and just sent Casascius the link to my latest code.  Something I maybe should have mentioned to him, is that the performance in Firefox is pretty bad (3x slower than Chrome.)  I'm not sure if the JS engine is just that much worse, or if I'm doing something dumb that's slowing me down.  So maybe performance could use some work, but all test cases are passing.

[casascius]

It looks like it functions as expected.  Would you mind adding it to github as a pull request and provide a bitcoin address for the bounty?

[bitvientiane]

Congrats, I was nearly done but had some annoying bug left. I'll check performance in firefox and see if my code happens to do better though. (Unlikely though if your scrypt is also based on this one: https://github.com/cheongwy/node-scrypt-js)

[scintill]

I submitted a pull request at https://github.com/pointbiz/bitaddress.org/pull/8 . (Edit: demo page at http://scintill.github.com/bitaddress.org-bip38.html )

I'm open to suggestions on improvements, or requests on other ways to package it up.  The core code is pretty short and simple, but it depends on EC crypto, biginteger, AES, SHA256, scrypt, and Base58 coding, so could need some adjustment if anyone would like to use it outside of the bitaddress.org page.  I may also release my scrypt code separately as it looks like there are no other browser-ready implementations.

Please send the bounty to 1GSo3Z3fgsvUH6yKr6s8kJHMFDWvLEuXjs, and thank you!

Congrats, I was nearly done but had some annoying bug left. I'll check performance in firefox and see if my code happens to do better though. (Unlikely though if your scrypt is also based on this one: https://github.com/cheongwy/node-scrypt-js)

Yes, my scrypt is based on that, replacing the node module dependencies with Crypto-JS functions.  I also used Web Workers to do 2 scrypt threads in parallel.