Subject: RE: [Cfrg] AES GMAC

From: [email-masked]
Date: Thu, 22 Sep 2005 19:37:00 +0300

Dear David,

Thanks for reading our note to NIST and for your response. Please find
our comments inline.

>>  Our
>> concern is that the GMAC construction proposed by MacGrew and Viega 
>> does not meet this requirement. Indeed, for a message of length 2^m 
>> blocks the forgery probability is about 2^{m-n}. In the current 
>> proposal, upperbound of 2^{-64} to the forgery probability 
>is achieved 
>> by using 128-bit tags and setting an upperbound of 2^64 to 
>the message 
>> length.
>
>But in the internet draft under discussion, messages are not 
>going to be anywhere near that length.  The largest that an 
>IPv4 packet can get is 64 kilobytes (2^{12} blocks), which 
>puts the single packet forgery probability at 2^{-116}.  This 
>value compares favorably to that of the recommended ESP 
>authentication methods, which use 96-bit tags.  In practice, 
>packets on the Internet are significantly smaller, and only 
>very rarely exceed 2kb (256 blocks) (see 
>http://www.caida.org/outreach/papers/1998/Inet98/Inet98.pdf or 
>similar studies), and MTUs around this size are common.
>

This being the case, one could set (for example)

- the upperbound of the message length to 2^{32} 128-bit blocks
- the tag length to 96 bits
- the big field size to 2^{128} and the small field size to 2^{96}

And use the double layer construction.

To do this one needs the following keys
- 128-bit point K1 for polynomial evaluation in the big field
- 96-bit point for K2 polynomial evaluation in the smaller field
- 96-bit one-time-pad K0 generated using CTR-AES with 128-bit key K

Your concern is where to get these keys. We suggest to generate them
using CTR-AES. With the above parameters this would mean either
1) three calls to AES, if all K0, K1 and K2 are generated in this
manner; or
2) two calls to AES, if we set K1 = K (as in your GMAC) and generate K2
and K0 using CTR-AES.

Note that both alternatives give also resistance against the "Multiple
Forgery Attack" since for each message, the polynomial is evaluated at a
different point. 
  
>> Using this construction, for example, 64-bit security level can be 
>> achieved with 64-bit tags for messages of up to 2^{64} 
>blocks, and it 
>> does not take more key, or more calls to the AES, or 
>essentially more 
>> computations than with the construction by MacGrew and Viega.
>
>I don't understand the claim in the last sentence.  Is the 
>"second 64-bit quantity" \lambda in Section 3 of your note to 
>NIST not additional key material?
>

The idea is the same as above. With one 128-bit key K and one call to
the AES one has 256 bits of key material which is enough: (with the same
notation as above)
- K1 = K
- 64-bit K2 (one half of the AES output)
- 64-bit one-time-pad K0 (another half of the AES output)

>p.s. - your note to NIST mentions that there is an ETSI SAGE 
>effort that is considering MAC designs.  It would be great if 
>CFRG and the IETF could liaison with that group and hear a 
>report on the status of this work.  Could you please let me 
>know who in ETSI I could bug about this?
>

The work is still on going and will be completed by the end of the year.
In our note to NIST the main features of the new 3GPP Integrity
Algorithm by ETSI SAGE are described.

With best regards,

Kaisa 

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

---

From: David McGrew <[email-masked]>
Date: Thu, 22 Sep 2005 12:04:46 -0700

Hi Kaisa,

On Sep 22, 2005, at 9:37 AM, <[email-masked]> wrote:

> using CTR-AES.

Of course, but a design intended for high throughput needs to take  
into account the delay due to the computation of K2.

> With the above parameters this would mean either

Here you mean that K2 is generated by using the nonce associated with  
the message, rather than using a 'special' nonce not associated with  
any message, right?   This has performance implications for software,  
since it would disallow the use of key-dependent precomputation for  
speeding up multiplication.

> - 64-bit one-time-pad K0 (another half of the AES output)

Yes, I understand.  My point was in reference to the need to either  
store and fetch the additional keying material or to compute it from  
the main key prior to using in the tag computation.

With your two-stage approach, there may be a nice design  
opportunity.  The secondary key K2 isn't needed until the very last  
part of the message processing algorithm, so it may well be possible  
to fit its computation into the encryption pipeline without adding  
much overall delay.  (This is in contrast to the initial hash key,  
which in some cases is needed before the encryption pipeline is done  
in order to process message headers or other authenticated but not  
encrypted data.)

> Algorithm by ETSI SAGE are described.

Since telephony is in scope there, I'd expect that the new integrity  
algorithm would be of interest to IETF SRTP.  The SRTP voip community  
would *welcome* a MAC that is more implementation-friendly to DSPs  
than HMAC-SHA1, so this is very interesting.  The main challenge in  
this domain seems to be to find a MAC that's not a PRF yet provides  
similar security even with short tags.

Best regards,

David

---

