0936: "Password Strength"

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

Moderators: Moderators General, Prelates, Magistrates

MrRubix
Posts: 49
Joined: Sun Jul 27, 2008 2:59 pm UTC

Re: 0936: "Password Strength"

Postby MrRubix » Fri Sep 16, 2011 1:46 pm UTC

Yakk wrote:No, it doesn't come down to that notion? You can have lots of entropy with structure that makes it easy to remember.

The "pass phrase of random words, which you then connect with additional words of your choice" generates easy to remember pass phrases that have more than enough entropy.

@#())IFΦDSKM1)*(8@F style passwords are harder to remember (even with mnemonics) and have no higher security (per effort put into remembering them). Which is the point of the comic.


@#())IFΦDsKM1)*(8@F style passwords are only hard to remember at first but are made easy through mnemonics -- eventually you won't need the mnemonic and the password becomes second-nature, and therefore the difficulty in memory is greatly diminished. A long passphrase takes a long time to type no matter what.

gmalivuk wrote:
MrRubix wrote:Ultimately, it comes down to the notion that easily-memorable passwords have some sort of non-random structure to it, and that non-random structure makes a password easier to crack, even if it's high-entropy.
That may be a notion some people have, but it's a completely incorrect one.


Please explain? Why would a @#())IFΦDsKM1)*(8@F style password be easier to crack?

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

Re: 0936: "Password Strength"

Postby gmalivuk » Fri Sep 16, 2011 2:29 pm UTC

MrRubix wrote:
gmalivuk wrote:
MrRubix wrote:Ultimately, it comes down to the notion that easily-memorable passwords have some sort of non-random structure to it, and that non-random structure makes a password easier to crack, even if it's high-entropy.
That may be a notion some people have, but it's a completely incorrect one.
Please explain? Why would a @#())IFΦDsKM1)*(8@F style password be easier to crack?
It's not easier to crack. It's the same difficulty to crack as another password with the same entropy, even if that other password is a string of 10 words from the diceware list. It might seem on the face of it that this latter one has less randomness, especially if you also add in grammar words to make it into a meaningful sentence or two, but the entropy is the same (or greater if the additional words are part of the password instead of just a mnemonic), and the crackability is the same.

So there does have to be the same amount of total randomness to have the same amount of total entropy and crackability. But your assertion was that additional non-random structure (such as adding words to make the passphrase grammatical) makes a password easier to break. This assertion is incorrect, because that structure doesn't in any way reduce the existing randomness.
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
Yakk
Poster with most posts but no title.
Posts: 11128
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: 0936: "Password Strength"

Postby Yakk » Fri Sep 16, 2011 2:45 pm UTC

I rarely type a password more than once per hour.

In one minute, how much can I type? Lets find out. I'll keep typing, making things up as I go, until the clock ticks over. Note that I'm also doing spell checking and correction, but when doing a memorized passphrase, I wouldn't have to. So this is a test that is biased in the other direction. If I spend less than 10 seconds banging out a password once per hour, I don't think that it will be a serious problem -- I don't.

Done. 429 characters/minute, or 7.15 characters/second throughput. A 10 second password is thus 72 characters for me. I could significantly increase my throughput by getting used to typing a given sentence, and not having to compose it as I typed it.

A random garbage password might bring my typing time down to 5 seconds. And once-per-hour is high frequency -- more likely, ~4-6 times per day for a work computer?

And a password that I'm entering more than once per hour seems like a serious problem (to me), or something I should automate (such as browsers saving passwords for me).
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

MrRubix
Posts: 49
Joined: Sun Jul 27, 2008 2:59 pm UTC

Re: 0936: "Password Strength"

Postby MrRubix » Fri Sep 16, 2011 2:54 pm UTC

gmalivuk wrote:It's not easier to crack. It's the same difficulty to crack as another password with the same entropy, even if that other password is a string of 10 words from the diceware list. It might seem on the face of it that this latter one has less randomness, especially if you also add in grammar words to make it into a meaningful sentence or two, but the entropy is the same (or greater if the additional words are part of the password instead of just a mnemonic), and the crackability is the same.

So there does have to be the same amount of total randomness to have the same amount of total entropy and crackability. But your assertion was that additional non-random structure (such as adding words to make the passphrase grammatical) makes a password easier to break. This assertion is incorrect, because that structure doesn't in any way reduce the existing randomness.


Right, but we're technically in agreement. For the same level of entropy, a shorter password of gibberish is just as tough to crack as a longer password of words.

I don't disagree that adding additional non-random structure takes away from the strength of existing randomness and did not mean to imply such. I was incorrectly lumping in the non-random structure with the definition of entropy (which is by definition random) when I was really aiming to say "number of elements." By this I mean if we were to make a ten-word passphrase, having ten completely random words is harder to crack than a ten-word passphrase that follows some grammatical order.

At any rate, given the same level of entropy, I'd rather use a shorter password than a longer one. There are always ways to break it down into an easier mnemonic that eventually becomes unnecessary once the password is moved into long-term memory. I prefer that to typing out some long-ass phrase every time I need to access something.

User avatar
Eebster the Great
Posts: 3460
Joined: Mon Nov 10, 2008 12:58 am UTC
Location: Cleveland, Ohio

Re: 0936: "Password Strength"

Postby Eebster the Great » Fri Sep 16, 2011 3:27 pm UTC

gmalivuk wrote:But the reason to then reject it is that the odds of an attacker checking that password before others are very high.

