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

[Marko Kreen <[e-mail]>]

On Fri, Feb 17, 2017 at 11:00:56AM +0100, Daniel Bleichenbacher wrote:
> On Fri, Feb 17, 2017 at 1:02 AM, Marko Kreen <[e-mail]> wrote:
> > 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.)

> 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.

> 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.

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.

> > Comments?

> 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.

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)
======================

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, 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
  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

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