Brute-Forcing using the bash script given on the Multibit website

[nowhere man]

Hi guys - I'd appreciate a bit of help here, if you have the time and don't mind helping a fellow fanatic - I'm trying to brute force my brother's multibit wallet after he has managed to forget his password. He gave me some 'stems' of words that he normally uses and I've set about trying to figure out exactly how I would try and brute force the private key encryption.

Here's what I've done so far. Copied and saved the bash script given on the multibit 'lost passwords' page. It's the script they advise using if you have a password manager. I've then used Excel to create a csv file of passwords using my brothers 'stems' with simple permutations. Essentially the stems but with the numbers 1 up to 999 on the end.

I've then saved the csv file and multibit key file in the same folder (entitled multibittragedy) along with the apply-guesses.sh file. I then ran the executable script and it was clearly working in some sense as it went about testing all the correct passwords stored in the file.

Now here's where it gets strange (at least to me) - It quoted 'success' and I got very excited as I thought i had found the right password. As it happened this 'success' password still failed to open the wallet. I tested another password list with variations on my name (jon1, jon2, jon3.......etc etc). And to my astonishment it quoted 'success!' again stating that jon32 was indeed my brother's password. Needless to say, that ain't my bro's password either.

So I'm curious, what am I doing wrong to generate all these false positives. Why are only some of them coming up correct? If there is anyone here familiar with the bash script I would love to hear what they think. I'm a rank amateur when it comes to the command line but I like to think of myself as a 'have a go hero' so if you could help me out that would be brilliant.

By the way, I know my post history is limited but I'm no scammer. The wallet i'm unlocking has 0.1 bitcoins in it and I'd really just like to learn a bit more about how this stuff works.

Any words of wisdom would be graciously and gratefully accepted.

All the best amigos.

[btchris]

Hi guys - I'd appreciate a bit of help here, if you have the time and don't mind helping a fellow fanatic - I'm trying to brute force my brother's multibit wallet after he has managed to forget his password. He gave me some 'stems' of words that he normally uses and I've set about trying to figure out exactly how I would try and brute force the private key encryption.

I can't directly answer your question as I'm unfamiliar with that bash script, but I can offer an alternative.

This sounds exactly like what btcrecover was designed to do. Instead of calling them "stems", it calls them "tokens".

There's a tutorial available here: https://github.com/gurnec/btcrecover/blob/master/TUTORIAL.md#btcrecover-tutorial. As the quick start says, it's a big tutorial, but you can skip a lot of it. It sounds like the first two or three parts of The Token File section would be relevant, and so would the section on Expanding Wildcards for adding numbers onto the end.

