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 <frantz@netcom.com> 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.