User:Gmaxwell/sequence numbering: Difference between revisions

From XiphWiki
Jump to navigation Jump to search
No edit summary
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.

Revision as of 08:55, 18 August 2008

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