User:Gmaxwell/sequence numbering - Revision history

Gmaxwell at 15:57, 18 August 2008

2008-08-18T15:57:59Z

← Older revision		Revision as of 15:57, 18 August 2008
Line 16:		Line 16:
	0 1 2 3 4 5 6 0 1 7 2 3 5 4 0 1 6 2 3 7 4 0 5 1 2 6 3 4 0 7 1 2 5 3 4 6 0 7 2 1 3 5 6 4 0 2 1 7 3 6 4 5 0 2 7 1 3 6 5 0 4 2 7 3 1 5 0 6 2 4 3 1 7 0 5 2 4 6 1 3 0 5 7 2 4 1 6 0 3 5 7 4 1 2 0 3 6 7 4 5 2 0 1 3 7 6 4 2 5 0 3 1 6 4 7 5 2 3 0 1 4 6 5 7 3 2 1 4 0 6 5 3 7 1 4 2 0 5 6 3 1 4 7 0 2 6 5 1 3 4 7 2 0 6 1 5 4 3 7 2 6 0 5 4 1 3 2 7 6 0 4 5 3 1 2 7 0 6 4 3 5 2 1 0 7 4 3 6 2 1 5 7 0 3 4 2 6 1 7 5 3 0 4 6 2 7 5 1 0 4 3 2 6 7 1 0 5 3 2 4 7 6 1 0 3 2 5 4 6 7		0 1 2 3 4 5 6 0 1 7 2 3 5 4 0 1 6 2 3 7 4 0 5 1 2 6 3 4 0 7 1 2 5 3 4 6 0 7 2 1 3 5 6 4 0 2 1 7 3 6 4 5 0 2 7 1 3 6 5 0 4 2 7 3 1 5 0 6 2 4 3 1 7 0 5 2 4 6 1 3 0 5 7 2 4 1 6 0 3 5 7 4 1 2 0 3 6 7 4 5 2 0 1 3 7 6 4 2 5 0 3 1 6 4 7 5 2 3 0 1 4 6 5 7 3 2 1 4 0 6 5 3 7 1 4 2 0 5 6 3 1 4 7 0 2 6 5 1 3 4 7 2 0 6 1 5 4 3 7 2 6 0 5 4 1 3 2 7 6 0 4 5 3 1 2 7 0 6 4 3 5 2 1 0 7 4 3 6 2 1 5 7 0 3 4 2 6 1 7 5 3 0 4 6 2 7 5 1 0 4 3 2 6 7 1 0 5 3 2 4 7 6 1 0 3 2 5 4 6 7

	This sequence of three bit ~~values~~ (0-7) has the following properties:		This sequence of three bit digits (0-7) has the following properties:
	*At all offsets (including wrap) the span of three contiguous digits is globally unique.		*At all offsets (including wrap) the span of three contiguous digits is globally unique.
	*At all offsets (including wrap) no single ~~value~~ is reused within a 2^3-1 ~~value~~ window.		*At all offsets (including wrap) no single digit is reused within a 2^3-1 digit window.

	With this sequence we could maintain packet-to-packet synchronization so long as loss/reordering does not span more than 2^3-1 packets. If synchronization is lost it can be recovered totally cold with only three contiguous correctly received packets.		With this sequence we could maintain packet-to-packet synchronization so long as loss/reordering does not span more than 2^3-1 packets. If synchronization is lost it can be recovered totally cold with only three contiguous correctly received packets.

	For short sequences implementing this is trivial. For practical applications digits of 8 to 16 bits and sequence lengths in the range of 2^48 to 2^64 ~~values~~ are interesting, but space and computationally efficient implementation is an interesting challenge. Less than optimal sequences can be generated with permutation counting, but optimal is always better.		For short sequences implementing this is trivial. For practical applications digits of 8 to 16 bits and sequence lengths in the range of 2^48 to 2^64 digits are interesting, but space and computationally efficient implementation is an interesting challenge. Less than optimal sequences can be generated with permutation counting, but optimal is always better.

Gmaxwell at 15:55, 18 August 2008

2008-08-18T15:55:28Z

