Comments

none • August 22, 2014 1:07 PM

Guess some context is missing, both on the article and in this blog post. Somebody minds to explain ?

JC • August 22, 2014 1:13 PM

So sad and true. I know someone whose master passwd still is one of their favorites Lord of the Rings characters.
Not funny at all, my pressiousss! 😉

Name (required) • August 22, 2014 1:19 PM

It would be funny, but that article just happens to be my banking password. Thanks for the Bruce-force cracking of it. Now I’ll have to find another article (this one obviously isn’t long enough).

stine • August 22, 2014 1:19 PM

I thought it was funny. Especially the way the article did more than tell you which show his password was based on, but what character, and what episode, and the details of the episode.

I wonder if this story was his password hint.

If it was, I hope he remembered his password.

Anura • August 22, 2014 1:44 PM

For those of you that don’t know what The Onion is, The Onion is a joke news site and Mark O’Connell is essentially a fictional character in a fictional news story.

MrC • August 22, 2014 1:59 PM

On the topics of “funny” and “passwords,” I’d like to revisit the XKCD password scheme. I know that Bruce dismissed when describing his own password scheme. But he didn’t really spare the space for an explanation at that time. Could someone kindly explain to me WHY the XKCD scheme is problematic, and perhaps HOW one would go about breaking it?

In my (probably oversimplified) understanding, the XKCD scheme is essentially a 4-character password using a ~25,000-character alphabet. That yields a search space on the order of 10^17. Similarly, a 9-character password using a 94-character alphabet also has a search space on the order of 10^17. (Unless I’ve miscounted, uppercase letters + lowercase letters + numerals + symbols = 94.) What am I missing here?

Anura • August 22, 2014 2:12 PM

@MrC

The problem with passwords is not length or complexity, it’s choosing them. The XKCD comic fails to mention how to choose passwords, and that is where most people will fail with the scheme. We should point people to diceware, which can generate passwords without relying on Human Semi-Random Number Generators.

Jim • August 22, 2014 2:55 PM

@Anura – Not true, the comic specifies using random words. If people don’t know how to randomize correctly, I agree that that’s a problem, but it’s not xkcd’s problem.

Clive Robinson • August 22, 2014 5:14 PM

@ Jim,

If people don’t know how to randomize correctly, I agree that that’s a problem

To be honest I don’t think anybody knows “how to randomize correctly”, because we still cannot say what “to randomize” is. To see why if you look “randomize” up in a dictionary it basicaly says to do things at random.

So in turn you look up “random” and it says,

Made, done, or happening without method or conscious decision

Which to be honest is not very helpfull, and is most definatly not the description of the quite deliberate “concious” and “methodical” action of throwing a dice etc.

Even the mathmatical definitions eventualy come down to talking about “chance”… where as some mathmaticians will say that the throw of a dice is in fact a “chaotic process” not a random process.

So it’s a bit difficult to do something correctly when people cannot accurately define or describe what the something is. And some natural philosophers are concluding that random does not exist at all, it’s just that we cannot see the process behind the events because they are outside of what we can observe….

Godel • August 22, 2014 5:18 PM

I thought the associated article on the Onion page was funnier (in a wry, bitter kind of way).

“Report: 79% Of Minority Suspects Receive Miranda Rights While Unconscious”

Anura • August 22, 2014 6:04 PM

@Godel

One of my favorites in recent times is this one:

“15 Years In Environment Of Constant Fear Somehow Fails To Rehabilitate Prisoner”

http://www.theonion.com/articles/15-years-in-environment-of-constant-fear-somehow-f,35434/

@Jim

Well, the point is that the single most important part is the quality of randomness which the comic doesn’t address, so pointing people to XKCD where random isn’t really explained. Colloquially, random can mean anything from someone saying something seemingly out of nowhere “Well, that was random” to the possibly non-existant idea of a number that can’t be predicted by someone who has 100% knowledge of everything in the universe to the point where the number is being generated.

This is why I mentioned the HSRNGs, because people do try and do random and it turns out they are horrible at it. Pointing someone to diceware, which is a well-defined and sufficient algorithm is the more appropriate avenue.

Joseph Arpaia • August 22, 2014 7:13 PM

@Clive @Anura

At the risk of being corrected by those with more formal training I think that mathematicians define randomness based on the probability distribution across all possible outcomes. What is colloquially meant by “random” is a uniform probability distribution in which each outcome has the same probability of occurring. An example of this would be a coin toss or rolling one 6-sided die.

There are other distributions in which the outcomes are based on chance but the probability of the outcomes are not equal. For example the sum of the roll of two 6-sided dice. The probability of rolling a 12 is much less the the probability of rolling a 7. If one were rolling a large number of dice the probability distribution of the outcomes would approach a Gaussian distribution. So the outcomes would be generated by chance and therefore random but some would occur much more frequently than others.

whpratt • August 22, 2014 7:39 PM

Anura, that Onion article brings to mind the sad, stupid, and damn near exact opposite case of one Rene Lima-Marin.

Anura • August 22, 2014 9:08 PM

@Joseph Arpaia

My experience is that when a non-math person says random, they really mean non-deterministic, which, along with the statistical definition, is insufficient for cryptography.

In cryptography, randomness is best thought of as unpredictability. Unpredictable is limited by knowledge; for all we know, anything can be predicted given enough information, and in cryptography the goal is to prevent the attacker from having enough information. So what is sufficiently random depends on the knowledge of your attacker; is your attacker viewing data in a database with no real information on who you are? Well, your MAC address, boot time, IP Address, and user name might be sufficient enough to seed a RNG without the attacker being able to recover the state.

