0936: "Password Strength"

This forum is for the individual discussion thread that goes with each new comic.

Moderators: Moderators General, Prelates, Magistrates

morriswalters
Posts: 6904
Joined: Thu Jun 03, 2010 12:21 am UTC

Re: 0936: "Password Strength"

Postby morriswalters » Fri Aug 25, 2017 3:37 pm UTC

orthogon wrote:
Eebster the Great wrote:... a many-to-one hash actually decreases entropy.

... and moving doubled letters to the end is, at least in principle, a many-to-one process. I was trying to think of some examples where it produces a collision, but in the end I had to revert to regular expressions.

Spoiler:

Code: Select all

me@mymachine:~$ sed -e 's/\(.*\)\(.\)\2\(.*\)/\1\2\3\2/g' /usr/share/dict/british-english |sort | uniq -d
basis
casinos
crepe
deserts
discrete
else
mete
mono
Moro
mouses
musings
Pele
polo
poses
Sara
sere
tense
these
verse
were

Some of the results are a bit dodgy, but some clearly cromulent word-pairs that collide are:
crepe<->creep
deserts<->dessert
discrete<->discreet
else<->eels
mete<->meet
mono<->moon
polo<->pool
poses<->posse
verse<->veers

My regex can only move one doubled letter to the end. I tried to make it do it repeatedly, but it gets stuck in an infinite loop once there's a tripled letter at the end. I tried to get around that using negative lookahead, but gnu sed doesn't seem to support that.
I see you. And you make a great point. Many eyes, right? New rule. Replace any duplicates with a letter not currently in use. And if it helps you see clearer, place them all at the end. Here is the game that I'm playing. Wherever I look, I desire that it look like everywhere else. The mistake I made was missing a symmetry. I removed this condition with that change in the rule. It doesn't mean that their aren't symmetries I still don't see. And I tell you there are.

Here is what I think I'm reading when I read about this. The safest any string can be is limited by the number of unique elements. Choosing letters gives you 26 unique tokens, and in this case 26 things taken 24 at a time. Their are only 12 cases possible for doubles. The endpoints are,all blank text, to all doubles. The passwords are all the words that could be written using 24 characters while never repeating. Minus those 12 cases. Here is how I view that. What you are hiding with a hash is the first member. If you break the hash you've identified one point. If you have that point you can figure out any password, since you now know the order. Is this close?

User avatar
PM 2Ring
Posts: 3619
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Mid north coast, NSW, Australia

Re: 0936: "Password Strength"

Postby PM 2Ring » Fri Aug 25, 2017 5:12 pm UTC

@morris
But why do you want to eliminate doubled letters? All else being equal, the total number of passwords when doubles are allowed is larger than the total number of passwords with doubles banned. So eliminating doubles makes password generation more complex and makes it easier to crack the passwords, a lose-lose situation.

KnightExemplar
Posts: 5489
Joined: Sun Dec 26, 2010 1:58 pm UTC

Re: 0936: "Password Strength"

Postby KnightExemplar » Fri Aug 25, 2017 5:50 pm UTC

morriswalters wrote:Here is what I think I'm reading when I read about this. The safest any string can be is limited by the number of unique elements.


You're wrong on multiple counts. If the underlying hash is SHA 256, the safest any string can be is limited to the 128-bit birthday attack. The 128-bit Birthday attack is the bottleneck in practice.

Reaching 128-bits is not a very hard problem technically. "Simply" memorize a perfectly randomized sequence of eight Unicode16 characters and you've achieved 128-bits.

The problem is that most people can't memorize eight perfectly random Unicode16 characters (or 19 perfectly random 7-bit ASCII characters). Especially when you add symbols and other such stuff to the matter. The question of password strength is to figure out memorization tricks to allow Humans to achieve the greatest amount of entropy with the least amount of effort memorizing.

-------------

Again, it is far more important to make sure that the human can easily memorize a secret. So if you wanted to improve the security of say "Correct Horse Battery Staple", perhaps you should extend the words into a full sentence. Such as:

