Re: [Cfrg] Adopting "AES-GCM-SIV: Nonce Misuse-Resistant Authenticated Encryption" as a CFRG document

[Andy Lutomirski <[e-mail]>]

On Apr 2, 2016 7:57 PM, "Adam Langley" <[e-mail]> wrote:
>
> On Thu, Mar 31, 2016 at 3:22 PM, Andy Lutomirski <[e-mail]>
wrote:
> > 4. Since this claims nonce-MR, setting nonce=0 is valid.  If someone
does
> > this, then I think they are vulnerable to the extra-easy parallel
attack.
>
> Ah, do you mean when the AES-GCM-SIV is used with a fixed nonce?
>
> In that case, it breaks down in the same way as AES-GCM with random
> nonces. We note that in the Security Considerations
> (https://tools.ietf.org/html/draft-gueron-gcmsiv-02#section-9):

I mean something different, but I read it a bit wrong.  If I understand
correctly, if AES256-GCM-SIV is used 128-bit keys, then you can only
encrypt with ~2^64 (key, nonce) pairs, even with different keys, before a
work factor ~2^64 attacker can decrypt one of them (which one is not under
their control).  This may not work if something prevents DJB's efficient
parallel attack from working.

With fixed nonce, the key derivation has no practical effect (as I said, I
read it wrong at first).  With *variable* nonce, the protocol no longer
works like the paper, so I don't believe the security proof works as is.