Subject: [MLS] Substitute AES-128-GCM with AES-256-GCM for TreeKEM

From: Raphael Robert <[email-masked]>
Date: Wed, 19 Sep 2018 19:17:05 +0200

I am proposing to substitute AES-128-GCM with AES-256-GCM for TreeKEM: 

https://github.com/mlswg/mls-protocol/pull/60

There was no particular reason why AES-128-GCM was chosen initially, and there is no obvious security downside to AES-256-GCM.

Raphael

---

From: "Salz, Rich" <[email-masked]>
Date: Wed, 19 Sep 2018 17:50:36 +0000

>    I am proposing to substitute AES-128-GCM with AES-256-GCM for TreeKEM: 
  
Why?  When do you think 128 is not secure enough?

---

From: Richard Barnes <[email-masked]>
Date: Wed, 19 Sep 2018 13:14:48 -0500

The obvious argument against this is that you don't ultimately get the
benefit of the bigger key.  Since you're generating the key off of a P-256
operation, your security level to limited to 128 bits.  The only way that
argument wouldn't hold is if you thought for some reason that AES-128-GCM
was going to degrade faster than P-256, or if you wanted to argue that
AES-128-GCM isn't really providing a 128-bit security level.

You could, of course, have a cipher suite where you upgrade everything:
AES-256-GCM, P-521, SHA-512.  But in that case, the size of a message
basically doubles.  Concretely: an element in a TreeKEM path has (1) a
public key for the node (2) an encrypted node secret with is (2a) a public
key (2b) an encrypted hash output and (2c) a GCM tag.  With the *256 suite,
that comes to 178 = 65 + (65 + 32 + 16) and with the *512 suite, 346 = 133
+ (133 + 64 + 16).

If other folks are keen on AES-256-GCM, I don't think there's any major
harm in upgrading the P-256-based scheme to use AES-256-GCM, but I don't
think there's much benefit either.  Likewise, if folks want to add a
higher-security-level suite, I wouldn't be opposed, but I don't think it'll
get much use.  In the Firefox TLS telemetry [1], the AES-256-GCM
ciphersuites get more than 6x the use that the AES-128-GCM suites do.

--Richard

[1] https://mzl.la/2PPT1YL
1 = RSA + AES-128-GCM = 55%
2 = ECDSA + AES-128-GCM = 18%
13 = ECDSA + AES-256-GCM =1%
14 = RSA + AES-256-GCM = 10%

On Wed, Sep 19, 2018 at 12:17 PM Raphael Robert <[email-masked]> wrote:

> There was no particular reason why AES-128-GCM was chosen initially, and
> there is no obvious security downside to AES-256-GCM.
>
> Raphael
> _______________________________________________
> MLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/mls
>

---

From: Dennis Jackson <[email-masked]>
Date: Wed, 19 Sep 2018 19:30:57 +0100

Would it be reasonable to apply a misuse resistant scheme such as
AES-GCM-SIV? [1]. 

I am more concerned by implementations getting nonce generation wrong
than the delta between 128 / 256 keys.  

[1] https://eprint.iacr.org/2017/168.pdf

On Wed, 19 Sep 2018 13:14:48 -0500
Richard Barnes <[email-masked]> wrote:

