Add support for Electrum Bitcoin Wallet

[kholia]

Useful links,

• https://github.com/spesmilo/electrum/blob/master/lib/storage.py#L118-L121 (KDF = PBKDF2 + some ECC stuff)
• https://github.com/spesmilo/electrum/blob/master/lib/bitcoin.py#L670 (password validation, secp256k1 ECC is involved)

These findings apply to Electrum 2.7+ encrypted wallets. The primitives involved in older versions are quite different.

[kholia]

@magnumripper

It seems that a secp256k1 implementation is required for implementing this format. I am planning to trim down https://github.com/bitcoin-core/secp256k1 for inclusion in JtR jumbo (similar to how aes stuff is handled).

The work-in-progress code is at https://github.com/kholia/JohnTheRipper/tree/electrum location.

I am trying to figure out how aes.a is automatically built when I run make. How do I make sure that the new secp256k1.a also get built in a similar fashion? I have some of the stuff in place (see my branch) for doing so but something seems to be missing.

[kholia]

Looking at https://pypi.python.org/pypi/coincurve can be helpful in implementing support for cracking Electrum 2.7+ encrypted wallets.

[gurnec]

Just an FYI, but you don't need to do any EC math to check an Electrum password. (You generally do however for Armory wallets which I see is also on the list.)

If anything, the annoying part for Electrum wallets is dealing with 3 different wallet versions (1.x, 2.0-2.6, 2.7+), some of which also have different wallet types. All this is best done in a separate Python extraction script IMO.

At the end of the day, it's a matter of extracting base64-encoded data from the right place in a wallet file, decoding it into 16 bytes of IV and 16 bytes of ciphertext (either the first or the last 16-byte AES block, depending on from where it's extracted, is sufficient), and comparing the plaintext from each guess to an expected pattern.

The cryptographic primitives are the same across all formats:

key = sha256( sha256( utf8( password ) ) )
plaintext = aes256_cbc( key, iv, ciphertext )

There are three possible patterns which can be narrowed down to one depending on the wallet version/type from which the cipertext was extracted. The plaintext is either:

• 16 bytes of lowercase hex
• a BIP32 extended private key, e.g. "xprv" followed by 12 base58 characters ([1-9A-HJ-NP-Za-km-z])
• the last block of a "WIF" format private key -- 3 or 4 base58 characters followed by 13 or 12 valid PKCS7 padding characters

The second one above has the worst false positive rate. If my math is right, it's around 1 in 2⋅10¹⁷, which seems a fair trade off to me for the (considerable) extra speed of avoiding EC math.

I can follow up sometime later with some more details if it would be helpful.

[kholia]

@gurnec Thanks for your work in this area and these tips!

The hash extraction script, called electrum2john.py, can be found here. The cracking code can be found here. These programs are majorly based on your work.

As far as I can tell, encrypted modern Electrum wallet format is neither supported by btcrecover nor JtR, at the moment. I am not sure about when this new encrypted wallet format was introduced.

