Enigma machine

Bcrypt is great, but is password cracking “infeasible”?

There are a lot of technical terms that mean something very specific to cryptographers but often mean something else to everyone else, including security professionals. Years ago I wrote about what it means to say that a cipher is “broken”. Today’s word is “infeasible”.

The news that sparked this lesson is the use of “computationally infeasible” in an announcement by Slack. Slack has announced that their hashed password database had been compromised, and their message was excellent: They clearly described what was available to attackers (usernames, email address, hashed passwords, and possibly phone numbers and contact information users may have added); they offered clear and useful instructions on what users should do (change passwords, enable two-step verification), and described what they have done and what they will be doing. And – most relevant for the technical discussion here – they have told us how the passwords were hashed.

In this case they said:

Slack’s hashing function is bcrypt with a randomly generated salt per-password which makes it computationally infeasible that your password could be recreated from the hashed form.

It is terrific that they chose to use bcyrpt for password hashing. bcrypt is among the three password hashing schemes that we recommend for sites and services that must store hashed passwords. The other two are PBKDF2 and scrypt. But Slack’s use of the term “computationally infeasible” here illustrates that one must be very careful when using cryptographic technical terms.

If you have a weak or reused password for Slack, change it immediately. Here is a guide to using 1Password for changing a password. And because the Slack app on iOS makes use of the 1Password App Extension, it is easy to use a strong and unique password for Slack.

Slack 1Password login Slack 1Password extension

If you would like to see how to use Slack’s two-step verification with 1Password take a look at our handy guide on doing just that.


But now back to what is feasible with password hashing.

One way hashing

When services that you log into store your password they should never store those as unencrypted “plaintext”. If they are stored as plaintext it means that anyone who can get their hands on that data file can learn everyone’s passwords. For example, Molly (one of my dogs) uses the same password on Poop Deck as she does on Barkbook. So if Patty (my other dog) learns Molly’s Poop Deck password, she can use it to break into Molly’s Barkbook account as well. This is why it is important not to reuse passwords.

Now suppose that Molly uses the password “rabbit” on Barkbook. (Have I mentioned that Molly is not the smartest dog in the pack?) Barkbook shouldn’t store just “rabbit”, but instead should store a one way hash of rabbit. A cryptographic hash function will transform something like “rabbit” into something like “bQ67vc4yR024FB0j0sAb2WKNbl8=” (base64 encoded).

One of the features of a cryptographic hash function is that it should be quick and easy to compute the hash from the original, but that it should be infeasible to perform the computation in the other direction. That is it should be pretty much impossible to go from “bQ67vc4yR024FB0j0sAb2WKNbl8=” back to “rabbit”. And it is.

Guessing versus reversing

With any halfway decent cryptographic hash function is it infeasible to compute the original from its hash if the original is chosen at random! But if you can make some reasonable guesses about the original then you can use the hash to check your guesses. Because passwords created by humans are not chosen at random, then it does become computationally feasible (and often quite practical) to discover the original based on the hash.

The actual formal definition of “one-way” for a cryptographic hash function, H(x), includes the requirement that x be the output of a uniformly distributed sampling of the domain of H. That is, considering all of the things that you can hash (under some set length), you need to pick something at random.  Otherwise a hash function might be invertible. Human created passwords do not meet that requirement and so the “computational infeasibility” of inverting a one way function isn’t applicable when its input is not chosen at random.

So now let’s correct Slack’s statement:

Slack’s hashing function is bcrypt with a randomly generated salt per-password which makes it computationally infeasible that a randomly created password could be recreated from the hashed form.

Modified Slack statement.

This, of course, is why you should use 1Password’s Strong Password Generator for creating your passwords. When your password is chosen randomly with a large set of possibilities, then it really is computationally infeasible to discover the password from the cryptographic hash.

Slowing down guessing

I mentioned that (for now) bcrypt, scrypt, and PBKDF2 are good choices for password hashing. Once the final results are in from the Password Hashing Competition and the dust has settled, we will probably have a good successor to those three. These are built upon cryptographic hash functions, but are designed for hashing specifically for when their input is not selected randomly.

Because cryptographic hashing is something that we have computers do a lot of, one of the things that we want is that it be fast. We want to be able to perform lots and lots of SHA-256 hashes per second without straining a computer’s memory. But if an attacker is going to be guessing passwords to see if they produce the right hash, we want to slow down the hashing. PBKDF2, scrypt, and bcrypt are all designed to require much more computation than a regular hash function to compute a hash. This can slow down an attacker from performing millions of computations per second to just thousands. The actual speed depends on many things, including the hardware that the attacker brings to bear on the system. scrypt, additionally, places specific demands on memory.

So the use of bcrypt means that attackers will need to do more work than they otherwise would to guess passwords stolen from Slack. That is a good thing, but it is not an “infeasible” amount of work.

What’s infeasible?

I started out by saying that I was going to talk about the word “infeasible”, but so far I have just been using it a lot. This is because its definition is abstract, subtle, and hard. I am not going to give a full definition, but I am going to try to get reasonably close. The discussion that follows is inherently technical, and nobody will blame you if instead of reading further you just wish to watch us pour ice water over ourselves. (Remember, that was a thing just last year.)

Welcome back to this article. It get’s progressively more arcane from this point onward.

The notion of infeasible depends on the relationship between the amount of work the defender has to do to secure the system compared to the amount of work that the attacker has to do to break it. A bank vault may take a minute to unlock if you know the combination, but it may take days to break through if you don’t. With cryptographic systems it can take just a fraction of a second to decrypt data if you have a key, but many times the age of the universe to do so if you don’t have the key.

Security parameters

What we want is the amount of work the attacker has to do to be vastly disproportionate to the work that the defender must do. It turns out that this can be stated mathematically, but first we need to introduce the notion of “security parameter” if we want our definition to stand the test of time instead of depending on the speed and power of current computers. So we will talk about how much work the defender and the attacker have to do in proportion to some security parameter.

Let’s pick, for purposes of exposition, an encryption system that operates at a security parameter of 56. The amount of computation that the the defender has to do to decrypt some data with the key is proportional to 56, but the amount of work that the attacker has to do to decrypt the data without the key is proportional to 2⁵⁶. Fifty-six is much much smaller than 2 raised to the 56th power, but today even 2⁵⁶ operations is within the reach of many attackers. Thirty years ago it was within the reach of just a few.

So now let’s suppose that we want to double this security parameter to 112. How much of a work increase might this cause the defender? You might be thinking that it doubles the cost to the defender, but the system I’m thinking of actually tripled the cost to the defender. Tripling the cost for double the security parameter may not seem like a good deal, but doubling the security parameter increased the work of the attacker by another 2⁵⁶, for a total of 2¹¹². This puts it well outside the reach of even the most resourceful attacker for a long time to come.

When we doubled the security parameter in that example, the work to the defender increased linearly while the work to the attacker increased exponentially. We want the work required of the attacker to increase exponentially with the security parameter while for the defender we increase it linearly or polynomially.

Doing time, time, time in an exponential rhyme

