PBKDF2

 

NAME

PBKDF2 - widen passwords  

SYNOPSIS

pbkdf2 [options] password [salt]  

DESCRIPTION

Pbdkf2 takes a weak password (a secret random string) and a salt (a long random string that needn't be kept secret) and writes a strong (ie widened) password on the standard output. If salt is not supplied a hidden one is generated using a strong source of random data. If password is '-' the program will read it from the standard input, prompting for it on standard error if the standard input is a terminal.

 

OPTIONS

-c, C, --charset C
Use the characters in C instead of base59 to encode the binary result in a printable form. Base59 consists of numbers and upper and lower ASCII letters bar the letters 'I', 'l' and 'O'.
-h H, --hash H
Use the hash named H instead of SHA1. Less commonly used hashes (like SHA224 or SHA384) are a better choice.
--help
Print a help message followed by a list of recognised hash names.
-l L, --length L
The length of the binary password generated in bytes. Multiplying by 8 yields the entropy of the widened password in bits.
-P P, --pbkdf2-iterations P
Use P pbkdf2 iterations instead of 10000 (or 1 if scrypt is used). Higher is more secure but (linearly) slower.
-s S, --scrypt S
Pass the output of pbkdf2 through Scrypt. S is the size in bytes of the on chip cache to defend against. Suffixes like KB, and GiB are accepted. It must be a power of 2. Higher is more secure but (linearly) slower.
-S S, --scrypt-iterations S
Use S Scrypt iterations instead of 1. Higher is more secure but (linearly) slower.
-t, --time
Print the time it took to widen the password on stderr.

 

SECURITY NOTES

The length the widened password needs to be is determined by how well the web site stores it. Typically they will use a salted hash. They shouldn't, but you have no control over it. You tell pbkdf2 the length you require using --length. --length 10 (which means you have 80 bits of entropy) is a reasonable minimum. But that is 10 binary bytes and typically you can't enter binary into a password field. Pbkdf2 will encode it for you into something you can enter (see --charset). The length of the encoded version is determined by the encoding, with the default encoding needing 14 characters for an 10 byte widened password.

Pbkdf2 itself can be attacked using brute force. Its defense against this is the amount of time it takes to calculate the widened password. Ensuring that time is long enough is critical to the security of your "weak" password. It can be printed using --time. Experiment with --scrypt-iterations (or --pbkdf2-iterations if not using Scrypt) to set it to an appropriate value.

Pbkdf2 provides two algorithms for widening the password - a standardised one (PBKDF2) and a newer, stronger but less well tested one called Scrypt. The PBKDF2 algorithm extends the time by using many ALU (Arithmetic Logic Unit - a part of a CPU) operations. Nowadays there are devices with many more ALU's than a modern CPU (in some cases 1000's more) so this strategy is no longer as effective as it could and should be. The Scrypt algorithm extends the time by using many off-chip memory references. The difference between other devices and a modern CPU in accessing is much smaller - a factor of 10 is perhaps feasible with custom silicon.

However, this implies that to have any effect at all Scrypt must force the attacker to not use on-chip memory, because on-chip memory is very fast. Such on-chip memory is often called cache. Scrypt does this by using far more memory than can fit into the on-chip cache (at least double). Since you set the amount of memory Scrypt uses with the --scrypt option, the figure you supply is critical to protecting your "weak" password. Modern CPU's have very large on-chip caches, so the amount of cache found in a desktop class CPU is a good guide. Use at least twice that, more if you want the password to be secure for many years.

When choosing the strength of the "weak" password to use and how much time pbkdf2 should use to widen it, it is helpful to consider the resources that will be available to the person trying to break it - the attacker. These resources can be reduced to time and money. If you are prepared to wait a second for your password and the attacker is prepared to wait a week to crack it that means the attacker can test 604,800 passwords. 604,800 is roughly equal 2^19 which means they will crack any supplied "weak" password with 19 or less bits of entropy. If they are prepared to spend 1,000 times the amount of money you did on a CPU and are prepared to wait a week then it goes up to 30 bits entropy. Brute forcing a password with 40 bits of entropy is feasible for a very well funded and patient attacker. The price here means the price of the CPU chip, not the entire system. A desktop CPU chip has stabilized at around $100, the price of the system it is in is typically 10 times that - use the $100 figure. The price of a CPU in a phone or tablet is around $10.

In practice this means the "weak" password you supply should have an entropy of at least 40 bits. Estimating the entropy is more of an art form than a science. A conservative way of doing it published by the US government, It is called NIST Special Publication 800-63. As a guide NIST 800-63 says a password of 20 characters that has both upper case and non-alphabetic characters and avoid things easily associated with you (like names, places or dates) will be around 40 bits. You can trade entropy bits for time. In practice, this means for the inconvenience of remembering and typing each extra character you have after 20 you can halve the amount of time you have to wait for pbkdf2 to widen the password.

 

HOW AND WHEN TO USE PBKDF2

Pbkdf2 is useful for protecting data you care deeply about. Examples might be an encrypted file containing your bank account login details, a Bitcoin wallet containing a substantial sum, private gpg keys used to sign a code, or even a master password file. In every case this information will be stored in an encrypted file protected by a password. A suitable password needs at least 80 bits of entropy. Remembering and entering a password with 80 bits of entropy is not something even the most paranoid human will or even could do. This is the problem pbkdf2 is designed to solve.

Step 1
Think up a suitable "weak" password. You only need one. You must memorise it as recording it anywhere, in any fashion, weakens its strength considerably.
Step 2
Use pbkdf2 to generate random characters suitable for using in the salt:

pbkdf2 -l 10 x

Use the password output as the salt. (Yes, the password is a widened version of the supplied (very) weak password 'x'. However, you didn't supply a salt, so pbkdf2 generated a large random salt for you. The end result is a PDKBD2 hashed version of a salt no one has seen.)

Step 3
The difficulty is remembering the salt. It is large, and you will be generating a different one for each file you need to protect. One technique is to rename the file you are protecting to include the salt. For example, if the file name was:

passwords.txt

The renamed version might be:

passwords-B42iuHkFWKh9qe.txt

The entire file name becomes your salt.

Step 4
Armed with a salt, encrypt the file using your favourite encryption package. Here I use openssl:

P=$(pbkdf2 -s 256M -l 10 - passwords-B42iuHkFWKh9qe.txt) \
    openssl aes-128-cbc -pass env:P -nosalt -e \
        -in passwords-B42iuHkFWKh9qe.txt \
        -out passwords-B42iuHkFWKh9qe.txt.aes

You will be prompted for your password. To decrypt, reverse this step by changing -e to -d and exchanging the filenames given to -in and -out.

Step 5
Following these instructions ensures your password is not the weakest link in the chain. In reality this won't stop an attacker, they will just move their attention to the next weakest link. Avoid malware, dementia, rubber hoses, and the UK.

 

ACKNOWLEDGMENTS

The Scrypt algorithm was designed by Colin Percival. Colin used Scrypt in his commercial backup solution, called Tarsnap. Tarspan's client code is open source. Some of the code in pbkdf2 is based on the implementation in Tarsnap.

 

SEE ALSO

Pbkdf's web page has a detailed explanation of the rational behind it's use. http://pbkdf2.sourceforge.net/

RFC 2898 for an explanation of PBKDF2. http://tools.ietf.org/html/rfc2898

Scrypt's home page is http://www.tarsnap.com/scrypt.html

 

AUTHOR

Russell Stuart, <russell-debian@stuart.id.au>.