Applied AEAD limits in (D)TLS, QUIC, OSCORE, ...

[John Mattsson <[e-mail]>]

Hi,

I took a more detailed look at how (D)TLS and QUIC apply the advantage bounds in practice. If I have understood correctly, (D)TLS and QUIC set bounds on CA and IA for a single key (called CA_key and IA_key below) and then force a rekey when (or before) this limit is reached. 

I think it is great that the AEAD limit work has made it clear that counters for v and q as well as frequent rekeying are needed. However the process of limiting CA/IA per key does not seem like the right thing to do for a security protocol where each connection has many keys, communication between two parties can use many connections, and adversaries can often trick the parties to tear down the old connection and set up a new connection. I think a general process need to be designed a bit differently.

The concrete limits on v and q set by (D)TLS 1.3 and QUIC seem essential to keep the GCM CA, CCM CA, and the CCM success probability per forgery attempt low. The process used can however give a bit strange and misleading results as seen below:



Example 1: The ideal t-bit MAC

IA_key = v / 2^t

Using the process of setting an upper bound p = 2^-57 for a single key gives v <= 2^t * 2^-57 and following QUIC and DTLS you must re-key when that limit is reached, but this does not improve the security at all for the ideal MAC. The forgery probability of each packet is always 2^-t anyway.


Example 2: Sending 2^64 packets with ChaCha20-Poly1305 (l=2^10)

CA_key <= v * l / 2^103

a) Rekying every TLS packet gives CA_key <= 2^-93
b) Rekying every 2^36 TLS packet gives CA_key <= 2^-57
c) Rekying every 2^64 TLS packet gives CA_key <= 2^-27

These looks drastically different, but assuming the single-key bounds are tight, an adversary trying to attack the whole connection can do so with an advantage of 2^-27 (CA_key * number of keys) for all three options.


Example 3: IA bounderies per key.

DTLS 1.3 limits IA per key but does not limit the number of keys per connection. That means an attacker can make IA for the connection arbitrary high. Limiting the IA per connection does not help either if the assumption is that the parties just set up a new connection. The only possible thing to do is likely to limit the forgery success probability per forgery attempt.



It seems quite easy to see from the inequalities when rekeying lower the advantage for the connection as a whole. Looking at the the single-key inequalities. If the dominating term in the advantage it proportional to q^2 or v^2 it is beneficial to re-key also for small v and q.

AES-GCM CA <= ((s + q + 1)^2) / 2^129
AES-CCM CA <= (2l * q)^2 / 2^128
AES-CCM IA <= v / 2^128 + (2l * (v + q))^2 / 2^128

If the advantage is proportional to q or v, re-keying does not lower the advantage for the connection as a whole even for large v and q:

AES-GCM IA <= 2 * (v * (l + 1)) / 2^128
ChaCha  CA <= v * ((8 * l) / 2^106)
ChaCha  IA <= v * ((8 * l) / 2^106)

For AES-CCM with 64-bit tags, the advantage is dominated by the term 
v / 2^64 when v,q is small and the term (2l * (v + q))^2 / 2^128 when v,q are larger.

AES-CCM_8 IA <= v / 2^64 + (2l * (v + q))^2 / 2^128

Assuming l=2^8 and limits v = q = 2^40, the integrity advantage after 2^40 packages is IA <= 2^-24 + 2^-28 which is very close to the advantage IA = 2^-24 for an ideal 64-bit MAC after 2^40 forgery attempts. CCM_8 has much worse IA than the other algorithms because of it tag length, but rekeying frequently does not improve application security.



To summarize:

- For GCM CA, CCM CA, and CCM IA, counters for v and q and rekeying definitely needs to be mandated to keep the quadricly growing advantage bounded. I think the AEAD limit work is great in showing the need for this. Thank you!

- The limits in the DLTS 1.3 draft also puts clear bounds on CA for the whole connection, CA per protected message, and IA per forgery attempt, which is great. The CA advantage for an attacker for the whole connection varies quite a lot between the algorithms, but that is ok. The limits in DTLS 1.3 does not limit the IA for the whole connection.

- I think the process to put a limit on CA and IA for a single key does not give the wanted results for a security protocol with many keys per connection, many connection per peers, and attackers can force new connections. It might be better to look at "multi-key" security involving all the keys in the connection and calculating CA/IA for a connection with a fixed number of messages. The best approach is might however be to just look at "single-key" security and set maximum limits for CA / q and IA / v or something similar. 

- When using CCM_8, frequent rekeying does not significantly improve IA for a long connection. When v << 2^40 and q << 2^40 CCM_8 is very close to an ideal 64-bit MAC. Any 64-bit MAC does of course provide much worse IA than a good 128-bit MAC.

- Very frequent rekeying should be recommended, but maybe even more as a way to limit the effect of key leagage then to lower CA and IA. This put higher requirements (forward secrecy, post-compromise security) on which re-keying mechanism that is used.

- I don't see any need for DTLS 1.3 and QUIC to change except maybe being more allowing to CCM_8 for IoT applications. I think CORE should introduce counters for v and q and rekeying, but probably use a slightly different process. I see no need to frequently rekey CCM_8. CCM_8 is close to the ideal 64-bit MAC unless for high values of v and q. CCM_8 is ok as long as 64-bit MACs are acceptable, which I think they are, especially for constrained IoT radio, where sending 2^64 packets (4.3 billion messages per second for 68 years) is infeasible.

Cheers,
John