Decentralised password recovery

Question

Are there good/established techniques for password/key recovery in situations without a centralised service?

(Anything goes, but I'd prefer solutions that distribute the recovery information across multiple places)

For example: I can imagine a system where a recovery key is generated, split using secret sharing and distributed e.g.

• some parts downloaded to local computer
• some parts emailed to yourself
• some parts printed out and placed in a safe-deposit box
• some parts given to friends to safeguard

This is essentially distributed key-escrow: are there some examples of existing systems that use a scheme like this? Are there alternative schemes? Are there best-practices?

Clarification: Personally, I trust myself to remember a relatively strong password - this is designing a system for other people to use, and not all of them might be confident doing that.

Answer 1

I wrote some comments up under your initial question, but I feel that combining my comments (which describe a solution) with all the answers mentioned thus far may produce something you can actually use (versus researching on your own).

As mentioned in the comments, split-key technology is the process of making X-number of sub-keys. The most common style of implementation is to require ALL X sub-keys to recover a protected key.

In the example I discuss next I'll define the following words to ensure clarity:

key: A crypto-variable that is static (aka, shared/symmetric) or is generated based upon a password or passphrase.

password: A clear-text or otherwise non-crypto-derived value that a human typically memorizes (or, shamefully, writes down on a sticky kept under their keyboard).

passphrase: For the purposes of this example a passphrase is identical to a password.

sub-key: A single chunk of recovery information that is equal in size to the key being protected.

split-key: The concept of breaking a recovery key into various splits (aka, sub-key's or chunks).

dictionary characters: The set of characters a user can enter into a recovery mechanism (e.g., A-Za-z0-9).

Now that we have that out of the way we can look at a method to implement this solution.

Assume that my password (as defined above) is IKnowThisIsBad.

I pass the password to the OpenSSL Linux bash command sha512sum and it outputs the hashed value: d3a48c640bbd58633138e2f88b2d3979e3d609df6cd22246dd73d35a77b6755fcf580be431a93c059bc7106ab8d37491d442339879947728d8da436a9c2c60c0

I use that hashed value (note: it is NOT salted at this point, I'm trying to keep it simple...) as my key. This is the key that we are going to protect and I use this key for all my relevant cryptographic purposes.

Let us assume we'll protect the recovery process by using 3 sub-keys (any number of sub-keys greater than 1 is valid, however).

We assume here that a user cannot remember such a sequence and thus cannot (in their head) store a sub-key. Nonetheless, to successfully (and properly) use split-key technology they must provide a chunk of appropriate length. We'll use our friend sha512sum again. In this example let us pretend that the user's passphrase for deriving their recovery chunk is My Secret Recovery Phrase. The output for that iteration produces: 196822a43878ff1c263fe16b6cb2d768b157cf1018ded64e6bab4d36822262ff7f61404ab21c2d279c6cfaa85112786044231917c484dcf3a81931d34fa86edd

Now we need a chunk that will be stored somewhere else. Using your example we'll say it's stored as text to an email. Back we go to our friend sha512sum to generate this sub-key value. We'll use the passphrase: Email Is Not Very Safe To Store Key Info!!, which yields the following value: a8a73e1c6ecd3f2ddff853901f3781fac5839d42cf360833e7148163beb2c05ad5288e6d3c30fd9e7a4bb854b7f507c70991f6c04c507c58028573b5f89ce6a7

At this point we have 2 out of the three recovery chunks or sub-keys generated. Regardless of how many sub-keys you make, the last one is treated special. If we had 10 sub-keys, then we could create the first 9 following the previous examples. If we had 30 then the first 29 could be created that way. But in any case, one value is generated special. To create the last recovery sub-key we must XOR all the know values up to this point together.

Let's look into this more closely.

The main reason we use XOR in cryptography is that it is recoverable (unlike OR and AND operations). When we XOR the previous three values (i.e., the key, the user recovery sub-key generated from the recovery passphrase, and the stored-in-email sub-key) we generate a 3rd sub-key that is automatically the same length as the other 3 inputs. This 3rd chunk can be assigned to your "download to local computer" recovery option. The result of this XOR operation (which can be thought of as: key ^ sub-key1 ^ sub-key2 -OR- key XOR sub-key1 XOR sub-key2) is: 426;94fc5?68`854eaff50ij?gcao?g`d7i2j;add=3af<3`71gehf0dm`26b7fa0511<7g1b`cjgc;g7`a65ibm5>340;l6`9?0d<k?`n40d7a352mm010gk=j8ecfc

I apologize for the weird formatting of that last output. It is necessary because the resultant sub-key value contained backtick (`) characters that had to be specially escaped.

At this point we save that final value somewhere as specified by the "download to local computer" policy.

Great. So that's a bunch of hash values, but how do you get your key back should it be lost from whatever underlying system(s) that use it? We recover all of the sub-key values and XOR them together. This will reproduce the original key value!

To prove this is the case I wrote a little Python blob that implements this XOR operation for arbitrary numbers of XOR strings. Find it below.

#!/usr/bin/env python

#KEY:    d3a48c640bbd58633138e2f88b2d3979e3d609df6cd22246dd73d35a77b6755fcf580be431a93c059bc7106ab8d37491d442339879947728d8da436a9c2c60c0
#RECOV1: 196822a43878ff1c263fe16b6cb2d768b157cf1018ded64e6bab4d36822262ff7f61404ab21c2d279c6cfaa85112786044231917c484dcf3a81931d34fa86edd
#RECOV2: a8a73e1c6ecd3f2ddff853901f3781fac5839d42cf360833e7148163beb2c05ad5288e6d3c30fd9e7a4bb854b7f507c70991f6c04c507c58028573b5f89ce6a7
    
#    RECOV3 is generated by running this script with the above 3 command-line values generated by 'sha512sum'
#RECOV3: 426;94fc5?68`854eaff50ij?gcao?g`d7i2j;add=3af<3`71gehf0dm`26b7fa0511<7g1b`cjgc;g7`a65ibm5>340;l6`9?0d<k?`n40d7a352mm010gk=j8ecfc

#    Recovery of KEY is accomplished by running this script with RECOV1 RECOV2 and RECOV3 as parameters.

import sys, binascii, argparse;

parser      = None;
stringlist  = None;


def xor_strings(base, new):
    return "".join(chr(ord(b)^ord(n)) for b, n in zip(base, new));


def SetParseArgs():
    global parser, stringlist;
    
    parser = argparse.ArgumentParser(description="XOR a bunch of strings!");
    parser.add_argument("string", nargs="+");
    stringlist = parser.parse_args().string;


def main():
    global sys, stringlist;
    
    SetParseArgs();

    res = stringlist[0];
    for index in range(len(stringlist) - 1):
        #skip string #1
        hexstr = stringlist[index + 1];
        res = xor_strings(res, hexstr);
    
    print "XOR result string:\n%s" %(res);


if __name__ == "__main__":
    main();
else:
    print "This script cannot be imported";
    print "Please run as: %s <string_1> <string_2> [string_n]" %(sys.argv[0]);
    print "For best (and most logically-correct) results, ensure strings are the same length";

This script can be used to create the recovery chunks, distribute them however you want, then use the script with ALL of the chunks and you will recover your original key.

This example should make it clear how recovery anything less than ALL of the chunks is just as useless as having none of them because an attacker would still have to brute-force every possible combination across the entire key address space.

I hope some of you find this useful. I enjoyed the exercise in putting it together and might actually use it myself now that the implementation is taken care of! :-)

Please comment on any typo's you observe. I used literal values for all examples above so anyone running the commands/tools described above will produce identical results. I wrote all pre-sha512sum'd strings to individual text files WITHOUT a newline at the end and fed them as parameters to sha512sum to create the key, sub-key1, and sub-key2.

Thanks and enjoy!

Answer 2

I think a password manager is honestly your best bet here if it is just you who is in control of these passwords. You can store passwords within an encrypted password database file. This file can be stored in the cloud, on a USB you give to a friend, and on your local/work computer.

All you need to keep or have is a strong passphrase for the database and keep that to yourself and you can have multiple recovery options. This is just as difficult, if not more difficult, to crack without knowledge of the key.

The splitting of recovery details is unnecessarily complicated if all you want is to store passwords securely and have a backup location for them that is secure.

Secret Sharing is useful when you need to have multiple parties come together in order to access sensitive materials. One very simplified and less secure way of doing this would be to have you and a friend memorize a password each. Then you use yours as the first component of the full password and she uses hers hers as the second. This way, you both have components of the key decentralized but can come together to access something.

Passphrase Generation There are really creative and interesting ways to easily remember super-secure passphrases, rather than investing in some decentralized method that is likely to risk the security of their password, they should spend 2-3 minutes deriving a memorable and secure password they can use consistently with a password manager.

Some methods include: The XKCD method. Using several words in sequence that are unrelated to create your password. I think this method needs slightly more scrambling to it than simple words because if this becomes the common method than you can easily derive a password cracking algorithm using commonly used words that makes it less amazing.

The Passphrase/Password manager method. Where you use memorable phrases to help you remember your derived password. This can be a nice method for longish and strong passwords.

Or, also great, some method you develop that hasn't already been mentioned that creates a strong, long, easy to remember/hard to guess passphrase.

But I'm still going to say that password/key recovery e.g. putting your passwords/keys in plain text somewhere else for anyone to find is a bad idea. It widens your web of trust, and decreases your overall security. Until someone finds a way to break into our minds I'm going to suggest that our heads are the safest place for any key and always will be.

On the off chance you have some super important encrypted file you want to pass along to family when you die or something. Give them the key on a usb and pass the file along to an attorney on a USB. Situations like this are all I can really think of when this might be needed. Even then, there are a few other options.

Hope this helps!

Answer 3

I´m not sure if I´m understanding correctly but I´ve seen systems that generate a random token on the client which is then entered on a remote server which validates token authenticity and in turn generates a second token, this second token is entered again on the client (or wherever the information you want to recover is) which now allows for a password reset if its valid.

Maybe that could help.

Answer 4

Passwords and keys are two distinct items. For example, when we hire new employees, and they need access to Unix based systems, we deploy ssh keys for them so there is no password is involved. If/when they leave, we revoke the keys. The need to manage any password they’d have is a moot point since we could reset the password.

Splitting a password is a waste of bandwidth considering there are more secure methods to deliver new password: via telephone, via SMS, fax.

There are open source password management systems for the enterprise such as Team Pass that do a good job but you must remember, the purpose of allowing someone to create a password is for them and only them to authenticate, not for an admin to have a user disclose their password. Most if not all operating systems allow for strict passwords. It becomes a matter of educating users on how to create strong passwords, otherwise the users do things like post it on post-it pads, etc.

Now, in separating a "key" and a password, Strongkey is an enterprise key management system. Imagine a business where everyone needed to create a GPG/PGP key. Managing those would be a nightmare when people will likely forget their passphrases, a user is fired/leaves, and now no one can decrypt his/her files. The term key and password are not the same even though used interchangeably.