Crowd-sourced password recovery with atomic exchange

[etotheipi]

So I've been mulling pieces of this idea for a while and finally found a way to make it click.  I will use simplified system with example numbers for clarity of explanation, but if of course it's all configurable.

Situation:

• User has encrypted wallet, but can't remember the passphrase.  And no paper backup, of course. (Assumption: they know something about their passphrase, just not all of it)
• Will pay some amount for individuals with significant computing power to help brute-force the passphrase.
• Doesn't want to give the whole wallet to brute-forcers because they can just take all the funds when they find the passphrase
• Brute-forcer should be able to prove they found the passphrase without giving it away
• If they can prove that they found the passphrase, they don't want to simply give it to the user, because the user might not pay out

My solution has the following CONOPs (concept of operations):

• User's wallet is setup to save extra data about the passphrase that does not compromise its security or the benefits of keystretching.
• User distributes an encrypted test string that is half known data, half secret data (perhaps in a forum post)
• User also provides a description of what they know about the passphrase
• Brute-forcers will test passphrases until they find one with the correct prefix (the known data).  At this point they have the secret data.
• Brute-forcer will send the user their address using the secret as an HMAC key, to prove that he found the passphrase
• User verifies HMAC and constructs a finder's fee tranasaction to the brute-forcer that requires both their signature and the encryption key to redeem it.

Yes, the encryption key goes into the blockchain -- it's the only way to claim the coins.
Therefore, zero trust is required to exchange the private key for a finder's fee!

Details:

Assume simple key-stretching that produces an encryption key from a passphrase by simply doing SHA256^1,000(passphrase).  The specifics of the key-stretching don't really matter -- this can be adapted to any key-stretching scheme.   When the user sets/changes their passphrase on their wallet, it will encrypt the private keys using AES256, using key = SHA256^1,000(passphrase).  The wallet will additionally save the following three pieces of information with the wallet:

• plainTestStr = "WalletTestString" + SecureRandom(16))
• encrTestStr = aes256_encrypt(SHA256^1,000(passphrase), plainTestStr)
• revealKeyStr = SHA256^1,002(passphrase) = SHA256²(key)

When the user forgets their passphrase, there will be a way to pop up a recovery window, where they can describe everything they know about their passphrase.  It will then generate a message that says something like the following, which can be posted on a mailing list, forum, etc:

Passphrase recovery help needed:  25 BTC finder's fee

Encrypted Test String:  abc13f98228aa3
Initialization Vector:  1832c1bf
Decrypted result starts with:  "WalletTestString"
Email finder's fee payment address to:  helpme@ididntmakeapaperbackup.com

Passphrase details:
I'm pretty sure the passphrase is 10-14 characters long, it contains two of '!', '@' and '#'.  It has the word "kitten" and a 5-digit number in it.  My best guess of the password is "41876!kittens#"

The brute-forcer will test passphrases until they find one that decrypts the test string to "WalletTestString87cca180a167".  The brute-forcer then constructs an email or forum message reply:

I found it.  Send finder's fee to 1xK39z375mPHn7aa
----
27da5542189ee

Where the hex at the end is

Code:

HMAC(87cca180a167, "I found it.  Send finder's fee to 1xK39z375mPHn7aa")

(the first hex arg is the secret part of the test string)

The user will plug the message into their wallet app which has the encrypted wallet they can't recover.  It has the 87cc verification string stored in the wallet (but was never revealed to the brute-forcers), and then they use that to verify the HMAC.  This proves that the person found the passphrase and proves they want the funds send to 1xK39z375mPHn7aa.  

Last step: the user constructs the following transaction TxOut script, for 25 BTC:

OP_DUP
<PubKeyUser>
OP_CHECKSIG
OP_NOTIF
   <PubKeyBruteForcer>
   OP_CHECKSIGVERIFY
   OP_HASH256
   <SHA256²(encryptionkey)>
   OP_EQUAL
OP_ENDIF

NOTE: It's not the passphrase that the claimant puts in the script, it's the actual encryption key (SHA256^1,000(passphrase)) that they put in the script.  Then the script will double hash it to get SHA256^1,002(passphrase) and compare to the target string.  SHA256^1,000(passphrase) must be stored in the wallet at encryption time, in addition to the test string.  Note that you don't lose the benefits of key-stretching because the SHA256^1,000(passphrase) has the full 256-bits of entropy.  It's still quicker to brute-force the lower-entropy passphrase hashed 1,000 times, than brute-force the 256-bit key without any hashing.

