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

[Stefano Tessaro <[e-mail]>]

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
<[e-mail]> 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
> [e-mail]
> https://www.irtf.org/mailman/listinfo/cfrg
>



-- 
Stefano Tessaro
Assistant Professor of Computer Science
University of California, Santa Barbara
http://cs.ucsb.edu/~tessaro/