PBKDF2
Encyclopedia
PBKDF2 is a key derivation function
that is part of RSA Laboratories' Public-Key Cryptography Standards (PKCS) series, specifically PKCS #5 v2.0, also published as Internet Engineering Task Force
's RFC 2898. It replaces an earlier standard, PBKDF1, which could only produce derived keys up to 160 bits long.
PBKDF2 applies a pseudorandom function, such as a cryptographic hash, cipher
, or HMAC
to the input password
or passphrase
along with a salt
value and repeats the process many times to produce a derived key, which can then be used as a cryptographic key
in subsequent operations. The added computational work makes password cracking
much more difficult, and is known as key stretching. When the standard was written in 2000, the recommended minimum number of iterations was 1000, but the parameter is intended to be increased over time as CPU speeds increase. Having a salt added to the password reduces the ability to use a precomputed dictionary to attack a password (such as rainbow tables) and means that multiple passwords have to be tested individually, not all at once. The standard recommends a salt length of at least 64 bits.
DK = PBKDF2(PRF, P,S,c,dkLen)
where
For each hLen-bit block Ti of derived key DK, computing is as follows:
DK = T1 || T2 || ... || Tdklen/hlen
Ti = F(P,S,c,i)
Where F is an xor of c iterations of chained PRF. First iteration of PRF uses master password P as PRF key and salt concatenated to i. Second and greater PRF uses P and output of previous PRF computation:
F(P,S,c,i) = U1 ^ U2 ^ ... ^ Uc
U1 = PRF(P,S || INT_msb(i))
U2 = PRF(P,U1)
...
Uc = PRF(P,Uc-1)
For example, WPA2 uses
DK = PBKDF2(HMAC−SHA1, passphrase, ssid, 4096, 256)
Disk encryption software
announced a password cracking
utility for Research In Motion BlackBerry
device backups that takes advantage of what Vladimir Katalov, ElcomSoft's CEO, described as the "very strange way, to say the least" in which the BlackBerry uses PBKDF2. The BlackBerry encrypts backup files with AES-256. In turn, the AES key is derived from the user's password using PBKDF2. However the BlackBerry software uses only one PBKDF2 iteration. By contrast, according to Katalov, Apple's iOS 3 uses 2000 iterations and iOS 4 uses 10,000. However, iOS's key management has proven to be a more serious weakpoint.
and scrypt.
Key derivation function
In cryptography, a key derivation function derives one or more secret keys from a secret value such as a master key or other known information such as a password or passphrase using a pseudo-random function...
that is part of RSA Laboratories' Public-Key Cryptography Standards (PKCS) series, specifically PKCS #5 v2.0, also published as Internet Engineering Task Force
Internet Engineering Task Force
The Internet Engineering Task Force develops and promotes Internet standards, cooperating closely with the W3C and ISO/IEC standards bodies and dealing in particular with standards of the TCP/IP and Internet protocol suite...
's RFC 2898. It replaces an earlier standard, PBKDF1, which could only produce derived keys up to 160 bits long.
PBKDF2 applies a pseudorandom function, such as a cryptographic hash, cipher
Cipher
In cryptography, a cipher is an algorithm for performing encryption or decryption — a series of well-defined steps that can be followed as a procedure. An alternative, less common term is encipherment. In non-technical usage, a “cipher” is the same thing as a “code”; however, the concepts...
, or HMAC
HMAC
In cryptography, HMAC is a specific construction for calculating a message authentication code involving a cryptographic hash function in combination with a secret key. As with any MAC, it may be used to simultaneously verify both the data integrity and the authenticity of a message...
to the input password
Password
A password is a secret word or string of characters that is used for authentication, to prove identity or gain access to a resource . The password should be kept secret from those not allowed access....
or passphrase
Passphrase
A passphrase is a sequence of words or other text used to control access to a computer system, program or data. A passphrase is similar to a password in usage, but is generally longer for added security. Passphrases are often used to control both access to, and operation of, cryptographic programs...
along with a salt
Salt (cryptography)
In cryptography, a salt consists of random bits, creating one of the inputs to a one-way function. The other input is usually a password or passphrase. The output of the one-way function can be stored rather than the password, and still be used for authenticating users. The one-way function...
value and repeats the process many times to produce a derived key, which can then be used as a cryptographic key
Key (cryptography)
In cryptography, a key is a piece of information that determines the functional output of a cryptographic algorithm or cipher. Without a key, the algorithm would produce no useful result. In encryption, a key specifies the particular transformation of plaintext into ciphertext, or vice versa...
in subsequent operations. The added computational work makes password cracking
Password cracking
Password cracking is the process of recovering passwords from data that has been stored in or transmitted by a computer system. A common approach is to repeatedly try guesses for the password...
much more difficult, and is known as key stretching. When the standard was written in 2000, the recommended minimum number of iterations was 1000, but the parameter is intended to be increased over time as CPU speeds increase. Having a salt added to the password reduces the ability to use a precomputed dictionary to attack a password (such as rainbow tables) and means that multiple passwords have to be tested individually, not all at once. The standard recommends a salt length of at least 64 bits.
Key derivation process
Function is defined asDK = PBKDF2(PRF, P,S,c,dkLen)
where
- PRF is a parameter of PBKDF2 - it is a pseudorandom function of two parameters with output length hLen (e.g. keyed HMACHMACIn cryptography, HMAC is a specific construction for calculating a message authentication code involving a cryptographic hash function in combination with a secret key. As with any MAC, it may be used to simultaneously verify both the data integrity and the authenticity of a message...
) - P is the master password for which a derivation is generated
- S is a salt
- c number of iterations, positive integer
- dkLen is a length of derived key
- DK is a generated derived key
For each hLen-bit block Ti of derived key DK, computing is as follows:
DK = T1 || T2 || ... || Tdklen/hlen
Ti = F(P,S,c,i)
Where F is an xor of c iterations of chained PRF. First iteration of PRF uses master password P as PRF key and salt concatenated to i. Second and greater PRF uses P and output of previous PRF computation:
F(P,S,c,i) = U1 ^ U2 ^ ... ^ Uc
U1 = PRF(P,S || INT_msb(i))
U2 = PRF(P,U1)
...
Uc = PRF(P,Uc-1)
For example, WPA2 uses
DK = PBKDF2(HMAC−SHA1, passphrase, ssid, 4096, 256)
Systems that use PBKDF2
- Wi-Fi Protected AccessWi-Fi Protected AccessWi-Fi Protected Access and Wi-Fi Protected Access II are two security protocols and security certification programs developed by the Wi-Fi Alliance to secure wireless computer networks...
(WPA and WPA2) used to secure Wi-FiWi-FiWi-Fi or Wifi, is a mechanism for wirelessly connecting electronic devices. A device enabled with Wi-Fi, such as a personal computer, video game console, smartphone, or digital audio player, can connect to the Internet via a wireless network access point. An access point has a range of about 20...
wireless networks - Microsoft WindowsMicrosoft WindowsMicrosoft Windows is a series of operating systems produced by Microsoft.Microsoft introduced an operating environment named Windows on November 20, 1985 as an add-on to MS-DOS in response to the growing interest in graphical user interfaces . Microsoft Windows came to dominate the world's personal...
Data Protection API (DPAPI) - OpenDocumentOpenDocumentThe Open Document Format for Office Applications is an XML-based file format for representing electronic documents such as spreadsheets, charts, presentations and word processing documents....
encryption used in OpenOffice.orgOpenOffice.orgOpenOffice.org, commonly known as OOo or OpenOffice, is an open-source application suite whose main components are for word processing, spreadsheets, presentations, graphics, and databases. OpenOffice is available for a number of different computer operating systems, is distributed as free software... - WinZip's AES Encryption scheme.
- 1Password for generating encryption keys.
- LastPassLastPassLastPass Password Manager is a freemium password management program developed by LastPass. It is available as a plugin for Internet Explorer, Mozilla Firefox, Google Chrome, Opera, and Safari...
for password hashing.
Disk encryption softwareDisk encryption softwareTo protect confidentiality of the data stored on a computer disk a computer security technique called disk encryption is used. This article discusses software that is used to implement the technique...
- FileVaultFileVaultFileVault is a system which encrypts files on a Macintosh computer. It can be found in the Mac OS X v10.4 "Tiger" operating system and later....
(Mac OS XMac OS XMac OS X is a series of Unix-based operating systems and graphical user interfaces developed, marketed, and sold by Apple Inc. Since 2002, has been included with all new Macintosh computer systems...
) from Apple Computer - FreeOTFEFreeOTFEFreeOTFE is an open source on-the-fly disk encryption computer program for PCs running Microsoft Windows, and personal digital assistants running Windows Mobile . It creates virtual drives, or disks, to which anything written is automatically encrypted before being stored on a computer's hard or...
(Windows and Pocket PC PDAs); also supports mounting Linux (e.g. LUKS) volumes under Windows - LUKS (Linux Unified Key Setup) (Linux)
- TrueCryptTrueCryptTrueCrypt is a software application used for on-the-fly encryption . It is free and open source. It can create a virtual encrypted disk within a file or encrypt a partition or the entire storage device .- Operating systems :TrueCrypt supports Microsoft Windows, Mac OS X, and...
(Windows, Linux, and Mac OS X) - DiskCryptorDiskCryptorDiskCryptor is the first open source full disk encryption system for MS Windows that allows the encryption of an entire PC's harddrive or individual partitions – including the ability to encrypt the partition and disk on which the OS is installed....
(Windows) - Cryptographic disk (NetBSD)
- GEOMGEOMGEOM is the main storage framework for the FreeBSD operating system. It is available in FreeBSD 5.0 and higher and provides a standardized way to access storage layers. GEOM is modular and allows for geom modules to connect to the framework. For example, the geom_mirror module will provide RAID1 or...
ELI module for FreeBSDFreeBSDFreeBSD is a free Unix-like operating system descended from AT&T UNIX via BSD UNIX. Although for legal reasons FreeBSD cannot be called “UNIX”, as the direct descendant of BSD UNIX , FreeBSD’s internals and system APIs are UNIX-compliant... - softraid crypto for OpenBSDOpenBSDOpenBSD is a Unix-like computer operating system descended from Berkeley Software Distribution , a Unix derivative developed at the University of California, Berkeley. It was forked from NetBSD by project leader Theo de Raadt in late 1995...
- EncFSEncFSEncFS is a Free FUSE-based cryptographic filesystem that transparently encrypts files, using an arbitrary directory as storage for the encrypted files....
(Linux) since v1.5.0
BlackBerry vulnerability
In September 2010, ElcomSoftElcomSoft
ElcomSoft is a Russian computer software company specializing in computer security and data recovery applications. Popular products include their eBook processing and password recovery software supporting many of Microsoft's products. ElcomSoft is also a co-founder of the Independent Software...
announced a password cracking
Password cracking
Password cracking is the process of recovering passwords from data that has been stored in or transmitted by a computer system. A common approach is to repeatedly try guesses for the password...
utility for Research In Motion BlackBerry
BlackBerry
BlackBerry is a line of mobile email and smartphone devices developed and designed by Canadian company Research In Motion since 1999.BlackBerry devices are smartphones, designed to function as personal digital assistants, portable media players, internet browsers, gaming devices, and much more...
device backups that takes advantage of what Vladimir Katalov, ElcomSoft's CEO, described as the "very strange way, to say the least" in which the BlackBerry uses PBKDF2. The BlackBerry encrypts backup files with AES-256. In turn, the AES key is derived from the user's password using PBKDF2. However the BlackBerry software uses only one PBKDF2 iteration. By contrast, according to Katalov, Apple's iOS 3 uses 2000 iterations and iOS 4 uses 10,000. However, iOS's key management has proven to be a more serious weakpoint.
Alternatives to PBKDF2
One weakness of PBKDF2 is its use of fast processing algorithms while better ones are slower (require greater processing/memory/effort to convert a passphrase into a longer key) and thus make brute force efforts less feasible. Modern alternatives include BcryptBcrypt
bcrypt is an adaptive cryptographic hash function for passwords designed by Niels Provos and David Mazières, based on the Blowfish cipher, and presented at USENIX in 1999...
and scrypt.
External links
- RSA PKCS #5 – RSA Laboratories PKCS #5 v2.0 - Multiple Formats, and test vectors.
- RFC 2898 – Specification of PKCS #5 v2.0.
- RFC 6070 – Test vectors for PBKDF2 with HMAC-SHA1.