Subject: [Lake] Discussion on IoT AEAD limits for AES_128_CCM_8

From: John Mattsson <[email-masked]>
Date: Mon, 16 Nov 2020 15:17:04 +0000

Hi,

As discussed during the meeting today, CFRG is working on an excellent document specifying equations to calculate AEAD limits for the number of encryption operations q and the number of forgery attempts v. TLS, DTLS, and QUIC have adopted strict limits based on these equations. Having strict limits is not a problem if re-keying is easy.

https://tools.ietf.org/html/draft-irtf-cfrg-aead-limits

Most constrained IoT systems today use some variant of AES-128 in CCM mode with a 32- or 64-bit tag. IETF use of AES-128 in CCM mode typically only use 64-bit tags.

The important equations for AEAD_AES_128_CCM_8 (AES-CCM-16-64-128, AES-CCM-64-64-128) are:

Confidentiality Limit:
q <= sqrt((p * 2^126) / l^2)

Integrity Limit:
v * 2^64 + (2l * (v + q))^2 <= p * 2^128

where:

q = Number of protected messages (AEAD encryption invocations)
v = Number of attacker forgery attempts (failed AEAD decryption invocations)    
p = Adversary attack probability
l = input length (plaintext + additional data) in blocks

For AEAD_AES_128_CCM_8 the integrity limit is the most limiting. DTLS 1.3 sets the limits for CCM to q = 2^23 and v = 2^23.5 and states that AES_128_CCM_8 MUST NOT used in DTLS without additional safeguards against forgery. This unfortunately severely limits the use case for DTLS 1.3 in very constrained IoT.

The assumptions used DTLS 1.3 (still a draft) are:

p = 2^-57
l = 2^10 (2^14 bytes)

It should be discussed which assumptions are relevant for IoT systems. It was suggested during the meeting today that this discussion should be held in a IoT focused security area WG like LAKE. There are a large number of aspects that affect how the limits v and q should be assigned:

- The probability p can be set to basically any value, it decides the security level. Some IoT systems might accept a higher forgery probability that (D)TLS in general.

- To optimize the forgery probablity the attacker cannot send a chosen message, the attacker has to settle for something that looks like a random string. For use cases where the payload has a certain format, this means that succesfull forgeries will likely be discarded on a higher level in the stack.

- The forgery probability is for a single forgery. In some systems a single forgery may not matter much and several forgeries might be needed to do any harm.

- The input lengths are typically much much smaller for most constrained IoT systems than the 16 KB packets assumed in the (D)TLS calculations.

- If the attacker uses a high speed broadband connection, a lot of forgeries can be sent quickly. On most constained IoT systems, the bandwith is very limited and it would take takes a long time to send forged message.

- Any denial-of-service resulting from low limits on v should be compared to other denial-of-service attacks on the system. If there are even easier ways to reduce the availability of a system, a low limit on v does not matter.

Looking forward to hear the IETF IoT communities comments on the above.

Cheers,
John

---

From: "Martin Thomson" <[email-masked]>
Date: Wed, 18 Nov 2020 11:48:15 +1100

You might find this tool useful in evaluating this:

https://chris-wood.github.io/interactive-aead-limits/

Note that with the value of p that TLS uses (2^-57), this cipher performs very badly.  The number of forgery attempts you can tolerate is 128.  That's not 2^128, it's 128.  I don't think that is acceptable.  You might be able to increase your tolerance for attack (p) to get something more realistic.

On Tue, Nov 17, 2020, at 02:17, John Mattsson wrote:
> Hi,
> 
> As discussed during the meeting today, CFRG is working on an excellent 
> document specifying equations to calculate AEAD limits for the number 
> of encryption operations q and the number of forgery attempts v. TLS, 
> DTLS, and QUIC have adopted strict limits based on these equations. 
> Having strict limits is not a problem if re-keying is easy.
> 
> Most constrained IoT systems today use some variant of AES-128 in CCM 
> mode with a 32- or 64-bit tag. IETF use of AES-128 in CCM mode 
> typically only use 64-bit tags.
> 
> For AEAD_AES_128_CCM_8 the integrity limit is the most limiting. DTLS 
> 1.3 sets the limits for CCM to q = 2^23 and v = 2^23.5 and states that 
> AES_128_CCM_8 MUST NOT used in DTLS without additional safeguards 
> against forgery. This unfortunately severely limits the use case for 
> DTLS 1.3 in very constrained IoT.
> 
> It should be discussed which assumptions are relevant for IoT systems. 
> It was suggested during the meeting today that this discussion should 
> be held in a IoT focused security area WG like LAKE. There are a large 
> number of aspects that affect how the limits v and q should be assigned:
> 
> - The probability p can be set to basically any value, it decides the 
> security level. Some IoT systems might accept a higher forgery 
> probability that (D)TLS in general.
> 
> - To optimize the forgery probablity the attacker cannot send a chosen 
> message, the attacker has to settle for something that looks like a 
> random string. For use cases where the payload has a certain format, 
> this means that succesfull forgeries will likely be discarded on a 
> higher level in the stack.
> 
> - The forgery probability is for a single forgery. In some systems a 
> single forgery may not matter much and several forgeries might be 
> needed to do any harm.
> 
> - The input lengths are typically much much smaller for most 
> constrained IoT systems than the 16 KB packets assumed in the (D)TLS 
> calculations.
> 
> - If the attacker uses a high speed broadband connection, a lot of 
> forgeries can be sent quickly. On most constained IoT systems, the 
> bandwith is very limited and it would take takes a long time to send 
> forged message.
> 
> - Any denial-of-service resulting from low limits on v should be 
> compared to other denial-of-service attacks on the system. If there are 
> even easier ways to reduce the availability of a system, a low limit on 
> v does not matter.
> 
> -- 
> Lake mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/lake
>

