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

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!

Lot of Thanks!

I´m already running it.

Hi, btchris!


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:


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

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:


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:


Then you can feed that into btcrecover like this:


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!

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

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).

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.

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


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

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).

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...

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.

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.

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...

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.

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.?

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).

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!

---
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.

why not just farm this out to an amazon ec2 cluster? 50 BTC can buy a lot of compute time.

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

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?

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.

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