THE ADVANCED COMPUTING SYSTEMS ASSOCIATION
`
`The following paper was originally published in the
`Proceedings of the FREENIX Track:
`1999 USENIX Annual Technical Conference
`
`Monterey, California, USA, June 6–11, 1999
`
`A Future-Adaptable Password Scheme
`
`Niels Provos and David Mazières
`The OpenBSD Project
`
`© 1999 by The USENIX Association
`All Rights Reserved
`
`Rights to individual papers remain with the author or the author's employer. Permission is granted for noncommercial
`reproduction of the work for educational or research purposes. This copyright notice must be included in the reproduced paper.
`USENIX acknowledges all trademarks herein.
`
`For more information about the USENIX Association:
`Phone: 1 510 528 8649
`FAX: 1 510 548 5738
`Email: office@usenix.org WWW: http://www.usenix.org
`
`
`
`
`
`
`
`Datavant Exhibit 1022
`Datavant v. Vigilytics
`IPR2024-00307
`
`Page 1 of 13
`
`

`

`A Future-Adaptable Password Scheme
`
`Niels Provos and David Mazi

eres
`fprovos,dmg@openbsd.org
`The OpenBSD Project
`
`Abstract
`
`the face of increasingly powerful attackers.
`
`Many authentication schemes depend on secret
`passwords. Unfortunately, the length and ran-
`domness of user-chosen passwords remain xed
`over time.
`In contrast, hardware improvements
`constantly give attackers increasing computational
`power. As a result, password schemes such as the
`traditional UNIX user-authentication system are
`failing with time.
`
`This paper discusses ways of building systems in
`which password security keeps up with hardware
`speeds. We formalize the properties desirable in a
`good password system, and show that the compu-
`tational cost of any secure password scheme must
`increase as hardware improves. We present two al-
`gorithms with adaptable cost|eksblowsh, a block
`cipher with a purposefully expensive key schedule,
`and bcrypt, a related hash function. Failing a ma-
`jor breakthrough in complexity theory, these al-
`gorithms should allow password-based systems to
`adapt to hardware improvements and remain secure
`well into the future.
`
` Introduction
`
`As microprocessors grow faster, so does the speed
`of cryptographic software. Fast cryptography opens
`many opportunities for making systems more se-
`cure. It renders encryption usable for a wide range
`of applications. It also permits larger values of tun-
`able security parameters such as key length.
`In-
`creasing security parameters makes cryptography
`exponentially or at least superpolynomially more
`dicult to break, dwarng any benet faster hard-
`ware may oer attackers. Unfortunately, one se-
`curity parameter|the length and entropy of user-
`chosen passwords|does not scale at all with com-
`puting power. While many systems require users to
`choose secret passwords for authentication, few ac-
`tually adapt their algorithms to preserve security in
`
`One widespread use of passwords, and a good ex-
`ample of failure to adapt, is the UNIX password
`system. UNIX, a multi-user operating system, re-
`quires 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 veries the pass-
`word using a system-wide password le. Given the
`importance of keeping passwords secret, UNIX does
`not store plaintext passwords in this le. Instead,
`it keeps hashes of passwords, using a one-way func-
`tion, crypt  , 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 le.
`
`At the time of deployment in , crypt could hash
`fewer than  passwords per second. Since the only
`known way of inverting crypt is to guess preim-
`ages, the algorithm made passwords very dicult
`to recover from their hashes|so much so, in fact,
`that the designers of UNIX felt comfortable leaving
`the password le readable by all users. Today, over
` years later, a fast workstation with heavily opti-
`mized software can perform over , crypt op-
`erations per second. Attackers can now expediently
`discover plaintext passwords by hashing entire dic-
`tionaries of common passwords and comparing the
`results to entries in a password le. crypt nonethe-
`less still enjoys widespread use, and legacy software
`even forces many sites to keep their password les
`readable by all users.
`
`Today we have authentication schemes considerably
`more sophisticated than the UNIX password le. In
`practice, however, implementations of these schemes
`still often depend on users remembering secret pass-
`words. There are alternatives, such as issuing spe-
`cial 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
`
`Page 2 of 13
`
`

