Subject: [MSEC] Final MIKEY edits

From: Mats Näslund <[email-masked]>
Date: Wed, 10 Mar 2004 09:21:30 +0100

Apologies for possible multiple posts, but this was mailed yesterday,
and there is some indication it did not reach the list properly, thus
this re-post.

---

Dear all,

We are anticipating that MIKEY will in a not too distant future
pop out of the RFC editor queue, and become an RFC. We will take
care of some editorial nits before this happens. However, there
is also one larger change that we are suggesting, hence this mail
to open up a possibility for the WG to provide feedback. We would
like to have a one week deadline for the comment period (see exact
dates below).

To summarize the change, it concerns the key derivation function,
and specifically, we would like to change input key ("inkey") block
size division in the pseudo random function (PRF) from 512 bits to
256 bits. This is an effect of some analysis the authors have made
(see below).

Editorially, this change is trivial, but since it is still of
technical nature, we here provide a short (but hopefully convincing)
rationale. A more nicely typeset and more complete problem description
is available for those interested by request (we wanted to avoid
flooding thousands of inboxes.)

The PRF in MIKEY is used e.g. to derive TEKs from TGKs. It's similar
to that of TLS with one change: while TLS applies the PRF to the
whole key, MIKEY's PRF applies it blockwise to 512-bit blocks of the TGK
(and XORs the results). The rationale for this is that since the PRF
is based on HMAC and HMAC by definition first hashes keys of size
 > 512, the TLS PRF cannot produce a key with, let's say, 384-bit
entropy, even if the the TGK is, say, a 2048-bit Diffie-Hellman key.
Although one could argue that most "practical" key sizes can still
be supported also by the TLS PRF, in MIKEY we wanted to remove this
bottleneck.

Now, it turns out that there is one problem with this (which applies
also to the original TLS PRF if one looks closer). To see what,
recall that the PRF(s) we talk about are HMAC (we assume using SHA1)
used (more or less) in an "output feedback mode" (OFB). (Refer to the
MIKEY draft for exact details.) Consider the following three cases:

1. The TGK is *longer* than 512 bits. Obviously, HMAC will hash
    the TGK and the effective key size is <= 2*160 = 320 bits
    (the hashed "TGK XOR ipad" and "TGK XOR opad"). This is all
     well known.

2. The TGK is *exactly* 512 bits. While a hash will not occur, the
    iterative nature of SHA1 and its 512-bit blockwise processing
    means that one can still guess the internal state of the "inner"
    and "outer" HMAC hashes at *precisely* the instant where the
    key has been processed. Again, the security is 320 bits.

3. Suppose the TGK is *almost* 512 bits, say 512-b bits. While the
    processing of the key material now does not coincide with the
    first block note that:

    - the additional b bits that enter the *first* SHA1 blocks are public
    - heuristically, with probability 2^(-b) the b-bit output prefix
      of any single hash/HMAC in the "OFB chain" will take a give value.

     Consequently, assuming L blocks of output is produced, with
     probability about 2^(-2b(L-1)), all hashes/HMACs in the chain will
     produce b-bit prefixes "colliding" with the (known) b-bit inputs to
     the first stage of the OFB chain. *If* this happens, guessing the
     2*160 bit hash states after the first 512 bits of the first two
     hashes (in the first HMAC) has been processed is enough to deduce
     the TEK.

Working out the details, the effective key size for MIKEY, when applied
to (512-b)-bit TGK to produce L*160 bit TEKs is bounded by

        320 + 3b(L-1)

bits. For instance, a 500-bit TGK will produce 480-bit TEKs with
entropy 392 bits, etc. (Note that similar bounds can be obtained for
the TLS, WTLS, and IKEv2 PRFs too, where the  "effects" will set in at
varying key sizes due to the slightly different construction. We make
no claims about "insecurity" of the PRF construction in general.)

For sure (or at least: relative to the above analysis), the PRF will
never produce keys with entropy less than 320 bits, and one could argue
that this is sufficient in "practice". Nevertheless, since removing this
"bottleneck" is easy (see below) we strongly feel that we would like to
make MIKEY theoretically sound by indeed fixing it.

The suggested fix is as follows: instead of diving long keys into
512-bit blocks, divide them into 256-bit blocks. This will assert
that "b" in the above expression is never less than 256 and will
effectively kill the collision probabilities of the above "attack".
Editorially, this implies to change one parameter in MIKEY from
"512" to "256" and the effect on an existing MIKEY implementation
seems very small.

We would like to hear your feedback whether you approve of this change.
We will put a deadline of one week. Specifically, we will collect
comments until March 16/2004, 2359UTC. The Security AD Russ suggested
the following way forward:

1. During the one week comment period, we address comments from
    the working group mail list immediately.

2. On March 17, we summarize the changes that the RFC
    Editor will be asked to make during AUTH48.

3. The Working group chairs confirm that the changes do not break
    rough consensus.

4. The ADs will handle IESG review of the changes, if needed.

5. The ADs will submit the changes to the RFC Editor, avoiding
    the need for them to seek further approval for the changes.

Comments?

Regards,

MIKEY authors

This communication is confidential and intended solely for the addressee(s). Any unauthorized review, use, disclosure or distribution is prohibited. If you believe this message has been sent to you in error, please notify the sender by replying to this transmission and delete the message without disclosing it. Thank you.

E-mail including attachments is susceptible to data corruption, interruption, unauthorized amendment, tampering and viruses, and we only send and receive e-mails on the basis that we are not liable for any such corruption, interception, amendment, tampering or viruses or any consequences thereof.

_______________________________________________
msec mailing list
[email-masked]
http://www.pairlist.net/mailman/listinfo/msec

---

From: "Elisabetta Carrara (KI/EAB)" <[email-masked]>
Date: Wed, 17 Mar 2004 13:28:33 +0100

Dear all,
last week we proposed a change to the MIKEY key derivation 
function (going from 512-bit blocks to 256-bit blocks) and 
asked for a one week comment period, which has elapsed.

We received one request for the paper describing the details 
behind the analysis, but got no comment. We interpret this 
as a "yes" from msec to the proposed change. 

We therefore suggest to complete the plan as outlined in the 
previous mail. The remaining steps are:
- Summarize the changes that the RFC Editor will be asked to make 
during AUTH48 (which is done above).
- We ask that the Working group chairs confirm that the changes do 
not break rough consensus.
- The Area Directors will handle IESG review of the changes, 
if needed.
- The Area Directors will submit the changes to the RFC Editor, 
avoiding the need for them to seek my approval for the changes.

Hence, we would like the chairmen to confirm the change, so that 
we can then submit to the ADs.

Cheers,
/MIKEY authors

> -----Original Message-----
> From: [email-masked]
> [mailto:[email-masked]]On Behalf Of Mats Näslund
> (KI/EAB)
> Sent: den 10 mars 2004 09:22
> To: msec
> Cc: Hardjono, Thomas; Ran Canetti
> Subject: [MSEC] Final MIKEY edits
> 
> 
> 
> This communication is confidential and intended solely for 
> the addressee(s). Any unauthorized review, use, disclosure or 
> distribution is prohibited. If you believe this message has 
> been sent to you in error, please notify the sender by 
> replying to this transmission and delete the message without 
> disclosing it. Thank you.
> 
> E-mail including attachments is susceptible to data 
> corruption, interruption, unauthorized amendment, tampering 
> and viruses, and we only send and receive e-mails on the 
> basis that we are not liable for any such corruption, 
> interception, amendment, tampering or viruses or any 
> consequences thereof.
> 
>