Re: tripple des

[smb@research.att.com]

	 Crypto question:
	 why was the following chosen for tripple DES :
	    EN(DE(EN(data,k1),k2),k3);   

	 The encryption would involve passing data through IP,
	 then doing 16 rounds forward with k1,
	 (factoring out the IP-1 and IP)
	 then doing 16 rounds backwards with k2
	 (factoring out the next IP-1 and IP)
	 then doing 16 rounds forward with k3
	 then going through IP-1

	 How would this compare with
	    EN(EN(EN(data,k1),k2),k3);

	 which goes through IP,  does 16 rounds each with k1, k2 then
	 k3, then IP-1 ?

	 The only difference is that the key scheduler rotates backwards
	 (or another interpretation keys used in reverse order) for the
	 second stage.

	 Does anyone know the rationale behind this?

First, it's usually done as

	EN(DE(EN(data,k1),k2),k1)

The middle step is a decryption for two reasons, one of which is no
longer important for DES.  The reason that is still valid is that by
setting k1==k2, you have compatibility with other implementations that
only do single encryption.  (See the Garon and Outerbridge paper in
the July '91 Cryptologia for why you want to triple-encrypt keys...)

The second reason, no longer a concern for DES, is that it was feared
that DES might be a group.  That is, given

	E(E(data,k1),k2)

it was feared that there might be a third key kx equivalent to encryption
with k1 and k2.  It's recently been proved that DES is not a group.  That
is, in general there is no such kx.  Conceivably, the problem could arise
with other cryptosystems, such as Skipjack.  I haven't yet seen the proof
about DES, and I don't know how much might transfer to other DES-like
algorithms.  In any event, doing a decryption as the second operation
was thought to dodge the whole question.

Finally, even though triple encryption as I've defined it only has a key
length of 112, it's still necessary to do three operations, rather than
a simple double encryption; for the latter, there's a birthday attack
in O(2^56) time, though it does require O(2^56) space as well, making its
feasibility a bit dubious.


		--Steve Bellovin