Subject: [Ietf-krb-wg] AEAD, new look?

From: Nico Williams <[email-masked]>
Date: Thu, 16 Jun 2011 15:57:15 -0500

So, the problem with using AES in any AEAD mode, last time we
considered it, was that it was too difficult to ensure that IVs never
get reused, with IV reuse being pretty fatal.  That was *my* take back
then anyways.

I'm thinking we (I) should reconsider.

We could use a 29-bit seconds count, a 20-bit microseconds count, and
a 15-bit CPU ID[*] to form an IV, and as long as clocks don't go
backward it'd be OK.  The exact IV construction might add more hi-res
timer bits over time as compute throughput goes up, say.

It's the clock going backwards that's the big deal for me.  I think we
could expect OS vendors to manage that though.  One way to do it would
be to disable the use of AEAD modes for KDC and AP exchanges (but not
for KRB-SAFE/PRIV and GSS per-message tokens) until the clock catches
up.  This would mostly require getting some hooks into NTP daemons.

Assuming that clocks don't go backwards then the likelihood of IV
reuse would be so low that I'd not care.  A hi-res timer could be used
that never outputs the same time twice, even if accessed multiple
times within the least significant time unit[**].

[*] This is OK as long as long-term keys change more frequently than
once every 17 years, which seems pretty reasonable.  Besides,
attackers will not keep 17 years' worth of ciphertext for any one
target key on the off chance that they might find a duplicate IV!  I'd
be uncomfortable with fewer than 29 bits, but I do think more than 29
bits could be a bit of a waste if we have other things we could add to
the IV to make it less likely to repeat.

[**] Hi-res clocks can be core or even hardware-thread specific, and
so might not be strictly increasing across all threads on a system.
For example, to build a high-performance hi-res timer that never
outputs the same time twice even when called within the same
microsecond would require that there be no synchronized global state,
and then a hardware thread ID suddenly matters  Where this is not true
these 15 bits could be seeded from a process ID, or randomly.

Nico
--
_______________________________________________
ietf-krb-wg mailing list
[email-masked]
https://lists.anl.gov/mailman/listinfo/ietf-krb-wg

---

From: Simo Sorce <[email-masked]>
Date: Thu, 16 Jun 2011 17:14:41 -0400

> up.  This would mostly require getting some hooks into NTP daemons.

If you want to use a "clock" you should use a monotonic clock from the
kernel, and not the current time or anything that can go forward and
backward when a user runs the 'date' command.

Simo.

-- 
Simo Sorce * Red Hat, Inc * New York

---

From: Nico Williams <[email-masked]>
Date: Thu, 16 Jun 2011 16:37:26 -0500

> backward when a user runs the 'date' command.

True, but there's still the possibility of the hardware clock being
set back at the BIOS.  Or the battery that keeps it going dying.  This
can be detected by storing a last known good timestamp on disk and
barfing if the clock ever appears to have backwards at boot time.
You'd also have to preserve the offset from the monotonic clock across
reboots.

There's a lot of little issues to address, but I'm thinking we can get
the risk of IV reuse to be acceptably low.  And that we can mitigate
for this risk by, for example, changing keys immediately when clock
regressions are detected, or blocking Kerberos operations until the
clock catches up, or by using Diffie-Hellman keys instead of symmetric
keys for services, and so on.

In the case of ticket encryption keys, the IV would have some bits
derived from a KDC ID.

Nico

---

From: Simo Sorce <[email-masked]>
Date: Thu, 16 Jun 2011 17:57:09 -0400

> In the case of ticket encryption keys, the IV would have some bits

What I am wondering is: if you are willing to use something as
predictable as a clock, why don't you just use a number stored on disk
and keep incrementing it ?

Simo.

---

From: Greg Hudson <[email-masked]>
Date: Thu, 16 Jun 2011 18:21:51 -0400

> timer bits over time as compute throughput goes up, say.

As a cross-platform implementor, I would not be enthusiastic about
trying to ensure that my platform has a clock which will increment
between each encryption operation performed on that kernel (even if
performed by different processes running on different cores) and never
go backward, as well as a CPU ID which is guaranteed to be unique across
all kernels running processes using the key (even if hosted within the
same hypervisor).

---

From: Nico Williams <[email-masked]>
Date: Thu, 16 Jun 2011 17:26:27 -0500

> and keep incrementing it ?

Because you'd have to have ACID semantics (which would be slow or
would require flash), and because you'd have to worry about restoring
from backup.  I guess the latter is comparable to the
clock-going-backwards problem, and this could be addressed by having
enough date bits to make such a restore unlikely.  The speed issue
could probably be overcome by doing an ACID update only every N
increments, and you always add N at boot time, that way you only pay
the slow update penalty once every N krb5 framework encryption
operations.

Hmmm!

So, 10 bits for counting time in week increments, an m-bit counter, an
n-bit KDC and/or hardware thread ID, and an o-bit random number.
Assuming 2^20 operations/s for any given protocol key (that's a very
large rate for protocol keys), you could update the on-disk counter
once a second (once per-million operations) (and you could do it
asynchronously), have m = 49, n = 15, o = 54.

Works for me!

Nico

---