Typically, however, in cryptography you want to assume as little as possible about how much the attacker knows. Basically, the ideal RNG is one in which an attacker in the same room as you, knowing everything about your machine, including the state when you first entered the room cannot determine or influence a future state of the RNG, with anything short of root access to your machine.

So that’s the real difference between randomness in cryptography and randomness in mathematics from my perspective.

Clive Robinson • August 23, 2014 12:28 AM

@ Joseph Arpaia,

You’ve missed the point of the comment.

The problem is that all the definitions boil down to either “random” or “chance” neither of which has a usefull definition in a dictionary or else where for that matter.

Try thinking about how you would explaining what chance or random is to a six year old, then the much harder task of explaining it to an adult who already thinks they know what chance or random is. And don’t cop out to arm waving or saying “you know” or avoiding it by using other words such as probability that when you strip off the mumbo jumbo come back to chance or random.

With regards random in mathmatics you have “determanism” which has the outlook that random does not exist, it is just “unpredictability” that is the value of a random variable is always found by a determanistic process, but the process is not discernible by an observer of the random variables value. As one might say “In the opposite corner” are those that take the rival Bayesian interpretation of probability, which choses to believe in the unexplainable chance or random as an axiom. They seek to charicterise the changing values of a random variable and charecterise it as a curve on a graph and call it a distribution. The fact that you get distributions that are not flat is seen by some as a point in favour of the determanists view point. Either way statistics is a usefull tool for people dealing with non complex physical objects and processes.

More recently we have another contender which some consider to sit in between the other two camps and these are the mathmaticians investigating chaotic systems, they will quite happily point out that the unpredictable nature of a dice roll is infact a chaotic process. Without going into details broadly a chaotic process is one that is determanistic in nature, but so sensitive to it’s starting values that the output is in effect unpredictable. There are however other views in other fields of science one of which is quantum physics, whilst random has worked for them for a century, it’s begining to show cracks at the seams which is causing some to revisit early ideas that were discarded for one reason or another. One view is that behind the quantum randomness is a determanistic process we cannot see or measure directly in our perceived three dimensional universe but that make sense in higher dimensions. But again is this notion of what we see is unpredictable.

But what does unpredictable mean, as already indicated from one point of view it implies a hidden determanistic process which is not readily apparent to the observer of the process output as expressed by the values of a random variable. Yet to others it implies that there is no pattern discernible and that there is ultimately something that is unknowable, that can not be predictable no matter what invention of mankind is brought to bear on the values of a random variable.

There is a fly in the ointment, which is the mathmatical notion of a one way function conceptualy it is a function which is easy to compute in the forwards direction, but hard to invert to find the input from any known output values. There are other constraints on the definition and the meanings of easy and hard may not be what you expect, nor for that matter do we have proof that the exist. However the bulk of cryptography rests on the notion and it’s used in the logic of hashes and block and stream ciphers as well as the more informal idea of mathmatical ciphers like Public Key.

As FEAL demonstrated on repeated occasions, the idea of what is and is not invertable can change quite quickly and what was assumed to be non invertable with an unpredictable output today is found to be invertable by new statistical methods thus is relegated from unpredictable to predictable (under certain constraints).

Thus there is a notion of degrees of unpredictability and this is where the problem hits the points. Few people have any idea about why a function or process might be unpredictable against an attacker, and thus chose what appears unpredictable to them. The fact others such as an attacker might find that trivially invertable and thus easily predictable does not figure in their calculations.

Thus without guidence they are very likely to make the wrong choices, which is the primary point.

The secondary point I was making, is that we currently have no way to test what is a good or bad choice except by trial and error, and most times we find error at some point. Thus it is not possible to “know” definitively “how to randomize correctly” it is now and will remain for the forseable future an open question, not just philosophically but theoretically, and to a certain extent practically.

Winter • August 23, 2014 5:39 AM

@Clive
“Thus there is a notion of degrees of unpredictability and this is where the problem hits the points. Few people have any idea about why a function or process might be unpredictable against an attacker, and thus chose what appears unpredictable to them. The fact others such as an attacker might find that trivially invertable and thus easily predictable does not figure in their calculations.”

I think you get carried away here. I think this is simply Kolmogorov (algorithmic) complexity: There is no easier way to get the result than to simply copy them (=check them all). Or in Bayesian terms: You have not enough information to make an informed choice out of all the possibilities.

In terms of passwords, this means that you do not have information to get to the password any faster than trying them all.

@Clive
“Thus without guidence they are very likely to make the wrong choices, which is the primary point.”

That depends. It might be very “easy” to guess the password of a spouse or child. I do not see how it will be easy to guess the password of a person I have never met. But adding “Do not use a popular TV show or movie” would help. In the original comic, that was most certainly done implicitly.

Also, Xkcd was giving a way to select a password of roughly 44 bits. That should not be your master password, but something you use online.

Clive Robinson • August 23, 2014 11:08 AM

@ Winter,

I think this is simply Kolmogorov (algorithmic) complexity

It would be nice to “think this is simply Kolmogorov complexity” (KC) problem but the idea only partly works in theory for bounded vectors of finite length and not at all for unbounded entropy generators (if they exist).

The simplest informal example of a KC generator is a program which wraps around the desired output and prints it, this obviously implies stored state which provides an upper bound on the output.

It can be trivialy shown [1] that the longest possible output of all 1s or all 0s in such a –non degenerate– stored state generator system is 3n-2 where n is the size of the state, and further the complexity in simple gates of the update function has a maximum relating to 2^n(n+1) + Cn simple gates (where Cn is the gates required to update the storage elements in the array and 2^n(n+1) the gates in an efficient ROM to map the update function).

