BIP38 decrypt may have a browser dependency (Safari 6.x issue)

cantonbecker commented 10 years ago

I've been doing some testing with BIP38 decryption at bitaddress.org and ran into a funny issue when encrypting/decrypting wallets using the passphrase "घोडा स्टेपल" (no quotes) -- which is what you get when you use google translate to translate "horse staple" (no quotes) into Nepali.

My own BIP38 generator is, weirdly enough, giving me two different BIP38 encodings for the same wallet, whose details are: public key 1ABCDF5v4oaodTPYnKfYvkfwuoa8PJkjMC WIF key 5J4pcwBDPwPY1cdNqxTdmZWr7yCK8rXi9avFvezgYbmoatJpKGn

If I use Safari to encrypt with घोडा स्टेपल, I get 6PRNXA7M57uqSYXX2TXHkfNJEVMiWarkPkqUv3AsZa5r41u3VpXHLkUD9q

If I use Chrome / Firefox / IE and encrypt with घोडा स्टेपल, I get 6PRNXA7M4qEppBJCHM2SEizfna7XTomzXwdCBrEG6Mjo3nU6iziS6vWWXA

I'm not sure if this is my own bug, or something native to the BIP38 implementation I'm borrowing from bitaddress.org. Hard to test because I don't think bitaddress.org will let me BIP38 encrypt my own vanity address or brain wallet.

But here's something you can replicate / experience. I've been using bitaddress.org to check the validity of my BIP38 wallets. What I do is I fire up bitaddress.org, open up the "wallet details" tab, and use this to decrypt my "6P..." keys. And I'm getting browser-dependent results:

* Using the 'wallet details' tab on bitaddress.org to decrypt the BIP38 key, if using safari, the safari-generated key (_9q) works, and the other-browsers key (_XA) fails to decrypt. If using chrome/FF/IE, the reverse is true. *

I'm experiencing the same browser-dependent decrypting success/failure using the "decrypt private key" function at bit2factor.org.

Any ideas on why bitaddress.org is unable to decrypt my Nepali-encoded private keys unless I'm using the same browser I used to generate those keys?

rouslanovitch commented 6 years ago

@Dal78 did you succeed to decrypt your bugged Private Key? And on which version of bitaddress did you tested it?

Dal78 commented 6 years ago

Nope

Sent on my mobile

On 20 Dec 2017 15:38, rouslanovitch notifications@github.com wrote:

@Dal78https://github.com/dal78 did you succeed to decrypt your bugged Private Key?

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHubhttps://github.com/pointbiz/bitaddress.org/issues/56#issuecomment-353096873, or mute the threadhttps://github.com/notifications/unsubscribe-auth/AciaqeORGwMNn8kdh99VcpRbaT-ITqOMks5tCSoFgaJpZM4BYHPr.

rouslanovitch commented 6 years ago

And on which version of bitaddress did you tested it? online / offline ? release number?

rouslanovitch commented 6 years ago

@Dal78 @lathom @cantonbecker this is the code which created wrong BIP38 encryption https://gist.github.com/rouslanovitch/3f85357bada792e662868f26c46a8927

Dal78 commented 6 years ago

@rouslanovitch Online, inside my VM OSX 10.8, version 2.7.2

I can create broken keys, not decrypt them in the clean browser, decrypt them on the same broken browser on first try, not subsequent trys until re-opening the browser.

However on attempted to decrypt my broken ( or lost ) key i still get rejected. I have tried multiple times and therefore assumed that my keys is infact not afflicted with the bug and im just an idiot who typoed their password.

I still have the VM and environment, i'll keep it in case something comes up.

rouslanovitch commented 6 years ago

Thanks @Dal78 which version of Safari is it? I am creating up my OSX Lion stack right now in Parallels

Dal78 commented 6 years ago

@rouslanovitch Safari 6.0.5 (7536.30.1)

rouslanovitch commented 6 years ago

@Dal78 where could I download this Safari version?

Dal78 commented 6 years ago

@rouslanovitch grabbed it from here: https://filehippo.com/mac/download_safari_for_mac/57591/

rouslanovitch commented 6 years ago