If the security parameter is n, we will tolerate it if the amount of work the defender must do is proportional to na for any a > 1. That’s what we mean when we say the work is “polynomial in n“. So if the work goes up with the square or cube of n we might grumble and seek more practical systems, but no matter how big the power that n is raised to gets, this is still a polynomial expression. An algorithm that works this way is called a “polynomial time algorithm”.

For the attacker we want the number of computations needed to be proptional to an expression in which n is in the exponent. So if the work to the attacker is proportional to b for any b > 1, so that the work is exponential in n. (Those of you who know this stuff, know that I’m leaving some things out and am taking some shortcuts.)

It might seem that a “big” polynomial get us bigger numbers than a “small” exponential, but no matter how much a polynomial function starts out ahead of an exponential, the exponential will always catch up. Let’s compare the exponential  y=1.1ˣ with the polynomial y=x⁶ + 2. For values of x below a few hundred, it looks like the polynomial is the runaway winner.Plot of polynomial taking early lead over exponentialBut we inevitably reach a point where the exponential function catches up. For the particularly examples I’ve given, the exponential catches up with the polynomial when x is about 372.73.

Plot with exponential catching up

Finally, if we go just a bit beyond the point where the exponential overtakes the polynomial, we see that the exponential completely flattens the polynomial.

Plot on scale where exponential flattens polynomial

Some computations will take a number of steps that are polynomial in n (“polynomial time algorithms”), and others will be exponential (“exponential time algorithms”). We say that a task is infeasible if there is no polynomial time algorithm to complete it with a non-negligible chance of success. I have not defined what a non-negligible chance of success is, but as the article appears to be growing in length exponentially, I will leave that discussion for our forums.

When we have this sort of asymmetry, where the work done by the attacker grows exponentially with the security parameter, but grows at most polynomially for the defender, there will always be some security factor beyond which the work to be done by the attacker is so enormously larger than what the defender must do as to just not be an option for any attacker.

Quibbling over terminology

Now that we have a workable definition of “infeasible” and a better understanding of what cryptographic hash functions do, we can take a closer look at Slack’s statement. First let me repeat that their overall statement was excellent, and I fully sympathize with the difficulty involved in writing something about security that is correct, clear, and usable. I’ve taken some shortcuts in my exposition on any number of occasions, and I’ve made my share of errors as well. My point here is not to criticize but instead to use this as an opportunity to explain.

Given what we believe about cryptographic hash functions it is infeasible to discover x if you are only given the hash of x but only if x is chosen at random. Furthermore this is true of any (decent) cryptographic hash function and is not limited to the slow functions that are recommended for password hashing. That is, we don’t need bcrypt or PBKDF2 for that property to hold.

The limits of slow hashes

Slow hashes – specifically designed for password hashing – are built because we know that passwords are not chosen at random and so are subject to guessing attacks. But slow hashes have their limits, and with the notions that have been introduced above, we can now talk about them more clearly. Using a slow hash like PBKDF2 slows things down for both the attacker and for the defender. And the amount of slow-down is roughly the same for both the attacker and for the defender.

If we increase the security parameter (number of iterations) for PBKDF2 the computational cost rises linearly for both the attacker and for the defender. This is unlike the security parameters we use elsewhere in cryptography, where we would like a small (linear or perhaps polynomial) increase in cost to the defender to create a large (exponential) increase for the attacker.

Let’s see how that works out with a concrete, if hypothetical, example. Suppose it is using 40,000 PBKDF2 iterations. Now suppose that you add a really randomly chosen digit to the end of your Master Password. Adding a single random digit will make an attacker do 10 times the amount of work that they would have to do to crack the original password. Adding two digits would make the attacker have to do 100 times the work of the original. Making a password just a little bit longer (with random stuff) makes the work required by the attacker increase exponentially. That is the kind of proportion of work that we like.

Now suppose 1Password uses 40,000 PBKDF2 iterations in deriving your Master Password. To get the same additional work as adding a single digit to your password, you would need to increase the number of PBKDF2 iterations to 400,000. And to get the equivalent of adding two digits, you would need to increase the number of iterations to 4,000,000. Once we have a goodly amount of PBKDF2 iterations, there isn’t that much gained by increasing it by an additional ten or twenty thousand. But there is much to be gained by even a small improvement in a Master Password.

PBKDF2 is terrific, and it is an important part of the defense that 1Password offers if an attacker gets a hold of your encrypted data. But you must still pick a good Master Password because the security parameter is linear for both the defender and the attacker. Unless there is a breakthrough in the slow hashing competition, a strong Master Password will always be required in order to ensure your security can withstand the test of time.

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.


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.

Your Master Password is your defense from Dropbox breaches, real and imagined

1Password in DropboxRumors of a Dropbox data breach spread this weekend, a breach that ultimately turned out to be false. But even in instances of false alarms, it is useful to remind 1Password users that their 1Password data cannot be decrypted without the Master Password. So let me take this opportunity to remind everyone that your 1Password data cannot be decrypted without your Master Password. If someone steals your 1Password data – whether from the theft of your own computer or through the breach of a sync service – they cannot decrypt it.

Fact checking

It is worth noting that when a perpetrator of a rumor like this self-identifies as “Operation Troll Security”, it might be worthwhile to double check their claims before jumping to conclusions or even reporting the claims further. This is particularly true if a perpetrator has a history of claiming responsibility for every notable site outage, then laughing at people who believed them. Operation Troll Security doesn’t often tell the truth, but it may be wise to heed one particular tweet:

Despite the fact that the claims of a Dropbox breach were a complete hoax, it still is worthwhile to point out some things about the security of your 1Password data if it ever does fall into the wrong hands.

End-to-end encryption

1Password uses what is called “end-to-end” encryption. 1Password on your computer or mobile device encrypts your data with keys that are derived from your Master Password. Those keys are never stored anywhere or transmitted. Nobody, not even us at AgileBits, ever sees those keys or your Master Password. This is why it absolutely essential that you don’t forget your Master Password. We cannot reset it or reconstruct it. Your data can only be decrypted by you.

We designed 1Password this way from the outset because we knew that computers get stolen and services get compromised. By placing all encryption and decryption under your control, we become far less reliant on the security of any sync service.

Protecting Master Passwords

If an attacker does get hold of your 1Password data, the only feasible way for them to attempt Password Based Key Derivation Function diagramto decrypt it would be to try to guess your Master Password. Of course, they wouldn’t sit there typing in guesses. Instead they would run automated password guessing systems against the data.

We have a long history of building mechanisms into 1Password’s data format that make it harder for attackers to guess your Master Password. When we released 1Password 2.5 in 2007 with the then new Agile Keychain data format, we added PBKDF2 so that anyone trying to run automated password guessing systems against captured 1Password data would have to perform lots of slow computation for each guess. You can read more about PBKDF2 and this aspect of our design in an older article of mine, Defending against crackers: Peanut Butter Keeps Dogs Friendly, Too. Many of the details have changed over the intervening years, but the essential concept remains the same.

Toward better Master Passwords

