Yes obviously cracking passwords scales linearly, we've known that for a long time. Oh, you could get 100 machines brute forcing instead of one, but what good is that? Either the password is crap and you crack is easily, or it's helluva complex and scaling it up 100x won't do a damn thing. In this case it looks like they just picked some random range and said "Hey, this is unfeasible on a single machine and doable on a cloud, let's do that" but they haven't produced any credible evidence it is in this range. Not unless semi-complex password possibility matches their corporate password policy or whatever.
Yes obviously cracking passwords scales linearly, we've known that for a long time. Oh, you could get 100 machines brute forcing instead of one, but what good is that? Either the password is crap and you crack is easily, or it's helluva complex and scaling it up 100x won't do a damn thing. In this case it looks like they just picked some random range and said "Hey, this is unfeasible on a single machine and doable on a cloud, let's do that" but they haven't produced any credible evidence it is in this range. Not unless semi-complex password possibility matches their corporate password policy or whatever.
It is significant because the lone hacker in his basement or the IT department of your unethical competitor might not have a spare server farm with 200 CPUs lying around. They show just how effortless it has become to do brute-force if you have a couple of minutes to set it up and a few spare bucks for the computing power... (And I bet that very few corporations have a password policy that mandates anything exceeding 8-char alphanumeric - which can be cracked for 45 bucks, as they show...)
It can only be cracked for 45 bucks if the attempt can be parallelized. Which is not always the case.
For example if the password is used for logging into a server, the admins will probably notice 100 amazon machines making brute force attempts, and if it takes seconds per try, that slows things down a lot. More so if the target server "falls over" or crashes in the process;).
Yes, but what if they recover a hash of the password? It better be well salted...
Actually salting does not help against brute-force. It only helps against dictionary attacks.
However other things help, for example instead of running your password/phrase through a crypto-hash once, do it a million times or, say, for 100ms (store the number or iterations). This increases effort proportionally.
Example: SHA-256 does around 100MB/sec on a single modern CPU. That is roughly 3 million hashes/sec. Doing this for 0.
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.
In most cases, a 9-char password is some 96 times (number of printable characters) harder than an 8-char password,
I'd believe 30 -40, but not 96. Most people are going to use letters and a small number of punctuation, and I'd wager that testing half of that will get you 90% of the possible choices. If it's just english words, I'll go with 16 as the multiplier, just given the info content of most english.
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.
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".
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 me
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.
Passwords are protected in the US by the fifth amendment, for now...
The UK is a different story, though you can always claim to have forgotten your password.
Perhaps an interesting set up would be having 2 computers on separate power supplies running full disk encryption. Each can only boot by requesting a keyfile from the other.
Hence you can shut one down, but when both go down, the two systems become unbootable.
In a police seizure, they will likely disconnect both computers, and unbeknownst to them, comple
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.
Take a look at the rainbow table you described. ASCII and length 256? That's 256^256, i.e. huge. Even if you restrict yourself to a modest subset of 70 characters (easily typable), and no more than 10 characters in length (too short in many cases), you need to store about 2.8 * 10^18 passwords. Just the MD5 hashes for a table like that would take up over 40000 petabyte.
Does the benefit of special characters in passwords derive from their actual use or in the expansion of the possible character set? If the possible character set includes the special characters, must they then be used in order to gain the advantage?
If one is going to crack passwords, one may need to (eventually) test the key space. If your passphrase is in the "easy" part of the key space (such as if you don't use special characters), it will be found very early on. So, yes -- you must use special charact
I have an idea : how about a self destructing key? There would be a physical USB key that would have your passphrases on it. The passphrases would be quite lengthy strings of randomly generated characters, effectively un-forcable unless there's a massive weakness in the encryption algorithm.
The key would have a small CPU and lithium ion battery. All the components would be potted in epoxy, and you would be able to put an outer shell around the key resembling a common brand of USB stick.
The best solution (if you are dealing with a desktop system) is to have the pass-phrase and keys but also have a small GPS module. If the usb key is not close to where it should be (with a fairly big margin for the fact that cheap GPS modules arent exactly accurate) it would erase the pass-phrase
If they try to force you to hand over your password (e.g. UK RIP act), you just hand it over (to the guys who seized your computer and are now trying to use it somewhere else other than the required GPS location) and boom, the data is gone forever.
If you need to move house, just log in from the old house and reset the GPS then when you get to the new house, log in and put in the new coordinates.
The best answer of all is "physical seganography" i.e. 802.11 NAS built into something that the cops are unlikely to seize (yet which has a legitimate need to be plugged in and doing what it does)
I looked at EC2 for raw processing power earlier this year (my company needs to train a lot of neural nets) and it just isn't worth it, unless you only need the power short term. A high-performance EC2 node gives you 8 cores running at (very roughly) the equivalent of a 2GHz P4, and costs $0.68/hr == about $460 per month, which is only a little less than what an equivalent box (probably a 2.83GHz Core 2 Quad or similar) would cost you. Put power to run that box down at about $0.05 per hour and you can build your own local cluster of equivalent performance for around the same amount of money as you'll save in your first month and a half of operation.
I looked at EC2 for raw processing power earlier this year (my company needs to train a lot of neural nets) and it just isn't worth it, unless you only need the power short term. A high-performance EC2 node gives you 8 cores running at (very roughly) the equivalent of a 2GHz P4, and costs $0.68/hr == about $460 per month, which is only a little less than what an equivalent box (probably a 2.83GHz Core 2 Quad or similar) would cost you. Put power to run that box down at about $0.05 per hour and you can build your own local cluster of equivalent performance for around the same amount of money as you'll save in your first month and a half of operation.
Indeed. EC2 is rather expensive for most applications. It really only pays off if you may need a lot of power on short notice (but usually need none). The article describes one of the very few general applications. There is also the problem that even EC2 only scales so far. You would probably not get the cores to do a 12 char password in parallel. In addition, EC2 has problems like confidentiality and data transfer also costs money. And you have no control over how reliable and available the resources are.
Having done a (small) bit of high-performance computing myself, I believe the most cost effective way is to get some bright people that do understand current computer hardware and your problem, and then have them get the hardware they think does the job best, preferably of the white box variant. I went so far to get components, because having a student assemble them got me something like 20% more cores for the same money and exactly the hardware I wanted. Never had serious issues in several years with the resulting infrastructure.
EC2 is rather expensive for most applications. It really only pays off if you may need a lot of power on short notice (but usually need none). The article describes one of the very few general applications.
I think most people don't realize just how often they need a lot (or even a little) computing power on short notice. Once you get used to that way of thinking, it's a little addictive. By way of example:
I host one of my company's websites on Dreamhost. Am I insane? Dreamhost experiences an outage every few months or so. Incompatible with a business application, right?
Wrong. I have an EC2 bundle with a startup script that automatically configures the instance and fails the IP address over. If my company's website is ever down for more than 2 minutes, a failover is triggered. The website on EC2 takes about 2 minutes to come up, so my maximum downtime is 5 minutes or so. That's an acceptable amount of downtime for my application, a brochureware site that displays vacant apartments and accepts rental applications (several hours, naturally, would be unacceptable).
EC2 as a cold spare saves me money. If I had to use a reliable webhost, it would cost me, what, $50/mo? Dreamhost costs $5, and I probably use about $5-$10/yr in EC2 charges for the cost spare. Based on the above assumptions (I have no idea what a reliable webhost costs these days), EC2 saves me roughly $530/yr.
What another example? A client of mine has a deployment process where they first deploy to a staging environment before production. Because the production environment has a clustered DB and clustered app server, their staging environment has 2 DB nodes and 2 web nodes. That's 4 machines that see roughly 50 hours of use per year. Not efficient at all.
We considered VMware, but they didn't have the admin expertise in-house, and I forget what the license cost was, but that was an issue, too. In addition, they could not do load testing because they didn't have enough boxes to replicate the production system architecture. Enter EC2.
Now, they spin up as many EC2 instances as they need for whatever testing scenario they need. 4 instances for application staging, and 15 for load testing, at a cost of a fraction of one of their staging boxes that sat idle 99.9% of the time.
Like I said, the concept that you can have a virtual box whenever you need it and then throw it away when you're done is very addicting. I find it to be extremely convenient.
Don't forget other cosets: cooling, system administration, datacenter space, backups, racks, switches, KVMs, UPSs, network administration, maintenance, etc.
No question EC2 is expensive if you plan on fully-utilizing that hardware. But that's why it's called the Elastic Compute Cloud, not the Static Compute Cloud. If your computational needs are static, EC2 is most definitely the wrong tool for the job.
When building your own system, you need to purchase enough hardware to cover your peak load. As a result, you have to buy more hardware than you usually need. Since I'm on the road, I don't have my paper archives accessible, but I think that average utilization tends to run at around 10%. When you use EC2, you only need to pay for peak hardware when you need the peak hardware. Thus, in our studies, EC2 tends to be cheaper for small/medium organizations (unless your workload is extremely stable). (I thi
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?
> 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;-)
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.
Scrabble tiles would be an exceptionally bad choice.
I'm also a bit confused. I've never used PGP to make an encrypted zip file, but I use GnuPG to encrypt emails all the time and I, too, was under the impression that it was infeasible in practice to brute force the encryption.
Is the difference that with PGP/GnuPG email encryption, our passwords are merely decrypting our keys which are themselves fully 128 or 256 bits long or whatever? Whereas in this situation with the ZIP file there was no separate key - the password was the key? (I haven't read all of TFA)
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.
Cracking algorithm attempts to open your encrypted archive using a list of, say, 20,000 english words. 'password' is 5th on the list. After 5 iterations, you notice that your decryption attempt has yielded data that looks like a valid zip archive, or contains english words. Result. You win the internets.
You can refine this.
1. Attempt a password list crack. 2. Attempt a Markov-chain based crack, looking for english-like words generated by your Markov Chain algorithm. Like, say. 'bibble' or 'foglet'. Tr 3. Repeat the above for all letter case combinations, and number/letter replacements - like B1bb7e, or f0Glet.
Et cetera,
The edge you have is that people often choose known words as passwords, or easy-to-remember nonsense words.
This reduces your password search space *hugely*.
For example, say your pgp doodad accepts up to 10 character passwords formed from any combination of letter case or number. 26 lowercase letter, 26 uppercase letters, 10 numbers. Your maximum search space would be the sum of all (26+26+10)^n, where n iterates from 1 to 10, or 853,058,371,866,181,866, or 8.5x10^17. This is the size of the set of all possible mixed case alphanumeric passwords up to a maximum length of 10. You would have to try each of these combinations to fully search this space. This is called 'brute forcing'.
It is a *much* larger number of passwords than the 20,000 in your dictionary list....
So, you use the search space limiting techniques *first*, which will yield a result in 95% of all cases. Then, you try brute force, or give up.
I thought the problem was that there was an infinite number of matching passphrases producing invalid results. Like, only a very simple hash or CRC - 1 or 2 bytes checks the validity of the passphrase to protect from common typos, but if you try even semi-hard, you will get a hash collision, the data decrypts, but it decrypts to garbage - a standard GIGO filter with a very weak anti-garbage protection on input.
This way, on top of one correct result you should get an infinite number of incorrect results and
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.
> 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.
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?
Yes, but the search space is significantly lower if you assume an password that's 1-8 latin alphanumeric characters, as this exercise did.
It's still 122 days on 10 VMs. One tenth of that on 100VMs.
It wasn't carbon, but the fuel consumed that was my first thought. Back when distributed.net was busy burning energy to win these pointless challenges, I did some rough calculations on the electricity required to solve it.
Turns out that the energy spent breaking RC5-64 used somewhere between 2 and 50 *trains* full of coal.
And that was only the energy directly consumed by the computers involved, and not any of the heating or cooling costs associated with it. And sure, more modern CPUs are more energy efficient, and I extrapolated the figures from a lot of published sources and made a lot of assumptions. But regardless of CO2 or greenhouse gasses or dirty coal or any of that environmental stuff, that's a lot of irreplaceable fossil fuel that's now gone.
I don't think it's sad or tainted to consider the overall impact of what you do. Saying "oh, I want to help search for E.T." is one thing. It may cost you an extra 1440 kWh/day, but you have the money, no big deal. But understanding that SETI@HOME is causing tens of thousands of people around the globe to collectively burn tons of fuel every day might make some of the volunteers rethink their decision. Ignoring that is the kind of perspective that thoughtlessly sucks up our finite resources.
And no, I don't consider alien hunting a valuable use of energy, at least not at this time in our history. Once we have fusion reactors or some other form of "free energy", all that will change.
Go ahead and crack keys, search for Extra Terrestrials, or fold proteins, or whatever you want to do with your box. Leave your lights on 24x7. Run the furnace and the air conditioner together. Just understand that what you do today has an impact, and consider the value of the outcome.
Distrubuted Computing (Score:5, Funny)
If only they'd thought of using distributed computing for the first post, instead of password cracking!
Pointless (Score:3, Interesting)
Yes obviously cracking passwords scales linearly, we've known that for a long time. Oh, you could get 100 machines brute forcing instead of one, but what good is that? Either the password is crap and you crack is easily, or it's helluva complex and scaling it up 100x won't do a damn thing. In this case it looks like they just picked some random range and said "Hey, this is unfeasible on a single machine and doable on a cloud, let's do that" but they haven't produced any credible evidence it is in this range. Not unless semi-complex password possibility matches their corporate password policy or whatever.
Re: (Score:3, Interesting)
Yes obviously cracking passwords scales linearly, we've known that for a long time. Oh, you could get 100 machines brute forcing instead of one, but what good is that? Either the password is crap and you crack is easily, or it's helluva complex and scaling it up 100x won't do a damn thing. In this case it looks like they just picked some random range and said "Hey, this is unfeasible on a single machine and doable on a cloud, let's do that" but they haven't produced any credible evidence it is in this range. Not unless semi-complex password possibility matches their corporate password policy or whatever.
It is significant because the lone hacker in his basement or the IT department of your unethical competitor might not have a spare server farm with 200 CPUs lying around. They show just how effortless it has become to do brute-force if you have a couple of minutes to set it up and a few spare bucks for the computing power... (And I bet that very few corporations have a password policy that mandates anything exceeding 8-char alphanumeric - which can be cracked for 45 bucks, as they show...)
Re: (Score:2)
For example if the password is used for logging into a server, the admins will probably notice 100 amazon machines making brute force attempts, and if it takes seconds per try, that slows things down a lot. More so if the target server "falls over" or crashes in the process
Re: (Score:2)
Yes, but what if they recover a hash of the password? It better be well salted ...
In reality, it wouldn't cost 45 bucks. A big botnet would do the heavy lifting, and crack millions of passwords at the same time. Ouch.
Re: (Score:3, Insightful)
Re: (Score:3, Interesting)
Actually salting does not help against brute-force. It only helps against dictionary attacks.
However other things help, for example instead of running your password/phrase through a crypto-hash once, do it a million times or, say, for 100ms (store the number or iterations). This increases effort proportionally.
Example: SHA-256 does around 100MB/sec on a single modern CPU. That is roughly 3 million hashes/sec. Doing this for 0.
Re: (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: (Score:2)
Even TFA story say to cover 50% of the keyspace for a length 12 password you're looking at $1.2M in EC2 fees.
Re: (Score:2)
Either the password is crap and you crack is easily, or it's helluva complex and scaling it up 100x won't do a damn thing
Or maybe the password is apparently complex to the average user, but actually not so much. How would you classify "Hello123" or "Hottie69" ?
I am sure that there is plenty of money to be made with people who think that they are safe...
Re: (Score:3, Funny)
1995: mail, shopping, and parallel computing.... on The Internet
2009: mail, shopping, and parallel computing .... in The Cloud
Re: (Score:3, Insightful)
In most cases, a 9-char password is some 96 times (number of printable characters) harder than an 8-char password,
I'd believe 30 -40, but not 96. Most people are going to use letters and a small number of punctuation, and I'd wager that testing half of that will get you 90% of the possible choices. If it's just english words, I'll go with 16 as the multiplier, just given the info content of most english.
Wanna be careful (Score:2)
They will want to be careful or else they just might get arrested. [slashdot.org]
In a word (Score:5, Funny)
So you wanna build your own massively distributed password cracking infrastructure?
No
All communications securely encrypted (Score:3, Interesting)
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.
Re: (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: (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 me
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: (Score:2, Interesting)
Passwords are protected in the US by the fifth amendment, for now...
The UK is a different story, though you can always claim to have forgotten your password.
Perhaps an interesting set up would be having 2 computers on separate power supplies running full disk encryption. Each can only boot by requesting a keyfile from the other.
Hence you can shut one down, but when both go down, the two systems become unbootable.
In a police seizure, they will likely disconnect both computers, and unbeknownst to them, comple
Re: (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.
Re: (Score:3, Insightful)
Re: (Score:3, Interesting)
If one is going to crack passwords, one may need to (eventually) test the key space. If your passphrase is in the "easy" part of the key space (such as if you don't use special characters), it will be found very early on. So, yes -- you must use special charact
Windows, yuck (Score:2)
What chore that they need to use Windows. For a brute force password guesser, most Slashdotters could write it in 10 lines of perl.
Re:Windows, yuck (Score:4, Funny)
What chore that they need to use Windows. For a brute force password guesser, most Slashdotters could write it in 10 lines of perl.
I think ten lines of Perl would be the ideal password somehow.
Parent
Hmm (Score:2)
I have an idea : how about a self destructing key? There would be a physical USB key that would have your passphrases on it. The passphrases would be quite lengthy strings of randomly generated characters, effectively un-forcable unless there's a massive weakness in the encryption algorithm.
The key would have a small CPU and lithium ion battery. All the components would be potted in epoxy, and you would be able to put an outer shell around the key resembling a common brand of USB stick.
In order to use th
Re:Hmm (Score:5, Interesting)
The best solution (if you are dealing with a desktop system) is to have the pass-phrase and keys but also have a small GPS module. If the usb key is not close to where it should be (with a fairly big margin for the fact that cheap GPS modules arent exactly accurate) it would erase the pass-phrase
If they try to force you to hand over your password (e.g. UK RIP act), you just hand it over (to the guys who seized your computer and are now trying to use it somewhere else other than the required GPS location) and boom, the data is gone forever.
If you need to move house, just log in from the old house and reset the GPS then when you get to the new house, log in and put in the new coordinates.
Parent
Re: (Score:3, Interesting)
The best answer of all is "physical seganography" i.e. 802.11 NAS built into something that the cops are unlikely to seize (yet which has a legitimate need to be plugged in and doing what it does)
Not the way of doing it (Score:5, Insightful)
I looked at EC2 for raw processing power earlier this year (my company needs to train a lot of neural nets) and it just isn't worth it, unless you only need the power short term. A high-performance EC2 node gives you 8 cores running at (very roughly) the equivalent of a 2GHz P4, and costs $0.68/hr == about $460 per month, which is only a little less than what an equivalent box (probably a 2.83GHz Core 2 Quad or similar) would cost you. Put power to run that box down at about $0.05 per hour and you can build your own local cluster of equivalent performance for around the same amount of money as you'll save in your first month and a half of operation.
Re:Not the way of doing it (Score:4, Interesting)
Indeed. EC2 is rather expensive for most applications. It really only pays off if you may need a lot of power on short notice (but usually need none). The article describes one of the very few general applications. There is also the problem that even EC2 only scales so far. You would probably not get the cores to do a 12 char password in parallel. In addition, EC2 has problems like confidentiality and data transfer also costs money. And you have no control over how reliable and available the resources are.
Having done a (small) bit of high-performance computing myself, I believe the most cost effective way is to get some bright people that do understand current computer hardware and your problem, and then have them get the hardware they think does the job best, preferably of the white box variant. I went so far to get components, because having a student assemble them got me something like 20% more cores for the same money and exactly the hardware I wanted. Never had serious issues in several years with the resulting infrastructure.
Parent
Re:Not the way of doing it (Score:4, Interesting)
EC2 is rather expensive for most applications. It really only pays off if you may need a lot of power on short notice (but usually need none). The article describes one of the very few general applications.
I think most people don't realize just how often they need a lot (or even a little) computing power on short notice. Once you get used to that way of thinking, it's a little addictive. By way of example:
I host one of my company's websites on Dreamhost. Am I insane? Dreamhost experiences an outage every few months or so. Incompatible with a business application, right?
Wrong. I have an EC2 bundle with a startup script that automatically configures the instance and fails the IP address over. If my company's website is ever down for more than 2 minutes, a failover is triggered. The website on EC2 takes about 2 minutes to come up, so my maximum downtime is 5 minutes or so. That's an acceptable amount of downtime for my application, a brochureware site that displays vacant apartments and accepts rental applications (several hours, naturally, would be unacceptable).
EC2 as a cold spare saves me money. If I had to use a reliable webhost, it would cost me, what, $50/mo? Dreamhost costs $5, and I probably use about $5-$10/yr in EC2 charges for the cost spare. Based on the above assumptions (I have no idea what a reliable webhost costs these days), EC2 saves me roughly $530/yr.
What another example? A client of mine has a deployment process where they first deploy to a staging environment before production. Because the production environment has a clustered DB and clustered app server, their staging environment has 2 DB nodes and 2 web nodes. That's 4 machines that see roughly 50 hours of use per year. Not efficient at all.
We considered VMware, but they didn't have the admin expertise in-house, and I forget what the license cost was, but that was an issue, too. In addition, they could not do load testing because they didn't have enough boxes to replicate the production system architecture. Enter EC2.
Now, they spin up as many EC2 instances as they need for whatever testing scenario they need. 4 instances for application staging, and 15 for load testing, at a cost of a fraction of one of their staging boxes that sat idle 99.9% of the time.
Like I said, the concept that you can have a virtual box whenever you need it and then throw it away when you're done is very addicting. I find it to be extremely convenient.
Parent
Re:Not the way of doing it (Score:4, Insightful)
Don't forget other cosets: cooling, system administration, datacenter space, backups, racks, switches, KVMs, UPSs, network administration, maintenance, etc.
No question EC2 is expensive if you plan on fully-utilizing that hardware. But that's why it's called the Elastic Compute Cloud, not the Static Compute Cloud. If your computational needs are static, EC2 is most definitely the wrong tool for the job.
Parent
Re: (Score:3, Interesting)
Re: (Score:3, Interesting)
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?
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
Parent
Re: (Score:3, Interesting)
Schneier had an interesting piece on deriving a limit of the necessary key length from thermodynamics. ... assuming your password is only bruteforce-able ... otherwise http://xkcd.com/538/ [xkcd.com]
http://www.schneier.com/blog/archives/2009/09/the_doghouse_cr.html [schneier.com]
Re: (Score:3, Insightful)
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.
Scrabble tiles would be an exceptionally bad choice.
Re: (Score:3, Funny)
Damnit, my password is all vowels again!
Re: (Score:2, Interesting)
I'm also a bit confused. I've never used PGP to make an encrypted zip file, but I use GnuPG to encrypt emails all the time and I, too, was under the impression that it was infeasible in practice to brute force the encryption.
Is the difference that with PGP/GnuPG email encryption, our passwords are merely decrypting our keys which are themselves fully 128 or 256 bits long or whatever? Whereas in this situation with the ZIP file there was no separate key - the password was the key? (I haven't read all of TFA)
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.
Parent
Re:And tons of carbon enter the air (Score:4, Interesting)
To pick a trivial example.
Your password is 'password'.
Cracking algorithm attempts to open your encrypted archive using a list of, say, 20,000 english words. 'password' is 5th on the list. After 5 iterations, you notice that your decryption attempt has yielded data that looks like a valid zip archive, or contains english words. Result. You win the internets.
You can refine this.
1. Attempt a password list crack.
2. Attempt a Markov-chain based crack, looking for english-like words generated by your Markov Chain algorithm. Like, say. 'bibble' or 'foglet'. Tr
3. Repeat the above for all letter case combinations, and number/letter replacements - like B1bb7e, or f0Glet.
Et cetera,
The edge you have is that people often choose known words as passwords, or easy-to-remember nonsense words.
This reduces your password search space *hugely*.
For example, say your pgp doodad accepts up to 10 character passwords formed from any combination of letter case or number. 26 lowercase letter, 26 uppercase letters, 10 numbers. Your maximum search space would be the sum of all (26+26+10)^n, where n iterates from 1 to 10, or 853,058,371,866,181,866, or 8.5x10^17. This is the size of the set of all possible mixed case alphanumeric passwords up to a maximum length of 10. You would have to try each of these combinations to fully search this space. This is called 'brute forcing'.
It is a *much* larger number of passwords than the 20,000 in your dictionary list....
So, you use the search space limiting techniques *first*, which will yield a result in 95% of all cases. Then, you try brute force, or give up.
Parent
Re: (Score:3, Interesting)
I thought the problem was that there was an infinite number of matching passphrases producing invalid results. Like, only a very simple hash or CRC - 1 or 2 bytes checks the validity of the passphrase to protect from common typos, but if you try even semi-hard, you will get a hash collision, the data decrypts, but it decrypts to garbage - a standard GIGO filter with a very weak anti-garbage protection on input.
This way, on top of one correct result you should get an infinite number of incorrect results and
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.
Parent
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!)
Parent
Re:And tons of carbon enter the air (Score:4, Funny)
Parent
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.
Parent
Re:And tons of carbon enter the air (Score:4, Insightful)
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?
Yes, but the search space is significantly lower if you assume an password that's 1-8 latin alphanumeric characters, as this exercise did.
It's still 122 days on 10 VMs. One tenth of that on 100VMs.
Parent
Re:And tons of carbon enter the air (Score:4, Funny)
How do you know they weren't cracking a PGP'd zip archive containing secret documents about alien protein folding technology?
Parent
Re:And tons of carbon enter the air (Score:5, Interesting)
It wasn't carbon, but the fuel consumed that was my first thought. Back when distributed.net was busy burning energy to win these pointless challenges, I did some rough calculations on the electricity required to solve it.
Turns out that the energy spent breaking RC5-64 used somewhere between 2 and 50 *trains* full of coal.
And that was only the energy directly consumed by the computers involved, and not any of the heating or cooling costs associated with it. And sure, more modern CPUs are more energy efficient, and I extrapolated the figures from a lot of published sources and made a lot of assumptions. But regardless of CO2 or greenhouse gasses or dirty coal or any of that environmental stuff, that's a lot of irreplaceable fossil fuel that's now gone.
I don't think it's sad or tainted to consider the overall impact of what you do. Saying "oh, I want to help search for E.T." is one thing. It may cost you an extra 1440 kWh/day, but you have the money, no big deal. But understanding that SETI@HOME is causing tens of thousands of people around the globe to collectively burn tons of fuel every day might make some of the volunteers rethink their decision. Ignoring that is the kind of perspective that thoughtlessly sucks up our finite resources.
And no, I don't consider alien hunting a valuable use of energy, at least not at this time in our history. Once we have fusion reactors or some other form of "free energy", all that will change.
Go ahead and crack keys, search for Extra Terrestrials, or fold proteins, or whatever you want to do with your box. Leave your lights on 24x7. Run the furnace and the air conditioner together. Just understand that what you do today has an impact, and consider the value of the outcome.
Parent
Re: (Score:3, Insightful)
No, they've been approached by a client who's forgotten the password they used. The client's told them they used 1-8 alphanumerics in the password.
In this case, the mapping to a binary key is irrelevant to the size of the brute forcing task.
Re: (Score:3, Informative)
Only if your communications with the cloud are in the clear. Why would they be?