From: Nico Williams <[email-masked]>
Date: Thu, 16 Jun 2011 17:32:24 -0500

> all kernels running processes using the key (even if hosted within the

We only have to agree on an IV layout locally to the sender, not to
the receiver, and on a per-protocol key usage way.

For homogeneous KDCs this means that the layout of the IV for ticket
and KDC-REP enc-part encryption can be completely implementation
specific.

For clients and services it gets a bit tricky because we can expect
them to be locally heterogeneous, so either we need a common IV layout
here or enough bits with which to distinguish layouts.  We could have
a handful of standard layouts and two or three bits (or a variable
length) for distinguishing between them.

I think this is surmountable.

Nico

---

From: Thomas Maslen <[email-masked]>
Date: Thu, 16 Jun 2011 22:41:35 +0000

Greg Hudson wrote:
> [...]

As a cross-platform Java implementor, I'm even less enthusiastic about
this degree of specificity.

In essence, if the bits that I can get from java.security.SecureRandom
aren't good enough to use as an IV for this (relying on the JVM + OS to
do some sort of decent seeding for SecureRandom) then I'm probably
not a fan of this.

(If it makes a difference, I'm not in the business of implementing KDCs,
just Kerberos clients and Kerberos services).
_______________________________________________
ietf-krb-wg mailing list
[email-masked]
https://lists.anl.gov/mailman/listinfo/ietf-krb-wg

---

From: Simon Josefsson <[email-masked]>
Date: Fri, 17 Jun 2011 08:01:01 +0200

> all kernels running processes using the key (even if hosted within the

Same here.

However, I don't see why we can't just demand that the nonce is
generated by a quality (P)RNG?  If the nonce is sufficient long, and the
(P)RNG is good, it rarely repeats in practice.  Is the worry that the
probability of repeat, even if it is very small, is non-negligible?

/Simon

---

From: Greg Hudson <[email-masked]>
Date: Fri, 17 Jun 2011 08:21:46 -0400

> probability of repeat, even if it is very small, is non-negligible?

It's not as negligible as one would like.

AEAD modes (CCM and GCM) are based on counter mode, which means you need
to fit the nonce, a block counter, and any control bits into a cipher
block (128 bits).  My original proposal for a CCM enctype used a 96-bit
nonce, a 24-bit block counter, and eight bits were swallowed by CCM
overhead.  This was uncomfortable on two fronts; it imposed a message
size limit of 256MB (current enctypes have no limit), plus you expect to
see a nonce collision after observing 2^48 messages, which isn't a
terribly impressive margin of security.  GCM loses less of the block
size to overhead (only one bit, I think) but has more drastic
consequences for nonce collisions.

It's possible to effectively extend the nonce by factoring some of the
nonce bits into key derivation instead of the counter block, but that
basically kills your performance for encrypting many messages with the
same key.  It's similarly possible to extend the maximum message size
through chaining, but that introduces problems with IOV-style encryption
APIs.  After a lot of agonizing, I retreated to CTS-CMAC, which fits
with RFC 3961's constraints much better and still eliminates the
reliance on a hash (except for string-to-key).  CTS remains kind of icky
to implement, of course, but it's a familiar pain.

Nico is proposing a way to guarantee nonce uniqueness without having to
use a big enough nonce to eliminate the birthday attack concern.  But I
think any attempt to do that is inevitably going to be too fragile, and
would wind up increasing the systemic risk of nonce collisions due to
failures of the underlying assumptions.

Counter-mode encryption fits best with protocols where the block cipher
keys are strictly ephemeral.  We have keys like that in Kerberos, of
course, but RFC 3961 and its implementations don't typically distinguish
between ephemeral and long-lived keys.

---

From: Simon Josefsson <[email-masked]>
Date: Fri, 17 Jun 2011 14:40:03 +0200

> consequences for nonce collisions.

Thanks for summarizing.  To me this sounds like information that should
be fed back to AEAD cipher mode designers, if they aren't already aware
that this is a practical problem that prevents adoption of AEAD modes.

> to implement, of course, but it's a familiar pain.

Agreed.  As long as CTS continues to be an recognized and approved
construct, that will be fine.  But in the long term, I suspect people
will want to move away from it.

> failures of the underlying assumptions.

I agree.  I believe it is both too fragile and too difficult to
implement in a portable way.

/Simon

---

From: Nico Williams <[email-masked]>
Date: Fri, 17 Jun 2011 10:28:41 -0500

Thanks Greg.  You've reminded me of other reasons I used to be against
AEAD mode ciphers in Kerberos.

Never mind,

Nico

---

From: Luke Howard <[email-masked]>
Date: Fri, 17 Jun 2011 15:45:21 +0000

> between ephemeral and long-lived keys.

We could update RFC 3961 to do so. This is deployable (usefully) with enctype negotiation.

-- Luke

---

From: Sam Hartman <[email-masked]>
Date: Mon, 20 Jun 2011 10:55:51 -0400

I think getting AEAD modes working  is not too difficult.
I don't think there are AEAD modes we can get working with NIST
specifications, which seemed to be a deal breaker for some.
_______________________________________________
ietf-krb-wg mailing list
[email-masked]
https://lists.anl.gov/mailman/listinfo/ietf-krb-wg