DicePBKDF2 makes it harder for those automating password guessing, but it does have limits. You need to do your part by choosing a good Master Password. Even a small improvement to a Master Password goes a long way. Adding a single truly randomly chosen digit to the end of your Master Password makes the attacker work ten times longer to guess it. Adding a truly randomly chosen word make the attacker work thousands of times longer. Adding two truly randomly chosen words makes the attacker work tens of millions of times longer.

You will note that I emphasized the phrase “truly randomly” a few times there. That part is crucial. People turn out to be very unrandom even (especially?) when they are trying to be random. If you follow our advice in Toward Better Master Passwords, you will see how you can securely pick words at random to add to a Master Password. Hint: It involves rolling dice. It’s fun!

A hoax is a hoax, of course of course

Even though the report of a Dropbox breach was a hoax, you still may ask what role Dropbox security plays in the security of  your 1Password data. I hope that this article helps explain that and how using 1Password can keep your secrets safe. I look forward to further discussion in our forums.

On hashcat and strong Master Passwords as your best protection

HashcatYou may have heard some news going around about hashcat, a password cracking tool, that recently increased its ability to guess Master Passwords for 1Password data files. It’s an impressive achievement for hashcat, and it is important to understand what this does and doesn’t mean for 1Password.

What you need to know

1Password has not been “cracked”

The existence of a new cracking tool (actually there is another new tool, but only the hashcat one is getting much attention due to its speed) does not mean that anything is broken in 1Password. Indeed, the fact that we are open about our design is one of our strengths. Hashcat’s remarkable guessing speeds is the real news here.

Your Master Password is your protection

This development only highlights what we’ve said all along: your Master Password is your defense. You need to pick a strong Master Password, and these are some great posts on how to do that. Our measures to slow down automated guessing helps a great deal, but they are no substitute for a great Master Password.

Is there a flaw? Well, yeah. It’s complicated

The announcement said that some of hashcat’s speed achievements is due to a flaw in the design of the Agile Keychain Format. Indeed, there is a very subtle flaw. Exactly how much the flaw contributes to their cracking speed is something I’ll talk about below. In short, it contributes—literally—one bit.  But more on that later.

There are a couple of technical misunderstandings about the flaw that I’d like mention here in our “cliff notes introduction”, but with the details and explanation to come further below.

  1. We didn’t call PBKDF2 twice during key derivation (that would be silly). However, we called PDBDF2 once in a way that had the effect of calling it twice. That is still a flaw because it has the identical result of doing something silly, but it was a non-silly flaw.
  2. Hashcat was able to reduce the number of hash calls four fold. But our flaw was only half of that. The other half is not specific to 1Password.

Terrific community

Understanding the precise nature of the “flaw” and related issues was a communal effort involving hashcat developers, John the Ripper developers, cryptographers, and members of the information security community. The debate, discussion, questioning, and explaining within this community is fantastic.  Some  the debate continues and not everyone involved will agree with every point of the more detailed assessment below.

More background

Ready for the next level of detail? Here goes.

Password crackers and how to defend against them

John the RipperPassword crackers, such as John the Ripper and hashcat, are tools that automate password guessing. Over the past year, they have turned their attention to password managers, including 1Password. This doesn’t reflect a weakness in password managers in any way. Indeed, I think the fact that we were among the first to draw this sort of attention is to our credit. The question isn’t whether someone has tools to automate password guessing—we should always assume that they do—but how many guesses can be checked in a short period of time. The faster they can guess, the stronger people’s passwords need to be.

Naturally, we have put in measures to make password guessing slow. We use PBKDF2, which requires that there be lots of computations to go from an entered Master Password to actually unlocking your 1Password data. Then the question is about how good a job our use of PBKDF2 does against these highly optimized tools. The short answer is that PBKDF2 helps enormously, but it is no substitute for a strong Master Password. When we get to the technical discussion (if you stick with me that far), you will learn a great deal more about PBKDF2.

What does this mean for my Master Password?

For a couple thousand dollars today, an attacker can build a machine that will guess millions of 1Password Master Passwords per second. So let’s look at how long it would take for that to crack various types of Master Passwords, assuming the scenario of an attacker getting a copy of your Agile Keychain and setting this machine to work on nothing other than guessing your Master Password.

Password strength comparison

hashcat-crack-timesFor the numbers I give, I’m going to pretend that you all created Master Passwords using the scheme in Toward Better Master Passwords, called “diceware.” It’s not because I actually assume that everyone is using that system, but we need to know how strong a password is (measured in bits of entropy) to perform calculations about how long it might take to guess them. It is remarkably hard to know how strong a password is just by counting letters, digits, and symbols. Instead you need to understand the system that was used to create the password.

If you have a three word diceware password with 1Password using 10000 PBKDF2 iterations, the hashcat machine (more on that in a bit) would have a 50% chance of running through all three word-long diceware passwords in about nine days. If you use a four word password then it would take almost 200 years. At five words, it would take 1.5 million years. With six words and above we are talking about billions of years.

What about increasing PBKDF2 iterations?

Password Based Key Derivation Function diagramThe very first versions of the Agile Keychain Format long ago used 1000 PBKDF2 iterations. More recently, when a new keychain is created or the Master Password changed (in version 3.9 for Mac), we changed that to a minimum of 10000 iterations (and possibly more depending on your system). It is tempting to think that we should just increase these numbers dramatically. We will certainly be looking at increasing that minimum, but it is very important to understand that increasing the number of PBKDF2 iterations stops paying off after a while. We reach a point where there is far greater security improvement for the effort making a Master Password stronger than there is for increasing the number of PBKDF2 iterations.

I’m going to talk about the security of Master Passwords in terms of bits of entropy. You don’t need understand the details other than to know that each additional bit doubles the cracking time. So if you have a Master Password that has 40 bits of entropy (basically that there are 2⁴⁰ different alternatives passwords you could have created using the same password creation system) it might take, say, 100 years to crack under certain conditions. If it were one bit more (41 bits) then it would take 200 years to crack under the same circumstance.

We can also double the amount of time to crack by doubling the number of PBKDF2 iterations. Going from 10000 iterations to 20000 doubles the crack time, and so it adds the equivalent of 1 bit to the the effective strength. Going from 1000 PKDF2 iterations to 10000 PBKDF2 iterations (increasing the iterations 10 times) effectively adds about 3.3 bits of entropy. The attacker needs to work 10 times harder. If you go from 10000 iterations to 20000 iterations, you only gain one additional bit. The attacker only needs to work twice as hard. Going from 20000 iterations to 30000 iterations gives about 0.6 bits of additional strength.

Now contrast adding a single randomly chosen lowercase letter to your password. Each one will add 4.7 bits of entropy. That would be like going from 10000 PBKDF2 iterations to 260000 iterations. Adding another randomly chosen lowercase letter would add additional 4.7 bits, but trying to do the same by increasing PBKDF2 iterations would now take us to 6.7 million iterations. Adding a diceware word to your master password will add 13 bits.

To get the same effect as adding a diceware word by adding PBKDF2 iterations would mean going from 10000 PBKDF2 iterations to 78 million iterations. With that, it would probably take more than an hour or two to unlock your 1Password data on an iPhone if the effort didn’t entirely drain the battery first. The simple lesson is that once we have a few tens of thousands of PBKDF2 iterations, increasing them doesn’t add much security, while it does add to real costs to the legitimate user of the data. The more effective route is to spend a second or two typing a longer password instead of having PBKDF2 spend a few seconds exhausting your battery.

