Re: Packet number encryption

[David Benjamin <[e-mail]>]

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
>    2. 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
>
>
>