Re: Explicit measurability in the QUIC wire image (was Re: Packet number encryption)

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

Instead of a static Pi table, an xorshift+ PRNG could be used. It would
likely be preferable to shorten the cycle such that observers can use hash
lookups and hamming distance computations against selected segments of the
sequence.

https://en.wikipedia.org/wiki/Xorshift#xorshift+

http://xoroshiro.di.unimi.it/xorshift128plus.c

uint64_t s[2];

uint64_t next(void) {
	uint64_t s1 = s[0];
	const uint64_t s0 = s[1];
	const uint64_t result = s0 + s1;
	s[0] = s0;
	s1 ^= s1 << 23; // a
	s[1] = s1 ^ s0 ^ (s1 >> 18) ^ (s0 >> 5); // b, c
	return result;
}


A simpler 32-bit version could also be used since we do not care about
long cycles.

http://excamera.com/sphinx/article-xorshift.html

uint32_t seed = 7;  // 100% random seed value

static uint32_t random()
{
  seed ^= seed << 13;
  seed ^= seed >> 17;
  seed ^= seed << 5;
  return seed;
}


The output would be the bits shifted out of the 32-bit our 64-bit word in
either MSB or LSB first. I’d prefer LSB because it is slightly simpler to
test the LSB bit and divide by 2.

On 7 February 2018 at 01.29.18, Mikkel Fahnøe Jørgensen ([e-mail])
wrote:

Also note that this approach is insensitive to skipped packet numbers in
optimistic ACK attack defence. It leaks zero information when the network
is perfect and if the CID hash is random.

------------------------------
*From:* Mikkel Fahnøe Jørgensen <[e-mail]>
*Sent:* Wednesday, February 7, 2018 12:58:33 AM
*To:* Kazuho Oku
*Cc:* Brian Trammell (IETF); QUIC WG
*Subject:* Re: Explicit measurability in the QUIC wire image (was Re:
Packet number encryption)

I actually think a static 1KB table of Pi could work quite well.

A subset of samples could be indexed in a hashtable and yield loss data
early with some probability. Some samples would miss due to reordering or
loss. If more exact analysis is wanted the levenshtein distance of a sample
sequence against Pi from a synced offset would tell a lot about the data.
Or DNA sequencing. This could be hardware optimized.

Yet, transmission is always just the next bit in the Pi table.

Since Pi is effectively random it will ebentually detect mutations if the
observed sequence is long enough.

Wrt privacy, the CID may be used as a start offset hash into the Pi table.

There isn’t any need to cover a full RTT worth of Pi bits unless it is used
for latency detection, but in that case the spin could be a pattern like
10101010 and 00001111 injected into the Pi sequence. A separate spin bit
would be simpler.


------------------------------
*From:* Kazuho Oku <[e-mail]>
*Sent:* Tuesday, February 6, 2018 5:22:35 PM
*To:* Mikkel Fahnøe Jørgensen
*Cc:* Brian Trammell (IETF); QUIC WG
*Subject:* Re: Explicit measurability in the QUIC wire image (was Re:
Packet number encryption)

2018-02-06 23:54 GMT+09:00 Mikkel Fahnøe Jørgensen <[e-mail]>:
> This idea can be taken further: You can modulate the signal so you use
> multiple packets to encode a zero or a one for half the wave duration. For
> example 1 could be encoded as 0101 over four packets and zero could be
> encoded as 0011 over four packets.
> If there is any reordering, it would show up as an unexpected value in the
> pulse.

That's definitely an option.

Actually, I considered using sin wave (that distributes the error
among 1-bit samples) as an example instead of the square wave.

The primary reason behind my preference to using a square wave is that
it is easier to implement; in fact, emitting a square wave with the
length of 512 packets is as easy as just taking the 9th bit (counting
from LSB) of the packet number (if we forget about the gaps for a
moment).


--
Kazuho Oku