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

From: Michael Clark <[email-masked]>
Date: Sat, 20 Dec 2014 16:52:53 +0800

Hi folks,

Please bear with me as I am a new to the list.

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
based on the literature and propose considering the addition of AES-EAX
to augment TLS security and mitigate against potential future security
attacks on AES-GCM. AES-GCM is currently the only widely implemented
TLS AEAD cipher. AEAD is now considered essential. AES-CCM is specified
but implementations are not widespread (rfc5116, rfc6655). AES-EAX
documents improvements to AES-CCM. In fact the EAX2 framework would
allow AAED with other ciphers.

I apologize if this has already been raised and dismissed. Here goes
my series of bullets.

AES-GCM vs AES-EAX/AES-CCM: Performance vs Scale vs Security

- AES-GCM GHASH, AES-EAX OMAC1/CMAC and AES-CCM CBC-MAC AEAD
  auth tags are all 128 bits (except for CCM-8 which is 64 bits)

- EAX OMAC1/CMAC (sp800-38b) addresses security issues in CCM CBC-MAC
  (CBC-MAC is secure only for fixed-length messages)

- GCM has weak keys. Choose an irreducible polynomial over a finite
  field; GF(2ⁿ); where n ≠ 128; preferably prime; observe n = 127;
  (Saarinen GHASH weak keys)

- GCM use a 96 bit IV prefix expanded from the nonce suffixed with
  a 32 bit counter per AES block (gcm-spec)

- EAX/CCM uses full IV expanded from nonce as the initial counter so
  cycling of IV is 2 ^ (n - 32) less frequent than GCM (sp800-38a)

- GCM has a 256GB upper limit on encryption due to incrementing only 32
  bits of the IV versus the whole IV in CTR mode (gcm-spec, sp800-38a)

- GCM has 32 bits less entropy from the nonce in the IV vs EAX/CCM
  due to counter construction difference from CTR (sp800-38a)

- Posit lower IV entropy combined with GHASH weak keys increases the
  susceptibility of introducing bit errors and forging an AEAD tag

- Cipher based CBC-MAC and OMAC1/CMAC with AES are birthday attack
  vulnerable at 2 ^ 64 blocks with known texts (MAC birthday paradox)

- Posit birthday MITM attack on EAX/CCM cipher based MAC are
  infeasible due to short nonce lifespan in TLS, assuming secure
  master secret for the PRF and termination of connections on
  authentication errors. TLS has different attack characteristics
  compared to generic MITM attacks on CCM in WPA2, IPSec and 802.11i
  as TLS is connection oriented and the nonce is derived from an
  ephemeral shared secret versus a pre shared key.

- GCM GHASH based AAED is high performance because GHASH partial
  products can be parallelised and xor reduced over multiple blocks
  (parallel ghash partial products)

- Posit that parallelizability in AES-GCM is a weakness not a strength.
  Many GCM ‘features’ exist because GCM was designed to be fast i.e.
  parallelizable in hardware. Performance also assists those with
  government level resources. GCM is highly parallelizable, has
  32 bits less IV entropy, auth tag is limited to 128 bits and there are
  2 ^ 9 multiplicative subgroups of GF(128) (Saarinen GHASH weak keys)
  While it may not be tractable to break the encryption; it may be
  tractable to introduce bit errors and forge authentication tags by
  substitution of 1 or more AES blocks i.e. disrupting integrity.

- EAX addresses variable size nonce, alignment, in-place operation,
  algorithm complexity and streaming issues over CCM at the expensive
  of a small per message overhead. (eax spec)

- EAX has a security proof and is not vulnerable to the attacks on
  the ANSI EAX’ (EAXPrime) variant; given a securely established nonce.
  EAXPrime for the sake of optimization removed essential EAX security

- EAX is the only AES mode besides GCM that has variable size nonce
  and AAED. i.e. is an exact drop in replacement for GCM (excluding
  patent encumbered single pass schemes like OCB)

- The CCM-8 scheme (rfc6655) only provides for an 8-octet or 64 bit tag
  This would be potentially more vulnerable to message forgery attacks.

- Scalability. EAX/CCM have lower memory usage than table based GCM

- Simplicity. EAX appears to be less complex than CCM. CCM has various
  AD and nonce length, prefix and alignment requirements (sp800-38c)

