Subject: [quicwg/base-drafts] Change Packet Number Gap to Packet Number Offset (#1307)

From: Nick Banks <[email-masked]>
Date: Thu, 19 Apr 2018 21:29:08 +0000 (UTC)

This is a proposed solution to the privacy/linkability problem by slightly modifying the existing packet number gap solution to make it a per connection ID packet number offset. The offset is used to transform the wire encoding of the packet number, but the connection still uses the same monotonically increasing packet number space (no gaps).

This solution requires very little per packet CPU overhead, compared to PNE.

Unlike the PNE proposal (#1079), this doesn't fix the ossification/greasing problem as well. Instead, I'd like to treat that as a separate problem (and a separate PR) and attempt to solve that with a non-cryptographic solution (shuffle for instance).

Closes:
- #1174
- #1034
- #990

You can view, comment on, or merge this pull request online at:

  https://github.com/quicwg/base-drafts/pull/1307

-- Commit Summary --

  * Packet Number Gap -> Offset

-- File Changes --

    M draft-ietf-quic-tls.md (4)
    M draft-ietf-quic-transport.md (56)

-- Patch Links --

https://github.com/quicwg/base-drafts/pull/1307.patch
https://github.com/quicwg/base-drafts/pull/1307.diff

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1307

---

From: Marten Seemann <[email-masked]>
Date: Thu, 19 Apr 2018 16:45:05 -0700

marten-seemann commented on this pull request.

> @@ -832,6 +832,27 @@ Use of a secure random number generator {{?RFC4086}} is not necessary for
 generating the initial packet number, nor is it necessary that the value be
 uniformly distributed.
 
+### New Connection ID Packet Numbers
+
+Packets with with new connection IDs have special rules for encoding the packet
+number in the headers.  They use an offset (see {{packet-number-offset}}) to
+transform the packet number via the following:

Why does this only apply to new connection IDs? Wouldn't it be easier to apply this transformation to every packet number?

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1307#pullrequestreview-113813136

---

From: Christian Huitema <[email-masked]>
Date: Thu, 19 Apr 2018 19:00:50 -0700

I think that's a terrible idea. It perpetuates the fallacy that offsetting packet numbers provides privacy. We have established that it doesn't in an important case, when there is overlap between two connections. The matching pattern of holes and sequence number increment is more that sufficient to establish correlation in these cases.

We would be much better off just getting rid of the gaps altogether. They force complex synchronization between sender and receiver, effectively the same management cost as managing encryption keys, but they do not provide nearly as much benefit as encryption.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1307#issuecomment-382941999

---

From: Nick Banks <[email-masked]>
Date: Fri, 20 Apr 2018 06:19:36 -0700

@huitema would adding the shuffle (or some other non-cryptographic greasing) alleviate your concerns here? Matching patterns between overlap would be more difficult then.

As for this design being a complex synchronization between sender and receiver, I disagree with you. Each side needs only generate the offset once, per connection ID and just store that offset. When sending, it's just an additional add and modulo operation. The sender just needs to do an add and subtraction operation.

Obviously adding whatever greasing algorithm will add additional complexity, but the CPU cost per packet should still be quite low, and easily implemented in hardware.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1307#issuecomment-383093339

---

From: Nick Banks <[email-masked]>
Date: Fri, 20 Apr 2018 13:21:12 +0000 (UTC)

nibanks commented on this pull request.

I was just following the existing model that gaps used. I don't have a strong opinion either way.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1307#discussion_r183047641

---

From: MikkelFJ <[email-masked]>
Date: Fri, 20 Apr 2018 13:51:06 +0000 (UTC)

@nibanks this looks a bit like my segmented packet numbers proposal but not that this proposal has a fixed offset per connection ID and that a connection ID is replaced before that offset is exhausted.

This avoids any linkage other than NAT rebinding.

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

You can further mutilate the clean packet number sequence with a reversible permutation

http://stackoverflow.com/a/12996028
```
   uint32_t x;

    x = ((uint32_t)(size_t)key) ^ (uint32_t)(MY_SEED);

    x = ((x >> 16) ^ x) * 0x45d9f3bUL;
    x = ((x >> 16) ^ x) * 0x45d9f3bUL;
    x = ((x >> 16) ^ x);
    return x;
```

And you can further encrypt that permuation using simple XOR magic - apparently IPSec style.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1307#issuecomment-383102463

---

From: MikkelFJ <[email-masked]>
Date: Fri, 20 Apr 2018 06:55:47 -0700

Just using a random seed might be sufficient to deter the average middle box and with CID update there is no privacy leak.
The resulting PN can be used as AEAD IV since it is a permutation of a unique non-repeating sequence. After CID update the AEAD keys must change, but then it is about time anyway.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1307#issuecomment-383103858

---

From: MikkelFJ <[email-masked]>
Date: Fri, 20 Apr 2018 07:08:28 -0700

I suppose a more elaborate encryption would go like

```
uint32_t key[4];
hkdf(key, context);

uint32_t x;

    x = ((uint32_t)(size_t)PN) ^ key[0];
    x = ((x >> 16) ^ x) * UINT32_C(0x45d9f3b) ^ key[1];
    x = ((x >> 16) ^ x) * UINT32_C(0x45d9f3b) ^ key[2] ;
    x = ((x >> 16) ^ x) * UINT32_C(0x45d9f3b) ^ key[3];
    x = ((x >> 16) ^ x);
    return x;
```
Due to brute force the encryption is not strong, but combined with per path CID and update before 2^32 PN's it should be robust since the PN encryption is not privacy.

To speed things up, one or two multiplication rounds can be taken out.

See also

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1307#issuecomment-383107718

---

From: MikkelFJ <[email-masked]>
Date: Fri, 20 Apr 2018 14:13:15 +0000 (UTC)

The above cannot be used directly as IV because the permuation is no longer a 1 to 1 mapping but a key guided mapping, so the encrypted PN will not work as an IV. The same issue should not be the case with the initial seeded value.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1307#issuecomment-383109213

---

From: Mike Bishop <[email-masked]>
Date: Fri, 20 Apr 2018 17:22:23 +0000 (UTC)

> After CID update the AEAD keys must change, but then it is about time anyway.

Given how frequently CID rotation might occur (path validation, quiescence, shifts in wind direction), I am dubious that it's wise to rotate 1-RTT keys every time a new CID is used, which I believe is what you're saying here.  This also falls prey to the same problem as #1174 -- if you switched keys because you used a new CID to probe, what key do you use back on the original path while you wait for the probe to complete?  Key rotation is supposed to be a ratchet forward, and you can't have two key rotations going on at once in the current design, so you also can't take the answer of doing a second rotation on the original path.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1307#issuecomment-383165020

---

From: Mike Bishop <[email-masked]>
Date: Fri, 20 Apr 2018 17:48:54 +0000 (UTC)

MikeBishop requested changes on this pull request.

I think @marten-seemann is correct -- this solution only makes sense as a transform on every packet, not just as something to do on particular packets with a new CID.  That's my key feedback on fixing the PR.

On the proposal itself, however, I share @huitema's concerns that correlation of gaps between flows is still possible.  A future PR for a shuffle can make that harder for an observer, but only so much (observing over the shuffle window, you can perform the same analysis).

The gap in the actual packet number was introduced at the point you sent the first packet with a new CID.  This proposal is a transformation of the actual packet number for wire presentation, so it needs to occur every time.

+~~~
+transformed_packet_number = (packet_number + offset) % 2^62

This might actually be okay, but the possibility that the transformed packet number might wrap around to zero before being truncated feels a little odd.

+### New Connection ID Packet Numbers
+
+Packets with with new connection IDs have special rules for encoding the packet
+number in the headers.  They use an offset (see {{packet-number-offset}}) to
+transform the packet number via the following:
+
+~~~
+transformed_packet_number = (packet_number + offset) % 2^62
+~~~
+
+Once transformed, the normal rules of packet number encoding are followed, only
+encoding the least number of bits required.

"only" and "the least" feels duplicative.  Maybe just replace the part with the comma with a reference to the section where the truncation is defined?

Better yet, since this is effectively a transform on every packet number, put this in the section about truncation (it becomes a description of how the 64-bit number is encoded on the wire) and make this section purely about determining what the offset will be.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1307#pullrequestreview-114065522

---

From: MikkelFJ <[email-masked]>
Date: Fri, 20 Apr 2018 11:43:53 -0700

> if you switched keys because you used a new CID to probe, what key do you use back on the original path while you wait for the probe to complete?

I forgot about my own proposal: No, rekeying is not needed for each new CID. The segmented packet number idea means that each CID is given an internal incremental high bit value. So the IV is the CID counter + the visible PN, permutated or not. Hence the AEAD can last much longer than CID's

However, for the sake of privacy, you need to do a a high bit increment for each CID, but that is also very cheap.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1307#issuecomment-383187307

---

From: Christian Huitema <[email-masked]>
Date: Fri, 20 Apr 2018 12:31:51 -0700

This design falls in the category of "obfuscation", analyzed in https://github.com/quicwg/base-drafts/wiki/Summary-of-the-PN-encryption-issues-and-alternatives#alternative-pn-encryption. It does not provide privacy, and also does not protect against ossification. You would be better off leaving the PN in clear text.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1307#issuecomment-383198839

---

From: MikkelFJ <[email-masked]>
Date: Fri, 20 Apr 2018 13:34:54 -0700

> You would be better off leaving the PN in clear text.
That was also my original intend, but it does offer privacy because it is unique per CID and there is no visible gap to be compared across CID's (modulo NAT rebinding). As to obfuscation, if seeded with an unguessable value, and filtered for the zero case, it would not be unbreakable, but neither would it be very trivial to make use of in a busy switch. So it comes down to how much you wan't to harden against ossification - if the answer is "very" then full PNE is the only way.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1307#issuecomment-383214788

---

From: Antoine Delignat-Lavaud <[email-masked]>
Date: Mon, 23 Apr 2018 12:35:14 +0000 (UTC)

@MikeBishop is right - the proposal only makes sense if it applies to all packets, so the text about this being only for new connection IDs must be removed

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1307#issuecomment-383559330

---

From: Antoine Delignat-Lavaud <[email-masked]>
Date: Mon, 23 Apr 2018 05:36:44 -0700

ad-l commented on this pull request.

I think that's a clear mistake, the transformation does apply to all packet numbers on the network

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1307#discussion_r183378081