---

From: Tero Kivinen <[email-masked]>
Date: Wed, 18 Nov 2020 08:49:21 +0200

Martin Thomson writes:
> Note that with the value of p that TLS uses (2^-57), this cipher
> performs very badly.  The number of forgery attempts you can
> tolerate is 128.  That's not 2^128, it's 128.  I don't think that is
> acceptable.  You might be able to increase your tolerance for attack
> (p) to get something more realistic. 

Also note, that the for example in IEEE 802.15.4 the maximum number of
messages which can be sent by one key is 2^32 messages, as the frame
counter is 32-bit counter, and when it reaches 0xffffffff the sending
of frames will fail.

When using TSCH the ASN is 40-bit incrementing timestamp, which
usually increments every 10 ms or so, meaning that for it to wrap
around it takes 348 years.

So the max q is 2^32 for 802.15.4 (or 2^40 if TCSH is used). I would
expect most of the other environments where lake is used will have
similar very small values of max q.

If I understood how the interactive tool works, then if I set p to 51
that would give log2(q) of 32 for message lengths of less than 256
bytes, but that gets log2(v) to quite low of 12.8.

On the other hand p of 32 and setting log2(q) to 33 will give log2(v)
of 32 for 256 byte messages.

So for AES_128_CCM_8 using p of 2^-32 allows sending max number of
messages for IEEE 802.15.4.
-- 
[email-masked]

---

From: John Mattsson <[email-masked]>
Date: Wed, 18 Nov 2020 07:37:59 +0000

Thanks Martin,

It is very good that you point out that it is always true that 

v <= p * 2^64

That simplifies analysis. I think most constrained IoT systems could live with slightly higher bounds on p. 

But I do not see why even 128 would be unacceptable. It is only a denial-of-service problem if the endpoint becomes unavailable or have to do a heavy key exchange/handshake.

When the counter of failed decryptions reaches v, the endpoint does not necessarily need to stop processing incoming messages, the important thing is that any successful forgeries are not forwarded to the higher layers and acted upon in any way. When the counter of failed decryption reaches v the endpoint can wait for a valid ciphertext, throw away the plaintext, and send an error message indicating that the other endpoint need to re-key. Re-keying can be done almost for free. So even with v = 128, an adversary would have to send 128 messages to force the endpoints to send 1 message each. 

Cheers,
John

-----Original Message-----
From: Lake <[email-masked]> on behalf of Martin Thomson <[email-masked]>
Date: Wednesday, 18 November 2020 at 01:48
To: "[email-masked]" <[email-masked]>
Subject: Re: [Lake] Discussion on IoT AEAD limits for AES_128_CCM_8

https://protect2.fireeye.com/v1/url?k=3eb60f28-612d37fa-3eb64fb3-866132fe445e-96ffc5c77ab20edd&q=1&e=b4763ea2-5ec7-4458-aa23-03e11fd005d5&u=https%3A%2F%2Fchris-wood.github.io%2Finteractive-aead-limits%2F

---

From: "Blomqvist, Peter" <[email-masked]>
Date: Wed, 18 Nov 2020 08:29:03 +0000

Thanks Martin, John and Tero.

The TLS bounds on p seems very strict compared to the TAG length of AES_128_CCM_8.
With SHAKE-128 in mind an AEAD allowing more flexible tag lengths would be nice.
Until then tuning the re-keying frequency as suggested by John looks like a usable approach.

Best
Peter

-----Original Message-----
From: Lake <[email-masked]> On Behalf Of John Mattsson
Sent: den 18 november 2020 08:38
To: Martin Thomson <[email-masked]>; [email-masked]
Subject: Re: [Lake] Discussion on IoT AEAD limits for AES_128_CCM_8

Thanks Martin,

v <= p * 2^64

Cheers,
John

-----Original Message-----
From: Lake <[email-masked]> on behalf of Martin Thomson <[email-masked]>
Date: Wednesday, 18 November 2020 at 01:48
To: "[email-masked]" <[email-masked]>
Subject: Re: [Lake] Discussion on IoT AEAD limits for AES_128_CCM_8

