Subject: Re: [Cfrg] RG Last Call on draft-irtf-cfrg-gcmsiv-06

From: "Paterson, Kenny" <[email-masked]>
Date: Mon, 2 Oct 2017 16:41:53 +0000

Dear Stefano, Priyanka and Viet,

Thanks for bringing this new research to the list. We (the chairs) really
welcome your work, and look forward to hearing from the draft's authors on
how they would view the proposed change to the draft that is implicit in
your message. There is no problem for us to extend the duration of
on-going "last call" for the draft in order to discuss it in detail.

At the same time, we would encourage you to put the details of your
analysis in the public domain as soon as you have it ready, so that
everyone can start to look at the fine detail.

Best wishes,

Kenny (for the chairs)

On 30/09/2017 15:00, "Cfrg on behalf of Stefano Tessaro"
<[email-masked] on behalf of [email-masked]> wrote:

>Dear CFRG:
>
>We wanted to bring to your attention a potential optimization of the
>key-derivation step in AES-GCM-SIV that has come out of some of our
>related research work. Sorry this comes somewhat late: We are in the
>process of finalizing a clean write up, but due to time sensitivity,
>we wanted to make the CFRG list aware of this related work.
>
>Currently, the key-derivation function DeriveKey of AES-GCM-SIV uses
>4-6 AES calls (4 to generate a 256-bit key, and 6 to generate a
>384-bit key). The overhead of key derivation over plain GCM-SIV can be
>up to 10% for messages under 1KB (according to the authors’
>benchmarks). Our findings suggest a simple optimization that halves
>the number of calls.
>
>Concretely: Suppose that we have a master key K and a 96-bit nonce N.
>If we want to produce a 256-bit key, DeriveKey(K,N) will output
>
>AES_K(pad(N, 0)) || AES_K(pad(N, 1)),
>
>whereas if we want to produce a 384-bit key, we will instead output
>
>AES_K(pad(N, 0)) || AES_K(pad(N, 1)) || AES_K(pad(N, 2)).
>
>Here, we demand that pad(N, 0), pad(N, 1), pad(N, 2) is different from
>pad(N’, 0), pad(N’, 1), pad(N’, 2), and that pad(N, 0) is not a
>possible input to AES within CTR encryption. Due to the way in which
>AES-GCM-SIV already adopts domain separation elsewhere, it is enough
>to implement pad(N, i) as the concatenation of the 96-bit nonce N and
>a 32-bit counter of value i, but here note that one has to swap the
>relative ordering of nonce and counter in the current proposal, namely
>the nonce comes first, and then the counter.
>
>To see why this would work, we note that the current DeriveKey
>function, and other proposals by Iwata and Seurin, are required to be
>a highly-secure pseudorandom function. Intuitively, this is because
>the current approach to prove security of AES-GCM-SIV reduces (as an
>intermediate step) to the security of GCM-SIV, and in turn of AES,
>under (multiple) independent random keys. This independence is not
>necessary in general, and security proofs go through even when key
>distributions are much more structured, such as the one produced by
>our simple DeriveKey proposal. (This can be validated in the so-called
>ideal cipher model, and we are not aware of any cryptanalytic insights
>that would invalidate this when using AES.) Similar ideas of more
>structured block-cipher based key-derivation have been used in
>different contexts, e.g., in https://eprint.iacr.org/2017/877.
>
>We can prove excellent security bounds for this variant of
>AES-GCM-SIV, in particular in the so-called “multi-user setting”,
>where attackers are accessing multiple instantiations of the scheme
>under independent keys (think of this as multiple TLS sessions using
>the scheme). In this case, we obtain a bound of the order LB / 2^{128}
>+ d(T + L) / 2^k, where: L is a bound on the number of blocks, B is a
>bound on the number of blocks encrypted/verified for a nonce-user
>pair, d is the maximum number of users that re-use a nonce in
>encryption queries, T is a bound on the time-complexity of the
>attacker, and k is the key length of AES, which is either 128 or 256
>bits. (For the single-user setting then obviously d = 1.) If nonces in
>encryption queries are picked at random then d is a small constant,
>and thus the multi-user security is roughly the same as the
>single-user security. (In particular, there is a folklore
>understanding that multi-user security fails when more than 2^{64}
>users are involved, for k = 128, as two of them will likely have the
>same key, but show that this is not an issue for AES-GCM-SIV.)
>
>If nonces are picked arbitrarily then d can be as big as the number of
>queries; in this case we need to pick key length k = 256 for high
>security in the multi-user setting.
>
>We note that previous analyses do not consider the multi-user setting.
>
>Best,
>
>Priyanka Bose (UC Santa Barbara)
>Viet Tung Hoang (Florida State University)
>Stefano Tessaro (UC Santa Barbara)
>
>
>On Sat, Sep 16, 2017 at 5:15 PM, Alexey Melnikov
><[email-masked]> wrote:
>> Dear CFRG participants,
>>
>> This message starts 2 week RGLC on "AES-GCM-SIV: Nonce Misuse-Resistant
>> Authenticated Encryption" (draft-irtf-cfrg-gcmsiv-06), that will end on
>> October 1st. Please send you comments, as well as expression of support
>>to
>> publish as an RFC (or possible reasons for not doing so) in reply to
>>this
>> message or directly to CFRG chairs. Your feedback will help chairs to
>>decide
>> whether the document is ready for review by IRSG and subsequent
>>publication
>> as an RFC.
>>
>> Thank you,
>> Kenny and Alexey
>>
>> _______________________________________________
>> Cfrg mailing list
>> [email-masked]
>> https://www.irtf.org/mailman/listinfo/cfrg
>>
>
>
>
>-- 
>Stefano Tessaro
>Assistant Professor of Computer Science
>University of California, Santa Barbara
>http://cs.ucsb.edu/~tessaro/
>
>_______________________________________________
>Cfrg mailing list
>[email-masked]
>https://www.irtf.org/mailman/listinfo/cfrg

---

From: Yehuda Lindell <[email-masked]>
Date: Tue, 3 Oct 2017 05:29:44 +0000

Dear all,

The paper by Bose, Hoang and Tessaro (BHT) shows that AES-GCM-SIV has excellent multi-user security bounds (according to the authors, this is the first scheme that has been shown to have the property that the multi-user security is essentially as good as the single user security). Thus, this is great support for AES-GCM-SIV as a standard.

Conceptually, the reason why AES-GCM-SIV gets much better multi-user security than other modes is due to the continual key derivation that ensures that even if two users have the same key, the damage is minimal since they must also use the same IV in order to face a problem.

The authors also show that the ORIGINAL key derivation mode proposed for AES-GCM-SIV is actually good enough (i.e., simple key derivation via CTR mode, and without truncation). They say that it is more efficient, and this is true theoretically. However, practically, when using AES-NI, the cost of 2 additional encryptions for the key derivation is almost zero due to the pipeline (2 more cycles), and negligible even for reasonably small messages. Especially, since these are shadowed by the key expansion that is required in any case.

At the time, there were objections to the plain CTR derivation method, during the CFRG discussions (e.g., due to the fact that for 256-bit keys, this rules out the possibility of keys of the form K||K). Instead, an OCB style derivation was promoted. Subsequently, we ended up with the current truncated CTR method. We therefore propose to not change the key derivation method (again).

Thanks,

Shay, Adam and Yehuda