[Bounty 50BTC] Looking for a GPU implementation of this algorithm

[stick]

860k tries per second per core here (Intel(R) Core(TM) i5 CPU @ 2.67GHz)

but I'd guess it could be improved if written entirely in C, or even better in OpenCL....

I don't think that GPU can beat CPU with AES-NI.

[1714024245]

1714024245

[1714024245]

1714024245

[1714024245]

1714024245

[1714024245]

1714024245

[fran2k]

I have made an interesting discovery: if you know the encoded seed of an Electrum wallet, then you can recover the unencrypted seed without the password stretching and fancy Elliptic Curve stuff. Simply try to decode the password, and if you get a valid hexadecimal number of 32 characters, then the password candidate is good, otherwise it is bad.
...
Its speed can be optimized to 10**7 (maybe 10**8 ) trials/sec/CPU_core.

Yup, that's exactly what I'm doing in btcrecover here. I'm only managing around 10^5 tries/s per CPU core (it's written in Python but uses libraries for SHA and AES written in C) but I'd guess it could be improved if written entirely in C, or even better in OpenCL....

It turns out that you can play similar tricks with many wallet encryption schemes (but not with Armory as far as I could find - Armory really got wallet encryption right).

Woh, great code there!

I have some wallet I do want to recovery. I did a dump with pywallet and discarded the wallet.dat long time ago. I do have a dictionary I made. Can I use the btcrecover starting from the pywallet data? Or I was guessing if I just can reconstruct the wallet.dat from another one, but that looks messy.

[btchris]

860k tries per second per core here (Intel(R) Core(TM) i5 CPU @ 2.67GHz)

Yeah, btcrecover has a lot of scaffolding to actually generate the passwords to test... still that's faster than I expected.
 

but I'd guess it could be improved if written entirely in C, or even better in OpenCL....

I don't think that GPU can beat CPU with AES-NI.

That could be true (I doubt PyCrypto uses AES-NI). Although the oclHashcat guys have done some impressive things, including password generation and AES decryption all on a GPU, which is far more than I've managed (I only do SHA's for Bitcoin Core in GPU, everything else is in CPU).

[btchris]

Woh, great code there!

I have some wallet I do want to recovery. I did a dump with pywallet and discarded the wallet.dat long time ago. I do have a dictionary I made. Can I use the btcrecover starting from the pywallet data? Or I was guessing if I just can reconstruct the wallet.dat from another one, but that looks messy.

Thanks for the compliment, flattery will get you everywhere

Getting what btcrecover needs from the pywallet dump is pretty easy.... if you actually manage to find the password, we can worry about the rest later.

Save only the "mkey" section from the pywallet dump to a new file, e.g. it should contain only something like this:

Code:

{
    "encrypted_key": "2e2c3b9b58e9b33c9799b4472e83c136e6246120c45e390daa6a57476e7fbe4f57d83f79d75f9b4c1db680fe5a846cb8", 
    "nDerivationIterations": 67908, 
    "nDerivationMethod": 0, 
    "nID": 1, 
    "otherParams": "", 
    "salt": "4593aff5639179c7"
}

The Python script below produces output in the same format as extract-bitcoincore-mkey.py, but it uses the file above instead of a wallet.dat file. Give it the filename from above as the first argument, and it will print out some base64-encoded stuff that btcrecover can use:

Code:

import sys, json, struct, base64, zlib

data = json.load(open(sys.argv[1]))

encrypted_master_key = base64.b16decode(data["encrypted_key"], True)
salt                 = base64.b16decode(data["salt"], True)
iter_count           = data["nDerivationIterations"]

bytes     = b"bc:" + encrypted_master_key + salt + struct.pack("<I", iter_count)
crc_bytes = struct.pack("<I", zlib.crc32(bytes) & 0xffffffff)

print(base64.b64encode(bytes + crc_bytes))

Then you can feed that into btcrecover like this:

Code:

btcrecover.py --extract-data --passwordlist existing-dictionary-file.txt
Please enter the data from the extract script
> lV/wGO5oAUM42KTfq5s3egX3Uhk6gc5gEf1R3TppgzWNW7NGZQF5t5U3Ik0qYs5/dprb+ifLDHuGNQIA+8oRWA==
...
Password found: xxxx

If the dictionary file is particularly long, it might be worth trying to get the somewhat experimental GPU support working-- it can improve speed w/Bitcoin Core wallets from somewhere in the 50s to somewhere in the 1000s (tries per second), but it can take some effort to get working well.

Good luck!

[Wotan777]

Hi, btchris!

