-----BEGIN PGP SIGNED MESSAGE-----
From: <solman@MIT.EDU> Date: Tuesday, July 19, 1994 2:31PM
You are then quite correct that meet-in-the-middle attacks can be done, but the key to the first encryption (the hashing multiplex) is 112 bits (for the split into two parts version) which would require 2^112 stored messages, substantially more than could possibly be stored by anybody ever (well, I guess ever is a bad word to use in this context).
There are two separate operations here. One is splitting the plaintext: P0, P1 = S_KS(P) The other is generation of the splitting key. I assume independent generation of the splitting key both because it maximizes the total keyspace and because it avoids the confusion that I believe is evidenced by the above quoted paragraph. To wit: You have suggested generating the split key with a one-way hash of the DES keys: KS = hash(concat(K0,K1)) If the concatenation of the DES keys is 112 bits, then there are 2^112 possible values of the concatenation. However, the hashing of this value is not the first of the two encryptions; the splitting of the plaintext is the first encryption, and the hash is merely a mechanism for generating the splitting key. The domain of KS is the determinant of the size of the intermediate memory in a brute-force meet-in-the-middle attack. Furthermore, even for an independently generated splitting key, if the size of the domain of KS is greater than the size of the domain of K0 or K1, then the DES-decrypted values can be stored as the intertext, requiring no more memory than that required for decrypting double DES.
I still believe that the security of the scheme, even when just splitting into two parts and using the hash of the keys to multiplex the split, is much worse (by more than a couple of factors of two) than DES.
I suspect that you mean better, not worse [smiley deleted by censor]. I do not contest this claim, but I consider a more pertinent metric to be the security of this scheme relative to that of double DES. One decomposite of the split+encrypt algorithm can be viewed as: C = E_K0(S0_KS(P)) And an analogous double DES encryption is: C = E_K0(E_K1(first_half(P))) For the sake of argument, I'll assume that the domains of KS and K1 are equal in size. Thus, a brute-force meet-in-the-middle attack will require the same number of encryptions and the same amount of memory in both cases, although the amount of computational power required will be somewhat less in the case of split+encrypt because the splitting is less computationally intensive than DES. However, the splitting algorithm is relatively simple, far more so than DES. It is unlikely that a brute-force approach is necessary to cryptanalyze the splitter. For example, consider the following splitting algorithm: p0[i] = (p[i+1] & ~key) | (p[i] & key); p1[i] = (p[i+1] & key) | (p[i] & ~key); This is particularly simple, and I chose it to be so for simplicity of discussion. Imagine that our cryptanalytic algorithm begins as follows: Decrypt first block of ciphertext with each possible DES key; check to see if the resulting intertext could possibly have come from first block of known plaintext; if so, store the key; continue. Without looping through all possible split keys, we can determine whether the intertext could have come from the plaintext: precompute: bits_in_common = ~(p[0] ^ p[1]); // ^ = XOR must_be_1 = bits_in_common & p[0]; must_be_0 = bits_in_common & ~p[0]; inside loop: if (test_block & must_be_0 | ~test_block & must_be_1) test_block could not be from plaintext This greatly shortens the amount of memory required for the search, making the algorithm much less secure than double DES. You may respond by suggesting improvements to the splitting algorithm, such as multiple-bit dependency; but there are doubtless other weaknesses that could be exploited. I did not spend a lot of time on the above technique; persons more qualified than I am, devoting serious time to the problem, will certainly develop better cryptanylitic attacks. I think you will be very hard pressed to develop an algorithm anywhere near as secure as DES. JD -----BEGIN PGP SIGNATURE----- Version: 2.6 iQCVAgUBLixRSUGHwsdH+oN9AQE4QgP8CMTmnk0It9Y4qWK08j9jLWCEYn2gLrEr +b17avqtVE/ArvLh3g6wHLQ4bMU0UOuLyNI0abk19FM7agqYT3WLo+U36DvU4qDJ 9lsyyUfqHgYrXOMGAPG/Kzg4ixqo+9IiCvnFxMbsniPnlCT5l5UuEOBLlAPqyrNQ ggvcxZ4a4rU= =gPdN -----END PGP SIGNATURE-----