Subject: Re: [TLS] AAED ciphers: AES-GCM vs AES-EAX/AES-CCM: a meta-analysis

From: Peter Gutmann <[email-masked]>
Date: Wed, 24 Dec 2014 06:15:20 +0000

Michael Clark <[email-masked]> writes:

>I have been doing some independent research on TLS AEAD ciphers and decided
>to share a meta-analysis on AES-GCM versus AES-EAX/AES-CCM

If you're going to look at these, what about also looking at encrypt-then-MAC,
which is another AEAD mechanism?

Peter.

---

From: Michael Clark <[email-masked]>
Date: Wed, 24 Dec 2014 16:58:54 +0800

> which is another AEAD mechanism?

What prompted me to do the analysis of AEAD ciphers was this:

    https://www.imperialviolet.org/2014/12/08/poodleagain.html

"This seems like a good moment to reiterate that everything less than
TLS 1.2 with an AEAD cipher suite is cryptographically broken"

This statement isn't strictly true. Agreed. CBC mode with AD and MAC is
a form of AEAD.

I am aware CBC mode was vulnerable due to implementation bugs in the
handling of padding not just in SSLv3.0 but also more recently in a
particular TLS implementation.  However an encrypt-then-MAC AD plus
cipher text (with arbitrary MAC) is not strictly equivalent to an AEAD
cipher both from a layering perspective and from the collision proof of
cipher based MACs and design respect to padding; such as AEAD_AES_EAX
and AEAD_CHACHA20_POLY1305. AEAD_AES_GCM implementations had padding
bugs too (Fragility of AES-GCM, Gueron). I guess it's a layering issue
and a matter of pushing AEAD into the cipher.

I understand there is a difference in Cipher based MACs and PRF based
MACs which is the difference between birthday attacks and reversing
cipher rounds vs finding collisions.

Poly1305 has a similar proof to EAX as it is a cipher based MAC,
originally AES and now CHACHA20

http://tools.ietf.org/html/draft-agl-tls-chacha20poly1305-04

>From a protocol design perspective (irrespective of TLS) it would be
desirable to having AEAD at the one layer as it would allow for
specification and implementation simplicity and symmetry, rather than
have it duplicated at the TLS implementation layer for some ciphers and
not for AEAD ciphers e.g. AEAD_AES_GCM, AEAD_AES_CCM, AEAD_AES_EAX and
AEAD_CHACHA20_POLY1305, etc. There is no reason why TLS implementations
couldn't support TLSv1.2 to maintain CBC mode and just have AEAD
ciphers. If TLSv1.3 only supported AEAD ciphers then a TLSv1.3
implementation would be simpler. Simplicity and composability between
layers is a good property.

I also saw the post about removing the MAC from the TLS cipher names as
they are now included in "signature_algorithms" since TLSv1.2. This
makes a lot of sense. I am aware some of the earlier TLS "features" were
vestiges of "export controls" i.e. mechanisms to lower cipher strength
based on the the certificate. I remember the days of SGC...

However that brings me back to the point before about all of the current
AEAD ciphers have an 128 bit auth tag (due in part to their proof of
non-collision as cipher-based MACs). I don't think this is a major issue
due to the nonce lifespan; except for highly parallelizable AEAD schemes
such as AEAD_AES_GCM (for reasons I noted). Given proof of no
key-independent collisions, then the bit strength of cipher based MACs
must be higher than one-way hashes without no-collision proofs.

If I were to choose, I'd go for symmetry and start thinking about 256
and 512 bit blocks, so the AEAD tag would be extended this way. But that
is futures. We don't have the ciphers. These all have 128 bit tags:

    AEAD_AES_GCM
    AEAD_AES_CCM
    AEAD_AES_EAX
    AEAD_CHACHA20_POLY1305

Then we couldn't use SHA256 and SHA384 to mitigate attacks on data
integrity (tag collisions) in AAED ciphers.

In this case the super-symmetry would be to allow CBC style MAC optional
on AEAD ciphers and mandatory on non-AEAD ciphers like CBC.

AES_256_GCM + SHA256 would mitigate the integrity risk of 128-bit tags.
Thanks for prompting the thought. AES_256_GCM 128-bit tags may be more
vulnerable to integrity attacks (bit errors) than AES_256_CBC with
SHA384 MACs.