Beyond diceware

DiceThe Master Password generation scheme that I recommend in Toward Better Master Passwords involves picking words from a list of 7776 words by rolling dice. We can make these passwords stronger by using a longer list of words. The reason that 7776 is that it works by rolling five dice (or one die five times). We can use a longer word list if we don’t need to roll dice. But it is absolutely essential for the security of the scheme that the process of picking words is really random and not under direct human control.

Another option is to do as I suggested in that article. Create a relatively short password the usual (not very good way), but make sure it isn’t something on the diceware list. Then create a diceware password and simply add the two together.

A third, more complicated option, is something that is a bit of a “work in progress”, but this hashcat news means we can talk about it a little early. The idea is to use lists of words from different languages as well as longer lists of words. Randomly pick which language to use for your first word, then use diceware on that. You may have to learn a few foreign words in the process, but once you’ve learned those words they should be about as easy to remember as the words of your native language.

I have prepared lists of words exactly for this scheme along with a README file that contains not fully fleshed out instructions on how to use the system. This is very experimental, but it has allowed me to have a a strong Master Password for 1Password on iOS which isn’t too annoying to type on an iPhone keyboard or to remember.

The really technical details

I was definitely impressed to learn that they are getting three million trials per second against 1Password data that used 1000 iterations for PBKDF2. It is important to understand how. There were four things that gave them a speed up, and I’ll work from the least (smallest speed up) to the most significant. I should note that some people I have enormous respect for do not fully agree with my assessment. If you’d like to dive into this, please follow the discussion on the hashcat forums.

But first, another word about PBKDF2

Three of the four mechanisms I discuss involve the inner workings of PBKDF2. So we need to peek a bit more into that black box.  PBKDF2 takes something like a password and transforms that password over and over again and eventually spits out a big number (a string of bits). When you call PBKDF2, you not only tell it how many iterations it should run through, but you also tell it what function should be used to transform the data in each round. The function has to be what is called a “pseudo-random function”, but other than that PBKDF2 doesn’t insist on much. We say that PBKDF2 “is constructed” from a PRF.

The PRF that is typically used with PBKDF2 is HMAC. I’ve written about HMAC before. Now HMAC is constructed from a hash function, and a number of different hash functions will work. Different hash functions give different size output. SHA1 gives 20 bytes of output. SHA256 gives 32 bytes, and SHA512 gives 64 bytes of output.  If you call SHA1 but only need 16 bytes of output you just take the first 16 bytes of of the 20 byte output and throw away the rest. This is called “truncating”.

The hash functions we use are constructed from “compression functions”. Compression functions are designed to be fast, but they are still where the real computation takes place. So the idea of PBKDF2 is to require that the underlying compression function is computed many times.

All of these concepts and constructions will play a role in the discussion of points 2, 3, and 4 below. But first, to the one that has nothing to do with PBKDF2.

1. Only one AES block needs be decrypted per guess

When data is encrypted using a block cipher (such as AES) in CBC mode with standard padding, the attacker doesn’t need to decrypt each block of ciphertext to see if things “work”. The attacker only needs to decrypt the final block. This is not anything particularly new, but it is an important optimization. This way, the attacker needs only one AES decryption per guess.

An aside to any application developers: It is perfectly fine for an attacker to use this shortcut, but applications should never, ever, ever, use this trick as a way to report decryption success or failure. Really. Don’t do it.

Again, I believe (but haven’t confirmed) that other crackers running against CBC mode use the same optimization. It’s an optimization, but a typical one and doesn’t represent a flaw. We want the slowdown to take place in PBKDF2.

2. PBKDF2-HMAC optimization

There is a neat trick that can be used to speed up PBKDF2-HMAC calculations by a factor of two. I first saw this trick in John the Ripper, and it is used here in hashcat as well. Now this optimization, however, is available to defenders as well as to attackers. So if our use of PBKDF2 uses the same trick as is used in hashcat and John the Ripper then this comes out as a tie between Attacker (them) and Defender (us).

HMAC diagramPBKDF2 calls HMAC for each iteration. Each run of HMAC normally involves two hashing operations. Each of those two hashing operations involve two compressions. So we have four compressions altogether for each call to HMAC. However, two of those compressions are going to be exactly the same (with the same data) for each PBKDF2 iteration. If we compute those two compressions only once and save those results, then we can cut down the computation needed for each PBKDF2 round in half.

This optimization of PBKDF2-HMAC-SHAn is available to both the attacker and to the defender. So this only really counts as a “speed up” for the attacker if the defender isn’t using it and isn’t taking it into account when calibrating the number of PBKDF2 iterations. So does 1Password use this optimization? It depends on the particular software libraries we use. I believe (but haven’t received confirmation from Apple on this yet) that the PBKDF2 implementation in CommonCrypto does do this. I don’t believe that the cryptographic library we use for 1Password for Windows does, which might help explain why unlocking 1Password on Windows takes a bit longer than it does on the Mac. Indeed, we’ve been looking at using our own custom PBKDF2 implementation on Windows specifically to get this optimization.

3. Don’t ask more of PBKDF2 than it is ready to give

This is where the design flaw in the Agile Keychain key derivation mechanism. We ask PBKDF2 to give us 32 bytes of data, but we also tell it to use HMAC-SHA1. This, combined with the fact that we used one half of its output for one thing and the other half for another, is our misdesign.

SHA1 only produces 20 bytes of data and so if we ask PBKDF2-HMAC-SHA1 for 32 bytes of data it can’t run its natural course. Instead what it does (with some rounding and truncating) is run PBKDF1 (which gives at most 20 bytes of output) twice. Once to produce the first 16 bytes that we asked for and once to produce the second 16 bytes of output. If we asked it 10000 iterations, it will actually run through 20000 iterations, 10000 to produce the first part of the output and 10000 to produce the second part of the output.  This is a fact about PBKDF2 that we were not aware of at the time.

Normally this behavior of PBKDF2 wouldn’t be a problem, as both the attacker and the defender would suffer from an equal slowdown of twice as many calls to the underlying hash function. But, in the words of Mr Monk, here’s the thing. We used the first 16 bytes that output as a derived AES key and the second 16 bytes as an initialization vector. The password guesser only needs the AES key to see if a password works. To actually decrypt the data, the IV is needed as well, but it is possible for the candidate password to be verified with only the AES key.

Splitting the output of PBKDF2 is a perfectly fine thing to do. Asking for more data from PBKDF2 that you’d natively get from the hash you give it should also be fine. After all, that is something that PBKDF2 was designed to handle. But doing both of those turns out to allow an attacker to do just half of the work that you need to do when you run PBKDF2.

Without this flaw, the guess rate would still be 3 million guesses per second for 1000 PBKDF2 iterations. It just means that our own use of PBKDF2 would “cost” half as much and so that we could double the number of iterations.

4. Really, really well designed GPU processing

