Date: Mon, 3 May 1999 18:24:40 -0400 (EDT) From: David Mazieres <dm@reeducation-labor.lcs.mit.edu> To: adam@homeport.org Cc: andrewr@slack.net, phk@critter.freebsd.dk, peter.jeremy@auss2.alcatel.com.au, freebsd-security@FreeBSD.ORG, provos@openbsd.org Subject: Re: Blowfish/Twofish Message-ID: <199905032224.SAA12518@reeducation-labor.lcs.mit.edu> In-Reply-To: <19990503155204.A28374@weathership.homeport.org> (message from Adam Shostack on Mon, 3 May 1999 15:52:05 -0400) References: <199905031554.LAA09846@reeducation-labor.lcs.mit.edu> <Pine.NEB.3.96.990503152350.29864A-100000@brooklyn.slack.net> <19990503155204.A28374@weathership.homeport.org>
next in thread | previous in thread | raw e-mail | index | archive | help
Well, I've browsed the freebsd website mailing list archives a little bit, and would like to respond to several points that have come up in discussion. If you read our paper (ftp://cag.lcs.mit.edu/pub/dm/papers/provos:bcrypt.ps.gz), keep in mind that we are making two points: First, we suggest a specific set of criteria that any password function should aspire to. Second, we suggest a particular algorithm, namely bcrypt, that we conjecture satisfies these properties. I like bcrypt because it seems to achieve all the important properties of a password function while being very conservatively based on a well-analyzed block cipher. Of course, I'm sure other people can design equally good hashing functions. While I would like to see more operating systems adopt bcrypt, I'm not going to defend bcrypt against largely non-technical objections. To the extent that people are missing some of the important motivating factors behind bcrypt's design, however, I will respond to certain objections in the hopes of helping people contemplating designing yet another password system (whether based on twofish or SRP). Points people have made: * Bcrypt is export restricted I can't offer legal advice on this point. However, since FreeBSD already distributes arc4random, it should be easy to create an implementation of bcrypt that can no more easily be used for encryption. Such an implementation would presumably be exportable. * People shouldn't use block ciphers as hash functions * The security of a password hash based on a a block cipher is suboptimal. * The performance of a password hash based on a a block cipher is suboptimal. One of the most basic requirements of any block cipher is that it resist known plaintext attacks. In other words, if an attacker knows a message M and an ecryption E_k(M), he should have no way of recovering the encryption key k (other than by brute force guessing). In practice, block ciphers must resist more powerful attacks--for instance, a "chosen plaintext/ciphertext" attack in which the bad guy gets to evaluate the encryption/decryption function on arbitrary values in his effort to recover k. In the case of bcrypt, we are only relying on Blowfish's resistance to known plaintext attacks. Thus, bcrypt has a cryptographically sound design based on the very reasonable assumption that Blowfish resists known plaintext attacks. There are several other reasons one might not want to use a block cipher as a hash function, but none of them apply to bcrypt. One reason is that the domain of a hash function might be larger than the key space (e.g. MD5 has an input size of up to 2^64 bits, while bcrypt only allows 448 bits). This is irrelevant for password hashing, since above a certain length of password you only care about 2nd preimage resistance. Bcrypt has better 2nd preimage resistance than MD5 and SHA-1 because of its larger output size. Another reason to use hash functions is efficiency. Certainly bcrypt is too slow to be used as a general-purpose hash function. However, we specifically designed it to be slow. Given bcrypt's application, the real performance issue is making sure that the algorithm runs as efficiently as possible during legitimate. That way users can crank the cost and make off-line guessing attacks more expensive. Bcrypt achieves this because it only uses operations that are fast in software One of the reasons I chose to use blowfish is that it consumes a fair amount of space (4KB). This makes it harder to create a pipelined hardware implementation of bcrypt. None of the popular hash functions (e.g. MD5, SHA-1, tiger) have this property, because they are all designed to run fast in different settings. Since, absolute speed was not a goal of bcrypt, blowfish seemed like an attractive algorithm to use as a base. * Don't use the number pi to encrypt I'm not sure I entirely understand this objection. In order to frustrate hardware implementations of a hashing function based on a block cipher, it seems very desirable to choose a cipher with "secret" S-boxes--that is S-boxes that depend on the encryption key. It's even better if you can repeatedly run the key schedule to keep modifying the S-boxes based on their previous state. That way, you end up with a large amount of memory that must constantly be accessed and modified during the key schedule (which is the expensive part of bcrypt), and with an algorithm that exhibits little parallelism. The point of initially filling the S-boxes with the digits of pi is that Bruce Shneier did not invent the digits of pi. Thus, one can reasonably believe that he did not maliciously construct the initial S-boxes to weaken the cipher in some secret way. Better yet, because the digits of pi are essentially unrelated to the rest of the block cipher, we can make a reasonable argument that spinning the key schedule multiple times does not weaken the encryption algorithm. If, for instance, blowfish's initial S-boxes were specifically designed to resist linear cryptanalysis [I'm not sure why you would do this, since the initial S-boxes aren't the eventual ones], then spinning the key schedule a second time might actually weken security. Here, however, we can claim that the "generalized blowfish problem" in which the initial S-boxes are random is probably as hard as breaking regular blowfish, and the multiple key schedule blowfish problem is probably as hard as the generalized one. * Who cares? We should all be running SRP anyway. SRP is a nice protocol, but its use is somewhat orthogonal to bcrypt. The point of bcrypt is to avoid password guessing when the SRP server is compromised. In a research project I am currently working on, we use SRP in conjunction with eksblowfish (the algorithm bcrypt is based on). We use eksblowfish to hash together the salt, password, SRP modulus, and hostname of the server, and use the result as the user's secret exponent (i.e. the discrete log of the verifier stored by the server). This makes an off-line guessing attack against a compromised SRP database very expensive. An alternative approach would be to use a fast hash function but choose a much larger prime as the SRP modulus. This would increase the cost of exponentiation when comparing hashes of password guesses to a user's verifier. However, it would also unnecessarily cost the server CPU time during execution of the algorithm and increase the size of messages across the wire. Since there are also good optimizations one can perform to speed up multiple exponentiations of the same base, an attacker may still be to achieve a reasonable speedup compared to a legitimate execution of the protocol (depending on the implementation). A better approach is just to have the client perform a more expensive hash of the password. So even if you use SRP, you should still use a variable-cost hash function on passwords before feeding them into the SRP algorithm. David To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-security" in the body of the message
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?199905032224.SAA12518>