Right, but the odds of picking such a password in the first place are low enough so you generally shouldn't worry about that possibility.

superluser
Posts: 16
Joined: Wed Aug 17, 2011 5:36 am UTC

Re: 0936: "Password Strength"

Postby superluser » Fri Sep 16, 2011 7:44 pm UTC

gmalivuk wrote:Of all the 12-character ASCII passwords, approximately 0.08% consist entirely of letters (upper and lower case). So the entropy lost by rules which prohibit such passwords is minuscule.


I'm not sure if this is supposed to be a response to me. What I can tell is that it doesn't refer to the argument that I've been making. In the example I gave, I'm talking about passwords that are considered too short if they are 48 ASCII characters long, and they're generated in pairs.

Half those passwords are excluded as being divisible by 2. Two thirds are excluded because they are divisible by 2 or 3, 13/15ths are divisible by 2, 3, or 5, and so on. And that's not counting the ones that are not in the safe category. That's for one class of high-entropy passwords.

You may see similar flaws in other security schemes.

erik65536
Posts: 8
Joined: Wed May 04, 2011 7:06 pm UTC

Re: 0936: "Password Strength"

Postby erik65536 » Fri Sep 16, 2011 10:45 pm UTC

Isil`Zha wrote:
I agree that the original poster was overstating the security, but I think they do have a valid point about using unicode characters.


I was simply pointing out that in most (if not all) cases, a brute force attack won't even include the appropriate key space - in those cases, it literally will never break the password.

In the cases that they actually do - entropy is significantly increased anyway, making the time it takes to crack it even more impractical - so much so it's effectively unbreakable.

...
Isil`Zha wrote:Right, but I don't go around telling possible attackers that there are unicode characters in my password

...
Isil`Zha wrote:This is exactly what I was saying. A) They already have to brute force my PW because dictionary attacks won't work. B) Any would-be attacker very likely will never have met or talked to me, likely meaning that they will not be searching the Unicode space - making it unbreakable to them. C) Even knowing all this, they're still stuck brute forcing for longer than their lifetime to break it, so the whole exercise is rather futile.


I agree that if an attacker was trying to brute force your password, it is unlikely they would try the entire unicode character set. Certainly not more than a few characters in length. But who says that they have to brute force your password just because it contains a few unicode characters? It would be very reasonable to think that an attacker would try common password algorithms and append a unicode character on the end. They could also try unicode characters between words or many other possibilities.

Most people probably do not choose randomly from the entire unicode set either. They probably choose only characters that can be typed with alt+XXXX. Also, most people choose characters they are familiar with. As a poster already pointed out, in my example I didn't choose a character randomly. I chose a greek character because I am familiar with them. So a smart attacker could make their attacks much faster. Just adding a unicode character does not make your password "practically unbreakable".

But it is less likely that an attacker will try unicode characters. And if an attacker is reduced to doing a brute force attack, it is even more unlikely that they will crack your password in a reasonable amount of time. So in practice it is safer than not using them. Never underestimate the cleverness of an attacker though. Do not assume that an attacker will have to resort to a brute force attack. Someone could glance over your shoulder and see the length of your password or a few characters. They could even see that you type on one side of the keyboard more than another. They can search your username on the internet to find out information about you. They might be able to crack a different password using an offline attack, and now that they know your pattern they can use a smarter online attack. Or they could even trivially break it by using a key logger or reading from memory. Or they can reduce the key space using cryptanalysis. Or they can get an SSL certificate signed by a CA and use a MITM attack. So to be as safe as possible always ensure that your password has adequate entropy. And also make sure you take reasonable precautions to mitigate "side channel" attacks as much as possible.

Google ( "Isil`Zha" forum ). I will bet you that many of the results are you. If someone tries to crack your password your password isn't uncrackable because it uses unicode characters, but it is if you have a lot of entropy.
( "isil zha" forum "password" -"forgot password" -"remember password" ) *cough* spacebattles *cough*

Harold
Posts: 14
Joined: Wed Jun 29, 2011 4:20 am UTC

Re: 0936: "Password Strength"

Postby Harold » Sat Sep 17, 2011 11:51 am UTC

A lot of you seem to be glossing over the actual application for something like this.

With a compromised database of million passwords, an attacker will just run a brute force attack with a character set not dissimilar to the following

Code: Select all

abcdefghijklmnopqrstuvwxyz0123456789


The most extreme search might use something like this, no extended ASCII, no UTF8, not even any accented characters

Code: Select all

 !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~


Even with a CUDA rig blasting out 10Bhash/second, almost all of the possible passwords mentioned in this thread are safe for a very long time. You will get a large percentage of the passwords, and it's easier picking just to get another database, than to continue.

User avatar
Eebster the Great
Posts: 3460
Joined: Mon Nov 10, 2008 12:58 am UTC
Location: Cleveland, Ohio

Re: 0936: "Password Strength"

Postby Eebster the Great » Sat Sep 17, 2011 4:11 pm UTC

But attackers don't just use brute force. Attacks using rainbow tables and the like are extremely common.

It is true that attackers typically go after the low-hanging fruit, but that doesn't mean a password with more entropy than "soccermom6" is actually "secure."

kragen
Posts: 1
Joined: Sat Sep 17, 2011 5:48 pm UTC

Re: 0936: "Password Strength"

Postby kragen » Sat Sep 17, 2011 6:19 pm UTC