> benefit of the bigger key.  Since you're generating the key off of a
> P-256 operation, your security level to limited to 128 bits.  The
> only way that argument wouldn't hold is if you thought for some
> reason that AES-128-GCM was going to degrade faster than P-256, or if
> you wanted to argue that AES-128-GCM isn't really providing a 128-bit
> security level.
> 
> You could, of course, have a cipher suite where you upgrade
> everything: AES-256-GCM, P-521, SHA-512.  But in that case, the size
> of a message basically doubles.  Concretely: an element in a TreeKEM
> path has (1) a public key for the node (2) an encrypted node secret
> with is (2a) a public key (2b) an encrypted hash output and (2c) a
> GCM tag.  With the *256 suite, that comes to 178 = 65 + (65 + 32 +
> 16) and with the *512 suite, 346 = 133
> + (133 + 64 + 16).
> 
> If other folks are keen on AES-256-GCM, I don't think there's any
> major harm in upgrading the P-256-based scheme to use AES-256-GCM,
> but I don't think there's much benefit either.  Likewise, if folks
> want to add a higher-security-level suite, I wouldn't be opposed, but
> I don't think it'll get much use.  In the Firefox TLS telemetry [1],
> the AES-256-GCM ciphersuites get more than 6x the use that the
> AES-128-GCM suites do.
> 
> --Richard
> 
> > There was no particular reason why AES-128-GCM was chosen
> > initially, and there is no obvious security downside to AES-256-GCM.
> >
> > Raphael

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

---

From: Richard Barnes <[email-masked]>
Date: Wed, 19 Sep 2018 13:37:13 -0500

In this case, I think we can do better than SIV by requiring that nonces be
generated in a certain way.  When I added TreeKEM, I erred in having an
independent nonce field in the ECIESCiphertext struct.  Instead, we should
generate the nonce from the ECDH exchange, in parallel with the key,
precisely as TLS does.

---

From: Dennis Jackson <[email-masked]>
Date: Wed, 19 Sep 2018 19:55:17 +0100

Currently the specification seems to require the application layer
messages are protected by the same AEAD defined in the handshake. [1] Do
you intend for the nonces to be deterministically generated for
application messages as well? If so, there is a risk state handling
bugs which SIV would mitigate. 

Alternatively, if the message layer is going to use a misuse resistant
algorithm, we might as well use it in the handshake as well? 

[1] Based on
https://github.com/mlswg/mls-protocol/blob/master/draft-ietf-mls-protocol.md
which differs from the current IETF draft. 

On Wed, 19 Sep 2018 13:37:13 -0500
Richard Barnes <[email-masked]> wrote:

> In this case, I think we can do better than SIV by requiring that
> nonces be generated in a certain way.  When I added TreeKEM, I erred
> in having an independent nonce field in the ECIESCiphertext struct.
> Instead, we should generate the nonce from the ECDH exchange, in
> parallel with the key, precisely as TLS does.
> 
> On Wed, Sep 19, 2018 at 1:31 PM Dennis Jackson
> <[email-masked]> wrote:
> 
> > I am more concerned by implementations getting nonce generation
> > wrong than the delta between 128 / 256 keys.
> >
> > > The obvious argument against this is that you don't ultimately
> > > get the benefit of the bigger key.  Since you're generating the
> > > key off of a P-256 operation, your security level to limited to
> > > 128 bits.  The only way that argument wouldn't hold is if you
> > > thought for some reason that AES-128-GCM was going to degrade
> > > faster than P-256, or if you wanted to argue that AES-128-GCM
> > > isn't really providing a 128-bit security level.
> > >
> > > everything: AES-256-GCM, P-521, SHA-512.  But in that case, the
> > > size of a message basically doubles.  Concretely: an element in a
> > > TreeKEM path has (1) a public key for the node (2) an encrypted
> > > node secret with is (2a) a public key (2b) an encrypted hash
> > > output and (2c) a GCM tag.  With the *256 suite, that comes to
> > > 178 = 65 + (65 + 32 + 16) and with the *512 suite, 346 = 133
> > > + (133 + 64 + 16).
> > >
> > > want to add a higher-security-level suite, I wouldn't be opposed,
> > > but I don't think it'll get much use.  In the Firefox TLS
> > > telemetry [1], the AES-256-GCM ciphersuites get more than 6x the
> > > use that the AES-128-GCM suites do.
> > >
> > > --Richard
> > >

---

From: Raphael Robert <[email-masked]>
Date: Thu, 20 Sep 2018 12:55:50 +0200

