[Cryptography] updating a counter

[John Denker]

On 05/19/2014 06:58 AM, Sandy Harris wrote:
> 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.

My favorite thing is to use a collection of subcounters.

Most of the subcounters are LFSRs.  Some of them shift 
left, and some of them shift right.  Between the shifting 
and the XORing, a lot of bits get changed.

Each subcounter gets updated every time.  I arrange for 
the periods to be relatively prime, so that the period 
of the collection is the product of the periods of the 
individual subcounters.

One of the subcounters can be a plain arithmetical
adder.  We agree that using a random (nonzero) addend 
flips a lot more bits than a simple increment, and 
costs nothing extra compared to a simple increment 
(i.e. addend=1).

One advantage of this approach is that you can test
each subcounter, to make sure that it is implemented
correctly.  Counting to 2^32 doesn't take too long.
You can then verify that the periods are relatively
prime.  Then you know that the collection has a very
very long period.

Last but not least, there is the issue of block cipher
(in counter mode) versus hash function (in counter mode).
The cipher has the advantage that it can be re-keyed.
Rekeying AES is remarkably fast.  There is some value
in doing that, not on every count, but maybe every 1000 
counts or so.

I consider all this to be in the category of belt plus 
suspenders plus crazy glue.  If the block cipher is 
any good, a simple increment is entirely sufficient.
To say the same thing the other way, if a simple 
increment is not sufficient, it constitutes a grave 
known-plaintext break of the cipher.  There are probably
other parts of the overall system that depend on the
cipher being not broken, so it's not worth spending
toooo much effort fussing with the counter.