Hi. I just posted an implementation of this password generation algorithm, together with some analysis of strengths and weaknesses of this sort of password. Ironically, the xkcd forums themselves suffer from an arbitrary password length limit: 30 characters, which is shorter than my new password. (So I used a random-characters password.)

http://lists.canonical.org/pipermail/kragen-hacks/2011-September/000527.html

fagricipni
Posts: 41
Joined: Thu Nov 04, 2010 7:32 pm UTC

Re: 0936: "Password Strength"

Postby fagricipni » Sat Sep 17, 2011 6:46 pm UTC

superluser wrote:`correct battery hor∫e staple' might make it difficult for script kiddies to defeat your password


I'd not be so confident in that particular phrase; if an competent attacker does try Unicode characters, they will try look-similars and sound-similars first; of course, replacing random characters with look-similars and/or sound-similars will make some increase in entropy, but not so much as one might think.

For the one who mentioned having trouble remembering random characters, the Diceware site has a suggestion for that, even if you don't like the basic Diceware idea. Indeed, you can even have the table of memory keys for the special characters written down, if you never reveal which the memory key(s) of the special character(s) correspond to the actual special character(s) in your passwords.

Harold
Posts: 14
Joined: Wed Jun 29, 2011 4:20 am UTC

Re: 0936: "Password Strength"

Postby Harold » Sat Sep 17, 2011 7:14 pm UTC

Everyone in this thread is far over estimating the speed at which even a local attack can be mounted. I have experimented with this; some example hashes and 40 x iMacs running a distributed GPU based MD5 cracker. It still took an insane amount of time.


Eebster the Great wrote:But attackers don't just use brute force. Attacks using rainbow tables and the like are extremely common.


A rainbow table is useful up to 8 characters or so with a limited ascii set, beyond that you are getting into the tens of terrabytes, and a massive search time. It's faster to use a GPU based cracker on a headless box, with multiple GPUs. Even so, still no where near the speed to make cracking anything over 10 characters alphanumerical at all probable.

It can be done, but the cost of power and time would never be worth it.


superluser wrote:`correct battery hor∫e staple' might make it difficult for script kiddies to defeat your password


I can not see any attack ever attempting that. The level of mutation you would have to do to reach that password would be astronomical, even taking two dictionary words and only applying one mutation per attempt. Even if I knew it was a mutation on horse staple, I would never have picked the '∫' character to be a mutation of 's', it appears simply to me as a 'f'. There would be literally thousands of 's' like characters in the various unicode maps.


fagricipni wrote:I'd not be so confident in that particular phrase; if an competent attacker does try Unicode characters, they will try look-similars and sound-similars first; of course, replacing random characters with look-similars and/or sound-similars will make some increase in entropy, but not so much as one might think.


An attacker will never attempt unicode characters; end of story. Easier just to use some run-of-the-mill spear phishing, or just go hit the person with a wrench if it's that important.


Spear phishing is a whole lot easier than anything people have mentioned here.

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

Re: 0936: "Password Strength"

Postby gmalivuk » Sat Sep 17, 2011 7:48 pm UTC

Harold wrote:Even so, still no where near the speed to make cracking anything over 10 characters alphanumerical at all probable.

It can be done, but the cost of power and time would never be worth it.
Sure, if it's a truly random 10-character alphanumeric password, it's probably pretty impractical to beat with a purely brute-force attack. But the whole point of the comic and much of the subsequent discussion is that 10-character alphanumeric passwords are really frequently based on mutating a single word rather than being truly random.

superluser wrote:`correct battery hor∫e staple' might make it difficult for script kiddies to defeat your password
I can not see any attack ever attempting that.
Oh good. Your argument from personal incredulity makes me feel *much* safer.

The level of mutation you would have to do to reach that password would be astronomical, even taking two dictionary words and only applying one mutation per attempt. Even if I knew it was a mutation on horse staple, I would never have picked the '∫' character to be a mutation of 's', it appears simply to me as a 'f'. There would be literally thousands of 's' like characters in the various unicode maps.
Be that as it may, ∫ is simply an elongated S. I mean, hell, that's why it's used for integration, replacing the Greek capital sigma (i.e. S) used in discrete summations. For anyone who actually knows that, ∫ as a replacement for s would be guessed far earlier than it apparently would be against you. So all you've so far told us is how to ensure that you won't figure out how to break our simple mutations.

An attacker will never attempt unicode characters; end of story.
Counterexample: I just tried logging into your account with some unicode characters.
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)

Harold
Posts: 14
Joined: Wed Jun 29, 2011 4:20 am UTC

Re: 0936: "Password Strength"

Postby Harold » Sat Sep 17, 2011 8:28 pm UTC

gmalivuk wrote:
superluser wrote:`correct battery hor∫e staple' might make it difficult for script kiddies to defeat your password
I can not see any attack ever attempting that.
Oh good. Your argument from personal incredulity makes me feel *much* safer. [/quote]

Even easier, the script kiddie just injects a a snippet of code to record passwords. Entropy doesn't matter then when you're sitting on the plaintext. All having a ridiculous password does is inspire reuse, or sticky notes with bits of paper sitting on their desks.


gmalivuk wrote:Be that as it may, ∫ is simply an elongated S. I mean, hell, that's why it's used for integration, replacing the Greek capital sigma (i.e. S) used in discrete summations. For anyone who actually knows that, ∫ as a replacement for s would be guessed far earlier than it apparently would be against you. So all you've so far told us is how to ensure that you won't figure out how to break our simple mutations.