This is a good argument. Upgrading the ECDH primitive would make sense. I guess replacing P256 by P521 is somewhat straightforward, but Curve25519 is not. Ed448-Goldilocks might be a potential candidate.
So the question has shifted to: Do we want to increase the security level consistently? And is the payload increase acceptable?

I will close the PR for now.

Raphael

> On 19 Sep 2018, at 20:14, Richard Barnes <[email-masked]> wrote:
> 
> The obvious argument against this is that you don't ultimately get the benefit of the bigger key.  Since you're generating the key off of a P-256 operation, your security level to limited to 128 bits.  The only way that argument wouldn't hold is if you thought for some reason that AES-128-GCM was going to degrade faster than P-256, or if you wanted to argue that AES-128-GCM isn't really providing a 128-bit security level.
> 
> You could, of course, have a cipher suite where you upgrade everything: AES-256-GCM, P-521, SHA-512.  But in that case, the size of a message basically doubles.  Concretely: an element in a TreeKEM path has (1) a public key for the node (2) an encrypted node secret with is (2a) a public key (2b) an encrypted hash output and (2c) a GCM tag.  With the *256 suite, that comes to 178 = 65 + (65 + 32 + 16) and with the *512 suite, 346 = 133 + (133 + 64 + 16).
> 
> If other folks are keen on AES-256-GCM, I don't think there's any major harm in upgrading the P-256-based scheme to use AES-256-GCM, but I don't think there's much benefit either.  Likewise, if folks want to add a higher-security-level suite, I wouldn't be opposed, but I don't think it'll get much use.  In the Firefox TLS telemetry [1], the AES-256-GCM ciphersuites get more than 6x the use that the AES-128-GCM suites do.
> 
> --Richard
> 
> [1] https://mzl.la/2PPT1YL <https://mzl.la/2PPT1YL>
> On Wed, Sep 19, 2018 at 12:17 PM Raphael Robert <[email-masked] <mailto:[email-masked]>> wrote:
> https://github.com/mlswg/mls-protocol/pull/60 <https://github.com/mlswg/mls-protocol/pull/60>
> 
> [email-masked] <mailto:[email-masked]>
> https://www.ietf.org/mailman/listinfo/mls <https://www.ietf.org/mailman/listinfo/mls>

---

From: "Salz, Rich" <[email-masked]>
Date: Thu, 20 Sep 2018 11:55:37 +0000

Is there a good rationale, perhaps a link, explaining why all parts of a cipher-suite need to be at the same strength? I tend to call those things “crypto numerology” but perhaps (not being a cryptographer) I’m just biased.  Yes, I understand that it might be no better than the weakest link.

---

From: Richard Barnes <[email-masked]>
Date: Thu, 20 Sep 2018 08:02:29 -0400

As I understand it:

The parts of a ciphersuite work together, so the idea is roughly that
there's no point in adding one super strong link to the chain if the others
are weak.

Following the TreeKEM / ECIES example below, if you generate a key for
AES-256 off of a P-256 ECDH operation, then the whole thing can still be
broken with 2^128 effort, by attacking the ECDH instead of the AES.

On Thu, Sep 20, 2018, 07:55 Salz, Rich <rsalz=[email-masked]>
wrote:

> Is there a good rationale, perhaps a link, explaining why all parts of a
> cipher-suite need to be at the same strength? I tend to call those things
> “crypto numerology” but perhaps (not being a cryptographer) I’m just
> biased.  Yes, I understand that it might be no better than the weakest
> link.
>
>

---

From: "Salz, Rich" <[email-masked]>
Date: Thu, 20 Sep 2018 12:06:57 +0000

*   The parts of a ciphersuite work together, so the idea is roughly that there's no point in adding one super strong link to the chain if the others are weak.

Well, there could be, but I get the point.

Is there a reason to think 128 is not strong enough?

---

