Subject: RE: [Cfrg] Question on key size reduction for Cipher-based PRFs and MACs

From: "Narayanan, Vidya" <[email-masked]>
Date: Thu, 12 Jul 2007 13:17:55 -0700

Sorry, I didn't clarify correctly in my previous email.  Please see
additional clarification below. 

> -----Original Message-----
> From: David Wagner [mailto:[email-masked]] 
> Sent: Wednesday, July 11, 2007 5:45 PM
> To: Narayanan, Vidya
> Subject: [Cfrg] Question on key size reduction for 
> Cipher-based PRFs and MACs
> 
> 
> In article 
> <[email-masked]
> you write:
> >Can that approach be generalized for all cipher-based PRFs in the 
> >following manner:
> >
> >K := Cipher-based-PRF(0^block-size, VK, VKlen)? 
> 
> I don't understand your notation.  If VK is the key to the 
> PRF and 0^block-size (and possibly VKlen) is the input to the 
> PRF, then yes, that works.  You can use any secure PRF, 
> cipher-based or not.
> 

In accordance with RFC4615, if the original key (VK) is longer or
shorter than 128 bits, then the key, K, is derived by "applying the
AES-CMAC algorithm using the 128-bit all-zero string as the key and VK
as the input message".  I was using the same notation as that in the RFC
for generalizing it.  Basically, I was wondering if there is a problem
with using all-zero string equal to the block size of the cipher as the
key and the original key (VK) as input to the PRF to derive a shorter
key, K.  

> I don't quite understand what VKlen is doing there or why you have
> 3 arguments to the PRF or what that ordering of arguments 
> implies, so if I have misunderstood your notation, you'll 
> need to post again.
> 

I'm actually not sure why the key length is part of the input to the PRF
even in RFC4615.  Is it necessary?  The RFC doesn't provide any
explanation for it. 

> >Also, does this approach equally apply to Cipher-based MACs as well 
> >(i.e., K := Cipher-based-MAC(0^block-size, VK, VKlen))?
> 
> Under the same assumptions as above, no.  However, most MACs 
> are also believed to be PRFs as well, so the distinction may 
> be mostly of theoretical interest.
> 

In the revised notation with the all-zero key and VK as input, can we
derive a shorter key using the notation above? 

Thanks much for your input. 

Regards,
Vidya

> -- David

_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg

---

From: Paul Hoffman <[email-masked]>
Date: Thu, 12 Jul 2007 13:38:32 -0700

The explanation of variable key lengths in RFC 4434 may be clearer. 
Or, it may not be; I adopted it because of oversights we made in 
IKEv2, not for a good cryptographic reason.

--Paul Hoffman, Director
--VPN Consortium

---

From: David Wagner <[email-masked]>
Date: Thu, 12 Jul 2007 13:44:10 -0700 (PDT)

> as the input message".

Oh.  Well, I don't know of any theoretical basis for thinking
that this will work.  One standard way for expanding a key or deriving
session keys from a master key MK is that you use a PRF with MK as the
key and some constant string (e.g., all zeros) as the input, and then
you take as many bits from the output of the PRF as you need.  This way
you can derive many subkeys from the master key MK as you want just by
changing that constant string.  Note that this is the reverse of
what you quote from RFC4615.

If you really want to derive only one key from MK, then another
strategy is to hash MK using a secure hash function (e.g., SHA256).
If the key is too short, that's what I'd recommend.

Perhaps RFC4615 is trying to do something clever for the case where
(a) the key VK is too short, and (b) they already have a block cipher
implemented in hardware and they don't want to take up the extra die
space to implement a hash function, too.  In that case, well, all I can
say is that what they are recommending seems likely to work but it is
not guaranteed or justified by any theory or by any standard assumptions
on AES, so it is mildly dubious.  In practice it is highly unlikely that
this crypto scheme will be the weakest link in your system overall, so I
may be arguing about the number of angels that can fit on the head of a
pin -- but at the same time this is not the best possible practice and
so I would probably not use this scheme except where necessary (e.g.,
applications where I really cannot use a hash function and I cannot
get a longer key).  For instance, I don't think this trick is likely
to be justified in most software applications, because it's easy enough
to just use some standard library implementation of SHA256 and there's
usually little cost in doing so.

