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

[cedivad]

I lost the password of my Electrum wallet. In fact, i didn't tough the wallet to have a password when i sent the money to it. What a dumb move, creating a password for the wallet 1.5 months ago, deleting the software, redownload it and suppose that since that he didn't asked, there wasn't any password. (the encrypted file was saved in my home directory).
I think to have a chance to brute force the password, but i need some more test speed, Electrum is in Python and it's really slow. I need to try at least one billion passwords.
So, if someone helps me by providing a GPU implementation of the following algorithm and i successfully recover my founds, i will be more than happy to reward him with 50BTC.

Code:

 def decode_seed(self, password):
        seed = self.pw_decode(self.seed, password)

        # check decoded seed with master public key
        curve = SECP256k1
        secexp = self.stretch_key(seed)
        master_private_key = ecdsa.SigningKey.from_secret_exponent( secexp, curve = SECP256k1 )
        master_public_key = master_private_key.get_verifying_key().to_string().encode('hex')
        if master_public_key != self.master_public_key:
            print_error('invalid password (mpk)')
            raise BaseException('Invalid password')

        return seed

def stretch_key(self,seed):
        oldseed = seed
        for i in range(100000):
            seed = hashlib.sha256(seed + oldseed).digest()
            exit()
        return string_to_number( seed )

I haven't found a john the ripper implementation for ECDSA, or it doesn't exist.
Here is a screenshoot of my wallet so that you can check whatever or not i successfully retrieve the founds.

(edit: removed).

If someone is willed to try, thank you.

[Scrat Acorns]

So you do know part of the password? What brute force scheme would you like to run? If you don't know anything about the password and it is more than 8 characters forget it.

ECDSA GPU code is here btw:
https://github.com/samr7/vanitygen/blob/master/oclengine.c

But that's only part of the equation. The key derivation function used will make it a lot slower.

[cedivad]

So you do know part of the password? What brute force scheme would you like to run? If you don't know anything about the password and it is more than 8 characters forget it.

ECDSA GPU code is here btw:
https://github.com/samr7/vanitygen/blob/master/oclengine.c

But that's only part of the equation. The key derivation function used will make it a lot slower.

I have several patterns I would like to try. The whole password could be even 10-12 characters. I want to try.

Sorry, what is the key derivation function? The 10000 sha256?

[Scrat Acorns]

Sorry, what is the key derivation function? The 10000 sha256?

It stretches the key by performing 100,000 sha256 rounds.

A Radeon 7970 can do about a billion sha256 / second. With this it's reduced to 10k hashes/sec. At this rate you can do the ECDSA part on the CPU (in C of course, not python) since it's at least 40 times faster than that.

So you don't even need an ECDSA GPU implementation.

[cedivad]

Cool cool cool.
Thank you for the valuable info.

I will try to code something.

[stick]

So you have your 12 word master seed and you are missing your wallet password or?

[etotheipi]

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.  

[oakpacific]

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?

[etotheipi]

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.

[oakpacific]

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.

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?

[grue]

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

[cedivad]

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!

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

[cedivad]

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

[w1R903]

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

[vamdor]

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.

[cedivad]

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

[Zeilap]

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.

[etotheipi]

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.

[Wotan777]

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

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