[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

RE: Generating 3DES keys from SKEYID_e



Good catch, Stephane.

Yet again, we see a suboptimal result from a parameter derivation where the
derivation formula appears to have been arbitrary chosen (and the
justification for the formula is omitted).

Yes, we all know that 2^128 is a large number, but 2^256 is a much biger
number. We deal with large numbers all the time. As cryptography
implementers, we have to set aside the "billions and billions" mumbo jumbo
and deal with quanitifiable safety margins. (For example, 2^128 is only 2^64
against meet in the middle.)

As Stephane pointed out, fixing this weakness would have been trivial, had
it been caught sooner. Fine, so in this case the weakness was not fatal...
But what assurance do we have that some other parameter derivation is not
casually discarding entropy?

IMHO, it just goes to show that pseudo-arbitrary parameter derivations do
not lead to a strong protocol.

BTW, although Stephane only mentioned the phase 1 SKEYID_e derivation, I
want to point out that this weakness also applies to phase 2 (although it's
fixed if pfs is used).

Andrew
--------------------------------------
Beauty with out truth is insubstantial.
Truth without beauty is unbearable.


> -----Original Message-----
> From: owner-ipsec@lists.tislabs.com
> [mailto:owner-ipsec@lists.tislabs.com]On Behalf Of Glawitsch, Gregor
> Sent: Friday, July 14, 2000 5:12 PM
> To: 'Stephane Beaulieu'; ipsec-list
> Subject: RE: Generating 3DES keys from SKEYID_e
>
>
> Stephane,
>
>         do you realize how large 2^128 is?
>
> Greg Glawitsch
> Network Associate, Inc.
>
> -----Original Message-----
> From: Stephane Beaulieu [mailto:stephane@cisco.com]
> Sent: Friday, July 14, 2000 1:56 PM
> To: ipsec-list
> Subject: Generating 3DES keys from SKEYID_e
>
>
> Hi All,
>
> In RFC 2409, Appendix B, there's some text on how to generate keying
> material for a cipher that requires a key larger than SKEYID_e.
>
> <begin insert>
> Encryption keys used to protect the ISAKMP SA are derived from
>    SKEYID_e in an algorithm-specific manner. When SKEYID_e is not long
>    enough to supply all the necessary keying material an algorithm
>    requires, the key is derived from feeding the results of a pseudo-
>    random function into itself, concatenating the results, and taking
>    the highest necessary bits.
>
>    For example, if (fictitious) algorithm AKULA requires
> 320-bits of key
>    (and has no weak key check) and the prf used to generate SKEYID_e
>    only generates 120 bits of material, the key for AKULA,
> would be the
>    first 320-bits of Ka, where:
>
>        Ka = K1 | K2 | K3
>    and
>        K1 = prf(SKEYID_e, 0)
>        K2 = prf(SKEYID_e, K1)
>        K3 = prf(SKEYID_e, K2)
>
>    where prf is the negotiated prf or the HMAC version of the
> negotiated
>    hash function (if no prf was negotiated) and 0 is represented by a
>    single octet. Each result of the prf provides 120 bits of material
>    for a total of 360 bits. AKULA would use the first 320 bits of that
>    360 bit string.
> <end insert>
>
> This probably comes from the same idea presented in RFC 2412,
> section 2.6,
> which uses similar formulas:
>
> Don't these methods limit the effective keyspace for 3DES?
>
> Someone wanting to guess the 3DES key, could start by simply guessing
> SKEYID_e.  SKEYID_e is only 128 bits long (assuming md5 is
> used for the
> hmac).
>
> The attacker then runs every one of those 2^128 SKEYID_e through the
> algorithm above (requiring 3*2^128 md5 computations), and
> ends up with 2^128
> possible 3des keys.
>
> So, effectively, the strength of the cipher could only ever
> be as strong as
> the size of the output of the hash algorithm.  Is this correct?
>
> If this is correct, then it could be fixed by including g^xy
> in K1, K2 and
> K3
>
>         K1 = prf(SKEYID_e, g^xy, 0)
>         K2 = prf(SKEYID_e, g^xy, K1)
>         K3 = prf(SKEYID_e, g^xy, K2)
>
>
> I searched through the archives, and haven't seen this discussed.
>
> Stephane.
>
> ------
> Stephane Beaulieu
> S/W Engineer
> VSEC Business Unit, Enterprise Line of Business
> Cisco Systems.
> email: stephane@cisco.com
> phone: (613) 271-3678
>
>
>



References: