6.2.1. OFB and CTR Sequences

One way to produce a strong sequence is to take a seed value and hash the quantities produced by concatenating the seed with successive integers, or the like, and then to mask the values obtained so as to limit the amount of generator state available to the adversary.

It may also be possible to use an "encryption" algorithm with a random key and seed value to encrypt successive integers, as in counter (CTR) mode encryption. Alternatively, one can feedback all of the output value from encryption into the value to be encrypted for the next iteration. This is a particular example of output feedback mode (OFB) [MODES].

An example is shown below in which shifting and masking are used to combine part of the output feedback with part of the old input. This type of partial feedback should be avoided for reasons described below.

        +---------------+
        |       V       |
        |  |     n      |--+
        +--+------------+  |
              |            |     +---------+
         shift|            +---> |         |      +-----+
           +--+                  | Encrypt | <--- | Key |
           |           +-------- |         |      +-----+
           |           |         +---------+
           V           V
        +------------+--+
        |      V     |  |
        |       n+1     |
        +---------------+

Note that if a shift of one is used, this is the same as the shift register technique described in Section 6.1.3, but with the all-important difference that the feedback is determined by a complex non-linear function of all bits rather than by a simple linear or polynomial combination of output from a few bit position taps.

Donald W. Davies showed that this sort of shifted partial output feedback significantly weakens an algorithm, compared to feeding all the output bits back as input. In particular, for DES, repeatedly encrypting a full 64-bit quantity will give an expected repeat in about 2^63 iterations. Feeding back anything less than 64 (and more than 0) bits will give an expected repeat in between 2^31 and 2^32 iterations!

To predict values of a sequence from others when the sequence was generated by these techniques is equivalent to breaking the cryptosystem or to inverting the "non-invertible" hashing with only the resources of the adversary. As a practical matter, if a strong algorithm is in use, this should not be feasible.