It can further be shown that by the use of a divide an conquer algorithm that the maping function can be reduced substantialy by the use of the equivalent of an n bit counter and successive simple maps that reproduce the sequency output of the generator –such as a Grey Code or Walsh generator– if and only if the generator output is compressable efficiently in some way.

This can be seen as the equivalent of a Turing engine driving a chain of Turing engines however each engine requires it’s own Tape which is the equivalent of increased internal state in the generator. Thus there is on some rare occasions the possibility of reducing the gate count of a complex stateless mapping function by swaping the number of gates in the statless update function with the use of increased secondary state within the Turing engines. By definition this means the usage of the state within such a system is sub optimal for any given algorithm.

But it gets worse, it is axiomatic that the set of all possible output strings, –for any given generator state size,– that by far the majority of the set members are “complex” in the sense that they cannot be compressed in any significant way. Thus, it turns out that the complexity of any given set member cannot be formally proven if the complexity of the string is above a certain unknown threshold. Which in turn means we cannot know if we have found a set member that is amendable to compression or not which means we cannot for the majority of set members say there is let alone find an efficient compression algorithm.

Obviously this is a problem, in that by far the majority of generators can not be differentiated between a counter driving a random map –which is only invertable by brut force methods that have significant limitations– and an efficient algorithm or what is regarded as an unbounded or true random generator. And the inverse of this is above a certain set of bounds set by the laws of physics we cannot tell in by far the majority of cases if the output of any generator we observe is produced by a true entropy generator or some kind of determanistic generator. Further if it is determanistic we have no reliable way to see if the sequence the generator produces has hidden markers that alow an adversary to reliably predict the next bit or entire series of bits from the generator.

Whilst this might still be acceptable for “just a one off password generation” it rapidly becomes a liability when the actual output state becomes known to an adversary. The problem then shifts from brut force searching or random guessing to finding an offset from a known starting position, which can be trivial to do.

As for finding a known start point you may at some point have set up an account on a machine under the control of an adversary or one due to a man in the middle or known key attack, the adversary can see the plaintext of the password being sent. As we know the NSA amongst others is known to have had available to use all of these attack methods for several years….

Thus the XKCD system fails on at least two counts, the first is not specifing a suitable random source, the second is not reusing words in the selection list in any future passwords.

That is the list of a thousand words is updated with a new word to replace a selected word for use in a password or for other purposes.

This obviously has practical limits so a lesser constraint is to ensure that if a word that has been used in the list before, it is not added back to the list in the same position as at any previous time and does not get used more than a quater of the list size times.

[1] The proof is simply this assume a binary storage array of length n and an update mechanism without state that maps one output to another –different– state in the storage array. The maximum length of any state patern is n bits the nearest patterns to this differ by one bit n-1 at either end of the array a simple three bit array would be 111 with 011 & 110 being the two n-1 patterns. Thus the maximum 1s output would be 011 111 110 giving seven set bits or 3n – 2 = 3×3-2 = 7. It can also be trivialy shown that in a degenerate state where one state updates to the same value that this can easily be compressed by a simple program that repeatedly prints out the same n bit length pattern. It can also be shown trivialy that either the state array update mechanism will not have a degenerate pattern and thus provide a total output of 2^n unique n bit patterns or it will either only produce a lesser pattern of unique n bit patterns before repeating them. Thus the upper bound on any given generator output pattern will be 2^n x n bits. Less trivialy it can be shown that any such string can be analysed to find it’s underlying sequency using Walsh transforms, and this will provide limits on the potential compressability –without adding aditional state– thus algorithmic complexity (in gates) of the output sequence from the generator (think of the state array as a counter of n bit length driving a gate array of unknown number of simple gates which map the output values, up to the limiting value of an efficiently implemented ROM of n bit address and n bit data output).

MrC • August 23, 2014 7:17 PM

@Clive

First of all, thank you for responding to my question.

Second: Many folks seem to criticize the XKCD scheme for the possibility that the words may not be chosen at random. That strikes me as an unfair criticism on two grounds: First, the comic does expressly say “random… words.” Second, it seems to me utterly obvious that the words must be random, so much so that I feel only an idiot would think otherwise. If “idiots might do it wrong” is accepted as a legitimate criticism, then just about any process for doing anything can be considered fatally flawed. For instance, consider Bruce’s password scheme — do we consider it fatally flawed because idiots might use common Bible passages or top-40 lyrics as the base sentences for password generation? (Aside: I think it is a legitimate criticism that a process is so complicated that the average person is unlikely to do it right; or even that something about the process makes it easier to do it wrong than right; or that the right way to do it is unintuitive, while the wrong way is intuitive — but I don’t think any of those apply in this case.) So, let me rephrase my question: If we assume that the user is not a complete idiot, and therefore does chose the words using an adequately random means, is there still something wrong with the XKCD password scheme?

Third: The discussion regarding the true meaning of “random” seems to me completely beside the point. Those questions hang over EVERY use of “random” input in the same way and to the same degree. They are not specific to this particular password scheme.

Fourth: I’m not convinced by your second point about never reusing words. In fact, I think I disagree. To me, it sounds akin to saying that, having once used a lowercase ‘c’ in a random alphanumeric password, I must never again use lowercase ‘c’.