Radeon hd 6990Hashcat does many things well, but I think that what they really excel at is GPU processing and parallelization. Their ability to spread out all of the work among four GPUs and have each one perform SHA1 computations very quickly is, I believe, where the real speed is.

The compression functions (invoked by the hash functions, invoked by HMAC, invoked by PBKDF2) happen to run really nicely on GPUs, and all of the constructions build on top of them also have nothing in them that presents difficulties for highly optimized code on GPUs. So roughly speaking, PBKDF2 provides no meaningful defense against parallel computation, and its typical components can be implemented very very nicely on GPUs.

Beyond PBKDF2

As we look at the above list, we see that three of them involve design features of PBKDF2. PBKDF2 is not serving its purpose as well as we would want. Now I love PBKDF2. It may not be engraved on my heart, but it is engraved on my iPad.iPad-Engraving But it has been growing clearer that the world needs a successor to PBKDF2. A possible successor, scrypt, does consume memory as well a CPU (or GPU). But PBKDF2, scrypt, and the search for a successor will have to be the topic of a separate article. Indeed, it is the subject of the article that I would have been working on today had not the hashcat announcement come.

We continue to use PBKDF2 in our new data format, but with some important changes. First of all, we use SHA512 which makes it safe for us to ask for 64 bytes of data that we do split into halves. Also our use of SHA512 should make things more difficult for GPU-based crackers. Exactly how difficult remains to be seen.

Our next steps

Quite simply it is far too early to promise specific changes in response to this. Changing the key derivation system in the Agile Keychain isn’t something that can be done quickly, as we would need to make sure that 1Password on every single platform we support would be ready for the change before we started converting data files. I’m not ruling that out; but it would take a great deal of time, be fraught with compatibility issues, and would only save one bit worth of effective password strength.

We could boost the number of PBKDF2 iterations, but as described above, we’ve reached a point of diminishing returns for that. It will probably happen slowly and behind the scenes, as it has done in the past.

We can make certain that all our PBKDF2 implementations perform the HMAC-PBKDF2 optimization. We were already in the process of doing this when the hashcat news broke.

We can advise people on creating stronger Master Passwords, as that has and continues to be your best protection. Indeed, we will continue to do so as we also explore ways to make it easier for people to create and use such passwords.

[Update 1: At the moment, changing your Master Password will only recalibrate the number of PBKDF2 iterations when you use 1Password 3.9 on the Mac. We will have further information about 3.8 and 1Password on other platforms shortly.]

[Update 2:  PBKDF2 settings for different versions of 1Password.

Calibration requires something introduced in OS X 10.7 (Lion) and iOS 5. So calibration is only available in the Mac App Store version of 1Password for Mac (which requires OS X 10.7) and in 1Password 4 for iOS (which requires iOS 6). 1Password for Windows, 1Password for Mac 3.0-8, and 1Password 3 on iOS do not calibrate.

  • 1Password 3.9 Mac: All versions of 1Password for Mac from the Mac App Store (MAS) calibrate the number of PBKDF2 iteration on initial set up and on Master Password change. A minimum of 10000 iterations is used.
  • 1Password 4 iOS: All versions of 1Password 4 for iOS calibrate the number of PBKDF2 iteration on initial set up and on Master Password change. A minimum of 10000 iterations is used.
  • Mac 1Password 2.5.0 (October 2007) – 3.8.10:  Keychains were created using 1000 PBKDF2 iterations.
  • Mac 1Password 3.8.11 (December, 2011) – 3.8.20: Keychains were created using 10000 PBKDF2 iterations. Changing the Master Password did not change iterations.
  • Mac 1Password 3.8.21 (April 2013): Keychains are created using 10000 PBKDF2 iterations. On a Master Password change, iterations will be increased from 1000 to 10000 if necessary.
  • Windows 1Password (April 2010) – 1Password Keychains created with 1000 PBKDF2 iterations.
  • Windows 1Password (October 2012) – 1Password Keychains created with 10000 PBKDF2 iterations.  Master Password change does not increase number of iterations.
  • Windows 1Password (May 2013): Keychains are created using 10000 PBKDF2 iterations. On a Master Password change, iterations will be increased from 1000 to 10000 if necessary.

Please note that that making a small improvement to your Master Password has a far far greater effect than making a large increase in the number of PBKDF2 iterations.]

[Update 3: 1Password and  hashcat: The Movie.

I presented on this at PasswordsCon in Las Vegas on Juny 31, 2013. Per Thorsheim, one of the organizers of the conference, has uploaded videos of the talks.

But really, you would be better off watching the other talks from PasswordsCon. You already know what I have to say. The other talks were fantastic. You can also get the  PDF slides for that presentation.]

Hashing fast and slow: GPUs and 1Password

The net is atwitter with discussion of Jeremi Gosney’s specially crafted machine with 25 GPUs that can test hundreds of billions of passwords per second using hashcat, a password cracking system. Password crackers, like hashcat, look at the cryptographic hashes of user passwords and repeatedly make guesses to try to find a password that works. 1Password has been designed to resist automated password cracking attempts exactly because we anticipated developments like this.

Don’t get freaked out by the numbers

Windows XPFirst and foremost the reports of 348 billion passwords per second is specifically about passwords stored in the LM format used on Windows XP, exploiting the notorious design flaws and limitations LM hashes. (If you are still running Windows XP; and particularly if you are running NT, 2000 or 2003 domain controllers, please, please upgrade.) The hundreds of billions of  passwords per second reached against those hashes does not mean that passwords stored in other formats can be cracked that quickly.

By the way, this isn’t the only important news about password security to come out this year’s excellent Passwords12 conference. I couldn’t quite make it there this year, but I will talk about other developments from it in coming weeks. Today, all eyes are on GPUs guessing billions of passwords per second.

Slow and Fast Hashing

Typically when a password is “stored” on a system that you log into it is not the password itself, but instead it is a cryptographic hash of the password. I’ve written about some of the ways that password  can be hashed before. HashcatThese can roughly be divided into two categories: slow hashes and fast hashes. Slow hashes are specifically designed to slow down the kinds of attacks we are discussing.

Your 1Password Master Password is processed using the slow hashing system known as PBKDF2. 1Password’s use of PBKDF2 and your use of a good Master Password keep your data resistant from password crackers such as John the Ripper and hashcat if you chose a good Master Password.

Defending against future threats

There are several lessons from this. Gosney’s work does reflect real innovation and a breakthrough, but it isn’t an unexpected breakthrough. People who keep an eye on these things – and we do keep an eye on these things – expected something like this within the next couple of years.

We need to design systems that work against plausible future threats, not just against current threats. This is what we have always tried to do with 1Password.

Lessons and actions

  1. Your 1Password Master Password and your 1Password data remain safe, we designed the Agile Keychain format from the beginning to resist crackers like this. But it is also important for people to select strong, memorable, Master Passwords.
  2. It is more important than ever to have unique passwords for each site and service. As password cracking gets easier, the risks of using the same password on multiple sites increases. This is because if password hashes are stolen from one site, attackers have a better chance of discovering the password from the hash. Once they have that, they can try the same password on other sites.
  3. When using 1Password’s Strong Password Generator, try to create passwords that are at least 20 characters long.

