-----BEGIN PGP SIGNED MESSAGE-----
From: <solman@MIT.EDU> Date: Friday, July 15, 1994 2:45AM
Although I mentioned "true" secret splitting at the end of my post, I was refering to non-redundant secret splitting in most of the post. That is, for each 128 bit block, you split it into two 64 bit blocks. Obviously you have to make sure that in the inverse of the split, each bit of the 128 is dependent on multiple bits in both 64 bit parts.
I read this as something like the following: int munge[16] = {0x0, 0xE, 0xD, 0x3, 0xB, 0x5, 0x6, 0x8, 0x7, 0x9, 0xA, 0x4, 0xC, 0x2, 0x1, 0xF}; for (int i = 0; i < num_blocks/2; i++) { unsigned int s0 = source[2*i], s1 = source[2*i+1]; unsigned int d0 = 0, d1 = 0; for (int j = 0; j < 8; j++) // 32-bit ints assumed { d0 |= munge[(s0>>(4*j)) & 0xF] << (4*j); d1 |= munge[(s1>>(4*j)) & 0xF] << (4*j); } dest0[i] = (d1 & 0xAAAAAAAA) | (d0 & 0x55555555); dest1[i] = (d1 & 0x55555555) | (d0 & 0xAAAAAAAA); } This fragment splits alternating bits from each contiguous pair of 64-bit blocks in the source[] array into two blocks, each of which is placed into one of the two dest[] arrays. The inner loop first makes each bit in the pre-split data dependent on the three other bits in the same nibble. Is this consistent with your suggestion?
This is obviously not as secure as traditional secret splitting, but you don't need it to be because this isn't a threshold scheme. You just need to guarantee that knowing one half does not allow you to reassemble the other half.
I believe these claims hold true for the above code.
I am claiming that you can allow the crypt analyst to remove half of the entropy from the plaintext (did I phrase that right? probably not :( ) and the other half will still require successful cryptanalysis of DES and since you can't tell if you're right until you get both halves, meet in the middle does not work.
Yes and no. Meet-in-the-middle does not work, per se, or more precisely has no applicability. Recall that meet-in-the-middle is a method of extending a known-plaintext attack on a single encryption to multiple encryptions by means of an enormous amount of memory to hold intermediate results. In the split+encrypt proposal (as I have implemented it above), a known-plaintext attack can be applied directly, with only twice as much computation as that needed for a single encryption, and no need for large amounts of memory. The cryptanalytic approach is simple: 1) Split the known plaintext, P, with the splitting algorithm, into P0 and P1. 2) Apply known-plaintext attack to P0 and C0 to determine key K0. 3) Apply known-plaintext attack to P1 and C1 to determine key K1.
So, is a secret splitting algorithm that does NOT increase redundancy followed by DES with different keys on both halves as secure as triple DES?
No. It is not even as secure as double DES, since cryptanalysis of the former has the same computational complexity as the latter, but without the extreme memory requirements of meet-in-the-middle.
I believe so, but I would like your opinions on the issue before I consider implementing this.
MHO.
If it works it would be especially nice because it allows arbitrary extension of keysize without substantially increasing the time required for computation.
A noble goal. It would also have allowed multi-threaded crypto code on multiprocessor machines to perform the separate encryptions in parallel.
I have a hunch that if I'm wrong, its because the time required to do secure non-redundant secret splitting is as large as the time I'm saving.
JWS
JD -----BEGIN PGP SIGNATURE----- Version: 2.6 iQCVAgUBLirAX0GHwsdH+oN9AQH9uQQAswJhWwuB57y/V2ETz0epmFCKqk9JAwLC WWF9P5sNoOIHDK0soACURcvRCAWnUMJnXspbQ+0B2nQa7aWFLgD9lbm9obvbZREP 9q1dAqjK1yKxu1qxunk3wsdc7tyDMJzdOwGnpUOR1Gs7hqDOtVbs3wG9napzBY4h 2ndBT/BtJec= =QDW9 -----END PGP SIGNATURE-----