From: Joel Alwen <[email-masked]>
Date: Thu, 20 Sep 2018 14:27:09 +0200

On 20/09/2018 14:02, Richard Barnes wrote:

> there's no point in adding one super strong link to the chain if the
> others are weak.  
>
> AES-256 off of a P-256 ECDH operation, then the whole thing can still
> be broken with 2^128 effort, by attacking the ECDH instead of the AES.

- I agree with this point of view. To me it seems the con of the switch
to AES-256 is some (small) additional cost in bandwidth, storage and
computation but there is no pro in terms of added security since keys
are negotiated on a 128-bit secure curve. So it doesn't make that much
sense to me... Nor do I think, at least for short and medium term
security, that there is a problem with 128-bit security.

- Having said that, I think 256-bit security does have legitimate use
cases in practice. (Say, long-term forward secrecy and/or hedging
against future improvements in cryptanalyis.) Therefor I'm quite in
favor of including in MLS a recommended fully 256-bit secure
instantiation. E.g. SHA-512, Ed448-Goldilocks, AES-256-GCM. (My
preference for Ed448 over P521 stems from P521 being less efficient,
less easy to implement in side-channel resistant way and Ed448 soon
being included in TLS hopefully leading to solid implementations
becoming widely available.)

- I think that mandating an explicit nonce reuse resistant mechanism
(whether via SIV or something else) makes a lot of sense and is
something MLS should do.

---

From: "Salz, Rich" <[email-masked]>
Date: Thu, 20 Sep 2018 12:32:03 +0000

*   Well, there could be, but I get the point.

I should point out why I think there could be a point to different strengths.  If you can break the ECDH curve, for example, you can get all conversations. If you can break only AES, you have one conversation at a time. The costs of each are probably very different.

---

From: Joel Alwen <[email-masked]>
Date: Thu, 20 Sep 2018 14:54:06 +0200

On 20/09/2018 14:32, Salz, Rich wrote:
>
> I should point out why I think there could be a point to different
> strengths.  If you can break the ECDH curve, for example, you can get
> all conversations. If you can break only AES, you have one
> conversation at a time. The costs of each are probably very different.
>
>  
>
At first glance: wouldn't that motivate switching to a 256-bit secure
curve rather than to a 256-bit block cipher as more depends on the
curves security than the block-cipher?

---

From: Dennis Jackson <[email-masked]>
Date: Thu, 20 Sep 2018 14:34:58 +0100

One area in which the symmetric cipher keysize does matter is if you
believe quantum computers will become viable in the next 5~10 years.
Considering the efforts standards bodies and corporations are putting
into developing post-quantum handshakes, this doesn't seem unreasonable.

If QC becomes practical (even assuming no other cryptanalytic
breakthroughs) AES-256 degrades to 128-bit security and AES-128
degrades to only 64-bit security (no better than DES). However, none of
the draft handshakes are post-quantum secure, which is arguably a bigger
problem.

Some options: 

a) do nothing
b) specify a post quantum handshake alongside AES-256
c) specify AES-256 in general and allow a PSK in addition to the usual
handshake

Wireguard uses c) to achieve "cheap" PQ-security without the
burden of implementing a PQ handshake. 

I'm not advocating for any of these options, just noting where
symmetric keysize is a consideration. 

On Thu, 20 Sep 2018 14:27:09 +0200
Joel Alwen <[email-masked]> wrote:

> > The parts of a ciphersuite work together, so the idea is roughly
> > that there's no point in adding one super strong link to the chain
> > if the others are weak.  
> >
> > Following the TreeKEM / ECIES example below, if you generate a key
> > for AES-256 off of a P-256 ECDH operation, then the whole thing can
> > still be broken with 2^128 effort, by attacking the ECDH instead of
> > the AES.  
> 
> - I agree with this point of view. To me it seems the con of the
> switch to AES-256 is some (small) additional cost in bandwidth,
> storage and computation but there is no pro in terms of added
> security since keys are negotiated on a 128-bit secure curve. So it
> doesn't make that much sense to me... Nor do I think, at least for
> short and medium term security, that there is a problem with 128-bit
> security.
>