`

`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|eksblowsh, a block cipher with a purposefully
`expensive key schedule, and bcrypt, a related hash
`function. Failing a major breakthrough in complex-
`ity theory, these algorithms should allow password-
`based systems to adapt to hardware improvements
`and remain secure  years into the future.
`
`In
`The rest of the paper is organized as follows.
`Section , we discuss related work on password secu-
`rity. In Section , we explain the requirements for a
`good password scheme. Section  presents eksblow-
`sh, a -bit block cipher that lets users tune the
`cost of the key schedule. Section  introduces the
`variable-cost bcrypt password hashing function and
`describes our implementation in the OpenBSD op-
`erating system. Finally, Section  compares bcrypt
`to two widely-used password hashing functions.
`
` Related Work
`
`Password guessing attacks can be categorized by
`the amount of interaction they require with an au-
`thentication system. In on-line attacks, the perpe-
`trator must make use of an authentication system
`to check each guess of a password. In o-line at-
`tacks, an attacker obtains information|such as a
`password hash|that allows him to check password
`guesses on his own, with no further access to the
`system. On-line attacks are generally considerably
`slower than o-line ones. Systems can detect on-
`line attacks fairly easily and defend against them by
`slowing the rate of password checking. In contrast,
`once an attacker has obtained password verication
`information, the only protection a system has from
`o-line attacks is the computational cost of checking
`potential passwords.
`
`Techniques for mitigating the threat of o-line pass-
`word guessing generally aspire to one of two goals|
`limiting a system’s susceptibility to o-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, stor-
`ing them in a read-protected shadow password le
`rather than in the standard openly readable one.
`
`Much of the work on preventing o-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 o-line guessing attacks. Gong
`et. al.  suggest several protocol design tricks to
`thwart password guessing by network attackers. Un-
`fortunately, their most interesting proposals require
`encryption algorithms with unusual and dicult to
`achieve properties.
`
`Several people have designed secure password pro-
`tocols that let users authenticate themselves over
`insecure networks without the need to remember or
`certify public keys. Bellovin and Merritt ,  rst
`proposed the idea, giving several concrete proto-
`cols putatively resistant to o-line guessing attacks.
`Patel   later cryptanalyzed those protocols, but
`people have since continued developing and rening
`others in the same vein. More recent proposals such
`as SRP   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 o-line guessing attack.
`Because secure password protocols require public
`key cryptography , they do have a tunable key
`length parameter. However, this parameter pri-
`marily controls the diculty of mounting o-line
`attacks without a server’s secret state; it only in-
`directly aects the cost of an o-line attack given
`that state. Tuning key length to preserve password
`guessing costs would have other unintended conse-
`quences, for instance increasing message sizes and
`costing servers unnecessary computation. By com-
`bining 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 o-line at-
`tacks, one can never rule them out entirely. In fact,
`the decision to have an openly readable password
`le was not an oversight on the part of the UNIX
`system designers  . Rather, it was a reaction to
`the diculty of keeping the password le secret in
`previous systems, and to the realization that a sup-
`posedly secret password le would need to resist
`o-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 o with the list of
`hashed passwords, whether shadowed or not.
`
`Page 3 of 13
`
`