Alright, so we can use the ∫ character for mutations of 's', 'f' and 'S'. That's going to effect a good portion of a standard dictionary, a dictionary based on common passwords would have tens of millions of entries, each of which need to be mutated. Each of these words, with each variation then needs to be concatenated with 3 others, and then tested. The amount of effort involved just isn't justifiable.


gmalivuk wrote:Counterexample: I just tried logging into your account with some unicode characters.


As you're not searching with any intent on finding this account's password (it's account unique); I don't think it's a reasonable counter. Even if you knew that it followed the pattern ([a-zA-Z0-9]{32}) (and it does), the chances of you solving even the fingerprint from the forums database is horribly slim. You're talking years of searching on multiple GPUs.


As any attack against local hashes (assumed in this case) is done on a large scale; the more hashes you're cracking simultaneously, the more cost effective your search is (to a certain point). Once an attacker has searched a large dictionary, maybe appending numbers, they are going to move on, not waste time with various permutations of passwords.

In all honesty, no one wants your forum password. They hope that you use the same password for your online banking, paypal, maybe some shell on a zesty high ranking site.

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

Re: 0936: "Password Strength"

Postby gmalivuk » Sat Sep 17, 2011 8:46 pm UTC

Harold wrote:Even easier, the script kiddie just injects a a snippet of code to record passwords. Entropy doesn't matter then when you're sitting on the plaintext. All having a ridiculous password does is inspire reuse, or sticky notes with bits of paper sitting on their desks.
Is "correct horse battery staple" really all that ridiculous? Is it so difficult to remember that you'd have to write it down on a sticky note?

Alright, so we can use the ∫ character for mutations of 's', 'f' and 'S'. That's going to effect a good portion of a standard dictionary, a dictionary based on common passwords would have tens of millions of entries, each of which need to be mutated. Each of these words, with each variation then needs to be concatenated with 3 others, and then tested. The amount of effort involved just isn't justifiable.
If I have a reasonable suspicion that people are using otherwise common passwords together with some "clever" substitution of one or two characters, then my search is really only a handful of bits more difficult than Tr0ub4dor$3.

As you're not searching with any intent on finding this account's password (it's account unique); I don't think it's a reasonable counter.
Look, dude, you never said "no attacker who has a reasonable expectation of breaking lots of passwords quickly is going to try unicode". You said no attacker would try unicode, ever [emphasis in original].

Even if you knew that it followed the pattern ([a-zA-Z0-9]{32}) (and it does), the chances of you solving even the fingerprint from the forums database is horribly slim.
We're not really talking about good, strongly random passwords, though. We're talking about the belief that a somewhat secure password can be made *really* secure by throwing in a unicode character or two.

Incidentally, I really strongly doubt that your password actually has 190 bits of entropy. It might be a 32-character long string of letters and numbers, but if I really were attempting to crack it, I wouldn't be so foolish as to just dumbly go through starting with aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa, followed by aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab. I'd try things based on words and dates and phone numbers and such, first.
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)

Harold
Posts: 14
Joined: Wed Jun 29, 2011 4:20 am UTC

Re: 0936: "Password Strength"

Postby Harold » Sat Sep 17, 2011 9:17 pm UTC

gmalivuk wrote:
Harold wrote:Even easier, the script kiddie just injects a a snippet of code to record passwords. Entropy doesn't matter then when you're sitting on the plaintext. All having a ridiculous password does is inspire reuse, or sticky notes with bits of paper sitting on their desks.
Is "correct horse battery staple" really all that ridiculous? Is it so difficult to remember that you'd have to write it down on a sticky note?


You'd be surprised. I've often seen people forget passwords very very easily. Moreover, looking at the logs from a service I administer, I've seen users that have used the password reset to log in almost every time. Judging by the mentioned service, and from what other people have mentioned to me, people forgetting passwords is a day-to-day occurrence. The xkcd community are by no means the norm.


gmalivuk wrote:If I have a reasonable suspicion that people are using otherwise common passwords together with some "clever" substitution of one or two characters, then my search is really only a handful of bits more difficult than Tr0ub4dor$3.


Agreed. From what password lists I've had had a quick glance though, the overwhelming number use strictly lowercase dictionary words, with a single letter appended to the end. I suppose for the most part, it works.


Look, dude, you never said "no attacker who has a reasonable expectation of breaking lots of passwords quickly is going to try unicode". You said no attacker would try unicode, ever [emphasis in original].


I was thinking that in the real world, it's probably easier to take another route than search for unicode characters. If the person is that smart, they probably have other protections in place, right?

That said, I could have worded it a lot better.


gmalivuk wrote:Incidentally, I really strongly doubt that your password actually has 190 bits of entropy. It might be a 32-character long string of letters and numbers, but if I really were attempting to crack it, I wouldn't be so foolish as to just dumbly go through starting with aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa, followed by aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab. I'd try things based on words and dates and phone numbers and such, first.


In this case, it actually does; generated by a KeePass-like script I made a while back at uni. From memory, I avoided unicode as unicode characters can display a little funky in certain situations. The master key for that is, however, a full 30+ character long random string. With a bit of practise, you can memorise almost anything.

I can respect though, in most situations a longer password would be something easily guessable. Phone numbers are apparently pretty popular for example, and of course, very easy to brute force against.

fagricipni
Posts: 41
Joined: Thu Nov 04, 2010 7:32 pm UTC

Re: 0936: "Password Strength"

Postby fagricipni » Sat Sep 17, 2011 9:24 pm UTC

I'll grant that there are time when the difficulty of memorization is balanced against the security of the passphrase. If the passphrase one uses here is not shared with any other site, the personal consequence of having the passphrase broken is not very much. Having the passphrase broken on a bank account would have much more severe consequences.

Interestingly many people who don't trust low-bit encryption on a computer to keep a credit card number safe are perfectly willing to give their credit card number to the company over land-line phones -- messages which are sent in the clear. One should consider what risks one is already taking; I would not use a 128-bit entropy passphrase on a forum; it would be unlikely that I would use such a passphrase on a banking site; but I might use it on a GPG private key -- of course, even then it is probably overkill. It is more a hedge against future improvements in computer speeds rather than current protection; currently anyone willing to spend the money to build a computer system that could brute-force GPG would be more likely to use rubberhose cryptanalysis; there used to be a publicly available deniable encrypted filesystem called Rubberhose, bus as far as I know it is no longer supported.

Harold
Posts: 14
Joined: Wed Jun 29, 2011 4:20 am UTC

Re: 0936: "Password Strength"

Postby Harold » Sat Sep 17, 2011 9:40 pm UTC

fagricipni wrote:Interestingly many people who don't trust low-bit encryption on a computer to keep a credit card number safe are perfectly willing to give their credit card number to the company over land-line phones -- messages which are sent in the clear.


I'd be more worried about the person at the other end writing it down; assuming you're not entering them via the DTMF numberpad, which is commonplace here.


wikipedia on 'rubber hose' wrote:The euphemistic term refers to beating someone with a rubber hose until they cooperate.


There's something drink-spillingly hilarious about that sentence.

superluser
Posts: 16
Joined: Wed Aug 17, 2011 5:36 am UTC

Re: 0936: "Password Strength"

Postby superluser » Sun Sep 18, 2011 4:54 am UTC

fagricipni wrote:
superluser wrote:`correct battery hor∫e staple' might make it difficult for script kiddies to defeat your password


I'd not be so confident in that particular phrase; if an competent attacker does try Unicode characters, they will try look-similars and sound-similars first; of course, replacing random characters with look-similars and/or sound-similars will make some increase in entropy, but not so much as one might think.


Well, really not much increase in entropy. It would provide nearly no additional challenge for a competent attacker. That's what I mentioned before about APTs (or advanced persistent threats). You don't really make it more secure. You just manage to lock out dumb thieves. The amount of work you might need to perform to keep out truly competent attacks may actually be beyond your capabilities, if for no other reason than you don't have control over the password policy, and the person who does insists that passwords must be less than six characters long.

Harold wrote:Even easier, the script kiddie just injects a a snippet of code to record passwords. Entropy doesn't matter then when you're sitting on the plaintext. All having a ridiculous password does is inspire reuse, or sticky notes with bits of paper sitting on their desks.


Right. As rainbow tables and some types of brute force attacks are pushed out, other types of attacks become more likely. Your task is to make your password strong enough that the attacker should prefer meatspace attacks, at which point, the difficulty or risk of discovery may cause the attacker to give up.

Fizzy McPhysics
Posts: 1
Joined: Tue Sep 20, 2011 12:41 pm UTC

Re: 0936: "Password Strength"

Postby Fizzy McPhysics » Tue Sep 20, 2011 12:57 pm UTC

Given the exponential growth in computing power how long will it be before correcthorsebatterystaple can be cracked in 3 days? Also will there come a point where a password the length of War and Peace won't be enough to protect my emails?

I ran some searches on this topic to see if this has been discussed yet and I couldn't find any posts that have. Sorry If I missed it.

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

Re: 0936: "Password Strength"

Postby gmalivuk » Tue Sep 20, 2011 9:33 pm UTC

A doubling of speed every 18 months means a given time is enough to crack a password with one additional bit of entropy every 18 months. At the starting rate described in the comic, there are 16 bits of difference between correcthorsebatterystaple and a 3-day-crackable password.

So, 24 years.

And a password as long as War and Peace can already be cracked quickly, if it's a shitty password. For example, if you use the text of War and Peace as your password, or an equally long string of a's. On the other hand, the Project Gutenberg version of the English translation has about 3 million characters. An equally long *random* password consisting of lower case letters, upper case letters, numbers, and two kinds of punctuation has 6 bits of entropy per character, for a total of 18 million bits of entropy. Which basically amounts to 18 million bits more than any passwords that are currently remotely practical to crack. Which means it would take 27 million years for Moore's Law alone to make a W&P-length random password practical to crack.
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
cjmcjmcjmcjm
Posts: 1158
Joined: Tue Jan 05, 2010 5:15 am UTC
Location: Anywhere the internet is strong

Re: 0936: "Password Strength"

Postby cjmcjmcjmcjm » Tue Sep 20, 2011 9:43 pm UTC

Eebster the Great wrote:And there is no reason a cracker would need to search the full unicode keyspace (which is enormous) when she could just search the ones that can be input with Windows alt-codes.

It would be grand if Windows alt-codes were useful and intuitive, like some of the mac option codes
frezik wrote:Anti-photons move at the speed of dark

DemonDeluxe wrote:Paying to have laws written that allow you to do what you want, is a lot cheaper than paying off the judge every time you want to get away with something shady.

Anonymously Famous
Posts: 242
Joined: Thu Nov 18, 2010 4:01 am UTC

Re: 0936: "Password Strength"

Postby Anonymously Famous » Tue Sep 20, 2011 10:19 pm UTC

cjmcjmcjmcjm wrote:
Eebster the Great wrote:And there is no reason a cracker would need to search the full unicode keyspace (which is enormous) when she could just search the ones that can be input with Windows alt-codes.

It would be grand if Windows alt-codes were useful and intuitive, like some of the mac option codes

I've just added the foreign keyboard layout that I need for practical purposes, and use Left Alt + Left Shift to switch between them. That's a lot more intuitive than the alt-codes.

Of course, for other non-ascii characters, I would need other layouts...

Isil`Zha
Posts: 8
Joined: Mon Aug 15, 2011 2:08 pm UTC

Re: 0936: "Password Strength"

Postby Isil`Zha » Fri Sep 23, 2011 2:05 am UTC

This calculation is utter bullshit.


Why? Because you said so? :?: You are right though... I extremely underestimated the key space size (see end of response to you.)

Did you even read the discussion? The comparison was between a password including a unicode character input via Windows alt-code and the same password with that character replaced by four decimal digits. Nobody suggested every single character in the password should be chosen from the set of all unicode characters; that would take forever to type (and again, would be no more secure than just a string of four times as many digits, and also no easier to remember, as they are in fact the same thing).


You're right, nobody suggested that, including me. Additionally, you seem to have this notion that passwords can be cracked 1 character at a time, which isn't true. Implied by the fact that you think a password with 1 unicode character somewhere in it, has a smaller key space to brute force than a password of all unicode characters. If the attacker knew that the password contained unicode, and their only choice was to brute force, they would be forced to check each character slot for the entire unicode key space (and all combinations thereof.)

Supposing your password is eight completely random printable ASCII characters (and as I understand it they are not in any sense completely random, but I'll give you the benefit of the doubt here) and a randomly chosen alt-code, of which there are a maximum of 10,000, the actual number of combinations is 94^8 * 10000 = 60956893854108160000, or just under 67 bits. Now, that really should be plenty of entropy for a password, but it's nothing like what you think it is.


Wait, what? You been watching too many movies? You can't brute force a PW 1 character at a time - alternatively, you're implying that the attacker not only knows that there's a unicode character, but that they know the exact position of it in the password. It doesn't work that way, they would have to attempt the entire 10,000 character set in every character slot: 10,000^8, or 10,000,000,000,000,000,000,000,000,000,000 possible combinations. Which actually makes the character space of an 8-character PW with unicode characters over 210 million times larger than the key space of a 12 character password with a character set of 94.

More to the point of my "most secure password" - you know nothing about it except the key space of it, everything else was an assumption, and every single assumption you made was utterly wrong.

I agree that if an attacker was trying to brute force your password, it is unlikely they would try the entire unicode character set. Certainly not more than a few characters in length. But who says that they have to brute force your password just because it contains a few unicode characters? It would be very reasonable to think that an attacker would try common password algorithms and append a unicode character on the end. They could also try unicode characters between words or many other possibilities.

Most people probably do not choose randomly from the entire unicode set either. They probably choose only characters that can be typed with alt+XXXX. Also, most people choose characters they are familiar with. As a poster already pointed out, in my example I didn't choose a character randomly. I chose a greek character because I am familiar with them. So a smart attacker could make their attacks much faster. Just adding a unicode character does not make your password "practically unbreakable".


I just wanted to point out here - all of your assumptions are wrong. You assume I don't know how to generate a secure password (with or without the Unicode set) and that led you down a path of assumptions that were all doomed to be wrong. ;)

But it is less likely that an attacker will try unicode characters. And if an attacker is reduced to doing a brute force attack, it is even more unlikely that they will crack your password in a reasonable amount of time. So in practice it is safer than not using them. Never underestimate the cleverness of an attacker though. Do not assume that an attacker will have to resort to a brute force attack. Someone could glance over your shoulder and see the length of your password or a few characters.


At this point the discussion is irrelevant - physical access = full access. Pop in specially built Linux disk, wipe password from SAM, logon to account without even having to put any effort and figuring out what the password was. Ta-da! You're done in 3 minutes.

They could even see that you type on one side of the keyboard more than another. They can search your username on the internet to find out information about you. They might be able to crack a different password using an offline attack, and now that they know your pattern they can use a smarter online attack. Or they could even trivially break it by using a key logger or reading from memory. Or they can reduce the key space using cryptanalysis. Or they can get an SSL certificate signed by a CA and use a MITM attack. So to be as safe as possible always ensure that your password has adequate entropy. And also make sure you take reasonable precautions to mitigate "side channel" attacks as much as possible.


Here's the thing - my entire point was that you a) force them to brute force, and b) Including unicode does two things - 1) significantly increases the keyspace, and 2) most attackers are unlikely to even include the unicode set in a brute force attack, making the password effectively unbreakable in most instances.

Google ( "Isil`Zha" forum ). I will bet you that many of the results are you. If someone tries to crack your password your password isn't uncrackable because it uses unicode characters, but it is if you have a lot of entropy.


See previous statement. ;) Most of this "discussion" has been a strawman of my original post, where I merely mentioned an added benefit, but by no means do I ever consider my password 100% unbreakable.