Back to the Future

Gosney slow hash chartI’ve talked (well even boasted, I suppose) about how our earlier design decisions are protecting 1Password users today. But we have to look at what design decisions we make today will do for 1Password users half a decade from now.

Gosney’s machine can also be used against slow hashes, including PBKDF2 passwords. You can read more (and see cool pictures) of the design of Grosney’s hashcatting machine in the conference presentation slides (PDF).

Furthermore PBKDF2 was not designed to specifically impair parallel processing. But because GPUs have unusual and restricted ways of addressing memory, it is possible to design systems that make parallel processing using GPUs slower. This leaves a number of questions that we continue to look at.

  1. Do we need to change anything at all in anticipation of even more powerful machines tuned toward PBKDF2? (We don’t yet Password Based Key Derivation Function diagramhave estimates on how many passwords per second this system could try against a 1Password data file.)
  2. If we do need to change things, when do we need those changes need to be in place?
  3. Should we look at more parallel and GPU resistant alternatives to PBKDF2, such as scrypt?
  4. Should we look at tinkering with options within PBKDF2 to make it more resistant to GPUs working in parallel?

These are not new questions. We are always asking ourselves these and other questions in order to keep your 1Password data secure and protected, both now and in the future.

[Updated 2012-12-06 15:50 UTC. Updated to correctly explain that Gosney’s system is not limited to LM hashes. Thanks to Jeremi Grosney, Solar Designer, and others who pointed out my error. I have also taken the opportunity to add more clarifications and links to background throughout.]

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


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.

A salt-free diet is bad for your security

I am not giving anyone health advice. Instead, I’m going to use the example of the recent LinkedIn breach to talk about hashes and salt. Not the food, but the cryptology. Before you dive into this article, you should certainly review the practical advice that Kelly has posted first. Also Kelly’s article has more information about the specific incident.

I’m writing for people who saw security people talking about “salt” and want to know more.
You may have seen things like this, that appeared in an article at The Verge.

It’s worth noting that the passwords are stored as unsalted SHA-1 hashes. SHA-1 is a secure algorithm, but is not foolproof. LinkedIn could have made the passwords more secure by ‘salting’ the hashes.

If you would like to know what that means, read on.

What we know

We know that a data set of about 6 million password hashes has been released. We also know that this does include LinkedIn passwords (more on how we know that later). The data made public does not include the usernames (email addresses), but it is almost certain that the people who got this data from LinkedIn have that. By the end of this article, you will understand why people who broke in would release only the hashes.

Hashing passwords

Websites and most login systems hash passwords so that they only have to store the hash and not the password itself. I have been writing about the importance of hash functions for a forthcoming article, but here I will try to keep things simple. A hash function such as SHA-1 converts a password like Password123 to “b2e98ad6f6eb8508dd6a14cfa704bad7f05f6fb1”. A good hash function will make it unfeasible to calculate what the password was if you only know the hash, but the hash function has to make easy to go from the password to the hash.

A hash function always produces the same hash from the same input. It will always convert “Password1” to that same thing. If both Alice and Bob use Password123, their passwords will be hashed to the same thing.

Let’s put rainbows on the table

Even if Bob and Alice use the same password (and so have the same hash of their passwords) they don’t have to worry about each other. Who they need to worry about is Charlie the Cracker. Charlie may have spent months running software that picks passwords and generates the hashes of those passwords. He will store those millions of passwords and their hashes in a database called a “Rainbow Table.”

A small portion of Charlie’s table may look like this

PasswordSHA-1 Hash

(Rainbow tables are structured to allow for more efficient storing and lookup for large databases. They don’t actually look anything like my example.)

When the hashed passwords for millions of accounts are leaked, Charlie can simply look up the hashes from the site and see which ones match what he has in his tables. This way he can instantly discover the passwords for any hash that is in his database.

Of course, if you have been using 1Password’s Strong Password Generator to create your passwords for each site, then it is very unlikely that the hash of your password would be in Charlie’s table. But we know that not everyone does that.

Charlie also has a lot of friends (well, maybe not a lot, but he does have some) who have built up their own tables using different ways of generating passwords. This is why Charlie, who has both the usernames and the hashed passwords, may wish to just circulate the hashes. He is asking his friends to help lookup some of these hashes in their own tables.

I also promised to tell you how we know that the leaked hashes are indeed of LinkedIn passwords. If someone has a strong unique password for their LinkedIn account it is very unlikely that it was ever used elsewhere. So if the hash for that strong and unique password turns up on the leaked list, we can know it is from LinkedIn. This is presumably what Robert Graham did when determined that this is the LinkedIn list.

Salting the hash

More than 30 years ago, people realized the problem of pre-computed lookup tables, and so they developed a solution. The solution was to add some salt to password.

Here is how salting can work. Before the system creates a hash of the password it adds some random stuff (called “salt”) to the beginning of password. Let’s say it adds four characters. So when Alice uses the Password123 the system might add “MqZz” as the salt to the beginning to make the password MqZzPassword123. We then calculate the hash of that more unique password. When storing the hash, we also use store the salt with it. The salt is not secret, it just has to be random. Using this method, the salted hash that would be stored for Alice’s password would be “MqZz1b504173d594fd43c0b2e70022886501f30aee16”.

Bob’s password will get a different random salt, say “fgNZ”, which will make the salted hash of his password “fgNZ2ec6fa506fa9048d231b765559e2f3c79bdee5a1”. This is completely different than Alice’s, and – more importantly – it is completely different from anything Charlie has in his rainbow tables. Charlie can’t just build a table with passwords like Password123, instead he would have to build a table that contained Password123 prefixed by all of the two million possible salts we get using a four character salt.

Beyond salt

Salting is an old technology, yet a surprising number of web services don’t seem to be using it. This is probably because many of the tool kits for building websites didn’t include salting by default. The situation should improve as newer toolkits encourage more secure design, and also as these issues make the news.

But just as we are getting people up to speed with a 30 year old technology, salting may no longer be enough. And mere salting certainly isn’t good for the passwords that require the most security. To defend against determined and resourceful password crackers you should use both strong passwords and a password based key derivation function like
PBKDF2, which 1Password does use when encryption your Master Password.

1Password 3.6.5 for iOS is out with PBKDF2 goodness!

1Password Pro icon1Password for iPhone, 1Password for iPad, and 1Password Pro (for both iPhone and iPad) have just been updated to version 3.6.5. All of the changes are behind the scenes, but they include a great security enhancement to how your Master Password is protected. Different versions may become available at different times in different locations, so if your free update isn’t ready for download just yet, try again in a little bit.

In addition to the security enhancements discussed below, there are a few bug fixes, more syncing in the background, and some images tailored for the Retina display in the new iPad. If you just want the cliffnotes, here we go:

★ Improved security. Now using 10,000 PBKDF2 iterations to protect the encryption key.
★ Dropbox authentication tokens are now stored in the system keychain.
★ Better support for iPad retina display.
★ Improved Login filling.
☂ Bug fixes.