`

`A poor hashing algorithm not only complicates re-
`covery from break-ins, it also endangers other ma-
`chines. People often choose the same password on
`multiple machines. Many sites intentionally main-
`tain identical password les on all machines for ad-
`ministrative convenience. While shadow password
`les certainly do not hurt security, the big aw in
`UNIX password security is not its openly readable
`password le. Rather, it is the choice of a hash
`function that cannot adapt to a , fold increase
`in the speed of hardware and software. This paper
`presents schemes that can adapt to such improve-
`ments in eciency.
`
`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 MD   mes-
`sage digest algorithm. MD crypt takes consider-
`ably longer to compute than the original crypt. Yet,
`it still has a xed cost and thus cannot not adapt
`to faster hardware. As time passes, MD crypt of-
`fers steadily decreasing protection against o-line
`guessing attacks. Signicant optimizations have al-
`ready been found to speed up the calculation of
`MD crypt.
`
`Abadi et. al.   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, pass-
`word strengthening inherently gives unauthenti-
`cated users the ability to mount o-line guessing
`attacks. Thus, it cannot be combined with tech-
`niques like SRP that attempt to limit the possibility
`of o-line attacks in the rst place.
`
`Finally, many systems rely less directly on password
`security for authentication. The popular ssh  
`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 ver-
`ify 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 -DES to
`encrypt private keys, making the cost of guessing
`ssh passwords comparable to the cost of computing
`crypt. Nonetheless, because of its exibility, 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 eksblowsh algorithm pro-
`posed in this paper to improve the security of stored
`secret keys.
`
` Design
`schemes
`
`criteria
`
`for
`
`password
`
`Any algorithm that takes a user-chosen password as
`input should be hardened against password guess-
`ing. That means any public or long-lived output
`should be of minimal use in reconstructing the pass-
`word. Several design criteria can help achieve this
`goal.
`
`Ideally, one would like any password handling al-
`gorithm to be a strong one-way function of the
`password|that is, given the algorithm’s output and
`other inputs, an attacker should have little chance
`of learning even partial information she could not
`already have guessed about the password. Unfortu-
`nately, one-way functions are dened asymptotically
`with respect to their input lengths|an attacker has
`negligible probability of inverting a one-way func-
`tion on suciently large inputs, but exactly how
`large depends on the attacker. Because there is a
`xed limit to the size of passwords users will tol-
`erate, we need a dierent criterion for functions on
`passwords.
`
`Informally, we would like a password scheme to be
`as good as the passwords users choose." Given a
`probability distribution D on passwords, we dene
`the predictability RD of the distribution to be the
`highest probability Prs of any single password s
`in D: RD = maxsD Prs. A function of a pass-
`word is secure if an attacker’s probability of learning
`any partial information about the password is pro-
`portional to the product of the work she invests and
`the predictability of the password distribution.
`
`What does it mean for an attacker to learn partial
`information about a password? We dene partial in-
`formation to be the value of any single-bit predicate
`on a password. Interesting predicates on passwords
`might include the rst bit of a password, or the par-
`ity of bits in a password. An attacker can always
`guess certain predicates with high probability|for
`instance, the trivial predicate P s = which re-
`turns on all passwords. If a function of a password
`is secure, however, its output should not let an at-
`
`Page 4 of 13
`
`

