D R A F T ... D R A F T

Suggested Layout of the Pad



Table of Contents

Preamble

SDP1 uses CBC mode and thus should negotiate a strongly unique IV ("initial value") for each datagram to prevent same-plaintext packets from appearing as the same cipher-text.

The use of the context IV ("CIV") is inadequate by itself to generate a unique datagram IV ("DIV"), as that is fixed across all datagrams within the context. Hence the first block in the plaintext is also the effective IV. This is organised by creating a Pad that includes sufficient contents for the purpose of making the IV unique.

In this manner, the first block encrypted is the DIV, and it uses as IV the CIV. The result provides the next IV for the remaining payload part of the datagram.

The requirement that the DIV must be unique is easy to specify, but substantially difficult to guarantee in practical implementations. For that reason, we describe here (at least one) suggested layout that is designed to give a highly reliable unique DIV under regular field circumstances.

Implementations MAY follow layouts specified here.

An additional benefit of these layouts may be the provision of useful statistical and debugging data. Whichever layout is followed, implementations are responsible for negotiating the Pad within the context, if the receiving end needs to understand it.

Predecessors

It would appear that the construction of putting a random block before the payload part of a message, in order to meet the uniqueness requirements of an IV, has been used before. [1] In Kerberos V, it is called a "confounder". In SSH 2, SSH_MSG_IGNORE message with random data in it is prepended to the plaintext.

Overall Requirements

Pad1

Overview

The suggested Pad is constructed of the following elements.

  1. Nonce Sequence Number. This is a Compact Integer (see Appendix 3) that increments with each new packet sent in the relevent direction.

  2. Time. This is a Compact Integer of the time as modified by the time base kept by the context.

  3. Random. Remaining bytes are random and pad the Byte Array up to the length required to make the combined plaintext length a factor of the encryption algorithm's block size (16 bytes).

Nonce Sequence Number

The sequence number of the packets sent is included as a Nonce in the first packet. [2]. The sequence number is sent as a Compact Integer.

The sequence number SHOULD start from a base number that is determined from the context, and increment with each successive packet. The value zero is reserved.

It is permitted to reuse numbers by resetting the counter, although this should be limited to circumstances such as where a node is restarted. (This results from the difficulties of guaranteeing a sequence number recording over a crash.) In this case, an implementation must ensure that the Time or the Randoms ensure uniqueness.

The sequence number is not purposed for retries or for unique packet identification and is not reliable. Specifically, it is permitted for the sequence number to leave gaps, and it is permitted to reuse numbers.

Time

To assist the uniqueness over restarts, a Time is included. The Time is the number of milliseconds since a timebase as obtained from the context. It is stored in a Compact Integer.

When combined with a time base taken from the context, the resultant time may indicate the GMT/UCT when the packet was first created. The time base should be before now, so that any time so expressed is positive. Also, a rollover and/or expiry decision is reached in 49 days or so with this method.

Other ideas... The following are possible:

  1. a millisecond difference from the timestamp in the context (generally expected to be a GMT timestamp).

  2. a UNIX seconds-since-1970 4 byte unsigned integer.

  3. WIN32 8 byte 100ns time?

  4. Java 8 byte milliseconds time?

To Be Determined...

Random Padding

The Pad is a Byte Array that is expanded out to fill out the concatenated stream to a boundary of the AES cipher block size (16 bytes).

The random padding is extended as required in order to make the Pad the right length. If the earlier elements require 8 bytes, then the random bytes will be at least 7 bytes (and one for the Pad length).

See the Security Notes for variations.

Additional Demands on the Context

In order to support this layout, an implementation may be assisted by the following additional features available from the context.

Time Base

The time base is a set number of milliseconds that applies to the beginning of the context. Each successive packet calculates its time as the number of milliseconds from this timebase.

The Time Base MAY be UTC Unix Time, but implementations should cope with alternates.

Sequence Number Base

The first sequence number in the context. This MAY be 1 and must not be zero.

Additional Uses

The additional information (sequence number, timestamp) in the Pad can be used for:

  1. client-side context re-initialisation,

  2. debugging and traces, and

  3. statistical tracking of losses of packets,

  4. timings statistics.

A client implementation MAY monitor the information and initiate that an out-of-bad context switch when any high water marks are exceeded.

A receiving node MAY retain the information from the last packet received for the purposes of monitoring packet losses, round trip times, etc. As packets are unordered, there will be no reliability to the measurements, reliable protocols must be implemented over the top of SDP1.

The Security of the DIV

In construction of the DIV, these are used:

  1. Sequence Count. Include a count of datagrams as a nonce in first block. This guarantees uniqueness as long as the count can be kept, but this becomes a difficult problem if a restart of the processes occurs. Further, it is predictable by an attacker. Including the count has the advantage that the receiver can generate statistics and warnings on any dropped packets (but this is unreliable, and not to be used for protocol considerations).

  2. Time. A time stamp is guaranteed to be unique as long as the time does not get reset, and as long as no more than one packet per unit time is sent. By itself, time as a nonce is unreliable, and is predictable by an attacker.

  3. Random data. Use a random block as first packet. Guarantees randomness and uniqueness, but also means that the protocol is strongly dependent on the source of random data. In practice, while random sources are well understood, they are often subject to misconfiguration, slowness and worse than all, unreliability.

To achieve a practically good IV, Pad1 is constructed as an array of all three elements. The sequence count and the Time work together to provide a guarantee of uniqueness even in the event of restarts and losses of a secure storage of the sequence count (we do not consider the case where time itself is reset!).

The inclusion of some random data helps to make the IV unguessable. But the inclusion of the unique count/Time also means that the protocol is not dependent on the quality of that randomness; implementations should use what quality they have available and not hold back when faced with a poor quality source of entropy.

In essence, the protocol should deliver good security if two out of three of the elements are good, and should even deliver security if only one of the elements is functioning. This makes for a strongly practical protocol in face of administration, engineering and configuration difficulties.

Pad2

TBD...

References

[1] Nicolas Williams, posts to Cryptography list, 25-27 April 2007.

[2] Phil Rogaway's comments on Nonces.




Copyright © 2004-2006 Systemics Inc. All rights reserved