Posts

Crackers report great news for 1Password 4

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.

keep calm

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.

20-and-5K-guesses-per-sec

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.

1Password is Ready for John the Ripper

John the Ripper, the pre-eminent password cracking tool, is getting ready to take on 1Password. Is 1Password ready? Yes! We have been ready for a long time, but you need to do your part by having a good Master Password.

We’ve written many times about how 1Password defends against automated password guessing programs (password crackers). And we’ve been strengthening those defenses as well. If you’ve been wondering why we’ve been devoting so much effort to this, well this is the article for you.

We’ve always known that that there is nothing we can do prevent someone developing an automated Master Password guessing tool that is tuned to 1Password data, and so we’ve designed our security around the assumption that such tools do exist. What we can do (and have done) is make any password guessing program work extra hard, so that it can only guess thousands of passwords per second instead of many millions per second. We also have been advising people to make sure that their 1Password Master Passwords are strong, unique, and memorable.

What’s new

Password crackers don’t break the cryptography or exploit bugs or design weaknesses. They are just programs that try millions or billions of different passwords until they either find one that works or the person running the program gives up.

John the RipperThe news is that the most popular and sophisticated open source password cracking tools available, John the Ripper, is now being adapted toward cracking password managers Master Passwords. More recently (July 25) we see the development of tools specifically designed for making John the Ripper work with 1Password’s Agile Keychain Format.

John the Ripper expects the data that it works with to be in particular formats. The modifications to John the Ripper for 1Password involve two components. One converts the relevant part of the Agile Keychain Format into an appropriate input file, and the second part allows John the Ripper to test against that input file in a way that allows it to recognize a successful guess.

Let me stress again that the existence of a password cracking tool does not reflect any kind of weakness in the system it is attacking. When you have encrypted data, there is nothing stopping a person or a computer from trying to guess the password.

What’s not new

Other than repeating the fact that 1Password users should have a unique, strong, and memorable Master Password, there is nothing that we need to do with 1Password in response to the new components of John the Ripper. We have been operating under the assumption that these sorts of tools already existed, even if they hadn’t been made publicly available.

PBKDF2 diagramWhen we introduced the 1Password data format in 2008, we knew that we needed to design it to defend against crackers, so we used PBKDF2 in the process of getting from Master Password to encryption key. PBKDF2 means that a computer has to do many complicated and slow computations to derive an encryption key from a password. So you might have to wait half a second or so after entering your master password for 1Password to actually be able to unlock your data, but that is barely noticeable to someone using the system. But for an automated password cracking system, it dramatically reduces the number of possible passwords it can guess in a day. We’ve written more about how PBKDF2 works in Peanut Butter Keeps Dogs Friendly, too. Plus, last year we increased the number of PBKDF2 iterations that many versions of 1Password use when creating a new data file.

We have also been encouraging people to use good Master Passwords for their 1Password data. 1Password means that your various login passwords don’t need to be anything that you need to remember (and so it is easy for those to be strong and unique), but your 1Password Master Password is something that needs to be strong, unique, easy to remember, and reasonable to type. There is a great deal of advice on the ‘net about how to pick a good password that you can remember, but much of that advice fails to take into account the flexibility of password cracking tools. So please take a look at Toward Better Master Passwords if you haven’t already looked at that.

How fast in John the Ripper and what does it mean for your master password?

I’ve spent much of the weekend playing with the new tools in the developer versions of John the Ripper.CPU cores are completely pegged I ran John the Ripper (JtR) against my 1Password data for about 20 minutes on my Early 2009 Mac Pro (Quad Core). John the Ripper cranked away and consumed more CPU power than I knew my machine had (see picture at right). Yet working against a 1Password data file that used 1000 PBKDF2 iterations, JtR was only able to try about 4200 password guesses per second. For my calculations in the table below, I rounded that up to 5000 guesses per second.

I also tested a data file with 28,000 PBKDF2 iterations. As expected John the Ripper was slowed down about 28 times from the case with 1000 PBKDF2 iterations.  In the table I provide estimated cracking times if the data file uses 25000 PBKDF2 iterations, which should make JtR run about 25 times slower than when there are 1000 iterations. (Again, my timing data was a bit messier, but I am always rounding toward the worst case. That is, whenever there is some ambiguity or a range of results, I am always picking the estimates that would have John the Ripper be faster.)

The author of the 1Password plug-in, Dhiru Kholia, anticipates that the module will soon be modified so that it can make use of Graphic Processor Units (GPUs). This, he estimates, will increase the guessing speed by more than 100 times. In my table below, I have used a 200 times increase in speed for GPUs. So that where I had roughly 5000 guesses per second on my Mac Pro, I assume that with GPU acceleration, there will be one million guesses per second.

