Techniques for mitigating the threat of off-line password guessing generally aspire to one of two goals--limiting a system's susceptibility to off-line attacks or increasing their computational cost. As a simple example of the former, many modern UNIX systems now keep password hashes secret from users, storing them in a read-protected shadow password file rather than in the standard openly readable one.
Much of the work on preventing off-line password attacks has centered around communication over insecure networks. If cryptographic protocols rely on user-chosen passwords as keys, they may open themselves up to off-line guessing attacks. Gong et. al. [7] suggest several protocol design tricks to thwart password guessing by network attackers. Unfortunately, their most interesting proposals require encryption algorithms with unusual and difficult to achieve properties.
Several people have designed secure password protocols that let users authenticate themselves over insecure networks without the need to remember or certify public keys. Bellovin and Merritt [2,3] first proposed the idea, giving several concrete protocols putatively resistant to off-line guessing attacks. Patel [11] later cryptanalyzed those protocols, but people have since continued developing and refining others in the same vein. More recent proposals such as SRP [16] show promise of being secure.
Of course, even a secure password protocol requires some server capable of validating users with correct passwords. An attacker who obtains that server's secret state can mount an off-line guessing attack. Because secure password protocols require public key cryptography [8], they do have a tunable key length parameter. However, this parameter primarily controls the difficulty of mounting off-line attacks without a server's secret state; it only indirectly affects the cost of an off-line attack given that state. Tuning key length to preserve password guessing costs would have other unintended consequences, for instance increasing message sizes and costing servers unnecessary computation. By combining a scheme like SRP with the bcrypt algorithm presented in this paper, however, one can vary the cost of guessing passwords independently from most other properties of the protocol.
Whatever progress occurs in preventing off-line attacks, one can never rule them out entirely. In fact, the decision to have an openly readable password file was not an oversight on the part of the UNIX system designers [9]. Rather, it was a reaction to the difficulty of keeping the password file secret in previous systems, and to the realization that a supposedly secret password file would need to resist off-line guessing anyway. This realization remains equally true today. Aside from the obvious issues of backup tape security, attackers who compromise UNIX machines routinely make off with the list of hashed passwords, whether shadowed or not.
A poor hashing algorithm not only complicates recovery from break-ins, it also endangers other machines. People often choose the same password on multiple machines. Many sites intentionally maintain identical password files on all machines for administrative convenience. While shadow password files certainly do not hurt security, the big flaw in UNIX password security is not its openly readable password file. Rather, it is the choice of a hash function that cannot adapt to a 50,000 fold increase in the speed of hardware and software. This paper presents schemes that can adapt to such improvements in efficiency.
Others have already proposed numerous schemes to increase the cost of guessing passwords. The FreeBSD operating system, for instance, introduced a replacement for crypt based on the MD5 [13] message digest algorithm. MD5 crypt takes considerably longer to compute than the original crypt. Yet, it still has a fixed cost and thus cannot not adapt to faster hardware. As time passes, MD5 crypt offers steadily decreasing protection against off-line guessing attacks. Significant optimizations have already been found to speed up the calculation of MD5 crypt.
Abadi et. al. [1] propose strengthening user-chosen passwords by appending random bits to them. At authentication time, software uses the known part of the password and a hash of the full password to guess the random bits. As hardware gets faster, one can easily tune this technique by increasing the number of random bits. Unfortunately, password strengthening inherently gives unauthenticated users the ability to mount off-line guessing attacks. Thus, it cannot be combined with techniques like SRP that attempt to limit the possibility of off-line attacks in the first place.
Finally, many systems rely less directly on password security for authentication. The popular ssh [17] remote login program, for example, allows users to authenticate themselves using RSA encryption. Ssh servers must have a user's RSA public key, but they need not store any information with which to verify user-chosen passwords. The catch is, of course, that users must store their private keys somewhere, and this usually means on disk, encrypted with a password. Worse yet, ssh uses simple 3-DES to encrypt private keys, making the cost of guessing ssh passwords comparable to the cost of computing crypt. Nonetheless, because of its flexibility, ssh's RSA authentication is a generally better approach than schemes more closely tied to passwords. For example, without modifying the core protocols, ssh could easily employ the eksblowfish algorithm proposed in this paper to improve the security of stored secret keys.