RE: Packet number encryption

[Mikkel Fahnøe Jørgensen <[e-mail]>]

The obvious advantage of a clear text nonce is that it can be immediately
decrypted without extra processing and without modifying the packet
content, and it avoids latency from a separate packet number decryption
step.

However, having per path unique nonces per path jumping randomly in order
to gain an insignificant amount of anti-ossification is not every
appealing. Neither is the extra space required for having both packet
numbers and nonces, when they in the majority of cases is one and the same,
effectively. The random jumps are effectively a hidden encryption step
although cheaper than packet number encryption.

So, I propose having a nonce that counts from 0 per path per direction and
also having a unique connection identifier per path direction (asymmetric
CID). Lets call this a half-path context (CID+nonce counter). It could also
work shared path CID as today, but it is not as clean.

The nonce can at most count to 2^32-1 due to hard limits on AES-GCM and
possibly general TLS requirements.

This leaves the packet number encoding:

If we enumerate each half-path with a path ID PID as a simpler counter
starting at zero, we have a 1-1 mapping from PID to CID. The packet number
PN is then encoded as <PID * 2^32 + nonce counter>. The PN is used
explicitly and implicitly in ACK frames but is never carried directly on
the wire.

During path migration packet numbers in the same ACK frame may have large
predictable jumps, but the ACK frame already competently deals with this,
and the jumps are limited to the number of concurrently active paths.

The only loss is the ossification concern of having predictable per path
counters, but I think that is low price of admission. There are no
linkability concerns with this, and all the networking monitoring people
would be happy too.

Kind Regards,
Mikkel Fahnøe Jørgensen


On 9 February 2018 at 21.55.33, Deval, Manasi ([e-mail])
wrote:

Going back to Ian’s point here – Can you be explicit about the issue you
see in the packet number encryption?



Thanks,

Manasi





*From:* QUIC [mailto:[e-mail]] *On Behalf Of *Praveen
Balasubramanian
*Sent:* Friday, February 09, 2018 11:59 AM
*To:* David Benjamin <[e-mail]>
*Cc:* Eric Rescorla <[e-mail]>; [e-mail]; huitema <
[e-mail]>
*Subject:* RE: Packet number encryption



With VLE its minimal overhead per packet so you are not encrypting 4 bytes
more all the time even with 64 bit or 128 bit packet number . So its
decidedly better. Also fewer calls into TLS, but I suppose one could do
some refactoring of TLS API. Many CPUs yes but this is a general purpose
transport and could run on CPUs that don’t.



Didn’t ask for nonce to be variable length. Fixed length for connection
lifetime. Datacenters connections could use 64-bit nonce to avoid frequent
key rollover.



Effectively the plain text nonce is a sequence number since it increases
monotonically with small jumps as needed to avoid ossification. So no worse
off than gQUIC or current draft. No more complex than using the packet
number. Just the starting number is randomized. Also please notice that
this proposal does not preclude using encrypted packet number as the nonce
as proposed previously. Changing how the nonce works makes 0 impact on the
transport logic. An implementation can choose to implement any form of
non-repeating nonce without revving the RFC. This is the biggest advantage
of separation of concerns IMHO.



*From:* David Benjamin [mailto:[e-mail]]
*Sent:* Friday, February 9, 2018 11:39 AM
*To:* Praveen Balasubramanian <[e-mail]>
*Cc:* Eric Rescorla <[e-mail]>; [e-mail]; huitema <
[e-mail]>
*Subject:* Re: Packet number encryption



Your primary worry here was the extra block cipher operation, right? By
moving the packet number into the plaintext, this proposal increases the
length, which will cost that same one extra block cipher operation, no?



It is one block operation under the same key, rather than a different key
so I suppose there are minuscule cache footprint wins (one symmetric key is
16 or 32 bytes). But the cost is per-packet (!) bandwidth and complexity. I
do not see how this could be worth it. Note that, for AES, many CPUs have
dedicated instructions for it already.



> Clear separation of concerns results if we don’t overload the packet
number as the nonce. Connection migration and multi-path are optional
features and we pay no extra compute cost for most connections that are not
impacted by unlnkability. Nonce field becomes optional for crypto that
doesn’t need it and can grow to larger size as needed for bulk transfers to
prevent frequent key rollovers (say in datacenter scenarios).



