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

[Martin Thomson <[e-mail]>]

I looked into these when I first considered packet number encryption.
They are not typically bijective on 2^N-1.  That's not a great outcome
here.  Also, random access is a requirement and that isn't
straightforward here, even with the good ones.  Also reversing is
possible, but more complicated.

On Wed, Feb 7, 2018 at 8:10 PM, Mikkel Fahnøe Jørgensen
<[e-mail]> wrote:
> 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