Subject: Packet Number Encryption outside of AEAD

From: Mikkel Fahnøe Jørgensen <[email-masked]>
Date: Wed, 25 Jul 2018 23:21:46 -0700

I created the following issue a while ago but go no response, so perhaps it
should have been discussed on this list:

https://github.com/quicwg/base-drafts/issues/1578

The issues covers the point, but in summary:

If the packet format is kept as it is today, but the packet number is not
included in the authenticated data when computing the AEAD tag, then the
decoder need not modify the received packet buffer when decoding the packet
number. This can lead to more efficient hardware implementations and make
multi-processor buffer sharing more effective.

Mikkel

---

From: Ian Swett <[email-masked]>
Date: Thu, 26 Jul 2018 12:52:32 -0400

That seems like a reasonable suggestion to me.

Adding Boris and Manasi to see if they also think it'll make hardware
offload easier?

On Thu, Jul 26, 2018 at 2:22 AM Mikkel Fahnøe Jørgensen <[email-masked]>
wrote:

> I created the following issue a while ago but go no response, so perhaps
> it should have been discussed on this list:
>

---

From: Christian Huitema <[email-masked]>
Date: Thu, 26 Jul 2018 14:33:04 -0700

On 7/26/2018 9:52 AM, Ian Swett wrote:
> On Thu, Jul 26, 2018 at 2:22 AM Mikkel Fahnøe Jørgensen
> <[email-masked] <mailto:[email-masked]>> wrote:
>
>     I created the following issue a while ago but go no response, so
>     perhaps it should have been discussed on this list:
>
>     If the packet format is kept as it is today, but the packet number
>     is not included in the authenticated data when computing the AEAD
>     tag, then the decoder need not modify the received packet buffer
>     when decoding the packet number. This can lead to more efficient
>     hardware implementations and make multi-processor buffer sharing
>     more effective.
>
>     Mikkel
>

It is not just a harware issue. It would make software easier to.
Currently, if we want to decrypt a packet, we need to somehow replace
the PN bytes with a decrypted version and pass that as "authenticated
data" to the AEAD decryption. This is really not necessary, since the
decrypted sequence number is included in the IV.

-- Christian Huitema

---

From: Kazuho Oku <[email-masked]>
Date: Fri, 27 Jul 2018 13:14:14 +0900

> multi-processor buffer sharing more effective.

I am not sure if this is a safe change.

What makes me worried is the fact that we will now have at most three
ways of representing a packet. My understanding is that having
indeterministic encoding is considered dangerous in crypto.

Consider the case where a sender encodes a packet number using 4
octets even when just using 1 octet is enough.

An on-path attacker rewrites the packet by applying XOR 0x80 to the
first octet of the encrypted PN, and trimming the latter three octets
of the encrypted PN.

Then, the attacker can observe if the packet is successfully consumed
by the receiver, and use the fact to infer if the upper 6 bits of the
30-bit PN was equal to the least 6 bits.

I am not sure if this attack is interesting, but allowing multiple
representation does create these kind of attack vectors.

-- 
Kazuho Oku

---

From: Mikkel Fahnøe Jørgensen <[email-masked]>
Date: Fri, 27 Jul 2018 00:02:46 -0700

Yes ideally you should include the packet length in AEAD, which of course
is the case already for long packet headers.

But on the other hand, it is widely accepted in cryptography that is is
safe to send the IV in clear text, and if isn’t, something else is wrong,
so from that point of view there shouldn’t be any dangers. Still it is
mildly disturbing that a verified tag does not correspond to single packet
size.

AES-GCM already includes a length in it’s tag, but it does of course not
cover content it does not include.

I’m not sure if it is reasonable to require a PN always being sent with the
shortest length possible, but it sure would save space on the wire.

Mikkel

On 27 July 2018 at 06.14.16, Kazuho Oku ([email-masked]) wrote:

> I created the following issue a while ago but go no response, so perhaps
it

-- 
Kazuho Oku

---

From: Christian Huitema <[email-masked]>
Date: Fri, 27 Jul 2018 06:43:22 -0700

> first octet of the encrypted PN, and trimming the latter three octets
That attack does not work, because the encoding of the PN is big-endian.
The actual packet number is in the fourth octet. Or rather, it only
works in the special case where the PN is 0.

-- Christian Huitema

---

From: "Deval, Manasi" <[email-masked]>
Date: Fri, 27 Jul 2018 22:11:31 +0000

About the issue of Packet Number Encryption outside of AEAD - We agree it simplifies both hardware and software logic. It also allows the2 encryption operations to run mostly in parallel, so it is a welcome modification.

Thanks,
Manasi

