Re: Editorial: Use of MAY in draft-ietf-ipsec-ikev2-algorithms

[Scott Fluhrer <sfluhrer@cisco.com>]

On Thu, 12 Jun 2003, Eric Rescorla wrote:

> Scott Fluhrer <sfluhrer@cisco.com> writes:
>
> > On Thu, 12 Jun 2003, Eric Rescorla wrote:
> >
> > > Paul Hoffman / VPNC <paul.hoffman@vpnc.org> writes:
> > >
> > > > At 10:22 AM -0400 6/12/03, Paul Koning wrote:
> > > > >96 is probably enough but it's not a common keysize, so 128 makes
> > > > >sense.
> > > >
> > > > But only if you want to eliminate TripleDES, whose key size is 112
> > > > bits. No one counts the parity bits as meaningful.
> > > As I understand RFC 2451, the 3DES we uses is 3-key 3DES in
> > > EDE mode, so the effective key size should be 168 bits.
> >
> > For a cryptographical standpoint, there may be 168 distinct key bits that
> > affect the ciphertext, but it is well known that you can break 3DES with
> > far less work than O(2**168) effort.  There is a meet-in-the-middle attack
> > that (with a lot of memory) brings the effort down to around O(2**112),
> > which is what I assume Paul was refering to.
> Uh, "lot" means O(2**56), no?

Well, yes, but the attack scales to lesser amounts of memory.  If you
had only O(2**40) memory, then the attack works in O(2**128) time --
still far less than 2**168.

>
> >>  In addition, if you have
> > vast quantities of known plaintext encrypted with the same key, Stephan
> > Lucks' attack becomes interesting, which reduces the effort a bit more
> > (I don't have a solid estimate at hand).
> >
> > Neither of these attacks are practical given current current limitations,
> > but one should remember that they do exist.
>
> Sure, but under practical conditions the effective key size of
> 3DES-EDE3 168 bits
Actually, as I pointed out above, even if you restrict the amount of
memory an attacker has available to a reaonable amount, the strength of
3DES is still less than 168 bits.

> and it's conventional to refer to it this way.

Conventional, perhaps, to people who aren't too concerned with precision
(although, in my experience, the estimate of 112 bits is rather more
common).

On the IPSec mailing list, we're supposed to be (one of the) IETF expert
groups on security -- I would hope that some greater amount of precision
is appropriate.

> In the same way, it's conventional to refer to DES as having a strength
> of 56 bits despite the fact that if you somehow laid your hands on 2^47
> chosen plaintexts the complexity of DES would be a measly O(2^47).
Actually, if you're refering to linear cryptanalysis, the common result is
that it takes 2^47 known plaintexts.


-- 
scott