Subject: Re: [kitten] pa-hints in draft-ietf-kitten-krb-spake-preauth-04

From: Sam Hartman <[email-masked]>
Date: Thu, 01 Feb 2018 08:58:59 -0500

Yesterday I also discussed my RFC 6113 alignment concerns with Greg.

If I were more involved in implementing Kerberos, I probably would be
arguing for a somewhat different approach--focusing on less duplication
of facilities provided in RFC 6113.  However, Greg reviewed the history,
and I have confidence that the issues I'm thinking about were
considhered by those involved in the design of the proposal.  So with
one exception, with regard to RFc 6113 alignment I believe my concerns
have already been considered and rejected.

I brought up one issue that I don't think has been adequately
considered: the decision not to include a pa-hint in this proposal.

Under RFC 6113, the preauthentication types that participate in a
preauthentication set are permitted to include a hint in the first
message.
The intent is for a client to know whether it has the necessary
facilities (CAs, algorithm support, access to appropriate tokens, etc)
in order to succeed at using a preauthentication set  before starting.

We're trying to avoid the following:

* A KDC proposes an authentication set with SPAKE as the second element

* The first member of that authentication set requires user
  interaction.  So the client interacts with the user.

* Then the client discovers that it doesn't share a group in common with
  the KDC.

The intent of RFC 6113 is that a client know what user interaction will
be required and whether it has the necessary support prior to starting
an authentication set.  I don't think SPAKE meets this intent.  There
are mechanisms prior to RFC 6113 that also don't provide this facility.
However, I think it would be relatively easy to define a hint message
including the set of groups the KDC supports to work in this case.

I realize that in the current draft, group offers are always sent from
the client to the KDC.
I note that beyond a relatively small specification complexity burden
(defining a message similar to an existing message), the complexity
burden of sometimes getting groups from the KDC would only be suffered
by implementations that use SPAKE  in authentication sets.

---

From: Simo Sorce <[email-masked]>
Date: Thu, 01 Feb 2018 09:10:11 -0500

On Wed, 2018-01-31 at 17:56 -0500, Greg Hudson wrote:
> On 01/31/2018 05:10 PM, Simo Sorce wrote:>>   2. Choose the hash based
> on the enctype [...]
> 
> > 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
> > ?
> 
> 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.
> 
> > 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" ?
> 
> 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.

It is a bit annoying to have to do this for each new enctype ... just
for a pre-auth mechanism.
I wonder if we couldn't simply add a field in the first message that
specifies the hash we are using.
The server can then just refuse operations if it doesn't want to use
the hash the client selected.
This would allow smooths transitions from "current-hash" to "new-hash"
in case current hash is not totally broken right away, but like SHA-1
gets weaker and weaker and we plan replacement.

It would mean potentially allowing clients to use a new enctype with a
keysize longer than the current hash, but I would assume we would add a
new hash option as that enctype is introduced and clients would do the
same. The server can simply refuse the older hash type with newer
enctypes, while still allowing older hash with older enctypes for
clients that have not caught up.

I do not know if this is desirable or can pose issues (downgrade
attacks ?), but I thought mentioning it as an option, to have a
possibility for a smoother transition in future.

> 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.

Indeed, I wouldn't do this without the option I mention above.

Simo.

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

---

From: Greg Hudson <[email-masked]>
Date: Thu, 1 Feb 2018 11:45:02 -0500

> considered: the decision not to include a pa-hint in this proposal.
[...]
> by implementations that use SPAKE  in authentication sets.

I think we can just reuse SPAKESupport, so this should be easy to
specify.  And yes, a KDC or client which doesn't implement
authentication sets doesn't have to do anything.  I can write up the text.

My inclination is to specify that the pa-hint should not affect the
transcript, since it occurs in an earlier phase of operation
(authentication set selection), and including it in the transcript would
make life harder for the KDC.  The client will send its own SPAKESupport
message once SPAKE preauth beginsw, and that message will be included in
the transcript.

---

From: Sam Hartman <[email-masked]>
Date: Thu, 01 Feb 2018 12:17:45 -0500

>>>>> "Simo" == Simo Sorce <[email-masked]> writes:

    Simo> It is a bit annoying to have to do this for each new enctype
    Simo> ... just for a pre-auth mechanism.  I wonder if we couldn't
    Simo> simply add a field in the first message that specifies the
    Simo> hash we are using.  The server can then just refuse operations
    Simo> if it doesn't want to use the hash the client selected.  This
    Simo> would allow smooths transitions from "current-hash" to
    Simo> "new-hash" in case current hash is not totally broken right
    Simo> away, but like SHA-1 gets weaker and weaker and we plan
    Simo> replacement.

I think that the idea of combining the hash definition with the group
definition is about the same as this, only a bit simpler.

My ranked options are:

* Combine choice of hash with choice of group (Kerberos SPAKE groups
  include a hash function in their definition).  Requires changing the
  spec to restart the hash when a KDC rejects an optimistic group
  offer.  Greg and I believe the security of this is fine.

* Registering a mapping of SPAKE hashes to enctypes.  The major
  advantage I see is that it can (I think) maintain interop with the
  existing protocol.  The down side is that in some cases you might have
  to register a new enctype or except a non-ideal SPAKE hash.

* Use the PRF.  I think  that while the concerns are real, the security
  is fine

* Your proposal of hash in first message

*  Get sufficient review and make RFC 3961 hashes deterministic

* Find other options

* Give up on SPAKE

---

From: Simo Sorce <[email-masked]>
Date: Thu, 01 Feb 2018 14:11:39 -0500

> * Your proposal of hash in first message

I think the above options are all fine by me, maybe not in the same
exact order, but they all work.

> *  Get sufficient review and make RFC 3961 hashes deterministic

I'd rather not go into the last three, but I am open to other options
that have substantial advantages and no big downside compared to the
first 4 on the table that it is worth spending time on them.

Simo.

---

From: Nathaniel McCallum <[email-masked]>
Date: Thu, 1 Feb 2018 15:15:58 -0500

I agree with Simo. The first two options are probably the best. I
don't have a strong opinion between them. However, I suspect that we
aren't worried about compatibility at this point (nobody ships this).

On Thu, Feb 1, 2018 at 2:11 PM, Simo Sorce <[email-masked]> wrote:
> _______________________________________________
> Kitten mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/kitten

---

From: Nathaniel McCallum <[email-masked]>
Date: Thu, 1 Feb 2018 15:27:40 -0500

If we reuse SPAKESupport, then we can never differentiate between the
client and server messages. I'm not objecting, just noting.

---

From: Benjamin Kaduk <[email-masked]>
Date: Thu, 1 Feb 2018 22:06:18 -0600

> message once SPAKE preauth beginsw, and that message will be included in

This is probably fine, and we can reiterate in the security
considerations that the hints are just hints (i.e., not
authoritative), and could be wrong.

-Ben

---

From: Greg Hudson <[email-masked]>
Date: Sat, 3 Feb 2018 13:19:16 -0500

