I can’t quite tell exactly what’s being said here. It doesn’t strictly say that each 55-or-fewer-characters password can be cracked, but it does say that passwords of “up to fifty five” characters “can now” be cracked. Not sure exactly what that means if it doesn’t mean all such passwords can be cracked. What would it mean to say that only “some” passwords of “up to fifty five” characters can be cracked? What would be particularly special about that 55 character limit in such a case?
Any password of any length can be cracked, given enough time. All the article is saying is that a particular program used to generate hash dictionaries with GPUs now supports hashing longer words.
Also the article points out that its still a dictionary attack ,but the increase allows phrases to be in the dictionary. One source of phrases was wikipedia.
Of course anyone may use any source for phrases. Bibles, books, lists of quotes, lists of full names (ancestory info.)
Why is the article so prominently mentioning character lengths? What relevance does a character limit have for a dictionary attack? (I speak from considerable ignorance here, so feel free to explain it to me like I’m an intelligent five-year old.)
Re-reading, I don’t see any mention in the article of “longer words.” Can you clarify?
The particular cracking is where you have possession of the encrypted password - perhaps by compromising a server somewhere. You want to find what textual password will match the encrypted one. You know the encryption algorithm. So you start to guess the password. This is going to take a very very long time. But there are optimised systems that will do the work. The big lever in being able to crack passwords in this situation is that most passwords follow a whole lot of well known patterns. This article talks about how one of the cracking programs is now able to attack passwords that are long phrases. For all intents, any sentence that can be found on the Internet, and assembled into a password may be used as input into the program, and will be used as a potential password in the search process. So if you are using a passphrase, there is a good chance it is open to attack. The 55 letter limit is because that is the length some password systems allow, and thus the cracking program now allows the same limit. The news-worthness of the article is because these long passwords are now within the grasp. But it can’t brute force the password (ie guess every possible combination of 55 characters) any time before the sun goes cold, but the much more limited set of passwords that 99% of people actually use are now within grasp, even 55 character long ones.
Why this matters is if a criminal compromises one database, they may crack your password - and then try it on another site. Which is why you never use the same passwords across sites. Not even passwords that are related.
No, a random 55 character string is uncrackable, and barring something entirely unforeseen, will remain so (by brute force attacks, at least). You’ve got just using letters on the order of 10[sup]78[/sup] possibilities, meaning that even if you can check a billion billion possibilities a second, you’ll still need about 10[sup]52[/sup] years to get through with it, which is still so much longer than the age of the universe that I can’t think of any useful comparison.
Only additional structure in the password/phrase, effectively meaning that one is sampling from a much (much, much…) smaller pool, can possibly bring down the computation time enough to make it feasible.
I’ve always wondered, isn’t this advice completely negated by the fact that almost any site will send you new login details to your email address? That way, any attacker actually only needs to know the password for your mail account. Also, the whole practice of ‘security questions’ is probably the best way to lower computational requirements—it probably won’t take long to brute-force the correct answer to ‘what is my favorite color’.
Or your mother’s maiden name. I started using a fictitious one some time ago for that very reason. I don’t know if you could enter “#’!!23” as a color? You also need to consider the likelihood of someone actually wanting to crack your password/phrase. I am not too worried about this site for instance, but more concerned about my bank and credit cards.
Does this article say that all passwords of up to 55 characters can be brute-forced?
No, it does not say that at all. In fact it says "It would have been impossible to use a brute-force attack ".
It is very clear and I do not understand what may be the confusion. It can crack passwords which are 55-or-fewer-characters and meet another condition which is being in the set of passwords being tried. If it is not in that set then it will not be cracked even though it meets the first condition. What is the confusion?
As Vaughn points out, the crack/brute force method works if they have your encrypted password. They may get this by downloading the database of passwords, or eavesdropping on the network line (since most programs will encrypt the password before transmitting it). I have heard very very few cases of the latter, unless it’s an inside job or they are eavesdropping on Wifi. And, to do the former, you usually need to hack into the system as someone with administrator privileges.
There are two ways to hack passwords - brute force and dictionary.
Brute force is what it sounds like - aaaaaaaa, aaaaaaab, aaaaaaac, etc. If you have to separate upper and lower case, and include a few punctuation, there are what - about 26+26+10+8=about 70 characters. 8-character passwords are 70^8 choices. To guess 9-character passwords with take 70 times longer. and so on…
You run the password guess through the same encryption algorithm, see if it matches what you have from hacking. Obviously, if you have a huge database, such as a major corporation or big online site, so much the better, because you can encrypt the guess once and see if it matches hundreds or thousands of passwords. They have modified the programming for graphics cards to use the dedicated chips that calculate 3D graphics to instead encrypt passwords, to process a vast number of guesses every second - plug multiple graphics cards into one system and use them all…
The other technique is “dictionary”. Once a password gets past 4 or 5 characters, odds are there’s a pattern to it - a word or a name. So instead of all possible sequences, just guess words. You can start by guessing the Oxford dictionary; then there are massive lists of common passwords. Of course it’s more complex than that. People can be incredibly clever, do things like not be able to spell, or toss numbers in the mix or at the end, or substitute for letters (1 for I or L, 2 for Z or S, 3 for E, etc.) Then they might toss in (random?) capitalization. Still, even with all these guesses they don’t find every password.
What the people in the article have done is extend this technique to words. To remember and type a really long password, people use a phrase, usually taken from literature or more likely, pop culture. Your password is less likely to be “January Suborbital Denomination” (Actual eveil organization lair voice recognition password from 1970 Mission Impossible episode). It’s more likely to be “She’s buying a stairway to heaven” or “I’llbeback!” or “IchbineinBerliner” (I am a jelly donut). So they used some large online sources to generate a “dictionary list” of phrases to simplify the guesses. Then they still have to apply the capitalization and numbers substitutions against that guess and encrypt it.
What they are finding is that on random tests, using the phrase guesses cracks a large number of previously unguessable passwords. While the number of possible phrases is massive, the number is still massively smaller than random character. They just chose about 56 characters long as an arbitrary upper limit for guesses of passwords. The moral of the story is - don’t use a common phrase, or if you do, mangle it in an unpredictable way.
I recall a workplace where passwords were assigned, and were basically unpredictable 10-character jumbles. That made them so hard to remember that most people had them written on a sticky note on their monitor.
It’s also worth mentioning that most password attacks aren’t looking to crack any particular password, just whichever one is easiest. You’ll have a whole list of encrypted passwords, and then you’ll try encrypting, say “123”, and see if that matches anything on your list. Then you try the same thing for “password”, and “password1”, and “letmein”, and all the other top few hundred or so passwords. By this point, you’ve probably cracked about 10% of the passwords on your list, and so have that many bank accounts you can steal from, or whatever.
It depends on what characters(and what range of characters) a particular company allows for its passwords.
Of course, and as I said, the numbers were for just using letters (and disregarding capitalization); but in any case, they’re really just placeholders for ‘unimaginably goddamn huge’.
So if they have the encrypted passwords in a list they’ve stolen, then they can crack one of the passwords in the list to see how they are encrypted and then crack the rest? Is that it?
Not at all. If you have no idea how something is encrypted, then how do you know if you have actually decrypted it? In the case of the passwords, you would have to test each possible decryption by doing a test login. Slow and attracts attention.
(Decrypted longer texts might be revealed since they might include words or readily recognized data. But no such guarantee with passwords.)
Assume the average word is 5 characters. 56 characters means a 10-word phrase. If there are 10,000 “common” words and names, that’s (10^4)^10 or about 10^40.
However, the number of words which fit together in phrases is substantially less. Pick the top sets of phrases, using the bible, IMDB movie titles, some song lyrics sites. etc.
Let’s say there are 10,000 movie and TV titles involving more than one word. That’s probably high. Let’s say there are 10,000 songs, with 30 lines of lyrics each (or pick first five lines and chorus lines). The King James bible has 783,137 words - about 31,000 verses, assuming people typically pick a verse or the start of it. Add in a few of the classics - Shakespeare - and apply the same logic. We probably have millions of phrases to try, or billions with punctuation, numbers, and capitalization - but 10^9 is a heckuva lot smaller than 10^40. 10^9 guesses is probably doable in a few weeks.
And so on…
To be slightly more technical, the passwords are encrypted by a hash function. For example using the MD5 hash function, if you put in “password” the function returns the hash “5f4dcc3b5aa765d61d8327deb882cf99”, while “password1” returns the hash “7c6a180b36896a0a8c02787eeafb0e4c”.
Say you break into a server and steal the list of passwords, and you know what hash function they are using. They should be stored as their hashes not in plaintext so you might have something like this.
User - Password
sweet chemist - 5f4dcc3b5aa765d61d8327deb882cf99
The Second Stone - 7c6a180b36896a0a8c02787eeafb0e4c
And so on.
You then start testing passwords and see if the hashes generated match any from your list. Once you have a match you then know the password for that user, you then continue testing.
I don’t answer any of those questions correctly, my answers follow password type logic.
No, even if one knows the encryption, that doesn’t mean that you can get from the encrypted data to the plain passwords easily. The principle behind this is that there are problems whose answers can be easily checked for correctness, but not easily found. One example of such a problem is given by hash functions: given some data, its hash is easy to calculate; but given only the hash, the data cannot easily be extracted. Another example, also relevant for cryptography, is prime number factorization: any number can be uniquely expressed as a product of prime numbers; given those prime factors, it’s easy to calculate the original number, but given only that number, finding the prime factors is a hard problem.
So in the example, you have a list of numbers, and what you want to extract is their prime factors (those are the analogue to the user passwords). In general, even though you know the encryption, there is no better way for doing that than systematically searching through products of primes, until you find a number that matches those on the list.
The hash algorithms are usually designed so that it is a heckuva lot easier to encrypt than to go the other way. This is useful because (a) all you need to do for authenticating a user is to hash what they supplied as a logon password and see if it matches the original password hash. (b) decrypting is so difficult that it’s pretty much impossible to “undo” the encryption.
So as others mention, it’s easier to make guesses and see if the guesses match, if you know the encryption process. If you have a thousand encrypted password, this value is multiplied by 1000 since you encrypt each guess, compare it against all 1000 stored hashes.