Re: Rekey with CTR mode

"Jakob" <jakobsson.ulf@xxxxxxxxx> wrote in message

Having read the rest of the conversation I understand Kristian's
frustration, so I'm just going to give you a solution.

Each connection requires a shared root key, rK
Each unit needs access to a shared unidirectional counter (more on this
later), i

The encryption key for the timeframe is AES(rK, i)
The MAC key for the timeframe is AES(rK, f(i)) (more on f() later)

There, that should solve all your problems, assuming the value of i never
repeats, and f() has certain behaviors this is at least as secure as AES,
and only requires the secure storage of a single value (rK).

For the unidirectional counter, it doesn't really matter what source it is,
in fact a widely shared source of the current time will work nicely.

For f() choose an f() such that f(j)!= k for all j and k in the expected i.
So for example if you have a shared counter, make it increment by 2 instead
of 1, then f(i) = i+1, and there will never be any collisions.

As for the size of i, which seems to be a concern for you, you simply need
for it to never repeat. So you said 1Million messages, your counter needs to
be 24-bits, this will give you several times the room you need, even your
20-bits is enough if you include an implied bit, for encryption the implied
bit is 0, for the MAC the implied bit is 1. But you need to be VERY careful
not to violate the non-repetition of i, if i repeats, f(i) repeats, or
j=f(k) your security disappears very quickly.