---

From: Richard Barnes <[email-masked]>
Date: Thu, 20 Sep 2018 09:52:19 -0500

If QC becomes practical, all the DH stuff is out the window anyway :)

---

From: "Salz, Rich" <[email-masked]>
Date: Thu, 20 Sep 2018 15:28:07 +0000

*   At first glance: wouldn't that motivate switching to a 256-bit secure curve rather than to a 256-bit block cipher as more depends on the curves security than the block-cipher?

Yes it would.  I am questioning why 128 isn’t enough.

---

From: Raphael Robert <[email-masked]>
Date: Thu, 20 Sep 2018 17:38:51 +0200

To clarify: I proposed AES256 as a cheap way of raising the security level, but it is now clear that this substitution alone is not enough. I have not specific argument against AES128 as such.

The reasons Joel and Dennis mention that speak for having a security level of 256 bits were also the ones I was thinking about:

 - potentially better long-term security
 - preparing future “cheap” PQ resistant extensions that don’t require the core of MLS to be changed, but can rather be bolted on an old version

> On 20 Sep 2018, at 17:28, Salz, Rich <rsalz=[email-masked]> wrote:
> 
> At first glance: wouldn't that motivate switching to a 256-bit secure curve rather than to a 256-bit block cipher as more depends on the curves security than the block-cipher?
>

---

From: Joel Alwen <[email-masked]>
Date: Thu, 20 Sep 2018 23:39:13 +0200

> c) specify AES-256 in general and allow a PSK in addition to the usual

I like the idea of having a PSK mode. Though forcing all other modes to
use AES-256 (and SHA-512 by the way) to accommodate it doesn't seem like
a great solution to me. Still, I do think PQ security should be
something we keep in mind (if not directly aim for) when designing MLS.
IMO already today, to make plausible long-term forward security claims
we should really already be using PQ secure crypto.

Having said that, while I think it would be *super* cool to specify a
concrete PQ secure key agreement protocol for MLS I, unfortunately,
think that's still rather risky at the point. The field (of truly
practical PQ schemes) is still in too much development. E.g. I believe
NIST still wants another 4-5 years till they are ready to finalize any
such recommended protocols. Also, doing so for key agreement would then
mean that we'd probably also want to recommend a PQ secure PubKey
encryption for TreeKEM not to mention a signature for message authenticity.

I do have a fourth (not necessarily mutually exclusive) option I wanted
to throw out there.

d) Specify ART using a generic Non-Interactive Key Agreement (NIKE)
instead of the current special case of (EC)DH. (This may include
specifying the expected interface and basic security property of a
NIKE.) Next, to make things concrete we can specify some instantiations
of the NIKE (say, ECDH on Curve25519 or P-521 or whatever ).

This way we could defer on specifying a concrete PQ instantiation (i.e.
a PQ secure NIKE construction) but it would still be left pretty clear
to those that care about PQ security what needs to be done to get a PQ
version of MLS (at least one that doesn't rely on a PSK). Namely:

A) Switch to 256-bit secure versions of the AEAD and Hash Function and
B) Select a PQ secure NIKE (and signature scheme). The NIKE plugs
directly into ART and, via a KEM/DEM construction of public key
encryption into TreeKEM.

As an aside, I think it would be great if any more rigorous
reasoning/security proofs for MLS were done not based on DH but rather
on a black-box NIKE (and AEAD and random oracle). I guess that's also
part of what motivates the above suggestion. A more generic (non-DH
specific) security proof would not only tell us something about the
security of MLS as we want to instantiate it but would also be useful
for those creating a PQ version as it would help nail down exactly what
pieces are still missing and what is achieved by plugging them into MLS.