-----Original Message-----
From: QUIC [mailto:[email-masked]] On Behalf Of Christian Huitema
Sent: Friday, July 27, 2018 6:43 AM
To: Kazuho Oku <[email-masked]>; Mikkel Fahnøe Jørgensen <[email-masked]>
Cc: IETF QUIC WG <[email-masked]>
Subject: Re: Packet Number Encryption outside of AEAD

-- Christian Huitema

---

From: Kazuho Oku <[email-masked]>
Date: Sat, 28 Jul 2018 21:35:06 +0900

> works in the special case where the PN is 0.

I do not see how the issue relates to the endianness.

Consider the following case.

encrypted PN + payload: 46 5f 00 01 02 03 04 05 06 07 08 09 0a 0b 0c
0d 0e 0f 10 11
AES-CTR mask for PN: c5 5c

The PN field after decryption is 83 03. IV used for PNE is 02 03 .. 11.

Attacker applies XOR 0x80 (to change the PN field length from 2 to 1)
and removes the second octet.

The modified encrypted PN + payload becomes: c6 00 01 02 03 04 05 06
07 08 09 0a 0b 0c 0d 0e 0f 10 11.

The PN field after decryption is 03, and IV used for PNE is 02 03 .. 11.

In such case, the receiver will successfully process the modified
input if the PN was expressible using one octet, thereby leaking the
fact that the first 6 bits of the 16-bit PN was equal to the least
significant 6 bits of the PN and that the 7th and 8th bits were zero.

Admittedly, this attack relies on the fact that the frames contained
in the packet are 2 octets. But I am not sure if this is the _only_
attack that is possible.

Am I missing something?

Besides, note also that the proposed change will prevent us from using
the PNE key to encrypt other information. For example, in #1322, we
have been discussing about how to protect the key-phase bit. It seemed
to me that we were leaning towards encrypting the key-phase bit using
the PNE key. That would no longer be possible (or lead to other
security concerns) if we adopt this proposal.

-- 
Kazuho Oku

---

From: Kazuho Oku <[email-masked]>
Date: Sat, 28 Jul 2018 22:16:02 +0900

> About the issue of Packet Number Encryption outside of AEAD - We agree it simplifies both hardware and software logic. It also allows the2 encryption operations to run mostly in parallel, so it is…

Would you mind elaborating a bit on how the proposed change would help
parallelization?

My understanding is that it does not help parallelizing "encryption",
because the only change is if you have the cleartext PN (which is
something you can prepare beforehand) as part of the AAD.

I also do not understand how it helps parallelizing decryption in practice.

The proposed change removes cleartext PN from AAD. It sounds like that
you would then have a chance to start processing AAD for GCM. But I am
not sure if that is correct.

In the current approach, input to GCM is: GCM(first-octet || CID ||
plaintext-PN || payload).

With the proposed change, it becomes: GCM(fist-octet || CID || payload).

Because where the payload begins depends on the value of the PN being
decrypted, in both cases you have the same degree of parallelism. You
can process GCM to the end of CID, but no more.

To conclude, I do not see how the proposed change helps parallelize
the encoder or the decoder.

-- 
Kazuho Oku

---

From: Mikkel Fahnøe Jørgensen <[email-masked]>
Date: Sat, 28 Jul 2018 06:44:35 -0700

You can have one core with access to an input queue that does nothing but
decrypting packet numbers.
The decrypted PN’s are placed on a queue.
Meanwhile one or several other cores verify the AEAD tag and places
validation on a queue.
A third set of cores processes decryption and places decrypted packets on a
queue. High priority frames are read from the decrypted packet queue and
processed, pending tag confirmation.
A fourth set of cores deal with ACK processing and other packet number
sensitive content.

If the original receive buffer needs to be modified, you first incur the
PNE decryption delay, then you force a possibly shared cache line into
exclusive mode by writing to the buffer. The separate concurrent stages now
not only have to wait for PNE, but also for the inter-processor cache
coherency synchronisation to take effect.

For encoding there are fewer benefits, but one is that you can encrypt
buffers without deciding the packet number immediately. This might be
helpful if sending via multiple cores feeding to a final transmit process
that synchronises packet numbers and applies PNE before sending data on the
wire.

Kind Regards,
Mikkel Fahnøe Jørgensen

On 28 July 2018 at 15.16.03, Kazuho Oku ([email-masked]) wrote:

2018-07-28 7:11 GMT+09:00 Deval, Manasi <[email-masked]>:
> About the issue of Packet Number Encryption outside of AEAD - We agree it
simplifies both hardware and software logic. It also allows the2 encryption
operations to run mostly in parallel, so it is a welcome modification.

-- 
Kazuho Oku

---

