Subject: [Cfrg] Critique of AES-GCM-SIV

From: Marko Kreen <[email-masked]>
Date: Fri, 17 Feb 2017 02:02:47 +0200

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

---

From: Daniel Bleichenbacher <[email-masked]>
Date: Fri, 17 Feb 2017 11:00:56 +0100

On Fri, Feb 17, 2017 at 1:02 AM, Marko Kreen <[email-masked]> wrote:

> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>

I have problems to see how this proposal is safe.
I.e. Cooley used that POLYVAL returns 0 if A and P are empty in the
AES-GCM-SIV cryptanalysis.
In the proposal above using A="" and P = "" results in
Tag = AES(K,N)
Therefore an attacker can use the proposal above as an oracle to for
encrypting single blocks with K.
This is all that is needed to break the proposal.
Hence it seems to me that even a nonce respecting adversary can break this
proposal.

I actually don't know what "ugly" means as a cryptographic term.
My guess would something like difficult to formally analyze.
E.g. in the proposal above if N and N xor 1 are both used as nonces then
AuthKey and SubKey1 change their role and that seems to add a lot of
complexity
to a potential analysis.

---

From: Marko Kreen <[email-masked]>
Date: Fri, 17 Feb 2017 14:52:55 +0200

> I actually don't know what "ugly" means as a cryptographic term.

Well, it was supposed to be a joke...

> My guess would something like difficult to formally analyze.

But I think we are mostly on same page.  My main complaint was that
if it's nonce-misuse-resistant mode, then why does nonce misuse
have such a big effect on behaviour: on one case message is protected
by fresh key and counter, on other case only fresh counter.

So nonce misuse makes it behave as different mode that needs to
be analyzed separately.

> AuthKey and SubKey1 change their role and that seems to add a lot of

But they are used for completely different algorithms?  If such
cross-algorithm usage is exploitable, it seems to mean both
algorithms are unexpectedly weak and should not be used?

Still, it should be simple to fix it.

> Hence it seems to me that even a nonce respecting adversary can break this

Thank you for your review.  Funny thing is that I was rather unsure
about xor N part when encrypting RawTag, but then I simply copied
what current AES-GCM-SIV does.

But main thing I take from your comment is that encrypting with K
does need domain separation between public and private values.

Here is draft 2 of AES-GCM-SAFE with following changes:
- remove xor 1, instead use recursive encryption
- remove xor N when encrypting RawTag
- spent 1 bit to separate public and private encryptions with K.
- add xor N to SubKey2 to keep all nonce bits in play.
- add AuthIV to get rid of special cases of zero-len and zero-filled
  data for POLYVAL.

AES-GCM-SAFE (draft 2)
======================

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

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

Where:
  || - concat
  SetBit(v, bit) - set low bit value

I don't see the need to separate internal encryptions, but than means
any of (AuthKey, AuthIV, SubKey1, SubKey2, Counter) may be equal.  It seems
like a good thing - less constrants for attacker to expoit.

Your thoughts?

-- 
marko

---

From: Aaron Zauner <[email-masked]>
Date: Fri, 17 Feb 2017 16:23:16 +0200

> On 17 Feb 2017, at 14:52, Marko Kreen <[email-masked]> wrote:
> 

Quick comment: This came up in an earlier thread on that topic already, I've also brought it up last spring. I think for this I-D in it's current form "nonce misuse resistant" might not be the best term (too strong, many people assume you can do what you want with the nonce with such a construction -- which certainly isn't the case for AES-GCM-SIV as proposed here). "nonce-misuse tolerant" came up and other suggestions. I haven't seen an update yet.

Aaron

---

From: Marko Kreen <[email-masked]>
Date: Fri, 17 Feb 2017 17:05:18 +0200

On Fri, Feb 17, 2017 at 04:23:16PM +0200, Aaron Zauner wrote:
> Quick comment: This came up in an earlier thread on that topic
> already, I've also brought it up last spring. I think for this I-D in
> it's current form "nonce misuse resistant" might not be the best term
> (too strong, many people assume you can do what you want with the
> nonce with such a construction -- which certainly isn't the case for
> AES-GCM-SIV as proposed here). "nonce-misuse tolerant" came up and
> other suggestions. I haven't seen an update yet.

I'm not complaining about security level as their goal is to replace
AES-GCM, so anything better is a win.

Although better categorization may be good idea, I still feel current
approach can be categorized as "clumsy":

- AEAD with synthesized key and IV when master key or nonce are unique.
- AEAD with only synthesized IV when master key and nonce repeat.

Clearer would be just one mode which does not change category if nonce
repeats:

- AEAD with just synthesized IV (like AES-SIV), no rekey.
- AEAD with synthesized key and IV.

If there is already decision that rekey is OK, then I think it's better
to take time and synthesize both key and IV properly, thus
achieve full nonce misuse resistance.

-- 
marko