Many authentication schemes depend on secret passwords. Unfortunately, the length and entropy of the passwords users choose remain fixed over time. In contrast, hardware constantly improves, giving attackers increasing computational power. As a result, password schemes (including the traditional UNIX user-authentication system) are failing to withstand off-line password guessing attacks.
In this paper, we formalize the notion of a password scheme ``as good as the passwords users choose,'' and show that the computational cost of such a scheme must necessarily increase with the speed of hardware. We propose two algorithms of parameterizable cost for use with passwords. Eksblowfish, a block cipher, lets one safely store encrypted private keys on disk. Bcrypt, a hash function, can replace the UNIX password hashing function or serve as a front-end to secure password protocols like SRP. We have deployed bcrypt as part of the OpenBSD operating system's password authentication. So far, it compares favorably to the two previous hashing algorithms. No surprise optimizations have yet turned up. As hardware speeds increase, OpenBSD lets one preserve the cost of off-line password cracking by tuning a simple configuration file.