( "isil zha" forum "password" -"forgot password" -"remember password" ) *cough* spacebattles *cough*


Oh n0es! Not another silly forum account! :P :mrgreen:

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

Re: 0936: "Password Strength"

Postby gmalivuk » Fri Sep 23, 2011 2:11 am UTC

Isil`Zha wrote:
Supposing your password is eight completely random printable ASCII characters (and as I understand it they are not in any sense completely random, but I'll give you the benefit of the doubt here) and a randomly chosen alt-code, of which there are a maximum of 10,000, the actual number of combinations is 94^8 * 10000 = 60956893854108160000, or just under 67 bits. Now, that really should be plenty of entropy for a password, but it's nothing like what you think it is.
Wait, what? You been watching too many movies? You can't brute force a PW 1 character at a time - alternatively, you're implying that the attacker not only knows that there's a unicode character, but that they know the exact position of it in the password. It doesn't work that way, they would have to attempt the entire 10,000 character set in every character slot: 10,000^8, or 10,000,000,000,000,000,000,000,000,000,000 possible combinations.
Wrong. That's only if any or all of the characters are from Unicode. But in the case where I know you're using one unicode character (the case under discussion), not knowing where it is only requires trying it in each position. Which multiplies the quoted number by 9, for each of the 9 positions it could be in.

Ooooh! Three whole extra bits!
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)

Isil`Zha
Posts: 8
Joined: Mon Aug 15, 2011 2:08 pm UTC

