Subject: [MLS] Proposal: Change AES-GCM to AES-SIV

From: Dennis Jackson <[email-masked]>
Date: Wed, 26 Sep 2018 22:30:43 +0100

Proposal: Change AES-GCM to AES-SIV

Rationale: 

AES-GCM requires a unique nonce for every message, otherwise it
fails catastrophically by directly leaking the authentication key
and consequently provides no resistance to active attacks on 
confidentiality. 

AES-SIV is a drop in replacement for AES-GCM which significantly
mitigates the impact of repeated nonces. For a message pair with
repeated nonces the attacker only learns if the two plaintexts were
equal. There is no other loss of confidentiality or authenticity. This
is provably the minimum leakage possible in the event of a repeated
nonce. 

Handling nonces is a tricky part of any implementation and easy to get
wrong in the presence of state loss or concurrency. Failures
in nonce generation are both catastrophic and subtle. Richard Barnes
has already improved the specification by moving from explicit to
implicit nonces which can aid the discovery of faulty implementations.
However, implicit nonces are not a silver bullet and recent papers have
uncovered serious nonce reuse issues in both TLS [1] and WPA [2]. 

+ AES-SIV significantly mitigates the impact of nonce reuse
+ AES-SIV is a drop in replacement with the same interface as AES-GCM
+ AES-SIV makes use of the same hardware support as AES-GCM
+ AES-SIV has a proof of security [3] and is described in RFC 5297 [4]
* AES-SIV has reasonable (but not extensive) library support (including
  OpenSSL, BoringSSL, Intel IPP)
* Despite being over 10 years old, AES-SIV has not seen widespread
  deployment
* AES-SIV Encryption is ~70% of the speed of AES-GCM Encryption
  (Decryption is the same speed as AES-GCM)

References: 

[1] https://www.usenix.org/system/files/conference/woot16/woot16-paper-bock.pdf

[2] https://www.krackattacks.com/

[3] http://web.cs.ucdavis.edu/~rogaway/papers/keywrap.pdf

[4] https://datatracker.ietf.org/doc/rfc5297/

---

From: Richard Barnes <[email-masked]>
Date: Wed, 26 Sep 2018 23:53:24 +0200

Hi Dennis,

Thanks for writing this up.  One brief note: The Böck et al. paper you cite
is about TLS 1.2 and earlier, which use explicit nonces.  In fact, that
paper cites the implicit nonce approach in TLS 1.3 as one of their two
recommended approaches.  That seems to support the idea that generating
nonces in the TLS 1.3 style is a reasonable solution here.

That, together with the persistent lack of implementation of AES-GCM-SIV,
makes me inclined to stick with normal AES-GCM, while assuring adequate
safeguards.

--Richard

On Wed, Sep 26, 2018 at 11:31 PM Dennis Jackson <[email-masked]>
wrote:

> [1]
> https://www.usenix.org/system/files/conference/woot16/woot16-paper-bock.pdf
>
> _______________________________________________
> MLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/mls
>

---

From: Dennis Jackson <[email-masked]>
Date: Thu, 27 Sep 2018 00:16:17 +0100

Hi Richard, 

The use of implicit nonces is complementary to SIV, but certainly
doesn't replace it. To be precise, implicit nonces ensures all
implementations use the same scheme for nonce generation. It does not
ensure that nonce generation scheme is correct.

One possible source of error is an edge case in which the
implementation unintentionally deviates from the standard. This is hard
to catch in practice. With AES-GCM, an attacker able to detect (or
force) this edge case would be able to derive the authentication key
and attack the protocol. With AES-SIV, the attacker would gain very
limited information about the message sent and the protocol would abort
normally. 

A second, more serious source of error is when the nonce generation
scheme is not correctly designed. This was the case in the KRACK attack
on WPA2. Despite the comparative simplicity of a 4-message 2-party
handshake and WPA2's wide deployment, every single implementation had
at least one nonce reuse attack. Although WPA2 does use explicit nonces
(since it is over a lossy medium), implicit nonces would not have
caught the KRACK attack, as both parties reset their nonce
counter in accordance with the specification. 

Given we are implementing a novel multi party asynchronous group key
exchange from scratch, I don't think we should shrug this away. Not
when the code level difference for implementors is only whether to pick
EVP_CIPH_GCM_MODE or EVP_CIPH_SIV_MODE. 

