Diceware strong master password generation method

Discussion in 'privacy technology' started by MrBrian, Dec 22, 2013.

Thread Status:
Not open for further replies.
  1. MrBrian

    MrBrian Registered Member

    Joined:
    Feb 24, 2008
    Posts:
    6,032
    Location:
    USA
    From The Diceware Passphrase Home Page:
    (Hat tip: Toward Better Master Passwords)

    Optionally, you can save a password hint as follows:
    1. Save the Diceware word set that you used. Save it to a file whose name doesn't make its use obvious.
    2. Save the die rolls in a password hint file. Save it to a file whose name doesn't make its use obvious, and isn't named similarly to the file from step #1. You could instead use a steganography program to hide the die rolls inside another file.

    Example password hint file:
    5453335521352454452313415

    Constructed master password using the Diceware list hxxp://world.std.com/~reinhold/diceware.wordlist.asc : snick rite kelly ouvre bat
     
    Last edited: Dec 23, 2013
  2. MrBrian

    MrBrian Registered Member

    Joined:
    Feb 24, 2008
    Posts:
    6,032
    Location:
    USA
    Alternately, you could use steganography to hide the generated master password itself inside of another file.
     
  3. MrBrian

    MrBrian Registered Member

    Joined:
    Feb 24, 2008
    Posts:
    6,032
    Location:
    USA
  4. MrBrian

    MrBrian Registered Member

    Joined:
    Feb 24, 2008
    Posts:
    6,032
    Location:
    USA
    Some notes from the Diceware site:
     
    Last edited: Dec 23, 2013
  5. MrBrian

    MrBrian Registered Member

    Joined:
    Feb 24, 2008
    Posts:
    6,032
    Location:
    USA
    From Password Security and ocl-Hashcat-plus:
     
  6. MrBrian

    MrBrian Registered Member

    Joined:
    Feb 24, 2008
    Posts:
    6,032
    Location:
    USA
  7. MrBrian

    MrBrian Registered Member

    Joined:
    Feb 24, 2008
    Posts:
    6,032
    Location:
    USA
  8. MrBrian

    MrBrian Registered Member

    Joined:
    Feb 24, 2008
    Posts:
    6,032
    Location:
    USA
    From Password with real words (like Diceware) really safe?:
     
    Last edited: Dec 23, 2013
  9. MrBrian

    MrBrian Registered Member

    Joined:
    Feb 24, 2008
    Posts:
    6,032
    Location:
    USA
    If your Diceware password contains patterns, or recognizable phrases spanning three or more consequtive words, it should be tossed aside.

    Also make sure that your Diceware password meets the following length requirements:
    for 4 Diceware words, at least 11 characters
    for 5 Diceware words, at least 14 characters
    for 6 Diceware words, at least 17 characters
    for 7 Diceware words, at least 20 characters

    Examples of bad Diceware passwords:
    angel angel angel angel angel (bad because of repetition)
    africa we are the world (bad because there is a recognizable phrase that could be in a password cracking dictionary)
    on if to me a so (bad because too few total characters)
     
    Last edited: Dec 27, 2013
  10. MrBrian

    MrBrian Registered Member

    Joined:
    Feb 24, 2008
    Posts:
    6,032
    Location:
    USA
  11. MrBrian

    MrBrian Registered Member

    Joined:
    Feb 24, 2008
    Posts:
    6,032
    Location:
    USA
  12. MrBrian

    MrBrian Registered Member

    Joined:
    Feb 24, 2008
    Posts:
    6,032
    Location:
    USA
    If you prefer (or must use) shorter passwords with random characters, see the Diceware FAQ. See post #16 also.
     
    Last edited: Dec 27, 2013
  13. wat0114

    wat0114 Registered Member

    Joined:
    Aug 5, 2012
    Posts:
    1,984
    Location:
    Canada
    This is excellent. At first I thought it was overkill but realized with the technology in place these days available to crack passwords with ease and speed, I've used this to re-create my master pass phrase.

    Thanks and Merry Christmas MrBrian :)
     
  14. MrBrian

    MrBrian Registered Member

    Joined:
    Feb 24, 2008
    Posts:
    6,032
    Location:
    USA
    You're welcome and thanks for the kind words. Merry Christmas to you and to everyone else that celebrates it :).

    I'm going to redo my master passwords also using Diceware. I have a die ready to roll. I'll probably use five Diceware words plus one non-dictionary word. I might store part (but not all) of the master password in my clipboard manager for quicker entry.

    (p.s. wat0114 might be referring to technology like that mentioned in Fast Password Cracking with a Huge Dictionary File and oclHashcat-Plus)
     
    Last edited: Dec 25, 2013
  15. wat0114

    wat0114 Registered Member

    Joined:
    Aug 5, 2012
    Posts:
    1,984
    Location:
    Canada
    You bet! Also I was amazed watching a WW2 documentary on the History channel last night where there was mention on how the Polish and British were able to decipher the German's Enigma machine, even after they placed a fourth rotor in it. Quite fascinating how it was done, especially with the Bombe machine :) There were some flaws, however, in the Enigma machine's setup that allowed the British to more easily decipher it, but it's still incredible all the same, considering the technology back then compared to what's available now :eek:
     
  16. MrBrian

    MrBrian Registered Member

    Joined:
    Feb 24, 2008
    Posts:
    6,032
    Location:
    USA
    The Diceware author has published a new method for situations in which you want or need shorter memorable secure passwords. From Making Random Letter Passwords Memorable:
    How to generate random letters using dice or coins (from The Diceware Passphrase FAQ):
    If you're using dice and generate a number instead of a letter, be sure to roll both dice again (or roll one die two times).

    This method should be stronger than the Bruce Schneier password scheme, since this method generates random letters.
     
    Last edited: Dec 27, 2013
  17. MrBrian

    MrBrian Registered Member

    Joined:
    Feb 24, 2008
    Posts:
    6,032
    Location:
    USA
    For the method in post #1, each Diceware word adds 12.9 bits of entropy (assuming that a non-letter separator is used in between each Diceware word).

    For the method in post #16, each random character adds 4.7 bits of entropy.

    Average time to crack password in seconds = 0.5 * (2 ^ BitsOfEntropyInPassword) / NumberOfGuessesPerSecond.

    NumberOfGuessesPerSecond depends upon hardware/software as well as details of the hash function used. Some systems use PBKDF2 or similar with varying numbers of iterations as a "speed bump" to slow down crackers. See http://en.wikipedia.org/wiki/PBKDF2 for a partial list of systems that use PBKDF2. NumberOfGuessesPerSecond for various graphics cards can be found at http://golubev.com/gpuest.htm. See the "Single MD5 speed" column for MD5 hashes; see the "WinZip/AES speed" column for PBKDF2 hashes with perhaps 1000 iterations. The highest value of NumberOfGuessesPerSecond at that link is about 10,000,000,000 for MD5 hashes and about 1,000,000 for PBKDF2 hashes with perhaps 1000 iterations.

    Examples of average time to crack using 1 Radeon HD 6990 graphics card:
    4 Diceware words hashed with MD5 = 170654 seconds
    4 Diceware words hashed with PBKDF2 (1000 iterations) = 1706545141 seconds

    5 Diceware words hashed with MD5 = 1304381782 seconds
    5 Diceware words hashed with PBKDF2 (1000 iterations) = 1.3043818e+13 seconds (i.e. a number with 14 digits)

    6 Diceware words hashed with MD5 = 9.9699199e+12 seconds (i.e. a number with 13 digits)
    6 Diceware words hashed with PBKDF2 (1000 iterations) = 9.9699199e+16 (i.e. a number with 17 digits)

    7 Diceware words hashed with MD5 = 7.6204148e+16 seconds (i.e. a number with 17 digits)
    7 Diceware words hashed with PBKDF2 (1000 iterations) = 7.6204148e+20 seconds (i.e. a number with 21 digits)

    See http://blog.agilebits.com/2012/07/31/1password-is-ready-for-john-the-ripper/ for a table with similar calculations.

    Number of random lowercase letters (see post #16 for memorization method) that have at least as much entropy as various number of Diceware words:
    4 Diceware words: 11 random lowercase letters
    5 Diceware words: 14 random lowercase letters
    6 Diceware words: 17 random lowercase letters
    7 Diceware words: 20 random lowercase letters

    My recommendations:
    If your system uses a "speed bump" such as PBKDF2, use 5 Diceware words (or 14 random lowercase letters) to protect against a smaller organization for the next few decades, or 6 Diceware words (or 17 random lowercase letters) to protect against a larger organization for the next few decades.

    If your system doesn't use a "speed bump" such as PBKDF2 (or if you're just not sure if it does), use 6 Diceware words (or 17 random lowercase letters) to protect against a smaller organization for the next few decades, or 7 Diceware words (or 20 random lowercase letters) to protect against a larger organization for the next few decades.
     
    Last edited: Dec 27, 2013
  18. MrBrian

    MrBrian Registered Member

    Joined:
    Feb 24, 2008
    Posts:
    6,032
    Location:
    USA
    The calculations in the last post assume the following:
    • if you're using Diceware words, that the cracker knows that you're using the Diceware scheme, knows the Diceware word list that you're using, and knows the number of Diceware words that you're using; if the cracker doesn't know that you're using the Diceware scheme, the average cracking time could be significantly longer than my calculations
    • if you're using Diceware words, that you're using a non-letter separator between Diceware words; you can use other non-letter characters other than the space character; if you're not using any separator between Diceware words, then the average time to crack could be lower than my calculations
    • if you're using Diceware words, that you've tossed aside any Diceware passwords that don't meet the requirements from post #9; failure to do so could result in significantly lower average cracking time than my calculations
    • if you're using the random lowercase letters method from post #16, that you've tossed aside any passwords that contain any noticeable patterns or words; failure to do so could result in significantly lower average cracking time than my calculations

    Note: I updated post #9.
     
    Last edited: Dec 27, 2013
  19. MrBrian

    MrBrian Registered Member

    Joined:
    Feb 24, 2008
    Posts:
    6,032
    Location:
    USA
    From 25-GPU cluster cracks every standard Windows password in <6 hours:
     
  20. MrBrian

    MrBrian Registered Member

    Joined:
    Feb 24, 2008
    Posts:
    6,032
    Location:
    USA
  21. MrBrian

    MrBrian Registered Member

    Joined:
    Feb 24, 2008
    Posts:
    6,032
    Location:
    USA
    (Update: see post #39 for changes since this post)

    Here's the method I think I'll use to both remember and write down my master password(s), which will be composed of random (or maybe pseudo-random) lowercase letters.

    1. Go to http://my-passwordcard.com/form_type1.php. Generate a password card with 208 pseudo-random letters by doing the following:
    a) Set "Masterpassword" field to abcdefghijklmnopqrstuvwxyz.
    b) Click tab "#1". Check "Random" checkbox.
    c) Do the same as step 1.b but instead for tabs "#2" to "#8."
    d) Click "Generate PDF" button to save the password card. Don't close this window because it will be used again if you do step #4. Mine looks like this, but yours should be different:
    Pseudo random.png

    2. You'll need eight questions for which you'll always remember the answers to, but for which as few other people as possible know the answers to. Some examples are found at http://goodsecurityquestions.com/examples.htm. The questions need to have only letters as the answers.

    3. This is how your master password is revealed/generated from the password card, so write the following down and keep it with the password card: (As an example, I'll use a 14 lowercase letter master password. You'll need to change the "length=" lines below so that the lengths add up to the number of characters in your master password, distributing the "length=" lines as evenly as possible amongst the 8 grid positions.)

    Concatenate the following in order without any additional characters (convert to lowercase letters):
    Start central letter=1st letter of answer to question 1; grid position=1; length=2; movement letter=3rd letter of answer to question 1
    Start central letter=1st letter of answer to question 2; grid position=2; length=2; movement letter=3rd letter of answer to question 2
    Start central letter=1st letter of answer to question 3; grid position=3; length=2; movement letter=3rd letter of answer to question 3
    Start central letter=1st letter of answer to question 4; grid position=4; length=2; movement letter=3rd letter of answer to question 4
    Start central letter=1st letter of answer to question 5; grid position=5; length=2; movement letter=3rd letter of answer to question 5
    Start central letter=1st letter of answer to question 6; grid position=6; length=1; movement letter=3rd letter of answer to question 6
    Start central letter=1st letter of answer to question 7; grid position=7; length=2; movement letter=3rd letter of answer to question 7
    Start central letter=1st letter of answer to question 8; grid position=8; length=1; movement letter=3rd letter of answer to question 8

    Question 1: (fill yours in)
    Question 2: (fill yours in)
    Question 3: (fill yours in)
    Question 4: (fill yours in)
    Question 5: (fill yours in)
    Question 6: (fill yours in)
    Question 7: (fill yours in)
    Question 8: (fill yours in)

    Grid position:
    1 2 3
    4 C 5
    6 7 8

    Movement letter:
    If movement letter is a,b,c then move up; if already at topmost row, then go to bottommost row of adjacent column to the left; if at central letter A, then go to central letter U
    If movement letter is d,e then move down; if already at bottommost row, then go to topmost row of adjacent column to the left; if at central letter V, then go to central letter G
    If movement letter is f,g,h then move left; if already at leftmost column, then go to rightmost column of adjacent row to the top; if at central letter A, then go to central letter Z
    If movement letter is i,j,k,l then move left; if already at leftmost column, then go to rightmost column of adjacent row to the bottom; if at central letter V, then go to central letter G
    If movement letter is m,n then move right; if already at rightmost column, then go to leftmost column of adjacent row to the bottom; if at central letter Z, then go to central letter A
    If movement letter is o,p,q then move down; if already at bottommost row, then go to topmost row of adjacent column to the right; if at central letter U, then go to central letter A
    If movement letter is r,s then move right; if already at rightmost column, then go to leftmost column of adjacent row to the top; if at central letter G, then go to central letter V
    If movement letter is t,u,v,w,x,y,z then move up; if already at topmost row, then go to bottommost row of adjacent column to the right; if at central letter G, then go to central letter V

    Since the letters j, q, x and z occur infrequently (source: http://en.wikipedia.org/wiki/Letter_frequency), try to make sure that you choose one question that results in a start central letter of j, q, x, or z if there isn't one already. (I failed to follow this advice in the example below.)

    As an example, let's suppose these are the answers to my 8 questions:
    boomer
    dallas
    wallace
    geraldo
    nicki
    kerschner
    shark
    italy

    The generator then is:
    Start central letter=b; grid position=1; length=2; movement letter=o
    Start central letter=d; grid position=2; length=2; movement letter=l
    Start central letter=w; grid position=3; length=2; movement letter=l
    Start central letter=g; grid position=4; length=2; movement letter=r
    Start central letter=n; grid position=5; length=2; movement letter=c
    Start central letter=k; grid position=6; length=1; movement letter=(doesn't matter because length=1)
    Start central letter=s; grid position=7; length=2; movement letter=a
    Start central letter=i; grid position=8; length=1; movement letter=(doesn't matter because length=1)

    The generated/revealed master password for the card above is srliddwhymsgjl.

    4. (Optional but recommended) In this optional step we'll replace the pseudo-random letters used in the master password with truly random letters.
    a) See post #16 for how to generate random lowercase letters with dice or coins. Let's suppose that our truly random 14 lowercase letter password is whsswiomjfreab.
    b) You'll need to replace the letters in your password card so that the correct password is generated. Generate a new password card. Mine looks like this, but yours should be different:
    Random.png

    The generated/revealed master password for the card above is whsswiomjfreab.

    5. As a mnemonic aid to help in remembering your password without needing to use your password card, see post #16.
     
    Last edited: Dec 30, 2013
  22. wat0114

    wat0114 Registered Member

    Joined:
    Aug 5, 2012
    Posts:
    1,984
    Location:
    Canada
    I just used diceware to roll out fifteen dice words, then chose five that I liked and made a pass phrase that I'm comfortable with and for me easily remembered, checked the entropy here and it scored a 90+ so I should be good to go :)
     
  23. MrBrian

    MrBrian Registered Member

    Joined:
    Feb 24, 2008
    Posts:
    6,032
    Location:
    USA
    The Diceware FAQ has some material on how much entropy drops when you drop words, rearrange them, etc. The entropy calculation at that site is different from the entropy calculation that would result if it's assumed that Diceware templates are being used by a cracker. I'll try to post more on this later tonight. That being said, if the words you ended up with seem unrelated to each other, you're probably good to go :thumb:. At least, you're a lot better off than most people.
     
  24. wat0114

    wat0114 Registered Member

    Joined:
    Aug 5, 2012
    Posts:
    1,984
    Location:
    Canada
    Thanks! Yeah, they really aren't related to one another at all afaict. They just seem to roll through my mind really well when I type them, making it that much easier for me to remember them :)
     
  25. MrBrian

    MrBrian Registered Member

    Joined:
    Feb 24, 2008
    Posts:
    6,032
    Location:
    USA
    When a die is rolled 5 times, there are 6*6*6*6*6=7776 possibilities, all of which are equally likely if you have a fair die and rolled it vigorously. That's why Diceware word lists have 7776 words. Each Diceware word is equally likely to be chosen if a fair die is rolled vigorously.

    Let's assume a cracker has perfect knowledge of your password generation scheme, except for the die rolls - i.e. the cracker knows that you're using Diceware, knows the Diceware word list that you're using, and knows that you're using 5 Diceware words. In that case, the best method that a cracker can employ against you is to enumerate the various combinations of Diceware words. Using 5 Diceware words gives 7776*7776*7776*7776*7776 = ~28,000,000,000,000,000,000 combinations of Diceware words. That's a lot of combinations to search! 2 has to be multiplied by itself more than 63 times to reach that number. In math notation, 2^64.6 = ~7776*7776*7776*7776*7776. That's why 5 Diceware words have ~64.6 bits of entropy when a cracker is using the Diceware template with your Diceware word list.

    A cracker without perfect knowledge of your password generation scheme could use a different template though. Let's assume that your 5 Diceware words consist of 30 characters, including spaces. Suppose the cracker also knows that your password consists of 30 characters, for ease of calculation. Let's suppose the cracker uses a template that each character is a lower case letter or a space. There are thus 27 possibilities for each character. The number of possible combinations is thus 27 multiplied by itself (30-1) times. In math notation, 27^30 = ~8,700,000,000,000,000,000,000,000,000,000,000,000,000,000= ~2^142.6. So your 30 character Diceware password has ~142.6 bits of entropy with respect to a template consisting of lowercase letters and spaces.

    You can see that the number of bits of entropy for your password varies depending upon the template the cracker uses. You can't be sure which templates a cracker will use, and there are an infinite number of possible templates.

    Why could dropping Diceware words that you don't like be a problem? Let's assume that Diceware users commonly drop the same 20% of Diceware words in a given Diceware word list, and that crackers discover this fact. This would allow the cracker to focus on the 80% of Diceware words that are more commonly used. Let's assume again that the cracker has perfect knowledge of your Diceware password generation scheme. The cracker could then test against just the 80% of Diceware words that aren't commonly dropped. Let's see how many 5 Diceware word combinations the cracker must go through now:
    (7776 * 8 / 10) * (7776 * 8 / 10) * (7776 * 8 / 10) * (7776 * 8 / 10) * (7776 * 8 / 10) = ~9,300,000,000,000,000,000. This number is approximately 1/3 of the size of the number of 5 Diceware word combinations when users don't drop any Diceware words. In other words, the average cracking time (using a Diceware template) of those users who dropped those unpopular 20% of Diceware words is now 1/3 of before.
     
Loading...
Thread Status:
Not open for further replies.