In the early days of Unix, the DES-based algorithm used to encrypt
(actually, to generate hashes from) passwords was considered to be quite
secure. Hashing a password took a significant fraction of a second, so
brute-force attacks were considered impractical. The possibility of
attacks using hardware-based DES engines was closed off by the addition of
a "salt" parameter which perturbed the algorithm slightly. All in all, the
authors felt pretty good about their work, to the
point that the encrypted passwords were stored in a world-readable file and
nobody worried about it.
Along came faster processors and smarter software. Simple passwords became
easy to crack with the right software (which was widely available), and the
harder passwords looked less hard all the time. So a few changes were
made, including moving the password hashes to a read-protected file and
changing to the MD5 hashing algorithm. Everything looked better for a
while. But along came faster processors and smarter software, and now MD5
passwords look rather less secure than they once did.
The attentive reader might notice a pattern here. Hashing algorithms
must be sufficiently expensive to compute that they are not susceptible to
brute-force attacks. But they cannot be so expensive that the user
community rebels. So the designers of a password hashing algorithm must
find a compromise between security from attackers and security from
aggravated users. As computers inevitably become more powerful, that
compromise must shift in favor of the attackers.
A solution to this problem was presented by Niels Provos and David Mazières
in a 1999
USENIX paper. Their conclusion was that, in order to have a
future-proof password hashing algorithm, one must be able to dial up the
computational cost of that algorithm over time. If the cost can be
provided as a parameter - and stored with the hashed password - then
password hashing can be made more expensive (in terms of CPU cycles) while
maintaining compatibility with currently-hashed passwords.
The authors implemented a version of the Blowfish algorithm with
a tweak to the key schedule generation mechanism. That code has a "cost"
parameter which controls how expensive the generation step is; a higher
cost will result in a longer key schedule generation task. Needless to
say, code checking a password must use the same cost as the code which
initially generated the hash, or the results will not match.
OpenBSD has used the variable-cost Blowfish code (called "bcrypt") for some
years now, but it is still relatively difficult to find on Linux systems.
Perhaps that will change with the release of crypt_blowfish 1.0, just announced by Solar
Designer. This release, being "the first mature version," comes with a
password-hashing interface and a PAM module for hooking it into Linux
systems. It should, thus, be relatively easy for distributors to add to
their configurations, as an option, at least. Making the front door to
Linux systems a little more secure has just gotten easier.
(For more information, see the
crypt_blowfish web page).
to post comments)