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

[Kazuho Oku <[e-mail]>]

2018-02-07 18:10 GMT+09:00 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.

The pros of using a sequence that randomly distributes 0 and ones
(i.e. PI or xorshift+) is that you can extract good loss / reordering
information if the error rate is low.

OTOH, it is fragile to high error rate or certain patterns of error.
Let me explain two examples.

Consider the case where the packet loss rate is 50%. I doubt if you
could use pattern matching against those sequences to figure out the
loss rate. This is because the power among the sequence is mostly high
frequencies. If you use a sequence that distributes power among lower
frequencies (like square wave or sin wave that I discussed), you can
calculate the loss rate in such cases as well.

Consider another case where the sender uses multiple queues to emit
packets belonging to a single QUIC connection (BTW, I plan to
implement such one). You would see non-neglible amount of reorders. On
the wire, it will look like if two adjacent packets packets were
swapped; it wouldn't have any practical impact on performance. But
such frequent reordering will destroy the observability of a random
sequence.

To summarize, I think that we need a low frequency signal. It could
either be a square wave or sin wave. Using a sin wave might be better
here, since you the bit pattern (which flips a lot) to observe at a
higher precision when the the error rates of loss and reorder are both
low.

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



-- 
Kazuho Oku