From daw@cs.berkeley.edu Sat Dec 7 11:30:24 PST 1996
Article: 1658 of isaac.lists.coderpunks
Path: news.isaac.cs.berkeley.edu!not-for-mail
From: daw@cs.berkeley.edu (David Wagner)
Newsgroups: isaac.lists.coderpunks
Subject: Re: Composing block cyphers for larger block sizes
Date: 6 Dec 1996 16:20:30 -0800
Organization: ISAAC Group, UC Berkeley
Lines: 50
Sender: daemon@abraham.cs.berkeley.edu
Approved: mail2news@news.isaac.cs.berkeley.edu
Distribution: isaac
Message-ID: <58ab3o$9ou@joseph.cs.berkeley.edu>
References: <199612062211.OAA12770@netcom7.netcom.com>
NNTP-Posting-Host: abraham.cs.berkeley.edu
Precedence: bulk
In article <199612062211.OAA12770@netcom7.netcom.com>,
Bill Frantz wrote:
> At 12:04 PM 11/28/96 -0500, Bruce Schneier wrote:
> HexaDES [...] is basically a doubling of triple
> DES with bit mixing between the rounds:
>
> 128 bits
> 64 | 64
> ---------------------------------
> | |
> Round 1: des(E,K1) des(E,K2)
> 32 | 32 32 | 32
> --------------------------------------------------------
> | | |
> Round 2: 1/2 des(E,K3) des(E,K4) 1/2 des(E,K3)
>
>
>
> Round 2: des(E,K3) des(E,K4)
> 32 | 32 32 | 32
> --------------------------------------------------------
> | | |
> Round 3: 1/2 des(E,K5) des(E,K6) 1/2 des(E,K5)
> | | |
>
>
> Round 3: des(E,K5) des(E,K6)
> | 64 64 |
> ---------------------------------
> |
> 128 bits
>
>
> I know of no analysis of either of these algorithms.
Well, I haven't examined it carefully, but after a first glance, I see
an attack that needs 2^16 chosen plaintexts and 2^72 offline trial decrypts.
Choose your plaintexts to be of the form A_i || B, where B is a fixed
64-bit block and A_i is random & different for each plaintext. We say
that two plaintexts form a match if the two inputs to the des(E,K4) box
are equal; this happens with probability 2^{-32} (since half the input
is guaranteed to match). Obtain the corresponding ciphertexts; for any
guess at K5, you decrypt all the 2^16 ciphertexts up through the des(E,K5)
box. A match should occur somewhere with high probability, by the
birthday paradox; you can recognize a match because half of the input to
the des(E,K5) will match in the two decrypted ciphertexts.
So I think HexaDES is not very much better than single DES; I would tend
to want something stronger, I think.