All the best,
Dennis 

On Wed, 26 Sep 2018 23:53:24 +0200
Richard Barnes <[email-masked]> wrote:

> Hi Dennis,
> 
> Thanks for writing this up.  One brief note: The Böck et al. paper
> you cite is about TLS 1.2 and earlier, which use explicit nonces.  In
> fact, that paper cites the implicit nonce approach in TLS 1.3 as one
> of their two recommended approaches.  That seems to support the idea
> that generating nonces in the TLS 1.3 style is a reasonable solution
> here.
> 
> That, together with the persistent lack of implementation of
> AES-GCM-SIV, makes me inclined to stick with normal AES-GCM, while
> assuring adequate safeguards.
> 
> --Richard
> 
> 
> On Wed, Sep 26, 2018 at 11:31 PM Dennis Jackson
> <[email-masked]> wrote:
> 
> > equal. There is no other loss of confidentiality or authenticity.
> > This is provably the minimum leakage possible in the event of a
> > repeated nonce.
> >
> > Handling nonces is a tricky part of any implementation and easy to
> > get wrong in the presence of state loss or concurrency. Failures
> > implicit nonces which can aid the discovery of faulty
> > implementations. However, implicit nonces are not a silver bullet
> > and recent papers have uncovered serious nonce reuse issues in both
> > TLS [1] and WPA [2].
> >
> > * AES-SIV has reasonable (but not extensive) library support
> > (including OpenSSL, BoringSSL, Intel IPP)

-- 
PGP Fingerprint: 5B93 F0B9 D6A8 9BC1 546B C98C 6105 A775 8CD2 46AC

---

From: Brendan McMillion <[email-masked]>
Date: Wed, 26 Sep 2018 23:04:52 -0700

> Handling nonces is a tricky part of any implementation and easy to get wrong in the presence of state loss

I think this is the core reason to consider using SIV. Since nonces are generated deterministically and statefully, is it possible for state loss (caused by an app crash) to cause nonce reuse? If so, SIV is necessary assuming implicit nonces.

Another solution is to use explicit random IVs, as this prevents nonce reuse (statistically, with a correct implementation) and means we can keep using abundantly available AES-GCM implementations.

> On Sep 26, 2018, at 4:16 PM, Dennis Jackson <[email-masked]> wrote:
> 
> Hi Richard, 
> 
> Richard Barnes <[email-masked] <mailto:[email-masked]>> wrote:
> 
>> Hi Dennis,
>> 
> [email-masked] <mailto:[email-masked]>
> https://www.ietf.org/mailman/listinfo/mls <https://www.ietf.org/mailman/listinfo/mls>

---

From: Dennis Jackson <[email-masked]>
Date: Thu, 27 Sep 2018 12:36:17 +0100

In response to the questions about implementations, I've quickly 
trawled for libraries supporting AES-SIV: 

[BoringSSL] - Google's port of OpenSSL 

[IntelIPP] - Intel, implemented in ANSI C 

[libaes_siv] - Akamai, implemented in C

[Miscreant] - Go, Rust, C#, Javascript, Python, Ruby 

[siv-mode] - Java, audited by Cure 53

[openssl] - PR, Awaiting second review before release

[AESSIVWrapper] - iOS Obj-C Wrapper

Summary:  all major languages seem to have at least one implementation. That said,
AES-GCM enjoys much wider support. I'm not an implementation person, so I can't 
speak as to whether this is a blocker for considering AES-SIV at all. 

References: 

[Miscreant] https://github.com/miscreant/miscreant

[BoringSSL] https://github.com/google/boringssl/blob/master/include/openssl/aead.h

[IntelIPP] https://software.intel.com/en-us/ipp-crypto-reference-aes-siv-functions

[libaes_siv] https://github.com/dfoxfranke/libaes_siv

[siv-mode] https://github.com/cryptomator/siv-mode

[openssl] https://github.com/openssl/openssl/pull/3540

[AESSIVWrapper] - https://github.com/daresaydigital/AESSIVWrapper

On Wed, 26 Sep 2018 22:30:43 +0100
Dennis Jackson <[email-masked]> wrote:

> However, implicit nonces are not a silver bullet and recent papers
> have uncovered serious nonce reuse issues in both TLS [1] and WPA
> [2]. 
>