Re: 0936: "Password Strength"

Postby Isil`Zha » Fri Sep 23, 2011 2:31 am UTC

Who made that limitation?

Oh, another incorrect assumption. Keep trying I guess, you'll get it eventual... wait, with those assumptions, no... no you won't. Ever. :P

(Also, extra bits are extra bits regardless.)

User avatar
Yakk
Poster with most posts but no title.
Posts: 11128
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: 0936: "Password Strength"

Postby Yakk » Fri Sep 23, 2011 2:51 am UTC

Because when trying to determine the average entropy of a randomly generated password, as a first step you describe your algorithm that generates the password.

Assuming that your algorithm is not known to the attacker is known as "security by obscurity". It has, historically, been found to be reasonably unreliable as a defense.

So gmal went and tried to formally describe your algorithm -- adding a unicode character at some point. From this, he determined how many bits of entropy it added to passwords generated by your algorithm.

So there is the answer to the question:
Isil`Zha wrote:Who made that limitation?
You, on the other hand, seem to be saying "security by obscurity is awesome", at least in your last post.

Security by obscurity has a non-zero value. Often it is negative. It is negative because, by refusing to discuss or tell others what your security measures are, you run into the problem that there could be some huge gaping hole in your security that would be pointed out if only you had spoken to someone on the subject.

