Re: [Cfrg] I-D Action: draft-irtf-cfrg-gcmsiv-03.txt

Shay, Adam and Yehuda,

There are 2 things I hope to discuss in this email below.

1) The draft said that "We recommend a limit of 2^50 plaintexts encrypted with a given key. Past this point, AES-GCM-SIV may be distinguishable from an ideal AEAD.  (This is based on standard assumptions about AES.)".

To keep the probability of having a collision among 128-bit blocks in the ciphtertexts below 1/2^32 (practically zero), it has been suggested that under a given key, the amount of ciphertexts is not more than 2^48 128-bit blocks for the GCM in TLS 1.3.

With 2^50 plaintexts (equivalent amount of ciphertexts) and each ciphertext can be up to 2^32 128-bit blocks in the GCM-SIV draft, there can be collision situations.

A. When the ciphertext size is only 1 128-bit block, the probability for a collision is already higher than 1/2^32.

B. The probability for a collision gets bigger when the size of a ciphertext gets bigger.

With the GCM-SIV, the collision issue is under multiple AES encryption keys when the corresponding nonces are unique which is different from the collision situation described at the beginning for the GCM in TLS 1.3 which is under only one key.

I can't think of a damage to the data owner who sends their encrypted data over a TLS session caused by collision(s) among 128-bit blocks of the ciphertexts. So, I don't have an opinion here.

2) The draft said that " However, we feel that the 2^32 limit for AES-GCM is too risky in a multi-key setting.  Thus with AES-GCM-SIV we recommend that, for a specific key, a nonce not be repeated more than 2^8 times.  (And, ideally, not be repeated at all.)" .

Currently, the GCM with 96-bit random nonces situation, NIST requires the number of encryptions to be not more than 2^32, so that the probability of a repeat of a pair (key and nonce) is below 1/2^32, under a given key.

With m keys, the probability for a repeat of a pair of (key and nonce) is about m/2^32.

Therefore, it is best to use  96-bit counter-nonces for GCM.

With the GCM-SIV, when a nonce is repeated 2^8 times, the AES-128 encryption key is repeated 2^8 times. The 96-bit nonces for the AES counter mode encryption are practically (pseudo)-random nonces (derived from plaintexts and the master key). The probability for a repeat of a pair of (key and nonce) is about 2^16/2^96 = 2^(-80).

If someone cares about the multi-key situation such as the amount of keys being 2^50 (2^50 sessions),  call the number of sessions 2^x, the probability for a repeat of a pair of (key and nonce) is about 2^(x - 80).

The actual break happens when a pair of (key and nonce) repeats AND at least one 32-bit counter value also repeats with this pair. This problem happens  with 100% chance when the ciphertext size is (2^31 + 1) 128-bit blocks or larger.

Call the size of a ciphertext 2^y 128-bit blocks, the probability for having at least one 32-bit counter value to repeat is about 2^(y + 1)/2^32 = 1/2^(31 - y) = 2^(y - 31).

So, the number 2^(x - 80) x 2^(y - 31) = 2^( x + y - 111) must be not greater than 2^(-32) in order to keep the probability for a complete break to be below 2^(-32).

2^( x + y - 111) <= 2^(-32)   <==>  x + y <= 79.

When y = 32, x <= 79 - 32 = 47.

So, when plaintext/ciphetext size is 2^32 128-bit blocks, the GCM-SIV might be not good enough for 2^47 (or more) sessions when each session has 2^8 repeated nonce if a user's objective is to protect all of those 2^47 (or more) sessions.

In short, this condition "x + y <= 79" should be respected for the current GCM-SIV: draft 3 when the mode is used to protect a large number of sessions (multiple users).

To protect a lot more than 2^47 sessions when the ciphertext size is about 2^32 128-bit blocks, maybe it would be good to require that nonce must not be repeated. A specific number of repetitions of a nonce allowed can be derived from each pair of x and y if desired.

Best,

Quynh.

________________________________
From: Cfrg <cfrg-bounces@irtf.org> on behalf of internet-drafts@ietf.org <internet-drafts@ietf.org>
Sent: Wednesday, January 18, 2017 12:30:31 PM
To: i-d-announce@ietf.org
Cc: cfrg@ietf.org
Subject: [Cfrg] I-D Action: draft-irtf-cfrg-gcmsiv-03.txt

A New Internet-Draft is available from the on-line Internet-Drafts directories.
This draft is a work item of the Crypto Forum of the IETF.

        Title           : AES-GCM-SIV: Nonce Misuse-Resistant Authenticated Encryption
        Authors         : Shay Gueron
                          Adam Langley
                          Yehuda Lindell
        Filename        : draft-irtf-cfrg-gcmsiv-03.txt
        Pages           : 45
        Date            : 2017-01-18

Abstract:
   This memo specifies two authenticated encryption algorithms that are
   nonce misuse-resistant - that is that they do not fail
   catastrophically if a nonce is repeated.

The IETF datatracker status page for this draft is:
https://datatracker.ietf.org/doc/draft-irtf-cfrg-gcmsiv/
draft-irtf-cfrg-gcmsiv-02 - datatracker.ietf.org<https://datatracker.ietf.org/doc/draft-irtf-cfrg-gcmsiv/>
datatracker.ietf.org
AES-GCM-SIV: Nonce Misuse-Resistant Authenticated Encryption (Internet-Draft, 2016)

There's also a htmlized version available at:
https://tools.ietf.org/html/draft-irtf-cfrg-gcmsiv-03

A diff from the previous version is available at:
https://www.ietf.org/rfcdiff?url2=draft-irtf-cfrg-gcmsiv-03

Please note that it may take a couple of minutes from the time of submission
until the htmlized version and diff are available at tools.ietf.org.

Internet-Drafts are also available by anonymous FTP at:
ftp://ftp.ietf.org/internet-drafts/

_______________________________________________
Cfrg mailing list
Cfrg@irtf.org
https://www.irtf.org/mailman/listinfo/cfrg