- AES_GCM vs AES_EAX. Credit (Bellare, Rogaway, Wagner)
  http://www.cs.berkeley.edu/~daw/talks/FSE04eax.ppt

Please attack my logic.

*** In Summary ***

The NIST approved CCM mode is not a drop replacement for GCM as it
does not support fully variable length AD and nonce and does not
support streaming due to its length prefix and alignment requirements.

EAX mode was designed expressly to address flaws and limitations in CCM
(sp800-38c, rfc5116, rfc6655) and offers most of the advantages of GCM
besides parallelizability. EAX can act as a drop in replacement for GCM
as its parameters and output size are equivalent to GCM.

The choice of a CCM mode for TLS (rfc5116, rfc6655) may be unrelated to
the benefits of EAX; which address flaws in CCM; rather are likely due
to the status of CCM being NIST approved. In terms of performance, EAX
varies only slightly in per message overhead compared to CCM, however
EAX is simpler, more flexible and supports streaming and variable sized
nonce. Standardization and security as we know are uncorrelated.

AES-EAX software implementation would have performance approximately
equivalent to AES-CCM and ~0% to ~70% less performance than AES-GCM
depending on GCM acceleration technique however AES-EAX has the
advantage that it is the simple to implement. EAX requires two AES
cipher encrypt operations per block with low memory overheads. GCM
has one encrypt per block and a GHASH computation which can consume
considerable memory per connection with table based GHASH approaches.

Non table based GCM GHASH implementations in software that conserve
memory are slow. Table based GCM implementations require more key
setup time than EAX and use more memory. EAX is well suited to low
memory environments and for servers where number of connections is
more important than single stream performance.

EAX cipher based MAC also benefits from AES acceleration primitives
such as those on available on recent Intel, ARM and Sparc. Concurrency
can ameliorate performance concerns in manycore architectures; versus
optimizing single stream performance using parralelization. With
AES-NI, EAX performance should be in the order of 5Gbps to 10Gbps per
core on modern Intel CPUS.

Ideas for TLSv1.3; dropping CCM-8 (rfc5116) and either preserving the
widely unimplemented CCM mode (rfc6655) and/or adding EAX mode as an
AAED alternatives to GCM. The principle being to reserve EAX/CCM as
AAED alternatives to GCM in a putative case where GCM weak keys and
parallelizability lead to a future GCM attack; in addition lowering
memory requirements (adding scalability). The CCM-8 (rfc6655) schemes
seem to offer less authentication value and could perhaps be removed.

So propose to either add these (forward secrecy only):

      CipherSuite TLS_DHE_RSA_WITH_AES_128_EAX_SHA256
      CipherSuite TLS_DHE_RSA_WITH_AES_256_EAX_SHA384
      CipherSuite TLS_DHE_DSS_WITH_AES_128_EAX_SHA256
      CipherSuite TLS_DHE_DSS_WITH_AES_256_EAX_SHA384
      CipherSuite TLS_ECDHE_RSA_WITH_AES_128_EAX_SHA256
      CipherSuite TLS_ECDHE_RSA_WITH_AES_256_EAX_SHA384
      CipherSuite TLS_ECDHE_DSS_WITH_AES_128_EAX_SHA256
      CipherSuite TLS_ECDHE_DSS_WITH_AES_256_EAX_SHA384

and/or retain these (forward secrecy only):

      CipherSuite TLS_DHE_RSA_WITH_AES_128_CCM_SHA256
      CipherSuite TLS_DHE_RSA_WITH_AES_256_CCM_SHA384
      CipherSuite TLS_DHE_DSS_WITH_AES_128_CCM_SHA256
      CipherSuite TLS_DHE_DSS_WITH_AES_256_CCM_SHA384
      CipherSuite TLS_ECDHE_RSA_WITH_AES_128_CCM_SHA256
      CipherSuite TLS_ECDHE_RSA_WITH_AES_256_CCM_SHA384
      CipherSuite TLS_ECDHE_DSS_WITH_AES_128_CCM_SHA256
      CipherSuite TLS_ECDHE_DSS_WITH_AES_256_CCM_SHA384

Lest we put all out eggs in one basket with respect to authenticating
all encryption with GHASH. If one of these AEAD schemes is exploited
then servers could mitigate by changing cipher advertisement.
Performance shouldn't be the only consideration.

