User:Gmaxwell/sequence numbering

From XiphWiki
Revision as of 08:57, 18 August 2008 by Gmaxwell (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

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

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.