Pages:
Author

Topic: [Bounty 50BTC] Looking for a GPU implementation of this algorithm (Read 5384 times)

hero member
Activity: 672
Merit: 504
a.k.a. gurnec on GitHub
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!
hero member
Activity: 784
Merit: 500
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("crc_bytes = struct.pack("
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
newbie
Activity: 37
Merit: 0
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.
hero member
Activity: 672
Merit: 504
a.k.a. gurnec on GitHub
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("crc_bytes = struct.pack("
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!
hero member
Activity: 672
Merit: 504
a.k.a. gurnec on GitHub
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).
hero member
Activity: 784
Merit: 500
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.
sr. member
Activity: 441
Merit: 266
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.
hero member
Activity: 672
Merit: 504
a.k.a. gurnec on GitHub
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).
newbie
Activity: 37
Merit: 0
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.

Sample Python code:


# -*- coding: utf-8 -*-

import aes
import hashlib
import base64

DecodeAES = lambda secret, e: aes.decryptData(secret, base64.b64decode(e))

def sha256(x):
    return hashlib.sha256(x).digest()

def Hash(x):
    if type(x) is unicode: x=x.encode('utf-8')
    return sha256(sha256(x))

def pw_decode(s, password):
    if password is not None:
        secret = Hash(password)
        try:
            d = DecodeAES(secret, s)
        except Exception, e:
            raise Exception('Invalid password')
        return d
    else:
        return s

def try_pw(encoded_seed, pw_cand):
  seed = ''
  try:
    seed = pw_decode(encoded_seed, pw_cand)
  except Exception:
    seed = ''
  finally:
    pass
  return seed

def chk_seed(seed):
  if len(seed) == 0:
    return False
  cnt=0;
  for c in seed:
    cnt+=1
    if cnt>32:
      return True
    i = ord(c)
    if i<48:
      return False
    if i>57:
      if i<97:
        return False
      if i>102:
        return False
  return True

def test():
  encoded_seed = 'Ww9jsiumblVPSM5owcLS6wODqxh0YDLIg/g+mNv+nuNP+f7yyhqOomTlK9tDv8xV0kYt/nUDeTZNtUOr3Zfp2w=='
  # pw_cand = 'test'
 
  cnt = 0
  cnt_good = 0
  for c1 in 't': #'abcdefghijklmnopqrstuvwxyz':
    for c2 in 'abcdefghijklmnopqrstuvwxyz':
      for c3 in 'abcdefghijklmnopqrstuvwxyz':
        for c4 in 'abcdefghijklmnopqrstuvwxyz':
          pw_cand1 = c1 + c2 + c3 + c4
          cnt += 1
          seed = try_pw(encoded_seed, pw_cand1)
          # print seed
          if chk_seed(seed):
            print 'pw is good: %s' % pw_cand1
            cnt_good +=1
  print 'cnt: %d' % cnt
  print 'cnt_good: %d' % cnt_good

test()


If you run it, it correctly finds the password:


$ python m2.py
pw is good: test
cnt: 676
cnt_good: 1


This "proof of a concept" code uses only  two SHA256 and one AES256 to try a password.
Its speed can be optimized to 10**7 (maybe 10**8 ) trials/sec/CPU_core.

So, with 128 cores, 10**15 (maybe 10**16) passwords can be checked in a day (at least in theory).

It is up to cedivad, what to do with that discovery...


legendary
Activity: 1428
Merit: 1093
Core Armory Developer
I haven't found a john the ripper implementation for ECDSA, or it doesn't exist.
From the code you pasted, it seems that the real issue here is the 10000 rounds of SHA256, not the ECDSA. It may be worth trying to put only the "stretch_key" method on a gpu, and then do the ECDSA on the CPU. Probably much less work to implement, but still a significant speed-up compared to naively running this python script.
A friend of mine said that he tried but he can't run ecdsa at a good speed... Not sure of why this doesent agree with other posts here...
I think I read that openssl has a purposely crippled implementation because otherwise timing information is leaked which can be used to recover the private key. I don't know the details, but there was a thread about it on here at some point. Maybe that's the problem - try a different ECDSA library designed for speed rather than security.

ECDSA is slow.  No matter how you look at it.  Implementations slow it down further in order to improve robustness to things like timing attacks, but you're just not going to get a fast implementation on a CPU.  I think 1,000/sec/core is about what you can expect.