These would both have 384 bits tags (with a super symmetry design):

AES_256_GCM + SHA256
AES_256_CBC + SHA384

Michael.

---

From: Michael Clark <[email-masked]>
Date: Wed, 24 Dec 2014 21:12:41 +0800

>> which is another AEAD mechanism?

CBC is MAC-then-encrypt in TLS1.2, however encrypt-then-MAC is the
current best practice? encrypt-then-MAC allows you to verify message
integrity before decryption and abort sessions after a (small) error
count to mitigate any brute forcing over the wire (without cost of
decryption). With MAC-then-encrypt you need to decrypt before you can
verify the MAC.

Also from TLSv1.2 6.2.3.3. "No MAC key is used." with AEAD.

If you replaced MAC-then-encrypt with encrypt-then-MAC in TLSv1.3 then
you could alter the behavior of the new encrypt-then-MAC to make it work
for non AEAD ciphers like CBC as well to (optionally) augment the
message authentication bits for AEAD ciphers that are currently limited
to 128 bits. I'm not talking about the common case where AES_128_GCM and
128-bit tags is a good start for SSL everywhere. I'm talking about cases
where the overhead of 3 passes may be acceptable. Also consider this a
pencil sketch. Of course servers that want to maintain backwards
compatibility would need to keep encrypt then Mac. These are just ideas.

A TLSv1.3 ClientHello and ServerHello extensions could advertise
something like this this:

enum { AuthBits128, AuthBits256, AuthBits384, AuthBits512}
MessageAuthenticationBits;

struct {
  MessageAuthenticationBits minimum_authentication_bits;
  MessageAuthenticationBits preferred_authentication_bits;
} MessageAuthSecurity;

The client and server choose a MacAlgorithm based on the combination of
the negotiated cipher's authentication tag bits (0 bits for non AEAD
ciphers) and the bits of the mac algorithms present in
SecurityParameters.mac_algorithms. A (null) MacAlgorithm may be chosen
if the cipher's AEAD tag bits meets the minimum or preferred
authentication bits or a suitable MacAlgorithm could be chosen to
provide the remaining bits. For non AEAD ciphers a MacAlgorithm would be
chosen that matches the minimum or preferred authentication bits. The
policy over the the choice of minimum or preferred message
authentication bits would need to be considered.

A negotiated MessageAuthenticationBits message_authentication_bits could
be added to the TLSv1.3 SecurityParameters along with MACAlgorithm
mac_algorithm which may or may not be (null) with an AEAD cipher.

If the client or server wanted 128 message authentication bits:

* AEAD cipher with 128 bit auth tag, (null) MacAlgorithm and no
encrypt-then-MAC at the TLS layer. AD would be be passed to the AEAD cipher.

* non AEAD cipher, hmac_sha128 with encrypt-then-MAC at the TLS layer.
AD would be prefixed in the MAC in the TLS layer encrypt-then-MAC when a
non AEAD cipher was used (currently the MAC is a suffixed in the
MAC-then-encrypt scheme in TLSv1.2).

If the client or server wanted 256 message authentication bits

* AEAD cipher with 128 bit auth tag, hmac_sha128 MacAlgorithm with
encrypt-then-MAC at the TLS layer. AD would be be passed to the AEAD cipher.

* non AEAD cipher, hmac_sha256 with encrypt-then-MAC at the TLS layer.
AD would be prefixed in the MAC in the TLS layer encrypt-then-MAC when a
non AEAD cipher was used (currently the MAC is a suffixed in the
MAC-then-encrypt scheme in TLSv1.2).

This is based on the observation that SHA1 is being phased out; however
it may well be that based on the nonce lifetime this is not needed. That
said some applications may like the idea of having Cipher based MAC in
an AEAD cipher combined with a PRF based MAC as they both have different
properties

And when I refer to the collision properties of Cipher based MACs I'm
referring to one block of course (the size of the tag).

Michael.

---

From: Michael Clark <[email-masked]>
Date: Thu, 25 Dec 2014 09:01:24 +0800

Hi Peter,