My point may come out clearer if I try to make explicit my thinking underlying my earlier post: One might describe a generic random password scheme as follows: “Select a symbol randomly from an alphabet of X symbols; repeat N times. (Make sure to pick X and N big enough to get sufficient entropy.)” Unless I’m mistaken (and, if I am, please explain how), this generic random password scheme is equivalent to both (a) the random string of uppercase-lowercase-numerals-and-symbols scheme — which everyone seems to agree is ideally secure, but difficult for humans to remember — and (b) the XKCD scheme (as well as any number of other schemes). I don’t see why a static alphabet is a shortcoming for this one particular scheme, but not any of the other variants of the same generic parent.

Perhaps, one might say, “it’s not a shortcoming per se, but the scheme could be improved by using a non-static alphabet. I’m not sure whether that’s true or not. I have an instinctual (and therefore possibly wrong) feeling that you’d be better off just using a larger alphabet that included all your replacement words from the outset. I’d also be worried about revealing information about existing passwords if one’s implementation accidentally leaked the alphabet’s state.

DB • August 23, 2014 9:41 PM

@MrC

The problem isn’t that xkcd forgot to say “random”… But that the average person on planet earth thinks that words chosen “randomly out of someone’s head” are at least “random enough” for the xkcd method. They most certainly are not, and most blog readers here know that, but the average person does not. This is where xkcd fails, for the average person.

Scott "SFITCS" Ferguson • August 23, 2014 10:10 PM

MrC

@Clive


First of all, thank you for responding to my question.


Second: Many folks seem to criticize the XKCD scheme for the possibility that the words may not be chosen at random.

With good reason. I won’t address your comments point-by-point as they are somewhat circular and some are strawmen. Hopefully my response won’t stop Clive from replying – I look forward to reading it.

Good math is a requirement for good cryptography. Good cryptography is not to the automatic result of good math. It’s a mistake many mathematicians make.

They are not random words (see my low-hanging fruit comments further down). Further – Randall does not claim they are random (wisely doesn’t use the word). “Many folk” confuse random – which may not exist, with “degrees of predictability” – but mostly they misunderstand and misapply Randall’s example[*1].

Randall shows how, for the purpose of creating a reasonably strong memorable password (singular). “Many folks” make the mistake of taking Randall’s example and using it as a formula to create strong passwords. And they fail to see the difference.

There are very few situations that justify the use of a memorable password. Use a password manager. Randall’s example compares a mixed case alpha/numeric/other printable character password of 11 characters, against a 25 character password composed of 4 lower-case alpha words. It’s not comparing apples to apples – nor is it meant to be (it’s done to make a point), and it solves a non-existent problem (failure to remember a password due to an OpSec failure – that of not using a password manager).

If you apply Randall’s suggestion to every password you create your security sucks. It’s fine for the few circumstances where you need to create a memorable password.

A cursory read of the cartoon may lead to someone believing that correcthorsebatterystaple would take 550 years at 100 guesses a second to break. It won’t. Don’t confuse entropy with difficulty of breaking the password.
Entropy (correctly calculated) is of as little relevance to the average “user” as me telling you that half the time the password would be brute-forced in 275 years at 100 guesses a second (I haven’t checked those figures of Randall’s – I did check his entropy calculation though…). Unless of course, you find “best case for defender” “predictions” comforting (see Madame Zelda instead of Bruce Schneier, ask for the “special” lucky rabbit’s foot). A “user” should be concerned about the “worst case” scenario – their measure of defence against an attacker that’s not an idiot – who will harvest the low-hanging fruit first (a significant number of oginaral thinkers actually use correcthorsebatterystaple, and mydogsnameissandy). That’s four low-hanging fruit attacks – see them?

  1. when attempting to break a password of more than 11 characters a significant percentage will be composed of words.
  2. those words will be lower-case
  3. those are dictionary words
  4. those words are 7 characters or less

2 to the power of 44 as a measure of exhaustion sounds good – until someone tries 10000 word combinations to break your password. Perhaps a 10% success rate using 10000 attempt attacks sounds comforting… unless you have more than one passworded account….

Does the user speak English as a second language? A significant percentage of those people will use words from two languages for passwords longer than 10 characters.
Does the user work in an environment that allows short passwords, has a requirement to use alpha upper-case and lower case with at least one number and are required to change the password at reqular intervals without reusing a password? A significant percentage will use the same word or two word combination followed by a two digit incrementing number.

Ask any drug squad police officer which 3 places pot smokers usually keep their pipe – or a burglar in close proximity of what do most people hide their valuables to find out just how clever we are (not). Predictability is dog without loyalty that sees the hand that feeds as just a source of protein.

Randall shows how, for the purpose of creating a reasonably strong memorable password (singular). The stated motivation is that people have trouble remembering good passwords – which is correct. That doesn’t automatically lead to the “a good password is memorable” or “doubling the entropy of the cartoon example is better”, or even “this creates a solution to a problem that doesn’t exist” (there are other, better, methods of creating memorable passwords that don’t avoid the necessity to learn OpSec).

If you don’t have a compelling reason to create a weak password you should create the strongest one possible (not – I “guess” this password is strong enough for the “guessed” risks). It’s implicit that the password should be defined by the context.

There are several major failings with Randall’s example – most only apply when making that mistake.

For the average “user” (if such a beast truly exists) there are two important points:-

  1. “Random” is a lazy way of saying “how unpredictable is your password”?
  2. Often the question “how does Average do this?” can only be properly answered when correctly phrased as “how does the uninformed become expert?”

