Re: Why triple encryption instead of split+encrypt?

[John Douceur <johndo@microsoft.com>]

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