Someone pointed out RFC 7366 to me off list. I will read. I like the
idea of encrypt-then-MAC being a core requirement for TLSv1.3.

Before I've read through can we do this with it?

AES-256-GCM + hmac_null   = 128 bits authentication
AES-256-CBC + hmac_sha128 = 128 bits authentication

AES-256-GCM + hmac_sha128 = 256 bits authentication
AES-256-CBC + hmac_sha256 = 256 bits authentication

AES-256-GCM + hmac_sha256 = 384 bits authentication
AES-256-CBC + hmac_sha384 = 384 bits authentication

I like the idea of >= 256 bits authentication, and the idea of the
combination of a cipher based MAC and PRF based MAC for AES-GCM, given
the properties of the AES-GCM CTR mode 'variant' and GHASH GF(2^128).

Michael.

On 24/12/14 2:15 pm, Peter Gutmann wrote:
> _______________________________________________
> TLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tls
>

---

From: Michael Clark <[email-masked]>
Date: Thu, 25 Dec 2014 09:34:16 +0800

The other point being to remove MAC-then-encrypt from TLSv1.3, not
necessarily AES-CBC (as its non parallelism is a good property in
certain situations).

The principle is considering TLSv1.3 from a 'profile' perspective and
that the 'known problematic' MAC-then-encrypt could be supported by
implementations that choose to offer TLSv1.2 (and older) profiles and
drop encrypt-then-MAC and make MAC-then-encrypt mandatory in the TLSv1.3
profile. i.e. a clean up, and improvement to auth integrity.

The principle being we shouldn't preserve back compatibility by
incorporating old baggage into to the new spec, rather have a design
that allows implementations to support older profiles.

This would make the spec simpler. TLsv1.3 would be completely
encrypt-then-MAC including the ability to augment AEAD ciphers with more
authentication bits. i.e. symmetrical (except for a special case of
hmac_null where the auth bits equals the tag bits of the AEAD cipher and
how the AD is handled for encrypt-then-MAC with an AEAD cipher).

my 2 cents.

---

From: Michael Clark <[email-masked]>
Date: Thu, 25 Dec 2014 09:36:38 +0800

> drop encrypt-then-MAC and make MAC-then-encrypt mandatory in the TLSv1.3

correction:

drop MAC-then-encrypt and make encrypt-then-MAC mandatory in the TLSv1.3

---

From: Watson Ladd <[email-masked]>
Date: Wed, 24 Dec 2014 20:57:00 -0500

> idea of encrypt-then-MAC being a core requirement for TLSv1.3.

And we have already made AEAD modes a requirement in the TLS 1.3
draft. I don't see the argument for adding RFC 7366 in addition to
these.
> the properties of the AES-GCM CTR mode 'variant' and GHASH GF(2^128).

I don't agree with this analysis.

For starters, GCM is not a PRF based authenticator. The security of
GCM authentication decreases with the length of the message, while the
security of HMAC authentication does not, while the numbers above
don't recognize this.

Secondly, attacks on authentication have to be online, and a failed
guess results in connection teardown. An attacker with a 2^{-64}
probability of forgery on any given connection would take decades to
inject data into a TLS connection, even if the connection restarted 1
million times a second.  By contrast, recovering data from a key 64
bits in length is a rather easy computation today, and will be easier
tomorrow.

Thirdly, the weak keys of GCM are a red herring. Using the logic of
those papers, every GCM key is weak, as there is a known difference
between messages that will lead to a forgery if a given key is used.
One could make the same argument against CBC-MAC: if an attacker knows
the key, they can produce forgeries.

Fourthly, this ignores performance. Recent Intel chips have a
significant amount of acceleration for AES-GCM that cannot be used for
other modes. The parallelism of CTR mode permits hiding the latency of
the AES instructions, while the carryless multiply can't accelerate
HMAC. It also ignores implementation complexity: making two passes
over the data, with different algorithms, is more complex than one.

In short, there are no real security gains from this proposal. But
there are large losses in simplicity and performance, as now the
existing record layer transformations have to be redesigned and
stacked in ways they aren't currently. One can't say "such and such an
algorithm has more bits, therefore it is more secure". You have to
look at the exact claims, and see how they apply to the way the
algorithms are used.