← Older revision		Revision as of 15:55, 18 August 2008
Line 18:		Line 18:
	This sequence of three bit values (0-7) has the following properties:		This sequence of three bit values (0-7) has the following properties:
	*At all offsets (including wrap) the span of three contiguous digits is globally unique.		*At all offsets (including wrap) the span of three contiguous digits is globally unique.
	*At all offsets (including wrap) no single value is reused within a 7-value window.		*At all offsets (including wrap) no single value is reused within a 2^3-1 value window.

	With this sequence we could maintain packet-to-packet synchronization so long as loss/reordering does not span more than 7 packets. If synchronization is lost it can be recovered totally cold with only three contiguous correctly received packets.		With this sequence we could maintain packet-to-packet synchronization so long as loss/reordering does not span more than 2^3-1 packets. If synchronization is lost it can be recovered totally cold with only three contiguous correctly received packets.

	For short sequences implementing this is trivial. For practical applications digits of 8 to 16 bits and sequence lengths in the range of 2^48 to 2^64 values are interesting, but space and computationally efficient implementation is an interesting challenge. Less than optimal sequences can be generated with permutation counting, but optimal is always better.		For short sequences implementing this is trivial. For practical applications digits of 8 to 16 bits and sequence lengths in the range of 2^48 to 2^64 values are interesting, but space and computationally efficient implementation is an interesting challenge. Less than optimal sequences can be generated with permutation counting, but optimal is always better.

Gmaxwell: User:Gmaxwell moved to User:Gmaxwell/sequence numbering: intended name

2008-08-18T15:54:37Z

User:Gmaxwell moved to User:Gmaxwell/sequence numbering: intended name

← Older revision		Revision as of 15:54, 18 August 2008
(No difference)

Gmaxwell: I've been working on this problem on and off for a long time, ... I thought I'd publically post this brief explination but it's not an exaustive list of my progress thus far.

2008-08-18T15:53:34Z

I've been working on this problem on and off for a long time, ... I thought I'd publically post this brief explination but it's not an exaustive list of my progress thus far.

New page

For real-time media streaming the streaming layer must provide sequence numbering for packets in order to cope with packet loss, reordering, or duplication.

Secure media transmission also requires a unique per-packet counter Initialization Vector to ensure the that the same keying material is not reused (reuse of IV, key is utterly fatal for stream ciphers), and is generally bad for all modes. The packet sequence number can be reused for this purpose, but (potentially expensive) re-keying must be performed before the IV wraps.

For very low latency operation larger sequence numbers can represent a substantial contributor to the overall per-packet overhead, so smaller sequence counters are preferred.

sRTP addresses this issue by using a 48 bit counter which is comprised of a 16 bit sequence number which is transmitted and a non-transmitted 32bit roll-over counter which increments whenever the 16 bit sequence number wraps. This saves overhead but it has some limitations:
*Loss over 65535 packets causes full and irrecoverable de-synchronization
*No ability to join a running transmission (think multicast) without two way communication and some extension to query the ROC.
*16 bits/packet still required.

The second point has the most practical implications. With quasi-static keying (no PFS) secure *one-way* multi/broadcast communication should be possible and would be useful.

We can do better: Consider the sequence of 230 values:

0 1 2 3 4 5 6 0 1 7 2 3 5 4 0 1 6 2 3 7 4 0 5 1 2 6 3 4 0 7 1 2 5 3 4 6 0 7 2 1 3 5 6 4 0 2 1 7 3 6 4 5 0 2 7 1 3 6 5 0 4 2 7 3 1 5 0 6 2 4 3 1 7 0 5 2 4 6 1 3 0 5 7 2 4 1 6 0 3 5 7 4 1 2 0 3 6 7 4 5 2 0 1 3 7 6 4 2 5 0 3 1 6 4 7 5 2 3 0 1 4 6 5 7 3 2 1 4 0 6 5 3 7 1 4 2 0 5 6 3 1 4 7 0 2 6 5 1 3 4 7 2 0 6 1 5 4 3 7 2 6 0 5 4 1 3 2 7 6 0 4 5 3 1 2 7 0 6 4 3 5 2 1 0 7 4 3 6 2 1 5 7 0 3 4 2 6 1 7 5 3 0 4 6 2 7 5 1 0 4 3 2 6 7 1 0 5 3 2 4 7 6 1 0 3 2 5 4 6 7

This sequence of three bit values (0-7) has the following properties:
*At all offsets (including wrap) the span of three contiguous digits is globally unique.
*At all offsets (including wrap) no single value is reused within a 7-value window.

With this sequence we could maintain packet-to-packet synchronization so long as loss/reordering does not span more than 7 packets. If synchronization is lost it can be recovered totally cold with only three contiguous correctly received packets.

For short sequences implementing this is trivial. For practical applications digits of 8 to 16 bits and sequence lengths in the range of 2^48 to 2^64 values are interesting, but space and computationally efficient implementation is an interesting challenge. Less than optimal sequences can be generated with permutation counting, but optimal is always better.