`

`tacker guess any predicate more accurately than she
`could have without the function’s output.
`
`bits:
`
`D; A;
`Prt  T; s  D; s  As; t;
`s = s ^ F s; t =F s; t
` jAj RD
`
`We should rst note that this denition matches
`our intuition about a password hashing function like
`crypt. If users choose predictable enough passwords,
`knowing a password hash gives adversaries a large
`advantage|they can compare hashes of the most
`popular passwords to that of the password they are
`trying to break.
`If, additionally, one can guess a
`useful predicate without even looking at a password
`hash|for instance by knowing that the third char-
`acter of most passwords is a lower-case letter|then
`clearly an adversary can guess this too.
`
`If, however, no single password occurs with partic-
`ularly high probability, an adversary should need
`to expend a large amount of eort as measured
`in circuit gates to discover any non-trivial infor-
`mation about a password. Finally, we also wish to
`prevent an attacker from nding other strings that
`hash to the same value as a password; such strings
`may prove equivalent to passwords during authen-
`tication. The requirement of second preimage re-
`sistance guarantees such collisions are hard to nd,
`even with knowledge of the original password.
`It
`also ensures that F does not ignore any bits of its
`password input.
`
`The denition implies that a secure password func-
`tion F s; t must make non-trivial use of its second
`argument, t. To see this, consider that the rst bit
`of F s;  is a perfectly valid predicate on passwords.
`An attacker could easily guess this predicate if either
`F ignored its second argument or the string oc-
`curred in T with high probability. This point is not
`merely an academic one. A single-input password
`hashing function F s can be inverted by a circuit
`large enough to encode a lookup table mapping F s
`or suciently many bits of F s to s. The size of
`such a circuit depends only on the probability dis-
`tribution of the passwords, not on the particulars
`of F .
`
`As proposed by Morris and Thompson  , however,
`lookup tables can be thwarted with the second in-
`put to F , which they call a salt. If a random salt
`is chosen whenever users establish new passwords,
`and if the salt space is large enough to ensure a neg-
`
`More formally, let F s; t be a function. The argu-
`ment s represents a user’s secret password, which
`will be drawn from a probability distribution D.
`The argument t represents any additional non-secret
`inputs F might take. Let the values of t be drawn
`from a probability distribution T . We model an at-
`tacker as a randomized boolean circuit , A, that
`tries to guess a predicate P about a password.
`The cost of an attack|or the work invested by
`an attacker|is the number of gates in the cir-
`cuit, which we denote jAj. We use the notation
`Prv  S ; v  S; : : : ; B to denote the proba-
`bility of statement B after an experiment in which
`variables v ; v; : : : are drawn from probability dis-
`tributions S ; S; : : :, respectively. Now we can de-
`ne what it means for a password function to resist
`attack. We say that function F s; t is an -secure
`password function if the following hold:
`
` . Finding partial information about F ’s secret in-
`put is as hard as guessing passwords. Put an-
`other way, for any password distribution D and
`predicate P , an attacker A who guesses P based
`on output from F will do almost as well when
`F is computed on unrelated passwords:
`
`D; P; A;
`
`Prt  T; : : : ; tc  T; s  D;
`b  At ; F s; t ; : : : ; tc; F s; tc;
`b = P s
`(cid:0) Prt  T; : : : ; tc  T; s  D;
`b  At ; F s; t ; : : : ; tc; F s; tc;
`s  D; b = P s
`
` jAj R D
`
` 
`
`
`
`. Finding second preimages is as hard as guess-
`ing passwords. A second preimage of an input
`s; t is a dierent password s
`= s for which
`F s; t =F s; t. Here we model the attacker
`A as a randomized circuit with multiple output
`
` Boolean circuits are a complexity theoretic abstraction.
`A boolean circuit is an acyclic collection of interconnected
`gates. Each gate computes a boolean function of , or 
`single-bit inputs. A randomized boolean circuit takes a cer-
`tain number of random input bits in addition to its regular
`inputs.
`
`Page 5 of 13
`
`