Here is a sample encrypted Electrum 2.9.0 wallet which btcrecover doesn't recognize. This wallet is not in JSON format. While the previous versions of Electrum wallets don't need EC math for cracking, I believe that EC match is required for cracking this new Electrum wallet format. I will double-check this by reading the Electrum source code (https://github.com/spesmilo/electrum).

[kholia]

Here is how this "modern" wallet encryption is turned on. I am using Electrum 2.9.0 from Git sources.

[gurnec]

Heh, I feel quite silly... thanks for being gentle with my complete failure to read/stay up-to-date on both the Electrum and JtR sides!

You're absolutely right, Electrum's new whole-file encryption requires a scalar multiply (and a modular square root), I can't see any way around them. (Also, just a minor nit - it's Electrum 2.8 which added this, there's no 2.9 as of yet).

I managed to walk through a decryption of an Electrum wallet using my preferred ECC library in Python (Crypto++, because it's convenient, not because it's the best or fastest option). Here are some thoughts, in case it helps.

First, there may be a problem with using just libsecp256k1. From what I can tell, it supports fixed-size 256-bit scalars (as would be expected for the 256k1 curve). Electrum inexplicably multiplies by a 512-bit scalar, you can see Electrum generate the scalar here. So if that's right, you'd need to reduce that 512-bit number modulo the curve order to get it down to a 256-bit number using some other arbitrary precision integer library before passing it to libsecp256k1 (or use some other ECC library). Incidentally, Crypto++ has no issue with the 512-bit scalar.

Second, there's the issue of how to recognize a correct password as quickly as possible. The plaintext is zlib-compressed JSON. I'd prefer to do as little AES decryption as possible in the interest of speed. Also, from a JtR point of view, it's probably not great to require the entire Electrum file be encoded into a JtR passwords/hashes file. Here are a few shortcuts which may help:

• Decrypting just the first AES block gives 19 bits of zlib/deflate header which I think doesn't change. Specifically, plaintext[0..1] == 0x78, 0x9c and plaintext[2] & 0x7 == 0x5.
• Decrypting just the last block gives us PKSC7 padding which can be validated.
• It should be possible to decrypt a few initial blocks, and feed them to zlib to see if we get any errors or if we start getting a JSON file which for Electrum always starts with {\n " (that's 4 spaces in there, and the \n can be either LF or CRLF). One problem is deciding how many blocks to decrypt; in my first test, I had to decrypt 5 blocks to get that string, but that can change depending on the length of the Huffman codes.
• Decrypting everything and checking it against the HMAC at the end of the file.
• Checking the ciphertext against the HMAC at the end of the file, which requires no AES decryptions, but does require access to (and the HMACing of) the entire ciphertext.

These are the only shortcuts I've found so far... please take them with a grain of salt, none of this is well tested yet. If/when I get around to implementing this in btcrecover, I'll be sure to post back.

[kholia]

I was planning on using libsecp256k1 but I don't know anything about ECC at the moment. I am planning to experiment with coincurve (python package) to learn a bit about ECC.

Update: It does seem that libsecp256k1 won't handle a 512-bit scalar/secret (called seckey in secp256k1_ec_pubkey_create function).

[gurnec]

I just pushed an update to btcrecover which supports the new wallet format if you're interested: gurnec/btcrecover@34b897214e522dfeb07c056c566b51a92c281ce7

Regarding the "shortcuts" -- I ended up using the first, second, and last from the list above. The last one might not be an option for JtR though... as already mentioned it would involve encoding an entire wallet file into the JtR passwords/hashes file.

Even though Crypto++ supports 512-bit ints (and so does Python), it turned out to be faster to reduce the int in Python just before calling Crypto++'s scalar-multiply (you can see it here). I assume you'd need a different library (GMP?) to do this before passing the int to libsecp256k1.

In any case, adding support to JtR looks like it might be a bit painful. libsecp256k1 may have good performance, but it doesn't look like the easiest option out there...

[kholia]

Thanks!

Yes, libsecp256k1 doesn't seem very easy to use. I am having trouble understanding how to do the following operation using libsecp256k1,

ephemeral_pubkey = self._crypto_ecdsa.UncompressPoint(btcrseed.SecureBinaryData(ephemeral_pubkey)).toBinStr()

In electrum source code the same operation is done as,

ephemeral_pubkey = ser_to_point(ephemeral_pubkey)

and ser_to_point function seems hard to translate to libsecp256k1.

Update: I learned a bit about libsecp256k1 and came up with the following code,

secp256k1_context *ctx;
secp256k1_pubkey pubkey;
int ret;

print_hex(ephemeral_pubkey, 33);  // this matches btcrecover

ctx = secp256k1_context_create(SECP256K1_CONTEXT_NONE);
ret = secp256k1_ec_pubkey_parse(ctx, &pubkey, ephemeral_pubkey, 33);

The ret value is 0 which means that the compressed public key was not parsed. I wonder what I am doing wrong.

This code is in https://github.com/kholia/JohnTheRipper/tree/electrum branch, if you would like to take a look.

Update 2: There was a problem with my hacks to make libsecp256k1 build without Autotools stuff. After removing my hacks, secp256k1_ec_pubkey_parse is working just fine.

[kholia]

Update 3: I was able to reduce the 512-bit PBKDF2 output modulo the curve order using OpenSSL. The latest code is at https://github.com/kholia/JohnTheRipper/tree/electrum URL.

Now I am trying to implement the following btcrecover operation using libsecp256k1,

shared_pubkey  = self._crypto_ecdsa.ECMultiplyPoint(static_privkey, self._ephemeral_pubkey_x, self._ephemeral_pubkey_y)

The corresponding code in electrum source code seems to be,

ecdh_key = point_to_ser(ephemeral_pubkey * self.privkey.secret_multiplier)

As far as I can see, libsecp256k1 doesn't seem to have such functionality. Or does it?

It seems I need to use secp256k1_ecdh function from libsecp256k1. However, it does not generate the same shared_pubkey / ecdh_key ;(

Update 4: I was able to figure this out! It turned out that secp256k1_ecdh doesn't do what we want but I was able to borrow code from it to implement the required point * scalar operation. Cracking works fine now :-)

[gurnec]

Update 4: I was able to figure this out! It turned out that secp256k1_ecdh doesn't do what we want but I was able to borrow code from it to implement the required point * scalar operation. Cracking works fine now :-)

That's great!

I do have a small suggestion for you. secp256k1_ecmult_const was written to be hardened against timing attacks. Assuming that JtR doesn't care about timing attacks, it's possible to speed things up a little.

Use secp256k1_ecmult instead, it's supposedly around 20-25% faster (though I don't know how much effect this will have overall). It has a different interface because it performs a double-multiply:

/** Double multiply: R = na*A + ng*G */
static void secp256k1_ecmult(const secp256k1_ecmult_context *ctx, secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_scalar *na, const secp256k1_scalar *ng);

But you can just set ng to 0 to drop out the last term. As an example, the secp256k1_eckey_pubkey_tweak_mul function does exactly this.

As a further optimization, you could copy the code from secp256k1_eckey_pubkey_tweak_mul into your multiply function, but move the calls to secp256k1_scalar_set_int, secp256k1_pubkey_load, and secp256k1_gej_set_ge (and maybe also secp256k1_context_create/destroy?) outside the password loop instead calling them just once per Electrum wallet during init. (although I kind of doubt this second optimization would result in much noticeable speedup...?)

[kholia]

@magnumripper Hello, I need your help in figuring out the autotools related changes needed for including the libsecp256k1 library in JtR source tree. https://github.com/kholia/JohnTheRipper/tree/electrum (top commit) has the latest code.

I have made changes to configure, configure.ac, Makefile.in to build secp256k1/secp256k1.a upon running make. However, secp256k1/secp256k1.a isn't getting built when doing make. Currently, I have to cd into secp256k1 directory and run make to build secp256k1.a file. It seems like I am missing a step somewhere but I can't spot it.

[kholia]

@magnumripper I was able to figure out this build problem. I was missing the following change,

diff --git a/src/Makefile.in b/src/Makefile.in
index d4adf62..d165b26 100644
--- a/src/Makefile.in
+++ b/src/Makefile.in
@@ -562,7 +562,7 @@ kernels: @KERNEL_OBJS@

 # PTHREAD_CFLAGS and OPENMP_CFLAGS may actually contain linker options,
 # like -fopenmp
-../run/john@EXE_EXT@: $(JOHN_OBJS) aes/aes.a @ZTEX_SUBDIRS@
+../run/john@EXE_EXT@: $(JOHN_OBJS) aes/aes.a secp256k1/secp256k1.a @ZTEX_SUBDIRS@

[kholia]

@gurnec Thanks! I will try to to implement your suggestions soon.

[kholia]

This is now done.