What does "random" mean in the context of password creation?

Question

Disclaimer: as you will see from my question I'm a total outsider in this subject, just very curious.

I was wondering how easy it would be to crack a password-protected RAR5 file, and I found many answers along the lines of "a truly random password would be much more difficult to crack than a password based on real words". Also, a lot of answers refer to password randomness.

I know that passwords based on real words are easily cracked by dictionary attacks and probably this is what those answers refer to, but I'm still not clear about what "random" means in the context of password creation, for the following reason.

Even if I generate a sequence of characters using the best "randomizer" ever, the chances that I get HelloWorld and the chances that I get f.ex. gkwwpBnePU are in my understanding exactly the same, so does "random" in this context mean "as distant as possible from any real word"? But if yes, doesn't this make the password not-so-random after all?

The thought that started my doubt - which I believe is the same concept but I'm not sure - is: if I choose a password which is a real word but from an obscure dialect of a very uncommon language whose dictionary no attackers would feed to their cracking tools, would such password still be more crackable than gkwwpBnePU? (assuming of course that gkwwpBnePU isn't actually a real word in any language, see what I mean?).

Answer 1

"Random" means: "that which the attacker does not know".

The important point to understand is that attack costs are always on average. They don't make sense on a single data point. An attacker may always get lucky and find the right password on his first try. This is merely improbable.

If you generate passwords as sequences of purely random characters, then you may obtain "HelloWorld"; but usually you won't, and, crucially, the attacker won't be able to guess with non-negligible probability that your password consists of two concatenated English words because, on average, it does not.

One way to say it is that password entropy is not a property of the password, but of the process that generated the password; and it does not impact the contents of a single password, but the average contents of passwords, taken over sufficiently many experiments. More on password entropy here.

Averages are still the important notion because the attacker, like everybody else, thinks in terms of economics (although he, like most other people, is not completely aware of it). The attacker won't bother attacking your password if his chances of breaking it are lower than his chances of winning millions of dollars at the lottery. Even if he may always "get lucky", the lottery is much less effort, and 50 millions of dollars are a lot more rewarding than an access to your Facebook account.

Answer 2

“Random” means that all possibilities in the search space (passwords of up to N character chosen in a set S) have the same probability (up to a small tolerance). The intent is that the adversary (the guy who wants to break the encryption by guessing the password) has no better strategy than try all possible passwords. With a random password, the adversary has to try half the passwords in the search space to get a 50% chance of guessing right.

Let's say you're generating a 10-character password where each character is a lowercase or uppercase letter. That's 52¹⁰ ≈ 1.45⋅10¹⁷ possibilities, i.e. over a hundred million billion. The probability of generating gkwwpBnePU as a password is thus one in a hundred million billion and some change. The probability of generating HelloWorld is exactly the same, so there is no advantage to you to pick one over the other: the two choices are equally strong.

Sure, the attacker could guess HelloWorld. But they have an equal chance of guessing gkwwpBnePU.

If you know that the attacker is working off a dictionary, then you may want to avoid words in this dictionary. However this is only useful if the dictionary represents a significant fraction of your password space. If that's the case, your password space isn't large enough.

Let's say the attacker's dictionary consists of a million words and he'll try two words together. That's pretty large already — 10¹² cracking attempts will require a small cluster of computers to carry out in a reasonable time. There's less than a chance in 100000 that your randomly-generated password is in that search space. You gain a tiny advantage in avoiding this search space, but there's a cost. First, you're adding complexity (so adding a risk of bugs, e.g. to accidentally eliminate more of the search space than you intended). Second, you don't really know what the adversary will do. Maybe one adversary uses this particular dictionary, but another adversary doesn't (and even the first guy will change their strategy once they find out what your password generation policy is). For any adversary who doesn't use this particular dictionary, you're helping them by restricting your password space. So this is counterproductive.

Choosing a password from an obscure language would be even worse. No matter how obscure the language is, if you have a dictionary for it, then you can assume that your adversary has one. Restricting to dictionary words would immensely reduce the search space and raise the capacity to find the password by brute force from infeasible to easy.

Answer 3

Even if I generate a sequence of characters using the best "randomizer" ever, the chances that I get HelloWorld and the chances that I get f.ex. gkwwpBnePU are in my understanding exactly the same, so does "random" in this context mean "as distant as possible from any real word"? But if yes, doesn't this make the password not-so-random after all?

Yes. This is a known problem with excluding so-called "weak keys" in cryptography. By excluding certain classes of weak keys, the remaining key-space has been reduced. From time to time, key selection algorithms have popped up that accidentally excluded almost all keys, leaving a very small search space for attackers.

The reasoning you describe is a typical precursor to this type of error: If certain keys are "weak", then surely the complete opposite of those keys would be "strong", right? However, if you try to find a key that is "the exact opposite" of a common phrase like Hello World, it will be guessable to an attacker that applies your "exact opposite" mapping function to common phrases.

