8

I read about Diceware passphrases and whipped up a little program to generate passwords in that style. I do this by taking the list of dictionary words to create passwords and "ordering them" by a random number (one produced by System.Security.Cryptography.RNGCryptoServiceProvider), in essence shuffling them. I then pass that into a queue and dequeue words when a password is to be generated.

This is a little bit different from the pen-and-paper version, since there is a chance there, however remote, that a word may be repeated. So clearly we reduce the number of possible passwords somewhat. Does this reduction in possible passwords significantly change the susceptibility of such passwords to cracking? Would it be better to read the dictionary into an array and get words by generating a random number and accessing the array at that index?

10

This might get better responses in crypto.stackexchange.com or math.stackexchange.com, but I think I can give you the gist of it.

If we step away from words and take a look at some numbers it might help to illustrate.

Take for example a four-digit code for a lock.
There are 10 possible digits (0-9) and four spaces where they can be entered, so there are 10 * 10 * 10 * 10 = 10^4 = 10,000 possible combinations.

If you say there can be no repeating digits, then on the first space you would have 10 possible digits, on the second 9, on the third 8, and finally 7 possible digits on the last space.
This leaves 10 * 9 * 8 * 7 = 5,040 possible combinations, or, about half.

If we apply this to your password maker, we would take the total number of words you are using as possibilities (most Unix systems come with an English dictionary with around 200,000, so we can use this number for now), and the total number of words in your password (using 6 as the minimum Diceware recommends).

This means that without any restrictions on repetition, there are exactly 200,000^6 = 64 nonillion possible password combinations.

If you were to disallow any repeating words, there would be 200,000 * 199,999 * 199,998 * 199,997 * 199,996 * 199,995 ≈ 63.995 nonillion possible password combinations.

That is a difference of approximately .00008%.

As you can see, with a dictionary of at least 200,000 unique words and a keyspace of six words, the difference between no password restrictions and and limiting repeating words is negligible.

This difference would then have an equally negligible effect on the password's resistance to cracking.

EDIT

LieRyan has pointed out Diceware uses a wordlist of 7776 common, easy to type words. If we wanted to see the difference with a list of that size, it would look something like:

No Restrictions: 7776^6 ≈ 2.21 sextillion possible combinations.
No Repeats: 7776 * 7775 * 7774 * 7773 * 7772 * 7771 ≈ 2.2064 sextillion possible combinations.
Difference: ~0.19%

Let's take a look at what that means to someone trying to crack your password.

Assume your adversary is capable of one trillion guesses per second. -Edward Snowden, 2014

If we take this estimate (emphasis), we would divide the total number of possible combinations by the number of guesses/second to get the total seconds taken to bruteforce every combination of the wordlist.

That is, 2.2 sextillion combinations / 1 trillion guesses/sec = 2.2 billion seconds = 69.72 years (compared to 70.03 years without password restrictions)

This is the average time it would take a well-funded and equipped password cracker (with access to a copy of your wordlist) to bruteforce a password made with this method.

  • 1
    Diceware uses a wordlist of 7776 common, easy to type words, not the full 200000 words from entire English vocabulary. – Lie Ryan Jan 28 '16 at 3:05
  • @LieRyan That's true, but the formula can easily be applied to that too (and besides that my implementation supports a much larger dictionary). – Casey Jan 28 '16 at 3:27
  • @LieRyan I was trying to use some standards I saw reasonable for use in a fork of the project, but I understand what you're saying. That is strange to me that they would use so few words. – cremefraiche Jan 28 '16 at 5:47
  • 1
    @cremefraiche: proper Diceware are intended to be generated using a physical six-sided dice, you roll five dices and look up the corresponding word in the word list. Also, the recommended six words diceware applies when using this standard 7776 wordlist. If you use a 200 000 wordlist, then you can get the same passphrase strength with 5 words. – Lie Ryan Jan 28 '16 at 6:46
  • 1
    The formulae are here: Repeats are allowed vs Repeats not allowed – SilverlightFox Feb 1 '16 at 10:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.