The user can redeem their coins (in the event they're not claimed) by simply putting "OP_0 <SigUser>" into the spending script.  
The brute-forcer can redeem the coins by putting "<HA256^1,000(passphrase)> <SigBruteForcer>" into the spending script

[gmaxwell]

I'd rather have distributed key escrow than making an industry out of bruteforcing and weakening the KDFs just to make bruteforcing remotely viable.

The you same zero trust transfer scheme could be used for key escrow.

This, unfortunately, isn't zero trust if the wallet file had been previously stolen and the thief is watching the blockchain for the cracking results. You could even have the sad outcome where someone gets a copy of your wallet and then later you pay them to brute force it, after they find the key they instantly spend the funds. I would prefer to use some operation in an additive group so that the challenge is not useful to someone who didn't prepare the challenge, even if they had the wallet. ... have to think about how to accomplish that.

As an aside, using the if construct lets the redeemer race. I would instead recommend a precomputed refund transaction instead of an if. Makes the tx data smaller in any case.   You write the payment transaction and then write a transaction on behalf of the payee which gives the funds back to you but has an nlock time a month in the future.  He signs the refund (without ever seeing the payment) then you announce the payment.

[etotheipi]

I'd rather have distributed key escrow than making an industry out of bruteforcing and weakening the KDFs just to make bruteforcing remotely viable.

This doesn't weaken the KDF at all.  Unless your passphrase is 256+ bits, in which case it's secure, regardless.   ("Note that you don't lose the benefits of key-stretching because the SHA256^1,000(passphrase) has the full 256-bits of entropy.  It's still quicker to brute-force the lower-entropy passphrase hashing 1,000 times on each guess, than brute-force the 256-bit key without any stretching.").

This, unfortunately, isn't zero trust if the wallet file had been previously stolen and the thief is watching the blockchain for the cracking results. You could even have the sad outcome where someone gets a copy of your wallet and then later you pay them to brute force it, after they find the key they instantly spend the funds. I would prefer to use some operation in an additive group so that the challenge is not useful to someone who didn't prepare the challenge, even if they had the wallet. ... have to think about how to accomplish that.

As an aside, using the if construct lets the redeemer race. I would instead recommend a precomputed refund transaction instead of an if. Makes the tx data smaller in any case.   You write the payment transaction and then write a transaction on behalf of the payee which gives the funds back to you but has an nlock time a month in the future.  He signs the refund (without ever seeing the payment) then you announce the payment.

That is true about the race, but it seems that you've solved it with the precomputed refund.  Once he's got the payment tx, he can personally give you the password knowing that he can redeem it.  That way you can unlock and sweep before he broadcasts the finder's fee tx.  Worst case, he broadcasts with the key and you get it from the blockchain, but that would be a last resort.  Does that work? 

[gmaxwell]

This doesn't weaken the KDF at all.  Unless your passphrase is 256+ bits, in which case it's secure, regardless.   ("Note that you don't lose the benefits of key-stretching because the SHA256^1,000(passphrase) has the full 256-bits of entropy.  It's still quicker to brute-force the lower-entropy passphrase hashing 1,000 times on each guess, than brute-force the 256-bit key without any stretching.").

I must be completely confused here.  Lets say we have a random user, who does what a random user does, and they make their password "qwerty5". Someone hacks their system and gets their wallet file.   With /sufficient/ KDF the attacker could not determine that the password is "qwerty5": because qwerty5 is entry 523,1234 on some statistically optimal ordered list of passwords for the victim, and KDF is such that this will take 20 years to crack.

But if this a cracking backdoor scheme is to work then the KDF must be weak enough that someone could find such a password. And thus by definition the KDF cannot do what it is intended to do (make it completely infeasible for an attacker, even one with more resource than the user) to perform a search.

That is true about the race, but it seems that you've solved it with the precomputed refund.  Once he's got the payment tx, he can personally give you the password knowing that he can redeem it.  That way you can unlock and sweep before he broadcasts the finder's fee tx.  Worst case, he broadcasts with the key and you get it from the blockchain, but that would be a last resort.  Does that work? 

Interesting point. This doesn't address the case where the cracker is cooperating (e.g. posting first for counter offers for your mac solution on a cracking forum ) with someone who has stolen the file, which I admit is getting a little further out there though but you are talking about people with businesses cracking passwords.

[etotheipi]

This doesn't weaken the KDF at all.  Unless your passphrase is 256+ bits, in which case it's secure, regardless.   ("Note that you don't lose the benefits of key-stretching because the SHA256^1,000(passphrase) has the full 256-bits of entropy.  It's still quicker to brute-force the lower-entropy passphrase hashing 1,000 times on each guess, than brute-force the 256-bit key without any stretching.").

I must be completely confused here.  Lets say we have a random user, who does what a random user does, and they make their password "qwerty5". Someone hacks their system and gets their wallet file.   With /sufficient/ KDF the attacker could not determine that the password is "qwerty5": because qwerty5 is entry 523,1234 on some statistically optimal ordered list of passwords for the victim, and KDF is such that this will take 20 years to crack.

But if this a cracking backdoor scheme is to work then the KDF must be weak enough that someone could find such a password. And thus by definition the KDF cannot do what it is intended to do (make it completely infeasible for an attacker, even one with more resource than the user) to perform a search.

You missed the part where I'm not talking about cracking a password from scratch.  Part of this process is that the user describes everything they know about their password, to reduce the search space from 5,231,234 possible passwords, to 2,381.  It may still be too much for one person to find it, but small enough that it could be done in a couple weeks by 10 people who all want the finder's fee.

If you look at the proposal again, you'll see that the original key-stretching is still intact.  All the brute-forcers still have to guess through the KDF (or try brute forcing the 256-bit encryption key directly, if they're dumb).  It's just that they're using info from the original user to reduce the search space to something feasible.

