john@hpcvlo.HP.COM (John Eaton) (10/23/87)
<<<<< I recently mentioned the use of multiple DES encryptions in order to get around the limitations of a 56 bit key length. Several people wrote to say that this won't work because encrypting with two keys would be equivalent to a single encryption with a third key. I dont think this is true for DES because of one simple reason. The number of possible DES encryptions is only a small subset of the total number of possible transformations. There are (2^64)factorial possible ways to transform a 8 byte group of numbers into another 8 byte group. The 2^56 ways that are equivalent to DES keys are only a small subset of possible transformations. If a crypto system has the number of keys equal to the total possible number of transformations then multiple encryptions would be useless but this is not the case with DES. Another characteristic of these systems is that they would have a "Null" key that would encrypt any input into itself. A possible way to prove this is simple. Take an 8 byte input and encrypt it with all 2^56 DES keys and make a list of the 2^56 results. Then take each of the results and encrypt each one with all of the 2^56 possible DES keys. If this second round of 2^112 encryptions ever produces a result that is not on your list from the first round then you have found a combination of two keys that can never be duplicated with a single key encryption. John Eaton !hplabs!hp-pcd!john
smb@ulysses.homer.nj.att.com (Steven Bellovin) (10/28/87)
Let me suggest that folks interested in multiple encryption consult "On the Security of Multiple Encryption", by Merkle and Hellman, in the July 1981 CACM. I won't run through their proofs; their conclusions are fairly simple. First, a doubly-encrypted text can be cracked by a ``meet-in-the-middle'' attack in o(2**56) operations, but at a cost of o(2**56) words of memory, using a known-plaintext attack. Second, triple encryption using three independent keys would require o(2**112) operations, and hence is immune to any brute-force scheme. A variant -- encrypting with K1, decrypting with K2, then re-encrypting with K1 -- requires the same effort and space as simple double encryption, but would require a chosen-plaintext attack. An interesting sidelight is that the meet-in-the-middle attacks will yield a number of false matches, about 2**48. Having 64 additional bits of known plaintext will reduce the error rate to 2**-16. They conclude that multiple encryption does offer advantages (enough 6250 bpi tapes to hold the 2**56 words of storage would cost ~$80e9 at $20 per tape, and hence is presumably beyond NSA's reach, especially since you have to sort the tpaes....). However, a 112 bit key would still be much stronger.
gwyn@brl-smoke.ARPA (Doug Gwyn ) (10/30/87)
In article <3123@ulysses.homer.nj.att.com> smb@ulysses.homer.nj.att.com (Steven Bellovin) writes: >They conclude that multiple encryption does offer advantages (enough >6250 bpi tapes to hold the 2**56 words of storage would cost ~$80e9 >at $20 per tape, and hence is presumably beyond NSA's reach, especially >since you have to sort the tpaes....). Hi, Steve! I hope you were being facetious. I doubt very much that NSA would have to resort to "brute force" key searches to crack DES or any system like it. If you really believe it would, I'd like to hear reasons why. So far in this type of discussion nobody ever has explained why "brute force" is the only approach considered. Obviously, if a system can be shown to be insecure against a "brute force" attack, it is absolutely insecure, but the converse definitely does not hold in general -- security against brute force does not guarantee absolute security.