I have reason to believe you aren't an expert on what makes a password secure from the simple fact that you are doing things like saying "10,000,000,000,000,000,000,000,000,000,000 possible combinations." instead of talking about bits of entropy in your password system. So, the most likely result of you being obscure and obtuse with your password generation scheme is that you will be generating passwords that are weaker than you think by some margin (what margin, I cannot tell you). Based off past performance of non-experts engaging in security by obscurity, the risk from your own possible incompetence (and if you aren't realizing you could be incompetent, that is even more evidence of danger! People who are reasonably competent at things first learn how incompetent they are, far before they think they are experts) is far higher than the added security of whatever clever variation on password generation you are using.

tl,dr: In a serious and polite discussion of security, "nya nya nya nya nya, I won't tell you" isn't appreciated, useful or all that interesting.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

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

Re: 0936: "Password Strength"

Postby gmalivuk » Fri Sep 23, 2011 3:34 am UTC

Isil`Zha wrote:Keep trying I guess, you'll get it eventual[ly]
No, you're the one who'll need to keep trying. A couple times in your previous post you seemed to be under the misapprehension that anyone was discussing breaking a password one character at a time. Yet, nowhere in anyone's math has anyone in this thread suggested that password cracking works that way.

The fact that you think that is what anyone is saying, therefore, just goes to prove you don't understand the math the rest of us have been doing. The person on the past couple pages who's made by far the most incorrect assumptions has been you.

For example, you say that someone brute-forcing a password they know to contain unicode would have no choice but to try all the unicode characters in all the slots, for a total of 10000^8 (106 bits). And yes, that's true if their goal is to go through all possible unicode passwords. However, if their goal is to efficiently break a likely password, they're going to start out going through the 8-character passwords that include only one unicode character (62 bits). So if yours does happen to include only 1, it could be broken much more quickly than by needing to check all 10000^8 possibilities.

And, once again: this isn't any more entropy than is gained by sticking the character's 4-digit code in the middle of your ASCII password.
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
Eebster the Great
Posts: 3460
Joined: Mon Nov 10, 2008 12:58 am UTC
Location: Cleveland, Ohio

Re: 0936: "Password Strength"

Postby Eebster the Great » Fri Sep 23, 2011 5:33 am UTC

Isil`Zha wrote:Wait, what? You been watching too many movies? You can't brute force a PW 1 character at a time

No, but if you could, you could crack a nine-character all-alt-code password in something like nine seconds on Randall's hypothetical weak remote web server. Obviously nobody is discussing this absurd Hollywood scenario.

Also, please note that, again, you are the only one here discussing a brute-force solution. It is difficult to brute force ANY sufficiently long password, so obviously the assumption is that any intelligent cracker will search a smaller space.

alternatively, you're implying that the attacker not only knows that there's a unicode character, but that they know the exact position of it in the password.

If you read the part of my post where I considered that he didn't know the position of the unicode character, you would realize your error. Instead, you are either intentionally ignoring the actual content of my posts, or are simply too ignorant of the subject to understand what we are talking about. In either case, your arrogance has almost reached a critical level. Can you please calm down and discuss things civilly?

