Why is this news? The Russian company Elcomsoft has ported password cracking software to a graphics card, boosting speed by 25 times.
The Utah company AccessData has been doing this sort of thing much longer, and has way better technology.
Rr • October 26, 2007 12:40 PM
Err. didn’t complete my thought.
I would think that for brute forcing, the porting of the code to the GPU is a major step forward. Of course doesn’t compare in speed to dictionary attacks, but really darn handy for when brute force is the only option. Apples and oranges, if you ask me.
Pat Cahalan • October 26, 2007 12:47 PM
This reminds me of the “Iran is buying PlayStation 2’s to BUILD NUCLEAR WEAPONS” story.
Neat hack, but a processor is a processor.
Chris • October 26, 2007 1:01 PM
Rr:
The two companies seem to be following very different approaches. AccessData just uses the CPU, but from Bruce’s article, it seems like they’ve got very intelligent routines for guessing which password to try first.
Elcomsoft uses the GPU, which allows it to try many more passwords per second, but the article doesn’t mention any optimization of the search space.
So which approach is better? It seems like it’s going to depend on the password. For someone who uses weak passwords (English words, words with a few numbers thrown in, short phrases, etc.) the AccessData approach would be superior. For someone using high security passwords (long strings of random or near random alphanumeric characters, their intelligent password guessing isn’t going to be much use. You need a pure brute force technique like Elcommsoft’s (or just find the post-it note where the person wrote down their impossible to remember password).
Of course, the best of both worlds would be to combine the greater brute power of GPU based password cracking with AccessData’s intelligent dictionary techniques.
Anonymous Mike • October 26, 2007 1:12 PM
Well, a brute force approach is just the first step toward a database-based attack. Brute all the hashes you can, save the results for the next go. Coordinate your efforts, and before you know it, some Latvian teenager has the whole hash database online.
Lance • October 26, 2007 1:16 PM
The technology Access Data uses in PRTK is straight brute force technology against various hashes and/or encryption algorithms and can take a very long time with even high powered computers. You can of course speed up the process by using rainbow tables that you buy from them or make yourself, but then you need a rainbow table for each hash type, i.e. md5, sha1, lanman, md4, etc.
As a frequent user of PRTK, other password tools and doing forensics where a password recovery is needed, I view this as big news and look forward to other companies jumping into this technology.
Eam • October 26, 2007 1:22 PM
@Rr, Chris:
I think Bruce may have been talking about the FGPA hardware add-on for AccessData’s PRTK (see the article he linked).
@Anonymous Mike:
Sure, but these rainbow table attacks fail in cases where salts are used properly. I imagine this is the case where the mentioned software packages excel.
—
I’m not entirely certain, but I don’t think Elcomsoft just ported existing code to the GPU. I believe they found some parallelizable aspect of a popular hashing function and used the GPU’s multiple execution units to run an entirely new version of that hashing algorithm.
If not, and they’re just patenting the porting of existing code to the GPU, they should probably be shot.
Stephen Smoogen • October 26, 2007 2:56 PM
@Bruce
It is news because it came from Russia right along the time the press is all up in the air about Russian mafia using pdf’s to steal people’s identities, Russian spies stealling information from computers, and big bad Russia supporting Iran. So it plays into a stereotype that people are predisposed to read and thus sell more ‘clicks/papers/etc’ for the people reporting it.
John Hardin • October 26, 2007 3:22 PM
Coordinate your efforts, and before you know it,
some Latvian teenager has the whole hash database online.
Hrm. I sense a new BOINC project…
aikimark • October 26, 2007 3:55 PM
Jeff Attwood has a nice synopsis of this problem if you need to answer this question and would like to use a ready-made presentation:
Bruce Schneier • October 26, 2007 5:19 PM
“I would think that for brute forcing, the porting of the code to the GPU is a major step forward. Of course doesn’t compare in speed to dictionary attacks, but really darn handy for when brute force is the only option. Apples and oranges, if you ask me.”
I was particularly thinking of AccessData’s use of FPGAs, but they have a whole bunch of other hardware tricks I didn’t get to write about in that essay.
Clive Robinson • October 27, 2007 3:19 AM
@John Hardin
Jeff Attwood’s comments show a bit of a problem in his reasoning,
“Brute force attacks, even fancy hardware-assisted brute force attacks, are still for dummies. If this is the best your attackers can do, they’re too stupid to be dangerous. Brute forcing is almost always a waste of time”
I would say his “theoretical” outlook is not backed up in the “real world”.
What he forgot to mention when he sugested upping the number of chars in a password from 8 to 12 or 14 is that the average mortal sitting behind a WordProc/SpreadSheet PC has difficulty remembering even 8 semi-random chars let alone 12.
The weakness of passwords has always been “Jo(e) Average” and for that reason alone using one or two $1K5 PCs to run a brut force search (effectivly) in the background will pay dividends a lot more often than expected by his reasoning. This makes the ROI very worth while especially if other avenues (social eng) might well allert the target.
Also what better excuse do the Tech guys need for the CapEx to get the latest Graphics Card for their “shoot-em-up” box than “We need it for checking the security of our users systems” 8)
Paul Crowley • October 27, 2007 6:57 AM
Cryptanalysis using CUDA is good fun, but what about cryptography? Has anyone used this for anything like
Should we be abandoning all the eStream entrants except Salsa20 since they are unable to make use of this massive parallelism?
Bruce Schneier • October 27, 2007 12:26 PM
“”Brute force attacks, even fancy hardware-assisted brute force attacks, are still for dummies. If this is the best your attackers can do, they’re too stupid to be dangerous. Brute forcing is almost always a waste of time.”
Not even close. Brute forcing works surprisingly well, as long as you guess keys in some clever order — a dictionary attack — rather than in random order.
Read this essay of mine:
http://www.schneier.com/essay-148.html
It’s amazing how well brute forcing works.
Bruce Schneier • October 27, 2007 12:28 PM
“Well, a brute force approach is just the first step toward a database-based attack. Brute all the hashes you can, save the results for the next go. Coordinate your efforts, and before you know it, some Latvian teenager has the whole hash database online.”
While there are lots of clever time-memory trade-offs in the literature, you do realize that there are waaaay too many hashes to make this possible. 2^^80 is a real big number.
Terry Cloth • October 27, 2007 12:44 PM
@Bruce: In essay-148 you note
“Your encryption program’s key-escrow system is almost certainly more vulnerable than your password, as is any “secret question” you’ve set up in case you forget your password.”
One thing I’ve finally realized is that the “secret question” is simply a password in a different form. You’d be surprised what my mother’s maiden name is. 🙂
Clive Robinson • October 28, 2007 11:01 AM
@Bruce,
With regard to Jeff Attwood’s comment
“Coordinate your efforts, and before you know it, some Latvian teenager has the whole hash database online.”
and your comment,
“While there are lots of clever time-memory trade-offs in the literature, you do realize that there are waaaay too many hashes to make this possible. 2^^80 is a real big number.”
Even if you bring it down to a more reasonable 32(2^40) bits (4TByte) of storage, which is within the average “pocket money” price range it realy does not get you anything.
Ask yourself the question “How many people can randomly search a large RAID array of 4Byte hashes at any given time?”.
The answer due to most hardware latency and random seek times is surprisingly low.
Then start figuring in HD MTTF/MTTR times (remember the RAID re-build time etc.), and things start to look even worse.
Oh and don’t forget the initial time to build (due to the very slow sorting (the one way function would be no good it it could be optomised), especially when the effective read/write times on large raid arrays compared to CPU times.
You will fairly quickly find that the ROI is not going to be worth while when compared to the cost of a brut force search.
There are ways you can improve things (solid state storage for instance) but not on any sensible budget “Latvia” let alone one of it’s younger generation is going to put forward.
Peter • October 28, 2007 1:41 PM
Not so hard, for a class project last year we replaced the crypt-md5 function with a cuda parallelized version in John the Ripper. We wanted to get the advantages of dictionary attacks and the speed of the GPGPU technology.
We called our version, “CUDA the Ripper.”
Of courese, we didn’t get as good a speedup as these guys (~10x if i remember), but we only really put two weeks work into it.
–Peter
Peter • October 28, 2007 1:42 PM
Not so hard, for a class project last year we replaced the crypt-md5 function with a cuda parallelized version in John the Ripper. We wanted to get the advantages of dictionary attacks and the speed of the GPGPU technology.
We called our version, “CUDA the Ripper.”
Of course, we didn’t get as good a speedup as these guys (~10x if i remember), but we only really put two weeks work into it.
–Peter
Konrads • October 29, 2007 2:31 AM
If password cracking is not a one-off thing, but a systematic effort, it makes sense to build big rainbow tables. In this case, the GPU acceleration is really good, as downloading 100GB over bittorrent isn’t that much fun.
Overall GPGPU is an interesting, developing area.
Tarkeel • October 29, 2007 7:57 AM
@Terry Cloth: “One thing I’ve finally realized is that the “secret question” is simply a password in a different form. You’d be surprised what my mother’s maiden name is. :-)”
As was said earlier, the problem here isn’t the people who read this blog, but normal users. I was helping a friend reset her hotmail password, and I actually managed to guess the reset-password on the first try, before she was able to remember it.
Anonymous Mike • October 29, 2007 10:33 AM
<shiver!> Bruce replied! To me!
I agree that while to actually house the password/hash for the entire keyspace is prohibitive (for the moment), you can certainly build/house enough of the keyspace to be effective. As CPU/disk get cheaper, it will continue to become more effective, never less.
It’s not if we’re screwed, it when. My answer is “a couple of weeks ago.” 😉
TSK • October 29, 2007 1:33 PM
I don’t understand how speed helps.
If you have physical access to the computer, you have normally won as dedicated attacker. So most attacks will come from the network where you can’t (?) read out the resulting hash. Lets concentrate simply on brute force, not
social engineering etc.
So why it is not possible to intentionally slow down the password check ? The best typewriter has something like 1000 characters per minute, meaning 20 ms.
50 ms are felt instantenous. So allow
minimal 10 ms for each character and block input for 50 ms for the next attempt and brute force attempts are senseless even with 5 characters; needing almost a year.
What is the problem ? Any help or link appreciated.
anonymous • October 29, 2007 2:37 PM
@TSK – You are missing one mode. Where you have access to a file of hashed/encrypted results. This could be an offline copy such as a backup, data captured off the wire, or data obtained online without full authority.
In this case the horse has left the barn and speed matters.
TSK • October 29, 2007 3:55 PM
Thanks Anon. But password files are normally deep embedded in the system and can be accessed only by a admin/superuser. So I think you refer to another file, right ?
In this case you must en-/decrypt the file for each key (the used algorithms modify the output strongly by tiny changes, so spurious similarities are no help) and test it with string comparison routines against a dictionary or likely phrases. I don’t know how much chars you need to identify the correct file, but I think 20-50 are a likely bet. This is a serious slowdown, especially because GPUs can’t handle strings well, to say the least.
It seems to me that the attack scenarios
always assume the best case for the attacker: You already have the hash value of the password and you can crunch it on the computer day for day with full speed.
Paeniteo • October 30, 2007 6:35 AM
@TSK: “But password files are normally deep embedded in the system and can be accessed only by a admin/superuser.”
Unless we talk about webapplications where passwords are usually stored in a database and accessible by the webapplication.
If there’s a security hole in the application, the password hashes may very well be compromised.
Anyway, a slowdown such as you suggest is done by more conscious developers.
Instead of saving MD5($password) into the database, they save MD5(MD5(MD5(…repeat 1000x…MD5($password)…)))
Adding a salt does not do any harm, either.
richrumble • October 30, 2007 3:21 PM
Elcomsoft also uses, on their office password cracker, a “key exhaustion” attack that is easily distributed to more than one PC, so pc1looks in 1-10,000’s key space, and pc2 looks for 10,001-20,000’s etc… AOPB it’s called
Advanced Office Password Breaker, or AOPB for short, is a program to decrypt Word and Excel 97/2000 files that have file open protection set, as well as Word and Excel XP/2003 files with default (Office 97/2000 compatible) encryption — guaranteed, regardless the password length and complexity. This is being done by trying all possible encryption keys (instead of brute-force and dictionary attacks) and takes only about ten days on single Pentium 4 PC (or just three-four days on faster dual-CPU systems).
Ahh the velvetsweatshop…
http://www.securiteam.com/windowsntfocus/6K003150KG.html
Different types of attacks work on different systems or implementations. Distributing the load between systems, or GPU’s, or CPU’s are very effective at speeding things up. JTR can be distributed by hand, try to BF passwords of 1-6 length on this pc, try 7-8 on this pc etc… Same with generating RainbowTables…
-rich
Meg Whitman • November 1, 2007 1:01 PM
Good article
Steve Jobs • November 1, 2007 1:02 PM
I like the idea!
kev • February 14, 2008 12:36 PM
it would be helpful to post benchmarks of AccessDatas application compared to Elcomsofts GPU code.
Also, how many people do you know owns an FPGA, Bruce? – thats the most critical point.
shrey • August 22, 2008 11:22 PM
in my pc i have installed a software name pc security and its password was security but now its not taking it so what to do now so that i can work properly.
Subscribe to comments on this entry
Sidebar photo of Bruce Schneier by Joe MacInnis.
Rr • October 26, 2007 12:37 PM
Way better technology? Based on what?