BSDCan2009 - Final Release

BSDCan 2009
The Technical BSD Conference

Colin Percival
Day Talks - 2 - 2009-05-09
Room MNT 202
Start time 15:00
Duration 01:00
ID 147
Event type Lecture
Track Hacking
Language used for presentation English

scrypt: A new key derivation function

Doing our best to thwart TLAs armed with ASICs

Password-based key derivation functions are used for two primary purposes: First, to hash passwords so that an attacker who gains access to a password file does not immediately possess the passwords contained therewithin; and second, to generate cryptographic keys to be used for encrypting or authenticating data.

In both cases, if passwords do not have sufficient entropy, an attacker with the relevant data can perform a brute force attack, hashing potential passwords repeatedly until the correct key is found. While commonly used key derivation functions, such as Kamp's iterated MD5, Provos and Mazieres' bcrypt, and RSA Laboratories' PBKDF1 and PBKDF2 make an attempt to increase the difficulty of brute-force attacks, they all require very little memory, making them ideally suited to attack by custom hardware.

In this talk, I will introduce the concepts of memory-hard and sequential memory-hard functions, and argue that key derivation functions should be sequential memory-hard. I will present a key derivation function which, subject to common assumptions about cryptographic hash functions, is provably sequential memory-hard, and a variation which appears to be stronger (but not provably so). Finally, I will provide some estimates of the cost of performing brute force attacks on a variety of password strengths and key derivation functions.