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.
Agreed so far.
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.
Yeah. You're right. Make a table of the backwards DES, then match against that when attacking the spliting part of the algorithm. I don't know how I missed that.
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.
Agreed (although I'll point out that my splitting algorithm IS dependent on both keys/) If I want a fast hash based symetric cipher, I'll use MDC or Luby-Rackoff. *sigh* JWS