Subject: [kitten] SPAKE and non-deterministic RFC 3961 checksums

From: Greg Hudson <[email-masked]>
Date: Sun, 17 Sep 2017 01:24:51 -0400

RFC 3961 says about the checksum profile get_mic operation: "This
function is not required to return the same deterministic result for
each use; it need only generate a token that the verify_mic routine can
check."  In practice, only the oldest checksum types (used with
single-DES keys) are non-deterministic.

The SPAKE preauth transcript checksum is computed independently by the
client and KDC using the RFC 3961 checksum operation (iterated several
times).  In hindsight, this design obviously requires a deterministic
checksum operation, so the pieces don't currently fit.  I unfortunately
only realized this mismatch today when I started doing integration tests
using DES keys in a prototype implementation.

The potential remedies I can think of fall into these bins:

1. Don't change the SPAKE design.  Instead, update RFC 3961 to specify
that new checksum types must be deterministic, and specify that SPAKE
preauth can't be used with single-DES keys.  Aside from the
standards-space cost of pushing our problem down into a lower layer, the
prohibition against using SPAKE with single-DES keys could make it
harder for clients to be configured to refuse encrypted timestamp
preauth on a pre-realm basis.  That is perhaps not a large cost as
Kerberos implementations are moving away from single-DES support anyway.

2. A relatively quick fix: use PRF instead of checksum.  (Or PRF+, in
which case we have to decide how much length of output we want.)  I
think PRF has the requisite properties, but I would want to think on it
more.