There is a huge difference between avoiding weak keys, and choosing only keys that are maximally distant from a weak key according to some distance metric (the latter is a serious mistake stemming from a misunderstanding about threat models and probabilities; don't do that).

So, avoid weak keys like Hello World, but not to the extent of narrowing the key choice down to a search space that is as small as the set of "weak" keys.

Answer 4

Random here means "what will be time-consuming for the attacker".

Passwords are technically made up from various characters (which may be lowercase, uppercase, ...) because they are handled as a string. There are two kind of passwords:

1. the ones which are handled by the users
2. the ones which are handled by a password manager

The second case is easy: go for long, complicated combinations of whatever you can, up to the limits of the application asking for the password (they put some limits, sometimes these limits are horrendous). !sg8Itp2%hjxXxo6a6TGMbJs8Jcxtk205XgZ@M^C2CmAgfC*q6 is a great password I just came up with, random and everything.

The first case is more complicated as you have a conflict between your memory, what is "random" for you and what is a "character".

Let's make it clear from the start that anything other that the truly random password above reduces considerably the so called 'key space', that is the number of possibilities for a password. the larger the key space, the better. But this is not a problem, when approached carefully.

Your only aim is to build a password which takes a "long time" to be cracked. You define yourself what is a long time. This can be 1 minute or 100 years. Due to statistics and the fact that CPU is cheap let's aim for 1000 years. 1000 years of efforts by a dedicated cracker who will have the computing power of the NSA at his disposal.

The cracker will attack you passwords by trying all possible combinations (I made some assumptions here regarding the proper quality of password storage by the application owner). This means that he will try a, b, ... aa, ab, ...

Well, no. He will not try that because he knows that your password is likely to be at least 6 characters long. And here comes one of the key points regarding randomness: you must absolutely assume that the cracker knows how your password is built. No "security by obscurity" here (it is useful in other places, but not here).

Which leads me to the last part: your memory. You will not be good at remembering the 50 characters password I gave earlier. You will end up with something which resemble words and their variations. Embrace that! Go full monthy and build a password made up from a few (4 or 5) random words!

But "everybody says that using dictionary words is bad". The ones who did not do the math do.

Let's compute that: you have a password made up of 4 words, each of them being one out of 7000 possibilities (this is the average vocabulary of the population. Please note that:

• the total vocabulary is in the range of 70,000-100,000 words (French or English) ...
• ... so we take a small subset of words you can actually think of ...
• ... as you will probably not choose your words with the dice method but rather out of the blue

You therefore have 7000^4 ~= 10^15 passwords. Top-end dedicated cracking environments can try 10^10 combinations per seconds, which is about 1 day with the 4 words version. 5 words bring you to 30 years. This is for offline attacks, when the attacker got hold of your password database. An online attack is impractical (about 1000 combinations pers second best case).

As a comparison, a 8 characters password with lower case, upper case and digits has 10^14 combinations.

Notes:

• the information above is pertinent when attacking passwords either online or offline, for correctly stored passwords. This is to say that if the password is stored in plain text or is a non-salted short one, it will be cracked immediately
• I strongly belive that the password stategy must be chosen wisely. Sometimes no password is OK, sometimes multifactor authentication is the way to go. There is no "one size fits all" solution.
• I also strongly belive that the password startegy must be pragmatic and address real-world constraints. Not everyone can remember 253 passwords which are 25 characters long and chnage every three months.
• sadly, many standards and official recommendations are dumb as [censored] and we still end up with Hello1 passwords because they happen to fit the construction rules.

I did recently a comparison of password recommendations from NIST, ISO27002, HIPAA, SANS, PCI-DSS, French and German governmental agencies, ISF and CobIT (specifically on password expiration). The order above is from "well thought" to "I took whatever was invented by a random guy or gal in the 90' and put that on paper because I stopped math in 6th grade and my 4 neurons do not allow me to concentrate more that 20 seconds on a problem"

EDIT: following a request in comments, below is the conclusion from the review of the standards. This is in contrast with research showing that password expiration does not improve security.

• no recommendation at all (NIST)
• no recommendation other than “regular changes” (ISO27002)
• risk-assessment based changes, less than 2 years (HIPAA)
• 180 days (SANS)
• 90 days (PCI-DSS, French and German governmental agencies, ISF, CobIT)

The ISF recommendation is particularly disappointing, taken into account the great work they do.

Answer 5

Even if I generate a sequence of characters using the best "randomizer" ever, the chances that I get HelloWorld and the chances that I get f.ex. gkwwpBnePU are in my understanding exactly the same, so does "random" in this context mean "as distant as possible from any real word"? But if yes, doesn't this make the password not-so-random after all?

No, that's where your fallacy is. If your reasoning was true, it would also be trivial to win the lottery because the winning numbers are just as likely to come up as the other numbers.

The reason is that for every one HelloWorld that makes sense, there are billions of "gibberish" passwords. So an attacker who knows that you use a dictionary password has a lot fewer passwords to try.

The definition of random is simply that all allowed characters have an equal chance of occurring. Usually, another criteria is added: each letter is also independent of the preceding letters.

Both of these criteria rule out using a dictionary from any language. In every conceivable language, some letters are more common than others (for instance, in English, e, n, s and t are more common than q or x). In cryptography (separate matter from passwords, just mentioning it for interest), this allows cracking some codes with statistical analysis.

Also in any conceivable language there are rules about which letters are more likely to follow other letters. For instance, in English an h is far more likely to follow a t than following a q.

Answer 6

What does “random” mean in the context of password creation?

Creating a string based on variables that (can) change (aka random).

A password can be "built" from many things: words, numbers, letters on their own, a combination of the aforementioned. A password could also be built from variables, such as the temperature of your GPU/CPU, amount of RAM, internet browser version, etc.

That being said, the password still has to be encrypted. The encryption method does not care whether your phrase is merely "hello" or a phrase based on truly random variables. It will simply encrypt the phrase with the same method, though the output should always be different.

Once the password is stored, in i.e. a database, and retrieved by a hacker, an attacker can start bruteforcing the password. Even though you have used an incredibly extraordinary method to generate a random password, it's still going to be decrypted at some point.