RE: Packet number encryption

[Praveen Balasubramanian <[e-mail]>]

The proposal is to keep the PN in encrypted portion of header and use a dedicated nonce in plain text. If non-repeating nonce is needed with that probability then we will need much larger nonce since 10 Gbps+ rates are common in the datacenter. A nonce can simply be generated using PRNG. Why does the peer’s PRNG matter? The peer uses a different PN space. The jumps are completely determined by the sender as needed and its just to prevent ossification of assuming that nonce always increments by 1.

From: Mikkel Fahnøe Jørgensen [mailto:[e-mail]]
Sent: Thursday, February 8, 2018 11:22 PM
To: Praveen Balasubramanian <[e-mail]>; Mike Bishop <[e-mail]>; [e-mail]; huitema <[e-mail]>
Subject: RE: Packet number encryption

You can’t safely reuse the combination of nonce and key, IIUC.  Since key rollover is infrequent, the nonce has to change every packet and be guaranteed unique over the lifetime of, if not the connection, at least the current key.
For CTR mode encryption which AES-GCM is, it is extremely bad to reuse the nonce. But it is still permitted if nonce only repeats with very low probability, like 2^-32 or so, don’t recall. This means that using a crypto hashed packet numbers as a nonce is an option, but a homegrown obfuscation is not.

As to hashing the packet number instead of encrypting, there is hardly any worthwhile hash that is faster than using AES, but precomputing the AES over several blocks as Mike and I have suggested earlier, is an option unless you expect large losses where a small lookup table is insufficient on average.

I share the concern on relying on the a peers weak PRNG for packet jumps etc. especially  if it is not the same as the crypto PRNG because if that is broken, it doesn’t matter anyway.

As the the 1% number - it is the only real life data we have, but I already argued that the overhead can much higher in low-latency operations with short packets. It has also been argued that packet number is lower than AEAD because it is shorter, but encrypting 64 bytes AEAD for a message is the same as encrypting 16 bytes packet number because of instruction level parallelism on current Intel hardware. You can see how the performance increases with data length in appendix A

https://software.intel.com/sites/default/files/m/d/4/1/d/8/10TB24_Breakthrough_AES_Performance_with_Intel_AES_New_Instructions.final.secure.pdf<https://na01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fsoftware.intel.com%2Fsites%2Fdefault%2Ffiles%2Fm%2Fd%2F4%2F1%2Fd%2F8%2F10TB24_Breakthrough_AES_Performance_with_Intel_AES_New_Instructions.final.secure.pdf&data=04%7C01%7Cpravb%40microsoft.com%7C20e615aa80de43354ae108d56f8dd2c9%7Cee3303d7fb734b0c8589bcd847f1c277%7C1%7C1%7C636537577282331419%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwifQ%3D%3D%7C-1&sdata=2Sh%2BzP6WC7fBGrKwUHUh4CEJTe2hWk3bR8ZAN%2BQcD1c%3D&reserved=0>

Mikkel

On 9 February 2018 at 07.19.32, Mike Bishop ([e-mail]<mailto:[e-mail]>) wrote:
You can’t safely reuse the combination of nonce and key, IIUC.  Since key rollover is infrequent, the nonce has to change every packet and be guaranteed unique over the lifetime of, if not the connection, at least the current key.  Since packet numbers also don’t repeat over the lifetime of the connection, I think using one as the variable part of the other was just taking advantage of the alignment.

I don’t think having a randomized starting value and incrementing is necessarily any better than exposing the packet number.  Having a PRNG seed established during the handshake and making the visible thing the next random output seems potentially interesting, but I’d want our more crypto-minded friends to comment.  I think the real issue would be guarantees about never-repeating from the PRNG, particularly as you don’t have guarantees about your peer’s implementation.  A defined key derivation and a counter can be verified in the protocol, independent of how good the peer’s PRNG is.

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

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.

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]<mailto:[e-mail]>>; [e-mail]<mailto:[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]] On Behalf Of Christian Huitema
Sent: Thursday, February 8, 2018 3:54 PM
To: [e-mail]<mailto:[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