[1] a common psychological failing – obviously the experts aren’t that clever, and must of spent those years drinking because I only had to “watch a half-hour television reality renovation show”/”look at a cartoon” to “understand” the subject. I can visualise it therefore I understand it. An emotional investment in intuition that cannot be challenged – so confirmation bias will occur when the belief is challenged. Try this – “all intuition is wrong”. How about “you are mostly wrong when you guess who it is that’s ringing”? 🙂
Don’t suffer from confirmation bias? – still convinced those words are random even after reading the low-hanging fruit? Hint: if those words don’t represent a range spread across the total possibilities they aren’t close to random (coughLowFoggIndex*cough).

Consider an account that locks out after 3 failed attempts – a password for it requires what degree of unpredictability? (there’s a missing risk management question there).
I find security fascinating – but I’m not a professional, and I refer to them constantly. The difference between an expert and I is not in the answer but in understanding the subject well enough to ask the right question. e.g. Why didn’t Randall include an upper-case alpha? Why not insert a number using the arrow keys (most key loggers don’t capture arrow keys)? Why wasn’t a word of more than 10 letters used? (vastly reducing the attack surface of a dictionary attack).

Simple is an synonym for dumb – often an inevitable result of the simplification process.

Please note – I know Randall just drew a cartoon, not wrote a security manual. It’s a pity some of his fans don’t.

Apologies for any/all errors – an unavoidably rushed post.
Kind regards

TL;DR (Too Lazy;Duly Recalcitrant?) It’s hard. Anyone believing otherwise is deluding themselves.

Scott "SFITCS" Ferguson • August 24, 2014 5:58 AM

@MrC

@Clive


Third: The discussion regarding the true meaning of “random” seems to me completely beside the point. Those questions hang over EVERY use of “random” input in the same way and to the same degree. They are not specific to this particular password scheme.

I agree randomness is not “specific” to this particular password scheme (apropos of what?). Are you seriously suggesting that “the degree of difficulty in predicting the password” is not relevant (to any password scheme)??!!

I’d suggest it’s critical. Replace the difficult term “random” with “degree of unpredictability” and it may be easier to understand i.e. in this instance correcthorsebatterystable is being presented as “more random” (less predictable) than Tr0ub4dor$3.

NOTE: there are at least two other “non-random” factors that identify the passwords used in that scheme. I most certainly would employ them, in addition to the other four I mentioned previously, if I was tasked with breaking that password. I’d be surprised if many other readers of Bruce’s site didn’t spot them. As Clive points out (I’m paraphrasing) random may well be an illusion resulting from lack of context and perspective. Humans are predictable, and rarely are their ideas unique.

Example password attack strategy if nothing is known of the creator

While not successful do:-

  1. create list of variations used for brute force molecular sieve attack up to 6 characters
  2. create low hanging fruit list of variations for up to 6 characters
  3. try all the variations from list 2
  4. remove previous attempts from list 1
  5. try all the variations from list 1
  6. create list of variations used for brute force molecular sieve attack from 7 to 11 characters
  7. create low hanging fruit list of variations for 7 to 11 characters
  8. try all the variations from list 7
  9. remove previous attempts from list 6
  10. try all the variations from list 6
  11. rinse and repeat to 44 characters

And I’m a light-weight attacker who would simply filter english nouns and verbs between 5 and 7 characters of a low Fogg index from a dictionary list to use for a low-hanging fruit attack. All lower-case, with no reuse of any word as part of another word in the list. NOTE: just using a low Fogg index will reduce the dictionary list of english words to around 7000, using just the nouns and verbs further reduces the size of the list, removing reiterations will further reduce it (but may not be a good idea if a human was not choosing the words – a human will probably not use words containing similar patterns). I’m not sure how Randall arrived at 2.5 bits of entropy per character – perhaps he drew from a very small list of words (perhaps 2048 common words – to give 16 trillion possibles)? I’d have used a “partial knowledge” entropy calculation – 1 bit per letter for common words – if the password was a phrase or sentence the entropy is even lower e.g. Microsoft’s example of mydogsnameissandy and for a significant number of cases the ease of breaking it would be even lower (I’ve broken those with as little as a few hundred attempts). Reading many of the comments about the cartoon here and elsewhere it’s apparent that many don’t understand entropy is a measure not just of exhaustion (rather than what’s required to brute-force it), but that entropy is a measure of a what a password could have been rather than what it is (how large was the pool of possibilities it was chosen from). Entropy is only a value of worst-case (theoretical) difficulty to guess – converting it into probability, especially when psychology is used in the attack, is very difficult and unreliable.

As a password for actual use (rather than an example of how to create a memorable password with lower predictability than Tr0ub4dor$3) – provided your application will accept the length and lack of complexity it’s a “reasonably” secure password. Not “highly” secure. As was originally suggested here – it could/should be improved by the use of a capital letter and the addition of a number and/or other non-alpha/numeric character.
“It’s too hard to remember” is reason to learn memory techniques (or get a password manager/pen and paper) – not to weaken passwords. Consider that as a result of Randall’s comic (through no fault of Randall), and the terrible suggestion by MS to use a sentence, a lot of people can be relied on to be using passwords that will yield to dictionary attacks if they are using large passwords.

“…..xKcd1……………” is a (much) less predictable than “correcthorsebatterystaple”, being hard to remember means only that it’s not as friendly to poor security practices.

Given that the “average” person has more than a dozen passwords – relying on memory makes password reuse and weak passwords likely, and they are the main problems with what people are taking away from that comic (no fault of the cartoonist). Like many, I use hundreds of passwords – and I change them – so I hope you can see why relying on memory for more than a few key passwords is a Very Bad Thing©. For every “memorable” password that’s broken the security of the others is greatly reduced by a huge factor as you are likely to use the same, predicable, password creation policies for all.

