Subject: [kitten] Concerns about draft-ietf-kitten-krb-spake-preauth-04

From: Sam Hartman <[email-masked]>
Date: Thu, 25 Jan 2018 13:51:39 -0500

Hi.
I came across the SPAKE preauthentication draft because IANA asked me to
look at it.
I was late and they sent it along to Larry before I could get around to
it.

I like the general approach.  I ran into two specific issues, and only
conducted a brief review of the document.
I support having a solution to something along these lines, but I
suspect we're a few revisions away from something solid here.

I have two initial concerns.

First, the draft claims to provide the strengthen reply key facility.
However as far as I can tell from section 8, the draft entirely replaces
the reply key.  The strengthen reply key facility is only appropriate if
the original reply key is mixed into the resulting reply key.
This is important because after the reply key has been replaced,
knowledge of the reply key does not imply anything about authentication.
I believe this mechanism provides the replace reply key facility not the
strengthen reply key facility.

I also have concerns about the proposal to make Kerberos checksums
deterministic.

Permitting non-deterministic checksums was an intentional decision
during the development of RFC 3961.
The theoretical basis behind deterministic checksums is dubious at best;
there are a lot safer models for non-deterministic checksums just as
there are better theoretical (and practical) models behind
non-deterministic encription.

During the SHA-3 competition, there was discussion of whether NIST
should look at parameterized/non-deterministic hashing.  The conclusion
was not to do so, but at least none of the discussions I saw seemed to
deny the value of  non-deterministic hashing.

We revisited this decision yet again when we drafted RFC 6113, and ran
into exactly the same issue that  I think drove the authors to want to
change Kerberos checksums: the desire to  create an incremental checksum
of the conversation in a manner similar to TLS.
After careful discussion, we abandoned that approach.
It would forbid non-deterministic checksums and would require exporting
partial checksum contexts in KDC cookies.

Even if we're going to revisit that decision again, this document is not
the appropriate place to do so.
That's a significant change to RFC 3961 and an explicit reversal of  a
decision that has been reviewed within the community  multiple times.

Such a change should be in its own standards track document not combined
with this specification.

Beyond these specific concerns, I'm nervous about the alignment of this
spec and RFC 6113.  Doubtless part of that is my involvement in 6113
speaking, and I certainly don't have anything substantiated.  I would
request others review for alignment with 6113.

I expect to fully review the document within the next week.

--Sam

---

From: Greg Hudson <[email-masked]>
Date: Thu, 25 Jan 2018 15:07:20 -0500

> strengthen reply key facility.

The replacement key K'[0] is PRF+(initial-reply-key, stuff) where stuff
includes the SPAKE shared result.  Do you think that is not an adequate
way of mixing in the initial reply key?

> I also have concerns about the proposal to make Kerberos checksums

Please have a look at
https://www.ietf.org/mail-archive/web/kitten/current/msg06416.html and
say which direction appeals to you the most.  I went with this approach
because it reflected WG consensus at the time, and tried to be up front
about it (I sent
https://www.ietf.org/mail-archive/web/kitten/current/msg06427.html with
a clear subject line).

> non-deterministic encription.

We have had a deterministic checksum tightly coupled to every enctype
after single-DES, and have used only those tightly-coupled checksums in
standards documents for many years.  We also haven't ever introduced a
checksum type negotiation mechanism other than "this enctype implies
this mandatory-to-implement checksum."  So I don't agree with this at
all; I think the value of admitting non-deterministic checksums is
highly dubious, and that it's vanishingly unlikely that we would ever
migrate towards non-deterministic checksums in the future.

If I could go back in time, I would strongly argue for deterministic
keyed checksums to be a function in the enctype profile, and for
checksum types to not be a thing.  Having a type registry purely for
unkeyed checksums would be okay if we had a need for it.  But having
checksum types with different properties lumped together, in a separate
registry from enctypes, is how we got CVE-2010-1324 and friends.

> partial checksum contexts in KDC cookies.

I do recall that an earlier iteration of 6113 would have required
storing either a partial checksum context or a partial conversation
transcript in the KDC cookie, but the transcript checksum mechanism in
the SPAKE draft doesn't require exporting partial contexts.

> Such a change should be in its own standards track document not combined

I am a little surprised to hear that.  We don't have a history of being
sticklers about document scope; for example, RFC 6806 introduced
PA-REQ-ENC-PA-REP and FAST negotiation, despite being primarily about
referrals.

---

From: Sam Hartman <[email-masked]>
Date: Mon, 29 Jan 2018 08:14:24 -0500

>>>>> "Greg" == Greg Hudson <[email-masked]> writes:

    Greg> On 01/25/2018 01:51 PM, Sam Hartman wrote:
    >> First, the draft claims to provide the strengthen reply key
    >> facility.  However as far as I can tell from section 8, the draft
    >> entirely replaces the reply key.  The strengthen reply key
    >> facility is only appropriate if the original reply key is mixed
    >> into the resulting reply key.  This is important because after
    >> the reply key has been replaced, knowledge of the reply key does
    >> not imply anything about authentication.  I believe this
    >> mechanism provides the replace reply key facility not the

    Greg> The replacement key K'[0] is PRF+(initial-reply-key, stuff)
    Greg> where stuff includes the SPAKE shared result.  Do you think
    Greg> that is not an adequate way of mixing in the initial reply
    Greg> key?

