Incorrect packet number encoding

[djelinski]

Originally filed under netty/netty-incubator-codec-quic#827

The encoding used by a packet number is sometimes too short to ensure correct decoding.

On a machine talking http3 to a Quiche implementation we observed long sequences of packets dropped because of tag mismatch. Example situation:

• the largest processed (and ACKed) PN observed on the client side is 0x11eaa
• the server sends a packet with 1-byte packet number 2e
• the packet number is decoded to 0x11e2e
• packet decoding fails, because the packet number was supposed to be 0x11f2e

The situation repeats for each packet number until the packet number reaches a8 (0x11ea8), after which the server starts sending 2-byte packet numbers and the transfer continues.

RFC 9000 dictates that the sender should start using 2-byte packet number encoding as soon as the packet number is more than 127 numbers away from the last number acked by peer.

The problem is caused by an off-by-one error in pkt_num_len:

quiche/quiche/src/packet.rs

Lines 571 to 572 in ad489e3

	// computes ceil of num_unacked.log2()
	let min_bits = u64::BITS - num_unacked.leading_zeros();

Compare https://www.rfc-editor.org/rfc/rfc9000.html#name-sample-packet-number-encodi

min_bits = log(num_unacked, 2) + 1

(the RFC could have been more clear about the rounding mode of log)

To confirm the problem, use the following piece of code:

		// roundtrip
		let base = 0xdeadbeef;
		for i in 1..255 {
			let pn = base + i;
			let num_len = pkt_num_len(pn, base);
			if num_len == 1 {
				let decoded = decode_pkt_num(base, pn & 0xff, num_len);
    			assert_eq!(decoded, pn);
			} else {
				assert_eq!(num_len, 2);
				let decoded = decode_pkt_num(base, pn & 0xffff, num_len);
    			assert_eq!(decoded, pn);
			}
		}

With the current implementation of pkt_num_len, the above test fails.