Mac Pro (Early 2009)And finally to read the table below, you need to be reminded of how I am measuring password strength. I can only calculate the strength of a password if I know the system by which the password was created. A great deal of advice floating around about creating passwords fails to take into account that the attackers know more about how people create passwords than the people creating the passwords, and these attackers can and do tune their cracking tools accordingly. Much of the common advice also fails to take into account that people are far more predictable than we imagine. So passwords that may look really strong are often far weaker than people imagine.

If you read the advice in Toward Better Master Passwords, you will see that the recommended system is to pick words from a list truly at random (by rolling dice) and then just using that sequence of randomly chosen words as your Master Passwords. This sort of system, until it became the subject of an xkcd comic, was known as diceware.

The table below looks at Master Passwords 3, 4, 5, 6, and 7 diceware words long. The entropy of those passwords are listed in bits. For an explanation of what “bits of entropy” means, take a look at The Geek Edition of the article on better master passwords.

The cracking times are the average or mean time to crack. For example if it would take 116 years to try every possible 4 word password created with the diceware scheme, then it would take on average 58 years.

JtR crack times for agilekeychain

Lessons

From the table you should surmise that three-word-long passwords of this sort aren’t long enough to withstand a plausible attack. You should also be able to see that anything over five words long is overkill. Or, given a Master Password with more than about 55 bits of real entropy (not the false reports that you get from most websites pretend to calculate password strength), you should be fine against any plausible attack for a long time to come.

PBKDF2 and its limits

It really is because of PBKDF2 that tools like John the Ripper will only be able to find weak Master Passwords. Its role is vital. But it is important to notice that once we have a sufficient number of PBKDF2 iterations, increasing those doesn’t add that much additional security. Going from 1000 iterations to 25000 iterations is the equivalent of adding less than 5 bits of entropy to a password, which is about the same as adding a truly random, lowercase letter to a password. Furthermore, there are continuing diminishing returns: Going from, say, 25,000 PBKDF2 iterations to 50,000 would only add the equivalent of one bit of entropy to a password.

In short, once PBKDF2 is in place with a reasonable number of iterations, you get far far more security for the effort by making your Master Password stronger.

Why doesn’t 1Password limit the number of password attempts?

Many websites or an ATM will lock someone out if they enter their password incorrectly too many times. Websites will also have a kind of back-off. After you’ve entered your password incorrectly three times in a row, it may make you wait ten minutes before it lets you try again. These are very good security measures for those sorts of services. So the question is: why don’t we do the same with unlocking 1Password?

1Password stores your encrypted data on your computer. You may use Dropbox for syncing, but when 1Password does its thing, it is always unlocking data that is on your computer. This means that if an attacker gets hold of your 1Password data (say your computer is stolen), they have the data right there. They do not need to use the 1Password software, they can go directly to the data with their own tools. Because an attacker doesn’t have to go through our software or systems we control, there is no place for using using throttling or back-off techniques. We have to build the security into the data format itself. Our use of PBKDF2 is an example of that.

More abstractly and to introduce a bit of technical jargon, your Master Password is an encryption password, not an authentication password. It is used as (or to derive) a key that decrypts something. It is not used as a mechanism to prove who you are so that you could be let into some service. The distinction is subtle, and particularly prone to confusion because, for the most part, a user shouldn’t have to know or care about it. But there are a couple of places where the distinction matters. It is part of the explanation for why 1Password doesn’t do back-off or throttling.

There is one other place that the distinction between encryption password and authentication password matters for users of 1Password. I will be writing about it more later, but in summary: it means that once you have a good 1Password Master Password, you should keep it for life. You gain no security by changing an encryption password frequently (indeed, it can hurt). So you should only change your 1Password Master Password if there is something wrong with your current one. I’ll talk more about changing passwords (when you should and when you shouldn’t) in a future article.

Should we keep our data format secret?

It’s natural to ask whether we could have made things harder for the developers of password cracking tools if we weren’t as open as we are about the design of our data format. We certainly could have made things a bit more annoying for them if we attempted to conceal details of our data format, but we couldn’t have made things harder for them in a way that would have mattered for security.

On the whole, people should be distrustful of systems that claim to gain security by having secrets known only to the developer. That approach is often called security through obscurity. It not only rarely works, but it often implies a weakness in the design. For example, if there were something that I knew about the design of 1Password that would enable me to unlock your data, then it would necessarily be the case that there is a weakness in the system. Such secrets can often be discovered by careful analysis or through the secret actually getting out from those who know it. Despite what I may have said on April Fool’s Day, proprietary encryption systems are a warning sign, not a virtue.

Join the discussion

I have set up a specific discussion thread on our forums for further discussion. Please join us there.