oclHashcat v1.02 support added to crack 1Password Cloud Keychain: http://t.co/Mk9qnu5LhL
— hashcat (@hashcat) March 9, 2014
To understand why this is really good news for us and for 1Password users, it is important to know what “crack” means in this context. I’ll come back round to that and why we encourage the developers of hashcat, John the Ripper, and cryptohaze to take a crack at 1Password. But first, let’s talk about this news and what it says about your password security.
Cracking fast and slow
If someone gets your 1Password data, they will not be able to decrypt it without your Master Password. A determined attacker might then try to guess your Master Password. Your job is to pick a good Master Password so that it will take trillions of guesses before the attacker finds the right one. Our job is to make sure that they can’t make millions of guesses per second on common hardware, thus significantly slowing down the guessing process, ideally to the point of futility. We do our job by using a “slow hash” for deriving encryption keys from your Master Password. In 1Password 4, that slow hash is PBKDF2-HMAC-SHA512. For the Agile Keychain Format it is PBKDF2-HMAC-SHA1.
Jens Stuebe, the developer of a password hashing system called hashcat, has been testing just how many guesses per second he can get out of hashcat for the 1Password 4 data format. The hashcat demonstration showed fewer than 500 guesses per second, but with somewhat beefier hardware and a more realistic data file, a better estimate based on the hashcat data would be between 5,000 and 20,000 guesses per second. For all of the calculations below, I will use the more pessimistic (for us, the defender) estimate of 20,000 guesses per second. It’s not because I think the pessimistic estimate is the most realistic, but simply that it is better to err on the side of caution.
If you use a four word password from the scheme described in Toward Better Master Passwords, then at 20,000 guesses per second it would take more than 5,600 years for a high-end PC with with multiple graphics processing units (GPUs) to work through all of the 3.65 trillion equally possible passwords. Of course, the attacker won’t have to try all of those. On average, she will find the right one after going through about half of the possibilities. So the average time to crack will be about 2,800 years. If you use a five word password, then the average time to crack will be more than 20 million years.
We like crackers
With enough time (perhaps far more time than the life of the universe) it will always be logically possible to guess a Master Password. This is simply the nature of the beast. We need to know how many guesses an attacker can make in a second, a day, a year with the resources available to them so that we can devise the most effective defenses against these sorts of attacks.
We make our own estimates, but the best estimates come from looking at real data. We will, on occasion, run our own tests but the people who specialize in password cracking are the people who perform the most stringent tests and will look for things that we might not notice. We want to know how hard they have to work at guessing passwords. We are extremely supportive of projects like John the Ripper, hashcat, and Cryptohaze. Indeed, conversation with people involved in these projects has very much helped us develop better resistance to password cracking.
This is one of several reasons why we are open about our data format. We get better analysis from the security community by doing so. Hashcat, and John the Ripper, worked against some sample data we make available to the public.
Cracking isn’t breaking
When crackers develop tools to guess at 1Password Master Passwords, they are not “breaking” anything. They aren’t exploiting vulnerabilities. They are just automating password guessing. Because they are working directly on the data files themselves, not with the 1Password software, things like lock-outs after multiple failed guesses aren’t an option (and don’t provide any meaningful security against encryption tools like this).
The technical stuff
The 1Password 4 data format uses PBKDF2-HMAC-SHA512 with an absolute minimum of 10,000 iterations when transforming a Master Password to a decryption key. I’m not going to explain what all of that means, but I will say that PBKDF2 is a Password Based Key Derivation Function that is designed to require that there be lots of computation in getting from an entered password to a key. It is specifically designed to slow down cracking attempts.
The attacker is able to build special machines for their cracking efforts, and software carefully optimized for that hardware. Defenders like us have to be able to process a single password in an acceptable amount of time for them on the hardware in their pockets. As a consequence, the attacker can process a candidate password much more quickly than the legitimate user. @bitwiesil, the developer of Cryptohaze, describes this as an Attacker/Defender Ratio (ADR).
For example: if it takes 1/4 of a second for a user’s Master Password to be processed on their mobile device, but the attacker using specialize hardware can make 10,000 guesses per second, the ADR would be 2,500. In a perfect world, the ADR should be 1:1, but that is never going to happen. Plus, ADR in the tens of thousands, instead of in the millions or billions, is a hard but more realistic goal.
The limits of PBKDF2
PBKDF2 isn’t perfect. Most importantly, it can only go so far. We can reach a point where even tiny improvements to a password (say, just adding a digit) can offer far more additional protection than adding extra strength to PBKDF2. For example, adding a single random digit to the end of a password will offer as much as going from 30,000 PBKDF2 iterations to 300,000. And the latter can do real harm in making legitimate decryption too slow. Increasing the number of PBKDF2 iterations does not change the Attacker/Defender ratio at all.
There are a couple of other things that PBKDF2 doesn’t do. When it uses SHA1 internally (a very common configuration), it can be optimized to run extremely quickly in GPUs, giving the attacker a high ADR. Computers built with several (or many) GPUs operating in parallel can still perform many billions of SHA1 computation per second. GPUs cannot be so easily tuned when PBKDF2 uses SHA512 instead of SHA1. Our use of SHA512 within PBKDF2 in 1Password 4 is overwhelmingly the biggest reason that we are seeing such a small Attacker Defender Ratio in the hashcat report.
There is another, more subtle issue with PBKDF2 which can allow the attacker to double the ADR in some peculiar cases. Those cases can be avoided (once people know to avoid them), and a doubling of the ADR is not a big deal. But this does show that PBKDF2 is not the slow hash we would design today.
PBKDF2 is not “memory hard”. It is designed to raise the cost in computation for both attacker and defender, but it doesn’t force a substantial demand on computer memory. If, as the case has been, that the price of computations falls faster than the price of computer memory, the attacker can affordably purchase or rent a fleet of fast processors. But, if we build a slow hash function that also requires substantial memory use, we have more flexibility in trying to reduce the ADR.
So why do we stick with PBKDF2?
For all of its warts, PBKDF2 is the best choice for 1Password today, although it may not be tomorrow. We can mitigate some of the limitations of PBKDF2 in our design, which we currently do. After all, the great results that we have from this weekend’s hashcat report show that we continue to be successful with it.
The best alternative to PBKDF2 that is reasonably well available and scrutinized is scrypt. If scrypt or similar had been further along as a standard, we probably would have used that. But because you need to unlock your 1Password data on a variety of different platforms, we need to use cryptographic functions that are included in well-tested libraries for all of those platforms.
This is why the Password Hashing Competition is so important. This is an effort to develop and agree upon a design for a successor to PBKDF2 that takes into account everything we’ve learned since it was first developed. The aim is that the successor will have enough support to become available to developers in many cryptographic tool kits. But that is a hope for the future. Right now we continue to use PBKDF2 in a way that takes its various quirks into account.
Your part of the job
Even the slowest hash with a perfect Attacker/Defender Ratio can’t protect a weak Master Password. Our job is to make sure that, when an attacker needs to guess trillions of passwords, they have to really work to do so. Your job is to pick a good Master Password so that it is trillions of passwords they need to guess instead of thousands. In our sample data that hashcat used, the password was “fred” (this was also made public). So even performing less than 500 guesses per second, hashcat was able to find the password “fred” in less than a minute.
Updated to correct spelling and add in a few links.