But if you want to learn a little more about what we’re doing under the hood to protect your 1Password data, venture on.

10000 PBKDF2 iterations

Your Master Password on your device is now protected with 10,000 iterations of PBKDF2. What this means is that if an attacker were somehow to get hold of your encrypted 1Password data from your phone (not an easy thing to do if you take proper precautions), it will be even harder for them to run automatic password guessing software against your master password. PBKDF2 makes the mathematical process of checking whether a Master Password is correct much longer and more difficult.

Your secrets are very well encrypted and protected by your Master Password, but these new measures strengthen that protection. You can read about PBKDF2 in an old article, Defending against crackers: Peanut Butter Keeps Dogs Friendly, Too to get more details as it applies to 1Password on the desktop; the same ideas work on iOS devices.

Why change things now?

We’ve long considered using PBKDF2 in 1Password for iOS. The advantages of using it are clear: It provides substantial additional resistance to attacks by password guessing software if your encrypted data falls into the wrong hands. There are a few reasons why now was the right time.

We have faster devices

The principle reason this didn’t come sooner is that, with PBKDF2, unlocking your 1Password data on older devices will take noticeably longer and will consume more power than not using PBKDF2. People running 1Password on first generation iPhones will now have an unlocking delay that may last up to a couple of seconds, and a delay of about one second on the iPhone 3G and on the  first generation iPod touch. Delays should not be particularly noticeable on newer devices, and the vast majority of our customers now use 1Password for iOS on said newer devices.

A great feature of iOS 5 and OS X 10.7 is that the number of PBKDF2 iterations can be calibrated to the particular device. We will be making use of that in 1Password 4 for iOS, and we already make use of that in 1Password 3.9 on Lion.

Finding the right implementation

A lesser reason is that the development toolkits for iOS 3 don’t include functions for performing PBKDF2. We try to work with established tool kits as much as possible. iOS 4 (and particularly iOS 5) contain built-in features that make it easier to write programs that perform complicated encryption functions.

That said, we are still able to bring PBKDF2 to 1Password running on iOS 3. Yes, it will be slow and power hungry on older devices, but it is possible because we found a way to take the PBKDF2 function from the OpenSSL libraries and incorporate it into our code. So even though this isn’t in the Apple supplied SDK for iOS 3, we are able to use a well tested and reviewed implementation.

Changes in the threat landscape

There has also been a change in the threat landscape since we first developed 1Password 3 for iOS. There are several “forensic” tool kits on the market for breaking into iOS devices. As new ways in which data can be taken from iOS devices come to light, we need to provide even better protection against off-line attacks on your 1Password data.

It is probably far less likely that that someone will capture your encrypted 1Password data from your iOS device than your 1Password data from your computer. A stolen computer, unless you use FileVault or some other disk encryption, means that your 1Password data will be available to who ever gets a hold of your disk. This is why we built PBKDF2 into 1Password on the desktop a long time ago.

But it is also the case that most people use better Master Passwords on their desktop systems than on their mobile devices. And so, in the less likely event that the data gets captured from an iOS device, the master password could do with extra protection. If everyone had sufficiently strong Master Passwords, PBKDF2 wouldn’t be necessary. But let’s face it: a very strong Master Password on an iPhone is a Master Password that won’t get used much.

Elcomsoft analysis

Although we have long been aware of the benefits of using PBKDF2, a recent report (PDF) by researchers at Elcomsoft highlighted how quickly a master password could be cracked without the additional protection of PBKDF2. We discussed that report in a recent blog post, “Strong Security Requires Strong Passwords“.

Other security improvements

Dropbox OAuth tokens

1Password stores your Dropbox username and password very securely on iOS for automatic syncing, but it hasn’t been quite as careful with the OAuth tokens used when connecting with Dropbox. If this data is copied and used on another device, it would grant access from that other device to a Dropbox account. We have fixed this in 1Password 3.6.5 for iOS.

We’ve discussed this issue extensively in a recent blog post: OAuth, Dropbox, and your 1Password data.

Padding, integrity, and standards

We try to stick to standards when it comes to encryption and protocols, but even well established standards can later be discovered to be flawed. There turns out to be a design problem with the padding scheme used as parts of the PKCS standards. Introducing PBKDF2 (also defined in the same set of standards) gets around the problem.

I won’t go into much detail, but here is a little background into the issue. An encryption algorithm like AES works on a block of data at a time. In the case of AES the blocks are 16 bytes (128-bits) long. Because the data to be encrypted won’t always be a multiple of 16 bytes, some extra data gets added to the end to “pad” it out to a multiple of 16 bytes. The details of the padding scheme have to include some clever tricks so that when the data in decrypted, the decryption process can recognize where the pad begins, so it knows what to remove.

The problem is that the padding scheme has also been used as an integrity check. That is, it provides a signal to the one decrypting the message whether the data has been modified. Padding is not well suited to that purpose, but that usage means that under certain circumstances it can be used to very quickly verify whether something has been decrypted correctly. The attacker is saved an extra decryption trial in testing whether they have “guessed” the right password.

The simple solution is to make use of cryptographically appropriate integrity checks, Message Authentication Codes (MACs) after encrypting the data. That is, the integrity check is performed on the encrypted data instead of on the plaintext. By using PBKDF2 we are forcing an attacker to go through a large number of extra steps with each “guess”, overwhelming any advantage an attacker might gain through the PKCS padding problem.

Processes and products

All this allows me to bring up a point that we’ve made before but will continue to make: Security is a process, not a product. One aspect of this is that a tool that your security depends on is never “done”. This is not the first security improvement we’ve made over the years, and it certainly won’t be the last. But process isn’t only in updating product. Process is about how people do things. That includes our own testing procedures, and it also includes always working to understand how people use 1Password so that we can continue in our effort to make the easy thing to do also the secure thing to do for people.

[Update April 11: Several people, including Quirks In Tech, have correctly pointed out that I should have been much more explicit in this post about the role that the Elcomsoft report played in our decision to start using PBKDF2. Earlier drafts of this included an extensive section on exactly that, but it got lost as I tried to cut this down to size. I’ve added a short section back into this post. -jeff]

Staying ahead with security

We just released 1Password 3.8.11, and this seemingly minor update packs some important security changes under the hood. I’d love to share those with you all.

For a quick review, recall that keeping 1Password secure is a process, and one which requires we at AgileBits keep our eyes on the horizon for potential threats to your security. We want 1Password to be as secure in the future as it has been up to now, so read on about some of  the key changes we’re making.

Also remember that 1Password 3.8.11 for Mac from our website and 3.9.2 from the Mac App Store are both our latest versions for the Mac. Their version numbers are different for now mostly to help us keep them straight.

Increased and more flexible PBKDF2 iterations

PBKDF2 is a trick we use with 1Password to make it much harder for automated password guessing systems to crack your password if they get hold of your encrypted 1Password data file.PBKDF2 diagram Without PBKDF2, automated password guessing systems could guess hundreds of thousands, even millions, of passwords per second. PBKDF2 slows down the processing of your Master Password. There is no way to check a possible password without going through many cycles, called “iterations.”

