[Cfrg] Critique of AES-GCM-SIV

[Marko Kreen <[e-mail]>]

Hello CFRG!

I have reviewed the AES-GCM-SIV proposal (draft 3).  And while there
are parts I like - overall direction to higher security and
getting rid of GCM bitflipping - current design feels "ugly".
(That's a cryptographic term.)

Specifically, it is supposed to be Nonce-Misuse-Resistant mode.
That means even if nonce+key repeat, you get enough unpredictability
from message hash, so security does not fundamentally change.
Except it is now possible to detect if same message repeats.

But this does not apply to draft-03 version - if key+nonce repeat,
mode fundamentally changes - it uses fresh key and counter in one
case and only fresh counter other case.  That is ugly.

Instead it would be clearer (less ugly) if MAC(message) is always
used as extension of nonce.  They both affect counter.  Similarly,
either both affect encryption key or neither affects encryption key:

1) No rekey, only counter is synthesized - that would be basically AES-SIV
   with modern hash.  This would be strict improvement over AES-GCM,
   better security (but not too good), but same performance.

2) MAC(Plaintext) always affects encryption key.  This would give
   significantly better boundaries than just synthesized counter.
   But at the cost of extra keygen per message, which is slow for AES,
   so the mode will seem more costly than current AES-GCM.

While I like the current direction of AES-GCM-SIV of trying to achieve
higher security level by using rekey, I wonder if it would be
good to standardise a simple AES-POLYVAL mode like 1) that is also
clearly securitywise better than AES-GCM.  For use in new designs
that do care about maximum performance.  Just a thought.


To throw out some ideas on 2), here is my proposal how to synthesize
both key and counter based on MAC.


AES-GCM-SAFE
============

Cipher mode that uses key, nonce and MAC(message)
to synthesize both counter and encryption key.

Input:
  K = 128/256-bit key
  N = 128-bit Nonce
  P = plaintext
  A = additional data

Process:
  AuthKey = AES(K, N)
  SubKey1 = AES(K, N xor 1)
  RawTag = POLYVAL(AuthKey, PAD(A) || PAD(P) || LEN(A) || LEN(P))
  Tag = AES(K, N xor RawTag)
  Counter = AES(K, Tag)
  SubKey2 = AES(K, Tag xor 1)
  EncKey/128 = SubKey1 xor SubKey2
  EncKey/256 = SubKey1 || SubKey2
  CipherText = AES-CTR(EncKey, Counter, P) || Tag

Where:
  || - concat
  xor 1 - flip lowest bit of first byte
  LEN(V) - number of bits in V in 64-bit little-endian format
  PAD(V) - zero-pad to full block
  AES(K, V) - Encrypt V with key K
  AES-CTR(K, C, V) - Encrypt V with key K and counter C

Improvements

+ When key and nonce repeat, then same AuthKey is used.  But both
  counter and encryption key will be synthesized based on MAC.

+ EncKey is used only for encrypting plaintext, so no need to waste
  bits on domain-separation.  Thus full 128-bit counter can be used.

* There are no steps that need dropping bits so 128-bit nonce can
  be used.  As this is supposed to be high-security mode.

+ More natural 128/256-bit keygen for EncKey.  It's faster too
  due to less blocks encrypted. 

+ Counter is not sent in clear.  While sending counter in clear does
  not change probability of catastrophic failure, it does make
  exploiting it less expensive.

Notes

* If AES256 has related-key problems when only half of the key changes,

    EncKey/256 = (SubKey1 xor Counter) || SubKey2

  should fix it.  This may be also useful if shorter nonce is used.

* Its possible to use domain-separation for AES(K,N) vs. AES(K,Tag)
  but it does not seem necessary.

Comments?

-- 
marko