From: Robert Baskerville robert@robert.net
To: secureshell@securityfocus.com
Subject: Triple DES keys
Date: Fri, 6 Dec 2002 13:02:31 +0000
X-Mailer: KMail [version 1.3.2]
Organization: rarely any

> I would like to know the key-length used for 3DES data encryption in
> openssh.

Triple-DES uses a 168-bit key (3 x 56).

DES keys are 56 bit. When you feed the key into the algorithm, you use a
64-bit value, but the extra 8 bits are "parity bits" in theory but rarely
used. The parity bits were added to DES in order to make it less obvious
that the key length was being reduced deliberately. Or maybe I'm just
cynical :-)

There is no such thing as "128-bit Triple-DES" :-)

The 168-bit key can be made from either TWO different 56-bit keys or THREE
different 56-bit keys.

The encryption uses standard DES three times, encrypt operation with key1,
decrypt operation with key2, encrypt operation with key3.

In the two-different-key version, key1 and key3 are the same.

The reason for the E-D-E is that by setting key1 = key2 = key3 the same
software can without modification give you single DES encryption for
backwards compatibility. Of course, you won't be using this if you have
any sense (all the processor overhead of 3DES without ANY of the strength
advantages)

> Also, I am interested in the export regulations concerning openssh in
> USA.

That's complex, but easy to cope with.

IMPORTING it to the USA is OK. If you want it outside the USA, get it from
outside the USA (ie avoid exporting it because the regulations are complex
and rediculous)

> the sshd man page states 128 bit key used for 3DES.

Hmmm. Not what my copy says. If it claims 128-bit 3DES, it is simply wrong
:-)

The other thing which may confuse is that even with 3 different keys 3DES
has only really got a "strength" of 112 bits. That's because the best
attack against double-DES (which requires stupidly large amounts of
memory, but is possible in principle) is an attack which works from both
ends. This results in double-DES only being approx 1-bit stronger (ie
insignificantly stronger) than DES (if you are able to find enough memory
to use this attack). This attack is defeated by adding the third DES
operation. (And if 3DES was ever too weak for you, you'd be wanting 5DES
rather than 4DES etc).

On the plus side, it has been proved that 3DES *is* stronger than DES.
[Just adding extra rounds doesn't necessarily make things stronger.
Triple-ROT13 anyone? If an algorithm forms a group over its keys then
N-rounds with N-different-keys can still be boiled down to a single round
with a single key and are therefore no harder to bruteforce than a single
round. Luckily DES doesn't form such a group. Apologies if this sounds
like gibberish;]

Robert Baskerville

Date: Mon, 09 Dec 2002 10:31:48 -0800
From: Michael Sierchio kudzu@tenebras.com
To: jaymo@hiwaay.net
CC: Rick Moen rick@linuxmafia.com, secureshell@securityfocus.com
Subject: Re: 3DES key-length for data authentication

jaymo@hiwaay.net wrote:

>The effective keylength of Triple-DES is 112 bits. I don't recall the
>rationale for this now - it should be available in all the usual
>places; e.g. google, "triple-DES effective keylength".

The meet-in-the-middle time-memory trade-off attack (Cf. Merkle-Hellman)
is a chosen plaintext attack, so it's applicable only if the adversary
can mount such an attack -- not likely in a VPN, probably likely in an
encrypted file system. It's easiest to describe for double DES --
Merkle-Hellman allows for breaking double DES with 2 keys in 2^(n+1)
chosen plaintext encryptions, rather than the 2^2n you might expect.
Merkle-Hellman breaks 3-DES-CBC-EDE-3K in 2^2n steps and requires 2^2n
blocks of memory.

The effective key length if the adversary can mount a CPA against
3-DES-CBC-EDE-3K is 112 bits. If the adversary cannot mount the MITM
attack, the effective key length is 168 bits.

In the case of using triple DES for SSH or SSL operations, my educated
guess is that it actually does provide 168 bits worth of key strength.