I'm sorry, I misread the spec.
We are in agreement that strengthen reply key is appropriate.

    >> I also have concerns about the proposal to make Kerberos
    >> checksums deterministic.

    Greg> Please have a look at
    Greg> https://www.ietf.org/mail-archive/web/kitten/current/msg06416.html
    Greg> and say which direction appeals to you the most.

I was leaning toward option 3: use a checksum independent of option
3961.  I had planned to propose that in a more detailed review.
I agree option 2 would be more convenient but also agree that we'd need
to make sure the prf has the required properties.
I'd be happy to meet with you and see if we think that's the case if
you're interested in that.

    Greg> I went with
    Greg> this approach because it reflected WG consensus at the time,
    Greg> and tried to be up front about it (I sent
    Greg> https://www.ietf.org/mail-archive/web/kitten/current/msg06427.html
    Greg> with a clear subject line).

I understand.  I think the issues I'm bringing up have not been
adequately considered by the WG.  I think a lot of people involved in
those earlier discussions including the design of RFC 3961 are not
currently involved in the WG (or the IETF).  I would not generally
describe myself as involved in the IETF these days.  So, I think it is
reasonable for the WG to consider whether this new information causes
the WG to change consensus.

    >> Permitting non-deterministic checksums was an intentional
    >> decision during the development of RFC 3961.  The theoretical
    >> basis behind deterministic checksums is dubious at best; there
    >> are a lot safer models for non-deterministic checksums just as

    Greg> We have had a deterministic checksum tightly coupled to every
    Greg> enctype after single-DES, and have used only those
    Greg> tightly-coupled checksums in standards documents for many
    Greg> years.

It sounds like you believe that the point of permitting
non-determisistic checksums was to support the existing DES checksum
types.  While we certainly needed to do that, there was a desire to
permit things like salting a checksum or selecting a function from a
family of functions if general attacks against a fully known function
got stronger.

Around the time of the MD5 and SHA-1 concerns, this felt like a very
important potential fallback.
I think it still is.

    Greg> We also haven't ever introduced a checksum type
    Greg> negotiation mechanism other than "this enctype implies this
    Greg> mandatory-to-implement checksum."  So I don't agree with this
    Greg> at all; I think the value of admitting non-deterministic
    Greg> checksums is highly dubious, and that it's vanishingly
    Greg> unlikely that we would ever migrate towards non-deterministic
    Greg> checksums in the future.

    Greg> If I could go back in time, I would strongly argue for
    Greg> deterministic keyed checksums to be a function in the enctype
    Greg> profile, and for checksum types to not be a thing.

If I could go back in time, I would certainly argue for checksum types
to not be a thing.

You seem to be conflating checksum type negotiation with deterministic
checksums.  I'm assuming if we wanted a checksum that was not
deterministic, we'd either introduce it at the same time as an enctype
migration or if we were responding to an attack, introduce a new enctype
explicitly for the checksum type.

I think it's fairly unlikely we're going to introduce a new enctype that
sees wide use until we see some sort of attack we're responding to.
I think whether we look at nondeterministic checksums will depend on the
state of our confidence in our hashes at the time.

    Greg> Having a
    Greg> type registry purely for unkeyed checksums would be okay if we
    Greg> had a need for it.  But having checksum types with different
    Greg> properties lumped together, in a separate registry from
    Greg> enctypes, is how we got CVE-2010-1324 and friends.

We're in agreement that RFC 1510's handling of key types, enctypes and
checksum types was a huge mess.  We tried to clean that up with RFC 3961
but were unable to remove checksum types because of legacy.  RFC 3961
does not come out and say that for new enctypes you have one checksum
type per enctype, but that's the only sensible thing to do.

    >> Such a change should be in its own standards track document not
    >> combined with this specification.

    Greg> I am a little surprised to hear that.  We don't have a history
    Greg> of being sticklers about document scope; for example, RFC 6806
    Greg> introduced PA-REQ-ENC-PA-REP and FAST negotiation, despite
    Greg> being primarily about referrals.

I don't think those changes were reversing previous consensus.
I think that if the WG is going to reverse a consensus decision it has
revisited multiple times before, writing a document to call that out and
to get the review from people who thought about those issues is
valuable.
I have no concerns about lumping in non-controversial changes into other
documents.

---

From: Greg Hudson <[email-masked]>
Date: Wed, 31 Jan 2018 16:40:56 -0500

On 01/29/2018 08:14 AM, Sam Hartman wrote:> I agree option 2 would be
more convenient but also agree that we'd need
> you're interested in that.

After a phone discussion with Sam:

