Re: Why triple encryption instead of split+encrypt?

-----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-----

> 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.

Clearly, if you have access to P0, P1; C0 and C1 this attack crushes the
algorithm. In most books I've seen, it is assumed that you do not have
access to this. For example, it is not considered a liability that somebody
hacking a DES encrypted message after 8 rounds could have a _relatively_
easy time hacking it.

Nonetheless, your cryptanalytic algorithm makes clear an additional
constraints that must be placed on the system which I had not realized:

From the algorithm, the plaintext, and the cypher text, in must not be
possible to reconstruct both the plaintext, and the cyphertext for either
half of the message.

To that end I would suggest the improvement of making the splitting
operation dependent on the keys.

One of many possible implementations: Do a simple splitting operation
like the one johndo suggested. Concatenate the two halves. Then hash
the concatenation of the two keys. Concatenate the negation of the hash
to the hash. Then multiplex the bits of the message to message #0 and
message #1 based on the bits in the resultant string of bits, repeating
the string until all the message bits are allocated. This prevents them
from splitting the problem in two thus, I believe, requiring the full
attack, giving arbitrarilly strong protection based on your favorite
fully analyzed encryption algorithm while only minimally decreasing speed
versus the single encryption (20-30%) and maintaining the same size. Am
I wrong?