Subject: [kitten] SPAKE Preauth

From: Nathaniel McCallum <[email-masked]>
Date: Mon, 27 Apr 2015 08:45:54 -0400

I have finally finished the first edition of SPAKE Preauth. You can
read it at this link:
http://www.ietf.org/id/draft-mccallum-kitten-krb-spake-preauth-00.txt

Comments welcome!

Nathaniel

---

From: Greg Hudson <[email-masked]>
Date: Tue, 28 Apr 2015 11:09:39 -0400

> http://www.ietf.org/id/draft-mccallum-kitten-krb-spake-preauth-00.txt

I think this mechanism has a lot of potential, and I hope the kitten
working group will adopt this document.  There is a lot of work to be
done at the detail level, but I think the general shape of the mechanism
is about right.

I think this mechanism addresses three under-served scenarios:

1. A realm administrators are concerned (or ought to be concerned) about
the potential for offline dictionary attacks conducted by an adversary
using passive network surveillance.  The realm is using only passwords
for user authentication and does not have the resources to deploy a
second factor.  Encrypted timestamps are in use but do not protect
against a network listener.

There are several other ways to address this use case, including FAST.
But SPAKE preauth can be deployed more easily than FAST--perhaps even
turned on by default--and does not require as many changes to other
layers to make deployment easier.

2. A realm is using passwords for user authentication, and the
administrators want to add a traditional OTP second factor (like Yubikey
or RSA tokens) for some or all principals.  FAST-OTP is designed to
replace, rather than augment, the use of Kerberos long-term keys, and is
therefore not easy to apply to this situation.

In this use case, SPAKE preauth is used with a second-factor challenge
in the second pass, and the token value is transmitted inside the key
confirmation.  The KDC issues a ticket if key agreement succeeded and
the token value is valid, and responds with an error if either is wrong.
 If there are no side channels, an attacker can't tell which factor was
guessed incorrectly.

3. Same as (2), but the realm administrators want to add a Duo-style
second factor.  In this style, the password needs to be validated first,
and then the user is presented with a choice of options for the second
factor.  Depending on the choice, there may or may not be an OTP value
presented to the KDC for validation.

In this use case, SPAKE preauth is used without a second-factor
challenge in the second pass, but additional challenge/responses occur
after key agreement.  An attacker does get to make on-line guesses at
the password separately from the second factor, but is unable to cause
nuisance second-factor challenges (such as pushes to the user's mobile
device) without knowledge of the password.

---

From: Benjamin Kaduk <[email-masked]>
Date: Tue, 28 Apr 2015 17:53:01 -0400 (EDT)

> done at the detail level, but I think the general shape of the mechanism

I agree with this assessment, and hope that the document will move forward
through the working group.

> against a network listener.

I think this point could be emphasized in section 1 -- the current text is
only "offline brute-force attack against the transferred packet", saying
nothing about passwords, let alone weak passwords.

>  If there are no side channels, an attacker can't tell which factor was

"can't tell which factor was guessed incorrectly" seems like a pretty
important property (I would be really excited to see a scheme with this
property get deployed!), but it does not seem to be mentioned in the
current section 1.2 text.  (It does talk about avoiding
ciphertexts^Wpackets which are vulnerable to offline brute-force attack,
but I don't see anything mentioning the online attack as well.)  Hmm, this
is mentioned in the security considerations, at least.  I think it should
be more prominent earlier in the document.

However, it seems like the text at the end of section 4.3 wherein "[i]f
validation of the second factor requires furthe round-trips, the KDC MUST
reply to the client with KDC_ERR_MORE_PREAUTH_DATA_REQUIRED [...]" loses
the indistinguishability property, as the encrypted SPAKESecondFactor
would not be generated if the long-term key (password) was incorrect.
This seems inherent to second factors which require multiple round trips
to validate, though, so maybe we have to make a choice of the tradeoff.

[case 3 trimmed]

Some additional comments:

The current version of 4.3 only allows for one second factor to be used.
Do we want to consider a design which permits multiple additional factors
to be used (maybe, phone and hardware token, or something like that)?

We talked about SPAKE on the MIT kerberos dev call today, and one of the
things mentioned is that the M and N values are specified per group in
draft-irtf-cfrg-spake2 (along with a procedure for selecting them for new
groups); we should explicitly note that their selection (and encoding?) is
delegated to the IRTF document.

Also covered on the MIT dev call, we should go into more detail about the
transcript hash (in a separate subsection?).  Apparently there is also a
discussion to have about the way the transcript includes the full exchange
of messages, i.e., whether it is okay to chain hashes or the full history
must be buffered.

With respect to the recommended groups in section 7, I believe that
interoperability concerns should drive us to pick at least one mandatory
to implement group.  The state of things elsewhere in the IETF and IRTF
seem to be leaning towards non-NIST curves as well; we should probably
consider if the CFRG curve recommendations to the TLS working group are
relevant for this case.

The IANA considerations are not considered complete by current standards;
see BCP 26 (i.e., RFC 5226 at present).  In particular, section 4.2
contains the list of what needs to be in a document which creates a
registry.

Nits:

In 1.2, "attempting to encrypt this data using the long-term password"
implicitly assumes "using authenticated encryption (such as RFC 3961
crypto)", as I understand it.