All of which gives me an excuse to rail against the criminally naive morons who create applications and sites that don’t support password managers (especially when it’s deliberate e.g. hidden forms), and/or large, complex passwords. There is no excuse – you lower the standards, and the Yuppie Nuremburg defence is no defence (just following orders to pay the mortgage).


Fourth: I’m not convinced by your second point about never reusing words. In fact, I think I disagree. To me, it sounds akin to saying that, having once used a lowercase ‘c’ in a random alphanumeric password, I must never again use lowercase ‘c’.

It’s the difference between your password being predictable, and your passwords being predictable. Another example of convenience being the entry fee for lowered security. Don’t worry so much about the most likely attack (script kiddies), worry about an intelligent, targeted attack. Risk is only relevant when worse case outcome is factored in (how hard will it bite when you lose?).

If you reuse characters, in the same position, and those characters become known – the entropy of those characters become zero.

I look forward to Clive, and others, corrections to my logic, and expansions.

Kind regards

Useful references:- Relationship between password creation policies and strength, Randall’s comments, NIS formulas

Clive Robinson • August 24, 2014 7:07 AM

@ Scott,

With regards your closing example “random choice” of TL;DR for a word substitution I would venture that “Recumbent” would be a better substitution than “Recalcitrant” 😉

MrC,

First a little house keeping,

We are talking not of the XKCD cartoon, but the “XKCD method/system” that various others have built up around the cartoon (and missing the point of the jokes/barbs within the cartoon in the process). Nor are we talking of other systems that might be considered comparable, because all systems have failings and this will lead to conflation with the XKCD Method’s failings.

So to frame the system under discussion, my understanding of the mishmash of “method” interpretations of the “cartoon” is the following,

1, Find a “chance” selection process.
2, Somehow build a two thousand word list.

To make a password,

3, Use (1) to produce 4 pointers to the word list.
4, Pull and memorise the four words pointed to.

All of the above steps have multiple further interpretations most of which skate on thin ice at best when talking of security.

For instance (4) does not say anything about what “order to use” the memorize words in. Likewise it does not say which “order to pull words” from the list. Nor does (2) say anything about the ordering of the words in the list.

With regards you second point of “the user not being a compleat idiot”, it would be quite reasonable to expect a non security wise person to use the four words alphabetically or in an order they can build into a sentence to memorise them, even though they might have been initialy “Randomly” selected for the word list (2) or by the chosen chance method (3).

In doing this they are reducing the value of the presumed 44 bits of “entropy” in all manner of ways, of which the low water mark would be close to 4 x 2^11 or thirteen bits…

With regards your fourth point about the word list, it is important to notice that it’s actually a “code book” (decoding / expanding half).

If you look into code book history you will find they have all sorts of weaknesses, and most people with some security experiance would say “code book mode should never be used” as it’s the prevailing mantra for the reasons history has taught cryptographers. Which is why code books were relegated to the role of “compression” which was then followed by “super enciphermenent” by the likes of number OTPs. Finally code books were then dropped altogether when hand encipherment was relegated to times past in the 1950s by machine ciphers. Unfortunatly “when they threw out the bath water the baby went too” and the advantages of using such systems were likewise relegated to times past.

So you have to ask what does the code book priciple bring to the XKCD Method party, and what does it take away?

Well, firstly the obvious reason is to help a poor memory, as that appears to be the stated purpose. However as a code book if it is used correctly it adds “confusion” as a substitution cipher as well as providing more complexity if used correctly (polyalphabeticaly), which has the benift of decoupling the “chance” selection method from the output so represents an extra encryption stage that if used correctly can be considerably stronger than the presumed 44bits of the basic method.

In fact it could take the strength to the brut force value of four words from a full or larger dictionary which could be up around 64 bits. Which appears to be a point missed by all those describing their XKCD Method ideas.

But the important point is if used properly it is also a one way function between the chance selection method and the final password. This makes attacks against a weak “chance” selection method near to impractical. Which is the point of not using words twice or to represent the same value from the “chance” selection method.

Now I don’t know about you but I find those fairly easily obtained and used traits to be quite desirable, especialy if the “chance” selection process is of unknown probably very insecure quality.

Which brings us back to your third point of what you apparently see as pointless musings about the “chance” selection process. I’m sorry you see it that way, but I realy don’t have the faith you apear to have in most peoples abilities to find not the unknown and probably insecure “random” method, you think most people will use, but a “secure random” method which is needed for the majority of the degenerate versions suggested for the XKCD Method.

The best throw away consideration to this is “use diceware” but this does not say that there are good and not so good ways to do “diceware”, and most end up becoming not so good in the hands of those who don’t understand the underlying security aspects.

MrC • August 24, 2014 10:35 AM

Four thoughts:

  1. Thank you for the replies.

  2. Everyone around here seems to have much less esteem for the intelligence of the average person than I do. Not quite sure what to make of that…

  3. All of the responses in this thread so far have criticized the XKCD scheme on the basis of some sort of implementation mistake by the user (e.g., no random source, poor/insecure random source, reordering the words into alphabetical order, etc.) and perhaps also that such mistakes are too easy to make. This still leaves open the real question I want answered: Assume a perfect implementation; is there something fundamentally wrong with the underlying scheme?

  4. I have an inclination to answer “no” to #3 because (i) I cannot think of any fundamental problems, and (ii) no one’s suggested one in this thread. BUT Bruce’s prior comments sure sounded like he thought the answer was “yes.” He didn’t say a single word about the possibility/probability of poor implementations by the user. He did say, “[P]assword crackers are on to this trick.” The leaves me with the impression that he thinks there’s a fundamental flaw that opens up an attack that would work against any implementation (even a perfect one).