This means that if you have a good master password along with our use of PBKDF2, your encrypted data is safe even if the bad guys get hold of your data file. If you want to learn more about PBKDF2, check out our previous overview on the topic: Defending Against Crackers: Peanut Butter Keeps Dogs Friendly, Too.

We were ahead of the game when we used PBKDF2 in the design of the current 1Password data file format more than three years ago. But we aren’t going to rest on our laurels. We have been phasing in an increase in the number of PBKDF2 iterations used from 1000 to 10000 or even more. Going from 1000 to 10000 iterations means that a cracker has to do ten times as much work to try a particular guess.

1Password 3.9, the Mac App Store version, can make use of a cool Lion-only feature that automatically calculates the optimal number of PBKDF2 iterations for use on your computer. When you first create a 1Password data file using 1Password 3.9, it will call the CCCalibratePBKDF function that is part of Apple’s new CommonCrypto framework. This will calculate how many PBKDF2 iterations are needed to force, say, a 500 millisecond delay on your machine. We then use this when creating the new data file. We do put an upper limit on these, because the files you create on your super powerful Mac Pro will still need to be used on other potentially less powerful devices that you sync your 1Password data file with.

1Password 3.8 needs to run on Snow Leopard as well as on Lion, so it doesn’t use the same mechanism as the MAS version. But in 1Password 3.8.11 we have set things so that a newly created data file will now use 10000 iterations instead of 1000.

These new settings apply only to newly created 1Password data files. You will have to be patient before we can provide a rock solid way of upgrading an existing data file. We need to make absolutely sure that no matter what may go wrong during a data file upgrade, you will not lose any data, and that testing simply takes time.

Groundwork laid long ago

We have been anticipating this increase in PBKDF2 iterations for a while. One thing that we need to make sure of is that every version of 1Password you may sync your data with will be able to cope with increased iterations. Otherwise, a 1Password data file created with, say, 1Password 3.9 couldn’t be unlocked on other systems, but we’ve had the infrastructure for this change in place for more than a year.

This means that new 1Password data files will also work with current versions of 1Password on iOS, Windows, and Android. It also means that those using 1Password 3.6 on Leopard or Snow Leopard will have no problem unlocking data files created using our latest version. Users of 1Password version 2 (are there any still out there?) will still be able to work with 1Password data files that have already been created, but will encounter problems using a data file that was created with the very latest systems.

HTML export and Login Bookmarklet are on their way out

It’s time to say good-bye to a couple of features that won’t stand up to the anticipated threat environment. One feature, loved by many, is the Login Bookmarklet. This was originally designed as a way to get some 1Password functionality into browsers we didn’t support at the time. Before we had 1Password for iOS, this could be used to kinda-sorta get 1Password data into browsers that didn’t support 1Password directly.

The data in the 1Password Bookmarklet is very well encrypted, but the password for it is not secured using PBKDF2. This means that if the Bookmarklet were to be captured it would need a very strong password on it to resist attack. Because the Login Bookmarklet lives in the browser’s bookmarks, there are more opportunities for it to be captured. Given these two issues, it is time to phase the bookmarklet out. Existing bookmarklets, already in the browser, will continue to work if users decide to keep them. But from this point onward, you will not be able to create new ones.

The story is similar for 1Password’s Encrypted HTML export feature. The passwords for those HTML files are also not protected by the PBKDF2 technique. But the good news is that our much-loved 1PasswordAnywhere feature will continue to work. 1PasswordAnywhere actually uses the same data file as the 1Password application itself, so there are no worries about its data format.

The Login Bookmarklet and Encrypted HTML export features were meant as temporary measures until something better could be put in place. 1PasswordAnywhere, 1Password for non-Mac platforms, and our 1Password extension for Google Chrome are those better ways of doing things.

Password strength indications

The last change I want to talk about is a perfect example of security in one area conflicting with security in another. The fact that you can list and sort your Logins by password strength means that you can easily see which of your passwords need to be updated. This is a very good thing for your security, but as we’ve described before, the information by which you can sort data is not encrypted in the current data format.

The security concern here is that if someone captured your 1Password data file, they wouldn’t be able to break its encryption but they could learn that you had a weak password for If they can also guess your username, they could try weak passwords logging into Fortunately, the real threat is far smaller because almost every website limits login attempts. But more importantly, we have been aware of this security trade-off since we designed the current format.

What we have been waiting for to resolve this trade-off is more powerful computers and cleverer programing techniques. Now that we have both, we’re implementing a new approach: starting with 1Password version 3.8.11 on Mac and 1.0.9.BETA-238 on Windows, password strength is not stored in the data at all, but is recalculated by 1Password as needed.

If you sync your data across different versions of 1Password, you may see some oddnesses where you would expect password strength to show up until those versions fully catch up with 3.8.11. That is, 1Password 3.9.2 from the Mac App Store (at the moment) will incorrectly treat the lack of a strength indicator as a lack of strength. So please have some patience with potentially misleading strength indications on versions that haven’t yet caught up to 1Password 3.8.11 with this.

Repeating myself

We’ve always known that security is a dynamic process and that we would need make these changes at some point. We remain vigilant about changes in computing and the threat environment so that you can rest assured that your data is safe.

Defending against crackers: Peanut Butter Keeps Dogs Friendly, Too.

What happens if someone gets hold of your encrypted 1Password data? What would it take to “crack” it? From the beginning, we’ve designed the 1Password data format with the knowledge that some people would have their computers stolen. I want to briefly talk about one of those design elements: PBKDF2.PBKDF2 diagram r

The abbreviation PBKDF2 stands for
Password Based Key Derivation Function version 2” and does not stand for “Peanut Butter Keeps Dogs Friendly, Too”, but my dogs love peanut butter, and I do find the latter easier to remember. I need to remember “PBKDF2” because it is a very important, though behind the scenes, part of your security.

PBKDF2 deliberately slows down the process of getting from a password to an actual decryption key. The idea is to make using automated password guessing tools, such as John the Ripper, impractical.
PBKDF2 strengthens what would otherwise the be weakest part of a system, your master password. PBKDF2 is called a “Key Strengthening Protocol” for this very reason.

It works by forcing the process that goes from your master password to the derived key go through a large number of complicated iterations. Each time through the data is transformed using an encryption process called HMAC-SHA1, and the resulting intermediate key is fed back into the whole thing again.

For our current (1Password 3) Agile Keychain format, we’ve set things to use 1000 iterations. [Update: changed to 10000 in November 2012] Without PBKDF2, password guessing program could try hundreds of thousands of passwords per second, with PBKDF2 that number is dramatically reduced because there is no way to test a possible master password without having to perform all of those operations. PBKDF2 may cause a fraction of a second delay for you when you enter your master password, but that fraction of a second quickly adds up when a password cracker is trying millions of passwords.

As the environment changes, we are beefing our use of PBKDF2 even more in our next data format. Today, a good master password in combination with our use of PBKDF2 protects your 1Password data, even if it falls into the wrong hands. [Update: There have been several adjustments to PBKDF2 settings since this article was first published, as can be seen by various articles on this blog that discuss PBKDF2]

Coming soon will be a blog post about what makes for a good master password.