Sincerely,
Watson Ladd

-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin

---

From: Michael Clark <[email-masked]>
Date: Thu, 25 Dec 2014 10:38:08 +0800

> security of HMAC authentication does not, while the numbers above

This is kind of my point. There is broken MAC-then-encrypt for non AEAD
ciphers and AEAD ciphers with 128-bit tags where the authentication
decreases with the length of the messages (non PRF based MACs based on
finite fields).

> bits in length is a rather easy computation today, and will be easier

Sorry I don't have numbers, however if you are attacking a target where
you know the message length of a oft repeated transaction and have a
128-bit GCM auth tag (theoretically ~64-bits strength if you have
captured texts) then there is a possibility you could forge auth tags.
DHTs are fast and disks are cheap. There may be some facilities that
have 100 million threads and more drives (if you knew Intel's order
book). I say dictionary lookup would be feasible within the next few
years which has to be the time domain that is considered. sha1 is being
deprecated elsewhere. Sure people have more time to attack CA certs.

> over the data, with different algorithms, is more complex than one.

I understand. I've read the code. I am aware of the properties of
GF(2^128) finite fields. There are all arguments for performance and
scary when it comes to the potential to forge tags for larger messages.
There is huge parallelism potential in AES-GCM. I know software
implementations with AES-NI are doing 4 blocks but the potential is not
limited to 4 blocks.

> look at the exact claims, and see how they apply to the way the

I see it a different way. hmac_null plus AEAD_AES_GCM allows for the
current level of integrity. The addition of a PRF based MAC provides
more message integrity. No doubt. I can't see a good argument against an
option for more integrity if a user wants it. I'm always worried by
people who trust the level of integrity in algorithms that have
deliberately sacrificed security for performance (32-bits less entropy
in IV, not following CTR IV method, along with GCM's parallel GHASH and
the properties of GF(2^128). This is all for speed. Good for a
SSL-everywhere plain text replacement. Fine for Facebook and Google
search. I'm sure the banks wouldn't trust it. Anyway, they have external
factors to mitigate flaws in TLS.

Consider it like insurance. The 'option' of adding authentication bits
with a PRF gives you *added* integrity that does not decrease based on
message length. It's up to a server whether it is used or not. I'm not
making any argument about what are good defaults, just an option for
more integrity.

We will have to agree to disagree. I don't trust AES_GCM given my read
of the spec. I noticed a shift towards better properties of prime sized
fields GF(P) and GF(2^p); where p is prime. It's a fallacy to trust the
security of AES_GCM when there are known weaknesses. We don't have to do
any math to know that adding integrity with a PRF based MAC would
mitigate future flaws in AES_GCM. i.e. reserve.

---

From: Ilari Liusvaara <[email-masked]>
Date: Thu, 25 Dec 2014 06:12:44 +0200

> deprecated elsewhere. Sure people have more time to attack CA certs.

Without side-channel leakage, nonce reuse or breaking AES, you simply
don't have enough information to tell the correct answer from wrong ones
(128 bits remain arbitrary). So you can't bruteforce the keyspace
offline.

(The similar goes for Chacha20-Poly1305 (modulo Chacha20)).

-Ilari

---

From: Yoav Nir <[email-masked]>
Date: Thu, 25 Dec 2014 08:50:44 +0200

> On Dec 25, 2014, at 3:01 AM, Michael Clark <[email-masked]> wrote:

<snip />

> the properties of the AES-GCM CTR mode 'variant' and GHASH GF(2^128).

Why? Why do you want 256-bit or more message authentication?

There is value in making encryption and key agreement more secure. There is great value to attackers in recording a session and later breaking the encryption or the key agreement. Breaking the message authentication after the TLS session has terminated provides no value to the attacker. Messages need to be forged online for the attack to be successful. 

So bit lengths whose only justification is being future-proof for 30 years are not relevant for message authentication. Even for encryption, where there is value in after-the-fact breakage, the BCP being written in UTA recommends 128-bit AES rather than 256-bit.  ChaCha20 uses a 256-bit mostly because of the nature of the algorithm. It would not be any faster if the key was reduced to 128-bit. The same is not true for your proposals.

Yoav