1.2, second paragraph, first line, comma after "FAST".

Still 1.2, it's "certification authority", not "certificate authority".

Last sentence of 1.2, is "leveraged into" really correct?  I thought that
the long-term key and the 2FA data were mixed into the DHE in the same
way.

In 1.3, first paragraph, penultemate sentence, "indistinguishable from
random" seems like an incomplete clause; maybe "random data" or "random
bits"?

1.3, second paragraph, antepenultimate sentence, in "equivalent security",
as a reader I expect to see what it is equivalent to, i.e., "equivalent
security using standard DH-KE".

In 3.1, I think the text would read more naturally if consolidated into a
single sentence, viz. "a PA-ETYPE-INFO2 element with a single
ETYPE-INFO2-ENTRY containing the etype [...]".

Perhaps 3.3 should cite RFC 6113 for KDC_ERR_MORE_PREAUTH_DATA_REQUIRED.

There are several places where the document indicates only the fields in
KDC-RE{Q,P}s which are specific to SPAKE, with no reference to the other
fields which will be included indicating support for other preauth
schemes, etc..  While this can be a valid style to use, I wonder if some
consideration should be given to some additional text about "in the set of
pre-authentication data in the KRB_ERROR message" for section 4.1, and
similarly elsewhere in the document.

Section 4.3 should forward-reference section 5.1 for key derivation.

In section 4.3, second paragraph, us a comma instead of a semicolon to
prefix "possibly using the challenge data for this second factor type",
since that is a dependent clause.

We should probably be a little more explicit about what key, usage, etc.
are going on for the EncryptedData encrypted/checksummed with the session
key derived from the SPAKE key; we covered this a little bit on the MIT
dev call today as well.

In 4.4, "second factor type specific" is a bit awkward; maybe "specific to
each type of second factor"?

In section 8, the integrity confirmation of the transcript messages occurs
when the SPAKEResponse is processed and validated, not when it is
transmitted, I think -- the KDC is the second party to compute the
transcript/key derivation, and the verification that the two parties'
transcripts agree occurs when the KDC compares its local copy to the one
it got from the network.

-Ben

---

From: Nico Williams <[email-masked]>
Date: Wed, 29 Apr 2015 11:17:19 -0500

> http://www.ietf.org/id/draft-mccallum-kitten-krb-spake-preauth-00.txt

I'm in favor of the WG adopting this as a WG work item.

I have some comments:

 - Kerberos doesn't really depend on synchronization of client clocks
   for any of the KDC exchanges (AS, TGS): because they are stateless
   and retriable, and the client learns the KDC's time in KRB-ERROR
   PDUs.

   Pre-auth methods that don't depend on the client's clock are mostly
   an optimization.  They are less of an optimization when failures
   count towards locking a principal, but still an optimization (since
   one can account for clock skew by adding one to N-strikes-you're- 
   locked policies).

   Time synchronization across services in a realm is not something that
   is being fixed here either.

   IMO the time sync aspects of this are a bit overdone :)

 - Section 1.1 is a bit weak.  I don't think it's even necessary to
   explain PAKE in terms of DH key agreement either.

   The properties of a PAKE are:

    - provides authenticated key agreement with both parties
      contributing entropy to the shared secret;

      (And each exchange yields a different shared secret.)

    - is resistant to off-line dictionary attacks by eavesdroppers, even
      for small, simple passwordsj

    - "servers" store password equivalents;

      (In an augmented PAKE the server stores a verifier, but you're not
      proposing the use of an augmented PAKE.)

    - users "store" passwords.

 - Section 1.2, the claim about why FAST is difficult to deploy requires
   more evidence, and I believe it's wrong.  The problem with FAST is
   that it's difficult to make it a requirement for PA-ENC-TIMESTAMP
   because FAST is not universally available yet -- the tragedy of
   legacy forever.  Sure, one has to deploy trust anchors, but then
   again, one doesn't have to (leap of faith), and one can (for machines
   that have "joined" a realm or hierarchy of realms).

   Either elaborate this claim, or leave it at "it's difficult to
   deploy".  This claim just isn't all that important to this work:
   after all, the key is the ability to combine a PAKE and a second
   factor in a way that leaks no information about which factor was
   incorrect when either (or both) were.  FAST doesn't help with that.
   Even more interesting properties can be dreamed up that FAST simply
   can't help with either.

   On the other hand, FAST is still relevant: for providing
   confidentiality protection of the client's principal name.

   There's just no need to justify this or any other pre-auth method
   based on FAST's real or perceived failure.

   Indeed, all new pre-auth methods might well (will!) suffer from some
   of the same barriers to adoption that I think FAST suffers from, and
   then what?  Should we stop designing new pre-auth methods?  No.

