[Cryptography] updating a counter

[Sandy Harris]

There are quite a few applications for block ciphers in counter mode,
but for large block sizes it looks as though a simple counter is not
ideal. Can we discuss better ways?

With a straight counter only  a few bits change on most iterations and
the high bits almost never, even if the counter is initialised
randomly. If you start from zero, rest the counter when rekeying, and
rekey at some sensible interval like 2^32 iterations, 96 bits of a
128-bit counter or 224 bits of a 256-bit one will never change. This
may not break things, but it cannot be a good idea to use a series of
values with small Hamming differences and many known bits.

Simple improvements include random initialisation, not resetting when
rekeying, and adding a constant instead of just incrementing. Are
those enough? Optimal?

There are many transformations that might be applied to a counter to
get faster changes. Rotations, byte or word swapping and bit reversals
are easy to implement and change lots of bits. Pseudo-Hadamard
transforms can be done for any size block. The Aria cipher and the W
cipher in the Whirlpool hash each have a transform that mixes 128
bits; those must be reasonably efficient since they are used in every
round. GCM authentication also includes an efficient 128-bit mixer.
Should one of those be applied to a counter? Which? Would that
complicate the analysis of counter mode?

My solution would look like this, where p[4] is four 32-bit words for
a 128-bit counter.

Keep switch() labels < 256 to accommodate limitations on some
machines. Pick five numbers  (I'd use primes just because), 251 as
largest prime < 256 and four others in interval 0 <= x <= 251, with
values roughly 50, 100, 150, 200 so they are evenly spaced.

    switch( iter_count )    {
        /*
        mix three array elements
        each element is used
        once on left, once on right
        pattern is circular
        */
        case 47:
            p[1] += p[2] ;
            break ;
        case 101:
            p[2] += p[3] ;
            break ;
        case 197:
            p[3] += p[1] ;
            break ;
        /* inject p[0] into that loop */
        case 149:
            p[1] += p[0] ;
            break ;
        /* restart loop */
        case 251:
            iter_count = -1 ;
            break ;
        default:
            break ;
    }
    /*
    p[0] is just a counter
    nothing above affects it
    */
    p[0]++ ;
    iter_count++ ;
}

This seems to have most of the desired properties. It should be cheap
but it changes a fairly large number of bits fairly often, and it
keeps p[0] as a pure counter so existing analysis should mostly still
apply. What do others think?

There are many other ways to deal with this. Can anyone suggest a better one?