Check out the new USENIX Web site. next up previous
Next: Related Work Up: A Future-Adaptable Password Scheme Previous: A Future-Adaptable Password Scheme

Introduction

As microprocessors grow faster, so does the speed of cryptographic software. Fast cryptography opens many opportunities for making systems more secure. It renders encryption usable for a wide range of applications. It also permits larger values of tunable security parameters such as key length. Increasing security parameters makes cryptography exponentially (or at least superpolynomially) more difficult to break, dwarfing any benefit faster hardware may offer attackers. Unfortunately, one security parameter--the length and entropy of user-chosen passwords--does not scale at all with computing power. While many systems require users to choose secret passwords for authentication, few actually adapt their algorithms to preserve security in the face of increasingly powerful attackers.

One widespread use of passwords, and a good example of failure to adapt, is the UNIX password system. UNIX, a multi-user operating system, requires users to prove their identity before accessing system resources. A user typically begins a session by providing her username and secret password to a login program. This program then verifies the password using a system-wide password file. Given the importance of keeping passwords secret, UNIX does not store plaintext passwords in this file. Instead, it keeps hashes of passwords, using a one-way function, crypt [9], that can only be inverted by guessing preimages. To verify a password, the login program hashes the password and compares the result to the appropriate hash in the password file.

At the time of deployment in 1976, crypt could hash fewer than 4 passwords per second. Since the only known way of inverting crypt is to guess preimages, the algorithm made passwords very difficult to recover from their hashes--so much so, in fact, that the designers of UNIX felt comfortable leaving the password file readable by all users. Today, over 20 years later, a fast workstation with heavily optimized software can perform over 200,000 crypt operations per second. Attackers can now expediently discover plaintext passwords by hashing entire dictionaries of common passwords and comparing the results to entries in a password file. crypt nonetheless still enjoys widespread use, and legacy software even forces many sites to keep their password files readable by all users.

Today we have authentication schemes considerably more sophisticated than the UNIX password file. In practice, however, implementations of these schemes still often depend on users remembering secret passwords. There are alternatives, such as issuing special authentication hardware to users or giving them printed lists of randomly generated access codes, but these approaches generally inconvenience users or incur additional cost. Thus, passwords continue to play an important role in the vast majority of user-authentication systems.

This paper discusses ways of building systems in which password security keeps up with hardware speeds. We present two algorithms with adaptable cost--eksblowfish, a block cipher with a purposefully expensive key schedule, and bcrypt, a related hash function. Failing a major breakthrough in complexity theory, these algorithms should allow password-based systems to adapt to hardware improvements and remain secure 20 years into the future.

The rest of the paper is organized as follows. In Section 2, we discuss related work on password security. In Section 3, we explain the requirements for a good password scheme. Section 4 presents eksblowfish, a 64-bit block cipher that lets users tune the cost of the key schedule. Section 5 introduces the variable-cost bcrypt password hashing function and describes our implementation in the OpenBSD operating system. Finally, Section 6 compares bcrypt to two widely-used password hashing functions.


next up previous
Next: Related Work Up: A Future-Adaptable Password Scheme Previous: A Future-Adaptable Password Scheme
Niels Provos and David Mazieres
4/28/1999