Controversial claims that are not core to the document should just go.

That's as far as I got reading the I-D so far.  I've reviewed the design
before and I approve, and I'll complete my review of the I-D at some
point.

Nico
--

---

From: Nathaniel McCallum <[email-masked]>
Date: Thu, 30 Apr 2015 09:49:49 -0400

Thanks for your feedback!

>    one can account for clock skew by adding one to N-strikes-you're- 

As I stated in the draft: "where a timestamp is used, time
synchronization between the client and KDC becomes a point of
fragility." I think your paragraph here proves this point. Where
synchronization is off, extra messages are sent. I think this
qualifies as fragility.

>    is being fixed here either.

Agreed.

>    IMO the time sync aspects of this are a bit overdone :)

Maybe. I'll see if I can come up with wording you like better. I still
think it is worth mentioning however.

>     - users "store" passwords.

The intent of this section is to explain PAKE to those unfamiliar with
it. If such is not needed in this document, I can remove it.

>    that have "joined" a realm or hierarchy of realms).

Well, that is not Red Hat's experience. We have FAST everywhere, but
we have people who don't want us to configure their client. This is
most especially true in open communities like Fedora where we are
working with volunteers.

In these cases we have two options:

1. Use the existing system trust anchor w/ anonymous pkinit. This has
all the problems that web developers are already trying to solve. For
instance, if we trusted Verisign, someone could setup
efdoraproject.org and configure the KDC for OTP. Anyone who did "kinit
[email-masked]" by mistake would leak both the first and
second factor to a completely trusted but malicious KDC.

2. Ask volunteers to trust our KDC cert explicitly. Then have them do 
a manual anonymous pkinit. Then have them use this ccache for enabling
FAST. This is error prone and requires manual configuration. It is a
no go.

In contrast, PAKE allows a completely configless usage with no third
-party trust and no leap of faith.

Perhaps I have simply not captured this concern well in the draft. But
it is most definitely more than "we don't have FAST everywhere."

>    confidentiality protection of the client's principal name.

Nowhere did I claim that PAKE obsoletes FAST. I said: "In the past,
this problem (2FA) has been mitigated by FAST which uses a secondary
trust relationship to create a secure encryption channel within which
pre-authentication data can be sent.  However, the requirement for a
secondary trust relationship has proven to be cumbersome to deploy and
often introduces third parties into the trust chain (such as
certificate authorities)."

Both of these statements are true and represent true complexities of
FAST that do not exist with PAKE.

>    based on FAST's real or perceived failure.

I do think this document needs to justify why we just shouldn't use
FAST like how RFC 6560 does. This draft represents a departure from
the recently established precedent of second factors. The reason why
this departure is necessary is because of the above reasons.

>    then what?  Should we stop designing new pre-auth methods?  No.

I'm not addressing all pre-auth types. I'm addressing why we should
depart from recent precedent in RFC 6560.

> Controversial claims that are not core to the document should just 

I agree. I just don't think these claims are controversial.

> before and I approve, and I'll complete my review of the I-D at some

Thanks! I look forward to your feedback!

Nathaniel

---

From: Greg Hudson <[email-masked]>
Date: Thu, 30 Apr 2015 12:07:54 -0400

> synchronization is off, extra messages are sent. I think this

Hm, I would give a more nuanced description:

In a normal scenario, the client can get the KDC's timestamp from the
PREAUTH_REQUIRED error.  This timestamp is unauthenticated, so using it
pretty much defeats any freshness value the timestamp might add to the
preauthentication protocol.  Since there isn't much freshness value in
that timestamp (an active or passive attacker immediately gets a
ciphertext with which to conduct offline password dictionary attacks,
rendering password lockout moot), the MIT krb5 client does use that
timestamp for encrypted preauth, and no extra messages are sent even if
the client's clock is off.

When authenticating with a keytab, a client might choose to use
optimistic encrypted timestamp preauth to indicate which key the client
possesses.  (The MIT krb5 client does not do this, and the MIT krb5 KDC
does not use the result for key selection.  The latter should definitely
change and the former might change.)  If this is done, clock skew could
force a second exchange.