From: Kazuho Oku <[email-masked]>
Date: Sat, 28 Jul 2018 23:24:10 +0900

> Meanwhile one or several other cores verify the AEAD tag and places

My point is that you cannot run PN decryption and AEAD tag
verification in parallel, because the input to GCM, specifically the
beginning offset of the ciphertext, depends on the length of the PN
field, a value that becomes available only after decrypting the PN
field.

The input that can be given to GCM is the first octet and CID,
regardless of the proposed change.

In the current approach, GCM calculation needs to wait for the result
of PN decryption, because it is the value that is fed to GCM following
the CID.

With the proposed change, GCM calculation still needs to wait for the
result of the PN decryption to determine where the ciphertext begins,
because the ciphertext is fed the thing that is fed to GCM following
the CID.

> If the original receive buffer needs to be modified, you first incur the PNE
> decryption delay, then you force a possibly shared cache line into exclusive
> mode by writing to the buffer. The separate concurrent stages now not only
> have to wait for PNE, but also for the inter-processor cache coherency
> synchronisation to take effect.
>

-- 
Kazuho Oku

---

From: Christian Huitema <[email-masked]>
Date: Sat, 28 Jul 2018 07:40:28 -0700

I think that Kazuho is making a strong point. The PNE is somewhat malleable, so there is indeed a risk in not using AEAD to protect the encoding. 

There are potential gains in not including the encoding in AEAD, but they are pretty small. There is no actual need to decrypt the PN in place and modify the input buffer. You can always decrypt it in a secondary buffer and use a scatter-gather API for AEAD input. Or you can copy the entire decrypted header in a secondary buffer if you don't have access to scatter-gather API.

-- Christian Huitema 

> On Jul 28, 2018, at 6:44 AM, Mikkel Fahnøe Jørgensen <[email-masked]> wrote:
> 
> You can have one core with access to an input queue that does nothing but decrypting packet numbers.
> Meanwhile one or several other cores verify the AEAD tag and places validation on a queue.
> A third set of cores processes decryption and places decrypted packets on a queue. High priority frames are read from the decrypted packet queue and processed, pending tag confirmation.
> A fourth set of cores deal with ACK processing and other packet number sensitive content.
> 
> If the original receive buffer needs to be modified, you first incur the PNE decryption delay, then you force a possibly shared cache line into exclusive mode by writing to the buffer. The separate concurrent stages now not only have to wait for PNE, but also for the inter-processor cache coherency synchronisation to take effect.
> 
> For encoding there are fewer benefits, but one is that you can encrypt buffers without deciding the packet number immediately. This might be helpful if sending via multiple cores feeding to a final transmit process that synchronises packet numbers and applies PNE before sending data on the wire.
> 
> 
> Kind Regards,
> Mikkel Fahnøe Jørgensen
> 
>

---

From: Mikkel Fahnøe Jørgensen <[email-masked]>
Date: Sat, 28 Jul 2018 08:13:14 -0700

Yes, the fact that you don’t know the PN length is a problem.
The PN length could be sent in clear text. Would that be a problem?

Copying is not very useful if you want to pipeline packets.
A gather API can work but it complicates things, especially in hardware.

Kind Regards,
Mikkel Fahnøe Jørgensen

On 28 July 2018 at 16.40.43, Christian Huitema ([email-masked]) wrote:

I think that Kazuho is making a strong point. The PNE is somewhat
malleable, so there is indeed a risk in not using AEAD to protect the
encoding.

There are potential gains in not including the encoding in AEAD, but they
are pretty small. There is no actual need to decrypt the PN in place and
modify the input buffer. You can always decrypt it in a secondary buffer
and use a scatter-gather API for AEAD input. Or you can copy the entire
decrypted header in a secondary buffer if you don't have access to
scatter-gather API.

-- Christian Huitema

On Jul 28, 2018, at 6:44 AM, Mikkel Fahnøe Jørgensen <[email-masked]>
wrote:

Kind Regards,
Mikkel Fahnøe Jørgensen

--
Kazuho Oku

---

From: Kazuho Oku <[email-masked]>
Date: Sun, 29 Jul 2018 03:13:57 +0900

> The PN length could be sent in clear text. Would that be a problem?

That would be a problem.

An endpoint can select the size of the PN field based on the number of
packets inflight. For such an implementation, sending the size of the
field effectively means leaking RTT.

> I think that Kazuho is making a strong point. The PNE is somewhat malleable,
> so there is indeed a risk in not using AEAD to protect the encoding.
>
> modify the input buffer. You can always decrypt it in a secondary buffer and
> use a scatter-gather API for AEAD input. Or you can copy the entire

-- 
Kazuho Oku