[Cryptography] Derive IV from time in ticks.

[Nico Williams]

On Mon, Feb 06, 2023 at 01:56:32PM -0500, Phillip Hallam-Baker wrote:
> On Fri, Feb 3, 2023 at 6:36 PM Nico Williams <nico at cryptonector.com> wrote:
> > On Thu, Feb 02, 2023 at 12:01:38PM -0500, Phillip Hallam-Baker wrote:
> > > On Wed, Feb 1, 2023 at 2:30 AM Nico Williams <nico at cryptonector.com>
> > wrote:
> > > What is your issue with OCB? I am trying to think of something that
> > > wouldn't have an issue...
> >
> > OCB fails pretty catastrophically with key&nonce reuse.
> 
> Do you have a link for that? The whole point of OCB was not to fail
> catastrophically like GCM does.

RFC 7253, section 5.1, Nonce Requirements:

   It is crucial that, as one encrypts, one does not repeat a nonce.
   The inadvertent reuse of the same nonce by two invocations of the OCB
   encryption operation, with the same key, but with distinct plaintext
   values, undermines the confidentiality of the plaintexts protected in
   those two invocations and undermines all of the authenticity and
   integrity protection provided by that key.  For this reason, OCB
   should only be used whenever nonce uniqueness can be provided with
   certainty.  Note that it is acceptable to input the same nonce value
   multiple times to the decryption operation.  We emphasize that the
   security consequences are quite serious if an attacker observes two
   ciphertexts that were created using the same nonce and key values,
   unless the plaintext and associated data values in both invocations
   of the encrypt operation were identical.  First, a loss of
   confidentiality ensues because the attacker will be able to infer
   relationships between the two plaintext values.  Second, a loss of
   authenticity ensues because the attacker will be able to recover
   secret information used to provide authenticity, making subsequent
   forgeries trivial.  Note that there are AEAD schemes, particularly
   the Synthetic Initialization Vector (SIV) [RFC5297], appropriate for
   environments where nonces are unavailable or unreliable.  OCB is not
   such a scheme.

I would term that 'catastrophic'.  Though given no quantifiers (I can't
find any in the literature) about the badness of key&nonce reuse for
OCB3, it's hard to say how catastrophic.  What is the work factor to
forge a message, recover plaintext, and/or recover the key given N
key&nonce reuses?  It'd be nice to know.

> Reuse the IV in GCM and you have a stream cipher so it is schoolboy level
> cryptanalysis. The tweakable cipher structure is supposed to make that
> hard. Did Phil Rogaway really blow it?

Well, no, since he's one of the authors of the above text.

The compromise of plaintext confidentiality in GCM is pretty obvious
given that it's a stream cipher constructed from a counter mode.  What
happens to security when key&nonce are reused in OCB3 is less clear.

> GCM-SIV is not an option for me because I have to be able to encrypt very
> large quantities of data, routinely in the 'no ordinary machine has this
> much RAM'. range.

Yup, SIV is much slower than OCB.

> > session keys == ...
> >
> > long-term keys == [...]
> 
> My problem with that distinction is that any primary key that gets applied
> to more than one envelope is going to start looking like a long term key.

If a key is used strictly and only in the context of a single process[0]
that can maintain a monotonic, non-repeating counter / clock, including
enforcement of maximum encryption limits, then it's a session key[1].
Otherwise it's not.

It's a stark distinction.

Are all the keys in your system that you mean to use with OCB used
strictly in such a way?

[0] Or cooperating processes, or threads, but which altogether maintain
    that monotonic, non-repeating counter / clock.

[1] Such a key practically has to be the result of a key exchange --
    what else could it be?

> [...]
> 
> So for example, in my scheme, a service host starts up and starts appending
> data to a log file. It should perform a key exchange each time it starts up
                      ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Keys produced by a key exchange, which are used as I described, and
which are not used again after the ephemeral, monotonic counter/clock
state is deleted, are session keys.

> and once an hour and append that into the sequence. So if the log has a
> million entries recorded over a year, there might be only ~750 key
> exchanges.

The service that accepts the log entries is not as interesting as the
clients that send it the messages to log.  It is those that might reuse
a key&nonce (unless the log service sends back ACKs, then both the log
and the clients are interesting).  If each client negotiates it's own
session key for use in encrypting messages to the log service, then
those are session keys, not long-term keys, thus perfectly safe to use
with OCB.

> > By the sounds of it these are what in Kerberos-land we'd call
> > "long-term keys".

But now it's sounding like in at least some cases the keys we're talking
about are session keys.

> > [...]
> 
> Hence my interest in using ticks.
> 
> But the other thing with ticks is that it potentially gives a guard against
> transaction replay attacks which was my original question.

Sequence numbers, IV chaining (and equivalent for nonces in the case of
OCB), and clocks, all give you the ability to detect replays trivially.

With IV chaning (and equivalent for nonces) you also get to enforce
in-order delivery.  With sequence numbers you get the ability to receive
messages out of order, re-order them, and also you get the ability to
know if you're missing messages.

With clocks you get the ability to receive messages out of order and
re-order them, but you don't get the ability to detect if you're missing
messages because with sufficiently precise clocks you'll usually not use
every possible clock value to construct messages!  But with clocks it's
too expensive to support re-ordering of messages, so you'll only want to
reject messages older than or the same age as the last one you've
received -- OTOH this is cheaper than keeping a window of seen sequence
numbers.

Nico
--