I am unaffiliated and am just curious why CCM is in TLS (rfc5116,
rfc6655) and EAX isn't. EAX appears to have some better properties
compared to CCM based on an analysis of the current literature.

Q. Besides performance analysis, has anyone done a formal analysis
   on the difference in eavesdropping and forgery potential between
   AES-GCM and AES-EAX/AES-CCM?

regards,
michael

---

From: Tapio Sokura <[email-masked]>
Date: Sat, 20 Dec 2014 20:21:05 +0200

Hello,

>       CipherSuite TLS_ECDHE_DSS_WITH_AES_256_CCM_SHA384

A bit off-topic on the actual question, but: Is DSS used anymore? Should
these be ECDSA instead?

  Tapio

---

From: Michael Clark <[email-masked]>
Date: Sun, 21 Dec 2014 08:19:12 +0800

> A bit off-topic on the actual question, but: Is DSS used anymore? Should

Thanks. Yes. I did mean ECDSA, the eliptic curve variant of DSA (DSS).
It was a mistake on my part.

Someone mentioned off list mentioned the AEAD ChaCha20-Poly1305 draft,
however I note the authenticator is still 16 bytes (128 bits). I had
seen the draft but wasn't sure if it was going to be included in TLSv1.3.

It occurred to me that a (perhaps not fair) comparison would be with
using MD5 which is 128 bits. MD5 has collisions. GHASH finite field and
the cipher based MACS (including Poly1305) should be safe in this regard
due to their construction. My understanding is that cipher based MACS
are vulnerable to attacks that reverse rounds of the cipher after a
certain number of texts have been seen (birthday attack). The fact that
the nonce has a short lifetime probably makes this intractible however I
began wondering about the 'designed in' lower entropy in GCM (IV suffix
on first block 32-bits starting at 0x00000001 versus incrementing the
whole IV and preserving entropy). Both this; and properties of the
parallelizability GHASH construction. The IV construction effectively
means only 96 bits need to be brute forced to forge an authenticator
(unless in practice a random initial counter was used) as we know the
counter for each block. It seems to be a designed in weakness along with
excellent parallelizability. CCM and EAX are not exploitable in this manner.

The main point was besides eavesdropping potential, was the ability of
an attacker to inject random bit errors by finding authenticator
collisions; i.e. message integrity; and also the parallelizability of
GCM. Parallelizability lowering the barrier to anyone with sufficient
resources. AES-GCM and AES-CCM are the only two implemented AEAD
ciphers. The later is not present in openssl, boringssl, libressl (last
time I looked).

The thought that occurred to me was the idea of having a 256-bit
authenticator with a 256-bit cipher. In practice we use 256-bit and
384-bit MACs. It's whether we consider the AEAD MAC as an "error
correction code" or a "cryptographic MAC". People are widely deploying
256-bit and 384-bit MACs in areas where a "cryptographic MAC" is
required. I guess it is also dependent on the time window (which in TLS
is short) however someone with acres/hectares of computers could make a
DHT (Distributed Hash Table). Drives are cheap and DHTs are fast for
vast amounts of data. Reasoning is 32 bits lost entropy, n bits in
storage, m bits computed online (from looking at table based GHASH).

OMAC1/CMAC is limited to the block size of the underlying cipher which
is 128 bits even with AES-256. EAX just seems simpler than CCM.

Just thought I would question the convention and established thought...

Cheers,
Michael.

---

From: Jeffrey Walton <[email-masked]>
Date: Sat, 20 Dec 2014 19:32:23 -0500

On Sat, Dec 20, 2014 at 1:21 PM, Tapio Sokura <[email-masked]> wrote:
> A bit off-topic on the actual question, but: Is DSS used anymore? ...
Also see "[TLS] Deprecating more (DSA?)",
http://www.ietf.org/mail-archive/web/tls/current/msg12006.html.

---

From: Russ Housley <[email-masked]>
Date: Wed, 24 Dec 2014 10:17:03 -0500

The folks doing the DTLS profile for low-end devices have chosen AES-CCM because they have hardware support for it.  I think we should include it to promote interoperability.

Russ

On Dec 20, 2014, at 7:19 PM, Michael Clark wrote:

> _______________________________________________
> TLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tls