More to the point of my "most secure password" - you know nothing about it except the key space of it, everything else was an assumption, and every single assumption you made was utterly wrong.

So your goal is to boast about the security of your password without telling us how it is generated?

If your algorithm is really as good as you say, you have nothing to lose by posting it. In fact, it would help us point out potential flaws, or if there aren't any, give us a good system to adopt for our own passwords.

If, on the other hand, your algorithm is not nearly as good as you say, you should let somebody here tell you how good it is anyway.

At this point the discussion is irrelevant - physical access = full access. Pop in specially built Linux disk, wipe password from SAM, logon to account without even having to put any effort and figuring out what the password was. Ta-da! You're done in 3 minutes.

. . . no?

This just proves you don't know how to properly password-protect your drive.

spce
Posts: 1
Joined: Wed Oct 19, 2011 6:02 pm UTC

Re: 0936: "Password Strength"

Postby spce » Wed Oct 19, 2011 6:04 pm UTC

Library_hack_enable = 1;

vine9
Posts: 1
Joined: Thu Oct 20, 2011 1:06 pm UTC

Re: 0936: "Password Strength"

Postby vine9 » Thu Oct 20, 2011 1:20 pm UTC

I'm sure it's been done, but here's a simple password generator using the "Password Strength" techniques

http://batterystaple.com/

        Link fine & relevant & interesting.

        gem scout pimps pony

        ~Felstaff

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

Re: 0936: "Password Strength"

Postby gmalivuk » Thu Oct 20, 2011 1:25 pm UTC

spce wrote:Library_hack_enable = 1;
What is it you think that will accomplish, exactly?
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
Copper Bezel
Posts: 2426
Joined: Wed Oct 12, 2011 6:35 am UTC
Location: Web exclusive!

Re: 0936: "Password Strength"

Postby Copper Bezel » Fri Oct 21, 2011 7:05 am UTC

Somewhat off-topic, but I'd never heard of Alt codes before reading this discussion.

Good God, I've never appreciated my AltGr key more. Hell, the Compose key doesn't sound so bad by comparison.
So much depends upon a red wheel barrow (>= XXII) but it is not going to be installed.

she / her / her

User avatar
TheGrammarBolshevik
Posts: 4878
Joined: Mon Jun 30, 2008 2:12 am UTC
Location: Going to and fro in the earth, and walking up and down in it.

Re: 0936: "Password Strength"

Postby TheGrammarBolshevik » Fri Oct 21, 2011 6:10 pm UTC

gmalivuk wrote:
spce wrote:Library_hack_enable = 1;
What is it you think that will accomplish, exactly?

It's the secret code that lets people hack your Runescape account. You have to give him all your gold or else he'll take your account.
Nothing rhymes with orange,
Not even sporange.

User avatar
Vash
Posts: 488
Joined: Sat Jan 22, 2011 9:14 pm UTC
Location: The planet Gunsmoke

Re: 0936: "Password Strength"

Postby Vash » Sat Oct 22, 2011 6:49 am UTC

I can straight up remember any password for quite a long time with memorization repeated over a few days. I think we are underrating human memory.

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

Re: 0936: "Password Strength"

Postby gmalivuk » Mon Oct 24, 2011 12:28 am UTC

I think people who are speaking from extensive experience with folks forgetting their passwords repeatedly probably have more accurate estimates of human memory than you with your one point of anecdotal data.
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
Eebster the Great
Posts: 3460
Joined: Mon Nov 10, 2008 12:58 am UTC
Location: Cleveland, Ohio

Re: 0936: "Password Strength"

Postby Eebster the Great » Mon Oct 24, 2011 3:41 am UTC

^It's really easy to fit a line to a single point, though.

PrinsValium
Posts: 3
Joined: Tue May 03, 2011 12:13 pm UTC

Re: 0936: "Password Strength"

Postby PrinsValium » Wed Nov 02, 2011 1:18 pm UTC

So, anyhow, did anyone pull this one yet?..
badger badger badger badger

Eogan
Posts: 10
Joined: Mon Feb 25, 2008 5:51 am UTC

Re: 0936: "Password Strength"

Postby Eogan » Wed Nov 02, 2011 9:14 pm UTC

So simple text replacement introduces entropy, but not as much as using a string of words?

xkcdt0Ehow2cree8st1=2pbuttwords

xkcd
taught (zero = aught)
me (E = major 3rd of C = the name I call myself)
how
to (dur)
create (you 8 jaffa! Cree!)
strong (1=2 is wrong)
passwords

Why not use both and throw a bunch of puns in to boot?

Of course now I will never use this one, but that's the dilemma inherent in thinking up a particularly clever password. It's similar to the question of what function a silicone BBQ-sauce brush will serve: kitchen utensil or bedroom toy?

User avatar
Eebster the Great
Posts: 3460
Joined: Mon Nov 10, 2008 12:58 am UTC
Location: Cleveland, Ohio

Re: 0936: "Password Strength"

Postby Eebster the Great » Wed Nov 02, 2011 11:56 pm UTC

Well that password has a ton of entropy, but some people might find it difficult to remember exactly (even one wrong capitalization or whatever and you're screwed) or it might take a while to input.

Clearly it's all about balance, like you said.


Return to “Individual XKCD Comic Threads”

Who is online

Users browsing this forum: xtifr and 35 guests