You're not going to find AEADs that don't require a nonce. Encryption must
not produce the same ciphertext twice for the same plaintext, so you need
some input to diversify them. That input is the nonce. Nonces also are not
variable-length, so you don't get to arbitrarily grow them. (AES-GCM per
spec is variable length, but that's a spec bug. If you size it above 96
bits, it's as if you randomized it and your nonce space crashes per
birthday.)



It is also harmful to separate the two concerns. When you are building a
transport, derive the nonce from a sequence number. TLS 1.2 AES-GCM
separated them, which was a mistake. It's less efficient (the world wasted
quite a lot of bandwidth due to this), and more error-prone. There was
nothing stopping implementations from sending the same nonce or generating
nonces randomly (the AEADs we use don't have large enough nonces for that),
and indeed some did just that. If you use some sort of sequence number, you
can lean on existing work both to filter out the obvious implementation
mistakes and to avoid sending unnecessary data.



On Fri, Feb 9, 2018 at 12:38 PM Praveen Balasubramanian <[e-mail]>
wrote:

Let me try to summarize the proposal again:



   1. Packet number is in the encrypted portion of the header and is no
   longer used as the nonce. It is encoded as a variable length number. Always
   starts at 0.


   1. No ossification of PN
      2. No linkability using PN
      3. Allows for growth beyond 64 bits if needed in future


   1. The nonce is in the clear in plaintext header. It is generated *per
   path* as a secure random number. Call this the “starting value”. Both
   sides MUST initialize the “starting value” nonce *per path*. Within a
   path it grows monotonically (to avoid repeats just like PN today) and can
   include short random jumps periodically so that middleboxes cannot assume
   anything about the field. Since nonce has nothing to do with PN the jumps
   don’t add any complexity to transport logic. Jumps are for greasing and
   preventing ossification. When the nonce rolls over and reaches close to the
   “starting value”, key rollover must happen. At high data rates the nonce
   field can be 64-bits to prevent frequent key rollover. For crypto that
   doesn’t need nonces, the field can be omitted.


   1. No ossification because there is no pre-determined sequence to the
      nonce.
      2. In gQUIC and the RFC as defined the nonce is a simple sequence
      that increments by one, so this is no worse off in terms of
security. It is
      non-repeating.
      3. No linkability because different paths start at a completely
      different random number. If repeating is a concern then
different paths use
      different keys. Carries forward to not just connection migration but
      mutli-path.
      4. Supports key rollover just like gQUIC and currently defined draft
      RFC.
      5. Allows for omitting the nonce when we use crypto that doesn’t need
      it.
      6. Allows for larger nonces for high data rates.
      7. It doesn’t preclude any other type of non-repeating nonces without
      having to modify the RFC! So implementations that want to use
cryptographic
      nonces can still do so.



The downsides:

   1. Even with variable length encoding the extra PN field is more space
   used per packet when a nonce is required. I think we can do with 2 bytes in
   version 1.
   2. It’s not perfect unlinkabiltiy but I have yet to see any solution
   that can provide this. A simple time based analysis using machine learning
   will allow flow correlation especially for connection migration. The IP
   addresses in the clear allow for a high degree of correlation. There is
   also the application sending pattern and other signals that could be used.



*From:* Eric Rescorla [mailto:[e-mail]]
*Sent:* Friday, February 9, 2018 5:52 AM
*To:* Praveen Balasubramanian <[e-mail]>
*Cc:* huitema <[e-mail]>; [e-mail]


*Subject:* Re: Packet number encryption







On Thu, Feb 8, 2018 at 9:40 PM, Praveen Balasubramanian <[e-mail]>
wrote:

Actually taking a step back what if we don’t we overloaded packet number as
the nonce?



Can we:

   1. Put packet number as a separate variable length field in the
   encrypted portion of the header. This allows for growth beyond 64 bits in
   future and completely avoids ossification. For short lived flows variable
   length encoding leads to minimal space overhead.
   2. Put a separate plaintext nonce which starts out as a secure random
   number and monotonically increases as short random jumps (every packet or
   every few packets) and could then rollover. This will prevent linkability
   and scales to multi-path as well. No major compute overhead. We can also
   make the nonce optional for crypto algorithms that do not need a nonce
   saving more space.



I'm not sure how to do #2 safely and efficiently. The primary concern is
that short random jumps don't actually prevent linkability because the high
order bits don't change and long random jumps are effectively randomly
sampling out of the nonce space, and you start to run into birthday
problems. Additionally, the cheapest PRNGs are basically ciphers in counter
mode, so at best you're going to get a small amount of overhead reduction
by getting multiple jump computations out of a single block, though if you
use 96-bit jumps, you only get 25% savings...



-Ekr







Some MSB of the nonce could be used for signaling reorder to the network if
needed. I don’t have the historical context for overloading of PN as the
nonce so pardon me if un-overloading option was discussed and ruled out
before.



*From:* QUIC [mailto:[e-mail]] *On Behalf Of *Praveen
Balasubramanian
*Sent:* Thursday, February 8, 2018 5:51 PM
*To:* huitema <[e-mail]>; [e-mail]
*Subject:* RE: Packet number encryption



>> and using separate packet sequences for each path

This alone prevents linkability right?



>> The packet number on each path will start at 1 (or maybe 0 ;-).

Is supporting multiple paths at the same time a goal? If yes, then yes all
paths will need to have separate tracking and ACK state and congestion
control etc. I thought this is not part of V1 RFC. If its just one
additional path for connection migration scenario then all you need is a
(random) jump to a offset in packet number space for the new path so that
the few packets in the old path can continue for a little bit. This works
with just one ACK space so no implementation complexity.



>> 2) Or, leaving the packet number in the clear but using different
encryption contexts for each path, and using separate packet sequences for
each path.
In addition if the value in the clear was obfuscated with an XOR transform
it will help prevent ossification. The obfuscation is not meant to guard
against later analysis that reveals the packet numbers - why do we care
about that. It is meant to grease the space and not make the numbers serial
so middleboxes cannot assume ordering etc.



