Is randomly generating passwords from an assortment of dictionary words cryptographically secure?

Question

We should all know the XKCD comic on password strength, suggesting (appropriately) that a password based on multiple common words is more secure and memorable than a password such as Aw3s0m3s4u(3 or something.

I have an application (multi-platform) that I want to generate somewhat secure passwords for, and my password requirements are much less demanding: if the password has no spaces I expect the 'multiple symbols, numbers, mixed alpha and 6+ characters', but if the password has more than one nonconsecutive space I'm relaxing the symbol/number/mixed case constraint, and instead require at least two words that are no less than 4 characters individually, with a minimum password length of 15 characters.

The question isn't about that aspect, but about generating: assuming I want to generate an easy-to-remember and hard-to-guess password for the user, is it cryptographically safe to generate a password based on 5 or so dictionary words from a 10k word list? (Literally 10k words sit in my database, scraped from various sources, emails, etc.) They're all pretty common words, no less than 3 characters in length.

Now I don't want to make these one-time passwords, but I'm suspecting I should at least require the user to change it to something else upon logging in after using this generated password, which is fine and I can, but I also want users to have the option (on changing a password) to generate a 'secure' password that fits my requirements.

From a cracking standpoint, how easy/difficult would it be to attack a password generated using this scheme? There's no fixed length, words in this database table range in length from 3 characters to 11 characters (environment is a word in the database, for example)? The programme generating the passwords will not pick two words with 4 or fewer characters (so the shortest password could be one three-character word, 4 five-character words, and 4 spaces, for a total of 27 characters), and it will not use the same term twice in a password.

Based on samples I've run against it, the average password length generated by the programme is ~34 characters, which seems acceptable to me. Even if we assume that each of the 27 minimum non-space characters (so 23 characters in the end) can be 26 possible states (a-z), that's 23^26 or 2.54e+35 possibilities.

There are 994 words in the database with 3 to 4 characters in length.

We can also assume that the attacker has the dictionary, and the generation parameters/algorithm. Is this still secure, can I get away with taking one word away from the generated password (that's still 21 characters, for 18^26 possibilities (4.33e+32) based on entropy alone), the only problem I see is that this isn't based on character entropy, but on word entropy, which would mean the 5-word password is 10000*9006*9005*9004*9003 possibilities, or 6.5e+19 possibilities, and the 4-word password is 10000*9006*9005*9004 possibilities, or 7.30e+15. Compared to a normal 6-character password ((26+26+10+33)^6 or 7.35e+11 possibilities: 26 lower alpha, 26 upper alpha, 10 numbers, 33 symbols) it's significantly stronger.

Another assumption I made: users will write this down, they always do. I suspect that five random words on a piece of paper (hopefully not in direct sight, but alas that's the most likely scenario) are less-likely to be picked up as a potential password than a, well, complex term that looks like a traditional password.

Lastly, before I get to my actual questions, the passwords are all salted before stored in the database, then hashed with the SHA-512 algorithm 100 times, with the salt being appended between each hash. If the user logs in successfully then the salt is changed and a new password hash is created. (I assume this doesn't help much in a brute-force offline attack, but it should help against active online attacks I would think.)

DatabasePassword = SHA512(...SHA512(SHA512(SHA512(password + salt) + salt) + salt) + salt)...)

So, finally, my actual questions:

1. Is my math correct? (You don't necessarily have to answer this, I'm sure it's close enough in principle to demonstrate my concerns.)
2. Is this generation secure or should I stick to the 'traditional' password generation? Do note that an attacker doesn't have any idea on whether the users' password was generated with this algorithm or selected by the user, the attacker can make an assumption if they know the length, but that may or may not be a safe one.
3. Lastly, did I make any assumptions that would significantly alter (increase or decrease) the security of this 'idea'? (By assuming the per-character entropy of a 6-character password is 95, for example.)

Apologies for the length, I'm used to over-explaining myself to hopefully alleviate confusion.

---

It was pointed out that my question is extremely similar to this one, I want to point out the differences in my generation method (though, honestly, it's still similar enough that it could be considered a duplicate, I leave that up to the community to decide):

1. Each word is separated by a space, this means that all but the first and last three characters have an additional potential state.
2. The password is not selected by a human, it's (mostly) uniform-random generation. No words are preferred over others except to only allow one ultra-short (3 or 4 character) word, once the random generator selects a word of that length no more of those may be selected. (Though the position that word will be in the list of words is random still, and there may not be an ultra-short word selected.)
3. This is mixed in with a separate password restriction, which means the attacker has two vectors to attempt to crack. The user could have selected a password meeting the 'traditional' requirements or a password meeting the 'XKCD' requirements.

Answer 1

First, there is no such concept as a cryptographically secure password. The aim of a password is to be hard to guess for an attacker and how hard it should be to guess depends on how the password is used: if the account is locked after three failed attempts the password can be more weak compared to when an attacker can try an unlimited number of passwords or when the attacker has access to the hashed passwords.

In your case you create a password from randomly choosing 5 words from a set of 10k words. Assuming that the attacker knows your dictionary (not unlikely because your requirement is easy to remember words) and the way the password is constructed from the dictionary this means that there are (10^4)^5 = 10^20 variants. This is similar to guessing 20 digits or a password with 12..13 random alpha-numeric mixed-case characters. Such passwords are usually considered secure enough for most purposes.

As for the storage of the password: don't invent your own method but use methods proven to be good. For details see How to securely hash passwords? In the current form I would consider the chosen method weak because you are using only 100 iterations with a hash function which is designed to be fast. Just for comparison: PBKDF2 recommended at least 1000 iterations in 2000 already and LastPass used 100.000 iterations for server side hashing in 2011. Fortunately you kind of make up for the weaker password storage by having more complex passwords.

Answer 2

It seems to me that your calculations are correct. Even though, please consider the following weaknesses:

1. An attacker can and will sign up for your service with multiple (a LOT of) accounts. From there, it is trivial to create a close-to-original word list. So assume the attacker knows the word list.
2. The attacker will also test your password length limitations. As described here, minimum password length of 12 character is a good hint to an attacker that consecutive dictionary words will be used, thus reducing the search space.
3. The actual word list makes a difference too. Consider a scenario where your word list consists of an amount of longer than 8 characters long words, and your maximum password length is, say 30. This means the attacker can safely assume that no password will be constructed with 4 consecutive 8 character words. Similar to this, many assumptions can exist according to your choice of word list. So another consideration that I think you've missed is word length entropy.
4. Lastly, the fact that you are supplying your clients with a secure and easy-to-remember password generator means that they will use it. So the attacker can also safely assume that all but the most security-aware will use your word list and you password generator.

Despite all of that, I think that what you are proposing is secure. Even when considering all of the above, the resulting search space is still huge.

These are all the problems/assumptions that I found in your description that may decrease the security of your password generator. For your consideration.

Answer 3

Building off of MiaoHatola's answer:

By MiaoHatola's first point, your attacker could narrow down the list and know both dictionaries(the one with short words and the other with 5-letter words). You said your short word list had 994 entries. They have a 1/994 chance of getting the short word on the first try. Now, let's say that you use a list of 10,000 common 5 letter words. These fractions apply:

1/994 * 1/10000 * 1/9999 * 1/9998 * 1/9997

This problem illustrates the combined chances of guessing everything on the first try, assuming they know your word lists.

That is a 1 in 9,934,037,100,000,000,000 chance of guessing just the words, not the order of the words. Factor in the order, and you get quite a high number. My calculator doesn't count that high.

This number doesn't include the possiblity of what MiaoHatola mentioned in their third point because you said you don't have a maximum length. One more thing:

Instead of randomly choosing just 5 words every time, why not randomize that number too? Throw in an extra 7 letter word every once in a while. Maybe include a 2 digit number at the end. Try making the attacker guess. That significantly increases your security. At this point, you could leave the hashed passwords unguarded, because the sheer amount of possibilities is overwhelming. So to answer your question, yes. This increases security. By a lot.

Answer 4

You cannot base uniqueness on 27 characters because the characters are not random.

If you have 10K words and use 5 words then 10^20 unique passwords (or phrases)
100,000,000,000,000,000,000

Is that unique enough to thwart a brute force attack
At 100 a millisecond that is is over 30,000 years

But the cost is users are entering 27 characters. I don't want to enter 27 characters. I will probably enter it wrong 1/2 the time and have to reenter. 5 words in a random order are not going to be easy to memorize.

Consider 6 characters from A-Z, a-z, 0-9, and _
That is 62,523,502,209 unique
As a user I would rather memorize and enter 6 random

I don't think 5 random words written down would be a good way to disguise a password. Especially if people know your application does that.