Weekly Edition
Return to the Security page
| |||||||||||||
crypt_blowfish
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
early crypt() 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). (Log in to post comments)
crypt_blowfish Posted Feb 9, 2006 8:56 UTC (Thu) by anselm (subscriber, #2796) [Link] Minor nit: The »salt« parameter to crypt() isn't used to foil hardware-based attempts to crack the encryption, but to introduce variation in the results. Without the salt, if users A and B by chance selected the same password, user A could notice in /etc/passwd that her encrypted password was the same as B's, and log in as B (remember that shadow passwords hadn't been invented yet). With the salt, every plain-text password is hashed to one of 4096 possible encrypted forms, with the chances of a collision being that much lower. The second benefit is that, for an attack based on a dictionary of pre-encrypted passwords, the dictionary must be 4096 times larger, which is significant if your machine is a PDP-11 with the amount of disk space usual in the late 70s/early 80s. The hardware-based cracking engine problem was addressed by modifying the actual algorithm used by crypt() enough for it to be quite like DES but different enough from what the DES chips implement, so that coming up with a crypt() cracker was no longer economically viable owing to the custom chips required. Anselm
crypt_blowfish Posted Feb 9, 2006 10:32 UTC (Thu) by kleptog (subscriber, #1183) [Link] One issue is ofcourse that if someone cracks the *algorithm* then it doesn't matter how difficult you make it, you're screwed.
Still, I'm not too knowledgable about this. I'm not sure if attacks on an algorithm at 32 rounds makes it a lot easier to attack the 64 round version. Also, I'm not sure if it is provable that n+1 rounds is always harder than n rounds and that there no mysterious number k where the cracking becomes trivial...
Is there much research in this direction of algorithm strengthening?
crypt_blowfish Posted Feb 9, 2006 21:46 UTC (Thu) by kamil (subscriber, #3802) [Link] I think you have a point.
Adding to what you wrote, we should not forget that the primary problem in real world are weak passwords, not weak algorithms.
Elaborating, with ever faster computers, ever more passwords have to be considered weak. So stronger algorithms are fine, but I believe that they have to be coupled with stronger passwords to give you real security boost. A chain is as strong as its weakest link...
This brings next problem: most people have difficulties remembering long passwords of semi-random characters (and these are the most secure). So we must face the fact that strong, i.e. long, passwords are not going to happen, if people need to memorize them.
Finally, if the password length remains limited, then password cracking becomes not that much a computational problem, as a storage problem. All you need to do is to generate a hashed version of every possible 8-letter combination and store it, sorted by hash. This problem parallelizes perfectly, so the algorithm complexity is not that relevant. After all, you only need to create the database once. And guess what? Storage capacity increases faster than CPU speed...
What saves us to an extent is "salt". With DES-like passwords, salt was a 10 or 12-bit (I don't quite remember) random value, used to artificially extend the password. I'm guessing that these new algorithms use a much longer salt, so that the disk capacity required for a complete database remains impractical. Now the question is: to what extend are current cryptographic algorithms analysed for a case where some/most bits of the key are known? (you need to store the salt in plain text along with the hash in the password file).
crypt_blowfish Posted Feb 11, 2006 11:38 UTC (Sat) by fergal (subscriber, #602) [Link] If you increase the salt or even throw in a per-machine salt then generating and keeping the database becomes impractical and pointless.
crypt_blowfish Posted Feb 18, 2006 2:33 UTC (Sat) by mikew (guest, #27697) [Link] I thought blowfish was available to Linux PAM systems for at least a few years now through pam_unix2. I've never used SuSE, but the guy who wrote this worked for SuSE, so I'm guessing it was used in SuSE. I've used it on my own system, at the very least.
crypt_blowfish Posted Feb 18, 2006 15:54 UTC (Sat) by solardiz (guest, #35993) [Link] Actually, SuSE has crypt_blowfish (precisely the implementation that this news item talks about) integrated into glibc - and that's what pam_unix2 uses.
Yes, this has been around for a few years. crypt_blowfish 0.x has been around for over 5 years - but I declared it "mature" and released as 1.0 just recently.
As the crypt_blowfish homepage says:
"crypt_blowfish is fully integrated into Owl and distributions by ALT Linux team, as the default password hashing scheme. It is a part of the glibc package on ASPLinux and SuSE Linux.
Additionally, crypt_blowfish is used in the PHP Hardening-Patch, in PostgreSQL's contrib/pgcrypto providing bcrypt support for crypt() and gen_salt() SQL functions, and in CommuniGate Pro messaging server starting with version 4.1 ..."
|
|||||||||||||