`

`ligible probability of recurrence, lookup tables oer
`an adversary no advantage; he may as well compute
`F at the time of attack. If, on the other hand, the
`salt space is too small, the output bits of F become
`useful predicates on passwords, a fact exploited by
`the QCrack   program described in Section .
`
`While salted passwords defeat lookup tables, given
`a particular salt and hash, an adversary can still
`mount a brute force attack by evaluating F s; t on
`every possible password. It follows that the best se-
`curity one can achieve is  =jF j, where jF j is the
`cost in gates of implementing F . Usability require-
`ments therefore eect a lower limit on |if people
`can only tolerate a one second delay for checking
`passwords, F can take at most one second to eval-
`uate. F should not take signicantly less, however,
`as this would unnecessarily weaken security.
`
`The number of gates jAj that an adversary can rea-
`sonably muster for an attack increases constantly
`as hardware improves. Fortunately, so does the
`speed of machines that must legitimately evaluate
`F . That means passwords should not be hashed by
`a single function F with xed computational cost,
`but rather by one of a family of functions with ar-
`bitrarily high cost. Instead of repeatedly throwing
`out functions like crypt and MD crypt to start over
`with more expensive but incompatible ones, systems
`should allow the cost of any password manipulation
`software to scale gracefully with a tunable param-
`eter. Thus, can decrease as fast as hardware im-
`proves and users will tolerate. Compromised pass-
`word databases will then enjoy maximum security
`against o-line attacks.
`
`In summary, a good password function makes ex-
`tracting any partial information about passwords
`as dicult as guessing passwords. A concrete pa-
`rameter, , should characterize this diculty. To
`achieve low values of , a password function must
`take a second input, the salt, that prevents adver-
`saries from beneting from large lookup tables. The
`best value of is inversely proportional to the cost
`of evaluating a password function. This establishes
`a lower limit for based on the maximum tolera-
`ble cost of evaluating F during legitimate use. As
`hardware speeds constantly improve, a good pass-
`word scheme should allow the cost of F to increase
`gradually so that can decrease over time.
`
`One nal criterion for a good password function is
`then to minimize the value jF j. That means one
`should make any password function as ecient as
`
`possible for the setting in which it will operate. The
`designers of crypt failed to do this. They based crypt
`on DES  , a particularly inecient algorithm to
`implement in software because of many bit transpo-
`sitions. They discounted hardware attacks, in part
`because crypt cannot be calculated with stock DES
`hardware. Unfortunately, Biham  later discovered
`a software technique known as bitslicing that elim-
`inates the cost of bit transpositions in computing
`many simultaneous DES encryptions. While bitslic-
`ing won’t help anyone log in faster, it oers a stag-
`gering speedup to brute force password searches.
`
`In general, a password algorithm, whatever its cost,
`should execute with near optimal eciency in any
`setting in which it sees legitimate use, while oering
`little opportunity for speedup in other contexts. It
`should rely heavily on a CPU’s fast instructions|
`for instance addition, bitwise exclusive-or, shifts,
`and memory access to state that ts in a processor’s
`rst level cache. Ideally these operations should all
`be portably accessible from high-level languages like
`C, so as to minimize the benet of hand-coded as-
`sembly language implementations. Conversely, the
`algorithm should avoid operations like bit transpo-
`sition on which customized hardware enjoys a large
`advantage.
`
`A password function should also not lend itself to
`any kind of pipelined hardware implementation. It
`should permit relatively little speedup from any
`kind of precomputation|for instance, hashing ,
`passwords with the same salt and hashing one pass-
`word under , salts should each cost , times
`more than hashing a single password.
`
` Eksblowsh Algorithm
`
`We now describe a cost parameterizable and salted
`block cipher that we call eksblowsh for expensive
`key schedule blowsh. Eksblowsh is designed to
`take user-chosen passwords as keys and resist at-
`tacks on those keys. As its base we use the blow-
`sh   block cipher by Schneier, which is well-
`established and has been fairly well analyzed.
`
`Blowsh is a -bit block cipher, structured as a -
`round Feistel network  . It uses  -bit subkeys,
`P ; : : : ; P , which it derives from the encryption
`key. The subkeys are known collectively as the P-
`Array.
`
`Blowsh encrypts by splitting a -bit input block
`
`Page 6 of 13
`
`

`