Clive Robinson • August 24, 2014 12:03 PM

@Mr C,

The answer to three is the number of equivalent bits of “unpredictability”. At best you are looking at 44bits.

Which given modern attacks is only just acceptable for an “uncritical” account (to say read newspapers).

However easy to make mistakes will quickly bring it to the low water mark of 13bits….

So no it’s not fit for purpose, that said few “memorable” systems are much better due to the artificial constraints applied by programers…

Clive Robinson • August 24, 2014 3:02 PM

@ Mr C,

With regards your point two,

I actually think you’ve got it the wrong way around, many of us have a healthy waryness of users intelligence.

In engineering there is a very old saying “Foolproof is easy, but there’s never a fool around”. That is your average user is far from being a fool / idiot / uninteligent, which makes them dangerous.

As Bruce and others have pointed out user incentives are misaligned. When it comes to a choice between meeting your boss driven targets or the CIOs security bleatings, you know which way the user is going to go. Thus they devote consideravle inteligence in developing short cuts arround, and removing security barriers, not just for themselves but their co-workers.

It’s a “no brainer” bread on the table today beats a possible job loss six months or more down the line after a possible security breach.

If organisations want security for real and not just for audit, then those at the very top have to “buy in” and align incentives accordingly. However if they are too draconian than the best employees will move on as only the unwanted time servers and dross will put up with the regime….

Winter • August 25, 2014 5:27 AM

This xkcd discussion is entertaining. So, lets take a few examples.

I am an idiot trying to think of four “random” words:

I look around:
Mirror, Clock, (coat) Hook, (power) Socket

What did I do yesterday:
Bus, Gorilla, Roller (case), Book

What will I cook tonight:
Pasta, Tunafish, Salat, Yoghurt

What did I watch yesterday:
Violin, Lady, Georgia (the country), Canal

Peronally, I have no idea what the strength of these combinations is. When I have to guess “Pasta Tunafish Salat Yoghurt” might be over 100 bits (it seems to max out online password checkers).

But that is just a naive guess.

Scott "SFITCS" Ferguson • August 25, 2014 6:49 AM

@Winter

This xkcd discussion is entertaining. So, lets take a few examples.


I am an idiot trying to think of four “random” words:


I look around:
Mirror, Clock, (coat) Hook, (power) Socket


What did I do yesterday:
Bus, Gorilla, Roller (case), Book


What will I cook tonight:
Pasta, Tunafish, Salat, Yoghurt


What did I watch yesterday:
Violin, Lady, Georgia (the country), Canal


Peronally, I have no idea what the strength of these combinations is. When I have to guess “Pasta Tunafish Salat Yoghurt” might be over 100 bits (it seems to max out online password checkers).

Using an online password checker is dangerous for two reasons:-

  1. If I wanted to harvest passwords I’d put up an online password checker….
  2. The result is wrong as the entropy value it uses is not relevant to your password

100 bits for is a lot higher than the actual entropy (by a large factor). There is difference between entropy and difficulty to guess. Entropy is a figure calculated from the size of the pool you made your choice from – in your example that’s a very small pool (low entropy). To convert that into a “difficulty to guess” figure presume two ranges: the first is the worst case for the attacker figure which presumes the attack has no low-hanging fruit shortcuts (insights into your password selection process)[*1]; the second presumes they do. You should be concerned by the second figure.

[*1] A significant percentage of people who use large passwords will use “memorable” passwords consisting of only words. An attacker that knows this means that your entropy is considerably reduced – the more they know (and make use of) the lower the entropy. When they “know” your password it’s entropy (total number of variations needed to exhaust all possibilities) is zero.
Oh course your attacker doesn’t know your password – but if they “assume” you’ve used English words (and you haven’t) your entropy is much lower than those online password checkers told you. They calculate a value as if your password was a nonsensical combination of printable characters (upper and lower case alphas, numbers, and other printable characters). If I knew your password consisted of just words both upper and lower case I’d have to try 48 variations for every character space – considerably less than the 256 variations your password checker assumes. If I knew what language/s you spoke I’d be trying word list of low Fogg index (simple words) – even less possible variations than if I simply brute-forced upper and lower case alpha combinations.


But that is just a naive guess.

Yes – but at least you recognise that. 🙂

What’s critical is context. If that’s your gmail password then it’s probably “secure enough” as there are a limited number of attack attempts possible. But if it’s to a web server where an attacker could steal the stored copy and crack it offline – then you would very quickly be screwed (millions of attempts per second).

First determine what you want to secure – then develop an appropriate security policy for it. There’s no such thing as a one-size-fits-all security policy.

Please note that having published your password process you should now not use it. Seriously – even if the attacker doesn’t match it to you personally – it increases the risk that someone will consider it when developing low-hanging fruit attacks. I suspect Randall’s “random” words were based on items in view of his desk – a professional attacker will consider this. Serious attack teams include behavioural psychologists and will investigate your life – paying special attention to what you were doing at the time you created a password. Word lists will be made from what you have written…

I “guess” the best security policy is one designed to prevent worst-case attacks – not script kiddies. If you want to hide something from professionals – don’t put it in the first place you think of – or the second. Humans are not as unique as we think – which is why when you here of two people “inventing” something at the same time you shouldn’t automatically think “one of them stole the idea” – history shows it’s generally not the case. You want to hide your password creation process – use the same strategy. Presume you are not unique, presume your first idea is often the same as the first idea of others.
If I was to make a somewhat educated guess I’d say your example password creation scheme was create mid-afternoon ;p