All said if I am alone in being concerned about the perf hit then I’d say
go on with option 1.



*From:* QUIC [mailto:[e-mail] <[e-mail]>] *On
Behalf Of *Christian Huitema
*Sent:* Thursday, February 8, 2018 3:54 PM
*To:* [e-mail]
*Subject:* Re: Packet number encryption



On 2/8/2018 1:13 PM, Mike Bishop wrote:

#2 won’t work.  The packet number is an input to the AEAD nonce, so you
have to get to the packet number before you can decrypt the payload.  It
can’t be based on anything internal to the encrypted packet.



In Martin’s proposal, it’s using a combination of the encrypted payload
(which requires nothing to access) and some stored state on each endpoint,
which requires only the Connection ID to look up.  You want the thing you
XOR by to be constantly changing, or it becomes easier to look at sequences
of obfuscated packet numbers and start drawing inferences about what the
XOR value is.  If overhead is the primary concern, I think there are a
couple approaches that might allow you to precompute values and amortize
the cost of doing the encryption step.  (At the cost of keeping the table
of precomputed values, of course.)



I still think Jana’s pushing in the right direction here:  Let’s agree on
goals, and then see if we can craft a design that meets those goals.  I
hear you saying that low overhead is a goal, which I think we can all agree
on.  I also think I hear you saying that 1-1.5% overhead is too high, but
it sounds like there’s less agreement on that.  You also raise an
interesting point that some clients will care less about linkability
because they will never intentionally migrate.


I think Victor said it best, "Obfuscation is just encryption done poorly."
Either we encrypt, or we don't. But there is no such thing as an
obfuscation middle-ground. Obfuscation would just be a speed bump, easily
broken. It won't provide privacy, and it won't prevent linkability.

As far as I am concerned, there are only two designs that prevent
linkability:

1) Martin's PR, in which the packet number is encrypted using sensible
crypto;

2) Or, leaving the packet number in the clear but using different
encryption contexts for each path, and using separate packet sequences for
each path.

The second option requires more computation when explicitly setting up a
new path. The connection ID would be used as part of the "salt" when
deriving connection contexts. The packet number on each path will start at
1 (or maybe 0 ;-). This requires maintaining separate SACK dashboards for
each path/Connection-ID, and constraining ACK to be per/path, or
alternatively adding a PATH-ACK frame that indicates the path for which
packets are acked.

The pros and cons of the two options are easy to get:

1) Option 2 does not require the cost of encrypting every packet, thus per
packet processing will be maybe 1% faster than option 1.

2) Option 2 requires computing encryption contexts for each path, which is
more complex than option 1, but the cost will be amortized over the
duration of the path.

3) Option 2 requires more complex data structures and ACK management, thus
increasing the chances that something goes wrong.

4) Option 2 does nothing against packet number ossification. The packet
number effectively becomes part of the invariants.

In short, the only advantage of option 2 is to avoid a single symmetric
encryption operation per packet, while making the code significantly more
complex, and at the cost of not protecting against PN ossification. The way
I see that, there is hardly any debate.

-- Christian Huitema