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

Michael Clark <michael@metaparadigm.com> Sat, 20 December 2014 08:53 UTC

Return-Path: <michael@metaparadigm.com>
X-Original-To: tls@ietfa.amsl.com
Delivered-To: tls@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 211A51A0430 for <tls@ietfa.amsl.com>; Sat, 20 Dec 2014 00:53:07 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 1.032
X-Spam-Level: *
X-Spam-Status: No, score=1.032 tagged_above=-999 required=5 tests=[BAYES_50=0.8, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, IP_NOT_FRIENDLY=0.334, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001, T_FROM_12LTRDOM=0.01, T_RP_MATCHES_RCVD=-0.01] autolearn=no
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id SEfTz5xEZtGS for <tls@ietfa.amsl.com>; Sat, 20 Dec 2014 00:53:05 -0800 (PST)
Received: from klaatu.metaparadigm.com (klaatu.metaparadigm.com [67.207.128.90]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 1204C1A0AF7 for <tls@ietf.org>; Sat, 20 Dec 2014 00:53:04 -0800 (PST)
Received: from monty.local (cm50.kappa90.maxonline.com.sg [58.182.90.50] (may be forged)) (authenticated bits=0) by klaatu.metaparadigm.com (8.14.4/8.14.4/Debian-4) with ESMTP id sBK9Dv8D019803 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES128-SHA bits=128 verify=NOT) for <tls@ietf.org>; Sat, 20 Dec 2014 09:14:00 GMT
DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=metaparadigm.com; s=klaatu; t=1419066842; bh=l3dJeSr2AwqtDjL5gvudweG9QClesJV3MwIKzo9ByZw=; h=Date:From:To:Subject:From; b=RRgHUg8nITnTc3S5rJpXfCanRaFnfndQXRb1wPRjd74cyHovtZkyh37DjhfI1434m q7CBh5c33KJP94IjhEc9mADxgmgN3CDnCXAwixaAISlhg110Q7r82qXefWRCEd0O/e dh60hBYib8/78yV2FLb8M2o1c0do0/oIt2mqW0X8=
Message-ID: <549538E5.7050109@metaparadigm.com>
Date: Sat, 20 Dec 2014 16:52:53 +0800
From: Michael Clark <michael@metaparadigm.com>
Organization: Metaparadigm Pte Ltd
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.10; rv:24.0) Gecko/20100101 Thunderbird/24.6.0
MIME-Version: 1.0
To: tls@ietf.org
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
X-Virus-Scanned: clamav-milter 0.98.4 at klaatu.metaparadigm.com
X-Virus-Status: Clean
Archived-At: http://mailarchive.ietf.org/arch/msg/tls/s50LaZh3gCFGqpyLPocE_qQm6Rk
Subject: [TLS] AAED ciphers: AES-GCM vs AES-EAX/AES-CCM: a meta-analysis
X-BeenThere: tls@ietf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: "This is the mailing list for the Transport Layer Security working group of the IETF." <tls.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/tls>, <mailto:tls-request@ietf.org?subject=unsubscribe>
List-Archive: <http://www.ietf.org/mail-archive/web/tls/>
List-Post: <mailto:tls@ietf.org>
List-Help: <mailto:tls-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/tls>, <mailto:tls-request@ietf.org?subject=subscribe>
X-List-Received-Date: Sat, 20 Dec 2014 08:53:07 -0000

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