`Plaintext
`
`32 bit
`
`64 bit
`
`32 bit
`
`32 bit
`
`P1
`
`32 bit
`
`32 bit
`
`F
`
`F
`
`13 More Iterations
`
`F
`
`P17
`
`32 bit
`
`32 bit
`
`64 bit
`Ciphertext
`
`P2
`
`P16
`
`P18
`
`EksBlowshSetup cost, salt, key
`state  InitState 
`state  ExpandKey state, salt, key
`repeat cost 
`state  ExpandKey state, , salt 
`state  ExpandKey state, , key
`return state
`
`Figure : Eksblowsh, expensive key schedule blow-
`sh, is a cost parameterizable and salted variation
`of the blowsh block cipher.
`
`Eksblowsh encrypts identically to Blowsh. The
`two dier in the functions they use to transform en-
`cryption keys into subkeys and S-boxes. Figure 
`sketches EksBlowshSetup, the algorithm used by
`eksblowsh. EksBlowshSetup has three input pa-
`rameters: a cost, a salt, and the encryption key. It
`returns a set of subkeys and S-boxes, also known as
`a key schedule.
`
`Figure : Blowsh Feistel network with F being the
`Feistel function, using only modular addition and
`XOR.
`
`into two -bit halves, L and R. The most-
`signicant half, L, is XORed with subkey P, and
`used as input for a function F . The result of that
`function is XORed with the least-signicant half,
`R. The two halves are then swapped, and the
`whole process repeated another  times for a to-
`tal of  iterations. Thus, for  i  , letting 
`denote XOR:
`
`The cost parameter controls how expensive the key
`schedule is to compute. The salt is a -bit value
`that modies the key schedule so that the same key
`need not always produce the same result, as moti-
`vated by Section . Finally, the key argument is a
`secret encryption key, which can be a user-chosen
`password of up to  bytes including a terminating
`zero byte when the key is an ASCII string.
`
`Ri = Li(cid:0)  Pi;
`Li = Ri(cid:0)  F Ri:
`
`After  rounds, the two halves are swapped again
`undoing the eect of the th swap, and each half
`is XORed with another -bit subkey:
`
`R  = L   P ;
`L  = R   P :
`
`This process is illustrated graphically in Figure .
`
`The function F in Blowsh uses four arrays,
`S ; : : : ; S, derived from the encryption key. Each
`array contains  -bit words. The arrays act
`as substitution boxes or S-boxes, replacing an -bit
`input with a -bit output. F splits its -bit in-
`put into four -bit bytes, a, b, c, and d, with a the
`most signicant byte. It replaces each byte by the
`contents of an S-box, and combines the results as
`follows: Letting signify addition modulo  :
`F a; b; c; d = (cid:0)S a Sb  S c Sd:
`
`EksBlowshSetup begins by calling InitState, a func-
`tion that copies the digits of the number  rst into
`the subkeys, then into the S-boxes.
`
`ExpandKeystate, salt, key modies the P-Array
`and S-boxes based on the value of the -bit salt
`and the variable length key. First it XORs all the
`subkeys in the P-array with the encryption key. The
`rst  bits of the key are XORed with P , the next
`  bits with P, and so on. The key is viewed as
`being cyclic; when the process reaches the end of
`the key, it starts reusing bits from the beginning to
`XOR with subkeys.
`
`Subsequently, ExpandKey blowsh-encrypts the
`rst  bits of its salt argument using the current
`state of the key schedule. The resulting ciphertext
`replaces subkeys P and P. That same ciphertext is
`also XORed with the second -bits of salt, and the
`result encrypted with the new state of the key sched-
`ule. The output of the second encryption replaces
`
`Page 7 of 13
`
`

