Other Directory Sites: SeekWonder | Directory Owners Forum
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:17:38
Cicero (cicero@redneck.efga.org)
26 Dec 1998 08:00:21 -0000
Michael Motyka <mmotyka@lsil.com> wrote:
>Jim,
>
>Since you're addressing "this thread" today, here's more. This is an
>idea of mine that's somewhat related to the cascade question. It's very
>simple to code; my version of a block cipher cascade.
>
>Choose a block cipher, block 2^(m+n) bits, key K bits
>Make a 2^m x 2^m data array with elements size 2^n bits
>Use a different key for each of the 3 * 2^m block cipher iterations
> Encrypt 2^m rows
> Encrypt 2^m columns
> Encrypt 2^m rows
>Done
>
>Block size = 2^(m+m+n)
>Key size = 3 * 2^m * K
>
>A real-life example -
>DES 2^6 bits, m = 3, n = 3 ==> 8 x 8 array of bytes
>Block size = 512 bits - perfect for disk sectors
>Key size = 1344 bits - more than plenty
>
>At the extreme you could ( especially in HW ) make n = 0.
>Block size = 4096 bits
>Key size = 10752 bits
>
>3DES is the m = 0 case.
>
>Speed should be comparable to 3DES. Roughly, anyway.
>
>It's easy to generalize it to multiple dimensions - to what end I'm not
>sure. It's also easy to think of things you might do to data as it winds
>its way through, like array element rotations and row or column rotates,
>shuffles or swaps. Again, unnecessary? You could repeat more times to
>grow the key: -|-|-. You could do diagonals: -\|/- , instead of: -|- to
>improve(?) the mixing. Yada yada yada...
>
>Intuitively it looks like a reasonable way to expand an existing block
>cipher: the block is large, the key is large and a single bit change in
>the input is nicely avalanched to the output array. It looks stronger
>than a simple cascade. Maybe you could even expand the expanded cipher.
>Or start with a very small, more easily-studied cipher and iterate the
>expansion to the desired size...
>
>I don't know if these are relevant or if there are easy answers to these
>but, what the hell.
>
>My questions are :
>
>Where are the problems?
>How many of the key bits are unwarranted?
>Are useful properties of the base cipher true of the expanded cipher?
>Can an expansion be iterated with any useful results?
>
>Regards,
>Mike
>
Mike,
You've asked a lot of questions about a rather general construction.
I think I can point out a shortcoming of a specific instance.
As you point out, n=0 is 3DES. Let's look at the construction for
m=0, n=3, K=56, and the cipher is DES. I believe that I have an
attack for that case with work factor a small multiple of 2^56.
This generalises to a small multiple of 2^K for any block cipher.
As you say:
>At the extreme you could ( especially in HW ) make n = 0.
>Block size = 4096 bits
>Key size = 10752 bits
...
>Speed should be comparable to 3DES. Roughly, anyway.
You will be doing 3 * 64 key schedulings for the 10752 bits of key,
instead of 3 key schedulings for 3DES. This will slow things down
considerably below the 3DES speed baseline. So you might consider
using one key for the initial encryption of the rows, then a second
key to encrypt the columns, and finally a third key for the last
encryption of the rows.
Let P be a known plaintext of 4096 bits, and P' a chosen plaintext
which differs from P in a single bit. Arrange P and P' in 64 rows and
columns, so it is a 64 x 64 matrix of bits. When we encrypt P and P',
the results agree on all rows except for the row in which the bit has
been flipped. In that row of 64 bits, the expected number of changed
bits is 32. For half of the choices of P, the number of bits will be
32 or less. Assume P has this property. When we subsequently encrypt
the columns, 32 or more of the columns will agree (those columns whose
intersection with that row was in a bit that did not change).
This is the structure we will look for.
Let C and C' be the respective triple encryptions of P and P' under
your construction. Compute 2^56 DES decryptions of the rows of each
of C and C'. Note that the decryption under the 3'd of the original
DES keys will will result in blocks that have the structure described
above. We need a lemma that shows this is an otherwise unlikely
result. It's late, so I'll work on that tomorrow... If you grant the
lemma, we have peeled off the last key. The second key is easier, and
the first is straightforward brute force.
Gaudete Saturnalia.
Cicero
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:17:38