Re: Hardware acceleration and packet number encryption

[Eric Rescorla <[e-mail]>]

I think it would probably be useful to ask this question in two pieces.

1. Is PN something we would want to do if it were free from a performance
perspective?
2. What are the technical options for building PN encryption, and then are
the costs acceptable?

My answer to #1 is "yes", but I imagine there are others who disagree. So
we should probably get that out of the way.

#2 obviously requires some technical thought. I am aware of three major
design options:

1. One like the one in PR#1079 where you separately encrypt the PN.
2. One with an external nonce like the one Kazuho describes.
3. A more exotic solution like AERO (
https://tools.ietf.org/html/draft-mcgrew-aero-00#ref-MF07).

PR#1079 has the disadvantage of double buffering.

An external nonce is possible but is a bit tricky. It is critical it be
nonrepeating, and if you randomly generate n-bit nonces, then the collision
bound gets scarily large before 2^{n/2}. So, for instance in Kazuho's
suggestion, you would be able to encrypt well less than 2^{32} packets
before you needed to rekey in some way, which is pretty suboptimal. Even 96
bits is not great. The difficulty of getting this right is one reason why
TLS 1.3 changed from TLS 1.2's explicit nonce to an implicit nonce based on
the counter. The canonical way to generate a sequence like this is to feed
a counter into a pseudo-random permutation, but our standard efficient PRP
is AES, and that works on 128 bits. I'm asking cryptographers if they have
a better plan.

Finally, we could use a more exotic solution like AERO. The draft has
details, but roughly speaking, it's like an extension of AEAD which also
takes the sequence number as an input on encryption and then returns it on
decryption, so you don't need a separate sequence number or nonce.
Obviously this is pretty much designed for our purpose, but it's a
relatively new construction and so I don't know how much analysis there has
been of its security. In addition, while it's based on AES-CTR, I don't
know what the performance is like in hardware.

-Ekr















On Sat, Mar 24, 2018 at 1:59 PM, Kazuho Oku <[e-mail]> wrote:

> Hi Christian,
>
> Thank you for starting the discussion. My comments inline.
>
> 2018/03/24 13:18、Christian Huitema <[e-mail]>のメール:
>
> There were a number of corridor discussions of hardware acceleration of
> Quic during the IETF meeting. In particular, Manasi Deval asked many of
> us our opinion about packet number encryption. From the conversation, I
> understand that packet number encryption as specified would make
> acceleration of Quic difficult to implement on Intel's hardware. She was
> trying to convince us that privacy is an unattainable goal, and that we
> should just as well ditch the linkability requirement in order to
> facilitate hardware acceleration.
>
>
> I would argue that packet number encryption and hardware offloading are
> not exclusive goals.
>
>
> The only reason the current proposed form of packet number encryption is
> requiring two-path encryption is because it uses packet number as a nonce
> as well.
>
>
> That means that we can attain both goals for example by using an explicit
> nonce and sending packet number as encrypted payload. The downside of such
> approach will be that per-packet overhead will increase (likely by 8
> bytes or so) and that we would be required to discuss how to tackle
> nonce-reuse.
>
>
> I am not sure if providing support for **current form of** hardware is
> necessary, but assuming that we decide so, I'd prefer using explicit
> nonce or any other way that provides both one-path encryption and packet
> number encryption.
>
>
> I would much rather see the issue
> debated in the open than in a series of 1-1 conversations. After all,
> open discussion is a key tenet of the IETF.
>
> When I look at the potential trade-offs, I see the following, which have
> been proposed at different times:
>
> 1- Single sequence number of all paths, starting at 0 (or 1), numbers
> sent in clear text;
>
> 2- Single sequence number for all paths, starting at 0 (or 1),
> obfuscated via a different random offset for each path. (We will assume
> that the offset is tied to the connection ID used in the path.)
>
> 3- Single sequence number for all paths, starting at 0, combined with
> packet number encryption as specified in PR1079.
>
> 4- Separate sequence number for each path, starting at 0 (or 1), numbers
> sent in clear text. (We will assume that the there will be a separate
> connection ID per path, so the combination of connection ID and sequence
> number is unique.)
>
> 5- Single sequence number for all paths, starting at 0, combined with a
> simpler packet number encryption than specified in PR1079.
>
> These options have different costs in term of privacy (linkability),
> ossification, hardware acceleration, and software complexity.
>
> Having a single sequence number sent in clear text on all paths (option
> 1) makes it very easy to correlate different paths. We also know that
> the random offset solutions (option 2) only provide a modest defense
> against linkability if the activity on two paths overlaps. It would
> definitely now be adequate for multipath, and it is probably not
> adequate either for the "make before break" variants of path migration.
> The other variants prevent linkability either by encrypting the sequence
> number, or by using different sequence numbers on different paths.
>
> Only encryption prevents ossification. If we send packet numbers in
> clear text (option 1 or 4), or even if we use simple obfuscation (option
> 2), middle-boxes can find the position of the sequence numbers by
> comparing the headers of successive packets. There are high chances that
> we would then see half-brained schemes, such as delaying packets for
> reordering, or enforcing some kind of sequence range. This is a classic
> ossification scenario.
>
> Packet number encryption as specified in PR 1079 relies on a two-pass
> algorithm. First encrypt the packet, then use the result of the
> encryption as a nonce when encrypting the sequence number. It seems that
> this two-pass approach forces double buffering in the acceleration
> hardware. Opinions vary about how bad that is, and hardware specialist
> should really explain the problem if they believe it is important. There
> may be different ways to encrypt the packet number (option 5) that do
> not require double buffering, but this is merely a theoretical
> possibility. Those schemes are not specified.
>
> Using separate packet number for each path would prevent linkability and
> facilitate acceleration, but it makes the protocol and the software
> significantly more complex..
>
>
> Actually, I think that packet number encryption makes multi-path easier.
>
>
> Both AES and chachapoly allows up to 96-bit nonce, while we only use 64
> bits. Remaining 32 bits are left zero. In that space, we can store
> path-id (that is incremented by one for every new path) to avoid
> nonce-reuse.
>
>
> By doing so, each path can start with packet number zero while using the
> same encryption key for all paths.
>
>
> It requires using different keys or IV for
> different paths, and it also require management of several sequence
> number spaces. Since the packet with number "3" on path 1 will not be
> the same packet as number "3" on path 2, the acknowledgements will need
> to be tied to a path, either implicitly because they are sent on that
> path, or explicitly by tagging the ACK frame with a path specific
> connection ID. We would probably need both, because in migration
> scenarios it is useful to send on the new path acknowledgement of
> packets received on the old path. This kinds of complexity breeds bugs
> and interoperability issues. Plus, this solution does not prevent
> ossification, as discussed above.
>
> My personal preference is to start with PR 1079, which is a sound
> solution to all problems except acceleration. The acceleration issue
> should be discussed in the open, and we probably want to hear from more
> than one possible hardware vendor. Do all hardware makers have an issue
> with double buffering, or is this just specific to one particular
> architecture? Is it worth exploring alternative packet number encryption
> techniques that would not have the double buffering issue?
>
> -- Christian Huitema
>
>
>
>