Bitcoin Forum
November 20, 2017, 10:23:38 AM *
News: Latest stable version of Bitcoin Core: 0.15.1  [Torrent].
 
   Home   Help Search Donate Login Register  
Pages: « 1 [2]  All
  Print  
Author Topic: [Bounty 50BTC] Looking for a GPU implementation of this algorithm  (Read 4865 times)
stick
Sr. Member
****
Offline Offline

Activity: 439



View Profile
July 02, 2014, 07:14:09 PM
 #21

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.

1511173418
Hero Member
*
Offline Offline

Posts: 1511173418

View Profile Personal Message (Offline)

Ignore
1511173418
Reply with quote  #2

1511173418
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1511173418
Hero Member
*
Offline Offline

Posts: 1511173418

View Profile Personal Message (Offline)

Ignore
1511173418
Reply with quote  #2

1511173418
Report to moderator
1511173418
Hero Member
*
Offline Offline

Posts: 1511173418

View Profile Personal Message (Offline)

Ignore
1511173418
Reply with quote  #2

1511173418
Report to moderator
1511173418
Hero Member
*
Offline Offline

Posts: 1511173418

View Profile Personal Message (Offline)

Ignore
1511173418
Reply with quote  #2

1511173418
Report to moderator
fran2k
Hero Member
*****
Offline Offline

Activity: 770


View Profile WWW
July 02, 2014, 11:40:45 PM
 #22

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
Hero Member
*****
Offline Offline

Activity: 672

a.k.a. gurnec on GitHub


View Profile WWW
July 03, 2014, 01:10:11 AM
 #23

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
Hero Member
*****
Offline Offline

Activity: 672

a.k.a. gurnec on GitHub


View Profile WWW
July 03, 2014, 01:33:30 AM
 #24

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 Wink

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
Jr. Member
*
Offline Offline

Activity: 37


View Profile
July 04, 2014, 07:16:56 AM
 #25

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
Hero Member
*****
Offline Offline

Activity: 770


View Profile WWW
July 05, 2014, 04:57:36 PM
 #26

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 Wink

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. Smiley
btchris
Hero Member
*****
Offline Offline

Activity: 672

a.k.a. gurnec on GitHub


View Profile WWW
July 06, 2014, 04:01:03 PM
 #27

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!
Pages: « 1 [2]  All
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!