But the other poster is right -- this is not really an ECDSA problem -- it's a hashing problem.  And there's plenty of hashing algos already implemented on GPUs.  It is probably reasonable to run hashing on the GPU, and then send a steady stream of results to the CPU for checking the answer.  Even if your GPU has lots of cores, I'm not sure it will out-pace the CPU-ECDSA compute speed.  This is probably a reasonable approach.
full member
Activity: 154
Merit: 100
I haven't found a john the ripper implementation for ECDSA, or it doesn't exist.
From the code you pasted, it seems that the real issue here is the 10000 rounds of SHA256, not the ECDSA. It may be worth trying to put only the "stretch_key" method on a gpu, and then do the ECDSA on the CPU. Probably much less work to implement, but still a significant speed-up compared to naively running this python script.
A friend of mine said that he tried but he can't run ecdsa at a good speed... Not sure of why this doesent agree with other posts here...
I think I read that openssl has a purposely crippled implementation because otherwise timing information is leaked which can be used to recover the private key. I don't know the details, but there was a thread about it on here at some point. Maybe that's the problem - try a different ECDSA library designed for speed rather than security.
legendary
Activity: 1176
Merit: 1001
I haven't found a john the ripper implementation for ECDSA, or it doesn't exist.
From the code you pasted, it seems that the real issue here is the 10000 rounds of SHA256, not the ECDSA. It may be worth trying to put only the "stretch_key" method on a gpu, and then do the ECDSA on the CPU. Probably much less work to implement, but still a significant speed-up compared to naively running this python script.
A friend of mine said that he tried but he can't run ecdsa at a good speed... Not sure of why this doesent agree with other posts here...
newbie
Activity: 50
Merit: 0
I haven't found a john the ripper implementation for ECDSA, or it doesn't exist.
From the code you pasted, it seems that the real issue here is the 10000 rounds of SHA256, not the ECDSA. It may be worth trying to put only the "stretch_key" method on a gpu, and then do the ECDSA on the CPU. Probably much less work to implement, but still a significant speed-up compared to naively running this python script.
full member
Activity: 218
Merit: 100

If someone is willed to try, thank you.

You didn't record your wallet generation seed mnemonic anywhere?  The 12-word passphrase you would have been shown at the beginning?  Did you record it and delete the file, or not record it?

You said the password may be up to 12 chars long and you remember specific parts of the password.  Do you know the order of those parts, like if they are beginning, end, etc.?
legendary
Activity: 1176
Merit: 1001
Guys, UP.
To whoever is willed to implement this in a short timeframe (<24H), 1000$ is my bounty. It will be payed at the delivery of the code, not if the crack is successful like i said in the first post.

I might be wrong but i think that for experienced coders this should be just as simple as copying existing projects into this, a few hours of work.

The program will have to run at at least 2000 tests/second on my 7970 (the os is up to you).
legendary
Activity: 1176
Merit: 1001
why not just farm this out to an amazon ec2 cluster? 50 BTC can buy a lot of compute time.
Well, you have a point here. I'm doing some calculations... let's see...
250BTC = 15k$. I'm assuming that a server with a 7970 will be priced at 250$ monthly and that, standing to the posts above this, it will do 10k tests/second. 15000/250 = 60 servers * 86400*30 seconds * 10k tests/second => 10^12 combinations to test. 52 ^ 8 = 10^13. I'm still one order of magnitude off.

Five to ten years from now, i'm quite sure that i will be able to recover the money.

It will be funny! Smiley

---
I should find the time to try some combinations, at least the billion i was referring to on the first post, i think to have a good chance that way. I'm afraid that brute forcing the password using a raw alphabet won't work, it's probably much longer than 8 characters. Fortunately, it's also is most probably composite with other stuff i remember.
legendary
Activity: 2058
Merit: 1431
why not just farm this out to an amazon ec2 cluster? 50 BTC can buy a lot of compute time.
hero member
Activity: 784
Merit: 1000
This is exactly why Armory uses a scrypt-like algorithm for its wallet encryption.  It does the 100,000 hashes of the passphrase, but requires them to all be stored in RAM at once, so you can do 100,000 table-lookups on it to get the final result.  This makes GPU-acceleration pretty useless for an attacker (GPU threads usually only have a tiny amount of fast memory, not megabytes).    That's why the Armory website advertises "GPU-resistant wallet encryption".  (for reference, it's called the ROMix algorithm -- found in the same paper as scrypt, it's just that ROMix is much simpler despite being much less flexible about compute-memory tradeoff)

On the other hand, if you forget your password, you likely remember enough of it that you may only require a few weeks of single-threaded processing to find it.  

Sorry, but on the Armory it said the wallet is encrypted with AES256, why is that?