"If you give the correct horse a battery, it will return to you a staple." (comma and period are included as part of the password). This method gives far more entropy, its way easier to type and way easier to memorize. Your minimum entropy is the four words chosen by diceware (51-bits). And roughly English has 0.75 bits of entropy per character, so the other characters give you around 33ish more bits of entropy (that's an improvement of 8589934592x). 84-bits still gives some room for improvement, but we're at least making progress to our goal.

Playing with methodologies that only improve password generation by 24x (lol 4.5ish bits) is... weaksauce. We measure password strength in terms of bits, and our aim is 128-bits if at all possible. Maybe 64-bits if the underlying system is using MD5 (a 128-bit hash)
First Strike +1/+1 and Indestructible.

User avatar
ucim
Posts: 5568
Joined: Fri Sep 28, 2012 3:23 pm UTC
Location: The One True Thread

Re: 0936: "Password Strength"

Postby ucim » Fri Aug 25, 2017 6:32 pm UTC

In terms of the "easy to remember" part, there's no advantage to altering words. In fact, there's a disadvantage; you have to in addition remember the alteration.

In terms of the "hard to crack" part, this depends on the number of tokens available, and the number of tokens used. The more, the better. But don't make the mistake of thinking of "things that look like tokens" and "actual tokens". The tokens in the "correcthorsebatterystaple" password are words selected from a dictionary (of maybe 70,000). "correct" is ONE token, not seven. Altering the token doesn't change the fact that it is still ONE token.

Characters are each one token (out of maybe 80) so you need more of them to reach the same entropy. But treating words as strings of characters is a mistake, because there are so many strings of characters that are not words, and are thus excluded from the search set.

And in both cases, the resulting password needs to be made from a randomly selected set of tokens. A random four word sentence has much lower entropy than four random words. A second password chosen from the same 70,000 dictionary will have much higher entropy than a second password chosen from the fifteen words from which you made your "master password loop".

Jose
Order of the Sillies, Honoris Causam - bestowed by charlie_grumbles on NP 859 * OTTscar winner: Wordsmith - bestowed by yappobiscuts and the OTT on NP 1832 * Ecclesiastical Calendar of the Order of the Holy Contradiction * Please help addams if you can. She needs all of us.

KnightExemplar
Posts: 5489
Joined: Sun Dec 26, 2010 1:58 pm UTC

Re: 0936: "Password Strength"

Postby KnightExemplar » Fri Aug 25, 2017 6:42 pm UTC

ucim wrote:In terms of the "easy to remember" part, there's no advantage to altering words. In fact, there's a disadvantage; you have to in addition remember the alteration.

In terms of the "hard to crack" part, this depends on the number of tokens available, and the number of tokens used. The more, the better. But don't make the mistake of thinking of "things that look like tokens" and "actual tokens". The tokens in the "correcthorsebatterystaple" password are words selected from a dictionary (of maybe 70,000). "correct" is ONE token, not seven. Altering the token doesn't change the fact that it is still ONE token.

Characters are each one token (out of maybe 80) so you need more of them to reach the same entropy. But treating words as strings of characters is a mistake, because there are so many strings of characters that are not words, and are thus excluded from the search set.

And in both cases, the resulting password needs to be made from a randomly selected set of tokens. A random four word sentence has much lower entropy than four random words. A second password chosen from the same 70,000 dictionary will have much higher entropy than a second password chosen from the fifteen words from which you made your "master password loop".


People recommend the Diceware list. EFF makes a strong case to use the EFF list instead.

Here's the EFF's list: https://www.eff.org/files/2016/07/18/ef ... rdlist.txt

In any case, these lists are organized in terms of 5 dice rolls. For example, if you roll "11111", you get "abacus". That's 6^5 entropy from each word, or roughly 12.9 bits per word.

So the "dictionary size" is only 7776.
First Strike +1/+1 and Indestructible.

morriswalters
Posts: 6904
Joined: Thu Jun 03, 2010 12:21 am UTC

Re: 0936: "Password Strength"

Postby morriswalters » Fri Aug 25, 2017 7:08 pm UTC

KnightExemplar wrote:You're wrong on multiple counts.
Okay. All I've said is that there are 26 unique alphabetic characters. And that every possible combination of those characters is unique. That is that their are 26 things taken 26 at a time and that with this set their are no duplicates. In this case n=r

Image=
Image

If you aren't talking about this, then we aren't talking about the same thing.

P(26,26) = 4.032914611266057e+26
P(52,52) = 8.06581751709439e+67
P(128,128) = 3.856204823625808e+215

The calculator crapped out with this
P(256,256) = Infinity

KnightExemplar
Posts: 5489
Joined: Sun Dec 26, 2010 1:58 pm UTC

Re: 0936: "Password Strength"

Postby KnightExemplar » Fri Aug 25, 2017 7:13 pm UTC

morriswalters wrote:
KnightExemplar wrote:You're wrong on multiple counts.
Okay. All I've said is that there are 26 unique alphabetic characters.


Your math is right.

Your assumptions are wrong. Particularly this one:

Here is what I think I'm reading when I read about this. The safest any string can be is limited by the number of unique elements.


The "bottleneck" of modern passwords is the 128-bit birthday attack. Which means the safest any string can be is limited to 128-bits of entropy (assuming a SHA-256 underlying). In essence, you are optimizing for a problem that doesn't exist. There are a myriad of simple ways to get to 128-bits of entropy, but the problem is that the human can't memorize them easily.

The discussion problem of this comic, and of the greater cryptographic community, is about memorization methodologies. Because the human brain is the bottleneck in practice. And your methodology does not seem to make the human have an easier time at all.

If you aren't talking about this, then we aren't talking about the same thing.


Indeed, we are not talking about the same thing. I'm trying to get you to switch over to my method. Your innate assumption of limitations is already a mistake. Its not so much that your math is wrong, its that your math is nonsense. You are calculating something that has no application to password complexity.

With that said, let me play along for a second. P(26, 26) is indeed a large number. But do you know what's an even larger number?

26 to the power of 26: 6.1561195802071573107966742884002e+36

You are removing duplicate letters, which is decreasing entropy. Allowing duplicates is 26^26, which is provably a much larger space than your "non-duplicate" based methodology. 26 random letters (duplicates allowed) is 26^26, which is provably larger than 26-permute-26. I mean, it should be obvious: 26 x 25 x 24... x 3 x 2 x1 is much much smaller than 26 x 26 x 26 x 26 x 26...

Even then, the methodology of improving entropy-per-character is kinda worthless if the human can't memorize it. Your P(26, 26) "No repeats" password of 4.032914611266057e+26 size looks like: jsowykzvpdhmcqrtuxibegnlfa

Which is really, really hard to memorize. It has 88-bits of entropy, so to beat that, I need a Diceware password of size 7. I went to here and generated a random password of size 7 (which has 90.3 bits of entropy, almost the same as your P(26, 26)).

So there's your two choices. Do you think "Salvage Ground Divinity Trowel Tipped Playmate Rectangle" is easier to memorize, or would you rather try to memorize "jsowykzvpdhmcqrtuxibegnlfa"??

For whatever damn reason, we humans are better at memorizing words than we are at memorizing random strings of letters, even if those random letters are much shorter. Therefore, humans should focus on memorizing longer passwords with more full words in them (at least, until people find a better memorization technique)
First Strike +1/+1 and Indestructible.

xtifr
Posts: 300
Joined: Wed Oct 01, 2008 6:38 pm UTC

Re: 0936: "Password Strength"

Postby xtifr » Fri Aug 25, 2017 8:29 pm UTC

I really have to ask at this point: morriswalters, do you believe that doubled letters in a password somehow means that there are doubled characters in the final hash which actually gets stored? Or even that the length of the final hash is in any way related to the length of the password?
"[T]he author has followed the usual practice of contemporary books on graph theory, namely to use words that are similar but not identical to the terms used in other books on graph theory."
-- Donald Knuth, The Art of Computer Programming, Vol I, 3rd ed.

morriswalters
Posts: 6904
Joined: Thu Jun 03, 2010 12:21 am UTC

Re: 0936: "Password Strength"

Postby morriswalters » Fri Aug 25, 2017 9:07 pm UTC

xtifr wrote:I really have to ask at this point: morriswalters, do you believe that doubled letters in a password somehow means that there are doubled characters in the final hash which actually gets stored? Or even that the length of the final hash is in any way related to the length of the password?
That's is a very good question, and the answer is no. I'm talking about passwords. I will say that if there is a pattern in the password, I can attack the hash. I don't need to beat the hash, I need to beat the password. I'll also say that the only patterns I'm interested in is ones that look different than anything else.
KnightExemplar wrote:So there's your two choices. Do you think "Salvage Ground Divinity Trowel Tipped Playmate Rectangle" is easier to memorize, or would you rather try to memorize "jsowykzvpdhmcqrtuxibegnlfa"??
I don't rely on memory. It's unreliable. Despite what you and anybody thinks about it. I talk about what I know. Permutations and combinations. Now when I gave you a rule and said that in Randall's passwords I would remove all double letters, what I said I was that doing was stealing edges for a hacker to find. Here is what that means. And I've said it once already. He has nothing to look at.

When I moved above 26, I threw away the alphabet and found a set constructed like the alphabet, with 52 unique characters.

This is a normal number. And this is the point I'm moving towards.
Intuitively this means that no digit, or (finite) combination of digits, occurs more frequently than any other, and this is true whether the number is written in base 10, binary, or any other base.


What I say is, that given this number, the probability of him getting my first letter is 1/P(26,26) = 4.032914611266057e+26. What I will furthermore say, is that I can write it down and tape it to my desk and tell you what it is. If I don't tell you where to start the search your chances of finding any number is that probability for every letter you search. At n=1 Those are the chances of your first guess. There are 26! combinations that start with 1. You have to do that 26 times and you have to get every character right when you test.

There is a theorem for this.
PM 2Ring wrote:But why do you want to eliminate doubled letters? All else being equal, the total number of passwords when doubles are allowed is larger than the total number of passwords with doubles banned. So eliminating doubles makes password generation more complex and makes it easier to crack the passwords, a lose-lose situation.
gmalivuk made that point, and it is correct.

Here is Randall's password in my mind. I know it's four words. And I know that he allows double letters. I construct passwords to feed to the hash. There are 12 edges possible. So I create a list of all words with double characters. I make an assumption. No word is longer than than 21 and no word shorter than 3. that set is finite and small. If you use those numbers that hash can be broken given the data available. Assuming that someone uses double letters. Do you understand how I've constructed it? I may be blowing smoke here. I know zero about encryption, give or take.

KnightExemplar
Posts: 5489
Joined: Sun Dec 26, 2010 1:58 pm UTC

Re: 0936: "Password Strength"

Postby KnightExemplar » Fri Aug 25, 2017 9:54 pm UTC

morriswalters wrote:I don't rely on memory. It's unreliable.


Why are you talking about passwords then?

A key requirement of a password is that its human-used. If the human is out of the picture, then we use things like private keys for security, and these can be as arbitrarily long or complicated as you want. Case in point, your web browser in "HTTPS" mode uses a method of encryption that has 2048-bits.

The thing about passwords is that they're a form of human derived security. They will always be weaker than say a private key for a bitcoin wallet. But they are necessary as a human-only method of authentication. If you can leverage a non-human source of authentication, there are many more powerful methods that exist.

I know zero about encryption, give or take.


Please realize that you're talking to people in this thread who do know about encryption. As stated earlier, a major problem is that you're not understanding the scope of the problem.

Again: Passwords are used because humans need an authentication methodology without any reliance on a computer or notebook. If you can rely on a computer, then use private keys, digital certificates, or a myriad of other methods. Those are much more secure (assuming your computer hasn't been hacked)

----------

As for your words / argument in particular, the paragraph you wrote makes virtually no sense at all. Attackers don't attack the way you think they do, defenders don't choose words the way you think they do. Case in point:

I make an assumption. No word is longer than than 21 and no word shorter than 3. that set is finite and small


The word-list that defenders use is exactly 7776 long. Here it is. You don't need to do any dictionary analysis or word analysis, or anything at all. Just use the 7776-long dictionary. The end. Attackers can pull these words from the list, and can safely assume that the defender is only using words from this list.

Despite that innate assumption: a human can memorize 7ish words from that list and this methodology can lead to a reasonable amount of security.

Randall is assuming 11-bits of entropy in his dictionary of 4-random words. This means that the set is of size 2048, and is even easier than the methodology I described with the EFF's wordlist.

This method is designed to be memorizable first and foremost. Because if we could use memory-devices (aka: computers or pieces of paper), there are WAAAAYYYYY more secure methods than passwords.
First Strike +1/+1 and Indestructible.

xtifr
Posts: 300
Joined: Wed Oct 01, 2008 6:38 pm UTC

Re: 0936: "Password Strength"

Postby xtifr » Sat Aug 26, 2017 12:06 am UTC

morriswalters wrote: I will say that if there is a pattern in the password, I can attack the hash.

This is incorrect. At least, with a cryptographically strong hashing algorithm.

I don't need to beat the hash, I need to beat the password.

This is correct. But if you think the hash is going to provide any partial information along the way, you're wrong. Changing a single bit in the password will change an unknown and unpredictable number of bits in the final hash.

This may be enlightening:

Code: Select all

$ echo a > tt
$ sha256sum tt
87428fc522803d31065e7bce3cf03fe475096631e5e07bbd7a0fde60c4cf25c7  tt
$ echo A > tt
$ sha256sum tt
06f961b802bc46ee168555f066d28f4f0e9afdf3f88174c1ee6f9de004fc30a0  tt

I literally changed one bit in my input, and the sha256s I got back bore no resemblance to each other.

Here is Randall's password in my mind. I know it's four words. And I know that he allows double letters. I construct passwords to feed to the hash. There are 12 edges possible. So I create a list of all words with double characters. I make an assumption. No word is longer than than 21 and no word shorter than 3. that set is finite and small. If you use those numbers that hash can be broken given the data available. Assuming that someone uses double letters. Do you understand how I've constructed it? I may be blowing smoke here. I know zero about encryption, give or take.

I don't know what sort of "edge" you think you're looking for, but you're not going to identify any edges in the hash. You can't find individual words. You can't break the problem down into subsets. Changing a single bit in the input causes an unknown and unpredictable number of bits in the hash to change. You can't check to see if "battery" is in the hash if the thing that's being hashed is "correcthorsebatterystaple". Because a whole lot of bits are different.
"[T]he author has followed the usual practice of contemporary books on graph theory, namely to use words that are similar but not identical to the terms used in other books on graph theory."
-- Donald Knuth, The Art of Computer Programming, Vol I, 3rd ed.

morriswalters
Posts: 6904
Joined: Thu Jun 03, 2010 12:21 am UTC

Re: 0936: "Password Strength"

Postby morriswalters » Sat Aug 26, 2017 2:12 am UTC

xtifr wrote:This is incorrect. At least, with a cryptographically strong hashing algorithm.
Your right. But if all you send is a password, and you get foolish and send that phrase I believe it could be found. Some one will use hello, bellow, mellow, and yellow for instance. I'm not looking for everything, I'm looking for things I might find. It's as much about the user as his password. And just for clarity, gmalivuk already pinned me and made me say uncle.
KnightExemplar wrote:The word-list that defenders use is exactly 7776 long. Here it is. You don't need to do any dictionary analysis or word analysis, or anything at all. Just use the 7776-long dictionary. The end. Attackers can pull these words from the list, and can safely assume that the defender is only using words from this list.
You are so busy thinking I'm misguided that you seem not to be able to see this as what it is. I don't need to remember anything. This is Randall's idea twisted to suit me.

Here it is. It would look better with a mono spaced font. And I would stack it 24 high. Swap the first and second letter and go again. Each password is unique. 6 passwords. Written down. In plain sight Run through the set of 26 stacked 24 tall. When you get to the end, turn ring one clockwise by one point and start again. Do nothing else. 26 more, still unique. Moving along the first row you can generate 624 passwords. All of them unique. Your guess is better than mine, as to what happens when you run a hash on it. It might come up all 1's or make the hash periodic, make it trivial to break, tilt or otherwise make me look foolish, but all those passwords are unique. :D I think.

1 2 3 4 5 6 7 8 9 0............................24 26
a b c d e f g h i j k l m n o p q r s t u v w x y z
z a b c d e f g h i j k l m n o p q r s t u v w x y
y z a b c d e f g h i j k l m n o p q r s t u v w x
x y z a b c d e f g h i j k l m n o p q r s t u v w
w x y z a b c d e f g h i j k l m n o p q r s t u v
v w x y z a b c d e f g h i j k l m n o p q r s t u

User avatar
Soupspoon
You have done something you shouldn't. Or are about to.
Posts: 2486
Joined: Thu Jan 28, 2016 7:00 pm UTC
Location: 53-1

Re: 0936: "Password Strength"

Postby Soupspoon » Sat Aug 26, 2017 2:43 am UTC

morriswalters wrote:Here it is. It would look better with a mono spaced font.

Use the "code" tag...

Code: Select all

1 2 3 4 5 6 7 8 9 0............................24   26                 
a b c d e f g h i j k l m n o p q r s t u v w x y z
z a b c d e f g h i j k l m n o p q r s t u v w x y
y z a b c d e f g h i j k l m n o p q r s t u v w x
x y z a b c d e f g h i j k l m n o p q r s t u v w
w x y z a b c d e f g h i j k l m n o p q r s t u v
v w x y z a b c d e f g h i j k l m n o p q r s t u


(Although I don't get your point, anyway... No new point, unchallenged, that is.)

User avatar
ucim
Posts: 5568
Joined: Fri Sep 28, 2012 3:23 pm UTC
Location: The One True Thread

Re: 0936: "Password Strength"

Postby ucim » Sat Aug 26, 2017 3:35 am UTC

morriswalters wrote:And I know that he allows double letters [...] So I create a list of all words with double characters.
...and that list doesn't help you unless you know that all the words in his password use double letters. If double-letter words are required, then you can limit your search space (to only those words). But if double-letter words are merely permitted, you cannot.

And if double-letter words are prohibited, you can also limit your search space. When words are the tokens, the letters don't matter.

morriswalters wrote: But if all you send is a password, and you get foolish and send that phrase I believe it could be found.
If you intercept the password, and it's sent in plain text (like a non-https site, like xkcd itself), then you have the password. You're done. If you don't intercept the (non https) password, then I don't see what you are going on about.

And if the site is https, then the browser encrypts everything that is sent its own way, and sends the encrypted part.
Spoiler:
...and assuming the site treats passwords properly (which some sites don't), the database doesn't hold the password, it holds a hash, done a known way. Upon receiving the password from a login attempt, the site hashes it the same way and compares the hash with what's in the database. The (plain text) password is not in the database at all. Unless the site is dumb.
morriswalters wrote:...but all those passwords are unique.
Yes, and? I'm not sure why you are going on about, unless the claim is that you have a password generation tool that generates 624x26=16224 unique passwords.

This would be trivial to crack, because if I know the system, I know what those passwords are. I just don't know which one you're using. I can let a bot just try them all.

But in any case, that's not how passwords are (typically) stolen.

Jose
Order of the Sillies, Honoris Causam - bestowed by charlie_grumbles on NP 859 * OTTscar winner: Wordsmith - bestowed by yappobiscuts and the OTT on NP 1832 * Ecclesiastical Calendar of the Order of the Holy Contradiction * Please help addams if you can. She needs all of us.

morriswalters
Posts: 6904
Joined: Thu Jun 03, 2010 12:21 am UTC

Re: 0936: "Password Strength"

Postby morriswalters » Sat Aug 26, 2017 3:51 am UTC

Soupspoon wrote:(Although I don't get your point, anyway... No new point, unchallenged, that is.)
There is no point. I see all of these things and think about them. Some of my ideas are foolish. Others aren't. Today I got schooled on hashes and passwords. I will read more. I won't ever understand some things completely, but I'll get a glimpse. That enough. Right now I'm trying to understand if uniqueness is meaningful in this regime. The question explicitly becomes, is the password I generate in the way that I do it, at least as secure as Randall's? Not is it perfect? Right now the score is uniqueness zero, and random words one. If I start using passwords made of four words, I won't worry about the words.

And I get nuggets. You just gave me one. However since no bank lets me use these types of passwords the issue is moot. I use a password manager and limit my exposure.

However my device has a name. It's called a Jefferson Disk.
Image

User avatar
Soupspoon
You have done something you shouldn't. Or are about to.
Posts: 2486
Joined: Thu Jan 28, 2016 7:00 pm UTC
Location: 53-1

Re: 0936: "Password Strength"

Postby Soupspoon » Sat Aug 26, 2017 12:14 pm UTC

As long as you're not trying to claim it's now two-factor verification by being "something you know, plus something that you have…" Which it won't be.

Maybe you want to see also https://en.wikipedia.org/wiki/Vigenère_cipher (that seems to be where you are heading in your enthusiastic learning curve). I think you're on a wild-goose chase if you think this is useful to your "simplify the human password memorisation, but complicate its automated breaking" plan, but there's still a lot of interesting things out there (Playfair, etc) that are interesting even if not any help with passwords. The most useful transform you could apply, however is a ROT26. A TripleROT26 if possible!

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 25789
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: 0936: "Password Strength"

Postby gmalivuk » Sat Aug 26, 2017 2:48 pm UTC

morriswalters wrote:Right now I'm trying to understand if uniqueness is meaningful in this regime.
Uniqueness of what? Randall's password doesn't work based on individual characters, but on words chosen randomly from a list. Those words have to be unique (i.e. each appearing only once on the list), but the letters in them don't.

As I mentioned before, your list could be nothing but different misspellings of the word "battery". If each letter can be used 1-4 times, so you have everything from "batery" to "bbbbaaaatttteeeerrrryyyy", then your list of "words" has 4096 elements and four randomly chosen words in a row gives you 48 bits of entropy instead of only 44.

That would be a stupid way to do it, obviously, because remembering how many of each letter you have ends up meaning you remember sequences of numbers (111111 to 444444, with the actual correct spelling being 112111), and if you're memorizing numbers anyway, just use a passcode that comes from all 10 digits and get the same security in a string of length 15.

The only advantage of Randall (and Diceware and EFF)'s method is that the resulting passwords are easier to remember than equally strong passwords where the individual characters are random. It's just an idiosyncrasy of the brain that we're better at remembering random words from a set of 10,000 than we are at remembering random 4-digit sequences of numbers, especially once we start putting several in a row. If you don't care about memorizing, then the passphrase method described in the comic is not necessary as part of your personal security practices.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

morriswalters
Posts: 6904
Joined: Thu Jun 03, 2010 12:21 am UTC

Re: 0936: "Password Strength"

Postby morriswalters » Sat Aug 26, 2017 3:27 pm UTC

gmalivuk wrote:Uniqueness of what?
In terms of permutations and combinations each 24 character string that I suggest never repeats. Ever. I am simply numbering the combinations. I have already accepted your argument. I'm getting the feeling that people don't believe or understand that. On another note, can you point me to some sources that will let me use Tex so I can generate expressions when I post. Here or in PM if you will.
Soupspoon wrote:As long as you're not trying to claim it's now two-factor verification by being "something you know, plus something that you have…" Which it won't be.
I get tickled to no end here. When I hire a plumber I do so because he knows plumbing. I don't. When he works I ask questions. He answers because he likes to talk. He tells me it doesn't work the way I thought it did, or he says, you got it. When he gets tired of me he starts to ignore me. What I never do, is put a plumbers sign on my car and offer up services. :lol:

I'm a college dropout. I made my living working on the things engineers create. And I understand those things. On those things I make claims. You tell me what pressure water you want on the 21st floor of a residential high rise and I'll tell you how to do it. And then I'll tell you who you need to get it designed. I understand my limitations. In the midst of another discussion with someone I posted exactly what I have taken in school and when I last used it. So when I tell someone that I'm using arithmetic or geometry I mean precisely that. This whole discussion I've talked about permutations and combinations, and I said as much.

Here is all I understand about this. When someone goes to crack my password I want him to spend so much time trying, that it costs more than what I have that could be stolen. I've actually said this another way in another argument. I want him to look at the sky and I want him to have to look at every star in the sky to find mine. And I have one other question that I have given up on. How is hello different then abcde. gmalivuk answered the question, why is Randall's method secure. My point was that I thought that double letters reduce the search space. The consensus seems to be no. Or that after a certain point it doesn't matter. Everything else is playing with numbers.

Later

User avatar
ucim
Posts: 5568
Joined: Fri Sep 28, 2012 3:23 pm UTC
Location: The One True Thread

Re: 0936: "Password Strength"

Postby ucim » Sat Aug 26, 2017 4:37 pm UTC

morriswalters wrote: And I have one other question that I have given up on. How is hello different then abcde.
The relevant way in which it is different depends on what they "mean", and in the context of passwords it involves the rules of construction for those strings.

If the strings are chosen from a pre-defined list of words (where both "hello" and "abcde" are in that list), then they are equivalent: each is equally likely to be chosen at random.

If the strings are constructed with a random letter generator, then again, they are equivalent. Each is equally likely. The chance of the first 'l' in "hello" is 1/26, and the chance of the second 'l' in "hello" is also 1/26. The chance of any given letter in any given slot is 1/26. There are 26^5 possible five letter strings.

If the strings are constructed with a random letter generator that rejects duplicate letters, then "hello" is impossible. After removing all the other impossible strings, you would be left with 26!/21! possible strings for the hacker to try (which is less than 26^5, so the hacker's job is easier).

Now, there's one very important kicker in all this: hackers do not stab randomly, because they know people aren't random. There are lists of the most common passwords (here's one) and those strings will be tried first. People like to use words, so a dictionary attack (including foreign words) will be tried next. There are several common alteration methods that people use (substituting 0 for o, misspelling, adding a 1 at the end...), these will be tried at the same time. Only after that search space is exhausted will a true brute force attack begin, because most people's passwords will have been cracked in the first step.

So, if you are using a character based random password, and your password generator just happens to spit out "password1" (which is a perfectly valid output), you would be smart to reject it and try again, as it would be first in the (non-random) list the hacker will try. Since there are relatively few bad passwords in a complete list of random 16 character-long strings, rejecting them doesn't reduce the search space appreciably, and ensures that your resulting password is not at the front of the line. Note that W isn't a less secure letter than H despite being made of two Vs; the components of the letter don't matter, as long as it's a letter.

And if you are using a word based random password, you just need to use enough words. Four is enough. It doesn't matter whether the words have duplicate letters or not, since the letters themselves are not what the password is made of. ("hello" isn't a less secure word than "noble" despite being made with two 'l's; the components of the word don't matter, as long as it's a word.)
Spoiler:
...with one caveat: when the words are put together, collisions cost you: "can" and "teenage" form the same password as "canteen" and "age". A proper word list is curated to avoid this. In some languages letters have the same issue, "ll" and "ch" are each one letter in Spanish. But in either case, the downside is fairly minimal, and overcome by adding one more token.


So, back to the original question - from a randomness point of view, "hello" and "abcde" are equivalent. Similarly, "ovulate" and "fuckyou" are equivalent. But "fuckyou" is a common password, and "ovulate" isn't, so "fuckyou" will be tried first, and "ovulate" will be tried later (and "3Tj&45H" will not be tried until the brute force stage, by which time the hacker will have probably given up).

To help you remember that last one, you could think "Three TJ Max and a 45 handgun". But don't come up with a catch phrase and try to make a password from it - instead let a password generator come up with some random passwords and then come up with a phrase that will help you remember one of them.

Jose
Order of the Sillies, Honoris Causam - bestowed by charlie_grumbles on NP 859 * OTTscar winner: Wordsmith - bestowed by yappobiscuts and the OTT on NP 1832 * Ecclesiastical Calendar of the Order of the Holy Contradiction * Please help addams if you can. She needs all of us.

wumpus
Posts: 498
Joined: Thu Feb 21, 2008 12:16 am UTC

Re: 0936: "Password Strength"

Postby wumpus » Sat Aug 26, 2017 6:11 pm UTC

KnightExemplar wrote:
morriswalters wrote:
KnightExemplar wrote:You're wrong on multiple counts.
Okay. All I've said is that there are 26 unique alphabetic characters.


Your math is right.

Your assumptions are wrong. Particularly this one:

Here is what I think I'm reading when I read about this. The safest any string can be is limited by the number of unique elements.


The "bottleneck" of modern passwords is the 128-bit birthday attack. Which means the safest any string can be is limited to 128-bits of entropy (assuming a SHA-256 underlying). In essence, you are optimizing for a problem that doesn't exist. There are a myriad of simple ways to get to 128-bits of entropy, but the problem is that the human can't memorize them easily.


Birthday attacks are trivially thwarted by means of adding a salt, and if the password-requiring site doesn't bother with a salt you can be nearly certain there are much bigger holes allowing greater attacks. If they were still a problem (presumably due to salts not being invented), you would need the full 256 bits of entropy to make your password as secure as the AES128 that transports the https data back and fourth (if they aren't using this, why have a password?).

Finally, while it is reasonable to assume that neurotypical individuals will be able to memorize unmodified words easiest, I'm not sure about the subset of individuals arguing over a 6 year old webcomic. Certainly recommend this to other users (if they can be persuaded to choose the words correctly and preferably not rearrange them*), but users still arguing the point might as well use their own system.

* is the math that bad for rearranging? Would adding a single word maintain the entropy while making the phrase easier to memorize?

KnightExemplar
Posts: 5489
Joined: Sun Dec 26, 2010 1:58 pm UTC

Re: 0936: "Password Strength"

Postby KnightExemplar » Sat Aug 26, 2017 6:52 pm UTC

wumpus wrote:
KnightExemplar wrote:
morriswalters wrote:
KnightExemplar wrote:You're wrong on multiple counts.
Okay. All I've said is that there are 26 unique alphabetic characters.


Your math is right.

Your assumptions are wrong. Particularly this one:

Here is what I think I'm reading when I read about this. The safest any string can be is limited by the number of unique elements.


The "bottleneck" of modern passwords is the 128-bit birthday attack. Which means the safest any string can be is limited to 128-bits of entropy (assuming a SHA-256 underlying). In essence, you are optimizing for a problem that doesn't exist. There are a myriad of simple ways to get to 128-bits of entropy, but the problem is that the human can't memorize them easily.


Birthday attacks are trivially thwarted by means of adding a salt, and if the password-requiring site doesn't bother with a salt you can be nearly certain there are much bigger holes allowing greater attacks.


Wrong. Salts stop rainbow tables. They do jack diddly squat against the birthday attack.

Of course, birthday attacks are theoretical and require an absurd amount of resources as long as the hash is secure. But birthday attacks are basically the upper bound on any hash based security methodology.

Proving that a defense is as secure as the birthday attack is ideal, because there is virtually no stopping it. Birthday attacks are practically brute force.

Indeed, a brute force cracker is really doing a birthday attack technically speaking.

If they were still a problem (presumably due to salts not being invented), you would need the full 256 bits of entropy to make your password as secure as the AES128 that transports the https data back and fourth (if they aren't using this, why have a password?).


Actually, you need a 256 hash and only need 128 bits of entropy.

Honestly, it sounds like you know what you are talking about, aside from a minor terminology confusion with regards to the definition of birthday attacks.

Finally, while it is reasonable to assume that neurotypical individuals will be able to memorize unmodified words easiest, I'm not sure about the subset of individuals arguing over a 6 year old webcomic.


Fyi, this methodology is considered the gold standard in modern computer security. NIST literally just changed their standards to fit the methodology recommended in the comic.

This is actually a very important comic and concept in the computer security world. It's not necessarily important to agree with it, but at least people should recognize its influence.
First Strike +1/+1 and Indestructible.

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 25789
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: 0936: "Password Strength"

Postby gmalivuk » Sat Aug 26, 2017 7:06 pm UTC

If you rearrange the four words you get, and if there were objectively easiest to remember arrangement of any four words on the list (or if the attacker somehow knew enough about you to know which one you'd pick), it reduces the number of possibilities by a factor of 24. Adding another word to the mix (or just tacking on a random letter) will more than make up for that.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

User avatar
Flumble
Yes Man
Posts: 1945
Joined: Sun Aug 05, 2012 9:35 pm UTC

Re: 0936: "Password Strength"

Postby Flumble » Sat Aug 26, 2017 7:17 pm UTC

wumpus wrote:Finally, while it is reasonable to assume that neurotypical individuals will be able to memorize unmodified words easiest, I'm not sure about the subset of individuals arguing over a 6 year old webcomic.

I don't think the percentage of people with high-functioning Asperger's (or some other memory peculiarity) is significantly higher in this topic than in the general population. And even people with Asperger's likely won't remember a (longer) sequence of symbols as easy as a (shorter) sequence of words, or at the very least it won't be easier for them.
I don't know about the space of transformation functions (e.g. rearranging letters or substituting letters in words) and the entropy of any transformation, but it seems likely to me that it has lower entropy per memorization effort than adding an extra word.

It'd be nice if there were some open, distributed authentication platform for authentication. And one with a distributed identity provider instead of google.

morriswalters
Posts: 6904
Joined: Thu Jun 03, 2010 12:21 am UTC

Re: 0936: "Password Strength"

Postby morriswalters » Sat Aug 26, 2017 7:43 pm UTC

ucim wrote:So, if you are using a character based random password, and your password generator just happens to spit out "password1"
Never gonna happen. I spit out passwords that won't repeat, won't have any double letters or words in the text. Here is what I think one set is. As a factorial. 1+25!+24!+.....+1. That is the number of the members of sets starting with 1. For n=r. Put that on a long line like the Real Integers. Each integer represents a different string. Count to 26! by incrementing n by one each time. The 26 characters starting at position n should be unique. Before you start close the interval (1,26!). You should end up precisely at 26!. With 26! unique sets. Looking at 1. Right where you started. Even better, I'll tell you that I can draw 26! combinations of n on the surface of the sphere and end up one position from my starting point while tracing a helical spiral. For n greater than 0.

I'm gonna take a moment enjoying the idea that what I just said is correct, even if it isn't. I need a moment. :D

Morris Walters
Is it? edits and edits.

User avatar
Eebster the Great
Posts: 2756
Joined: Mon Nov 10, 2008 12:58 am UTC

Re: 0936: "Password Strength"

Postby Eebster the Great » Sat Aug 26, 2017 8:29 pm UTC

But a birthday attack just finds hash collisions, right? It doesn't actually crack any particular password. The idea of a birthday attack is that I keep hashing passwords at random (or with whatever method) until two produce the same hash. That is not useful for cracking a password with a salted hash tied to a unique username. In that case, I have to keep hashing passwords with that particular salt until one happens to collide with that particular hash, which is brute force, not a birthday attack.

EDIT: This paper indicates there is a vulnerability in the Davies-Meyer compression function which is the standard for SHA-256 hash function, among others. This vulnerability makes prefixed salts vulnerable to birthday attacks but not suffixed salts.

Also, the probability that a random password generator spits out an insecure password purely by chance is the same as the probability that a cracker brute forces a secure password purely by chance, so it isn't really something worth worrying about.

rmsgrey
Posts: 3080
Joined: Wed Nov 16, 2011 6:35 pm UTC

Re: 0936: "Password Strength"

Postby rmsgrey » Sat Aug 26, 2017 10:22 pm UTC

When it comes to digital security, a good rule of thumb for most people is that you don't need to be fully secure; you just need to be more secure than the next person on the list. It's only when you, yourself are being deliberately targeted that a hacker will bother to go significantly beyond what would successfully crack a typical password.

You don't have to outrun the bear so long as it's willing to go after the slower runner instead...

wumpus
Posts: 498
Joined: Thu Feb 21, 2008 12:16 am UTC

Re: 0936: "Password Strength"

Postby wumpus » Sun Aug 27, 2017 5:38 pm UTC

KnightExemplar wrote:
wumpus wrote:
KnightExemplar wrote:
morriswalters wrote:
KnightExemplar wrote:You're wrong on multiple counts.
Okay. All I've said is that there are 26 unique alphabetic characters.


Your math is right.

Your assumptions are wrong. Particularly this one:

Here is what I think I'm reading when I read about this. The safest any string can be is limited by the number of unique elements.


The "bottleneck" of modern passwords is the 128-bit birthday attack. Which means the safest any string can be is limited to 128-bits of entropy (assuming a SHA-256 underlying). In essence, you are optimizing for a problem that doesn't exist. There are a myriad of simple ways to get to 128-bits of entropy, but the problem is that the human can't memorize them easily.


Birthday attacks are trivially thwarted by means of adding a salt, and if the password-requiring site doesn't bother with a salt you can be nearly certain there are much bigger holes allowing greater attacks.


Wrong. Salts stop rainbow tables. They do jack diddly squat against the birthday attack.

Of course, birthday attacks are theoretical and require an absurd amount of resources as long as the hash is secure. But birthday attacks are basically the upper bound on any hash based security methodology.


It took me some time to realize how we disagreed on this (using the same mathematics) [and both making different errors in the math of a birthday attack].

A birthday attack represents a limit to attacking a group of M passwords/accounts using a N bit hash and each password containing arbitrary bits of entropy should find a hash collision in 2**(N-log2(M)) operations, so your "128 bits" error confused me. The halving the strength depends on the number of users, and it would take something like 2**64 users to break a 256 bit hash with a a birthday attack in 2**128 tries. Obviously, a birthday attack will be faster than individual brute force attacks (and have that funky exponential increase), but the sizes needed for modern hashes simply make the differences insignificant (even before considering the impossibility of 2**128 operations on a classical (non-quantum) computer).

- Note: Wiki agrees with your 128 bit analysis but it is obviously wrong (consider the case of 2 accounts with secure 256 bit passwords, it will will obviously take 2*255 operations to crack them). Note that while birthday paradox works because the chances of a collision scale factorially, in a birthday attack the target hashes are fixed and only the attackers hashes increase. Collisions between the attackers hashes do not damage the system. Wiki also suggests that some sort of limit on the quantum case, but who knows what they are basing their math on.

The "all existing passwords are cryptographically strong" case never occurred to me. The condition is unthinkable in the current generation of users. I assumed that salt would add entropy to weak passwords that I assume to exist, but a sufficiently unbiased hash shouldn't need that (if your hash has a bias then your troubles are nearly as big as the user using "password1").

The problem with considering a birthday attack in a discussion of passwords is that it is a collective attack on a system that depends on individual action that can't be reliably checked. If absolutely all passwords have entropies>>100 bits, then the best an attacker can do to get a user account (but not *your* user account) is a birthday attack. If a single password has about 100 bits (in a system with less than thousands of accounts), an attacker is better running all hashes through a password guesser. Note that this ignores real physical limitations: birthday attacks are either impossible (because you don't have a quantum computer and an algorithm that works on SHA256) or much easier (because you do. And in that case it is just as likely to brute force *all* the passwords).

[note that you later insisted that there is no one method to force on users. While this might be correct, unless you have the means of limiting password generation systems to known good ones and checking their use, it guarantees at least one guessable password.]

If xkcd readers still think their [worse] methods will generate better passwords, where are you going to find a system with hundreds (or thousands) of accounts that are all cryptographically strong (I suspect that password managers helped a lot more than this comic, but obviously the comic's method is great for the password manager). Even then there are issues about all users keeping their passwords in secure password managers (that are not connected to the internet) and the making sure the users are out of range of a $2 wrench.

[edit: fixed the obvious log2() issue for accounts. Sleeping while someone is wrong on the internet is easier then sleeping when your own post is wrong].

KnightExemplar
Posts: 5489
Joined: Sun Dec 26, 2010 1:58 pm UTC

Re: 0936: "Password Strength"

Postby KnightExemplar » Mon Aug 28, 2017 4:11 pm UTC

wumpus wrote:It took me some time to realize how we disagreed on this (using the same mathematics) [and both making different errors in the math of a birthday attack].

A birthday attack represents a limit to attacking a group of M passwords/accounts using a N bit hash and each password containing arbitrary bits of entropy should find a hash collision in 2**(N-log2(M)) operations, so your "128 bits" error confused me. The halving the strength depends on the number of users, and it would take something like 2**64 users to break a 256 bit hash with a a birthday attack in 2**128 tries. Obviously, a birthday attack will be faster than individual brute force attacks (and have that funky exponential increase), but the sizes needed for modern hashes simply make the differences insignificant (even before considering the impossibility of 2**128 operations on a classical (non-quantum) computer).


To be honest, I haven't heard of the "Birthday attack" being used in your description. We are quite possibly talking about two very different things.

"My" birthday attack is far simpler and generalized to all Hash Functions. The definition of an ideal Hash Function is a random mapping from the set of (infinite) strings -> a 256-bit number (for a 256-bit hash). Since the "domain" of this mapping is infinite, and the output / range is finite, the ideal Hash Function is necessarily a one-way function.

For any Hash output, this means that there are an infinite number of inputs that could map to it. And since the Hash of the password is the only thing stored and compared, then any of these infinite strings can unlock the account.

Lets say Hash("password123") -> "savkwahqvivyawdprwjr". Well... maybe Hash("pyyzazlsmnklqchsobrg") -> "savkwahqvivyawdprwjr". In this case, both "password123" and "pyyzazlsmnklqchsobrg" are valid passwords to the account. A salt changes things slightly, in that I have to search for Hash("salt+password123"), which means that maybe Hash("salt+godosyigjggrtisjcirg") -> something, but the "collision" always exists. The question is how much effort does it take to find these collisions?

The estimated number of strings you have to try before you come up with a 256-bit collision is estimated to be 2^128 tries, as per the Birthday Paradox.

Therefore, any "brute force" methodology against a Hash-based function is innately going to be a birthday attack with a complexity of 1/2 the number of bits (roughly the square-root of the total search space).
First Strike +1/+1 and Indestructible.

rmsgrey
Posts: 3080
Joined: Wed Nov 16, 2011 6:35 pm UTC

Re: 0936: "Password Strength"

Postby rmsgrey » Mon Aug 28, 2017 5:05 pm UTC

KnightExemplar wrote:The estimated number of strings you have to try before you come up with a 256-bit collision is estimated to be 2^128 tries, as per the Birthday Paradox.

Therefore, any "brute force" methodology against a Hash-based function is innately going to be a birthday attack with a complexity of 1/2 the number of bits (roughly the square-root of the total search space).


The thing is, the collisions in the Birthday Paradox are between any two strings entered. If you're trying to crack my password, then hitting the same hash twice with your guesses is going to make it harder rather than easier for you - you've "wasted" a guess hitting the same spot.

If you want to find my password (assuming it's cryptographically strong), then, on average, it's going to take 2^255 tries if you can guarantee hitting a different hash each time; 2^256 if the hashes of each guess are independent.

KnightExemplar
Posts: 5489
Joined: Sun Dec 26, 2010 1:58 pm UTC

Re: 0936: "Password Strength"

Postby KnightExemplar » Mon Aug 28, 2017 5:08 pm UTC

rmsgrey wrote:
KnightExemplar wrote:The estimated number of strings you have to try before you come up with a 256-bit collision is estimated to be 2^128 tries, as per the Birthday Paradox.

Therefore, any "brute force" methodology against a Hash-based function is innately going to be a birthday attack with a complexity of 1/2 the number of bits (roughly the square-root of the total search space).


The thing is, the collisions in the Birthday Paradox are between any two strings entered. If you're trying to crack my password, then hitting the same hash twice with your guesses is going to make it harder rather than easier for you - you've "wasted" a guess hitting the same spot.


I don't care if your real password was "password123" if "pyyzazlsmnklqchsobrg" works just fine. Either way, I get all your Gmail / Youtube / Google Hangouts / everything secured through Google (and since a lot of emails have account information as well as "account reset" permissions, I get all of those too).

Professional hackers don't want your passwords. They want your accounts, and passwords are just a way of accessing accounts. Fortunately, birthday attacks are infeasible for the foreseeable future... they're a theoretical ideal. No one is going to birthday attack your system (any more than they're going to guess your password). But since the birthday attack is "technically" easier than guessing a secure password, the birthday attack of sqrt(search space) is the theoretical upper bound on all Hash-based password systems.
First Strike +1/+1 and Indestructible.

User avatar
Soupspoon
You have done something you shouldn't. Or are about to.
Posts: 2486
Joined: Thu Jan 28, 2016 7:00 pm UTC
Location: 53-1

Re: 0936: "Password Strength"

Postby Soupspoon » Mon Aug 28, 2017 5:57 pm UTC

I've always conflated two aspects in the Birthday Attack idea.

1) As above, you're looking for the same hash, regardless of the input - at its simplest misapplication, you don't care exactly how old someone is, including the year of birth, if they reply that they have the same day and month as your reference date then it's a match. (A bad hash function, so predictably cyclic in its many-to-one reduction, but arguablg dropping the year is hashing, of a kind.)

2) Via the Birthday Paradox, you're comparing many-to-many. In an untargeted attack you don't care which account B has a password that coincides with (possibly hypothetical, possibly also same-hash-despite-different-password!) account A's login details, you're looking at many potential As and Bs and comparing them, until you get a usable match. Not quite the same maths as the Paradox, but still discovers low-hanging fruit (and maybe some non-low fruit, that just happen to swing into reach!) so long as the target system isn't savvy enough to detect the Bruting necessary.


Incidentally, on one old system of mine, I experimentally messed with the login module to require the (valid) password to be used twice, sequentially. It would reject the first attempt, exactly as if actually wrong, but then accept it if the very next attempt was the same (valid) password. I could have had it need one password for priming, a second password to complete the job, but there was a chance that a very lucky brute-forcing algorithm could have tried each in turn. But which one would try an invaljd one, again? Without being forewarned, somehow.

(And I could have engaged advanced IDS actions upon "these bad passwords are all being used twice!", if I had seen fit. Requiring an additional unlock-password/repeat, maybe, to undo the lockdown that came from the many undesirable attempts. The trouble being that once you get beyond the login-shell, and onto things that remote machines with standard password-authentication sending modules, like a browser getting a 401/403 error. There's no easy way to deal with that without a rebuilt browser made to do the appropriate authentication request twice, before truly admitting defeat for the user, etc.)

With a little thought, though, you can come up with all kinds of proprietry 'fake failures' that are actually an intrinsic part of a handshaking of authentications. 'All' you need, then, is the wherewithal to twiddle the mechanisms involved to accommodate your background trickery, to your own spec. And yet not introduce vulnerabilities or other failure modes into the mechanism, whilst you do so, naturally.

User avatar
Eebster the Great
Posts: 2756
Joined: Mon Nov 10, 2008 12:58 am UTC

Re: 0936: "Password Strength"

Postby Eebster the Great » Mon Aug 28, 2017 7:16 pm UTC

KnightExemplar, you are wrong about how birthday attacks work. A birthday attack as you describe searches for a hash collision. It does not search for a collision with any hash actually stored in a database. In other words, there may be nobody on Earth who has ever had a password that would generate that hash. Rather, you are simply trying to find two strings--any two strings--that produce the same hash. In that way, you can use the same logic that is applied to the Birthday paradox to find a collision in the square root of the time you would otherwise expect.

But if you are looking for a collision with a particular hash, for example to crack a password, then this is useless. Since properly salted hashes use a different salt for every hash, there is no better method than to keep hashing different passwords with a given salt to hope to collide with that particular salted hash. This is brute force, not a birthday attack.

KnightExemplar
Posts: 5489
Joined: Sun Dec 26, 2010 1:58 pm UTC

Re: 0936: "Password Strength"

Postby KnightExemplar » Mon Aug 28, 2017 7:58 pm UTC

Eebster the Great wrote:KnightExemplar, you are wrong about how birthday attacks work. A birthday attack as you describe searches for a hash collision. It does not search for a collision with any hash actually stored in a database. In other words, there may be nobody on Earth who has ever had a password that would generate that hash. Rather, you are simply trying to find two strings--any two strings--that produce the same hash. In that way, you can use the same logic that is applied to the Birthday paradox to find a collision in the square root of the time you would otherwise expect.

But if you are looking for a collision with a particular hash, for example to crack a password, then this is useless. Since properly salted hashes use a different salt for every hash, there is no better method than to keep hashing different passwords with a given salt to hope to collide with that particular salted hash. This is brute force, not a birthday attack.


I disagree. Although we've left the realm of English words so I'll use a concrete example.

Lets have a 1 decimal digit checksum be the "hash", a trivial hash but one that satisfies enough conditions that this toy example works out. In Python, this code will be:

Code: Select all

 reduce(lambda x,y: x+y, map(ord, "string_to_hash")) % 10


Which for this example, should output "0".

-----------

A simple salt, say from "crypt" era, would be to add two random letter/Number [A-Za-z0-9] to the beginning (this is a weak salt, but I'm trying to keep things simple for this example). Lets take "zK" as our salt. This means that the password would be stored as:

Salt: "zK"
Password (not stored): "string_to_hash"
Hash: reduce(lambda x,y: x+y, map(ord, "zKstring_to_hash")) % 10 == 7.

Any "Hash("zk" + password)" that results in "7" will work. For example:

Hash("zKexample_collision7") == 7, and therefore would be a valid password to enter the system. This is the birthday attack. I didn't need to find the original password, because "example_collision7" is enough to log me in through this simple system.

Of course, "real" hash functions are 256-bits long, not 3-bits long. So I'd never really find a real collision in practice (unless you're using a weak hash).

The salt does nothing for birthday attacks. It changes the underlying hash function a little bit, but not enough for it to make a difference in this particular case. All hash functions (even those modified by a salt) will have the many-to-one reduction, which means an infinite number of strings exist as valid passwords... as a potential collision.

Salts are important to prevent a Rainbow Table attack. But that's it. They don't help in many of the other cryptographic attacks that exist out there.
First Strike +1/+1 and Indestructible.

wumpus
Posts: 498
Joined: Thu Feb 21, 2008 12:16 am UTC

Re: 0936: "Password Strength"

Postby wumpus » Mon Aug 28, 2017 8:23 pm UTC

I'm sorry to have brought up the salt, it does nothing for birthday attacks.

Presumably Soupspoon made things obvious, but I'll do my try.

But the problem with your [KnightExemplar] description of a birthday attack is that even if you generate 2**128 gmail accounts, that doesn't get you any more access to any google account data than a single account (except any obvious means around data and transmission limits).

Sure, you now happen to know more than one password to access at least one of your accounts, but since you already have the original password, that buys you nothing.

Assuming that there are 2**32 gmail accounts out there, it is going to take way more than 2**128 gmail accounts to get a collision with an account you don't already own. And that is for a system with an absolutely huge number of accounts (I think I've had notification of 8 character randomly generated passwords being subverted).

- funky tale from the past: While salts were indeed created to prevent rainbow tables, a common use of such tables (or brute force hacking) involved brute forcing enough possible passwords (typically numbers) to generate various (typically rude) words for the .passwd file. Nerds gotta nerd

User avatar
Eebster the Great
Posts: 2756
Joined: Mon Nov 10, 2008 12:58 am UTC

Re: 0936: "Password Strength"

Postby Eebster the Great » Mon Aug 28, 2017 11:14 pm UTC

Knight, that is emphatically not a birthday attack. That is a brute force attack. You simply guess random passwords until one of them yields the correct hash. There is no slower possible method. A birthday attack works by checking each hash against all previously generated hashes (or sometimes a subset of them, such as in a digital signature attack). It finds a collision in the square root of the time it would take to collide with any particular given hash.

With a 256-bit hash, the brute force method you described would take 2255 guesses before it had a 50% probability of finding a collision with the given hash. A birthday attack would require about 1.2 * 2128 guesses before at least two of the generated hashes probably collide.

wumpus wrote:I'm sorry to have brought up the salt, it does nothing for birthday attacks.

Salts are very relevant for the reasons below.

wumpus wrote:Assuming that there are 2**32 gmail accounts out there, it is going to take way more than 2**128 gmail accounts to get a collision with an account you don't already own. And that is for a system with an absolutely huge number of accounts (I think I've had notification of 8 character randomly generated passwords being subverted).

But if those hashes are all salted with different salts, you cannot simply keep hashing with a single algorithm until you collide with at least one of them. Rather, you have to keep hashing with a particular salt until you collide with the hash of the single unique account using that salt. That's sort of the point.


Obviously all this assumes that the passwords chosen are all very secure. Realistically, this would all be a waste of time, because instead you could just try the most popular passwords and variations thereof and crack most of the passwords right away.

KnightExemplar
Posts: 5489
Joined: Sun Dec 26, 2010 1:58 pm UTC

Re: 0936: "Password Strength"

Postby KnightExemplar » Mon Aug 28, 2017 11:27 pm UTC

EDIT: Lemme think about this a bit more. I'll restore my post (if no one has posted), or repost later.

EDIT2: Upon further thought, I think Eebster the Great is correct.

Eebster the Great wrote:Knight, that is emphatically not a birthday attack. That is a brute force attack. You simply guess random passwords until one of them yields the correct hash. There is no slower possible method. A birthday attack works by checking each hash against all previously generated hashes (or sometimes a subset of them, such as in a digital signature attack). It finds a collision in the square root of the time it would take to collide with any particular given hash.

With a 256-bit hash, the brute force method you described would take 2255 guesses before it had a 50% probability of finding a collision with the given hash. A birthday attack would require about 1.2 * 2128 guesses before at least two of the generated hashes probably collide.


The Birthday paradox only works because you're checking (any to any). If one "leg" of the check is fixed (ie: the salted hash of a password), then the Birthday paradox attempt will not work.

In terms of the Birthday problem: it will take 365/2 people to (probably, 50% chance) find somebody who has the same birthday as you. But it only takes (on the order of) sqrt(365) or ~23 people to (probably 50%) find somebody who has the same birthday as somebody. (sqrt is a very crude estimation)

Which would imply that Wumpus was correct a few posts ago when he says that Salts protect against the Birthday attack.
First Strike +1/+1 and Indestructible.

rmsgrey
Posts: 3080
Joined: Wed Nov 16, 2011 6:35 pm UTC

Re: 0936: "Password Strength"

Postby rmsgrey » Tue Aug 29, 2017 1:05 am UTC

KnightExemplar wrote:In terms of the Birthday problem: it will take 365/2 people to (probably, 50% chance) find somebody who has the same birthday as you.


That's only true if the 182.5 people all have different birthdays from each other. If people's birthdays are independently uniformly distributed through the year (not actually true, but it makes the maths easier) then you need n such that (364/365)n < 0.5 or at least 253 people (roughly 5/7 of 365). If you ask random people their birthday until you find someone who has the same as you, then, on average, you'll ask 365 people.

User avatar
Eebster the Great
Posts: 2756
Joined: Mon Nov 10, 2008 12:58 am UTC

Re: 0936: "Password Strength"

Postby Eebster the Great » Tue Aug 29, 2017 4:04 am UTC

KnightExemplar wrote:But it only takes (on the order of) sqrt(365) or ~23 people to (probably 50%) find somebody who has the same birthday as somebody. (sqrt is a very crude estimation)

Technically, it is O(√n), and a good approximation for the exact value of the number of guesses is 1.25√n. That actually works quite well in the classic "birthday paradox" problem itself, as it does in birthday attacks in general.

morriswalters
Posts: 6904
Joined: Thu Jun 03, 2010 12:21 am UTC

Re: 0936: "Password Strength"

Postby morriswalters » Tue Aug 29, 2017 1:02 pm UTC

My apologies to everyone. My set of possible passwords is shorter than Randall's. I miscounted it by using permutations incorrectly. Randall's set is a larger set, mine are all unique. Since in theory his set contains my set. I'll use mine. Randall's is easy to use if you need to remember them, I have no such need. I want to generate them easily, and organize the sets by their index. Thank you all for sharing your skills with me.

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 25789
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: 0936: "Password Strength"

Postby gmalivuk » Tue Aug 29, 2017 2:31 pm UTC

Randall's are all unique, too, because if two passwords were the same they wouldn't be two passwords.

And if memorization isn't an issue, just use randomly generated gibberish, as it will be much more secure than a list of discrete words.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)


Return to “Individual XKCD Comic Threads”

Who is online

Users browsing this forum: No registered users and 47 guests