Re: 3DES and super-encryption

From: Roger Fleming (roger_for_nntp_at_hotmail.com)
Date: 02/25/04 

Date: Thu, 26 Feb 2004 05:17:15 +1100

Chun wrote:

> Hello,
>
> I'm basically familiar with 3DES and how it was developed to extend the
> useful life of DES. In the circles I move in 3DES is considered very strong
> because of adequate key size (168 bits) and the fact that it has survived as
> long as it has without being broken. Everyone admits that 3DES is dog slow.

You should be aware that the security of 3DES isn't anything like as
great as is suggested by a 168 bit key. The most efficient known attacks
on 3DES are probably not actually practical quite yet but they are much
closer to practicality than the most efficient known attacks on, say,
IDEA or Blowfish (both of which have also been around for a fairly long
time).

All three of these algorithms also suffer from a 64 bit block; the
possibility of code book attacks means that they can no longer be
unreservedly recommended for all applications. In particular, for very
high throughput applications they all require very careful key management.

Thus it is debateable whether 3DES can still be considered the
conservative choice. Today I would only recommend 3DES for a new
application if:
1. You will only ever encrypt less than 100 MB of data with one key,
whether due to slow operation or diligent key management; AND
2. Your data does not need to remain secure for so long as 10 years; AND
3. The (relatively) low speed is acceptable; AND
4. You don't require standards compliance; AND
5. It would be absolutely infeasible to deploy an updated algorithm in
the event of a surprising new attack being discovered against your
chosen algorithm.

> The newer 256 bit ciphers are viewed with some suspicion because they
> haven't been around long enough for the flaws to surface. Here is the real
> short version of what I know (or think I know) about the transition from DES
> to 3DES. Then I'll get to my question.
>
> DES is basically a secure cipher except that with 56 bit keys it is
> vulnerable to a brute force attack. As far as I know brute force is still
> the only known attack against DES. So the designers of DES (IBM, I think)

No, this is not true. Real live linear cryptanalyses of DES have been
carried out, and are considerably faster than brute force. IIRC the
fastest so far broke a DES key in 12 hrs, using just *one* FPGA for
computation. Of course 3DES also provides strength against linear and
differential cryptanalysis, though.

> came up with a scheme to strengthen DES against brute force attack. This
> involves running the cipher three times with three different keys. The first
> time the plain text is encrypted with one key, then it is decrypted with a
> different key, finally it is encrypted with a third key. The
> encrypt/decrypt/encrypt sequence (rather than an encrypt/encrypt/encrypt
> sequence) was chosen for some reason having to do with compatibility with
> DES encryption hardware. Encrypt/decrypt/encrypt isn't otherwise superior to
> encrypt/encrypt/encrypt.
>
> This is all what I think, so please correct me on details where I am mistaken.
>
> So here are my questions. I've heard that encrypting ciphertext not only
> adds nothing to the strength of encryption but may actually weaken a cipher.
> For example I start with plaintext foo.txt. I encrypt it with serpent (or
> AES or MARS or Twofish or RC6- chose one) and key1 to produce foo.enc1. Next
> I encrypt foo.enc1 using key2 to produce foo.enc2. Then I encrypt foo.enc2
> using a third key to produce foo.enc3.
>
> Question 1. I have been told that foo.enc1 is actually more secure than
> foo.enc3. Is this true?

Not quite. What was proven is that foo.enc3 *can* be weaker than
foo.enc1, which is pretty surprising. However in practice it usually is
stronger, although in a surprising number of cases it is only very
slightly stronger. For example, *if* the encryption operations commute
(e.g. stream ciphers), then you can prove it is at least as strong as
the strongest cipher.

> Question 2. If this is true, why is 3DES considered more secure? Why don't
> the same rules apply.

The proof that DES is not a group convinced most people that 3DES is
extremely unlikely to exhibit the kind of degenerate features referred
to in the above proof. However attacks are known against 3DES which
weaken it down to a similar order of strength as single DES, provided
one has access to a (currently infeasible) amount of memeory and can
obtain large numbers of chosen plaintexts. When this attack was first
presented, the amount of memory required was so vast it seemed unlikely
to be available for at least 30 years, but further refinements have
reduced the memory requirements to the point where it might be feasible
in this decade.

> Question 3. Or is what I was told really about 256 bit encryption being
> strong enough and anything else is really irrelevant overkill? Might the
> claim really be that complexity is increased (making the encryption
> potentially weaker) without any additional benefit? But in the case of 3DES,
> the increase from 56 bit to 168 bit is worth the added complexity?

Nevermind 256 bit, even 128 is more than adequate for anything except
storing secret treaties with the aliens. At this level, your opponent is
far more likely to be bugging your computer and bribing your cleaners,
than cracking your keys.

Cheers,
Roger