Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

25-GPU cluster cracks every standard Windows password in less than 6 hours

arstechnica.com

Post reply on HN
Print view View original

71–77 of 77 posts

Re: 25-GPU cluster cracks every standard Windows password in less than 6 hours

#71

Post by apawloski »

phpnode wrote: post #70
apawloski wrote: post #69

Earlier quoted context omitted.

This is purely a thought experiment at this point, but it would actually be a pretty interesting project. I wonder if it's true that longer sentences would be more secure -- or perhaps entropy decreases with larger inputs that give more data to analyze. In the cipher world this would be true, but for O(1) hashes, I'm curious how this could be tested. Edit Ultimately security from these types of attack would be with u…

The problem is that you have no hints about what is correct or not because presumably a one way hash is being used, so even if you get the first 29 words right, you don't know that. Assuming the cracker just uses a wordlist containing 200,000 terms and unsophisticated brute force, this thing could crack a 3 word password in a day and a 4 word password in 800 years[1]. It would certainly be an interesting project, but…

I know we've pretty much made our points by now, but my argument is that brute forcing at this level might be more feasible than what you suggest here (if we assume the sentence is correctly using a particular language).

Say we choose one word from the 200,000 and it's a noun. Then we can make assumptions about the next word (eg it's likely a verb) and immediately the number of options for the next word collapses from 200,000 to a subset of some smaller cardinality. In fact we can use our knowledge of common English to restrict the next options down further -- to only verbs that make sense to this particular noun and that agree with the noun's plurality.

So unlike current password brute forcing, where every character is independent of the others -- thus having exponential complexity -- brute forcing a sentence using current NLP methods could be much less expensive. Perhaps a hierarchical method exists that would scale at O(n log n).

Anyway, this is just fun thinking. You're right that current password strategies are a long way away from making this type of cracking worthwhile.

Re: 25-GPU cluster cracks every standard Windows password in less than 6 hours

#72

Post by SageRaven »

sunraa wrote: post #59
phpnode wrote: post #49

Earlier quoted context omitted.

or you can literally write the whole sentence, which is even more secure and you don't have to remember any special rules, just the sentence itself. Of course it's more typing: Guess what? Back in 2009 I saw a uniquely attired man traipsing round local places with a high number of legs, necks and shirt collars. 136 characters or 14 Gigayears to crack. Wow today I learnt that there's such a thing as a Gigayear.

I just went through the process of changing passwords to sentences. You'd be surprised at how many sites do not allow sentences.

I use a password manager, and I have a unique password per site. I generally try to use an MD5 hash resulting from a "ps waux | md5" at the time of registration. I've encountered sites that rejected this due to lack of upper characters (oracle.com, which then allowed me to use "Abc123"), having no special characters, being too long (often forcing me to down-size to 16 or 8 chars). The worst are sites that silently truncate long passwords (I'm guessing due to code errors), so your password is invalid the second you register and must immediately proceed with a password reset.

Big sites are generally good about allowing long/strong passwords. Many mom-n-pop sites are often hit-or-miss.

Re: 25-GPU cluster cracks every standard Windows password in less than 6 hours

#73

Post by Caerus »

hayksaakian wrote: post #45
Caerus wrote: post #29

Earlier quoted context omitted.

From what I remember of the comic, the point was not the length of the password. The entropy was calculated based on 4 possible words. Assuming ~2000 common English words, the number of possible passwords in that format is 2000^4 ~= 2^44. If the calculation is based on a completely random string of letters it is far stronger at 26^30 ~= 2^141 but it's safe to assume people aren't going to memorize a 30 character rand…

Why would that be true? Wouldn't you have to know in advance that the longer password was only lower case letters?

I'm not sure which part you're asking about. I'm assuming it's that "correcthorsebatterystaple" is only lower case.

I was mainly commenting on the format suggested by the comic - 4 all-lower case words. You could throw in capitilzation, but most people are going to follow some pattern such as capitilizing all the words or the first and last, etc. These schemes only add a couple extra bits. Fully random capitilization would greatly increase the strength but make it nearly impossible to remember.

There are a lot of assumptions in these calculations, chief among them already knowing the format of the password. It's somewhat reasonable to ignore though, because not knowing the format of the password is going to add extra complexity more or less evenly across all formats.

Re: 25-GPU cluster cracks every standard Windows password in less than 6 hours

#74

Post by alephnil »

mikeash wrote: post #60
joshmaker wrote: post #55

Earlier quoted context omitted.

- 8 chars: 84 minutes - 6 chars: 1.2 seconds All of which demonstrates the importance of requiring longer passwords. Also, keep in mind that these are maximum times required to crack a password and not the average times.

The average time to crack will just be half of the maximum, so it's not a big difference (compared to order of magnitude errors, anyway). Still good to point out, though.

I would guess that the letter frequency, digram and trigram frequencies etc are quite skewed compared to random. Just by taking that into account, you would crack an average password much faster than you suggest by trying the most likely passwords first. There are plenty of already cracked passwords to draw statistics from.

That in addition to traditional dictionary attacks.

Re: 25-GPU cluster cracks every standard Windows password in less than 6 hours

#75

Post by pserwylo »

jasonwatkinspdx wrote: post #46
rjempson wrote: post #32

I'm not sure there is much significance to this article. It points out "The technique doesn't apply to online attacks, because, among other reasons, most websites limit the number of guesses that can be made for a given account." Same applies to Windows.

Offline attacks matter. The last few years have seen a continuous stream of high profile account database leaks. There are now some 1 billion known real user selected passwords that are readily downloaded from any of a number of shady sites. It is irrational to assume that password database leaks won't continue. The hashing scheme and salting matters less and less, as the total entropy humans can conveniently recall…

I saw a talk on Mozilla Persona [0] the other day from one of the devs. I like the idea of these decentralised authentication systems. I was (and still am a fan of) OpenId too.

There is no practical reason that website operators need to know that a user typed in the right password, only that they are who they say they are. Anything which is able to prove this (to a satisfactory level) with the least amount of information being stored by the website is good in my books.

[0] - https://www.mozilla.org/persona

Re: 25-GPU cluster cracks every standard Windows password in less than 6 hours

#76

Post by phpnode »

apawloski wrote: post #71
phpnode wrote: post #70

Earlier quoted context omitted.

The problem is that you have no hints about what is correct or not because presumably a one way hash is being used, so even if you get the first 29 words right, you don't know that. Assuming the cracker just uses a wordlist containing 200,000 terms and unsophisticated brute force, this thing could crack a 3 word password in a day and a 4 word password in 800 years[1]. It would certainly be an interesting project, but…

I know we've pretty much made our points by now, but my argument is that brute forcing at this level might be more feasible than what you suggest here (if we assume the sentence is correctly using a particular language). Say we choose one word from the 200,000 and it's a noun. Then we can make assumptions about the next word (eg it's likely a verb) and immediately the number of options for the next word collapses fro…

I agree that you could potentially reduce the search space based on rules, but English especially is not well known for it's adherence to rules, see http://en.wikipedia.org/wiki/Buffalo_buffalo_Buffalo_buffalo...

Conversations like this are why I come to hacker news.

Post reply on HN