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

[Adam Langley <[e-mail]>]

On Wed, Jan 18, 2017 at 3:46 PM, Brian Smith <[e-mail]> wrote:
> The intro defines nonce-misuse-resistant AEADS as ones that are
> safe(r) to use when "two distinct messages are encrypted with the same
> nonce". However, in reality we usually don't care only about the case
> where *two* (==2) distinct messages are encrypted with the same (key,
> nonce), but rather we care about the case where *multiple* (>=2)
> messages are encrypted with the same (key, nonce). In particular the
> new draft makes a distinction between encrypting <2^8 vs >=2^8
> messages with the same (key, nonce), not a distinction between 1 vs 2
> messages with the same (key, nonce).

You're correct that the problem is multiple messages (potentially)
encrypted with the same (key, nonce) pair. But the number is very
small since the number of random nonces that need to be sampled from a
96-bit space in order to expect at least one to appear > x times,
rises *very* fast with x. As noted in the draft, for x=256, it's about
2^102.

The main thrust of that section in the spec is to say "pick nonces at
random". The 2^8 number was picked out of the aim to emphasize this
over fixing a specific nonce and not encrypting too many messages.

> The practical motivation for POLYVAL is unclear. In an email message
> in an earlier mailing list thread, Shay said "We chose to use POLYVAL
> so that 128-bit blocks can be viewed as field elements and as AES
> ciphertexts in a consistent way (with respect to the order of the bits
> inside each byte))," and I think that this should be included in the
> spec, along with a more plain explanation that this is done (IIUC)
> simply to avoid byte byteswapping on little-endian systems that GHASH
> requires.

I'll let Shay add something about this if he wishes, but I think the
bit ordering in GHASH is weird and it''s not just a big/little endian
thing. I know, having spoken to other people who have dealt with
GHASH, but I'm not unique in this either.

POLYVAL straightens this out :)

> It isn't clear how the nonce length of 96 bits was chosen. I can see
> some advantages, e.g. it is more of a drop-in replacement for AES-GCM,
> which is almost exclusively used with 96-bit nonces in IETF protocols,
> but is there any other reason?

It used to be 128 bits, but we wanted to change the KDF to use counter
mode. Thus we needed three bits for the counter. However, a 125-bit
nonce would be too weird so we rounded down to 96 bits.

An analysis of the probabilities of repeats shows that, even with 96
bits, there is a vast security margin so we're happy with that length.

> The email also said "We now generate keys by using counter mode and
> discarding half of each ciphertext block." The motivation for
> discarding half of each ciphertext block should be added to the draft
> (maybe in security considerations), along with a reference of how
> discarding half of each ciphertext block achieves that goal.

Agreed and I'm hoping that a more concrete comparison of how the new
KDF affects the bounds will come from Shay and Yehuda soon :)

> The draft makes an argument about safety when "nonces are selected
> uniformly at random." However, isn't a key motivation for AES-GCM-SIV
> our lack of confidence in our ability to select nonces uniformly at
> random?

No. The motivation is that selecting nonces at random with AES-GCM
isn't very comforting. NIST recommends a limit of 2^32 plaintexts for
a given key in this case, and that still has a 2^-33 chance of serious
failure.

> I personally would like to see discussion of the case where we
> can't assume nonces are selected uniformly at random. (While I can't
> come up with one off the top of my head right now, it seems likely
> that there would be simpler and less invasive ways of defining a
> nonce-misuse-resistant AEAD based on AES-GCM if we can also assume we
> have a good random number generator and we're willing to accept the
> birthday bound analysis in the draft. Thus, based on intuition it
> seems like AES-GCM-SIV must be useful in contexts where nonces aren't
> chosen uniformly at random in order to justify its complexity.)

Off the top of my head, I think we would need a cipher with a 256-bit
block in order for a scheme that doesn't depend on nonces being
(mostly) distinct to have comfortable security margins. AES-GCM-SIV is
not such a scheme.


Cheers

AGL

-- 
Adam Langley [e-mail] https://www.imperialviolet.org