Entropy of PBKDF2
How many bits of entropy does PBKDF2 add?
In other words, Dice Ware now recommends 6 words, but 1Password says 55 bits of entropy (5 words) is sufficient. I'm assuming this is because PBKDF2 is slowing the computation down. So, in the master passowrd time-to-crack charts (e.g. one https://blog.agilebits.com/2014/03/10/crackers-report-great-news-for-1password-4/), what would be the times for equivalent passwords where the processing is not slowed down by PBKDF2?
Thanks,
Sean
Comments
-
Hi @lotusone,
Those are some great questions! It sounds like you're looking for some specific/technical answers about all that, and in case you haven't already seen them, the following knowledgebase articles might do a better job of giving you the information you're looking for than I could:
You can find the above articles and more in the Security and Privacy section of our knowledgebase. Does that help to answer your questions? If you need to know more specifics that aren't covered there, I'm sure our security guru would be happy to elaborate on all that. Just let us know! :)
0 -
Thanks for the links! I've already read those documents, which were very interesting, but didn't answer my specific question. Maybe I phrased it poorly; let me phrase it more generally…
Given that Dice Ware's creator now recommends 6 words (or 77.5 bits) [1], and quotes a paper recommending 75 bits of entropy for now and 90 bits to future-proof [2], what makes 1Password unique that you are recommending 55 bits [3]? I was assuming it had to do with PBKDF2, but maybe there's another reason? Or do you disagree with Reinhold's analysis?
Thanks again,
Sean[1] http://world.std.com/~reinhold/dicewarefaq.html#howlong
[2] ftp://ftp.research.att.com/dist/mab/keylength.txt
[3] https://blog.agilebits.com/2012/07/31/1password-is-ready-for-john-the-ripper/0 -
That's a really good question, @lotusone. The answer depends a bit — no pun intended — on the number of PBKDF2 iterations which are calibrated when you first created your vault.
From our blog post On hashcat and strong Master Passwords as your best protection:
We can also double the amount of time to crack by doubling the number of PBKDF2 iterations. Going from 10,000 iterations to 20,000 doubles the crack time, and so it adds the equivalent of 1 bit to the the effective strength. Going from 1000 PKDF2 iterations to 10,000 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.
The simple way to state it is that increasing PBKDF2 iterations offers diminishing returns.
If you are concerned about the protection offered by your Master Password, it is far better to add just a single random character (or Diceware word) to increase the length of your Master Password than to worry too much about the specific protection provided by a specific number of PBKDF2 iterations. We intentionally don't expose that in the UI anywhere since we know folks would focus on the wrong aspect of the protection afforded by their Master Password. There would always be someone who cranks the iterations up to eleventy-million and thinks that allows them to get away with a 6 character Master Password. (I exaggerate, but perhaps less than I wish were true.)
Lastly, different recommendations on how many bits of entropy you want to protect your data are essentially just guidelines. It really just depends on how long of a Master Password you want to type in versus how long you want to make someone work to crack your data. It's a personal preference. For example, I may be okay if someone takes a hundred years to crack my data. I'll be dead by then and won't care what happens. Someone else may want to make sure that it takes millions of years to crack their data. Personal preference. You'll have to choose what's right for you.
I hope that helps. Please don't hesitate to ask any follow up questions. We love talking about this stuff. :)
0 -
I'm enjoying the discussion too!
What I'm trying to determine is the source of the difference between your recommendation and Reinhold's. If the only difference is individual comfort level, then I get it. But I want to make sure there's not a more technical difference. For example, maybe the paper he referenced for his 6 word recommendation used a more sophisticated attack than the one in the Agile blog post. Or maybe his analysis does not include a technique (like PBKDF2) to slow down computation, which, when added makes a 4-5 word passphrase equivalent to a 6 word one without such a technique. I get all the technical stuff on both ends, but can't reconcile them. I'm not comfortable making the call on my own until I understand the source of this difference!
Sean
0 -
@lotusone: It isn't about comfort. It's about security. But ultimately the choice you make regarding your security will depend on your comfort level. So, similar, but not quite the same.
Lastly, different recommendations on how many bits of entropy you want to protect your data are essentially just guidelines. It really just depends on how long of a Master Password you want to type in versus how long you want to make someone work to crack your data. It's a personal preference.
khad really said it all, I think, but I can try to illustrate: if the most sensitive information in my vault is my Facebook login, I'm probably going to be happy with a 3-word Diceware phrase; whereas if it's nuclear launch codes, I'm using at least 10.
It sounds like you're asking us to tell you how many to use, but we can't really do that. It's your data, not ours, so that has to be your choice. You have to balance the cost of having to enter the password with the benefit you'll get from added security.
The best we can do is offer advice based on our own educated guesses and those of the security community at large. And these are all going to be guesses, because we can't know exactly what hardware or methods someone might use to try to crack your data. If they ever even do. Even that scenario is hypothetical. And it would be silly for us to offer you a concrete recommendation for a hypothetical situation — never mind that none of us knows what the future may bring.
In the end, 5-word Diceware is a solid, middle-of-the-road recommendation that should be more than sufficient for everyone's Facebook passwords. If you have more sensitive information that you're storing, by all means, crank it up to 11. Your future self will thank you! :)
0 -
These are tricky questions @lotusone. Some of it is, as @khad pointed out, it is tricky to even say how many "bits" PBKDF2 adds in general (though sometimes we can in specific cases.) But what we can say must be placed within the context of a threat model (which I will return to).
As a recap of what what @khad said, when we add a randomly chosen digit letter to the end of a password we are always increasing that password's strength by log2(10) bits (3.3 bits). It doesn't matter how strong or weak the original password was, by adding that random digit to it we are always increasing its strength by 3.3 bits.
But with PBKDF2, we can't say what adding 10000 rounds does. If we are starting with 10000 rounds, than adding another 10000 rounds adds (effectively) 1 bit. If we started with 50000 rounds, then adding 10000 adds (effectively) only 0.26 bits.
So when talking about these things with PBKDF2 we can only talk about what it does in comparison to something very specific that we can actually compare to.
Making a comparison
Now Diceware was originally designed for PGP passphrases in 1995. At the time PGP used a very simple "String to Key" algorithm. (Indeed, the very earliest versions of PGP just used a simple unsalted hash.) I would have to dig through old source to figure out what was in common usage in 1995. My guess is that it would have have been a (at best) salted MD5.
So let's make up a number. Let's say that a1 round of PBKDF2-HMAC-SHA512 is 32 times (2^5 times) more costly to an attacker that one round of MD5 all other things being equal.2 With this assumption, 1024 (2^10) rounds of PBKDF2-HMAC-SHA512 would be 2^16 times as costly per guess than an MD5 guess. So that is 15 bits. Going from, say, 1024 rounds to, say, 32768 rounds gives us another 15 bits. So in comparison to what Diceware was designed for 1Password's key derivation function is about 30 bits more expensive.
But that calculation is meaningless for very weak passwords. A really weak password is still really weak under any plausible set of PBKDF2 calibrations.
Threat models
Threat models are things you create to help you think clearly about what sorts of capabilities your opponents have, what they are after, and what resources they will use to get at.
Let's talk about threats and opsec
As I've a few time, attackers would prefer to go around encryption than through it. Encryption (if it is done right) is the strongest part of the system. When we are talking about serious attackers (and that is the only context in which Arnold Reinhold's advice matters), then we need to remember that if it is easier for them to break into your computer than break the crypto, they will do that. If it is easier for them to break into your house and tamper with your computer than to break the crypto they will do the easier and cheaper thing.
Defending against those "cheaper" attacks involves "operational security" (OpSec). And we can get a sense of what sorts threat model Arnold Reinhold's advice is based on by the kinds of OpSec use PGP users were using back then.
The fact that Diceware involved rolling dice instead of using a computer should
give you a feel for the kinds of attackers Arnold Reinhold was thinking about.
(Though some if this is because very few computers had good random numbers
generators back then as well.) The idea is that an attacker who has information about the state of a machine you generate your Diceware passphrase on (or even control that machine) could discover your passphrase even before you created it.When I first set up my PGP key, I created one that was on a machine that was never connected to the Internet. The idea was that to keep it secure from attack, I would copy messages onto a floppy disk and then take them home at the end of the day and deal with them on a computer that was never connected to the network. Of course I compiled my copy of PGP myself, checked its signature, and also compiled the operating system it was running on as well.
If I were Edward Snowden, I would be using 80 bit pass phrases. But I would also be using extreme operational security. There is no need for me to use passphrases that would defend me against a billion dollar attack if the attacker organize a break in for twenty thousand dollars.
My costs matter
Of course, using 128 bit or 256 bit encryption is great. Sure it is far far stronger than my operational security, but it doesn't cost me more to use 128 bit keys instead of 64 bit keys. But it does cost me more to use an 80 bit passphrase compared to a 50 bit one. Otherwise I would just be telling everyone to use passphrases that match our key strength of 256 bits.
A dollar is more than eight bits.3
For a long time, I've been putting together various (fairly speculative) tables saying how long in years it would take various kinds of attackers to crack a Master Password. But I think that time isn't the right measure. Instead we should be thinking in terms of total cost to the attacker.
The cost to an attacker includes the capital costs of the hardware (spread out over its lifetime), and the same with the cost of the software. There are the running costs of the hardware (including electricity, cooling, housing it), and general labor costs of operations and maintenance.
Now some big attackers will benefit from economies of scale; but if we fudge around that, this gives us a way to talk about attackers like an individual criminal with a few thousand dollars worth of dedicated hardware to the NSA in the same terms. Let's say, for example, that against 1Password's use of PBKDF2
-HMAC-SHA512 it costs 1USD per million guesses. (Well, let's round that up to 10^20 guesses).This means that a 30 bit password would cost $1000 to crack. A 40 bit password would take a million dollars to crack, and a 50 bit password would take billion (10^9) dollars to crack. Each bit doubles the cost.
So at this rate (1 dollar for 10^20 guesses), a four Diceware word password would cost three and a half billion USD to crack.
-
The very first round of PBKDF2-HMAC-X will twice times as costly as each individual subsequent round, which is why I said "a round" instead of "one round". (This assumes that the defender's PBKDF2 implementation is doing things right. Otherwise the defender will might end up doing twice the work needed for each round. The attacker will not be making that mistake.) ↩︎
-
SHA512 is not that much slower than MD5 under normal circumstances, but MD5 can be much better tuned to using GPUs in a way that SHA512 can't be; so on more specialized hardware of more serious attackers these differences start showing up. ↩︎
-
There was a time when a "bit" referred to eighth of a dollar. ↩︎
0 -
-
Thanks! That was a great answer :)
0 -
On behalf of @jpgoldberg, you're very welcome! If there's a level above "expert", I'd use it to describe his knowledge of & familiarity with this subject. :)
Please let us know if you have more questions - we're always happy to help!
0