I hope that dense wall of screed is of interest.

Kind regards

Winter • August 25, 2014 6:56 AM

“But that is just a naive guess”

I did a simple word look up in Startpage, # of results (pages) for each word divided by # number of results for typing a single letter or “the” (~2 billion).

Then I get (based on document frequency):
Pasta ~ 5.6 bits
Tuna fish ~ 13.0 bits
Salat ~ 10.3 bits
Yogurt ~ 7.4

Total ~ 36

If we add the spaces, capitalization, and ordering, we get awfully close to 44 bits.

And this is based on the documents frequency, not the word frequency.

Winter • August 25, 2014 7:05 AM

@Scott “SFITCS” Ferguson
“First determine what you want to secure – then develop an appropriate security policy for it. There’s no such thing as a one-size-fits-all security policy.”

I know, a four character pin of a Pin&Chip card is something different from the hashed passwords in a downloaded password database.

Scott “SFITCS” Ferguson
“Please note that having published your password process you should now not use it.”

That is good advice I have always followed. Reader, beware. Be assured that none of these are anywhere near any password I use.

Google has indexed somewhere around a petabyte of the Internet. So if Google has indexed the source of your password, then your password has a strength of less than ~55 bit

Google stores all search terms. So, if you have searched your password, it most certainly has less than 55 bits strength.

AlanS • August 25, 2014 11:41 AM

@MrC

As Anura and DB have pointed out, the problem is the method for choosing the words. The calculations only work if the selection isn’t predictable.  In practice the entropy of a four word password is significantly less than 25000^4 because users are much more likely to use some words and very unlikely to use most of the words in the pool. “Might do it wrong” is a legitimate criticism because XKCD never explains how to do it right.

Also note that even XKCD only claims 44 bits of entropy for their ‘random’ four words which is only secure if you assume XKCD’s guess rate of a thousand guesses/sec. In practice, as Clive notes above, 44 bits is “only just acceptable for an ‘uncritical’ account”.  A minimum  billion guesses/second is a safer assumption for a critical account especially if one lacks reliable knowledge of how the passwords are stored. Most users appear to reason that no person could guess my password; they have no notion of attackers defining sequences of attack based on common patterns deduced from huge samples of user-generated passwords and GPUs zipping though those sequences at rates of billions of combinations a second.

Appendix A: Estimating Entropy and Strength in NIST SP800-63-2

“Experience teaches us that many users, left to choose their own passwords will choose passwords that are easily guessed and even fairly short dictionaries of a few thousand commonly chosen passwords, when they are compared to actual user chosen passwords, succeed in “cracking” a large share of those passwords.”

Linguistic properties of multi-word passphrases

“…our results suggest that users aren’t able to choose phrases made of completely random words, but are influenced by the probability of a phrase occurring in natural language. Examining the surprisingly weak distribution of phrases in natural language, we can conclude that even 4-word phrases probably provide less than 30 bits of security which is insufficient against offline attack.”

Winter • August 25, 2014 12:43 PM

@AlanS
Humans are indeed really bad at generating Semantically Unpredictable Sentences. That is why you should select “random” words first, and only then think of a sentence (where you can add words to make it fit).

And this is most definitely not intende for something that should withstand an offline attack.

Anura • August 25, 2014 6:53 PM

@AlanS

Well, 90% of my passwords I can generate randomly without worry, some of them I have to memorize like my office password. Luckily they have a reasonable policy that lends itself to strong passwords: 8 characters exactly, at least one upper, one lower, one number (and yes, I rolled my eyes very heavily when I saw that). So I go with a nonsensical but grammatically correct sentence made up usually of 6-7 words and a number, and take the first letter of each word, although I bet it can be cracked relatively easily. For passwords I have to type, but don’t necessarily need to memorize I go with a 6 word passphrase chosen from a list of 16384 4-5 letter words.

Erik Holmberg • September 4, 2014 1:23 PM

I think one of the problem with the xkcd method is that many website still hashes the passwords with the md5 algorithm. Since that algorithm is partially broken words can be guest one by on making the password trivial easy to brake regardless how many words are chosen.

Anura • September 4, 2014 2:42 PM

@Erik Holmberg

Weaknesses in MD5 cannot be exploited for the purpose of breaking passwords. The same offline attacks that work against MD5 work against SHA-512 as well (although SHA-512 is slower, that’s only a linear change in cracking time, and irrelevant if they are stored properly). The big problems with storage are 1) not salting the passwords, and 2) only hashing once.

If you use a sufficiently large random salt (8 bytes is probably fine, I usually do 16 because space is cheap), you block precomputation attacks (and prevent anyone from seeing that two accounts have the same password), forcing attackers to break each hash separately. If you use PBKD52 with a count of 1024 then it’s the same as if each password was 11 bits stronger than MD5 alone.

So if you are following best practices, and if you do MD5 and SHA-512 so they are both 100ms per hash, then it will probably not be any faster to crack the SHA-512 password over the MD5 password; that said, there’s no reason to use MD5 over SHA2, and for any new development you should use SHA2 as a matter of habit, even if there is no real advantage. Of course, memory bound password hashing functions hold up better against GPU based cracking, so it’s a good idea to use one of those.

Leave a comment

Login

Allowed HTML <a href="URL"> • <em> <cite> <i> • <strong> <b> • <sub> <sup> • <ul> <ol> <li> • <blockquote> <pre> Markdown Extra syntax via https://michelf.ca/projects/php-markdown/extra/

Sidebar photo of Bruce Schneier by Joe MacInnis.