Methods of password backup and recovery using challenge questions

From Protecting Secret Keys with Personal Entropy:

I successfully tried this method using the following programs:
Secret Sharing - implementation of "(n, t)-threshold scheme" mentioned in the paper; http://en.wikipedia.org/wiki/Secret_sharing lists other similar programs/services
7-Zip - for file encryption/decryption
http://anandam.name/pbkdf2/ - generates "slow hash" of text; I highly recommend that you save this page locally so that you can use this again if the website vanishes someday; be sure to write down the values you used for "Salt," "Number of iterations," and "Number of bytes for Key"

If anyone needs more help, say so.

Note about this paper (from paper mentioned next):

---------

From Error-Tolerant Password Recovery:

This paper looks good too. I haven't tried it yet.

---------

From Secure Secret Recovery by using Weighted Personal Entropy:

---------

From "A Fuzzy Vault Scheme" (direct pdf link hxxp://people.csail.mit.edu/madhu/papers/2002/ari-journ.pdf):

 

I changed the hash function program in the last post to http://anandam.name/pbkdf2/. This uses a "slow hash" function to slow down bruteforcing.

 

Method that uses a character grid: https://www.wilderssecurity.com/showpost.php?p=2322841&postcount=39 and https://www.wilderssecurity.com/showpost.php?p=2322050&postcount=21. You can use this method with passwords that contain non-random characters, as well as with passwords that contain random characters.

Another method that uses a character grid: https://www.wilderssecurity.com/showpost.php?p=2322986&postcount=52. You probably shouldn't use this method with passwords that contain non-random characters if the password is too long, because an attacker may be able to spot character patterns in the grid too easily.

 

Method for generating memorable strong passwords: Diceware strong master password generation method. See post #16 in that thread for a method for generating strong memorable passwords consisting of random lowercase letters.

 

Unless I have a misunderstanding or didn't read the paper closely enough, the first method in post #1 could be extremely weak with respect to bruteforcing if the decryption algorithm tells you whether a given decryption key is correct or incorrect, because then every part can be bruteforced separately.

Update: the paper does mention this:

7-Zip is not suitable for this method, since it tells you whether a given decryption key is correct or incorrect.

 

If you don't need the capability to forget the answers to some challenge questions, a simple method is to encrypt the password with a key comprised of answers to challenge questions. Use enough challenge questions so that the encryption key is likely to take a very long time to crack.

 

In this post I'll show how to implement the method mentioned in the paper "Error-Tolerant Password Recovery" (see post #1). The advantage of this method over the method in post #6 is that you can forget a certain number of answers and yet still recover your password.

We'll need a hash function, very preferably a "slow" hash function that slows down bruteforcing considerably. I'll use http://anandam.name/pbkdf2/ in this post. I highly recommend saving the web page for http://anandam.name/pbkdf2/ to a file in your browser, so that you can still use it in case the page is unavailable in the future.

Let NumberOfBytesPerHash = number of bytes in the output of the hash function used. I'll use NumberOfBytesPerHash=16 in this post.

If the hash function you use requires salt, then go to http://www.random.org/bytes/ and generate 16 random bytes with output displayed as hexadecimal. Let Salt=these 16 bytes (without spaces). In my case Salt=5972163fee3a6dd5724ce1ff28533f41, but your Salt is highly likely to be different.

If the hash function you use lets you specify the number of iterations to use (to slow down bruteforcing), then let NumberOfHashIterations=this value. I'll use NumberOfHashIterations=1000 in this post.

Let MaximumNumberOfWrongAnswers=desired number of answers to questions that you (or an attacker) can get wrong while still being able to recover your password. I'll use MaximumNumberOfWrongAnswers=2 in this post. The slides for the paper suggest using MaximumNumberOfWrongAnswers=4.

Let MinimumNumberOfRightAnswers=desired minimum number of answers to questions that you (or an attacker) must get exactly right in order to recover your password. I'll use MinimumNumberOfRightAnswers=5 in this post. The slides for the paper suggest using MinimumNumberOfRightAnswers=11.

Let TotalNumberOfQuestions = MaximumNumberOfWrongAnswers + MinimumNumberOfRightAnswers. In this example TotalNumberOfQuestions = 2+5 = 7. The slides for the paper suggest using TotalNumberOfQuestions = 4+11 = 15.

Go to http://www.random.org/bytes/ and get TotalNumberOfQuestions*NumberOfBytesPerHash random bytes, displayed in hexadecimal. Let PasswordEncryptionKey=this value without spaces. In my case PasswordEncryptionKey=df8b943b52609a6133685d39df6ff6af3cd70310a0dc5bad678be239a264e90c5f3396e4d96c3 (continued on next line)
b6ebd64b812208127c78db0254e36d327ac7bd8d7f319446877fefd8202eb78e2ff26ca2632a0abc9da051e08f11a9 (continued on next line)
327054475e46848d23b2259337b29c4e9a17293ecd0f61ceff10d. Yours is highly likely be different. In a new text file named PasswordEncryptionKey.txt, save the value of PasswordEncryptionKey.

Place the password you wish to backup in a file and encrypt the file using a symmetric-key encryption program such as AxCrypt, using PasswordEncryptionKey as the key. You need to use an encryption program that can handle long encryption keys. AxCrypt can. 7-Zip can't.

You'll need TotalNumberOfQuestions challenge questions. For examples of challenge questions, see http://goodsecurityquestions.com/examples.htm. I'll use these 7 challenge questions in this post:

1. What is my mother's maiden name (all lowercase)?
2. What is the last name of the teacher of my 10th grade World History class (all lowercase)?
3. What is the last name of the star of my favorite childhood comedy (all lowercase)?
4. What is my first wife's nickname for me (all lowercase)?
5. What is my childhood nickname (all lowercase)?
6. What is my oldest sibling's middle name (all lowercase)?
7. What is the city I was born in (without state or country) (all lowercase)?

Suppose the answers to these questions are:
1. zimmerman
2. anderson
3. white
4. tuddles
5. bozo
6. wilson
7. tuscon

Use the hash function to hash each of the answers to your TotalNumberOfQuestions challenge questions separately. If your hash function uses salt, then use Salt from above. If your hash function lets you specify the number of iterations to use, use NumberOfHashIterations from above. If your hash function lets you specify the number of bytes per hash function output, use NumberOfBytesPerHash from above.

Using hash function http://anandam.name/pbkdf2/ I get these 7 hashes:
1. 594ee27d17d4f35d2eed5b8f0aa28c17
2. 66a3bfc2cef8d202ab2de52bb1ae8c1e
3. 7b45ae673001e7d7e1a9000e035c5c9c
4. 452eb931763bcb1041184bced836f688
5. f8e333638d2330fef0820ecf44e1e5bd
6. 54df8c201fdd099d6770a62d27910777
7. 3694895f2f45570f835bc9b1007d1091

Let UnencryptedPasswordEnsemble = the concatenation of the hashes of the answers to your TotalNumberOfQuestions challenge questions, from first question to last question, without spaces. In this example, UnencryptedPasswordEnsemble=
594ee27d17d4f35d2eed5b8f0aa28c1766a3bfc2cef8d202ab2de52bb1ae8c1e7b45ae673001 (continued on next line)
e7d7e1a9000e035c5c9c452eb931763bcb1041184bced836f688f8e333638d2330fef08 (continued on next line)
20ecf44e1e5bd54df8c201fdd099d6770a62d279107773694895f2f45570f835bc9b1007d1091.

Check that PasswordEncryptionKey has the same length as UnencryptedPasswordEnsemble. If they're different, something is wrong.

Let EncryptedPasswordEnsemble be the bitwise exclusive OR (XOR) of PasswordEncryptionKey and UnencryptedPasswordEnsemble. You can use http://calculator-fx.com/calculator/bit/bitwise-xor-operation-on-two-numbers to perform this calculation, and http://danvk.org/hex2dec.html to convert the decimal result to hexadecimal (omit the '0x' at the beginning). You'll have to do this calculation in multiple chunks if your Xor calculator can't handle large hexadecimal numbers. For a Xor calculation where the output is shorter than either of the inputs, manually prepend 0's to the output until the output is the same length as the either of the inputs. For my example EncryptedPasswordEnsemble=86c5764645b4693c1d8506b6d5cd7ab85a74bcd26e2489afcca607 (continued on next line)
1213ca651224763883e96ddcb95ccdb81c23dd7b5bc89e9c7f40e8ecbc3ac09c3dc17 (continued on next line)
29eff061eb161665bd201d64828fde44a2c6751c184d1054e2e98230542456f433.c556fa7f276ebacf67d10b719471c92e19c.

Make sure that UnencryptedPasswordEnsemble and EncryptedPasswordEnsemble have the same length. If not, something is wrong.

We'll need a program that can do Reed–Solomon encoding. I'll use QuickPar. In QuickPar Options, set Preferred Block Size to Exact(ly) 2*NumberOfBytesPerHash Bytes, which equals 32 in this example.

In QuickPar, click "Add Files." Add file PasswordEncryptionKey.txt. Set Block Size to 2*NumberOfBytesPerHash. In my example, this is 2*16=32. Set Number of Recovery Blocks to MaximumNumberOfWrongAnswers. In my case this is 2. Check that Source Block Count = TotalNumberOfQuestions; if not, something is wrong. Click Create button to create the .Par2 error correction files.

Delete any other files used, preferably using a secure file wiping program.

Here is what you keep when finished:
1. Challenge questions, in the correct order
2. Hash program/service used
3. Any of the following that your hash function used as parameters: NumberOfBytesPerHash, Salt, NumberOfHashIterations.
4. The encrypted password file
5. EncryptedPasswordEnsemble
6. .Par2 files for PasswordEncryptionKey.txt. but not PasswordEncryptionKey.txt itself.
7. QuickPar installer (or whatever similar program/service you used)
8. Program/service used for bitwise OR (XOR) calculations
9. These instructions

---------

If you need to recover your password, do so as follows:
Answer your challenge questions to the best of your ability.

Suppose I answer the questions as follows:
1. zimmerman
2. johnson
3. white
4. tuddles
5. ?
6. wilson
7. tuscon

Two of these answers are wrong, including the forgotten one.

Use the hash function to hash each of the answers to your TotalNumberOfQuestions challenge questions separately. If your hash function uses salt, then use recorded Salt. If your hash function lets you specify the number of iterations to use, use recorded NumberOfHashIterations. If your hash function lets you specify the number of bytes per hash function output, use recorded NumberOfBytesPerHash.

Using hash function http://anandam.name/pbkdf2/ I get these 7 hashes:
1. 594ee27d17d4f35d2eed5b8f0aa28c17
2. 477690360494050d837cd0359b8e4076
3. 7b45ae673001e7d7e1a9000e035c5c9c
4. 452eb931763bcb1041184bced836f688
5. 01b0aabb2bd4ad0addd4ea2e331314d6
6. 54df8c201fdd099d6770a62d27910777
7. 3694895f2f45570f835bc9b1007d1091

Let UnencryptedPotentiallyWrongPasswordEnsemble = the concatenation of the hashes of the answers to your TotalNumberOfQuestions challenge questions, from first question to last question, without spaces. In this example, UnencryptedPotentiallyWrongPasswordEnsemble=594ee27d17d4f35d2eed5b8f0aa28c17477690360494050d837 (continued on next line) cd0359b8e40767b45ae673001e7d7e1a9000e035c5c9c452eb931763bcb1041184bced836f68801b0aabb2bd4ad0 (continued on next line)
addd4ea2e331314d654df8c201fdd099d6770a62d279107773694895f2f45570f835bc9b1007d1091.

Let PotentiallyWrongPasswordEncryptionKey be the bitwise exclusive OR (XOR) of EncryptedPasswordEnsemble and UnencryptedPotentiallyWrongPasswordEnsemble. You can use http://calculator-fx.com/calculator/bit/bitwise-xor-operation-on-two-numbers to perform this calculation, and http://danvk.org/hex2dec.html to convert the decimal result to hexadecimal (omit the '0x' at the beginning). You'll have to do this calculation in multiple chunks if your Xor calculator can't handle large hexadecimal numbers. For a Xor calculation where the output is shorter than either of the inputs, manually prepend 0's to the output until the output is the same length as the either of the inputs. For my example PotentiallyWrongPasswordEncryptionKey= df8b943b52609a6133685d39df6ff6af1d022ce46ab08ca24fdad7 (continued on next line)
27884425645f3396e4d96c3b6ebd64b812208127c78db0254e36d327ac7bd8d7f31 (continued on next line)
944687707ae1bda4d8f7f0b0b9cc2d3d75938b1051e08f11a9327054475e46848d23b2259337b29c4e9a17293ecd0f61ceff10d.

Create a new file called PasswordEncryptionKey.txt and place the value of PotentiallyWrongPasswordEncryptionKey into it. Put this file in the same folder as the .Par2 files. In QuickPar, click the Open button and open one of the .Par2 files. If PasswordEncryptionKey.txt doesn't contain the correct password encryption key, then QuickPar should be able to repair it if and only if you got at least MinimumNumberOfRightAnswers questions exactly right. If the password in PasswordEncryptionKey.txt is correct, you can use it to decrypt the encrypted file containing your password .

 

From "Challenging Challenge Questions" (direct link hxxp://homepages.inf.ed.ac.uk/mjust/Trust2009.pdf):

From "Personal Knowledge Questions for Fallback Authentication: Security Questions in the Era of Facebook" (direct link hxxp://cups.cs.cmu.edu/soups/2008/proceedings/p13Rabkin.pdf):

From "What’s in a Name? Evaluating Statistical Attacks on Personal Knowledge Questions" (direct link hxxp://www.jbonneau.com/doc/BJM10-FC-name_guessing_statistics.pdf):