Kent Borg wrote:

> I think the problem with 112-bit double-DES was not that it was weaker
> than single-DES, it was that it wasn't stronger.

Well, close. From Schneier's Applied Cryptography (2nd edition), page
348:

"When discussing an algorithm, the question of whether it is a group
arises. The elements of the group are the ciphertext blocks with each
possible key, and the group operation is composition. Looking at an
algorithm's group structure is an attempt to get a handle on just how much
extra scrambling happens under multiple encryption.

"The useful question is, however, not whether the algorithm is actually a
group, but just how close to a group it is. If it were only lacking one
element, it wouldn't be a group, but double encryption would be --
statistically speaking -- a waste of time. The work on DES showed that
DES is very far away from being a group."

And on page 358:

"If this is not the case [i.e. if the algorithm is not a group], the
resultant doubly-encrypted ciphertext block should be much harder to break
using an exhaustive search. Instead of 2**n attempts (where in is the bit
length of the key), it would require 2**2n attempts. ... This turns out
not to be true for a known plaintext attack. Merkle and Hellman developed
a time-memory trade-off that could break this double-encryption scheme in
2**(n+1) encryptions, not 2**2n. ... This attack is called a meet in the
middle attack."

Schneier describes the attack in detail, and then goes on to consider
triple encryption with two keys (DES-EDE2), noting that it is not
susceptible to the meet in the middle attack, but describing another
time-memory tradeoff attack, also discovered by Merkle and Hellman.

Finally, on page 360:

"If you are going to use triple encryption, I recommend three different
keys. The key length is longer, but key storage is not usually a
problem. Bits are cheap. ... The best time-memory trade-off attack takes
2**2n steps and requires 2n blocks of memory; it's a meet in the middle
attack. Triple encryption, with three independent keys, is as secure as
one might naively expect double encryption to be."

It is worth noting that the Merkle-Hellman attacks are chosen plaintext
attacks, that is, the cryptanalyst gets to choose what plaintext gets
encrypted. This will not frequently be the case in a VPN setting such as
we have apparently been discussing. If you cannot run the meet in the
middle attack, the effective key strength for double encryption goes back
to 2**2n and triple encryption (with three keys) back to 2**3n.

(Unless of course there are other attacks I'm not aware of, which is
certainly possible -- I'm not a cryptographer by any stretch of anyone's
imagination.)

Regards,
Donald McKillican
Bell Canada Corporate Security

• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]