-- David

---

From: "Narayanan, Vidya" <[email-masked]>
Date: Thu, 12 Jul 2007 14:34:08 -0700

Thanks, David. 

In the case under consideration, we don't have an issue of shorter than
needed keys.  We have a 64 octet (or longer) key that may be used with a
variety of integrity algorithms for generating a MAC.  For hash-based
integrity algorithms, we recommend that the key be first hashed to
reduce the size of the key before generating the MAC.  

For cipher-based integrity algorithms, in order to allow cases where the
device does not have a hash-based algorithm, we were considering an
approach using the cipher-based algorithm itself.  But, I agree with you
that requiring the availability of SHA-256 is not really restrictive.
So, we will stick to recommending reducing the key size by hashing the
key in all cases. 

Thanks again.  

Regards,
Vidya

> Sent: Thursday, July 12, 2007 1:44 PM
> To: Narayanan, Vidya
> Cc: David Wagner; [email-masked]
> Subject: Re: [Cfrg] Question on key size reduction for 
> that this will work.  One standard way for expanding a key or 
> deriving session keys from a master key MK is that you use a 
> PRF with MK as the key and some constant string (e.g., all 
> zeros) as the input, and then you take as many bits from the 
> output of the PRF as you need.  This way you can derive many 
> subkeys from the master key MK as you want just by changing 
> that constant string.  Note that this is the reverse of what 
> you quote from RFC4615.
> 
> If you really want to derive only one key from MK, then 
> another strategy is to hash MK using a secure hash function 
> (e.g., SHA256).
> (a) the key VK is too short, and (b) they already have a 
> block cipher implemented in hardware and they don't want to 
> take up the extra die space to implement a hash function, 
> too.  In that case, well, all I can say is that what they are 
> recommending seems likely to work but it is not guaranteed or 
> justified by any theory or by any standard assumptions on 
> AES, so it is mildly dubious.  In practice it is highly 
> unlikely that this crypto scheme will be the weakest link in 
> your system overall, so I may be arguing about the number of 
> angels that can fit on the head of a pin -- but at the same 
> time this is not the best possible practice and so I would 
> probably not use this scheme except where necessary (e.g., 
> applications where I really cannot use a hash function and I 
> cannot get a longer key).  For instance, I don't think this 
> trick is likely to be justified in most software 
> applications, because it's easy enough to just use some 
> standard library implementation of SHA256 and there's usually 
> little cost in doing so.
> 
> -- David
>

---

From: "Narayanan, Vidya" <[email-masked]>
Date: Thu, 12 Jul 2007 14:40:02 -0700

I'm not sure how RFC4434 differs from RFC4615 in the case of longer
keys.  It also seems to talking about using a PRF with an all-zero key
and the longer current key as the input to the PRF.  What did I miss? 

Vidya 

> From: Paul Hoffman [mailto:[email-masked]] 
> Sent: Thursday, July 12, 2007 1:39 PM
> To: Narayanan, Vidya
> Cc: [email-masked]
> Subject: RE: [Cfrg] Question on key size reduction for 
> Or, it may not be; I adopted it because of oversights we made 
> in IKEv2, not for a good cryptographic reason.
> 
> --Paul Hoffman, Director
> --VPN Consortium
>

---

From: Paul Hoffman <[email-masked]>
Date: Thu, 12 Jul 2007 15:04:00 -0700

At 2:40 PM -0700 7/12/07, Narayanan, Vidya wrote:
>keys.

RFC 4434 does not explicitly mix the key length into the calculation.

>It also seems to talking about using a PRF with an all-zero key

Nothing, it seems.

Basically, if you have a too-long key and you want to shorten it and 
you don't want to use a hash function and you want to use AES, this 
is a simple way of doing that. As David says, there is no proof (or 
even suggestion of a proof) based on properties of AES behind it.

--Paul Hoffman, Director
--VPN Consortium