From: David McGrew <[email-masked]>
Date: Fri, 23 Sep 2005 10:47:11 -0700

Geir,

thanks for the info!

The SNOW cipher is quite interesting, so it was a pleasant surprise  
to find it in the specification (for others: in the d2_draft document  
in the .zip file at the website that Geir referenced).  Do you know  
what, if any, differences there are between the "snow 3g" variant  
that it defines and the "snow 2" version defined in SAC '02?

David

On Sep 22, 2005, at 1:23 PM, [email-masked] wrote:

> Hi,
>
> The new UMTS integrity and confidentiality algorithms is currently  
> under
> security evaulation. They are *not* yet approved as standards for  
> UMTS.
> Anyway, the basis is SNOW and the temporary documents (tdoc's) are
> released on the 3GPP web.
>
> You can fetch them via the email list at
> http://list.3gpp.org/scripts/wa.exe? 
> A2=ind0509&L=3gpp_tsg_sa_wg3&T=0&O=A&P=5277
>
> ETSI SAGE is commisioned by the 3GPP SA3 group to do the  
> development work.
> This is the SA3 meeting minutes on the new algorithms:
>
> *******
>
> TD S3-050579 contained a report from ETSI Sage.
> ETSI SAGE project team STF 278 has produced draft specifications  
> for UEA2
> and UIA2 According to the project plan and the SA3 decisions at SA3
> meetings #38 and #39 they are now going for public evaluation. This  
> will
> be performed by two contracted academic teams. Evaluation is of course
> also open to all SA3 members and interested parties. The period for
> external evaluation of the algorithms is 1st September - 30th  
> October, so
> anything received after the end of October may be too late.
> It was noted that the UEA2 and UIA2 have a different structure than  
> Kasumi
> so that a potential break in Kasumi need not lead to the cracking  
> of UEA2
> and UIA2. Based on this, it was noted that the evaluation period is  
> short.
> However, it was also noted that UEA2 and UIA2 are based on SNOW,  
> which has
> been available for some time. Still it was questioned why this is  
> being
> rushed. It was answered that there is a paid analysis and there is  
> a time
> limit on this hence the deadline. Also, the intention of the UEA2  
> and UIA2
> is to replace Kasumi if Kasumi should be broken.
> However, the public evaluation (public scrutiny) is being based on
> voluntary contributions and it was asked if the period could be  
> extended
> to allow for public comments.
> A counter proposal was that the existing schedule should be kept in  
> order
> to allow UEA2 and UIA2 to be frozen and be part of Rel-7 as a  
> candidate
> for early implmentation. This would allow for mobile manufacturers to
> implment UEA2 and UIA2 in the mobiles early; something that will not
> happen unless the algorithms are frozen and mobile manufacturers  
> gets some
> assurance that it will not change. Of course, it is SA that decides if
> this is for early implementation although only on the advice of SA3.
> The chairman commented that some extra time could be given in order to
> allow for comments from voluntary evaluators. The chairman asked if  
> SAGE
> could wait a little longer. If an error is found, then SAGE is the  
> best
> group to evaluate any comments.
> It was decided to targetting the delivery of the final  
> specifications as a
> normal part of Rel-7. This will give some extra time to voluntary
> evaluations.
> Another question was if the paid for evaluations will be made  
> public. It
> was answered that there will be a report from SAGE on its work and  
> this
> will contain information on the evaluations of its work.
>
> ******
>
> So, basically, you are welcome to comment on the algorithms at this  
> stage,
> but you should not yet plan to use them.
>
> BR,
>
> /Geir M. Køien
> Telenor R&D and Agder University College
>
>

---

From: David McGrew <[email-masked]>
Date: Tue, 27 Sep 2005 06:05:03 -0700

On Sep 23, 2005, at 10:47 AM, David McGrew wrote:

> to find it in the specification (for others: in the d2_draft  
> document in the .zip file at the website that Geir referenced).  Do  
> you know what, if any, differences there are between the "snow 3g"  
> variant that it defines and the "snow 2" version defined in SAC '02?

FYI: I hear that it is an sbox change due to the work of Billet and  
Gilbert (thanks to Mats Näslund for pointing this out).
Olivier Billet and Henri Gilbert, Resistance of SNOW 2.0 Against  
Algebraic Attacks.  Available on Springer Online at http:// 
www.springerlink.com/(gp2ell45rueskr55umggnr55)/app/home/ 
contribution.asp?referrer=parent&backto=issue,3,25;journal, 
281,2200;linkingpublicationresults,1:105633,1

David

>> meetings #38 and #39 they are now going for public evaluation.  
>> This will
>> It was noted that the UEA2 and UIA2 have a different structure  
>> than Kasumi
>> and UIA2. Based on this, it was noted that the evaluation period  
>> is short.
>> A counter proposal was that the existing schedule should be kept  
>> in order
>> allow for comments from voluntary evaluators. The chairman asked  
>> if SAGE
>> So, basically, you are welcome to comment on the algorithms at  
>> this stage,