7

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.

cloudfeet
  • 2,528
  • 17
  • 22
  • I think a key recovery would have to be tailored to the specific de-centralized password scheme that you're trying to break. I'm not sure a general technique could be established. – RoraΖ Oct 01 '14 at 16:36
  • 2
    Mozilla Firefox used to do this with their Firefox Sync service. Your passwords were locally encrypted, and the encryption never left your browser. Your browser would generate a recovery password for you, and you were to print it and store the paper somewhere safe. But they recently moved to an "account" model for Sync, and so it's not an example you can follow today. (And because they changed it to tie the security to your Firefox account and password, I found it impossible to place trust in it. I still have FF28 installed, and won't "upgrade" until I get an external password manager.) – John Deters Oct 01 '14 at 18:18
  • Can you clarify if you mean implementing this as a system within an application or for your personal use? I think that would clear some questions up. – Fernando Dec 08 '14 at 17:21
  • @Fernando - good point, added – cloudfeet Dec 09 '14 at 12:51
  • Got it! This makes the questions slightly more interesting. Although my answer remains mostly unchanged. It's important for them to develop a strong memorable passphrase, splitting it up like this is likely to make it less secure. Unless their adversary is a non-dedicated attacker in which case they might just want to leave it in a safe somewhere. – Fernando Dec 09 '14 at 16:19
  • The technique you describe falls under the concept of "split key" technology. You would not want to divide it up into parts because that would make it such that if an attacker could compromise 3 out of 4 "chunks" of data they could brute-force the remaining chunk. Instead, you'd want to distribute a sequence of chunks that each span the full size of the key (or hash) that you're archiving. That way even if 3 out of 4 recovery chunks are compromised, the entire size-space of a chunk must be compromised. – Nick Dec 22 '14 at 20:20
  • To clarify my point consider the following. Assume that the key size is 16-bytes and you were to chunk recovery data into 4x 4-byte pieces and protect each one using a different (it could be the same but let's assume they are different) security scheme. If 3 out of 4 are compromised then only a 4-byte chunk must be bruteforced (trivial in current times). Alternatively, if you break the key 4x 16-byte chunks then if 3 out of 4 were compromised the remaining chunk is still 16-bytes and that is much more computationally-intense to bruteforce. To recover: XOR all 4 chunks together for the key... – Nick Dec 22 '14 at 20:24

4 Answers4

2

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!

Nick
  • 437
  • 2
  • 9
0

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!

Fernando
  • 705
  • 5
  • 17
  • The thing is, it's the "strong passphrase" that I'm actually trying to recover here. Using a password manager just means I have to recover the passphrase for the password manager instead of my original service. – cloudfeet Dec 05 '14 at 16:58
  • You should be able to memorize a strong passphrase if it is just you needing to use it. In fact using this sort of system might make it more insecure. – Fernando Dec 05 '14 at 17:42
  • So... your answer is "don't use a recovery scheme, and just don't forget your password"? That doesn't really answer the question. :p – cloudfeet Dec 08 '14 at 13:35
  • If you need secret sharing for multiple people that is another question but, basically that is my answer haha. If you are the singular user just remember a good passphrase. Any of your other options compromises your security more than it helps. A strong password would take a good trillion years to crack. But if you give information to multiple parties or store it in insecure mediums like email it might actually make that password less secure. – Fernando Dec 08 '14 at 17:19
  • Just edited to better respond the question. I'm not trying to sound snarky but you asked for best practices and I responded that this might actually not be best practice. I think that it might be contrary to security in itself to use a decentralized key recovery mechanism for important passwords. With a small caveat. – Fernando Dec 09 '14 at 16:30
0

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.

Kotzu
  • 944
  • 7
  • 10
  • In that setup, the client already has the capability to decrypt the information, but it refuses to do so without a suitable (second) token from the server. This means the decryption key is not lost, merely hidden in the client's state. What if the data is *actually inaccessible* without the original key, so the issue is recovery of that key? – cloudfeet Dec 05 '14 at 17:01
  • Oh ok, I get it now, maybe you could tweak that approach a bit, depending on how your information is encrypted, if it is a symmetric key, the server could hold a copy and you could recover the key + the token, or you could have multiple servers holding each a part of the key. – Kotzu Dec 08 '14 at 17:46
  • OK - so more or less key escrow? – cloudfeet Dec 09 '14 at 12:38
  • Yes, although , I don´t particularly like that approach since like Fernando says in the other answer, giving out information to multiple parties might also put you at risk even if only part of the key is compromised. – Kotzu Dec 09 '14 at 17:29
  • With a proper secret-sharing system, the information each party has is useless unless they combine them. A simple example is a bunch of equal-size parts which need to be XOR'd together - if you're missing just one person's info from that scheme, then you're still nowhere. – cloudfeet Dec 10 '14 at 12:29
0

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.

munkeyoto
  • 8,682
  • 16
  • 31
  • Good point! I guess what I actually meant was "recovery from password loss" - I was thinking of a situation where an asymmetric key (RSA) is stored symmetrically-encrypted with a key derived from the password. What I actually *want* is to recover the RSA key, but from the user's perspective the issue is that they "forgot their password". – cloudfeet Dec 10 '14 at 12:26