https://urldefense.proofpoint.com/v2/url?u=https-3A__protect2.fireeye.com_v1_url-3Fk-3D3eb60f28-2D612d37fa-2D3eb64fb3-2D866132fe445e-2D96ffc5c77ab20edd-26q-3D1-26e-3Db4763ea2-2D5ec7-2D4458-2Daa23-2D03e11fd005d5-26u-3Dhttps-253A-252F-252Fchris-2Dwood.github.io-252Finteractive-2Daead-2Dlimits-252F&d=DwIGaQ&c=fP4tf--1dS0biCFlB0saz0I0kjO5v7-GLPtvShAo4cc&r=ReOhyTHbHxF59rwa6NKLJmWnWtc32YE99Fj4rlHBZBM&m=A46AlixXRGEsUOZM85WuosdFcqMfKlPeK2LkNNz7N8c&s=BnsLLG77-rL_R-U01zyo2Kz2WC77eHWdcqOO2RUFoYw&e= 

On Tue, Nov 17, 2020, at 02:17, John Mattsson wrote:
> https://urldefense.proofpoint.com/v2/url?u=https-3A__tools.ietf.org_ht
> ml_draft-2Dirtf-2Dcfrg-2Daead-2Dlimits&d=DwIGaQ&c=fP4tf--1dS0biCFlB0sa
> z0I0kjO5v7-GLPtvShAo4cc&r=ReOhyTHbHxF59rwa6NKLJmWnWtc32YE99Fj4rlHBZBM&
> m=A46AlixXRGEsUOZM85WuosdFcqMfKlPeK2LkNNz7N8c&s=OGFcV0z2XzTGaOjBgLdcEG
> h4pWz05Vi7K6AB2Sa4nkI&e=
> 
> compared to other denial-of-service attacks on the system. If there 
> are even easier ways to reduce the availability of a system, a low 
> limit on v does not matter.
> 
> https://urldefense.proofpoint.com/v2/url?u=https-3A__www.ietf.org_mail
> man_listinfo_lake&d=DwIGaQ&c=fP4tf--1dS0biCFlB0saz0I0kjO5v7-GLPtvShAo4
> cc&r=ReOhyTHbHxF59rwa6NKLJmWnWtc32YE99Fj4rlHBZBM&m=A46AlixXRGEsUOZM85W
> uosdFcqMfKlPeK2LkNNz7N8c&s=K3y4u6XppyQptH-3iBBNp1SntQRbeoK7evd7EE3J7Vw
> &e=
>

--
Lake mailing list
[email-masked]
https://urldefense.proofpoint.com/v2/url?u=https-3A__www.ietf.org_mailman_listinfo_lake&d=DwIGaQ&c=fP4tf--1dS0biCFlB0saz0I0kjO5v7-GLPtvShAo4cc&r=ReOhyTHbHxF59rwa6NKLJmWnWtc32YE99Fj4rlHBZBM&m=A46AlixXRGEsUOZM85WuosdFcqMfKlPeK2LkNNz7N8c&s=K3y4u6XppyQptH-3iBBNp1SntQRbeoK7evd7EE3J7Vw&e= 

--
Lake mailing list
[email-masked]
https://urldefense.proofpoint.com/v2/url?u=https-3A__www.ietf.org_mailman_listinfo_lake&d=DwIGaQ&c=fP4tf--1dS0biCFlB0saz0I0kjO5v7-GLPtvShAo4cc&r=ReOhyTHbHxF59rwa6NKLJmWnWtc32YE99Fj4rlHBZBM&m=A46AlixXRGEsUOZM85WuosdFcqMfKlPeK2LkNNz7N8c&s=K3y4u6XppyQptH-3iBBNp1SntQRbeoK7evd7EE3J7Vw&e=

---

From: "Martin Thomson" <[email-masked]>
Date: Wed, 18 Nov 2020 22:56:28 +1100

On Wed, Nov 18, 2020, at 18:37, John Mattsson wrote:
> But I do not see why even 128 would be unacceptable. It is only a 
> denial-of-service problem if the endpoint becomes unavailable or have 
> to do a heavy key exchange/handshake.

The general rule here is that if v exceeds this value, the keys cannot be used without risking an unacceptable increase in the chance that the attacker is able to successfully create a forgery.  That means that 128 *unsuccessful* forgery attempts is enough to cause the keys - and therefore the connection, probably - to be unusable.  That's a fairly simple DoS to mount, even against a device that has very limited communication capabilities.

Now, as I said, maybe 2^-57 is too low for your use case.

> When the counter of failed decryption reaches v the endpoint can wait for a valid ciphertext, [...]

The problem is that the next ciphertext is now a forgery with a higher probability than you determined to be acceptable from the outset.  You can't even *try* to use the keys.  Unless you accept that higher risk.

You can, if you are able, try to rekey at this point.  However, you are now racing the attacker, because it is likely that your peer will be unable to read your messages too.  So even if you don't attempt to use your keys and you only use your write keys to try to force an update, you have no guarantee that your message will be readable to a peer in the same state you are in.

Put another way, you are effectively saying that you are using an unauthenticated message to determine when to rekey, which gives your attacker a relatively low cost control surface onto your app.

Maybe you can tolerate very low limits for forgeries if you are able to guarantee that your messages win races.  A lock step protocol might easily manage with this limit if the rekey cost is tolerably low.  But I would look instead at p and whether a looser target is better.