On 02/01/2018 12:17 PM, Sam Hartman wrote:> * Combine choice of hash
with choice of group (Kerberos SPAKE groups
>   offer.  Greg and I believe the security of this is fine.

Under this choice the transcript hash cannot be started until a group is
selected, so in the normal message flow we won't initialize the
transcript until the KDC sends its challenge message.  This works
because the client and KDC both still have access to the client's
support message (the client because it is stateful, and the KDC because
the support message is present in the request the KDC is processing).
We can concatenate the support and challenge message together and update
the transcript hash with both at once, saving a hash operation.

For the case where the group's hash function doesn't output enough bytes
for the enctype's random-to-key function, I currently have this text:

        [as the last field of the hash input:]
        * A single-byte block counter, with the initial value 0x01.

    If the hash output is too small for the encryption type's key
    generation seed length, the block counter value is incremented and
    the hash function re-computed to produce as many blocks as are
    required. The result is truncated to the key generation seed length,
    and the random-to-key function is used to produce the key value.

For edwards25519 and P-256, SHA-256 is a clear best choice.  From a
security perspective, I believe SHA-256 is also an adequate choice for
P-384 and P-521 because we're likely going to truncate down to 128 or
256 bits for the key anyway.  But if someone is using P-384 or P-521,
they're probably doing so for compliance with some kind of 192-bit or
256-bit security standard, and the use of SHA-256 might raise a flag
because of its 128-bit collision resistance.  So I lean towards
specifying SHA-384 for P-384 and SHA-512 for P-521.  If someone is using
those groups, they are already wasting a bunch of bytes on unnecessarily
large public keys anyway.

---

From: Nathaniel McCallum <[email-masked]>
Date: Sat, 3 Feb 2018 13:46:52 -0500

I agree regarding hash choices. However, as I was thinking about the hint,
it does open the door to a downgrade attack. If the hint isn't in the
transcript, we can't tell if it was modified. As the protocol currently is
defined, any attempt to modify the SPAKESupport message will break the
final key derivation.

So in my mind, the value of using a hint needs to be weighed against this
cost.

What is the precise reason the hint can't be included in the transcript?

On Feb 3, 2018 1:19 PM, "Greg Hudson" <[email-masked]> wrote:

---

From: Greg Hudson <[email-masked]>
Date: Sat, 3 Feb 2018 16:24:48 -0500

On 02/03/2018 01:46 PM, Nathaniel McCallum wrote:
> I agree regarding hash choices. However, as I was thinking about the
> hint, it does open the door to a downgrade attack. If the hint isn't in
> the transcript, we can't tell if it was modified. As the protocol
> currently is defined, any attempt to modify the SPAKESupport message
> will break the final key derivation.

A pa-hint would be used only when a KDC advertises an RFC 6113
authentication set containing SPAKE and one or more other preauth
mechanisms.  (As far as I know, nobody implements RFC 6113
authentication sets at this time.)  The pa-hint would be used by a
client to decide whether to select between this authentication set, and
another authentication set which perhaps does not use SPAKE.  The
pa-hint would allow the client to determine ahead of time whether SPAKE
group negotiation will succeed.  Without the pa-hint, the client might
only find out that SPAKE won't work after it has already processed an
earlier part of the authentication set, perhaps asking for user input.

If the client does decide to use this authentication set, it will use
the normal message flow which begins with a client's SPAKESupport
message.  This support message will be included in the transcript, so
group negotiation will be protected.

Including the pa-hint in the transcript would pose some difficulty for
the KDC.  The KDC does not know at the time of the pa-hint what group
will be negotiated (so it doesn't know what hash function to use, if the
hash function is a property of the group).  It also might not want to
use network bytes on a cookie at this point, since it doesn't know if
the client understands SPAKE at all.  So I would expect a KDC to instead
reconstruct its pa-hint later on when it processes the client's support
message.  That would mean changes to the KDC configuration could break
authentications in progress.

(It's possible that you were thinking of a rejected KDC optimistic
challenge rather than a pa-hint, the problem is that the hash function
might change when the selected group changes.  If the client rejects an
optimistic KDC challenge, it will fall back to the normal message flow
which still protects group negotiation.)

(It's also possible that you were thinking of the initial pa-value that
gets included in a preauth_required error that simply lists SPAKE as one
of several preauth types.  That would be understandable because the MIT
krb5 KDC code calls the preauth_required method-data a "hint list", but
that is not what an RFC 6113 pa-hint is.  Currently the initial SPAKE
pa-value is empty unless the KDC issues an optimistic challenge, and we
are not proposing to change that.)

---

From: Nathaniel McCallum <[email-masked]>
Date: Sat, 3 Feb 2018 23:02:30 -0500

Got it. Thank you for the clarification.

---

From: Benjamin Kaduk <[email-masked]>
Date: Sun, 4 Feb 2018 21:06:43 -0600

I also think that we should probably go with one of the first two
options.  There is some appeal to attaching the hash to the SPAKE
group, since they both are things new in this spec and we don't have
to awkwardly try to force enctypes to also include a new thing.
The downside is of course that we might choose a hash that is "too
small" for some hypothetical new enctype that uses large keys, but
presumably we will notice the conflict if such a new enctype arises,
and can make new group entries (even if they are the same underlying
groups) with larger hashes.

-Ben

---

From: Greg Hudson <[email-masked]>
Date: Mon, 5 Feb 2018 01:00:19 -0500

This option seems to have the most initial WG support.  So I have put
together proposed changes to the spec:

https://github.com/greghudson/ietf/pull/4/commits/77753ee1c901ff771cba46b8c16d801fd8c74676

I have also updated my Python implementation to produce updated test
vectors, and my C implementation (for MIT krb5) to verify them.

Substantial bits of new text:

[In the section "SPAKE Pre-Authentication Message Protocol":]
  Each group definition specifies an associated hash function, which
  will be used for transcript protection and key derivation.

[In the section "Second Pass":]
  The client and KDC will each initialize a transcript hash [xref]
  using the hash function associated with the hosen group, and update it
  with the concatenation of the DER-encoded PA-SPAKE messages sent by
  the client and the KDC.

[In the section "Optimizations":]
  If the group chosen by the challenge message is supported by
  the client, the client MUST skip to the third pass by issuing an
  AS-REQ with a PA-SPAKE message using the response choice. In this case
  no SPAKESupport message is sent by the client, so the first update to
  the transcript hash contains only the KDC's optimistic challenge. If
  the KDC's chosen group is not supported by the client, the client MUST
  continue to the second pass. In this case both the client and KDC MUST
  reinitialize the transcript hash for the client's support message.
  Clients MUST support this optimization.

[In the section "Transcript Hash":]
  When the transcript hash is updated with an octet string input, the
  new value is the hash function computed over the concatenation of the
  old value and the input.

  In the normal message flow or with the second optimization described
  in [xref], the transcript hash is first updated with the concatenation
  of the client's support message and the KDC's challenge, and then
  updated a second time with the client's pubkey value. It therefore
  incorporates the client's supported groups, the KDC's chosen group,
  the KDC's initial second-factor messages, and the client and KDC
  public values. Once the transcript hash is finalized, it is used
  without change for all key derivations [xref].

  If the first optimization described in [xref] is used successfully,
  the transcript hash is updated first with the KDC's challenge message,
  and second with the client's pubkey value.

  If first optimization is used unsuccessfully (i.e. the client does
  not accept the KDC's selected group), the transcript hash is computed
  as in the normal message flow, without including the KDC's optimistic

  challenge.

[In the section "Key Derivation":]

  [As the fourth field in the hash input:]
  The PRF+ output used to compute the initial secret input w as
  specified in [xref].

  [As the ninth and final field in the hash input:]
  A single-byte block counter, with the initial value 0x01.

  If the hash output is too small for the encryption type's key
  generation seed length, the block counter value is incremented and the
  hash function re-computed to produce as many blocks as are required.
  The result is truncated to the key generation seed length, and the
  random-to-key function is used to produce the key value.

The section "Update to Checksum Specifications" is removed, and with it
the prohibition against using SPAKE with single-DES enctypes.

For the pa-hint for authentication sets, I realized that we probably
want to include second factor info as well as KDC group support, so I
will address that in a separate update and thread.

---

From: Nathaniel McCallum <[email-masked]>
Date: Mon, 5 Feb 2018 11:08:00 -0500

This all looks good. Thanks!

---

From: Nathaniel McCallum <[email-masked]>
Date: Mon, 5 Feb 2018 11:11:00 -0500

Unless I'm missing something, I don't think this is necessary. When
the hash is associated with the group choice, the output size of the
hash is correlated to the strength of the group used. If a new enctype
arises with stronger keys, increasing the hash alone won't increase
the security of the SPAKE exchange itself. Therefore, an entirely new
group is needed.

---

From: Greg Hudson <[email-masked]>
Date: Mon, 5 Feb 2018 15:32:05 -0500

[...]

Nathaniel wrote, in a different part of the thread responding to Ben:
> When

Ben may have been thinking about the protocol working at all (easily
solved by hash extension), but Nathaniel's response made me think about
the possibility that the SPAKE exchange might reduce the work an
attacker would require to discover the reply key, in the case where the
initial reply key was high-entropy to start with.  As Nathaniel notes,
for this possibility we have to consider the group as well as the hash
function.

To make a long story short, I think to be excruciatingly correct we
should compute KRB-FX-CF2 of the derived key with the initial reply key,
in case w (as represented by the PRF output used to compute it) is
shorter than the initial reply key was and therefore contains lower
entropy.  So we would have:

  reply-key <- KRB-FX-CF2(initial-reply-key,
                          random-to-key(H(...|w|K|...)),
                          pepper1, pepper2)

That way we can't possibly make the reply key any worse.  This is only
really an issue for a future where attackers can do 2^128 brute force
work (enough to break ECDLP on edwards25519 or P-256), but we may as
well get it right.

---

From: Nathaniel McCallum <[email-masked]>
Date: Mon, 5 Feb 2018 16:39:16 -0500

Agreed.

---

From: Benjamin Kaduk <[email-masked]>
Date: Mon, 5 Feb 2018 19:00:23 -0600

> for this possibility we have to consider the group as well as the hash

Right, I mean the case where the group size matches the SPAKE hash, but
the enctype is bigger than both, though you have taken this even a
little further than I had in mind.  (But it still makes sense!)

> work (enough to break ECDLP on edwards25519 or P-256), but we may as

Yup.

---

From: Sam Hartman <[email-masked]>
Date: Tue, 13 Feb 2018 09:17:50 -0500

>>>>> "Nathaniel" == Nathaniel McCallum <[email-masked]> writes:

    Nathaniel>    Agreed.

The changes, including the discussion of  using krb-fx-cf2 to protect
initial high-entropy reply keys.
I agree that high entropy reply keys are unlikely in cases where SPAKE
is valuable, but it's relatively easy to do.