Pbkdf2 widens passwords. Here widen the password means make the password stronger.
Password widening takes a weak password and a salt and produces a strong (long, high entropy) password which can be safely used in a weak storage environment. Weak storage allows an attacker to check if a guessed password is right or not quickly. Here quickly means a few pico seconds which is what could be achieved in 2014 with $25K of hardware checking a salted SHA256 password. Such hardware can brute force a “weak” password (with an entropy of 40 bits or so) in about a second. Pbkdf2 widens the weak password to an arbitrary (configurable) number of bits, and takes an arbitrary (configurable) amount of time in doing so. The configurable time means the time to reverse the process using brute force is also configurable. Pbkdf2 offers two algorithms for doing this: PBKDF2 (RFC 2988) and Scrypt.
There is a man page, a change log and a README.
Development for pbkdf2 is hosted on Source forge:
Passwords are cracked using brute force. That means each possible password is tried in turn until one works.
In practice the attacker doesn't try every password. Instead they have a list of likely passwords they check against. That list is produced from passwords people have used before plus a set of rules humans use to generate passwords. (Examples of such rules are “substitute 1 for l”, “add a year”, “spell word in reverse” or “capitalise letters”.) In the last decade millions of passwords have exposed, and these passwords have been given to machine learning algorithms. As a result you must assume that if your human brain can remember a password, it is on a password hacker's list.
There are only two things that affect the time it will take to brute force your password. They are:
There is a standard for measuring a password's entropy. It is called NIST Special Publication 800-63. If you are very conservative in choosing a password, meaning your password includes upper and lower case letters, numbers and other special characters and does not use any dictionary words, place names, or dates easily associated with you then a plot NIST 800-63 of your password's strength versus its length looks like this:
The plot dips at 20 characters because NIST assumes once you get to 20 characters you will have included an English word. Passwords beyond 30 characters are cumbersome to enter, so from the plot we can see that even if you are very, very careful and choose a long and complicated password, it will probably have about 40 bits of entropy.
The other variable is how long it takes to check if a given password works. In days gone by we could control this. For example, if you entered a password wrong three times, the system would not let you try again for 10 seconds or so. Most password systems still assume we can control it, but in reality that time has passed. With the advent of the internet most passwords are cracked by hacking servers, downloading the encrypted passwords then using the attacker's own hardware and software to check each guess against the downloaded database. As a consequence, as of 2012, about USD$30K worth of hardware can test each password in 3 pico seconds (3 trillionths of a second). A very good password (ie one with 40 bits of entropy) will take around 3 seconds to crack on such hardware. It is very easy for the owner of a server to encrypt a password using something that takes much longer to check. But in practice almost none do, and since there is no way for you to know whether they do or not you have to assume they don't.
This is where pbkdf2 comes in. It can take your 40 bit password and a salt, and widen it (ie produce another password) to any number of bits. If you widen it to 80 bits it will take the same hardware 38,000 years to crack. In practice the speed at which an attacker can crack your password is determined by how much they are willing to spend, and how long they are prepared to wait for the answer. 80 bits means if they spent USD$1 billion it would take them about 12 months to crack a password in 2012. Adding an additional bit of entropy means one of those numbers doubles (the attacker gets to pick which one).
Which brings up to the other thing you must supply pbkdf2: the salt. A salt is very like a password. The one difference from a password is it doesn't have to be secret. It is a loooong random string, which in practice must be generated by a computer because as we have seen humans are lousy at generating passwords. The salt must have at least as much entropy as the widened password you plan to generate. An 80 bit salt will be around 16 characters long. The strength calculations here assume the attacker knows it. That means you can write it down, and plaster it all across the internet in mailboxes, forums and social networking sites. It is good policy to use a different salt for everywhere you need a password, but in practice that's easy. You can just append the web site name, file name or whatever to the random salt you generate just once, and plaster everywhere.
Unfortunately nothing comes for free and this is true for pbkdf2 too. Using a very strong, widened password just means the next weakest link in the chain will be attacked, and this could be pbkdf2 itself. The attacker can run pbkdf2 on his own hardware and, by running multiple copies in parallel, can reduce the amount of time it takes to check if your “weak” password matches the one downloaded from the hacked web site. The amount of reduction is in principle arbitrary: as before it only depends on the amount of money he is willing to spend. Pbkdf2 defends against this by allowing you to increase the amount of time it takes to create the password. In principle you can make it arbitrarily large, but in practice no one is willing to wait arbitrarily long for their password to be produced.
There is another factor working against pbkdf2. The best pbkdf2 can achieve against an attacker spending N times more money than you did on your computer is him taking 1/N′th of the time it took you to generate the password to check each guess. So, if you spent USD$1000 on a computer, and he spent USD$10 million, he can effectively check 10,000 of your “weak” passwords per second. This means if you are willing to wait 1 second for pbkdf2 to to widen your 40 bit password, it will take the attacker about 3 years to reverse the process to determine your original password.
But that isn't the factor I was referring to. The problem is you are constrained in the computer you can use. It will contain an off the shelf CPU. Attackers with $10 million can choose any hardware they like — GPUs, FPGAs or even custom designed chips (ASICs).
We now come to the reason pbkdf2 offers two ways to widen passwords. One, which pbkdf2 is named after is standardised as RFC 2898. Called PBKDF2, it increases the time it takes to extend a password by increasing the number of ALU operations it takes to calculate the widened password. In the year 2000, when PBKDF2 was proposed, that was reasonable. In the same year Intel released their Netburst CPU architecture, and that was when we collectively learned the raw speed of CPUs as measured in MHz had plateaued. The speed the ALU runs at is determined by raw MHz, so in that year ALU performance also plateaued. Computer programmers are pitifully poor at using multiple ALUs for the tasks an off the shelf CPU does, so CPU designers started using the extra silicon made available by the regular density improvements predicted by Moore's law for other things programmers could use, like speculative execution, floating point and memory cache. The net result is a modern CPU devotes far less than 1% of its silicon to the thing that ultimately determines the speed PBKDF2 runs at: the number of available ALUs. (An Intel Haswell core has 3 integer ALUs and 4 cores. 100,000 transistors per 64 bit Integer add/shift ALU seems like a complete overkill. So that's 1.2 million transistors devoted to ALUs. The Haswell has 1.4 billion transistors.) So one might expect a custom ASIC to be 1000 times faster than Haswell at a fixed ALU task, and as we can see by comparing the speed of Bitcoin ASIC block miners to a Haswell chip of similar cost, that is indeed the case. From that table a HashFast Sierra is 1,690 times as fast per dollar as an Intel Core i5 at 0.1 MHash/sec/$.
That 1000 fold advantage for custom silicon means the calculated 3 years for an attacker armed with $100 million of the same computers you buy becomes 1 day if instead he spends that money on ASICs. Right now this advantage is theoretical, as to my knowledge no one has designed such ASICs. (But then I'm not sure I would know.) However, GPU and FPGAs also provide similar advantages and they are readily available today. A GPU is around an order of magnitude slower, which extends the time required from 1 day to 10.
Enter the second widening method pbkdf2 provides: scrypt. Where PBKDF2 extends the time to widen the password by increasing the ALU operations, scrypt extends it by increasing the number of memory operations; specifically, the number of off chip memory operations. The reason this is better is straight forward: modern off the shelf CPUs are pretty good at accessing memory, and this is unlikely to change. While it is true memory bandwidth has increased over the years, memory latency has remained stubbornly constant. (Latency is the time to access an arbitrary byte, bandwidth is the additional time required to access bytes near that one.) Scrypt leaps around memory chaotically, with each memory block used depending on a cryptographic hash of what was found at the previous one. The process is seeded with the output of a PBKDF2 run. This makes memory latency (as opposed to bandwidth) the dominating factor.
The ultimate speed of many instances of scrypt running in parallel is determined by the number of memory lanes available. This is constrained by the number of pins a chip has. Modern chips top out at around 5000 pins and a memory lane takes around 250 pins, putting the upper limit at 20 lanes. A CPU has 2 lanes typically making the speed difference between it and an ASIC a mere 10 to 1. At that speed, the 3 years is still a respectable 100 days – if the ASICs actually exist. If they don't you are stuck with a FPGA, but raw memory runs too fast for the programmable side of an FPGA, so they have dedicated DDR controllers - usually just one. GPUs tend to have fewer memory lanes than CPUs.
All this adds up to one thing: unlike PBKDF2, Scrypt can do a serviceable job of protecting human memorable passwords. Its one downside over PBKDF2 is it is new, relatively untested, and not standardised.
Pbkdf2 is copyright © 2014,2015,2018 Russell Stuart. It is licensed under the GNU Affero General Public License.
This program is free software: you can redistribute it and/or modify it under the terms of the GNU Affero General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.
The copyright holders grant you an additional permission under Section 7 of the GNU Affero General Public License, version 3, exempting you from the requirement in Section 6 of the GNU General Public License, version 3, to accompany Corresponding Source with Installation Information for the Program or any work based on the Program. You are still required to comply with all other Section 6 requirements to provide Corresponding Source.
This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Affero General Public License for more details.
Russell Stuart, 2014-Jun-02.