About 1-3 times per month I get emails from users in exactly this situation.  They give me as much information as they know about what the password might be, and I either tell them (1) you don't know enough to make this feasible, or (2) Here's a script that tests the most likely 2,381 passwords against your wallet, it will take about three weeks to run.

P.S. - For reference, the default settings for an encrypted wallet in Armory, requires 0.125-0.25 seconds of compute time, with somewhere between 1 and 32 MB of RAM usage.  Therefore, when I user gives me their wallet, I can usually process about 5 passwords per second per core.  With my quad-core system, that's 20 passwords per second.  So I can do somewhere between 1M and 2M passwords per day if they give me their wallet and it was created with default settings.  Of course, I've gotten users in the past who set compute time to 5 sec for "extra security", which turned out to be extra security from themselves...

[etotheipi]

I was just talking to goatpig about this, and figured out a secure way to do the payment without the race.  I guess this is a more-general pattern for doing any type of information exchange where you want the payer to be able to recover the funds if the data is not revealed.

What I originally proposed was a this single transaction type, but it does create a race:

Code:

OP_DUP 
<PubKeyUser> 
OP_CHECKSIG 
OP_NOTIF 
   <PubKeyBruteForcer> 
   OP_CHECKSIGVERIFY 
   OP_HASH256 
   <SHA2562(encryptionkey)> 
   OP_EQUAL 
OP_ENDIF

Instead, create a tx sending the finder's fee to a 2-of-2 between user and brute-forcer.  But before that is broadcast, create two spending tx, and get both parties to the sign the tx before the user broadcasts the escrow tx.

Escrow:

Input:
   User:  10 BTC
Output:
   2-of-2:  (user, bruteforcer) (10 BTC)


Tx1 (refund):

Input:
   2-of-2:  10 BTC
Output:
   User (10 BTC)
LOCKTIME:
   30 days


Tx2 (finder's fee):

Input:
   2-of-2:  10 BTC
Output:

Code:

   <PubKeyBruteForcer> 
   OP_CHECKSIGVERIFY 
   OP_HASH256 
   <SHA2562(encryptionkey)> 
   OP_EQUAL 

(no locktime)

That gives the brute-forcer 30 days to reveal the key and claim the funds.  But if he disappears, the user can broadcast the locked tx after 30 days to get the money back.

Note: this depends on malleability being fixed, in order to be truly trustless.