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

#1 Michael26  Icon User is offline

  • DIC-head, major DIC-head
  • member icon

Reputation: 359
  • View blog
  • Posts: 1,529
  • Joined: 08-April 09

xkcd Password strength

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  Icon User is online

  • Fire giant boob nipple gun!
  • member icon

Reputation: 3517
  • View blog
  • Posts: 12,008
  • Joined: 12-December 12

Re: xkcd Password strength

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

Was This Post Helpful? 1
  • +
  • -

#3 modi123_1  Icon User is online

  • Suitor #2
  • member icon



Reputation: 9277
  • View blog
  • Posts: 34,780
  • Joined: 12-June 08

Re: xkcd Password strength

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
http://forums.xkcd.c...4b060bbc77ad2fe
Was This Post Helpful? 1
  • +
  • -

#4 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10595
  • View blog
  • Posts: 39,252
  • Joined: 27-December 08

Re: xkcd Password strength

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.
Was This Post Helpful? 2
  • +
  • -

#5 jon.kiparsky  Icon User is offline

  • Pancakes!
  • member icon


Reputation: 7805
  • View blog
  • Posts: 13,199
  • Joined: 19-March 11

Re: xkcd Password strength

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

Was This Post Helpful? 0
  • +
  • -

#6 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10595
  • View blog
  • Posts: 39,252
  • Joined: 27-December 08

Re: xkcd Password strength

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.

I was talking about crypto. I misread the OP, thinking it was related to hashing passwords.
Was This Post Helpful? 0
  • +
  • -

#7 jon.kiparsky  Icon User is offline

  • Pancakes!
  • member icon


Reputation: 7805
  • View blog
  • Posts: 13,199
  • Joined: 19-March 11

Re: xkcd Password strength

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

Was This Post Helpful? 1
  • +
  • -

#8 Michael26  Icon User is offline

  • DIC-head, major DIC-head
  • member icon

Reputation: 359
  • View blog
  • Posts: 1,529
  • Joined: 08-April 09

Re: xkcd Password strength

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.
Was This Post Helpful? 0
  • +
  • -

#9 jon.kiparsky  Icon User is offline

  • Pancakes!
  • member icon


Reputation: 7805
  • View blog
  • Posts: 13,199
  • Joined: 19-March 11

Re: xkcd Password strength

Posted 19 November 2013 - 01:43 AM

View PostMichael26, 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.
Was This Post Helpful? 0
  • +
  • -

#10 Michael26  Icon User is offline

  • DIC-head, major DIC-head
  • member icon

Reputation: 359
  • View blog
  • Posts: 1,529
  • Joined: 08-April 09

Re: xkcd Password strength

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 ;)
Was This Post Helpful? 1
  • +
  • -

#11 jon.kiparsky  Icon User is offline

  • Pancakes!
  • member icon


Reputation: 7805
  • View blog
  • Posts: 13,199
  • Joined: 19-March 11

Re: xkcd Password strength

Posted 19 November 2013 - 01:53 AM

You're right - essential for real security.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1