`

`subkeys P and P. It is also XORed with the rst
`-bits of salt and encrypted to replace P and P.
`The process continues, alternating between the rst
`and second  bits salt. When ExpandKey nishes
`replacing entries in the P-Array, it continues on re-
`placing S-box entries two at a time. After replacing
`the last two entries of the last S-box, S and
`S, ExpandKey returns the new key schedule.
`
`In computing ExpandKeystate, , key, a block of
`  bits is used instead of the salt. This is equiv-
`alent to a single iteration of the standard blowsh
`key schedule. The call to ExpandKeystate, , salt
`simply treats the salt as a -byte key.
`
`After calling InitState to ll a new key schedule with
`the digits of , EksBlowshSetup calls ExpandKey
`with the salt and key. This ensures that all sub-
`sequent state depends on both, and that no part
`of the algorithm can be precomputed without both
`salt and key. Thereafter, ExpandKey is alternately
`called with the salt and then key for cost iterations.
`For all but the rst invocation of ExpandKey, the
`second argument is a block of  bits. This more
`closely resembles the original blowsh key schedule,
`and also allows EksBlowshSetup to be implemented
`more eciently on CPU architectures with few reg-
`isters.
`
`We hope that the unpredictable and changing con-
`tent of the P-array and S-Boxes will reduce the ap-
`plicability of yet unknown optimizations. Addition-
`ally the eksblowsh S-Boxes require  KB of con-
`stantly accessed and modied memory. Thus, the
`S-Boxes cannot be shared across key schedules|
`separate S-Boxes must exist for every simultaneous
`execution. This vastly limits the usefulness of any
`attempts to pipeline the Feistel network in hard-
`ware.
`
` Bcrypt Algorithm
`
`The problems present in traditional UNIX pass-
`word hashes led naturally to a new password scheme
`which we call bcrypt, referring to the Blowsh en-
`cryption algorithm. Bcrypt uses a -bit salt and
`encrypts a -bit magic value. It takes advantage
`of the expensive key setup in eksblowsh.
`
`The bcrypt algorithm runs in two phases, sketched
`in Figure .
`In the rst phase, EksBlowshSetup
`is called with the cost, the salt, and the password,
`to initialize eksblowsh’s state. Most of bcrypt’s
`
`bcrypt cost, salt, pwd 
`state
`EksBlowshSetup cost, salt, key
`ctext
`OrpheanBeholderScryDoubt"
`repeat 
`ctext  EncryptECB state, ctext 
`return Concatenate cost, salt, ctext 
`
`Figure : The bcrypt algorithm for hashing UNIX
`passwords, based on eksblowsh.
`
`time is spent in the expensive key schedule. Follow-
`ing that, the -bit value OrpheanBeholderScry-
`Doubt" is encrypted  times using eksblowsh in
`ECB mode with the state from the previous phase.
`The output is the cost and -bit salt concatenated
`with the result of the encryption loop.
`
`In Section , we derived that an -secure pass-
`word function should fulll several important cri-
`teria: second preimage-resistance, a salt space large
`enough to defeat precomputation attacks, and an
`adaptable cost. We believe that Bcrypt achieves all
`three properties, and that it can be -secure with
`useful values of for years to come. Though we can-
`not formally prove bcrypt -secure, any aw would
`likely deal a serious blow to the well-studied blow-
`sh encryption algorithm.
`
`.
`
`Implementation
`
`We have implemented bcrypt and deployed it as part
`of the OpenBSD operating system. Bcrypt has been
`the default password scheme since OpenBSD . .
`
`An important requirement of any bcrypt implemen-
`tation is that it exploit the full -bit salt space.
`OpenBSD generates the -bit bcrypt salt from an
`arcfour arcrandom  key stream, seeded with
`random data the kernel collects from device timings.
`
`OpenBSD lets administrators select a password
`hashing scheme through a special conguration le,
`passwd.conf. passwd.conf allows detailed control
`over which type of password to use for a given user
`or group. It also permits dierent password schemes
`for local and YP passwords. For bcrypt, one can also
`specify the cost. This lets people adjust password
`verication time for increasing processor speed. At
`the time of publication, the default cost is  for a
`normal user and  for the superuser. Of course,
`
`Page 8 of 13
`
`

`

`whatever cost people choose should be reevaluated
`from time to time.
`
`To dierentiate between passwords hashed by dif-
`ferent algorithms, every password function other
`than the original crypt prexes its output with a
`version identier. Thus a single password le can
`contain several types of password.
`In the cur-
`rent OpenBSD implementation, bcrypt passwords
`start with $a$", while MD crypt passwords with
`$ $." Because the result of traditional crypt never
`begins with a $", there is never any ambiguity.
`
` Bcrypt Evaluation
`
`Because bcrypt has adjustable cost, we cannot
`meaningfully evaluate the performance of the algo-
`rithm on its own. Instead, we will place it in the
`context of two popular password hashing functions.
`We describe various attacks and optimizations these
`functions have undergone, and discuss the applica-
`bility of the same techniques to bcrypt.
`
`. Comparison
`
`In the following, we give a brief overview of two
`password hashing functions in widespread use today,
`and state their main dierences from bcrypt.
`
`. . Traditional crypt
`
`Traditional crypt ’s design rationale dates back to
`   . It uses a password of up to eight characters
`as a key for DES  . The -bit DES key is formed
`by combining the low-order  bits of each character
`in the password. If the password is shorter than 
`characters, it is padded with zero bits on the right.
`
`A -bit salt is used to perturb the DES algorithm,
`so that the same password plaintext can produce
`,  possible password encryptions. A modica-
`tion to the DES algorithm, swapping bits i and i+
`in the DES E-Box output when bit i is set i