It is encrypted with AES256.  There's two distinct steps to unlocking your wallet:

  • (1) Convert your password to an encryption key
  • (2) Use the key to encrypt your wallet with AES256

Passphrase --> 32-byte AES256 key --> Encrypt Wallet

The encryption key is a full 32-bytes of data, which would be impossible to guess.  But your password/passphrase is much less than that.  So an attacker doesn't need to guess the encryption key if they guess your password -- so they just need to guess a bunch of passwords, run them through (1), and then check if it's correct.

Bitcoin-Qt and Armory both do this, they just use a different step-1:  X,000 sequential hashes, forcing the attacker to spend a full 0.1-0.25 seconds to check whether they got your password correct.  The difference is that the key-stretching used in Bitcoin-Qt only requires compute-time.  It only requires a few dozen bytes of fast-access memory to convert your passphrase to an encryption key, it just requires a lot of hashes.  Because of this, is very parallelizable -- an attacker with a bunch of GPUs having 2,000 threads each can get 100-1000x speedup compared to only using their CPU.

But Armory key-stretching (and scrypt-based algorithms) requires each thread to have access to megabytes of fast-access RAM.  Thus, you might not be able to put it on a GPU at all, or you would only be able to run 10 of those 2,000 threads at once.  In that case, you might as well just use a CPU.

Ah, I see, so it maybe slightly better to say "wallet key encryption" to avoid the confusion. Smiley

So in principle can certain key-stretching algorithms generate brute-force resistant keys from even relatively weak passwords(Say, only 8 characters with one capital), as long as the password is not commonplace?
legendary
Activity: 1428
Merit: 1093
Core Armory Developer
This is exactly why Armory uses a scrypt-like algorithm for its wallet encryption.  It does the 100,000 hashes of the passphrase, but requires them to all be stored in RAM at once, so you can do 100,000 table-lookups on it to get the final result.  This makes GPU-acceleration pretty useless for an attacker (GPU threads usually only have a tiny amount of fast memory, not megabytes).    That's why the Armory website advertises "GPU-resistant wallet encryption".  (for reference, it's called the ROMix algorithm -- found in the same paper as scrypt, it's just that ROMix is much simpler despite being much less flexible about compute-memory tradeoff)

On the other hand, if you forget your password, you likely remember enough of it that you may only require a few weeks of single-threaded processing to find it.  

Sorry, but on the Armory it said the wallet is encrypted with AES256, why is that?

It is encrypted with AES256.  There's two distinct steps to unlocking your wallet:

  • (1) Convert your password to an encryption key
  • (2) Use the key to encrypt your wallet with AES256

Passphrase --> 32-byte AES256 key --> Encrypt Wallet

The encryption key is a full 32-bytes of data, which would be impossible to guess.  But your password/passphrase is much less than that.  So an attacker doesn't need to guess the encryption key if they guess your password -- so they just need to guess a bunch of passwords, run them through (1), and then check if it's correct.

Bitcoin-Qt and Armory both do this, they just use a different step-1:  X,000 sequential hashes, forcing the attacker to spend a full 0.1-0.25 seconds to check whether they got your password correct.  The difference is that the key-stretching used in Bitcoin-Qt only requires compute-time.  It only requires a few dozen bytes of fast-access memory to convert your passphrase to an encryption key, it just requires a lot of hashes.  Because of this, is very parallelizable -- an attacker with a bunch of GPUs having 2,000 threads each can get 100-1000x speedup compared to only using their CPU.

But Armory key-stretching (and scrypt-based algorithms) requires each thread to have access to megabytes of fast-access RAM.  Thus, you might not be able to put it on a GPU at all, or you would only be able to run 10 of those 2,000 threads at once.  In that case, you might as well just use a CPU.
hero member
Activity: 784
Merit: 1000
This is exactly why Armory uses a scrypt-like algorithm for its wallet encryption.  It does the 100,000 hashes of the passphrase, but requires them to all be stored in RAM at once, so you can do 100,000 table-lookups on it to get the final result.  This makes GPU-acceleration pretty useless for an attacker (GPU threads usually only have a tiny amount of fast memory, not megabytes).    That's why the Armory website advertises "GPU-resistant wallet encryption".  (for reference, it's called the ROMix algorithm -- found in the same paper as scrypt, it's just that ROMix is much simpler despite being much less flexible about compute-memory tradeoff)

On the other hand, if you forget your password, you likely remember enough of it that you may only require a few weeks of single-threaded processing to find it.  

Sorry, but on the Armory UI it says the wallet is encrypted with AES256, why is that?
Pages:
Jump to: