Subject: Re: [quicwg/base-drafts] Packet number encryption (#1079)

From: MikkelFJ <[email-masked]>
Date: Thu, 01 Feb 2018 03:38:43 -0800

mikkelfj commented on this pull request.

> +on the negotiated AEAD.
+
+Packet number protection is applied after packet protection is applied (see
+{{aead}}).  The ciphertext of the packet is sampled and used as input to an
+encryption algorithm.  For packets with a long header, the ciphertext starting
+immediately after the packet number is used (that is, octet 17 onwards).  For
+packets with a short header, the packet number length is not known, so it is
+assumed to be its largest possible length (4 octets).  Thus, for a short header,
+the sampled ciphertext starts at either octet 5 when the connection ID is
+omitted, or octet 13 when the connection is present.
+
+The protected packet might not have produced enough input for the negotiated
+packet protection algorithm.  This might happen if a packet with a short header
+contains minimal data and uses a packet number encoding that is shorter than 4
+octets.  Additional zero octets are added to the end of the sequence to reach
+the required amount of data.

I was about to propose something similar to @huitema but then thought zero padding might do just as well.

However, I think it is better to take the tail content when the default start overreach because then you can always consume the content directly without moving it to a separate buffer. It's a quite simple solution.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1079#discussion_r165331679

---

From: Christopher Wood <[email-masked]>
Date: Thu, 01 Feb 2018 15:56:09 +0000 (UTC)

chris-wood commented on this pull request.

> +### ChaCha20-Based Packet Number Protection
+
+When AEAD_CHACHA20_POLY1305 is in use, packet number protection uses the
+raw ChaCha20 function as defined in Section 2.4 of {{!CHACHA}}.  This uses a
+256-bit key and 16 octets sampled from the packet protection output.
+
+The first 4 octets of the sampled ciphertext are interpreted as a 32-bit number
+in little-endian order and are used as the block count.  The remaining 12 octets
+are interpreted as three concatenated 32-bit numbers in little-endian order and
+used as the nonce.
+
+The encoded packet number is encrypted with ChaCha20 directly.  In pseudocode:
+
+~~~
+encoded = EncodePacketNumber(packet_number)
+counter = DecodeLE(sample[0..3])

Missing sample definition, or is it just assumed to be the same as with AES?

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1079#pullrequestreview-93332425

---

From: Christopher Wood <[email-masked]>
Date: Thu, 01 Feb 2018 15:58:53 +0000 (UTC)

+Use of the same key and nonce more than once can weaken the guarantees provided
+by this protection.  For the schemes described, protecting two different packet
+numbers with the same key and nonce reveals the exclusive OR of those packet
+numbers, which might be used to compromise confidentiality.  For packet number
+protection to be effective, the output of the packet protection AEAD needs to be
+effectively random.
+
+All the AEAD functions used meet indistinguishability under (adaptive) chosen
+plaintext attack (IND-CPA, IND-CPA2) goals and produce minimal expansion of the
+plaintext, adding only an authentication tag.  Therefore, this document assumes
+that each bit of sampled AEAD output contains one bit of entropy and that an
+attacker is unable to reduce this without knowledge of the key.  Based on this
+assumption, the odds of two samples of ciphertext being identical approach the
+birthday bound for the size of the sample (that is, two to the negative power of
+half the number of sampled bits).

Possible simplification of these three paragraphs: 

Assuming all AEAD functions used are reducible to PRFs, an (encoded) packet number p is encrypted as:

~~~
    p XOR PRF(pn_key, m),
~~~

where m is an L-bit string sampled from a protected packet’s ciphertext. This construction is secure 
against chosen plaintext attacks (IND-CPA) if the distribution of m is uniform over {0,1}^L {{KatzLindell}}. 
Since AEAD schemes are semantically secure, we assume each bit of sampled ciphertext contains one bit 
of entropy. Thus, two ciphertexts will collide, possibly leading to nonce reuse, with probability bounded by 
2^(-L/2), i.e., the birthday bound. Use of the same key and nonce more than once can weaken the 
guarantees provided by this protection. For the schemes described, protecting two different packet 
numbers with the same key and nonce reveals the exclusive OR of those packet numbers, which might be 
used to compromise confidentiality. 

KatzLindell: Katz, Jonathan, and Yehuda Lindell. Introduction to modern cryptography. CRC press, 2014.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1079#pullrequestreview-93333605

---

From: Christian Huitema <[email-masked]>
Date: Thu, 01 Feb 2018 21:19:54 +0000 (UTC)

huitema commented on this pull request.

+the sampled ciphertext starts at either octet 5 when the connection ID is
+omitted, or octet 13 when the connection is present.
+
+The protected packet might not have produced enough input for the negotiated
+packet protection algorithm.  This might happen if a packet with a short header
+contains minimal data and uses a packet number encoding that is shorter than 4
+octets.  Additional zero octets are added to the end of the sequence to reach
+the required amount of data.
+
+Before a TLS ciphersuite can be used with QUIC, a packet protection algorithm
+MUST be specifed for the AEAD used with that ciphersuite.  This document defines
+algorithms for AEAD_AES_128_GCM, AEAD_AES_128_CCM, AEAD_AES_256_GCM,
+AEAD_AES_256_CCM (all AES AEADs are defined in {{!RFC5116}}), and
+AEAD_CHACHA20_POLY1305 ({{!CHACHA=RFC7539}}).
+

I find this whole section hard to understand and hard to implement. I would like to see much more uniformity between the various constructs. I get the following:

1) We are going to use the same encryption algorithm for PN as the encryption algorithm part of AEAD.

2) There will be a specific key for PN encryption, different from the key used for data encryption. 

3) The PN encryption will use a 16 byte sample of the packet's ciphertext as nonce.

4) Our AEAD specification tells us that the nonce is obtained by combining a preset IV with a sequence number. In our case, we will use the first 4 bytes of the sample as a 32 bit sequence number, and the last 12 bytes of the sample as IV, zero padded to the length required by the selected algorithm if necessary. 

5) Conceptually, AEAD algorithm encode an N byte filed by XOR it with a crypto-graphically generated stream of data, plus a 16 byte MAC. When doing PN encryption, we only use the first N bytes of the output, and do not compute or check the MAC. That is, PN encryption uses the "XOR" subset of the AEAD algorithm.

6) Using only the XOR part of the AEAD algorithm requires specific optimizations depending on the specific AEAD algorithm. These optimizations are presented in the following sections for AES and CHACHA20.

7) One way to test that a PN encryption implementation is correct is to compute the AEAD encryption of the PN with the selected IV and sequence number, and verify that the AEAD algorithm provides for the same initial bytes as the PN encryption implementation.

Do we agree on that?

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1079#pullrequestreview-93441330

---

From: Martin Thomson <[email-masked]>
Date: Thu, 01 Feb 2018 17:07:44 -0800

martinthomson commented on this pull request.

I think that's the right formulation: we assume that the AEAD is a PRF.  It's not guaranteed to be by the contract, but it's probably true for the AEADs here.  Thanks for the text.  I'll probably want to make the assumption much more prominent though.  Also, the general form here is using AES or ChaCha as a PRF, so that means that we can factor out the cipher-specific parts.

I'll see what I can do.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1079#discussion_r165535019

---

From: Martin Thomson <[email-masked]>
Date: Fri, 02 Feb 2018 03:27:46 +0000 (UTC)

You can consider this an application of the AEAD, but I think that would be an error.  I prefer to think of this as using the same primitives that the AEAD uses.  That is, we build AEAD_AES_128_GCM using AES, and so we use AES here.

There are commonalities in the design, and I suspect that if you abuse your AEAD interface hard enough, you can get the AEAD to produce the right bits, but that's probably inefficient (you don't need the MAC, but the AEAD will calculate one) and not a general solution (there is no guarantee that the AEAD puts the MAC at the end, or doesn't do other post-processing that would might this design).

The reason for that is part of what we sample from the ciphertext of the packet is fed into the counter part and most AEADs don't let you tweak that (all AEADs I've seen have an internal counter that starts from 0 for each invocation).  We need that counter because the 96-bit nonce doesn't have enough entropy.  128 bits ensures that we don't have to worry about collisions, because we can only send 2^62 packets.

So 1 - shared primitives, not same, 2 - agreed, 3 - this will depend on AEAD, unfortunately, 4 - that's internal AEAD details, 5 - that's AEAD-specific, 6 - see point about shared primitives, 7 - this might be true for the current AEADs if you can abuse them enough, but it's not generally true.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1079#discussion_r165551157

---

From: Martin Thomson <[email-masked]>
Date: Fri, 02 Feb 2018 03:30:40 +0000 (UTC)

@martinthomson pushed 1 commit.

a0d40c3  Take and rework suggestions by @cwood

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/1079/files/810ae7f4c1d5fc83ea6b5c1a05ac59bb210212a5..a0d40c32029dc8e81bbac08b97860df3f04dcc10

---

From: Christian Huitema <[email-masked]>
Date: Thu, 01 Feb 2018 19:52:13 -0800

I think Kazuho has a plausible generalization with his CTR mode API. Maybe we should find a way to document that.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1079#discussion_r165553428

---

From: Martin Thomson <[email-masked]>
Date: Fri, 02 Feb 2018 04:06:44 +0000 (UTC)

We can't know that there is a CTR mode for the underlying primitive.  I'm happy to include some advice along the lines of "for AES, this is just CTR mode", or a hint that in general CTR mode is a good design, but any further generalization is a presumption that might make it harder to deploy a new cipher.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1079#discussion_r165554606

---

From: Kazuho Oku <[email-masked]>
Date: Fri, 02 Feb 2018 04:15:58 +0000 (UTC)

kazuho commented on this pull request.

I can understand @martinthomson's point that if a stream cipher (or block cipher in CTR mode) exists beneath an AEAD is an implementation detail. Hence we need a mapping.

I also agree with @huitema that it would help implementors if the AES algorithm was explained as CTR mode. That would help people come up with an implementation that shares the code between the cipher suites.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1079#discussion_r165555327

---

From: Martin Thomson <[email-masked]>
Date: Fri, 02 Feb 2018 04:20:03 +0000 (UTC)

737c4ee  Just use AES-CTR

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/1079/files/a0d40c32029dc8e81bbac08b97860df3f04dcc10..737c4ee183f67469c18a0954dd78dae45ddc42fa

---

From: Martin Thomson <[email-masked]>
Date: Fri, 02 Feb 2018 04:27:57 +0000 (UTC)

> @@ -866,6 +867,85 @@ the connection that is hosted on stream 0.  This sequence number is not visible
 to QUIC.

+## Packet Number Protection {#pn-encrypt}

So this isn't missed by people reviewing, I've taken this suggestion.  That way we can make stronger assertions about birthday bounds.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1079#discussion_r165556080

---

From: Brian Trammell <[email-masked]>
Date: Fri, 02 Feb 2018 12:42:25 +0000 (UTC)

The section "Receiving Protected Packets" needs to be updated as part of this PR; at least

> Failure to unprotect a packet does not necessarily indicate the existence of a
protocol error in a peer or an attack.  The truncated packet number encoding
used in QUIC can cause packet numbers to be decoded incorrectly if they are
delayed significantly.

no longer holds.

I'd also suggest adding a more in-depth outline of what a receiver should do with a given packet to this section -- I went through the exercise of doing this myself, and it alleviated many of my concerns about the complexity of this approach.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1079#issuecomment-362576322

---

From: Martin Thomson <[email-masked]>
Date: Fri, 02 Feb 2018 14:18:17 -0800

@britram, that statement is still true.

I've noted the suggestion.  Monday.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1079#issuecomment-362724479

---

From: Christian Huitema <[email-masked]>
Date: Sat, 03 Feb 2018 04:41:04 +0000 (UTC)

With the updated text, I understand very well where to pick the sample. That's good. But there is still an issue. You note that "For packets with a short header, the packet number length is not known before decryption". If that is the case, then the receiver has to decode the first PN byte, get the length, then decode the other bytes. That means either two passes of encryption, or doing the XOR manually. Not great.

I would prefer "encrypt from the beginning of the PN to just before the start of the sample". One pass, no fuss.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1079#discussion_r165804822

---

From: Martin Thomson <[email-masked]>
Date: Sun, 04 Feb 2018 23:26:10 +0000 (UTC)

Why not copy out 4 octets, XOR those, and then read off the PN?  Any excess will be nonsense, but you aren't using those bits.  That should be perfectly efficient and it's very easy to implement. 

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1079#discussion_r165862551

---

From: Martin Thomson <[email-masked]>
Date: Wed, 07 Feb 2018 00:30:13 +0000 (UTC)

894e0fe  Make the order of operations clearer.

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/1079/files/737c4ee183f67469c18a0954dd78dae45ddc42fa..894e0fe7006407fd1730748a3396aa4c47241297

---

From: MikkelFJ <[email-masked]>
Date: Wed, 21 Feb 2018 21:43:49 +0000 (UTC)

The CCM mode has a 16 byte header that includes the nonce - it won't be encrypted unless it is taken care of explicitly for that mode and if it isn't encrypted, encrypting the packer number is pointless.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1079#discussion_r169787251

---

From: ekr <[email-masked]>
Date: Wed, 21 Feb 2018 22:42:25 +0000 (UTC)

ekr commented on this pull request.

@mikkelfj: I believe you have misunderstood how CCM is used in TLS (and presumably in QUIC).

The inputs to CCM encryption are:

- A nonce N
- The key
- The plaintext
- The associated data A

The inputs to CCM decryption are:

- A nonce N
- The key
- The ciphertext
- The associated data A

In some versions of CCM, you explicitly render N on the wire, but in TLS 1.3, you would not do this, but rather (as in AES-GCM), derive it from the PN. There is then no need to render the nonce on the wire, and it behaves as GCM does.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1079#discussion_r169802077

---

From: MikkelFJ <[email-masked]>
Date: Wed, 21 Feb 2018 15:32:40 -0800

That is reassuring to hear. I original found an older RFC 3610, but I then checked  TLS 1.3 draft 23 which referred to RFC 5116 which in turn referred via https://tools.ietf.org/html/rfc5116#ref-CCM to NIST https://csrc.nist.gov/publications/detail/sp/800-38c/final appendix A, which lists said header with NONCE - but it wasn't very clearly formulated, so I (apparently incorrectly) assumed it was similar to https://tools.ietf.org/html/rfc3610 except for fixed parameters chosen in the header (as I would have expected).

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1079#discussion_r169812478