If you have any questions, please feel free to ask (full disclosure: I'm the dev of that tool).

And of course, good luck!

[nowhere man]

Well firstly thanks a bunch for your response; after a cursory glance your btcrecovery tool seems to be *exactly* what I was looking for. You the man! 

Here's the bash script I was using just in case you're interested. It might be obvious to you why it was producing false positives occasionally:

#!/bin/bash
echo Usage: apply-guesses.sh [password CSV] [key file]
echo Password file: $1
echo Key file: $2
for password in $( awk -F , -v OFS=' ' '{print $3}' $1 ); do
   echo ------
   echo Attempting: $password...
   openssl enc -d -p -aes-256-cbc -a -in $2 -out recovered.key -pass pass:$password
   if [ $? -eq 0 ];
     then
       echo "Success!";
       break;
     else
       echo "Failed";
   fi
   echo ------
done


But I'm really pleased you've given me something else to try though. I really took this on because I felt partly responsible for the lost coins: I distinctly remember misinforming him that the password was irrelevant, if you have the private key. What a douche. Obviously I now realise the password has been used to encrypt the private keys! Well, this gives me a chance to learn some new stuff. And I love a challenge. I'm going to be quite busy for the next two days with work but I'll get stuck into this at the weekend and whether or not I have any success, expect a little something coming your way.

Thanks again sir, you're a true gent.

Jon.

[btchris]

So....

.key files are encrypted with AES-256 (in CBC mode), which is a block cipher. It operates on blocks of exactly 16 bytes.

In order to deal with the case where a plaintext isn't a multiple of 16 bytes long, encryption tools often append additional padding bytes to the end of the plaintext to make it a multiple of 16 before encrypting it.

A very common padding standard (at least in the Bitcoin world) is standardized in PKCS7. MultiBit and openssl both use this style of padding.

When openssl decrypts a ciphertext, its exit status is zero (as you already know) if the decryption "succeeds", and non-zero otherwise. When a (properly encrypted) ciphertext is decrypted with the wrong key, the output should appear completely random. To check if a decryption succeeded, the only thing openssl can check is whether or not the padding at the end appears valid as per PKCS7.

After reading the description of that padding standard (linked above), you may notice if a plaintext is one byte short of being a multiple of 16 bytes long, the padding that must be appended is a single byte of value 0x01. That means that any ciphertext that happens (by random chance) to decrypt into a plaintext which ends in a 0x01, openssl has no choice but to assume that the decryption succeeded.

In short, about 1 in every 256 (actually slightly higher) decryption attempts will result in positives from openssl, even though they may be false positives.

btcrecover uses additional knowledge about what's in a decrypted .key file to throw out these false positives. Actually, btcrecover only bothers decrypting the first 16-byte block (in the interest of speed), and then it looks for a properly "WIF" encoded private key. This also has a chance of false positives, but it's on the order of 1 in 300 billion... much more palatable .

I'm going to be quite busy for the next two days with work but I'll get stuck into this at the weekend and whether or not I have any success, expect a little something coming your way.

Thanks! Tips always appreciated!

[nowhere man]

So I finally had a chance to give btcrecover a go tonight and all I can say is wow wow wow. I tested it with an encrypted empty multibit wallet password 123jonnyboy456 and the token %0,3djonnyboy%0,3d and the script found that password in a flash, so I know that your program clearly works, and damn quickly too. Just wanted to give you a quick message to say thanks a bunch and I'm going to spend the rest of tonight trying to crack my bro's password (with his permission - seriously don't worry!).

By the way, your explanation of the padding made a lot of sense too - so thank you for that! One thing I can't understand is how you do better than openssl. If the characters of the private key are (as I believe they should be) uniformly distributed with the exception of the padding on the end, how can you ever tell an honest decryption from a random decryption? I really need to look back over my notes from the coursera cryptography course I studied!

Still having great fun working on this. Will be back in touch after a couple of hours, hopefully with some good news.

All the best and speak soon

Jon. 

[btchris]

So I finally had a chance to give btcrecover a go tonight and all I can say is wow wow wow. I tested it with an encrypted empty multibit wallet password 123jonnyboy456 and the token %0,3djonnyboy%0,3d and the script found that password in a flash, so I know that your program clearly works, and damn quickly too.

Yeah... unfortunately, MultiBit Classic is one of only two popular wallets that uses no key stretching to improve brute-force resistance (well, I suppose that's "fortunately" for you ). Electrum is the other one. MultiBit HD (still in Beta) for the most part fixes this.

It also helps that btcrecover by default spawns one worker process per CPU core on your machine.

One thing I can't understand is how you do better than openssl. If the characters of the private key are (as I believe they should be) uniformly distributed with the exception of the padding on the end, how can you ever tell an honest decryption from a random decryption?

Encoded in binary, 32 out of the 33 bytes of a private key are uniformly distributed (the first is typically a flag byte to indicate whether or not the corresponding public key is compressed). However, MultiBit chooses to write the private keys into a .key file not in a binary format, but in a WIF-encoded format (which is then stored in plain ASCII). (This is to maintain compatibility with Bitcoin Core's import/export format.) It's easy to check for such a key, and extremely unlikely for such a correctly formatted key to appear at the beginning of an incorrectly decrypted .key file. It's so unlikely, that's why btcrecover only bothers decrypting the first 16-byte block.

I'll be around tonight (it's now early evening where I live), so let me know if you have any questions!

-Chris

[nowhere man]

Cheers Chris for all the help you've provided - I've sent a little something over to the wallet address on github as a donation (0.06btc). Its not much and it certainly won't compensate you for all the time you've put into developing that fantastic tool, but I hope it goes some way to saying thanks.

I haven't managed to crack the password yet, but I can be patient and quite stubborn about these things so I'm optimistic that all will be fine.
Even if I don't crack it, It's been really interesting for me looking at these issues in a practical context and learning lots and lots. I'd like to learn a bit more about it,

Updates on the wallet - I'm beginning to think that the tokens that my brother gave me have sent me on a wild goose chase, so I've resorted to using password lists. Your program seemed to manage that a bit better than using the token programme and six full willcards (90^6 possibilities there or thereabouts) where it naturally made my desktop collapse. I was thinking that next for me might be just exploring all possibilities for 8 lower case letters - although i think thats still 200 billion which is beyond what my desktop seems to take - Does a maximum of about 15million with the tokens and wild cards running sound right to you? Thats what I seem to get (I presume a memory problem??). With password lists I seem to be able to do about 50 or 60 million before I get a crash. If you have any suggestions for optimisation, I'd welcome them

Anyways, I will continue my search through the galaxy of passwords, desperately trying to uncover the right molecule..........

All the best dude and thanks once again!
Jon.

[btchris]

Cheers Chris for all the help you've provided - I've sent a little something over to the wallet address on github as a donation (0.06btc). Its not much and it certainly won't compensate you for all the time you've put into developing that fantastic tool, but I hope it goes some way to saying thanks.

That's very generous of you (especially considering I haven't actually helped yet )! The amount doesn't matter (much ), the sentiment absolutely does! Thank you!!

I've resorted to using password lists. Your program seemed to manage that a bit better than using the token programme and six full willcards (90^6 possibilities there or thereabouts) where it naturally made my desktop collapse.

If you're dealing with really big sets, there are a few things that can help (if you haven't noticed them already).

• the "--no-dupchecks" command-line option: saves a lot of RAM. Doing duplicate checking isn't very effective for MultiBit Classic .key files anyways.
• the "--max-tokens #" command-line option: if you limit the max # of tokens per guess, it can drastically reduce the # of permutations.
• the "--threads #" command-line option: the # defaults to the number of cores your CPU has, but sometimes using number_of_cores + 1 is a bit faster.

I was thinking that next for me might be just exploring all possibilities for 8 lower case letters - although i think thats still 200 billion which is beyond what my desktop seems to take

That number sounds right. My Desktop (an c. 2012 quad-core) would take about a week to run through that. Painful, but not impossible IMO.

(I presume a memory problem??). With password lists I seem to be able to do about 50 or 60 million before I get a crash. If you have any suggestions for optimisation, I'd welcome them

If you're running into memory issues or crashing, definitely use the "--no-dupchecks" command-line option I mentioned above. If there's some other sort of crash, could you post the full error message you're getting?