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

IKE entropy issues with long keys

I've not seen that this analysis is indicated anywhere in the IPSEC
RFCs, so I'll submit it here and suggest that the results probably
should be mentioned in the IKE document directly.  (It has been
mentioned previously on the ipsec mailing list (I saw at least once
reference in the archives from 96)).

For situations where the needed key length of an ISAKMP SA encryption
algorithm is greater than what the prf() (hash) algorithm generates,
appendix B of RFC 2409 specifies that longer keying material should be
generated using:

      Ka = K1 | K2 | K3
  and
      K1 = prf(SKEYID_e, 0)
      K2 = prf(SKEYID_e, K1)
      K3 = prf(SKEYID_e, K2)

  where SKEYID_e is defined previously in section 5 as:

      SKEYID_e = prf(SKEYID, SKEYID_a | g^xy | CKY-I | CKY-R | 2)

The problem with the method of chaining hash outputs for generating a
longer key is the entropy of the longer key doesn't increase beyond
the entropy generated by a single hashing pass.

Let me switch to "example" mode, where we'll use the BlowFish
encryption algorithm with a 448 bit key and HMAC-MD5 as the prf()
function.

  SKEYID_e = 160 bits long (the length of the SHA1 output).
  K1,K2,K3 = 160 bits.
  K        = 160*3 = 480 bits (which is then truncated to 448).

However, if I was to brute force breaking of the ISAKMP SA, I would
merely iterate over the SKEYID_e values and use that to calculate Ka.
At most I would have to iterate over all the possible values of
SKEYID_e, which would be only 160 bits, since the full key can be
derived from it.  This reduces the entropy of encryption algorithm to
the prf()'s entropy, in this case only 160 bits.

The ISAKMP SA is then used in the future to negotiate new SAs.
Fortunately, the strength of these new keys is depends on
more information:

Assuming a brute force attack against the ISAKMP SA is used, the
following derivations of the key material for the new SA can be
derived with the same entropy level if no new key exchange material is
used for future key negotiation.  From section 5.5 describing Quick
Mode:

      KEYMAT = K1 | K2 | K3
      where
        K1 = prf(SKEYID_d, [ g(qm)^xy | ] protocol | SPI | Ni_b | Nr_b)
        K2 = prf(SKEYID_d, K1 | [ g(qm)^xy | ] protocol | SPI | Ni_b |
        Nr_b)
        K3 = prf(SKEYID_d, K2 | [ g(qm)^xy | ] protocol | SPI | Ni_b |
        Nr_b)
        etc.

Assuming the ISAKMP SA has been broken, all of the above attributes
are known except SKEYID_d and g(qm)^xy (protocol, SPI, Ni_b, Nr_b are
all retrievable from the decrypted ISAKMP SA packets).  If a new key
exchange message is not included with future SA negotiations, then the
strength of the entropy associtaed with the SA keys will be limited to
the strength of the SKEYID_d value, which is again the output of the
hashing (or prf) function.  Fortunately, if the optional Key Exchange
portion has been included the entropy of the g(qm)^xy must also be
included, which should be significantly larger.

Therefore, I submit that to brute-force any encryption algorithm
negotiated by IKE one needs only to iterate through 2^N iterations,
where N is the number of bits produced by the prf/hashing algorthim
and not the number of bits used the encryption algorithm.  This would
result in 128 bit entropy for algorithms using keys derived from MD5,
160 bit entropy for algorithms using SHA-1 and ? bit entropy for
algorithms using TIGER.  Fortunately, SHA-256, SHA-384 and SHA-512
have been defined which should help produce larger entropy keys.

I feel this should be mentioned in the documents (but more briefly),
as people expecting full strength from their encryption algorthim will
not get it if they allow the simultaneous use of a smaller hash/prf
algorithm.  (Fortunately for the time being, 128/160 bit keys seem
strong enough for my personal use).  This will become more and more
important as larger key sizes are used in the new algorthims like
AES.  Not mentioning it may give people a false sense of security.

IMHO, the proper thing that should be done (or should have been done)
is to require more Key Exchange packets to generate larger key lengths
such that chaining was not used to generate longer keys, but rather
the key segments be generated independently from different g^xy
values:

      SKEYID_d = 
         prf(SKEYID #1, g^xy #1 | CKY-I | CKY-R | 2) 
       | prf(SKEYID #1, g^xy #2 | CKY-I | CKY-R | 2)
     [ | ... ]

     whhere

      SKEYID #N = prf(Ni_b | nr_b, g^xy #N)

(being careful to make sure the entropy of the g^xy value is greater
than that of the hashing algorthim).
  
-- 
"Ninjas aren't dangerous.  They're more afraid of you than you are of them."
Follow-Ups: