-----BEGIN PGP SIGNED MESSAGE----- [ To: Cypherpunks, sci.crypt ## Date: 02/09/96 01:44 am ## Subject: RC2's key schedule and passphrase hashing ] Summary: Don't use RC2's key schedule to hash passphrases, with or without the export hack. Instead, hash the passphrase first, and then pass the result into RC2 to get expanded. (This is a good rule to follow with any cipher whose designers didn't specifically intend for it to be used to hash passphrases.) Don't use phase two at all--if you need exportable 40 bit security, generate a 128-bit random value, and leak 88 bits as salt. Hash the value, and use the result as the RC2 key.
Date: Fri, 02 Feb 1996 10:02:37 -0800 (PST) From: baldwin <baldwin@RSA.COM> (Robert W. Baldwin) Subject: RC2 technical questions
- How does the length of the key influence the mixing of bits during each pass of the expansion algorithm?
- If the first pass of expansion is viewed as a hash function that produces 40 or 128 bits out, what are its properties?
These are good questions, and they turn out to be pretty educational. I no longer can see any good reason for the effective-bits hack. Let me explain why, briefly: Suppose I'm hashing a 64-character passphrase, where each character has about three bits of actual entropy, for use in an export- controlled application. Clearly, this gives us plenty of entropy (192 bits) in the whole user key. How much entropy can make it to the last five bytes of expanded key? These last five bytes are a function of the last five bytes of user passphrase (total entropy of about 15 bits), and the previous byte of expanded key (which can't have more than eight bits of entropy). Those are the only inputs that aren't known to all attackers. This means that in this (very degenerate) case, we'd have 23 bits of entropy in our last 40 bits. If we then did phase two of the key expansion based on those 40 bits, we'd wind up with a total expanded key entropy of 23 bits. In short: Guess an 8 bit random number and the last five bytes of the user key, and you've got the entire expanded key. (Of course, if the application always padded the user passphrase with blanks or something to make it 64 bytes long, and then scheduled the key with the export control hack, we'd have *eight* bits of entropy in our expanded key, which probably qualifies for some kind of special thank-you note from Fort Meade or something.) Suppose I'm hashing a 32 character user passphrase. The same analysis applies to the bytes 60..63 of expanded key. Those bytes can have no more than 23 bits of entropy, if each character of the passphrase carries three bits of entropy. This means that bytes 92..95 carry at most 31 bits of entropy, and thus that bytes 124..127 carry at most 39 bits of entropy. If we pad the passphrase out on the right to 32 bytes before sending it into the RC2 key schedule, then we wind up with about 24 bits of entropy in the whole expanded key after phase two. Our assumptions about entropy in user passphrases can make this better or worse. For example, we may assume that it costs us 16 bits to guess the first three characters of any passphrase substring, and one bit per character after that. In that case, processing a 64-character passphrase into 40 effective key bits gives us 26 bits of entropy. If we assume that each additional character after the first three guessed costs us two bits, then processing a 64-character passphrase down to 40 bits gives us 28 bits of entropy, and processing it down to 56 bits gives us 32 bits. Without phase two, long user passphrases simply leave most of the expanded key fairly predictable, especially in the high couple of bits of each byte. I haven't tried to analyze yet what this does to RC2's security, but it's almost never a good idea to have highly-predictable bits anywhere in a cipher's expanded key. The moral of the story seems to be this: Don't use key schedules as passphrase hashing functions, unless they're specifically designed as such. In particular, don't use RC2's key schedule to hash your passphrase. Pass your passphrase (and salt) through a good one-way hash function like SHA1, and feed the result into your key schedule. Can anyone guess what the effective-bits parameter is used for? It doesn't seem to be secure for hashing passphrases, making some reasonable-sounding assumptions about actual entropy per character in user passphrases. I can't see an intelligent use for it. Note that setting effective bits to 40, we have only a 40-bit key--no salt. This means that using alleged-RC2 with phase two of the key schedule and effective bits set to 64 or less, we're potentially vulnerable to a precomputation attack. This is a real problem if we're doing something like encrypting a constant block at the beginning of the encryption, to verify that we have the right decryption key. (It's enough of a potential problem to be worrysome, anyway--note that almost all of my notes to John Smith start out with the same eight characters: "[ To: Jo". Precomputation attacks based on this are quite feasible.) I am very curious about how this is dealt with in practical implementations. The obvious way to do this would be to leave effective-bits = 1024, and just hash an 88-bit salt with a 40-bit session key to get the 128-bit key actually passed into RC2. But that begs the question: What's the use of having the effective-bits parameter? I certainly hope nobody is using RC2 with effective-bits set to 40 in any important, real-world applications.
--Bob
Note: Please respond via e-mail as well as or instead of posting, as I get CP-LITE instead of the whole list. --John Kelsey, jmkelsey@delphi.com / kelsey@counterpane.com PGP 2.6 fingerprint = 4FE2 F421 100F BB0A 03D1 FE06 A435 7E36 -----BEGIN PGP SIGNATURE----- Version: 2.6.2 iQCVAwUBMRsR1kHx57Ag8goBAQFzOAQAnjL06eTNMkqgT9OatMa2FRm2dFU7yffU lH3blWxV2Wv8XrMGTB3WTES6ME1D84qJMk641MNxAtH1PAigFzEFDeBHxDr83fR4 tJFECzQ0KWGUu3Pn9/sHJFhjOWUbg6AAtNQ94XN4kBx+NSb3rF/AtoEMyJr6azug FA5T+AQq+Jo= =Y7P+ -----END PGP SIGNATURE-----