Slashdot Mirror
Cheap GPUs Rendering Strong Passwords Useless
StrongGlad writes with a story at ZDNet describing how it's getting easier to use GPU processing against passwords once considered quite strong.
"Take a cheap GPU (like the Radeon HD 5770) and the free GPU-powered password busting tool called 'ighashgpu' and you have yourself a lean, mean password busting machine. How lean and mean? Working against NTLM login passwords, a password of 'fjR8n' can be broken on the CPU in 24 seconds, at a rate of 9.8 million password guesses per second. On the GPU, it takes less than a second at a rate of 3.3 billion passwords per second. Increase the password to 6 characters (pYDbL6), and the CPU takes 1 hour 30 minutes versus only four seconds on the GPU. Go further to 7 characters (fh0GH5h), and the CPU would grind along for 4 days, versus a frankly worrying 17 minutes 30 seconds for the GPU."
Isn't the speed of computation pretty irrelevant if there's a delay built in to the challenge/response routine?
And any system worth its salt (crypto-hashing joke) won't allow that many attempts against any external or internal authenticator and will NEVER expose its password hashes.
Seriously, if someone has your password hash, it's game over anyway and it doesn't matter if it takes 2 weeks or 2 months to guess the passwords. And if they don't, then you shouldn't be letting them try several BILLION attempts at guessing a password anyway.
Go further to 7 characters (fh0GH5h), and the CPU would grind along for 4 days, versus a frankly worrying 17 minutes 30 seconds for the GPU."
OK, so go to 15 characters. Using a password generator I can go as far as I like. Using some sort of password bank program, I can store passwords / phrases of any complexity and use copy and paste, thus having only one strong password to remember.
So, what am I missing? (And lets keep it on topic, folks).
Faster! Faster! Faster would be better!
this is why you use them.
...to 1min/try and it will take up to 3.3billion minutes to guess...
It is well known that if someone gets your hashed password, it is as good as cracked. 17 minutes vs 4 minutes is irrelevant.
On a live system, it is quite another story. You can't just remotely try 3.3 Billion passwords per second.. You'll be locked out after 10 attempts or so.
My passwords(for important things like the disk encryption one or my work email) are at least 13~15 characters long, including Upper-Lower cases, numbers and special characters, and no dictionary words. Now I did my part, so how about the people on the server side ?
The answer to this kind of attack is to hash passwords using hash functions that take a bit more time to compute.
Is my five letter password more secure if the salt is 15 characters long?
Or am I misunderstanding the nature of the attack and of hashed passwords?
[Fuck Beta]
o0t!
From TFA: "It gets worse. Throw in a nine-character, mixed-case random password, and while a CPU would take a mind-numbing 43 years to crack this, the GPU would be done in 48 days."
Hooray, you can crack an NTLM password in like five seconds! Too bad Windows has preferentially used Kerberos since Win2K, which means that pretty much any in-practice Windows network you'd like to hack in to is using a real security scheme.
I mean, really. This article isn't about how much faster a GPU is than a CPU for hash cracking (after all, four days to reverse a hash is still unacceptable, and that's brute forcing it and not using one of the widely available NTLM rainbow tables), it's about how much NTLM sucks and Microsoft should have never contravened the first rule of cryptography and tried to roll their own.
Shameless plug follows...
Seriously, once you're free from having to remember your own passwords, you can make them as long and complex as you like, and you can use a different *truly random* password for every login, so one compromise won't lead to others. There are freeware workalikes, but none that match 1P's feature set (syncing, browser auto-fill/change plugins, etc). Highly recommended.
This is really a Windows problem. Windows uses a simple, fast hashing function (I think some version of HMAC). This means that an attacker can churn through many passwords very quickly (apparently billions per second per the article). You should really use a slow hashing function that takes around 0.1 to 1 seconds to calculate one hash on the server. Even a GPU will then take very long! Plus don't forget salt (different per user) against rainbow table attacks, plus key strengthening. Something like bcrypt is pretty good, but scrypt is probably even better as it does not only require a lot of CPU time but also significant memory (making dedicated hardware crackers much more expensive).
For now, you should a) use more characters (say, 12) and b) include symbols in the alphabet. Assuming 25 symbols, you'd then 1.88*10^23 possible passwords already (that's not counting shorter ones!), which would still take your GPU about 1.8 million years to go through.
So for now, we're safe - although computers will get faster, and it's interesting to see what'll happen in the future. Will we ever be forced to remember complicated 30-character passwords because everything else is unsafe? Will we want to - will we come up with something better than passwords so we don't have to?
Give it a 4 years and your digital watch will do the lot in 3 femto seconds, computing power has always been increasing over time. Don't blame GPU's for being well made! Most of this stuff can be stolen at typing point by microwave hacking anyway ...
The purpose of existence is to make money.
A 6-7 letter password only using letters and numbers is NOT strong.
It would be trivial to cover it with rainbow tables and have near realtime cracking even without GPUs.
_Not weak_ would be 10 letter+, with a salt. Would make brute forcing not really that easy anymore...
HI O WISE PRINCE. WHT TOOK U SO DAM LONG?
If only storage technology had kept up with GPUs! Instead of being limited to 8 character passwords because of stringent storage limitations, we could use entire passphrases that might be both fairly easy to remember and far more challenging for password guessing. But I guess we'll have to wait for some sort of technological breakthrough...
Don't think of it as a flame---it's more like an argument that does 3d6 fire damage
Does anyone really use less than ten character passwords anymore?
Ten is the minimum as far as I'm concerned. It IS NOT that difficult to remember a string of ten characters. Hell, even twenty isn't that bad. Yes. TWENTY!
Yeah, brute forcing NTLM login passwords. What's next, brute forcing your bank's 4 digit pin code? Please, give us a break. From wikipedia on NTLM: http://en.wikipedia.org/wiki/NTLM
Microsoft no longer recommends using NTLM in applications:
Implementers should be aware that NTLM does not support any recent cryptographic methods, such as AES or SHA-256. It uses cyclic redundancy check (CRC) or message digest algorithms (RFC1321) for integrity, and it uses RC4 for encryption. Deriving a key from a password is as specified in RFC1320 and FIPS46-2. Therefore, applications are generally advised not to use NTLM.
So, if 6 chars takes 4 seconds and 7 chars takes 1050 seconds then it seems to suggests it's scaling at 256x per character. So are we talking ~260,000 seconds (3 days) for 8 characters?
See? Hashing passwords is overrated!
Yours sincerely,
Sony
If you're a hacker, my bet is you have at least 10 more friends with recent gaming rigs... And guess what? The problem is embarrassingly parallelizable. 4.8 days for a 9 char password(worst case, btw)
Comment removed based on user account deletion
So, make password hash computation more expensive:
http://www.tarsnap.com/scrypt.html
Just make the hashing algorithm slower. For example, let's say you use md5 to hash the passwords. Hash the password 1000 times with md5 instead of just once. This will increase the time it takes to crack the passwords by a factor of around 1000.
Since GPUs are rendering traditional passwords insecure and obsolete, why not go with a broader usage of smart cards? Also, build in mechanisms to deny IP addresses from machines that are attempting to use brute force. I do it with OpenBSD's PF. After so many failed attempts over a period of time, the IP gets blacklisted. After 24 hours, the blacklist gets purged.
Self-explanatory.
http://www.wimp.com/strongpasswords/
The NSA guy who needs to spend 43 cpu years across a farm of, say, 1000 servers in order
to get a password in half a month probably has to write an application to his boss.
The NSA guy who needs to spend 48 cpu days on the same farm in order to get a password
in a little more than an hour can probably just go ahead.
(And, yes, servers in farms often do have GPUs in order to expose this kind of specialized
performance.)
Comment removed based on user account deletion
Not any more, you're not.
So the TFA proves that password cracking is exponential in the length of the password, and that GPUs cut down on the rather large constant in front of the exponent. This still does not eliminate the fact that each digit added increases the cracking time exponentially. In other words, use a longer password. Of course, NTLM is a farce since it only hashes 8 byte chunks, so you can't up the cracking time by more than X^8. The moral of the story here is that GPUs are faster than CPUs (for some specialized applications), yet you can still overwhelm them using a longer password. The other moral is that NTLM is an utter failure, but we all knew that.
If anyone really cared enough, they could build a single-purpose circuit to calculate hashes and compare with the hash file. With enough money invested, you could easily beat any GPU by a couple orders of magnitude. That still doesn't make this news worth discussing as the other side can up the ante by adding to the password length again (among many other things already mentioned such as salts).
Government is not reason; it is not eloquent; it is force. Like fire, it is a dangerous servant and a fearful master.
You're aware of course that this is an offline attack? The way it works is you snag a hash as it goes across the wire (via man in the middle, client installed malware, or some other attack) then you take that hash and you calculate on your cracking machine passwords until you reach a password that matches that hash. Then the attacker takes your password and goes and logins with it. The server never sees 'billions passwords per second'.
8-character passwords were strong enough for Unix thirty years ago, but that was a long time ago in Moore's Law cycles; I've got wristwatches faster than that PDP-11. It's annoying how many systems still seem to use them.
For systems that do passwords interactively, you're not going to get the same brute force speed, but you're still exposed to automated attacks - using a CAPTCHA in addition to the password can help prevent them.
Bill Stewart
New Fast-Compression-only CPR http://preview.tinyurl.com/dy575ks
it seems to me, if your password is random, mixed-case alphanumeric, and fairly long, there is an added layer of security against a brute-force hash attack like this. that being that the incorrect hashes will just be jumbled strings of letters and numbers... but the correct password will be, as well. how would such an attack differentiate the valid password from the invalid in this situation?
-It is by will alone I set my mind in motion.
So if anything, this reaffirms my belief that biometric authentication is the way future security measures should go. Of course dual layer: biometric authentication as well as a password, but biometric authentication none the less. But I've known about this for years... not really anything new. And a 15 character password with upper and lower case letters, numbers, and symbols will still take forever on either.
3m are going to introduce a larger post-it-note
Cheap GPUs Rendering Strong Passwords Useless [...] a password of 'fjR8n' can be broken [...]
"fjR8n" is not a "strong password" by any definition, unless you think password crackers are limited to dictionary attacks. 5-character rainbow tables are fairly easy to obtain, and even a brute-force attack is trivial on something that short.
All my passwords are 8 characters or longer; important ones (login, e-mail) are 16 characters or longer. Really important ones (used to encrypt sensitive business data) are over 24 characters long. That doesn't even include the salting that most systems add (although a tailor-made cracker can make that irrelevant).
The problem with NTLM has been known for some time, but it is not just NTLM. It is in fact any challenge response protocol. Check this slide deck presented at the IETF in 2005: http://www.huitema.net/talks/ietf63-security.ppt. The punch line is simple: don't rely on challenge response protocols! If the attacker can see both the challenge and the hash, and if the password can be remembered by the user, it will probably be cracked.
Try reading the post you are replying to...
The title of the article is extremely misleading.
I don't really care that someone can break short passwords generated via MD4. MD4 is very broken. NTLM is essentially 1992-era technology that was later picked up by Microsoft, who now deprecates its use.
When a GPU can break 15-character AES256 keys, then I'll start to worry about the security of my 24-character key.
Am I part of the core demographic for Swedish Fish?
Hold on, I just have to turn off all my bitcoin miners first...
What kind of incompetent fool would still use such a pathetically weak password hashing scheme?
Even for Slashdot, this is a little pathetic: the link is to a ZDNet article, which regurgitates a PCPro article, which in turn regurgitates a blog post by the guy who actually ran the tests, Vijay Devakumar. And here's Ivan Golubev, who wrote the cracking tool.
Still, ZDNet's advertisers thank you for the hits!
It is well known that if someone gets your hashed password, it is as good as cracked. 17 minutes vs 4 minutes is irrelevant.
Yes. Now do that calculation again for a 12 char password.
(I use LastPass. I remember one insanely long password for my vault, and then I have one new 12-18 char long password for each new site)
It's the power of modern GPUs that's worrying you? Really? What you should be worried about is the security software you're using that uses md5 for password hashes. Use a more expensive algorithm - bcrypt, or better yet, scrypt. And if your software or OS uses md5 for passwords in a situation that's vulnerable to local brute force hacking... upgrade!
hashes don't normally "go over the wire". They don't for web logins, they don't for remote logins. They reside in a file on the host. If you copy that hash file from machine to machine by insecure means that's your problem, not something a good admin does. Encrypted file copy is a nice feature of the ssh/sftp/scp suite. E
Does igashgpu attack the NT hash (MD4) or the LanMan "hash" (DES-based)? I'm guessing the former, but the latter is much easier to attack. With the LM "hash" you can break any length password almost instantly using rainbow tables. (But I think maybe MS has LM hashes disabled by default in recent versions of Windows, due to its severe weakness.)
You should check out gibson research's page on password lengths, its over at http://www.grc.com/haystack.htm it's a good read.
Right, so it will take 10 black hats a work week to crack one password. Given the ratio of black hats to usernames, I wouldn't worry too much unless you are person of relative interest.
Also, they have to get the password file (or equivalent) in the first place.
http://hashcat.net/oclhashcat/ runs numerous tools for this and with some users GPU rigs going totally insane: 4 x ATI Radeon 6990 throwing MD5 hashes out @ 45.7 Billion/sec, that's mixalpha-numeric password of length 8 in 1 hr 20 mins and then we can start on the dictionaries / hybrib-dictionaries / case-mutations / etc. The way passwords are used / stored is becoming broken by design.
If we're not expected to RTFA, how do you expect us to RTFC(omment)?
Browsing at +1 - no ACs, I ignore their posts. So refreshing!
Not exactly anything new here. Generate your passwords using a program or using a sequence only you know.
I can generate passwords with as many characters as I want to, just from my head, using sequences that would confuse even someone with a great memory watching you put the keys in.
You can use the same sequence with a unique ID creation system too, such as a simple "split alphabet in to 3 groups, for each letter of a program / site / whatever, output the number of whatever group the letter is in"
Sequences could include inserting a number sequence inside a first-letter-caps quote from whatever with a stepping value only you know. This could be repeated with several different step sequences to create stupidly complex passwords well in to the 100 characters with a decent quote, a large-ish number, some random word and the unique ID sequence above. Easily.
Now that I read it, hashing, however, is the bigger problem if someone gets a hold of that from DB leaks or stolen hardware.
In all honesty, stronger, slower hashing should probably be used and better ones created considering how powerful hardware is these days.
And with quantum computers literally on our doorsteps right now, those will become a reality for brute-forcing large number sets sooner than you think.
Adiabatic Quantum Computers, while not the right kind, is still one form of the overall goal.
As more of these are built and researched, no doubt other methods to create the kinds that can deal with these large number sets will be here and if we aren't ready, it won't be a fun time at all..
Also, what the hell is the deal with the mess of buttons and AV-navigation bars on the submit comment section?
It is well known that if someone gets your hashed password, it is as good as cracked. 17 minutes vs 4 minutes is irrelevant.
Bullshit. It is well known by people who don't know what they're talking about, which includes TFA.
Do you seriously think that in the age of bitcoin we can't make a hash function that is arbitrarily difficult?
Use an adaptive cryptographic hash function: bcrypt, PBKDF2 or scrypt. The key feature is a tunable stretch factor that basically sets the number of rounds of hashing. Set that factor (by means of a simple timing loop) to require 1 second of CPU time (or GPU time or whatever) to hash.
Now the simplest 8 character A-Z password will take an expected 3,311 years to break. You'll obviously want a safety margin, and will expect them to have more computing power a few years down the road. But you can tune the stretch factor to ensure that a reasonably strong password is perfectly good against offline attacks.
This article spells it out:
http://www.baekdal.com/tips/password-security-usability
Too bad most sites are too stupid to allow a long enough password. I'll take a 16-character pass-phrase with all lower case + whitespace over a hard to remember 8 character one anyday.
Cracking one password may be enough for a larger attack even if the target user is not particularly high priority. So, maybe the hackers gain access to the shadow file of some other system, and correctly surmise that a low-level employee at the target company uses the same password for their work account as for whatever other system was compromised, and now they have access to the target company's internal LAN.
The real answer, IMO, is to start moving toward cryptographic authentication methods, and remove the problem of passwords altogether.
Palm trees and 8
A more informative link should be included, like:
http://www.openbsd.org/papers/bcrypt-paper.ps
so nerds not in the know can understand how silly the article is. NT hashes are a joke and other than pointing out how bad all the non-bcrypt ones are. It is not all that useful to work on GPU brute forcing for poorly designed systems... (other than to make a point or to aid in exploitation of them.)
You can use shorter passwords if the hash algorithm is sound. dictionary attacks will work regardless but once you are into using brute force your password could be short if it takes a long enough amount of time to cover the domain. bcrypt "scales" to as slow as needed ( I feel odd using "scales" in this way... ) one could make it so expensive that searching the space for short passwords would be too costly.
Democracy Now! - uncensored, anti-establishment news
Because the crypted passwords never get grabbed for cracking offline.
Never all in all of computer security history.
All those stupid passworded files you download from rapidshare/megaupload/etc. can be brute force opened without having to jump through the maker's stupid loop holes.
How long would it take if the authentification system limited ot to one attempt per hour?
It is well known that if someone gets your hashed password, it is as good as cracked.
Say what now? My passwords are 32 characters long, contain upper case lower case numbers and symbols, and are easy to remember. That creates a search space of 1.86 x 10^65 possible passwords. Have fun with your measly 3.3x10^9 passwords per second. The article considers a 7 character password to be secure. It isn't. Every additional character increases the search space by a factor of 95. Length matters.
+1
Cryptographic hash functions are optimized for speed and small implementations (and security of course). To use them without iterations is stupid for passwords.
Any decent site won't allow you to make multiple attempts at guessing a password withing a certain space of time - i.e. doubling the lock out time, each time you fail.
So billions of guesses would end up taking eternity.
Phrases are not as secure as one might expect, it is not equivalent to a password several dozen characters in length. In some ways it is like substituting words for letters, a seven word password is only more secure than a seven character password in the sense that there are more words in a person's vocabulary than they are letters in the alphabet. Perhaps a "practical" improvement but not even approaching "pretty much unbreakable", even with substitution. In short, all the things that make passphrases easier to remember works in favor of the cracker. Frequency and correlation are a factor. In something analogous to a dictionary attack, given a phrase of a certain number of characters one might try famous quotes, passages, etc that match that length.
FWIW, phrases were often used to test the configuration of German enigma encryption machines during WW2. The British at Bletchley Park had some success in discovering unknown phrases and that was with 1940s technology. One German operator was discovered to be using the German equivalent to "mary had a little lamb". Better yet, he used that phrase every morning despite his training.
Oh noes! This means that my 12-character password can be brute forced in (an average of) just 39,000 years!
If only there were some way that one could, I dunno, modify that password somehow during those millennia, thus forcing the cracker to start over.
It's both factually incorrect and just plain stupid to call a 6-character password "strong." And memorizing a handful of 12-character passwords is no harder, in a practical sense, than memorizing a handful of 10-digit phone numbers.
Sensational alarmist crap at its best.
The title of the article is extremely misleading.
Isn't that a requirement for being on Slashdot?
Same shit with all the scare on rainbow tables. I remember the hype of "It can crack any password in seconds!" Then I found out it meant any LM password, which has some real limitations on it (14 characters total max, as two 7 character hashes, no upper and lower case). Ahh, not so impressive then.
Same shit with NTLM. Worlds better than LM, but not current. Wake me when it is a threat vs NTLMv2, which is what Vista and 7 use exclusively unless you manually change security policy (and XP and 2000 support it).
Then there's the fact that they are talking about short passwords. Security comes in length and it goes up drastically with each character. They are crowing on about how easy 7 character passwords are. Ok, fine, try 14 then. It isn't like if 7 takes 18 minutes 14 takes 38 minutes. It is more like if 7 takes 18 minutes 14 takes years.
Also to make a long, secure, password doesn't have to be that hard. Just take a phrase and modify it a bit. Say you decide the phrase "There can only be one," should be your password. Do something like "Th3r3 can only be #1!" Fairly easy to remember, yet you have to exhaust a massive space for a brute force attack.
Finally, all this is an attack against the hashes. While we want hashes to be strong, let's face it they are a last line of defense. This is a situation where someone has already gotten in, gotten high privileges, and stolen that list. This has no relevance to dealing with breaking in to a random system remotely.
Pretty much this is just fear mongering. Yes, you need to use longer passwords these days. So do so. However a short password really isn't as bad as they make it seem. The risk they are talking about here is only if someone happens to get the hash file from a system with NTLM passwords stored that you use a short password on. Given that the only system that qualifies for that for most people is their home desktop, if they get it the hacker has owned your system already (you have to have admin to get the SAM file) so it doesn't matter.
All the break-in attempts I've ever seen happening to one of our systems has only tried running through a list of users / passwords that are, bluntly, pretty dam' obvious choices. That none of them has ever succeeded on any of our user accounts tells you nothing about the strength of the individuals' passwords (policy set by the CIO's IQ/memory abiliity: 6 or more letters+numbers)
All it tells you is that the amateurs who run these scripts get a high enough hit-rate from rest of the internet to keep them happy - and not wanting to try anything harder. My personal belief is that if we did ever get hacked, the source would be internal or through information leaked by a user from social engineering, not from some script kiddie with a room full of GPUs, throwing off enough heat to make the cops think they've got a marijuana farm in the building.
politicians are like babies' nappies: they should both be changed regularly and for the same reasons
... My passwords are 32 characters long, contain upper case lower case numbers and symbols, and are easy to remember. That creates a search space of 1.86 x 10^65 possible passwords. ...
That sounds like you are using some words. If so the search space is smaller than you believe. Any time you can use the phrase "easy to remember" you no longer can use the mathematics of random permutations. Think in terms of tokens not characters, with a token being a word or a character. A token that is a word may be more secure since there are more words in a vocabulary than letters in an alphabet but a five character word is far less secure than 5 random characters.
This problem is trivial to defend against. Simply employ key stretching. You can make it take as long as you want.
NTLM hashes are calculated on the host and submitted across the wire to a server in response to a request for authorization.
If you're a hacker, my bet is you have at least 10 more friends with recent gaming rigs... And guess what? The problem is embarrassingly parallelizable. 4.8 days for a 9 char password(worst case, btw)
But your friends have to stop playing games for 4.8 days. Good luck convincing them of that because you want to crack a single password. ;-)
You are assuming a lot of knowledge about the password scheme for an attack. This may apply when dealing with secrets of national security, this does not apply to random systems on the Internet. Yes, a pass phrase could potentially be weakened by some cryptanalysis against the person. Knowing something about their vocabulary, the movies and literature they like, dates, addresses, and other things significant to them, etc could be used to load a system to search a smaller space.
However that isn't the kind of research someone is going to do. You and your data are not worth that kind of money. Hackers are not going to spend tons of time researching a target like that.
Also you have to remember that you slow down tries a lot if the logic gets more complex. These brute forcers are fast because they are simple. It is "Pick next valid combo, hash it, compare to hash, if it doesn't match, repeat." If you start having tends of thousands of cycles of logic to generate your guess, that slows shit down a ton.
Always be aware of the threat you are trying to protect against. The measures the government needs to go to to protect nuclear secrets are not the same ones you need to protect your lolcats photos.
Think of it in terms of physical security. Think how flimsy your door lock is, how easily a battering ram could take it out. Think how easily your windows are broken, and so on. Should you secure all that? Should you live in an underground bunker, guarded by marines? No, because you've nothing worth that kind of effort to protect. You are sensible about what protection you need.
Nowdays, once your hashed password is exposed (e.g. someone posts a database dump of your favourite forum somewhere), it is unlikely that the system where it was stored was not completely compromised. It is unlikely that the attacker could not grab or modify all personal data / other information that was stored on the system. He can gain entry to the system using your account by modifying your password, so 0 security left there to compromise by recovering the plaintext password.
...
The only benefit he or someone else could gain from cracking your password would be to try it elsewhere in case you are stupid enough to still use the same password for several different accounts... So: don't do that, use long random passwords stored in a safe place (in your password-protected browser if you must) and you might as well stop worrying about the next generation of rainbow tables or 100 times faster GPUs etc.
"I love my job, but I hate talking to people like you" (Freddie Mercury)
I use a 4 character password to slip out the back door of this arms race.
Right, so it will take 10 black hats a work week to crack one password. Given the ratio of black hats to usernames, I wouldn't worry too much unless you are person of relative interest.
Wait, aren't we looking at this wrong? Yes, if the black hats only had one password to crack, it would take this long. But if they've gained access to the entire password hashfile, they have many passwords to crack, and they're just trying to get lucky. Each time they pull a hash from a rainbow table, they have the equivalent of [number of users] lottery tickets. Successfully cracking one password would give them access to the machine, and no matter what level of privilege that account has, gaining any kind of access is a huge step.
I guess what I'm saying is, from the perspective of one person who wants to protect their individual account, yeah, you might not worry too much. But if you're the guy in charge of protecting the server itself -- and by extension, the security of every account on that server -- then worrying seems justified.
Breakfast served all day!
Wouldn't changing to SHA-512 from MD5 make this a moot point ? What if the stored hash was the MD5 hash of the SHA-512 hash of the actual password ? Or, the Md5 of the SHA-512 of the MD5 and so on.......
SHA512 takes less time to calculate than MD5. You'd be making brute force easier event though you are adding more bits!
bcrypt, scrypt, and pbkdf2 allow you to adjust the of iterations necessary to calculate a password. If you want you can crank up scrypt where it takes several seconds of pegging your server cpu to authenticate a password. A GPU could still accelerate that, and if it was a thousand times faster than a CPU (it's not) it would take a year to walk through 3 billion guesses instead of doing it in a second.
“Common sense is not so common.” — Voltaire
Do you seriously think that in the age of bitcoin we can't make a hash function that is arbitrarily difficult?
All right, strong enough with the spurious bitcoin references. We don't care about your silly toy project, no matter how many times you choose to mention it.
Wow, until you came along, I couldn't visualise the difference between a 6 letter password and a 7 letter one.
Thanks!
This could be more of an issue for something like a zip file, 7-zip file, truecrypt volume, etc. Something where the encrypted data is local, and protected by a password. Think of a stolen DVD or USB hard drive which you had put stuff on.
In such a case, the attacker can hook the device up to their own computer, which will NOT enforce any artificial delays. In such a case, the only thing protecting your data would be the complexity of the password itself, and of the algorithm from which an encryption key is derived from the password.
You assume the only use of passwords is for "online" systems where an artificial delay can be imposed by the server.
What about encrypted files? How are you going to impose a delay on someone trying to decrypt the file on their own computer, potentially using different software than what you used (e.g. the software you used might impose a delay, but maybe they have written their own implementation, or modified an open-source version, to skip the delay and continue full speed ahead)?
I can break a password of 'fjR8n' in less time than the GPU.
fjR8n
see?
All this is talking about NTLM password hashes, the algorithms used by modern unix systems are a lot tougher and even with modern GPUs, still very slow to crack...
More importantly, NTLM password hashes are plaintext equivalent, so you can use them without having to crack them at all (google for pass the hash), so cracking them is only for amusement value anyway.
So the problem is not so much GPUs, its more to do with windows systems having extremely weak methods of storing passwords.
http://spamdecoy.net - free throwaway anonymous email - avoid spam!
Do you seriously think that in the age of bitcoin ...
I think there's a whole bunch of people with cheap GPU's out there in the age of Bitcoin.
"I'm not much interested in interoperability. I want substitutability. I want to be able to throw your software out."
'You can't really prevent these [brute force] attacks: nothing prevents an attacker to just try all possible keys and look if the database decrypts. But what we can do (and KeePass does) is to make it harder: by adding a constant work factor to the key initialization, we can make them as hard as we want."
To protect its database (of passwords), the program actually performs N rounds of AES encryption, with N being a large number of your choice, chosen so that these rounds take "a lot of time", say 1 second. This way, the attacker will only test 1 password per second.
Does this make sense ?
Nobody is trying to brute force a remote login--your account would be locked after a few failed attempts anyways. This is only a valid approach if you've somehow got your hands on the hash file. More and more we see people like sony having plaintext passwords or Gizmodo have unhashed (reversible encryption) passwords. The sites that have your password properly stored as a hash are not the ones getting hacked in the first place.
I though the use of delay loops went away with computer games of the 80's. Besides, as soon as a faster computer comes out, the old algorithm is useless for security, and the new algorithm is so slow that it's useless on the old computers. Same problem that led to the move from DES to salted DES to MD5 to SHA512 to... You're chasing your tail with key stretching.
require 1 second of CPU time (or GPU time or whatever) to hash.
if you have a login system on a e.g. desktop machine there is usually only 1 user logged in anyway the 1 second delay will not really bother them, and make that ahsing system a nice secure password storage. .... And then theres those that do not use Javascript.
But I wonder how you would use a hashing algorithm that takes 1 second to compute a password has in an actual production website. You could only support 60 logins per minute, and then you would need a dedicated box that only calculates hashes, and not have any other software on that box.
You could do the hash calculation client side with javascript, but then you have issues with those that use mobile devices that just do not have the raw processing power of an 8 core opteron and make those users wait for lets say 10 seconds to log in, which of course will not make them click refresh , and have them stuck and no able to log in, or they give up
Thus,unless I missed something on how you would deploy such a "slow" hashing algortihm, I do not see it as a practical solution, even though it makes brute force attacks against the hashes quite impossible. I dont see it scale to a level that a moderately sized website would have any use for it. Since those are the juicy targets that will bring many more password hashes then a desktop machine, slow hashin algorithms are nice, but cannot bring and aditional safety to your passwords
Quit pushing the solutions on the users. You don't need to use longer passwords to make it harder to reverse password hashes, all you need to do is salt the passwords and use iterative hashing (key stretching) to make each guess take longer. In a well designed system, it should take 200 days to brute force passwords for 1000 users, assuming all users had three character lowercase alphabetic passwords. This is base on tuning the number of hash iterations so that a guess takes 1 second to verify.
Taking the information into the article into account, there is a new wrinkle. The application will be using the CPU to compute hashes an attacker might use a GPU based approach. The numbers for the article show the GPU to be about 1500 times as fast as a CPU, getting the horrible passwords from the previous paragraph in about three hours. However, those were absolutely horrible passwords. By tweaking the password policy so that passwords must be five characters long (still no requirement for mixed case or non-alphas), we could still see passwords take 1 second to be verified in the application and the 1/1500th of a second for the GPU based attack would still require 91 days to complete brute forcing the entire database. Of course, nothing will help the users with passwords that are at the top of the dictionary. The best part about iterative hashing is that if we have the same discussion twenty years from now, we simply tweak the number of hash iterations and we get exactly the same results.
What fascinates me about this scenario is how many collisions can be found during this brute-force process?
It's not that simple. Cryptography is an asymmetric game: you always have to assume the attacker has orders of magnitude more computing resources than the target. Cryptography works because we can (usually) find problems that get exponentially harder and harder to crack. For instance, let's say you just want to encrypt something. A block cipher with a 64-bit key is just on the edge of being brute-forcible today. But, as a general rule, you could use a block cipher with a 128-bit key and it should only be half as fast as the 64-bit cipher (note I said this is a general rule, there are number of factors that influence speed). A 128-bit block cipher is 2^64 times more difficult to crack than a 64-bit block cipher. So, the target can make something 2^64 times more difficult to crack by just doing twice the work.
Your proposed solution just grows linearly, not exponentially. If you iterate SHA-1 10,000 times instead of just 5,000 you're also doing twice the work, but this time you've only made your password twice as difficult to crack. If you can suddenly start doing twice the work you did before, you have to assume the attackers can as well.
Yes, iterating hash functions buys us more time, but this is a game that targets can't win. Plus, you're ignoring all of the problems associated with moving to higher iteration counts. Probably first and foremost is interoperability. There's a massive application base out there that just uses MD5 or SHA1 with little to no iteration. It's not easy for software like Windows to change. I think it wasn't until Vista that Microsoft stopped storing a LAN Manager hash of users' passwords, which made then trivial to break. That's been known to be bad for a long, long time. Plus, in most web-based applications its not the client that does the hash operation, its the server. While your new Core i5 processor could probably easily handle bumping up the iteration count by an order of magnitude or so, Google's Gmail servers probably can't.
Longer, more complicated passwords would be more effective than increasing iteration counts, but people are bad at generating and remembering long passwords. So, the only long term solution seems to be moving to stronger forms of authentication, like smart cards or using devices like smart phones as one-time password devices.
NTLM hashes (and most others) are sent over the wire in a number of circumstances.
The whole point of password hashes is to have something more secure than a raw password to transmit over the wire. What do you think is sent over the wire if not a password hash?
- Michael T. Babcock (Yes, I blog)
Thank you for pointing this out. I'm wondering why people are upset about NTLM hashes being broken; any good user disables the legacy storage of them.
My password is tYidsasaf770 and my IP is 198.81.129.125 - can someone try this GPU thingie on me? I want to be secure as possible. Thanks...
Humor from a Genetically Molested Mind
Thats why i dont use a password..or at the very least...
So the combination is... one, two, three, four, five? That's the stupidest combination I've ever heard in my life! The kind of thing an idiot would have on his luggage!
------------
Sase
"It's the opposite of that."
And don't forget all the people who set up rigs specifically optimized for computing lots of hashes quickly to mine bitcoins *looks around furtively*...
Information theory is life. The rest is just the KL divergence.
so this means i may finally have a quick way to get back into that encrypted file I forgot the password for? I should have known that the 32 character password was a bad idea.
I've decided to Diversify my Holdings. I've divided my cash between my left and right pockets, instead of all in one.
Single point of failure.
Essentially, you will need to carry a copy of your password bank with you AND the application which opens it at all times to function.
This means that if it gets compromised (your memory stick gets stolen/your dropbox account gets compromised/ etc...) an attacker will only need to guess/bruteforce/dictionary attack/social engineer/look over your shoulder one password and gain access to everything in your wallet.
Keepass can use keyfiles and passwords. So, even if someone gets the wallet, they have to figure out which keyfile to use, and then brute force. Keyfile is stored somewhere else, it can be something simple, like a picture in your album, which happens to also be on your blog, just in case.
I don't need a Windows password using a weak algorithm, I have an encrypted partition with Truecrypt that ask a password at boot just after BIOS, mine is 24 characters, I am wondering what a GPU could do...
"Science will win because it works." - Stephen Hawking
Everyone keeps complaining about how inefficient CPU's are due to the fact that they have to make the instruction sets backwards compatible. Fine. Have newer motherboards come with lean, dual core, 2Ghz per core, backwards compatible x86 CPU's built in and allow for the installment of an additional CPU that's not backwards compatible but instead seeks to provide for a more speed (and energy/heat) efficient instruction set. Old applications can be ran on the old CPU's, while developers can start developing new applications on the new CPU's. As more and more applications start being developed on the new CPU's, we'll slowly transition out the old obsolete CPU's and replace them with newer, more efficient CPUs with better instruction sets.
Running Linux Mint 11 Katya,
Nvidia GTX460 - latest x64 Nvidia drivers
Wine 1.3
$ wine ighashgpu.exe -h:239361613fe5281d8efb90e7f8e0ceb0 -t:md5 -c:sd -m:????assw???1234
Cannot find any compatible GPU device.
Yes, it scales linearly. But if you set a 1-second minimum on hashing, and a GPU normally does 3.3 billion/second, then you've done 3.3 billion times the work. Not twice the work. Plus a brute force attempt would not know the number of rounds, and so would have to try, say, everything from 1 round to 9.9 billion rounds, just to be reasonable. So requiring a second or two of hashing has potentially required billions of times more work to generate the hash, and requires billions of times more work to break (which already takes relatively a long time), assuming no shortcuts.
Perhaps it's reasonable to do this much work when generating each password. How many new users/minute do you expect? If you add users at that rate, there are bigger scaling problems.
Stronger forms of authentication should be used in addition to strengthening passwords, since passwords will likely still be one factor used. Even two-factor authentication employing a password plus a "stronger" form can become meaningless if the password can be brute forced and the other factor overcome with social engineering or simple theft.
I'm not really up with all the tech encryption stuff, but.......if we had systems that required 3 seconds between password attempts, would that not defeat all the brute force attacks, by increasing the time needed to crack them astronomically? Instead of having a billion attempts per second, a billion attempts would take 3 billion seconds, or just over 31 years......
Instead of arguing on which of you guys got the best encryption scheme and can beat the test with whatever solution, can you just agree that GPUs can be a lot faster at executing some tasks that today's state of the art CPUs still take forever to do (no news there for us, the article is meant for general public) ???
How you will use that power efficiently is more the target of the discussion here. There's not just trying to get in a system through decrypting hashes, there's the capturing of encrypted data that you would like to see decrypted, there's pattern recognition in images or sound (like facial recognition), weather forecast calculations, and much more.... And now lots of this can be accomplished without buying a Cray, the article is simply pointing that even cheap GPUs today have enormous potential.
You don't just hash a password when you you store a new password. You also have to hash the password every time a user logs in. Now I agree you could certainly increase the iteration count on passwords, but one full second of computation on a busy server isn't going to fly. Companies have pushed back over far less. It has taken a long time to get where we are today when it comes to using TLS for login pages, and that's far less than one second of computation. Far fewer companies continue to use TLS once you get off the login page, even though the symmetric encryption operations that take place after the initial key establishment are even less computationally intensive.
I was just the example of twice the work to show how much easier it is to make brute-forcing a key infeasible versus brute-forcing a password. Yes, I'm sure you can do more than twice the work. But you're not going to get away with doing 3 billion clock cycles. I think you'd have a hard time getting people to deploy enough iterations to block brute-forcing attacks. And even if you do, it would be short-term fix. Bumping up the key length of an encryption algorithm can extend security a long time. From a practical perspective, AES-256 should work indefinitely, as long as someone doesn't break the algorithm itself. There's probably not enough energy in the universe to brute-force a 256-bit key, and quantum computers don't help that much. Bumping up the iteration count by a factor of 50 or so (any more and I think you'd have a hard time getting people to deploy it) basically just gets you the same thing as another character in the password. That's not enough to block these attacks. And by the time you'd actually get that deployed password crackers would be even more powerful. And since you can't get companies to change crypto algorithms and protocols constantly, you'd basically be stuck with that for 5-10 years.
You're not going to close hole with higher iteration counts alone.
They get excited about breaking six character alphanumeric passwords. Does anyone think those are secure / enough?
Try 14+ characters, mixed case, numerics, punctuation, and symbols. That should keep them amused for a little while. Add a little salt and watch their GPU burn. :-)
I use sentences for all of my passwords. I have in effect a 20+ character password which is just as easy to remember as a word. I throw in a number in replace of a word or letter and bam - i have an alphanumeric 20+ character password which is extremely easy to remember.
Whats the harm in yelling 'Computer, end program!'? You could be living in Star Trek! Go on.. give it a try.
I don't give a fuck, God sent me to piss the world off, so F*ck U!
U are an idiot
NTLM by default stores as a HASH. If you have a registry tweak it can be stored in a more secure way. In corporate america we turn that off as it creates problems with all the weird SMB systems we have. If you use a password that is over 14 MS will save it and send it in a different way. Same shit since Windows NT. Microsoft has not done a damn thing with the SMB but make it so that 3rd parties have issues.
Grow up Punk, ur first computer was prolly windows xp!
NTLM hashes do NOT go over the wire. You use the hash to encrypt a "well known" key and sent THAT across the wire. The remote server then does the same thing and compares the results.
Bottom line: Want a strong password that you can type anywhere? Make it 12 mixed case letters, numbers and at least one punctuation mark. Based on the times claimed in the article, that should take 35,000 current GPU-cracker-years.
And what about Rainbow tables? Those things can break weak password even faster than a GPU, by virtue of being precomputed. And available for download.
And slightly OT, but is there any actual GP-GPU software out there that isn't for black hats?
Newest Photoshop and Folding at home GPU client, CUDA optimized.
Two that come to mind quickly.
-AI
For me, it is far better to grasp the Universe as it really is than to persist in delusion
hunter2
[...] memorizing a handful of 12-character passwords is no harder, in a practical sense, than memorizing a handful of 10-digit phone numbers.
Sensational alarmist crap at its best.
I don't disagree at all with your overall point, but as a practical matter here you are wrong. As it turns out, most human brains have a threshold at 7 items. Below that the difficulty of remembering a sequence of items grows linearly with a very low slope (i.e. remembering 7 numbers is only slighly harder than remembering 6) but past that it gets hard parabolically, so much so that most people will find mental ways to break up any series longer than 7 into parts. You don't really remember a 10-digit (NANP format ) phone number, you remember the 3-digit area code and the 7-digit local number, which most people probably break into 3+4 . If you are remembering a 12-character password your brain will break it up into at least 2 pieces, both of which should be rather random (unlike phone numbers) and containing more than digits. However you do it, the same number of 12-character passwords will be harder to remember than 10-digit numbers.
Using pass the hash, you don't need to crack windows passwords if you have the hashes. You can just use the hashes directly as passwords. If someone can get your windows hashes, that is game over, no matter how slow their computer.
"fjR8n" is your idea of a secure pword? Allow me to introduce you to the following chars: "!@#$%^&*()_+-={}[]"
Does Win* allow those in pwords?
"Tongue tied and twisted, just an Earth bound misfit
Note that the article is referring to NTLMv1 which uses 56 bit DES and, as illustrated by the article, that is easily broken. However, the article conveniently fails to mention that as of Vista and Windows 2008, default security policy requires NTLMv2 which uses 128 bit RC4. That is a totally different crypto scheme. Despite the fact that the protocol for exchanging authentication tokens (NTLMSSP) has been around since early Windows NT days, it doesn't matter - cryptographically 128 bit RC4 is fairly secure. At least the difference between 128 bit RC4 and the 256 bit AES used by Kerberos is not the weak link (and as of today Windows domains still default to allowing 128 bit AES to be negotiated anyway).
Also, note that NTLM authentication is absolutely not obsolete. Kerberos clients require access to domain controllers. Kerberos is very sensitive about the name a client uses to authenticate with a service and it is very sensitive about DNS. It requires a lot of manipulation of principal names and key files. Time must be synchronized on all three machines involved in a Kerberos authentication. Stale tickets may need to be purged. If any of these things are not right, it can be non-trivial to track down the problem. NTLM does not have any of these issues. NTLM is much more robust than Kerberos. It's just less efficient and it lacks features like delegation. A "pass through Kerberos" mechanism is being developed to replace NTLM that would resolve some of these issues (the main one being that clients would not be required to access domain controllers), but I suspect it will still be quite a while before it actually does and it's not clear that it will solve all of the aforementioned issues anyway.
Well, the thing is NTLM is still being used. Whether it's a new or old tech, 95% of us are still using them.
As usual, when discussions of cryptography happen on Slashdot, a lot of nonsense gets bandied about. Let's clear some of it up:
Bcrypt is "adaptive" in a sense, in that you can specify (to a certain extent) the number of key setup rounds to be used in the algorithm. But there are some assumptions that many people are making in this discussion that simply aren't true. Let's take care of the assumptions first:
(A) This discussion is about brute-forcing passwords via the Web.
No, it is not. Because of various factors (one of which I bring up below), it would make no sense if this were about web-based attacks. For one thing, there is no way in hell a GPU utility could be doing web-based attacks that fast, no matter how fast it was itself.
(B) bcrypt is an advantage when faced with attempted brute-forcing over the web.
This is simply false. When doing web-based authentication, it is the server that does the hashing. The only advantage that bcrypt might have is that computing the hash takes time... but since it's happening on your own server, that is not an advantage. You could simply introduce a small delay before your hash is computed, and you will get exactly the same effect. Better, in fact, because of a serious issue with bcrypt, which I will explain below. But to be clear, this discussion is about breaking passwords assuming that someone has your database.
(C) Both MD5 and SHA1 are broken, to some degree.
This is nonsense. Certain weaknesses have been found, but the odds against those particular weaknesses (such as the probability of a collision with MD5) being used in a real-world exploit are astronomical.
(D) Certain hashing algorithms are vulnerable to rainbow tables.
No... ALL hashing algorithms, no matter how complex, or how much time they take, are vulnerable to rainbow tables, by their very nature. There is nothing in the world that can change that, except:
(E) Salts are completely unnecessary if you use the right hashing algorithm.
Utter nonsense. Salts are the only thing that can save you from rainbow tables. Some people have pointed to bcrypt, saying that it doesn't use salts, but in fact it does. It's just that unlike most other schemes, it stores the salt in the same database entry as the hashed password.
Now here are some things that seem to be contrary to popular opinion about bcrypt:
(1) You can specify how much time the algorithm takes to hash your password.
No... all you can do is set a "work factor" (N) to be used by bcrypt. The number of key setup rounds will then be 2^N. Not only is that NOT a fine-grained "tuning" mechanism, it has nothing directly to do with time. Given the same work factor, a supercomputer (or GPU) will still compute the hash a hell of a lot faster than a standard CPU doing the same thing. What you are adjusting is difficulty, not time, and and settings that can only be powers of 2 do not exactly constitute "fine-tuning".
(2) bcrypt will help prevent web-based brute-forcing.
No (see above). If your only concern is a web-based attack, then introducing a simple delay before your existing hash function will give you exactly the same protection... over the web. In fact, it gives you better protection in a sense. You see, using bcrypt with one "work factor" setting is NOT compatible with bcrypt at a different work factor. If for any reason you wanted to ratchet up your security by increasing bcrypt's work factor, all your existing passwords would have to be re-entered by their users, because there is no way to go from one hash to the other... the new hash has to be computed from scratch.
Which means that, for all practical purposes, bcrypt is not really "tunable" at all. Once you have users with established passwords, changing bcrypt's "work factor" will require each of those passwords to be re-computed. Which means the end user will have to manually
There's been a raging debate internally as to whether or not we should change to hashed passwords. (for historical reasons, passwords aren't hashed now)
I've pushed for hashing repeatedly, but it's always been downsided by the fact that users are often technological cave-dwellers who have trouble turning their computer ON, let alone not being able to get their password from a support staff.
However, I'm not sure it matters so much, anyway. There are a number of techniques (such as hash tables) that make hashing much less usable, this GPU attack only exacerbates an already bad situation.
I'm of the opinion that anything less than 2 factor authentication is broken now or soon, anyway. I'm in favor of a random, cell phone text tied to the password, myself, except that texts are sometimes delayed. It works like a one-time password and can't meaningfully be broken since the time window of opportunity is far less than the password timeout for trying again.
Done right, this can't even be used to cause a DDOS because, if it's tied to IP addresses, the cracker would have to work 24x7 for a few hundred thousand years to make the window of opportunity, or, use a few hundred thousand IP addresses for a year to do the same in a year.
I have no problem with your religion until you decide it's reason to deprive others of the truth.
If you are using a CPU to calculate the hash, and the bad guy is using a GPU, reduce that 3,311 year to about 7. And if he can afford 100 GPUs, you are down to less than a month.
The "nobody but us geniuses can make or use strong passwords" problem has been over and done with for a long time. And it turns out that anyone who advocates for requiring non-alphabetic keystrokes is simply ignorant, genius or not.
Just use diceware. Roll five D6 dice, look up the resulting base six number in the diceware dictionary, and write it down. There's your first short, memorable word. Repeat three times for login credentials and the like, seven times for "really strong" cryptographic pass phrases. When calculating password search space, it is easily found that length is everything: Increasing the symbol set increases the base, increasing the length increases the exponent. So your diceware pass phrases lose nothing of value if they are all lower case with no spaces and no "exotic" keystrokes - they just become much easier to remember.
http://world.std.com/~reinhold/diceware.html
Passwords grow exponentially in complexity but GPU reduce this complexity linearly. There must be a password length that can be unreachable by GPUs no matter how complex your password is. For example, say I have a password like 'mymumlovesmesoooomuch' which is easy to remember and impossible to break by any GPU (26^20 => 6.4×10^15 centuries with 1 millisecond per password check).
So, the only long term solution seems to be moving to stronger forms of authentication, like smart cards or using devices like smart phones as one-time password devices.
Actually, the only solution is to do away with passwords as the ONLY 'lock' on protected systems. Multi-factor authentication is the only way to go. Sure there can be a password in there (something the user KNOWS), but cracking that gets you nowhere in itself. You'll also need the access card, token or whatever the user HAS and the finger, eye or whatever biometric component that represents what the user IS.
So, with such systems you can't just steal a hash file and crack that. You'll also need to physically access the user and get his code key and his finger... As 99% of all computer crime is executed remotely, this will be efficient to stop intruders. Even social engineering is mostly done remotely over the phone. Having to get close physically means a greatly increased risk and thus chance of capture. In other words - it will be pretty efficient at keeping unwanted visitors out. This is probably why most online banks use something like this (two factors minimum) as their access security.
"For every complex problem, there is a solution that is simple, neat, and wrong." -- H.L. Mencken (1880-1956) --
If the password protects access to a system, it needs to be secure only so long as it is the password in use for that system. If it becomes less secure, switch to a different one (or a different system like two factor authentication). If it protects data (like an encrypted volume) then you need to decide how long that data needs to be secure for.
PBKDF2 is an iterative hash. If you want to exponentially increase the # of iterations simply rehash your DB of hash values. You do not need the original plaintext to do this.
If your original DB has hashes of 1,000 iterations, and you want to go to 10,000 iterations, you would rehash each row 9,000 times. You are not limited to linear increases in time cost.
Using passphrases instead of passwords, as many others here have mentioned, is always a good idea. But are you multilingual? If you are, it can help to maximise security from attacks like this* by creating even more secure passphrases via the mixing and matching words from different languages into one phrase. For example "Uno dish of coffee sivousplait" (note the non-standard French spelling). You could even remove the spaces, but I'm not sure if that matters from a "crackable" point of view.
Even better—are you multilingual in language(s) that don't primarily use the (common) Latin alphabet? For example, if you know Japanese, Mandrin and Korean you could archive a similar result: "wousotukeinida"; even better, in this case, you can see I used a kind of non-standard romanization for the Korean ("inida" = "ipnida") and Japanese ("usotuke" = "usotsuke"); it could be considered a form linguistic "salt" that makes it even harder to match up in a dictionary attack. Sprinkle in some numbers and symbols and you're ready to go.
As long as you memorise the phrase (duh), and even with predictable switching word bounderies, you would compilcate/defeat a plain dictionary attack by (a) huge factor(s). First, an attacker wanting to use a dictionary attack would have to deal with finding out what languages you might/may/most-likely could know, (i.e. they would need some kind of "real life" info about you as well, which complicates things even more), along with "in what order" and "in what place" you used each language crossed with the factors of where you put spaces and perhaps the possibility, like above, that you used some kind of non-standard romanization scheme if you pulled it from a language with a different kind of orthography... plus the phrase length... plus the "random" symbols/numbers... THEN the computational factors start to pile up sky-high.
As for simply entering a "password" using a native script via an IME into the password field... well, I try not to do that. I was burnt in the early days of multi-lingual computing with different operating systems/programs rolling their own encoding schemes that resulted in different "output" in different situations and a lack of wide support across platforms (and in some cases, countries!). All computers handle simple latin text in a standard way since the dawn of time, so I just started doing it like that. YMTDMV (your mileage, these days, may vary).
(* Actually, on closer inspection, it looks like this wasn't a dictionary attack but a key-space search. Still this advice also helps to expand your passphrase length as well as fortifying it.)
(Posted anonymously for obvious reasons.)
When a GPU can break 15-character AES256 keys, then I'll start to worry about the security of my 24-character key.
First of all, AES-256 has a 32 character key AES-128 has a 16 character key. With "character", I of course mean the whole alphabet from 0x00 to 0xFF.
Second of all, though I might be mistaken, you may need to read up on entropy. Your 24 character key is unlikely to hold more than a handful bits of entropy (don't remember the math, but ~20-30 maybe), compared with a cryptographic key that should have a very high entropy (as close to 256 or 128 bits as possible, depending on which cipher you use).
In short, you should start to worry about the security of your 24 character key.
Strange how information on Bitcoin was ommited. With strong radeon cards you can get quite rich. Months ago there was article of 1 bitcoin reaching 1.00 USD exchange value. Now 1 BTC is 19.5 USD.. :D
And any system worth its salt (crypto-hashing joke) won't allow that many attempts against any external or internal authenticator and will NEVER expose its password hashes.
What an utterly irrelevant comment, obviously you can't GPU-accelerate a remote login, that's got nothing to do with the issue here.
Fact is data breaches do happen (see Sony) and if you can suddenly brute force a password 300x faster than before that is a very big deal. 10 GPU equipped desktops can now do the work of 3,000 CPU based desktops...
Which means that, for all practical purposes, bcrypt is not really "tunable" at all. Once you have users with established passwords, changing bcrypt's "work factor" will require each of those passwords to be re-computed. Which means the end user will have to manually enter it again.
Your users enter their passwords when they log in giving you an opertunity to replace their password hash.
So provided you have some policy on expiring inactive accounts you can switch to a new hash scheme (or the same scheme with different settings) over whatever your inactivity timeout period is without users noticing a thing.
note: i'm known as plugwash most places but i screwd up registering that here somehow in the past and now can't register
If only they'd built it with 6001 hulls!
(1.21 gigawatts) / (88 miles per hour) = 30 757 874 newtons
And I talk about the old style 8 chars max unix hashes.
See some stats here:
http://openwall.info/wiki/john/benchmarks#Collected-john-test-benchmarks-for-one-CPU-core
and cracking the newest sha512 takes how long?
Atari rules... ermm... ruled.
And That's we have a 256-bit encrypted luks /homes
I use 12-character passwords. http://howsecureismypassword.net/ [howsecurei...ssword.net] estimates that my root password would take 25 million years to hack.
Well, I also use a 12 character password, with at least one upper-case, at least one lower-case, at least one numeric, and at least one non-alphameric character. That web site estimates a mere 4 million years for a desktop PC to crack it. However, it does not indicate whether that's using the CPU or a GPU. Several orders of magnitude might vanish from that estimate if it is based on use of the CPU and a cracker uses a decent GPU. The remaining safety factor may become uncomfortably slim before long, given the performance improvements expected in GPUs and the parallelism inherent in password cracking.
The other posters are correct: passwords should be a necessary step in authentication, but by themselves should not be sufficient for authentication. After all, we can't expect to keep using longer and longer passwords (or pass-phrases). A few years ago, I was content with 8 character passwords for root (and sudo) accounts, and often containing only two character classes. Now it's 12 characters, containing four classes of character. Clearly, this trend is not good, as my memory for passwords is not improving at the same rate.
Those who can make you believe absurdities can make you commit atrocities. - Voltaire
I have to add that the title *is* misleading. The 7 character password which was cracked in 17 minutes is alpha-numeric only. That hardly constitutes a strong password.
Including special chars, the 8 character password estimated 25 days to beat, while the nine char password of the same set, estimates a 7 year solve period.
I think the concept is very interesting and how this can be done! I still love it!
The simplest solution that I can think of is to use an authenticator system.
That way the passwords can be as simple as the users want, they do not have to be changed every 90 days (the duration of a password in our facility) and with the code changing every 60 seconds, it means that even if they somehow managed to snag your passwords, they can't do anything with them.
And I know that such a system is not fool-proof. But until someone develops a way to break that system it may be the simplest and the best solution for now.
-- Wiccan Army, 13th Airborne Division "We will not fly silently into the night"
It is well known that if someone gets your hashed password, it is as good as cracked.
It still depends on how much time / money the attacker is willing to spend. If you use slightly longer passwords / passphrases, then you won't be the low-hanging fruit. A dedicated, targeted attacker is still a big problem, but the opportunistic attackers will check the hashes, fail to crack them and move on to the next target.
I did an analysis on this a few years back, when CUDA and GPUs first started getting popular. Back then, my estimated speed was 5 billion hashes per second for a single GPU. A bit of an overestimation, but in line with the ~3 billion/sec of current GPUs. Passwords were assumed to be semi-random with 65% lower case letters, 20% upper, 10% numbers, 5% symbols. A big assumption, but it provides a starting point.
Very few attackers are going to spend more then a day on a single account. Even with a large botnet of 10,000 GPUs at their disposal. The ones that will go that distance are targeted attackers and they will be trying other methods as well to compromise your security.
Brute force times:
chrs
8 = 9 hrs
9 = 22 days
10 = 1325 days (44 months)
11 = 79,000 days
12 = 4.7 million days
13 = 282 million days
14 = 16.8 billion days
15 = 1 trillion days
The lesson from that was that 8 characters or fewer (of the stated complexity) passwords are screwed. You really have to go out to 11-12 characters and enforce some measure of password complexity to be safe.
Wolde you bothe eate your cake, and have your cake?
Why not start including Biometric Info in the crypto process? Say use a hash of a fingerprint pattern (with polygonal mask determined by characteristic points or a numerical combination of the relative point locations themselves) in combination with a mental phrase (possibly written in UTF-16) or layer it all: Use a pass phrase to hash a data set of fingerprint point-relative information into a has for the actual information. you could easily come up with a 1k-long final key determined by a small amount of information you remember and large amount of information thats built into your finger.
And what happens when it takes 10 seconds for one of your users to log in (not to mention what happens when you got multiple logins at the same time), and the attacker still can do a billion tries per second thanks to his GPU farm?
It's The Golden Rule: "He who has the gold makes the rules."
Does the strength of the encryption significantly affect the user's experience with passwords and encrypted files? I mean, if 256-bit encryption is better than 128-bit encryption, why isn't everybody using 32678-bit encryption or maybe megabit encryption?
It is impossible to have both. GPUs are only about 2000 times faster than CPUs at calculating hashes. A reasonable password policy ensures that passwords won't be cracked before users have time to react (usually months or years). Your example would require that a GPU be tens of billions of times faster than a CPU at hashing.
I guess what I'm saying is, from the perspective of one person who wants to protect their individual account, yeah, you might not worry too much. But if you're the guy in charge of protecting the server itself -- and by extension, the security of every account on that server -- then worrying seems justified.
Excessive worrying is only justified if:
- You allow passwords shorter then 8 characters.
- You do not enforce password complexity.
- You do not uniquely salt your passwords on a per-account basis.
Change at least two of those things and you're protected against opportunistic attackers (which is probably 99% of the threat). Force passwords to be at least 10-11 characters (I suggest 12-15). Force passwords to have at least some numbers / symbols / mixed-case feature. Make sure you use a different salt for each account, of at least 12 bits, for storing the password.
Maybe switch to a hash that takes 100x longer to calculate then MD5. (The other steps will buy you the equivalent or better time over using a difficult hash method.)
If the information is that valuable, consider adding a 2-part authentication system (password + token, or password + biometrics).
Once you drive the time to brute-force a password hash into the hundreds of years (even assuming that everything gets 1000x faster before we hit the physical limits of the universe), then you're pretty much done. No attacker is going to spend a year cracking a single password. Now you need to worry about the other dozens of ways to get at the information - like social engineering, exploits, vulnerabilities, sniffing, spyware, physical intrusion or intimidation.
Wolde you bothe eate your cake, and have your cake?
You're assuming that the cost ratio CPU / GPU will continue to be the same. That's not certain at all.
I can easily see both the per-card cost going down, and see per-gpu calculating power get increasingly ahead of CPU in these things.
It's The Golden Rule: "He who has the gold makes the rules."
It's not quite that simple... If you make a hash/crypto scheme that will be less vulnerable to this, you make it much more difficult to use it as a means for passwords in the first place as it's much more difficult to compute for authentication.
I am not merely a "consumer" or a "taxpayer". I am a Citizen of the State of Texas
5 characters, just letters and numbers? Ummm those are not strong. Add some symbols and they could be complex but still not strong.
Since Windows NT a strong pass was complex and over 14 characters. I'm not seeing those getting tested.
let it try cracking "I read Slastd0t all day!". A nice strong pass that is easy to remember and type. I'm guessing the GPU, the person trying to crack the pass, as well as the pass owner, will have died long before the GPU cracks that pass.
GP here, posting anon from work. Considering some other replies, I was specifically talking about offline attacks.
Yes, it scales linearly. But if you set a 1-second minimum on hashing, and a GPU normally does 3.3 billion/second, then you've done 3.3 billion times the work. Not twice the work.
This is what I was getting at, but...
Plus a brute force attempt would not know the number of rounds, and so would have to try, say, everything from 1 round to 9.9 billion rounds, just to be reasonable.
Normally I'd assume that if they compromised the system to where they've got the password database itself, they've also got the binary (at least) of the code producing the hash.
But, generally, you've nailed it: the attacker's systems scale exponentially in power, but the defender systems are also scaling exponentially at about the same rate. So if we've got a GPU now and they've got a farm of ASICs, we would expect an imbalance of the same order of magnitude 20 years down the road. If we can make that up today, I can't see why we can't make it up in the future.
The program is only generating hashes. It cannot tell whether the has matches anyone's password without either:
a) Physical access to the Windows system in question
b) Attempting to log in
Obviously no system can accept, let alone allow, 3.3 billion login attempts per second. Which leaves only physical access. Well, you would need physical access and the system would need to have all this GPU hardware in it. Not really a threat to any real world security scenario - plus is you already have physical access you don't really need to be cracking passwords - you can simply get anything you want off the disk if you have physical access.
Not to mention that the hashing they are talking about is NTLM, which is not in use anymore by modern versions of Windows.
Sigh - just more FUD...
So, when do you forsee GPUs getting to the "tens of billions of times faster" that I mentioned above and is necessary for your comparison to be valid?
That's a good point I had not considered. It would take a rewrite or patch of most plugin authentication systems, but that would probably do the job.
So then how would you use this to crack a truecrypt volume? Or can you?
Quadrupling the time it takes to crack a password is significant if yours is one of thousands and the attacker doesn't have the resources or will to crack them all. If your password is four times harder to crack than everyone else's, it may be skipped. Just like any security measure, passwords are never absolute protection.
Any security measure from a closed door to a combination lock to an army can be overcome with enough resources and will. Sufficient security is something that requires more resources or will to overcome than the attacker possesses or just delays the attacker long enough that the attack can be rendered useless. In the case of password hashes being obtained by an attacker, the longer it takes for the password to be cracked, the greater the chance the victim can be made aware of the attack and change the password or take other measures that render the attack useless.
Isn't it better to simply get the public RSA key of the user and be done with it? You get a 2048 bits key that won't need replacing often (good till the heat death of the Universe), won't burn your money into useless server cycles (fast algorithm), and is still more secure (older, way more tested than your idea). We just need to adapt the browsers, untill then you just don't limit the size of passowrds on your site, so people can protect themselves with longer ones.
Rethinking email
I can confirm this as true because every single person responding to this thread is actually me. Getting everyone's password was a breeze. Logging into everyone of them and posting something different....... that was a pain.
Does God treat us as servants or friends? Check my homepage.
Your point is not really true at all because you fail to take into account the scale of turning a few microseconds per calculation into a several seconds calculation. I just made it cost a million times more to crack passwords. There are no 10 billion machine botnets.
You think a 2-factor system is more user friendly than limiting authentications to roughly 35 logins per hour per quad core system? Having to wait in a queue seems less painful to me, and less likely to line the pockets of RSA Security.
“Common sense is not so common.” — Voltaire
My bank (Société Générale, France) only allows 6-digits passwords. chars have to be numerics only. yes.
With these algos, tell me... is it possible to calculate a "problem" in a very short time, provide some amount of data to an opponent and have them solve it ? The scale of the problem (overall complexity) and the size of the amount of data (clues) need to both be streeeetchable.
What I'd like to see/know is this possible based on any of the above password hashes ?
If so could it be implemented in SMTP as a solution to SPAM but as SMTP level, a bit like hashcash does at the MUA (Mail User Agent) level ?
Wouldn't this just fix the SPAM problem ? The server presents a mathematical problem to the client to bruteforce, the server is able to scale the size of the problemfor Moore's law and able to tweeak the amount of clue given to make less trusted parties have to do more work to send a single message. On top of this SMTP client/enterprises also exchange cookie tokens to build up reusable reputation with the intention of lowering the cost to send a message.
So how might a mixture of stretchable matematics solve this problem ?
DLM
The comments seem to all assume a hacker has access to one hash (since bruit force over a network would not give you many tries). They also seem to assume the attacker would only try to crack a single hash...
If an attacker got one hash, its fairly safe to assume they downloaded the hashed passwords database. At this point it is no longer trying to find a string that produces a single hash.. assuming they are after any access at all, or any users account without caring who's, then the likelyhood they will succeed is much higher. They set their gpu's to start producing hashes, once any hash matches one in the password database they have succeeded.
I am not a math guy, but I would be interested to see the numbers when you assume a hacker has a large database of hashes and considers any account they break into a success. For instance say the recent sony hacks, assume the hackers steel a CSV file containing 1 million rows of username => pass_hash. As well as the code for the hashing algorithm including any salt and transforms. Is it possible to calculate an accounts cracked per minute/hour/day/week/year?
Now also consider that unless the hashing algorithm is a 1-to-1 algorithm (IE all strings produce unique hashes) their could be shorter strings that produce the same hash as your uber-secure password.. Are hash values truncated in any way to fit into the database field being used to store them?
Assuming an attacker has 1 hash to crack, and that the hashing algorithm is 1-to-1 is an interesting oversight, I do not see how wither can be assumed without knowing the user count of a system, and the hashing algorithm and storage engine in place.
Funny, l0phtcrack did a great job of pulling in NTLM hashes over the wire.
- Michael T. Babcock (Yes, I blog)
The post I replied to suggests stopping at the first collision. Perhaps the question was poorly worded. I would like to know how many collisions occur for a given hash. Could this be calculated without a brute-force attempt or is that the only way?