I also thought it was weird to lead with timestamp issues in the draft.
 I'm not sure I would mention them all in section 1.

>>    that have "joined" a realm or hierarchy of realms).

This is partly true.  Unauthenticated anonymous PKINIT plus encrypted
challenge would carry some of the advantages of SPAKE preauth.  But
there are a lot of missing pieces for clients without keytabs:

* The MIT krb5 client only supports KDC-authenticated anonymous PKINIT
at this time.  That could change, but it would carry risks by
complicating the client security model (e.g. we need to make sure not to
do FAST OTP over the resulting channel).

* The get_in_tkt stack would need to be augmented to try anonymous
PKINIT FAST automatically.  At the moment the user (or other external
machinery) has to manually obtain anonymous tickets and then use those
as armor.

* Administrators have to turn on anonymous PKINIT; it's not on by
default.  To turn it on you have to generate a KDC certificate, even if
the client won't verify it.

* Anonymous PKINIT in MIT krb5 is slow right now because it only
supports integer DH.  It also increases the attack surface on the KDC
significantly, because PKINIT is so complicated.

Other implementations are in different states (e.g. Heimdal has
supported ECDH PKINIT for many years), but I think have most of the same
those missing pieces and some additional ones as well.

SPAKE preauth doesn't currently exist, which is also a big missing
piece.  The advantages are that:

1. It's just a preauth mech.  It provides all of its advantages without
requiring any difficult changes to other parts of the stack.  (It does
require some non-difficult changes discussed in RFC 6113: supplying a
single ETYPE-INFO2 value, cookie support within the KDC preauth
framework, and MORE_PREAUTH_DATA_NEEDED support in the client and KDC.)
 If it performs well enough, it could become available and used by
default, supplanting encrypted timestamp.

2. It supports second factor features which aren't currently supported
by any standard.

> this departure is necessary is because of the above reasons.

Agreed.  RFC 6113 states that "Mechanism designers should design FAST
factors, instead of new pre-authentication mechanisms outside of FAST."
 We are going against that advice, and need to justify why.

(Of course nothing prevents SPAKE from being used as a FAST factor, and
it builds on RFC 6113 features.)

---

From: Nathaniel McCallum <[email-masked]>
Date: Thu, 30 Apr 2015 12:12:55 -0400

> http://www.ietf.org/id/draft-mccallum-kitten-krb-spake-preauth-00.txt

After getting many great comments from everyone, I decided to setup a
git repo to track my changes. Pull requests are welcome!

https://github.com/npmccallum/ietf

Nathaniel

PS - This also include the other drafts I have recently published.
Pull requests are welcome on these as well.

---

From: Nico Williams <[email-masked]>
Date: Thu, 30 Apr 2015 11:38:19 -0500

> synchronization is off, extra messages are sent. I think this

Extra round trips != fragility.  Fragility -> sometimes clients fail.

In this case the extra round trips are merely sub-optimal behavior that
users mostly don't notice, and which is greatly amortized anyways.

Clients can sometimes fail, but only if they don't implement clock skew
correction based on the timestamps in KRB-ERROR PDUs.  Implementation
issues don't really count for this argument unless implementation is
particularly difficult, which it's not.

> think it is worth mentioning however.

But it's not really a motivating factor for this work, is it?  It's just
icing on the cake.

> it. If such is not needed in this document, I can remove it.

To me it reads like an explanation by the author to a younger version of
the author :)  Especially given the focus on DH.  One can construct key
agreement protocols with PFS using RSA instead of DH, so the focus on DH
strikes me as accidental rather than fundamental.  (Heck, I think I can
construct EKE-like ZKPPs out of RSA as well.)

I'd rather that the properties of a PAKE be listed and references to DH
be left out in this section.

> [...]

OK, this is what I was looking for, thanks.

Nico
--

---

From: Nathaniel McCallum <[email-masked]>
Date: Thu, 30 Apr 2015 12:52:53 -0400

> But it's not really a motivating factor for this work, is it?  It's 

Agreed. I'll de-emphasize it in the next edition.

> > >     - is resistant to off-line dictionary attacks by 
> > > eavesdroppers, 
> > > even
> > >       (In an augmented PAKE the server stores a verifier, but 
> > > you're 
> > > not

Fair enough. My concern was to provide a good introduction to PAKE for
those unfamiliar with it. But if we aren't worried about such, then we
can just list the properties and move on.

> OK, this is what I was looking for, thanks.

Glad we're on the same page now. I look forward to your
comments/patches. :)

Nathaniel