[Cryptography] Derive IV from time in ticks.

[Nico Williams]

On Thu, Dec 29, 2022 at 03:27:41PM -0500, Phillip Hallam-Baker wrote:
> I am writing a very small scale scheme for use on a UDP based presence
> service. I am not concerned about traffic analysis at this point, I will
> add an obfustification layer later on. Same for rekeying the connection,
> just starting things off with a Kerberos like scheme.

Are the keys involved session keys or long-term keys?  You mention
rekeying, so I assume we're talking about session keys produced by a
reasonable key exchange.  If it's long-term keys then OCB is not the
droid you're looking for.

Kerberos uses "confounded" ciphertext-stealing mode (CTS), which is a
variant CBC with explicit IV, plus an HMAC.  This is perfectly fine for
long-term keys and also session keys, but it's ~3x slower than OCB.

("Counfounded" means that a block's worth of random nonce is prepended
to the plaintext prior to encryption.  This is a lot like an explicit IV
in CBC uses, but it requires one more block operation, though on the
flip side the confounder makes CTS possible even for messages shorter
than one block [because the confounder adds a block], and CTS means
there's never any padding.)

As it happens Luke Howard is working towards adding OCB and GCM to the
Kerberos GSS mechanism, but only for session keys.

It's exceedingly hard to make safe use of OCB, CCM, or GCM with
*long-term* keys.

> Messages to the service are prefixed by a token currently 8 bytes in length
> which specifies the client endpoint device. I am considering changing that
> to:
> 
> DeviceID (8 bytes)
> CurrentTime (8 bytes) [in ticks)

Wait.  This makes it sound like you're using long-term keys.

<engage-cold-sweats/>

If it's long-term keys and you _really_ must use OCB (don't!), then you
need to make sure that time is monotonic and non-repeating in all the
devices implementing this protocol.  That's so hard to ensure that I
would suggest you use a different cipher mode, either SIV or a
Kerberos-style confounded CTS/CBS w/ a MAC.

> So how about bundling those up and using them as the IV for encrypting the
> packet with OCB?

The DeviceID feels like it could be implicit if this were a stateful
protocol over TCP, but being a protocol over UDP the DeviceID has to be
explicit, which means that shoving it into the IV doesn't save you space
in the message.  The CurrentTime has to be explicit since the receipient
couldn't guess the sender's time.  So if you were meaning to save
message header space by moving these into the IV, that's not going to be
possible.  The best you could do by shoving these into the IV is to
reduce the amount of time dealing with the "additional data" part of the
AEAD cipher mode.

Assuming these were session keys...  You really want sequence numbers
and block counters, not time, unless you can guarantee that time is
monotonic and non-repeating, and even then you need a few bits to count
the blocks in each message.  This is true whether you're using OCB, CCM,
or GCM, except that GCM helpfully reserves 32 bits for the block
counter.  Key+IV reuse is catastrophic for those three cipher modes, for
slightly different values of catastrophic for each of them, so you
really have to get this right.

> So the reason I am finding including the time in this scheme attractive is
> that it provides a lightweight means of preventing replay attacks outside
> an arbitrarily narrow time window. The presence service also provides NTP
> like synchronization.

If we're talking about long-term keys, then, yes, you need time to help
prune replay caches.

Performant replay caches are hard to implement.  Performant clustered
replay caches much more so.

So if your protocol is stateless / over UDP and uses long-term keys,
then you either have to make replays harmless, add an extra round trip
to prevent replays, or put a lot of effort into a sound and performant
replay cache.

Been there, done that with Kerberos.  (Most Kerberos applications always
have the client send the first application message after the one round
trip AP exchange, so those can have replay protection w/o a replay
cache.)

If OTOH we're talking about session keys, then sequence number windows
are not hard to implement, while using timestamps instead of sequence
numbers it's hard to know if you're _missing_ messages.  FYI Kerberos'
KRB-PRIV and KRB-SAFE messages have the option to use either sequence
numbers or timestamps.  And GSS-API tried to accomodate that (even
though the Kerberos GSS mechanism uses _only_ sequence numbers), but the
result is a difficult to use API for sequencing -- worse, ONC RPC (and
therefore NFS) has to add its own sequence number because of that, thus
doubling the already non-trivial overhead of sequence numbers in
Kerberos!

FWIW, I believe Microsoft used to use Kerberos as an authenticated time
service.

> What do folk think? Good idea or not?

That hinges on whether these are long-term keys or session keys.  If
they're long-term keys, then no.

Nico
--