I have made an interesting discovery: if you know the encoded seed of an Electrum wallet, then you can recover the unencrypted seed without the password stretching and fancy Elliptic Curve stuff. Simply try to decode the password, and if you get a valid hexadecimal number of 32 characters, then the password candidate is good, otherwise it is bad.
...
Its speed can be optimized to 10**7 (maybe 10**8 ) trials/sec/CPU_core.

Yup, that's exactly what I'm doing in btcrecover here. I'm only managing around 10^5 tries/s per CPU core (it's written in Python but uses libraries for SHA and AES written in C) but I'd guess it could be improved if written entirely in C, or even better in OpenCL....

It turns out that you can play similar tricks with many wallet encryption schemes (but not with Armory as far as I could find - Armory really got wallet encryption right).

Very nice program!
I tried it yesterday, with an Electrum wallet.
I modified it to use only the first 44 characters of the encoded seed:

Code:

$ diff btcrecover.py btcrecover_mod.py
572c572
<     if len(wallet) != 64:                raise ValueError("Electrum encrypted seed plus iv is not 64 bytes long")
---
>     ###if len(wallet) != 64:                raise ValueError("Electrum encrypted seed plus iv is not 64 bytes long")
580c580
<     encrypted_seed, iv   = wallet[16:], wallet[:16]
---
>     encrypted_seed, iv   = wallet[16:32], wallet[:16]
584,585c584,587
<         # If the 48 byte encrypted seed decrypts to exactly 32 bytes long (padded with 16 16s), we've found it
<         if seed.endswith(b"\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10"):
---
>         ### # If the 48 byte encrypted seed decrypts to exactly 32 bytes long (padded with 16 16s), we've found it        
>         ### if seed.endswith(b"\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10"):
>         # if all the digits are hexadecimal
>         if all(c in string.hexdigits for c in seed):

Maybe you can use it to extend your extract-scripts with Electrum as well.

[fran2k]

Woh, great code there!

I have some wallet I do want to recovery. I did a dump with pywallet and discarded the wallet.dat long time ago. I do have a dictionary I made. Can I use the btcrecover starting from the pywallet data? Or I was guessing if I just can reconstruct the wallet.dat from another one, but that looks messy.

Thanks for the compliment, flattery will get you everywhere

Getting what btcrecover needs from the pywallet dump is pretty easy.... if you actually manage to find the password, we can worry about the rest later.

Save only the "mkey" section from the pywallet dump to a new file, e.g. it should contain only something like this:

Code:

{
    "encrypted_key": "2e2c3b9b58e9b33c9799b4472e83c136e6246120c45e390daa6a57476e7fbe4f57d83f79d75f9b4c1db680fe5a846cb8", 
    "nDerivationIterations": 67908, 
    "nDerivationMethod": 0, 
    "nID": 1, 
    "otherParams": "", 
    "salt": "4593aff5639179c7"
}

The Python script below produces output in the same format as extract-bitcoincore-mkey.py, but it uses the file above instead of a wallet.dat file. Give it the filename from above as the first argument, and it will print out some base64-encoded stuff that btcrecover can use:

Code:

import sys, json, struct, base64, zlib

data = json.load(open(sys.argv[1]))

encrypted_master_key = base64.b16decode(data["encrypted_key"], True)
salt                 = base64.b16decode(data["salt"], True)
iter_count           = data["nDerivationIterations"]

bytes     = b"bc:" + encrypted_master_key + salt + struct.pack("<I", iter_count)
crc_bytes = struct.pack("<I", zlib.crc32(bytes) & 0xffffffff)

print(base64.b64encode(bytes + crc_bytes))

Then you can feed that into btcrecover like this:

Code:

btcrecover.py --extract-data --passwordlist existing-dictionary-file.txt
Please enter the data from the extract script
> lV/wGO5oAUM42KTfq5s3egX3Uhk6gc5gEf1R3TppgzWNW7NGZQF5t5U3Ik0qYs5/dprb+ifLDHuGNQIA+8oRWA==
...
Password found: xxxx

If the dictionary file is particularly long, it might be worth trying to get the somewhat experimental GPU support working-- it can improve speed w/Bitcoin Core wallets from somewhere in the 50s to somewhere in the 1000s (tries per second), but it can take some effort to get working well.

Good luck!

Lot of Thanks!

I´m already running it.

[btchris]

Hi, btchris!
...
I tried it yesterday, with an Electrum wallet.
I modified it to use only the first 44 characters of the encoded seed:

Code:

...

Maybe you can use it to extend your extract-scripts with Electrum as well.

You're right, the unencrypted seed is all hex, I completely missed that. That reduces each check from three AES block decryptions down to just one, and as you noticed makes an extract script possible which only extracts half the seed, still leaving 64 bits of unknown entropy once/if the password is found. I'll definitely be incorporating these improvements and an extract script for Electrum, thanks for discovering this!