3. We could use a hash (it doesn't need to be keyed) independent of RFC
3961.  The hash algorithm could be specified in the group profile,
perhaps, but I believe the rejected-optimistic-challenge case poses a
difficulty for that design.

4. The most open-ended option is to back up and reconsider the purpose
of the transcript checksum, which is to bind at least the public keys
into key derivation.  The current transcript also binds in group
negotiation and the initial factor challenge.  I can't immediately think
of an alternative design which doesn't require the KDC to store a lot of
information in the cookie.

---

From: Benjamin Kaduk <[email-masked]>
Date: Mon, 18 Sep 2017 20:59:38 -0500

> think PRF has the requisite properties, but I would want to think on it

This is probably the most appealing option, provided we can accurately
state which properties we need (and they are provided by PRF(+)).

> difficulty for that design.

The hash algorithm could also be negotiated independently (so that in
practice, e.g., sha256 is always used, at least in the initial deployments).
For the rejected-optimistic case there is still an issue, but if the KDC
only supports O(2) hash algorithms during a hash transition, then the
amount of state needed in the cookie is bounded by a number that might
be smaller than the number of supported groups (but then again, might
not).

> information in the cookie.

I agree that we are likely to end up with something resembling a
"transcript hash", even if it does not directly use a hash primitve.

-Ben

---

From: Simo Sorce <[email-masked]>
Date: Wed, 20 Sep 2017 11:09:29 -0400

> state which properties we need (and they are provided by PRF(+)).

Why is this more appealing than just saying no to DES ?
Do we have any concern we may get future enc types that have non-
deterministic checksums ?

> be smaller than the number of supported groups (but then again, might

The nice thing about using the enctypes is that as new ones will come
out with new, stronger checksums, we'll get those automatically,
without adding a new thing to negotiate ...

> "transcript hash", even if it does not directly use a hash primitve.

I have to say that between PRF and a separate Hash I would rather use a
separate hash.

Simo.

-- 
Simo Sorce
Sr. Principal Software Engineer
Red Hat, Inc

---

From: "Henry B (Hank) Hotz, CISSP" <[email-masked]>
Date: Wed, 20 Sep 2017 18:14:31 -0700

Seems like a lesser of evils question. I don’t like backing up at this late stage, so I favor 1,2 over 3,4. No strong preference between 1 and 2, just don’t want to let single-DES drive the future. If we’re sure we’ll never want non-deterministic checksums, then go with 1.

> On Sep 16, 2017, at 10:24 PM, Greg Hudson <[email-masked]> wrote:
> 
> _______________________________________________
> Kitten mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/kitten

Personal email.  [email-masked]

---

From: Benjamin Kaduk <[email-masked]>
Date: Sat, 23 Sep 2017 14:05:27 -0500

> deterministic checksums ?

There's two aspects that push me this way: first, from a standards process
point of view, now we have to also Update a core protocol spec and hope
that people remember to check our new document whenver they try to make
a new enctype/checksum type.  While it's unlikely that a hyptoehtical
future document would actually get through the full process with such an
error, it does add to the burden on future work in this space.  The second
concern relates to implementations, in that there will need to be some sort
of logic to handle the interaction of single-DES and SPAKE preauth.  If
we were in a place where implementations were actively removing the code
for single-DES support, I would not see this as an issue, but my understanding
is that we're still several years (at least!) away from completely removing
the code (as opposed to just not using it by default).  Even though we
know that no one ought to be using the two things together, our code still
has to come up with something to do in that case, and if we get the logic
wrong things could break badly.

> without adding a new thing to negotiate ...

That is a good point, about the required checksum being matched in
perceived strength, and that holding as an invariant in the future.

> I have to say that between PRF and a separate Hash I would rather use a

Hmm, so no we have a split on 2 vs. 3, unless we can somehow make 1 more
appetizing.  Do we have the collective will to make single-DES actually
go away entirely and force any continued users to either run custom solutions
or stay on old software?

-Ben

---

From: Simo Sorce <[email-masked]>
Date: Mon, 25 Sep 2017 13:03:11 -0400

On Sat, 2017-09-23 at 14:05 -0500, Benjamin Kaduk wrote:
> > > > Kerberos implementations are moving away from single-DES
> > > > support
> > > > anyway.
> > > > 
> > > > 2. A relatively quick fix: use PRF instead of checksum.  (Or
> > > > PRF+,
> > > > in
> > > > think PRF has the requisite properties, but I would want to
> > > > think
> > > > on it
> > > > more.
> > > 

Why not simply state in the spake document that single-DES MUST NOT be
supported ?

> > > > 3. We could use a hash (it doesn't need to be keyed)
> > > > independent of
> > > > RFC
> > > > perhaps, but I believe the rejected-optimistic-challenge case
> > > > poses
> > > > a
> > > For the rejected-optimistic case there is still an issue, but if
> > > the
> > > KDC
> > > > of the transcript checksum, which is to bind at least the
> > > > public
> > > > keys
> > > > negotiation and the initial factor challenge.  I can't
> > > > immediately
> > > > think
> > > > of an alternative design which doesn't require the KDC to store
> > > > a
> > > > lot of

I say that if you are on old software you have bigger problems to deal
with than not being able to use SPAKE, and having SPAKE actively
disallow a knowingly broken enctype is not a bad thing at all. It gives
you one more lever to get off of DES.

Simo.

---

From: Benjamin Kaduk <[email-masked]>
Date: Mon, 25 Sep 2017 21:25:51 -0500

> Why not simply state in the spake document that single-DES MUST NOT be

The potential reason to not do that that I have in mind is roughly that
"it makes things easy for us now but could make things harder for
us/others further down the line".  But perhaps it is not actually that
hard, given that DES will be used less and less.

> you one more lever to get off of DES.

Another lever to get of DES is, on the face of it, good.  On the other
hand, we just removed the text preventing SPAKE from using a knowingly
broken hash algorithm (MD5), which is not quite the same situation
but bears some similarities.  And over in the TLS WG trying to use
TLS 1.3 as a lever to force adoption of RSA-PSS signatures is not
going terribly well, so I don't know how much weight to give to the
argument of having another lever to get rid of ${bad-thing}.

That said, Greg noted on IRC that if we do have a "no DES and SPAKE
together" requirement, the KDC knows the initial reply key and can
do the right thing fairly easiliy, including rejecting optimistic
attempts from (broken) clients.  So, I'm starting to come around to
the camp of "prevent SPAKE with 1DES, and require all future mandatory
checksum types to be deterministic".  (Possibly all future checksum
types entirely, but that may be too aggressive.)

-Ben

---

From: "Henry B (Hank) Hotz, CISSP" <[email-masked]>
Date: Mon, 25 Sep 2017 22:04:15 -0700

> On Sep 25, 2017, at 7:25 PM, Benjamin Kaduk <[email-masked]> wrote:
> 

Do we really have that many single-des deployments to worry about anymore? Everything I know of, including AFS and AD/Windows, has better alternatives available and just waiting to be turned on. Surely nobody is still using JGSS in Java 1.4.

---

From: Robbie Harwood <[email-masked]>
Date: Tue, 26 Sep 2017 11:25:28 -0400

"Henry B (Hank) Hotz, CISSP" <[email-masked]> writes:

> Do we really have that many single-des deployments to worry about
> anymore? Everything I know of, including AFS and AD/Windows, has
> better alternatives available and just waiting to be turned on. Surely
> nobody is still using JGSS in Java 1.4.

I don't think we can really know until we start pulling support for it,
rather than just having it off by default.  Our model makes it easy to
deploy a KDC in a "compatibility" mode (which I suspect a lot of sites
do) and then worry less about what clients are running around.

Thanks,
--Robbie

---

From: Benjamin Kaduk <[email-masked]>
Date: Wed, 27 Sep 2017 21:21:28 -0500

> Do we really have that many single-des deployments to worry about anymore? Everything I know of, including AFS and AD/Windows, has better alternatives available and just waiting to be turned on. Su…

As I understand it, there is not much (any?) modern software that strictly
requires single-DES, but there are also many sites where the effort to
upgrade has not been expended.  Even in ATHENA.MIT.EDU, we have cross-realm
keys that are actively used (albeit not for terribly critical functionality)
that remain single-DES because of the logistical challenges involved in
getting both KDC administrators in contact and with a trusted channel.

-Ben

---

From: "Henry B (Hank) Hotz, CISSP" <[email-masked]>
Date: Sat, 30 Sep 2017 02:05:25 -0700

> On Sep 27, 2017, at 7:21 PM, Benjamin Kaduk <[email-masked]> wrote:
> 

I know that kind of thing can be much harder than it seems it should. OTOH, do you think that difficulty (as a specific example) should prevent us from stipulating "no 1des with SPAKE”?

---

From: Benjamin Kaduk <[email-masked]>
Date: Sat, 30 Sep 2017 14:02:09 -0500

> I know that kind of thing can be much harder than it seems it should. OTOH, do you think that difficulty (as a specific example) should prevent us from stipulating "no 1des with SPAKE”?

No, I don't think examples of that sort should prevent us from placing
that restriction on SPAKE usage.

-Ben