Page 1 of 1

## 10 Replies - 1358 Views - Last Post: 19 November 2013 - 01:53 AM

### #1 Michael26

Reputation: 380
• Posts: 1,574
• Joined: 08-April 09

Posted 18 November 2013 - 01:50 PM

This is in reference to this
http://xkcd.com/936/

Can you explain the concept of entropy in password strength?
If you'll give me code snippets i don't really care for language, that is why i posted it here in Software development.

But my preferred languages are C, C++, C# or Java.
Is This A Good Question/Topic? 0

## Replies To: xkcd Password strength

### #2 andrewsw

• Well, I'll need some beer.

Reputation: 4998
• Posts: 19,001
• Joined: 12-December 12

Posted 18 November 2013 - 02:04 PM

Just for reference:

wiki said:

It is usual in the computer industry to specify password strength in terms of information entropy, measured in bits, a concept from information theory. Instead of the number of guesses needed to find the password with certainty, the base-2 logarithm of that number is given, which is the number of "entropy bits" in a password. A password with, say, 42 bits of strength calculated in this way would be as strong as a string of 42 bits chosen randomly, say by a fair coin toss. Put another way, a password with 42 bits of strength would require 2^42 attempts to exhaust all possibilities during a brute force search. Thus, adding one bit of entropy to a password doubles the number of guesses required, which makes an attacker's task twice as difficult. On average, an attacker will have to try half of the possible passwords before finding the correct one.[2]

wiki
The key thing initially is: "a password with 42 [entropy] bits of strength would require 2^42 attempts to exhaust all possibilities during a brute force search."

BTW Those are all the same language

This post has been edited by andrewsw: 18 November 2013 - 02:07 PM

### #3 modi123_1

• Suitor #2

Reputation: 10843
• Posts: 42,494
• Joined: 12-June 08

Posted 18 November 2013 - 02:07 PM

Information Entropy - how predictable (or un-) a chunk of data is. Entropy - in physics - is related to disorder... how to get this into thermodynamic equilibrium. Take that fuzzy concept and apply it back into information.. so things like a standard coin flip is more entropic than say one that is a weight bias to side. The pure random coin flip cannot be crunched, patterned, or broken down into smaller bits. .. unlike, say, a rigged game where the value is weighted. A pattern can, and will, emerge.

Take that and apply it to passwords.. passwords that can be quantified by either being in a dictionary, follow linguistic patterns, patterns for password types, etc.. so it's a measurement of the brute force method required crack the password.

https://en.wikipedia...ssword_strength
https://en.wikipedia...rmation_entropy

### #4 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11449
• Posts: 43,171
• Joined: 27-December 08

Posted 18 November 2013 - 02:33 PM

In Cryptography, you want high levels of entropy, as it means the cryptographic schema dilutes a lot of the structure of the plaintext. That is, you want the ciphertext to be as structurally close to random as possible. You can measure entropy using the formula H(X) = -\sum_{x \in X} Pr(x) log2(Pr(x)). You can compare the entropy of the ciphertext to the English language. If they are close, there is quite a bit of structure to the ciphertext, which means the system can be exploited by something like frequency attacks.

### #5 jon.kiparsky

• Pancakes!

Reputation: 8939
• Posts: 15,450
• Joined: 19-March 11

Posted 18 November 2013 - 04:00 PM

Quote

That is, you want the ciphertext to be as structurally close to random as possible.

Actually, this is not really a good strategy. It turns out that people are not very good at either remembering structurally random strings or typing them in if they're long enough for that randomness to do you any good. "Hard for humans to remember, but easy for computers to guess".

Consider the entropy of a ten-word sentence versus a ten-character random string. The number of ten-word English sentences is grotesquely larger than the number of 10-character strings over the alphabet of typeable characters, even if we limit ourselves to some ridiculously small number, like 1K words in the "English language". So let's suppose I tell you "My password is a meaningful sentence in English, ten words long, with standard capitalization and punctuation." What on earth are you going to do to exploit that structure?

Now think about whether it's easier to remember a meaningful ten-word sentence, or a ten-character random string. Or rather, whether it's easier to remember an arbitrarily large set of sentences or random strings, since that's the actual case you find yourself in.

On the back of my envelope, randomness loses on both of those tests.

EDIT: Or wait - are you still talking about passwords? Everything you say is true wrt crypto, of course, but doesn't really carry over to password selection.

This post has been edited by jon.kiparsky: 18 November 2013 - 04:01 PM

### #6 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11449
• Posts: 43,171
• Joined: 27-December 08

Posted 18 November 2013 - 05:25 PM

Quote

EDIT: Or wait - are you still talking about passwords? Everything you say is true wrt crypto, of course, but doesn't really carry over to password selection.

### #7 jon.kiparsky

• Pancakes!

Reputation: 8939
• Posts: 15,450
• Joined: 19-March 11

Posted 18 November 2013 - 05:44 PM

Yeah, after I posted I figured that was probably what had happened.

Michael26, the simplest way to think of entropy in this context is to consider physical entropy as measuring the "total disorder" of a system. That is, it's the number of states that system could be in. In terms of passwords, that amounts to "how many passwords does the attacker have to try before they hit on your password by chance?" A password which can be found in a dictionary has very low entropy, which is why you never pick a password from the dictionary.

This can be increased by increasing the size of the alphabet from which the passwords are drawn, by reducing the strength of any patterns in the passwords, or by increasing the length of the password. Munroe's comic is an argument that increasing the length of the password is the right solution, and I think he's right, although I would never use four random words in that fashion. "The horse kicked the aggressive mule, several times." is easy to remember, easy to type, and very hard to guess. Even if you know it's a grammatical sentence in English, there are an infinite number of those.

This post has been edited by jon.kiparsky: 18 November 2013 - 05:47 PM

### #8 Michael26

Reputation: 380
• Posts: 1,574
• Joined: 08-April 09

Posted 19 November 2013 - 01:00 AM

1 question.

Quote

"Hard for humans to remember, but easy for computers to guess".

Shouldn't that say "easy for humans to remember, but hard for computer to guess", it's the computer program that's doing the guessing and if its easy for computer to guess the you F*ed.

### #9 jon.kiparsky

• Pancakes!

Reputation: 8939
• Posts: 15,450
• Joined: 19-March 11

Posted 19 November 2013 - 01:43 AM

Michael26, on 19 November 2013 - 03:00 AM, said:

Quote

"Hard for humans to remember, but easy for computers to guess".

Shouldn't that say "easy for humans to remember, but hard for computer to guess", it's the computer program that's doing the guessing and if its easy for computer to guess the you F*ed.

Yes, your way is what we're going for. The phrasing I used came from the Munroe comic, and it describes the standard pseudo-obfuscations used in weak passwords (ie, l33t substitutions on dictionary words) and required by the terrible distribution enforcement systems (ie, "you must have one number and one non alphanumeric character and one capital letter and one devanagari ligature and two hiragana in your password"). Munroe's point in that comic is that those approaches produce great difficulty for human beings, but a computer hardly notices them - because forcing the user to add a "1" in front of their ordinary weak password doesn't add any noticeable degree of entropy, but it makes it harder for the human to remember exactly how the password went.

### #10 Michael26

Reputation: 380
• Posts: 1,574
• Joined: 08-April 09

Posted 19 November 2013 - 01:49 AM

Quote

(ie, "you must have one number and one non alphanumeric character and one capital letter and one devanagari ligature and two hiragana in your password").

Don't forget the blood of the virgin

### #11 jon.kiparsky

• Pancakes!

Reputation: 8939
• Posts: 15,450
• Joined: 19-March 11