* PRF might not have the required properties, although it would probably
still be difficult to attack.  SPAKE2's security proof relies on a
random oracle (implemented using a hash) over the concatenation of the
party identities, the public keys, the initial secret, and the shared
group element.  A PRF is supposed to emulate a random oracle if the
function is chosen randomly from the PRF family, but in this case we're
choosing it based on a low-entropy secret.  It seems unlikely that an
attacker could make any headway since a large part of the PRF input
string (the shared group element) is unknown, but the security proof
most likely does not work.

* If we want to hew closely to the SPAKE2 security proof, we probably
need to bring an unkeyed hash into the operation (as the current draft
already uses PRF+ instead of a hash function for the final key
derivation).  There are two possibilities for choosing the unkeyed hash,
the second of which I hadn't considered in detail:

  1. Choose the hash based on the group number (make it part of the
group definition).  There are two concerns here:
  1a. If the KDC issues an optimistic challenge and the client rejects
it (going back to issuing a SPAKESupport), the hash function might
change.  We could fix this by not including rejected optimistic
challenges in the transcript, which should be fine; the subsequent group
negotiation should still be secure.
  1b. There's no hard guarantee that the group's hash function output
size is as large as the enctype's random-to-key input size, although
SHA-256's output size would likely be good enough for the forseeable
future.  So we would have to specify an exception case when the hash
output size isn't big enough, or use a hash extension scheme, which is
easy to do (it would look a lot like PRF+) but is fiddly.

  2. Choose the hash based on the enctype, essentially defining a
SPAKE-specific extension to RFC 3961 in the form of a mapping from
enctype number to hash function.  Mapping this way means we can ensure
that the chosen hash function output size is at least as large as the
enctype random-to-key input size, for each enctype.  We would probably
want to use SHA-256 for every existing enctype, even for enctypes which
use SHA-1 or something worse internally.

  One question which informs the choice between (1) and (2) is whether
bigger, harder groups (P-521 as compared to P-256, for example) benefit
from larger intermediate hashes.  I don't think they do, as everything
gets hashed down to the enctype random-to-key input size in the end.

* Using recursive hash operations to limit how much the KDC has to
remember should be fine, under the random oracle assumption.
random-oracle(random-oracle(A|B)|C) should look the same to an attacker
as random-oracle(A|B|C), assuming the intermediate hash size is too
large to practically attack.

> explicitly for the checksum type.

So the concern here (clarified via the call) is that we could find a
theoretical attack on existing uses of checksums, which could be
resolved using non-deterministic MACs, and perhaps isn't bad enough to
create an immediate practical attack but is bad enough that we want to
migrate away from deterministic MACs via new enctypes.  I continue to
think this scenario too unlikely to worry about, but Sam having raised
the objection does motivate me to more strongly consider substituting an
unkeyed hash for the draft's existing key derivation and transcript
checksum methods.

---

From: Simo Sorce <[email-masked]>
Date: Wed, 31 Jan 2018 17:10:54 -0500

> use SHA-1 or something worse internally.

The one concern here is, what happen if the hash function turns out to
be broken down the line ?
How would new and old code negotiate what hash to use ?

Or is the thinking that we'd add new enctypes if the hash function is
broken anyway so new enctypes will be mapped to this new hash function
?

What happens when a new enctype is introduced ? Will there have to be
also an explicit allocation of a hash type to be use for SPAKE?
Will it be implicit ? At least SHA-256 or whatever the enctype uses if
"better" ?

> unkeyed hash for the draft's existing key derivation and transcript

I do not have an issue with this, assuming we do not corner ourselves
with the choice of hash.

Simo.

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

---

From: Greg Hudson <[email-masked]>
Date: Wed, 31 Jan 2018 17:56:01 -0500

On 01/31/2018 05:10 PM, Simo Sorce wrote:>>   2. Choose the hash based
on the enctype [...]

> broken anyway so new enctypes will be mapped to this new hash function

We would have to migrate to a new enctype to change the hash function we
use in SPAKE.  That's a high cost in some scenarios--like if someone
discovers a horrible preimage attack on SHA-256, but SHA-1 still appears
as preimage-resistant as it does today, so that aes-sha1 still seems
like a decent enctype to use for every purpose other than SPAKE.  But I
think those scenarios are vanishingly unlikely.

> Will it be implicit ? At least SHA-256 or whatever the enctype uses if

When a new enctype is defined, we would also have to populate its entry
in the SPAKE mapping of enctype to hash function (which could be an IANA
registry).  If there's no mapping for an enctype then that enctype can't
be used with SPAKE.  But it should be easy to update the SPAKE
enctype-to-hash registry in the same document as we define a new enctype.

There is the option of specifying "SHA-256 as long as the key size is <=
256 bits unless there's an explicit mapping," but that option runs a
serious interoperability risk--one party might use the SHA-256 default
(through negligence or some time window between the enctype assignment
and the SPAKE mapping update) while the other party uses a different,
explicitly specified hash function.