Ok just reproduced the issue on my side:

OSX Lion 10.7.3
Safari 6.0.5
dogeaddress.com code (https://gist.github.com/rouslanovitch/3f85357bada792e662868f26c46a8927)

http://jsutftest.azurewebsites.net/testCrypto.html ==> Fails the two lines are not similar

The code generates BIP38 encrypted keys which decryption fails on current version of Chrome/Safari in High Sierra but decryption works on Safari 6.0.5 / OSX Lion.

Legacy Encrypted BIP38 PKey not working with the "historical" passphrase.

Having other wallets on my side from the same batch using the same password this will validate if the issue is coming from wrong password or crypto version issue.

cantonbecker commented 6 years ago

Can you please check to see if this is also the case with the current release of bitcoinpaperwallet.com ? The reason I ask is that we found a work-around for this bug when the 6.05 bug cropped up. We sent in a recommendation to have the work-around implemented in bitaddress.org but it was not folded in.

https://github.com/cantonbecker/bitcoinpaperwallet

If the bug is cropping up in newer versions of safari, but our work-around circumvents it, then I think it’s definitely a good idea for bitaddress to consider folding it in as Safari may not be as reliable as we’d like.

On Dec 20, 2017, at 10:42 AM, rouslanovitch notifications@github.com wrote:

Ok just reproduced the issue on my side:

OSX Lion 10.7.3 Safari 6.0.5 dogeaddress.com code (https://gist.github.com/rouslanovitch/3f85357bada792e662868f26c46a8927 https://gist.github.com/rouslanovitch/3f85357bada792e662868f26c46a8927) http://jsutftest.azurewebsites.net/testCrypto.html http://jsutftest.azurewebsites.net/testCrypto.html ==> Fails the two lines are not similar

The code generates BIP38 encrypted keys which decryption fails on current version of Chrome/Safari in High Sierra but decryption works on Safari 6.0.5 / OSX Lion.

Legacy Encrypted BIP38 PKey not working with the "historical" passphrase.

Having other wallets on my side from the same batch using the same password this will validate if the issue is coming from wrong password or crypto version issue.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/pointbiz/bitaddress.org/issues/56#issuecomment-353132462, or mute the thread https://github.com/notifications/unsubscribe-auth/AD9S4ys_3lZOEbGaLOT8rECP4e0MSQ9Aks5tCUbogaJpZM4BYHPr.

Canton Becker canton@gmail.com • (505) 570-0635 • http://cantonbecker.com

Dal78 commented 6 years ago

I'm happy to check on sat when I get back home.

On 21 Dec 2017 23:22, cantonbecker notifications@github.com wrote: Can you please check to see if this is also the case with the current release of bitcoinpaperwallet.com ? The reason I ask is that we found a work-around for this bug when the 6.05 bug cropped up. We sent in a recommendation to have the work-around implemented in bitaddress.org but it was not folded in.

https://github.com/cantonbecker/bitcoinpaperwallet

If the bug is cropping up in newer versions of safari, but our work-around circumvents it, then I think it’s definitely a good idea for bitaddress to consider folding it in as Safari may not be as reliable as we’d like.

On Dec 20, 2017, at 10:42 AM, rouslanovitch notifications@github.com wrote:

Ok just reproduced the issue on my side:

OSX Lion 10.7.3 Safari 6.0.5 dogeaddress.com code (https://gist.github.com/rouslanovitch/3f85357bada792e662868f26c46a8927 https://gist.github.com/rouslanovitch/3f85357bada792e662868f26c46a8927) http://jsutftest.azurewebsites.net/testCrypto.html http://jsutftest.azurewebsites.net/testCrypto.html ==> Fails the two lines are not similar

The code generates BIP38 encrypted keys which decryption fails on current version of Chrome/Safari in High Sierra but decryption works on Safari 6.0.5 / OSX Lion.

Legacy Encrypted BIP38 PKey not working with the "historical" passphrase.

Having other wallets on my side from the same batch using the same password this will validate if the issue is coming from wrong password or crypto version issue.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/pointbiz/bitaddress.org/issues/56#issuecomment-353132462, or mute the thread https://github.com/notifications/unsubscribe-auth/AD9S4ys_3lZOEbGaLOT8rECP4e0MSQ9Aks5tCUbogaJpZM4BYHPr.

Canton Becker canton@gmail.com • (505) 570-0635 • http://cantonbecker.com

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHubhttps://github.com/pointbiz/bitaddress.org/issues/56#issuecomment-353482474, or mute the threadhttps://github.com/notifications/unsubscribe-auth/AciaqYj0w4pukyv6HdUDLRuf7tW-8Z4Rks5tCugbgaJpZM4BYHPr.

rouslanovitch commented 6 years ago

@cantonbecker I checked on Safari 6.0.5 the current bitcoinpaperwallet offline generator and it generates a private BIP38 encoded key which cannot be decrypted on any version of Safari current & 6.0.5

Hope this helps

zgbee commented 6 years ago

Hey All - recently ran across this thread after having given up on a few wallets I gave out for the holidays back in 2013, and have renewed hope I'll be able to decrypt them, but haven't had any luck yet. (pretty sure I created BIP38 wallets on bitaddress.org using Safari, thinking it'd be more secure than using my 'primary' browser which was Chrome)

I've so far tried two of the encrypted private keys I distributed, and both have so far failed to decrypt in a VM (Parallels Lite, which is free from Mac App Store if you're not using it to run Windows).

Try 1: OSX 10.7, immediately upgraded to Safari 6.0.5 (7536.30.1)

downloaded from http://mac.filehorse.com/download-safari/3625/
did not try with the factory-installed Safari 5.x, but may reinstall the OS to appease my curiosity

In addition to attempting to decrypt one wallet, I ran the link provided by @artiomchi (http://jsutftest.azurewebsites.net/testCrypto.html) with the following results (note that the results were the same every time I refreshed the page - I was unable to find a difference on the first run after re-opening the browser):

Expected: 80,84,90,200,243,142,148,51,18,52,58,127,144,147,42,40,172,31,5,249,4,211,149,232,100,179,13,200,182,100,49,54,146,202,93,103,54,30,244,238,119,50,209,252,46,75,99,180,13,105

Actual: 31,122,37,156,131,63,37,145,75,239,33,116,191,180,213,94,254,146,47,164,51,146,46,20,77,146,141,65,210,169,136,215,251,233,177,113,136,38,185,243,128,8,202,56,242,39,110,80,106,255

Try 2: I downloaded/installed the 10.8 upgrade from the App Store (was in my purchase history), which installed Safari 6.0.5 (8536.30.1) by default.

had the exact same results as above, and also failed to decrypt an additional key that was originally generated at the same time as first key I tried

@scintill Do you still happen to have a copy of that WebKit nightly build? It doesn't seem to be online anymore

edit: just dug up some old backups, and had Safari 6.0.5 (8536.30.1) installed at the time

second edit: i got the wallet back! but it doesn't seem to have been related to the Safari bug, oddly enough. I found a clue in the backup - I had been very slightly mis-remembering the key. And now that I have the correct key, it also decrypts in a current version of Chrome. @Dal78 if you'd like me to try anything in the VM environment anyway, let me know

rouslanovitch commented 6 years ago

@zgbee what do you mean by "I had been very slightly mis-remembering the key" ?

your encrypted key was containing wrong letters?
you mis-typed your BIP38 decryption password?

Thanks!

zgbee commented 6 years ago

@rouslanovitch I was missing a single character from the end of the password I had used to encrypt the wallets.

DavidVeksler commented 5 years ago

FYI, I wrote a script that wraps the bitaddress.org libraries to run brute force in the web browser:

https://github.com/DavidVeksler/bitaddress.org

brianshould commented 3 years ago

I've been looking at this old bug for a while. Sure, there's a workaround, but reverting to Safari 6.0.5 to reclaim you bitcoin is a hassle. And there's another reason for this post: maybe some of you have experienced that remembering an old passphrase is hard and there might be a few variations you need to try. @DavidVeksler kindly offers the solution to this, by providing automated brute-forcing for bitaddress. However, I suspect that this may not work correctly for the bugged version of bitaddress (see 'Caching' below).

Please note that my work may depend on the hardware and/or software that I used, so results may be different for other setups. If you have a setup that produces different results, the procedure below may help you to track down the bug in your case. If you do, please share your results. I did my research using VMWare Fusion Pro (version 11.5.1). I ran this on a 2016 MacBook Pro with macOS High Sierra (macOS 10.13.6, 16 GB memory). The VMWare client OS runs Mac OS X 10.7.2 (2 GB memory) with Safari 6.0.5. I used Bitaddress version 2.9.3 because that is the version I was interested in. I have looked at the differences between version 2.9.3 and newer versions of Bitaddress, and expect they do not change the way the bug works.

If anything appears to be incorrect in my post, please reply so we can all learn.

My approach to this bug was pretty straightforward. Bitaddress produces incorrect results on Safari 6.0.5. Let's run two copies of Bitaddress, one on Safari 6.0.5 (buggy), and one on a recent version of Firefox (correct). Then add logging to track down where the buggy version goes wrong. First, I created a few test vectors and I saw that the versions indeed produce different results and that the buggy version produces incorrect ones as expected. Second, I added logging. And then the bug disappeared.

So what happened? As @artiomchi noticed, an extra call to salsa20_8() removes the bug. So does adding logging. Why? Some Googling taught me that the bug is caused by an error in the Javascript optimisation in Safari. So it makes sense that significant changes to the code alter the way in which it gets optimised. Luckily, I managed to work around this quirk by adding minimal logging only. Another issue that @artiomchi noticed is that if you log an array to console, it may give you the final state of the array, rather than the intermediate value when you logged it. I worked around that by using .toString(). In most cases I also used .slice(a, b) to only log part of the array, because the arrays used by Bitaddress can be pretty large. So my logging statements often looked like: console.log(" salt: " + salt.slice(0,32).toString());

Caching

Just when I thought I had fixed the issue of the bug disappearing, it disappeared again. This time, the issue was most probably caused by browser caching. When a piece of Javascript gets optimised by the browser, the browser usually caches the optimised Javascript, just in case it gets called again. So when I was testing multiple test vectors, only the first test vector would be processed in the 'correct buggy way'. For my setup, all subsequent test vectors would be processed in a non-buggy way. So for those of you who created a wallet with bitaddress in Safari 6.0.5, the result may be correct if you started with a test run before you created your actual wallet. Due to browser caching, @DavidVeksler 's brute-forcing version of Bitaddress will probably not work for brute-forcing buggy wallets. For my tests I needed a buggy Safari, so I closed Safari after each run, and used a different html file with a different name for each run.

Tracking down the bug

With these hurdles out of the way, it was time to track down where the bug occurs exactly. This pointed me towards the function scrypt. This function makes 8 calls to scryptCore, and these calls are made in parallel if possible. In my VM setup, the guest OS only had 1 processor core available, so the calls were always made successively. With a few logging statements I found out that the bug appears in the first call to scryptCore. So I went one level deeper.

scryptCore makes multiple calls to ROMix. ROMix is called smix in Bitaddress; I chose to follow the function names used in the Wikipedia description of Scrypt (https://en.wikipedia.org/wiki/Scrypt). Again the bug already appears in the first call. So I went one level deeper again. ROMix makes multiple calls to BlockMix (called blockmix_salsa8 in Bitaddress). To be precise, ROMix has 16384 iterations in each of which it calls BlockMix twice. In this case, the outputs of the buggy and non-buggy version were identical after the first iteration. So I performed a binary search, comparing the results after 8192, 4096, 2048, etc. iterations, to find that the bug first occurs on iteration 10 counting from 0, so the 11-th time it gets called.

BlockMix makes multiple calls to Salsa20/8 (called salsa20_8 in Bitaddress). Another binary search showed that the bug occurs on iteration 6 counting from 0, so the 7-th time it gets called. Before I reached this conclusion, I went through multiple detours exploring other functions like blockxor and arraycopy, to find that they were not causing the bug.

Salsa20/8 performs lots of operations on integer arrays, and it makes a call to arraycopy. arraycopy was not causing the bug, so finally I had arrived at the level where the bug actually happens. At this point I needed to be careful to not produce too much logging, because this would remove the bug again. I worked around this problem by producing logging only for the iteration I was interested in. After looking at different parts of logged arrays and comparing them between the correct and the buggy version, I finaly spotted the bug! The bug didn't actually happen in Salsa20/8, but in BlockMix. For some reason, it sets the first byte of X to 0 after calling Salsa20/8. So effectively, the buggy version works as normal, except that it may be thought to contain an extra statement:

X[0] = 0;

I wasn't done yet. The bug appeared at ROMix iteration 10, BlockMix iteration 6, but was only persistent for a while. After some more binary searches, I found that it disappeared after ROMix iteration 15, BlockMix iteration 7. And now I was done, at least in a practical sense. I still wanted to know why the bug appears after some number of iterations, then disappears again some number of iterations later.

Javascript optimisation

Some more Googling provided a plausible explanation for this. Javascript engines have multiple levels of optimisation. When the script starts, code is executed 'as is'. But the engine keeps track of functions that get called a lot so that it can optimise these. The engine has multiple levels of optimisation, so if a function gets called even more often, it gets optimised a second time, and possibly even a third time. So what we are seeing here is a bug that occurs in either the first or the second optimisation layer. The first part works fine, as does the last part. Somewhere in the middle we have a buggy Javascript optimisation.

Another observation is that Bitaddress works in a non-buggy way if the passphrase is longer than - I think - 16 characters. It makes sense that the code behaves in a slightly different way for a long passphrase: the passphrase enters into PBKDF2, where it acts as an HMAC key. If the HMAC key is longer than the block size of the underlying hash function, an additional call to the hash function is needed to compress it. I believe SHA-256 is used as a hash function, which has a block size of 32 bytes. So this makes sense if the passphrase would be encoded with 2 bytes per character, which I'm not sure is the case.

Multithreading

As I mentioned, my VM's guest OS only had a single core at its disposal, causing scrypt to run 8 successive iterations of scryptCore. One wonders what happens if the OS has multiple cores. It is unclear how this will affect the tallies that tell the Javascript engine when to optimise a function. Behaviour may become non-deterministic as we now have multiple threads with race conditions. So I gave my VM's guest OS two cores, and guess what? The bug disappeared. At this point I'm not sure my VM correctly simulates the way Bitaddress would run on an old MacBook with two cores. If anyone has an old MacBook with Safari 6.0.5 lying around, I would be interested how it handles Bitaddress.

Attachments

I have attached a 'buggy' version of Bitaddress 2.9.3. This should reproduce the bug explained above when run in a normal browser. I expect this may easily be transferred to other versions of Bitaddress by applying the same diffs as I did to the code. This should also work with @DavidVeksler 's brute-forcing version of Bitaddress. The result should be a brute-forcing 'buggy' version of Bitaddress that runs in any browser.

bitaddress.org_buggy.zip

I have also attached a few test vector for the buggy version of Bitaddress.

test_vectors_buggy.txt

Questions and issues

I'm happy to help others who cannot access their BIP-38 encrypted wallet. That is exactly my reason for this post. However, this analysis has taken me quite some time as I'm not a very experienced programmer. So I'm not going to make a buggy branch for other versions of Bitaddress, nor am I building a buggy version of @DavidVeksler 's brute-forcing Bitaddress. Nonetheless, I'm available for questions, so do not hesitate to raise any questions or issues if you run into them.

cantonbecker commented 3 years ago

I have attached a 'buggy' version of Bitaddress 2.9.3. This should reproduce the bug explained above when run in a normal browser.

That’s a fantastic service you’ve provided, kudos to you. As time goes on, it will be more and more difficult for people to setup virtual or real environments that can still run Safari 6.0.5.

canton

rouslanovitch commented 3 years ago

I've been looking at this old bug for a while. Sure, there's a workaround, but reverting to Safari 6.0.5 to reclaim you bitcoin is a hassle. And there's another reason for this post: maybe some of you have experienced that remembering an old passphrase is hard and there might be a few variations you need to try. @DavidVeksler kindly offers the solution to this, by providing automated brute-forcing for bitaddress. However, I suspect that this may not work correctly for the bugged version of bitaddress (see 'Caching' below).

Please note that my work may depend on the hardware and/or software that I used, so results may be different for other setups. If you have a setup that produces different results, the procedure below may help you to track down the bug in your case. If you do, please share your results. I did my research using VMWare Fusion Pro (version 11.5.1). I ran this on a 2016 MacBook Pro with macOS High Sierra (macOS 10.13.6, 16 GB memory). The VMWare client OS runs Mac OS X 10.7.2 (2 GB memory) with Safari 6.0.5. I used Bitaddress version 2.9.3 because that is the version I was interested in. I have looked at the differences between version 2.9.3 and newer versions of Bitaddress, and expect they do not change the way the bug works.

If anything appears to be incorrect in my post, please reply so we can all learn.

My approach to this bug was pretty straightforward. Bitaddress produces incorrect results on Safari 6.0.5. Let's run two copies of Bitaddress, one on Safari 6.0.5 (buggy), and one on a recent version of Firefox (correct). Then add logging to track down where the buggy version goes wrong. First, I created a few test vectors and I saw that the versions indeed produce different results and that the buggy version produces incorrect ones as expected. Second, I added logging. And then the bug disappeared.

So what happened? As @artiomchi noticed, an extra call to salsa20_8() removes the bug. So does adding logging. Why? Some Googling taught me that the bug is caused by an error in the Javascript optimisation in Safari. So it makes sense that significant changes to the code alter the way in which it gets optimised. Luckily, I managed to work around this quirk by adding minimal logging only. Another issue that @artiomchi noticed is that if you log an array to console, it may give you the final state of the array, rather than the intermediate value when you logged it. I worked around that by using .toString(). In most cases I also used .slice(a, b) to only log part of the array, because the arrays used by Bitaddress can be pretty large. So my logging statements often looked like: console.log(" salt: " + salt.slice(0,32).toString());

Caching

Just when I thought I had fixed the issue of the bug disappearing, it disappeared again. This time, the issue was most probably caused by browser caching. When a piece of Javascript gets optimised by the browser, the browser usually caches the optimised Javascript, just in case it gets called again. So when I was testing multiple test vectors, only the first test vector would be processed in the 'correct buggy way'. For my setup, all subsequent test vectors would be processed in a non-buggy way. So for those of you who created a wallet with bitaddress in Safari 6.0.5, the result may be correct if you started with a test run before you created your actual wallet. Due to browser caching, @DavidVeksler 's brute-forcing version of Bitaddress will probably not work for brute-forcing buggy wallets. For my tests I needed a buggy Safari, so I closed Safari after each run, and used a different html file with a different name for each run.

Tracking down the bug

With these hurdles out of the way, it was time to track down where the bug occurs exactly. This pointed me towards the function scrypt. This function makes 8 calls to scryptCore, and these calls are made in parallel if possible. In my VM setup, the guest OS only had 1 processor core available, so the calls were always made successively. With a few logging statements I found out that the bug appears in the first call to scryptCore. So I went one level deeper.

scryptCore makes multiple calls to ROMix. ROMix is called smix in Bitaddress; I chose to follow the function names used in the Wikipedia description of Scrypt (https://en.wikipedia.org/wiki/Scrypt). Again the bug already appears in the first call. So I went one level deeper again. ROMix makes multiple calls to BlockMix (called blockmix_salsa8 in Bitaddress). To be precise, ROMix has 16384 iterations in each of which it calls BlockMix twice. In this case, the outputs of the buggy and non-buggy version were identical after the first iteration. So I performed a binary search, comparing the results after 8192, 4096, 2048, etc. iterations, to find that the bug first occurs on iteration 10 counting from 0, so the 11-th time it gets called.

BlockMix makes multiple calls to Salsa20/8 (called salsa20_8 in Bitaddress). Another binary search showed that the bug occurs on iteration 6 counting from 0, so the 7-th time it gets called. Before I reached this conclusion, I went through multiple detours exploring other functions like blockxor and arraycopy, to find that they were not causing the bug.

Salsa20/8 performs lots of operations on integer arrays, and it makes a call to arraycopy. arraycopy was not causing the bug, so finally I had arrived at the level where the bug actually happens. At this point I needed to be careful to not produce too much logging, because this would remove the bug again. I worked around this problem by producing logging only for the iteration I was interested in. After looking at different parts of logged arrays and comparing them between the correct and the buggy version, I finaly spotted the bug! The bug didn't actually happen in Salsa20/8, but in BlockMix. For some reason, it sets the first byte of X to 0 after calling Salsa20/8. So effectively, the buggy version works as normal, except that it may be thought to contain an extra statement:

X[0] = 0;

I wasn't done yet. The bug appeared at ROMix iteration 10, BlockMix iteration 6, but was only persistent for a while. After some more binary searches, I found that it disappeared after ROMix iteration 15, BlockMix iteration 7. And now I was done, at least in a practical sense. I still wanted to know why the bug appears after some number of iterations, then disappears again some number of iterations later.

Javascript optimisation

Some more Googling provided a plausible explanation for this. Javascript engines have multiple levels of optimisation. When the script starts, code is executed 'as is'. But the engine keeps track of functions that get called a lot so that it can optimise these. The engine has multiple levels of optimisation, so if a function gets called even more often, it gets optimised a second time, and possibly even a third time. So what we are seeing here is a bug that occurs in either the first or the second optimisation layer. The first part works fine, as does the last part. Somewhere in the middle we have a buggy Javascript optimisation.

Another observation is that Bitaddress works in a non-buggy way if the passphrase is longer than - I think - 16 characters. It makes sense that the code behaves in a slightly different way for a long passphrase: the passphrase enters into PBKDF2, where it acts as an HMAC key. If the HMAC key is longer than the block size of the underlying hash function, an additional call to the hash function is needed to compress it. I believe SHA-256 is used as a hash function, which has a block size of 32 bytes. So this makes sense if the passphrase would be encoded with 2 bytes per character, which I'm not sure is the case.

Multithreading

As I mentioned, my VM's guest OS only had a single core at its disposal, causing scrypt to run 8 successive iterations of scryptCore. One wonders what happens if the OS has multiple cores. It is unclear how this will affect the tallies that tell the Javascript engine when to optimise a function. Behaviour may become non-deterministic as we now have multiple threads with race conditions. So I gave my VM's guest OS two cores, and guess what? The bug disappeared. At this point I'm not sure my VM correctly simulates the way Bitaddress would run on an old MacBook with two cores. If anyone has an old MacBook with Safari 6.0.5 lying around, I would be interested how it handles Bitaddress.

Attachments

I have attached a 'buggy' version of Bitaddress 2.9.3. This should reproduce the bug explained above when run in a normal browser. I expect this may easily be transferred to other versions of Bitaddress by applying the same diffs as I did to the code. This should also work with @DavidVeksler 's brute-forcing version of Bitaddress. The result should be a brute-forcing 'buggy' version of Bitaddress that runs in any browser.

bitaddress.org_buggy.zip

I have also attached a few test vector for the buggy version of Bitaddress.

test_vectors_buggy.txt

Questions and issues

I'm happy to help others who cannot access their BIP-38 encrypted wallet. That is exactly my reason for this post. However, this analysis has taken me quite some time as I'm not a very experienced programmer. So I'm not going to make a buggy branch for other versions of Bitaddress, nor am I building a buggy version of @DavidVeksler 's brute-forcing Bitaddress. Nonetheless, I'm available for questions, so do not hesitate to raise any questions or issues if you run into them.

Hello @brianshould

I still have my MBP from the time I generated my PKs, I will clean it and roll-back to OSX Lion with Safari 6.0.5 to see if its really deterministic. If you have any other options to unlock my BIP38 wallet

hlbfrancois commented 1 year ago

@brianshould Does the buggy branch only support decryption or also encryption with bip38? I haven't been able to create any "buggy paper wallets" with it.

Would @DavidVeksler 's brute forcing tool work with browser caching disabled?

pointbiz / bitaddress.org