Cracking PGP In the Cloud 167
pariax writes "So you wanna build your own massively distributed password cracking infrastructure? Electric Alchemy has published a writeup detailing their experiences cracking PGP ZIP archives using brute force computing power provided by Amazon EC2 and a distributed password cracker from Elcomsoft."
Re:And tons of carbon enter the air (Score:5, Informative)
> I was under the impression that crypto like PGP was based on stuff which
> would (in theory) take millions of years to crack even with every machine on
> earth dedicated to it?
That's true if everything's equal. Including your passphrase. If the cipher
for encryption is 128-bit strong, then your password/passphrase needs to match
that. If it doesn't it's the weakest link, easier to attack than the actual
crypto algorithm and will take accordingly less time to crack.
Example: For a password composed only of lower-case a-z english characters, ;-)
you'd need 28 characters chosen in a true random fashion (think scrabble tiles
pulled out of a hat) to actually achieve a strength of 128-bit, that matches a
128-bit crypto or hash algorithm.
The strength of TFA 'sweetspot' passwords were somewhere around 60-bits.
Since even RC5 has been broken at 64-bits (distributed.net - though it took
some time), such passwords are OK for low-priority stuff but not, if say, the
NSA is after you
Bottom Line: Use Long, Unusual Passwords (Score:5, Informative)
First of all, the article is a very nice summary of the issues involved with setting up a cloud to crack passwords - the nuts and bolts, if you will. I liked that the authors took the time to look into the economics of trying to crack passwords, how much money it would cost vs. how long it would take. Password cracking is one example of massively scalable computing, which is presumably why the NSA allegedly has had to keep upgrading the electrical infrastructure at their headquarters. Elcomsoft certainly made a splash with their PGP-cracking software and managing to harness the power of cheap GPU cards (which are set up for parallel processing) was a bit of genius. That said, even massive horsepower runs into a brick wall once the passphrases become long and the encryption algorithm is good.
On page 2 of the article, the authors nicely summarize the cost of cracking longer and longer passwords. Once passwords start incorporating special characters (per SPEC), the cost shoots sky high even for relatively short passwords (i.e. $10MM+ for a 9 character password, $1BN for a 10-character password, the US national debt for a 12-character password). The article so clearly lays out why the various law enforcement agencies have been focusing on being able to force folk to disclose their encryption keys. The cost of cracking a well-executed encryption scheme combined with a good password is simply too high. So, go ahead and use those special characters, upper and lowercase, etc. to make life interesting for would-be snoops. But realize that unless trends in privacy rights swing the other way, law enforcement will simply compel key disclosure, as they have for years in the UK, for example.
Lastly, the article underscores the value of keychain-type schemes that allow many long passphrases to be stored in a accessible format. Make it easy to have long, complex passphrases and it becomes more likely that people will actually use them.
Re:And tons of carbon enter the air (Score:5, Informative)
In this case, it sounds like the customer was pretty glad they'd used weak passwords.
The implication is that they'd locked some files up in an encrypted zip, forgotten the password, and wanted the contents back.
If they'd chosen a stronger key, they'd not have got their files back.
TFA:
This analysis may be insightful as you develop your enterprise password policies, or choose your personal passwords.
(A good password policy is: don't forget your passwords!)
Re:All communications securely encrypted (Score:3, Informative)
One of the adversized features of ElcomSoft Distributed Password Recovery is that all network communications between password recovery clients and the server are securely encrypted. How is that possible, I wonder.
SSL would do. There's no real magic going on in that network conversation. "Try passwords 'alphabet' through to 'backgammon' and tell me when you're done".
Re:Can't you snoop on this ? (Score:3, Informative)
Only if your communications with the cloud are in the clear. Why would they be?
Re:And tons of carbon enter the air (Score:5, Informative)
The company surely did have the private PGP key lying around. They just forgot the password.
As an analogy, think of a safe. A good safe is hard to break in if you don't have the key. If you have the key, it's quite easy. Now you fear that someone could break in your house, get the key and open your safe. Therefore you put the key for the big safe into another, smaller safe. If you need to open the big safe, you first open the small safe, take out the key of the big safe and then open that.
Now if you have lost the key for the small safe, and the small safe is less secure than the big safe, you'll certainly not crack the big safe, but just the small safe in order to get the key of the big safe.
Now, the key for the small safe is your password, and the key of the big safe is the PGP key. If someone has access to the small safe (the password-protected PGP key), then the security of whatever is in the big safe is certainly limited by the security of the small safe.
Now with emails, the point is that the big safe (the encrypted email) is out in the public, while the small safe (the password-protected PGP key) is in your home (i.e. on your computer, which hopefully itself has appropriate protection against intruders).
So the security of your PGP encrypted mail is limited by the combination of the security of your computer and the security of your PGP password. If your computer is basically unprotected, and your PGP password is weak, then anyone can read your encrypted mail by simply breaking into your computer, copying the private PGP key, and breaking the password. If your computer is well-secured, the attacker will have a hard time to get your private PGP key, and if you PGP password is strong, the attacker will have a hard time to break it if he manages to get the PGP private key.
Re:And tons of carbon enter the air (Score:4, Informative)
> If the encryption software works as advertised, they would need the private
> key file to exploit this.
You are confusing public key encryption (1 private key & 1 public key) with
conventional/symmetric encryption (gpg -c) where no separate key per se is
required. The encrypted file is all you have.
Re:And tons of carbon enter the air (Score:4, Informative)
That's only a problem if you have no idea what the encrypted data might be. But in most reality-based cases, that's not the problem. You almost always have the clues you need.
In this case, for example, the file is a ZIP archive. That means the archive contains in the clear the original file names including any extensions, such as .jpeg, .bmp, .doc, .pdf, or whatever. All those file types have artifacts you can test for. They all have specific formats. They'll have version numbers, dimensions that must fall within reasonable boundaries, or other attributes that simply won't produce a coherent file unless they're correct.
For example, a JPEG image file is a container and is filled with markers identifying all the different sections. They all must be right or it won't display. So you'd start by looking for the SOI marker as the first byte of the file (0xffd8) or you'd throw it out. After the SOI you'd have to find another valid JPEG marker (two more bytes beginning with 0xFF.) So that's three bytes you'd have to match exactly, and the fourth byte would have to be on the list of valid markers. After you find the next marker, it'll probably be followed by a length (two or four more bytes). If that length is greater than your file size, it's a fail. Sure, if all that passes you'd have to decrypt more data to figure out if you're still in a valid file, but the chances are now only about 1 in 16 million keys tested. You then farm all these "potentials" to a machine or other process dedicated to deeper examination of the candidates.
If I were writing this, I'd have enough smarts in the key tester to look for all possibilities within the first blocksize of the cypher. Anything that looked reasonable at that point would be exported to the "evaluate potentials" system.
Every data file has its structure. You just have to look for it.
Re:Less geeky solution (Score:2, Informative)
Can we get a "-1 Wrong" moderation option?
Funny sig considering your post. Look, first thing; the authorities aren't stupid. The first thing they do is mirror your data, then test the passphrase you give them on the mirrored data. When your phassphrase deletes the data, they still have a copy backed up, and now you've bought yourself a prison sentence, or worse.
As to entering your ATM passphrase backward, that doesn't work anywhere. Some guy tried to make it a standard, but the authorities, noticing immediately all the problems with it, choose not to implement it anywhere. If you think you're right, and want to prove me wrong, go to Snopes and look it up.
Re:Pointless (Score:3, Informative)
Actually salting does not help against brute-force. It only helps against dictionary attacks.
It also helps against rainbow table attacks, which I believe the GP was referring to. Salting the hashes makes it much less feasible for someone to develop a rainbow table database, unless they are specifically targeting your system as opposed to every Windows instance on the planet.
Re:All communications securely encrypted (Score:3, Informative)
Noooo... their system is built to brute-force passwords. That has basically nothing at all to do with cracking an SSL session.
See, SSL uses asymmetric encryption to generate a large-ish session key between two parties, which can then be used in conjunction with a symmetric cipher to protect the session. So, while brute-forcing passwords is really just a matter of throwing hardware at the problem, brute-forcing an SSL session key likely requires more energy than is available in the known universe, which means you're forced to find a weakness in the cipher that you can exploit to reduce the computational complexity of the problem.
Re:Bottom Line: Use Long, Unusual Passwords (Score:3, Informative)
Wrong. Dead wrong.
Reason 1: Rainbow tables only work when the cryptosystem doesn't use salt (or uses it incorrectly). These days everyone uses salt. It's not a big secret.
Reason 2: Even if salt wasn't used, Rainbow tables aren't feasible against long passwords. Rainbow tables are essentially just saving the results of one attack and using them on subsequent attacks. If the password in question is long enough, even the "one attack" (table precomputations) will never get to that password.
So, educate yourself. Rainbows tables are not some kind of magic crypto attack. They are very limited in scope. These days pretty much all they're good for is Windows passwords and old 40-bit MS Office documents. Definitely not PGP.
Re:But did it work (Score:1, Informative)