Subject: [kitten] Kerberos preauth negotiation techniques

From: Greg Hudson <[email-masked]>
Date: Wed, 11 Feb 2015 13:35:58 -0500

Nathaniel McCallum has been working on a Kerberos PAKE preauth mechanism
(https://github.com/npmccallum/krb5-pake) which also supports a second
factor value.  Although there are many variables to how this mechanism
could wind up working, we know that the exchange will end with the
client sending a key confirmation and encrypted second factor (perhaps
in addition to a client public value), and the KDC either issuing a
ticket or an error.  If the KDC implementation is careful enough about
operating in constant time, the client doesn't find out whether it was
wrong about the key or the second factor value.

If the PAKE mechanism only requires two hops (as in SPAKE2), then we
could theoretically fit the whole exchange into the same number of round
trips as traditional encrypted timestamp:

    C: unauthenticated AS-REQ
    K: PREAUTH_REQUIRED (KDC public value in hint)
    C: AS-REQ (client public value, key confirmation, second factor)
    K: ticket or error

Naively putting a KDC public value into a hint list isn't a great
strategy for a preauth mech.  Even with a modern group like Curve25519
the public value will take non-negligible time to compute and
non-negligible space to transport.  If there were many preauth mechs
making this choice, the hint list would become large and expensive to
produce.  Also, if there is any kind of sub-negotiation within the
preauth mech (curve choice, PAKE algorithm choice, etc.), this approach
doesn't work.

I think there are basically three options:

1. Add a third round trip.  The exchange could look like this:

    C: unauthenticated AS-REQ
    K: PREAUTH_REQUIRED (empty hint)
    C: AS-REQ (client sub-negotiation parameters)
    K: MORE_PREAUTH_DATA_REQUIRED (KDC parameter choice, KDC public value)
    C: AS-REQ (client public value, key confirmation, second factor)
    K: ticket or error

Other variations are possible--the KDC hint list could contain
sub-negotiation parameters to be interpreted by the client, and the
second client AS-REQ could contain a client public value for three-hop
PAKE mechanisms.  The point is that the KDC doesn't put much work or
data into its hint list, and receives sub-negotiation parameters before
it generates a public value.

This approach fits solidly within the confines of RFC 6113 and (at least
with an empty KDC hint) postpones almost all of the cost of the mech
until after it is agreed upon by the client and KDC.  The only real
disadvantage is the extra latency of a third round trip.

2. Use pseudo-enctypes:

    C: unauthenticated AS-REQ (pseudo-enctypes in etype field)
    K: PREAUTH_REQUIRED (KDC public value in hint)
    C: AS-REQ (client public value, key confirmation, second factor)
    K: ticket or error

Each pseudo-enctype indicates client support for the preauth mech and
particular sub-negotiation parameters.  Because the KDC knows the client
supports the mech, it can suppress other preauth mechs in the hint list
and generate a public value known to be compatible with the client's
capabilities.

There is some half-hearted precedent for this idea.  RFC 4556 specifies
some PKINIT pseudo-enctypes to indicate CMS algorithm support, but then
immediately deprecates the practice and recommends the use of OIDs
instead.

Pseudo-enctypes are compact, and there is already support for them in
the MIT krb5 client preauth framework because of PKINIT.  However, this
approach requires that every sub-negotiation parameter value be
registered within the IANA Kerberos enctype registry; one can't use OIDs
to name curves, for instance.  And some people find it inelegant to use
the enctype number space for purposes other than actual RFC 3961
encryption types.

3. Use client preauth hints:

    C: unauthenticate AS-REQ (padata containing sub-negotiation params)
    K: PREAUTH_REQUIRED (KDC public value in hint)
    C: AS-REQ (client public value, key confirmation, second factor)
    K: ticket or error

In this strategy, the client includes an unsolicited padata value in its
initial request which indicates support for the mechanism and contains
sub-negotiation parameters.  RFC 6113 does not currently envision this
kind of client hint as part of preauth negotiation, so we would have to
extend it.  Clients would have to retry without hints if an older KDC
rejects the unauthenticated AS-REQ with PREAUTH_FAILED; this is already
required for clients implementing RFC 6806 FAST negotiation.

The client hint value will inevitably be larger than a few
pseudo-enctypes would be, especially if the sub-negotiation parameters
could include multiple OID values.  If several preauth mechanisms come
into the world using non-trivial client hints, initial AS-REQs could
grow larger than we might like.  Otherwise, this approach has similar
properties as option 2, but without requiring any abuse of the enctype
number space.

---

As I write this, I am leaning towards option 1.  My only reservation is
that I would like this mechanism to eventually displace encrypted
timestamp in the Kerberos ecosystem, and it might be a shame to make
essentially all password-based initial Kerberos authentications take
three round trips.  What are other people's thoughts?

---

From: Simo Sorce <[email-masked]>
Date: Wed, 11 Feb 2015 14:01:12 -0500

> three round trips.  What are other people's thoughts?

I strongly prefer 3.
Clients can easily limit the amount of data they will send so I am not
concerned that the AS_REQ will grow too much.

Simo.

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

---

From: Benjamin Kaduk <[email-masked]>
Date: Thu, 12 Feb 2015 15:33:59 -0500 (EST)

> three round trips.  What are other people's thoughts?

I agree that (1) is the cleanest in terms of fitting into the existing
structures.  But, practical considerations of reducing the round-trip
count may end up causing us to go with (3), which is also fairly elegant
but has the wart of needing to update RFC 6113.  I generally like to avoid
changing existing specs that had a lot of thought go into them, but
perhaps this is a minor enough change that it would be acceptable.  Do you
want to write a little bit about the existing pa-hint and how this new
usage would differ from the current standardized usage?

-Ben

---

From: Nathaniel McCallum <[email-masked]>
Date: Tue, 17 Feb 2015 11:14:35 -0500

On Wed, 2015-02-11 at 13:35 -0500, Greg Hudson wrote:
> Nathaniel McCallum has been working on a Kerberos PAKE preauth 
> mechanism (https://github.com/npmccallum/krb5-pake) which also 
> supports a second factor value.  Although there are many variables 
> to how this mechanism could wind up working, we know that the 
> exchange will end with the client sending a key confirmation and 
> encrypted second factor (perhaps in addition to a client public 
> value), and the KDC either issuing a ticket or an error.  If the KDC 
> implementation is careful enough about operating in constant time, 
> the client doesn't find out whether it was wrong about the key or 
> the second factor value.
> 
> could theoretically fit the whole exchange into the same number of 
> round trips as traditional encrypted timestamp:
> 
> strategy for a preauth mech.  Even with a modern group like 
> Curve25519 the public value will take non-negligible time to compute 
> and non-negligible space to transport.  If there were many preauth 
> mechs making this choice, the hint list would become large and 
> expensive to produce.  Also, if there is any kind of sub-negotiation 
> within the preauth mech (curve choice, PAKE algorithm choice, etc.), 
> this approach doesn't work.
> 
> Other variations are possible--the KDC hint list could contain sub-
> negotiation parameters to be interpreted by the client, and the 
> second client AS-REQ could contain a client public value for three-
> hop PAKE mechanisms.  The point is that the KDC doesn't put much 
> work or data into its hint list, and receives sub-negotiation 
> parameters before it generates a public value.
> 
> This approach fits solidly within the confines of RFC 6113 and (at 
> least with an empty KDC hint) postpones almost all of the cost of 
> the mech until after it is agreed upon by the client and KDC.  The 
> only real disadvantage is the extra latency of a third round trip.
> 
> 2. Use pseudo-enctypes:
> 
> Each pseudo-enctype indicates client support for the preauth mech 
> and particular sub-negotiation parameters.  Because the KDC knows 
> the client supports the mech, it can suppress other preauth mechs in 
> the hint list and generate a public value known to be compatible 
> with the client's capabilities.
> 
> There is some half-hearted precedent for this idea.  RFC 4556 
> specifies some PKINIT pseudo-enctypes to indicate CMS algorithm 
> support, but then immediately deprecates the practice and recommends 
> the use of OIDs instead.
> 
> Pseudo-enctypes are compact, and there is already support for them 
> in the MIT krb5 client preauth framework because of PKINIT.  
> However, this approach requires that every sub-negotiation parameter 
> value be registered within the IANA Kerberos enctype registry; one 
> can't use OIDs to name curves, for instance.  And some people find 
> it inelegant to use the enctype number space for purposes other than 
> actual RFC 3961 encryption types.
> 
> In this strategy, the client includes an unsolicited padata value in 
> its initial request which indicates support for the mechanism and 
> contains sub-negotiation parameters.  RFC 6113 does not currently 
> envision this kind of client hint as part of preauth negotiation, so 
> we would have to extend it.  Clients would have to retry without 
> hints if an older KDC rejects the unauthenticated AS-REQ with 
> PREAUTH_FAILED; this is already required for clients implementing 
> RFC 6806 FAST negotiation.
> 
> The client hint value will inevitably be larger than a few pseudo-
> enctypes would be, especially if the sub-negotiation parameters 
> could include multiple OID values.  If several preauth mechanisms 
> come into the world using non-trivial client hints, initial AS-REQs 
> could grow larger than we might like.  Otherwise, this approach has 
> similar properties as option 2, but without requiring any abuse of 
> the enctype number space.
> 
> ---
> 
> As I write this, I am leaning towards option 1.  My only reservation 
> is that I would like this mechanism to eventually displace encrypted 

I see 1 and 3 as the only good options. Having to register group 
parameters instead of using OIDs is a deal-breaker in my book.

1 and 3 are also compatible workflows. In 3, the first AS-REQ is 
exactly the same padata as the second AS-REQ in 1. That is to say, 3 
is an optimization of 1 where the first round-trip of 1, which 
includes no meaningful data, is simply not used. Put another way, 3 is 
just 1 with optimistic preauth.

So a KDC can actually implement both 1 and 3 simultaneously. If the 
KDC does not receive the padata in the first step (option 3), it 
generates the empty hint (option 1). Otherwise, 1 and 3 are identical. 
Only one thing differs: PREAUTH_REQUIRED or 
MORE_PREAUTH_DATA_REQUIRED. Can we just always use the latter error?

The problem, as Greg rightly notes, is that a client cannot know if 
the KDC supports the PAKE preauth mech and will have to handle 
PREAUTH_FAILED properly.

After thinking about this (and implementing it), I think the best way 
forward is 1 with 3 as an optional optimization. The KDC should always 
support both 1 and 3; adding support for (optional) 3 should be 
trivial. Clients should choose whether or not to support 3 based on 
complexity of implementation; 3 can always be added later as an 
optimization.

Nathaniel

---

From: Nico Williams <[email-masked]>
Date: Tue, 17 Feb 2015 11:27:52 -0600

> preauth mech (curve choice, PAKE algorithm choice, etc.), this approach

Agreed.

(For some two-round-trip PAKEs the amount of work to do on the first go
could be negligible, but nonetheless, the remaining points apply.)

> 1. Add a third round trip.  The exchange could look like this:

This has the advantage of having a return routability check built-in so
that the AS doesn't spend too many resources computing public values for
a client that isn't there to complete the exchange.

At a minimum, an over-worked AS should have an option to force the
additional round-trip.

> immediately deprecates the practice and recommends the use of OIDs

Not just that, but this approach has been used to extend other
protocols (e.g., TLS).

> the enctype number space for purposes other than actual RFC 3961

I don't mind this too much.

A problem with (2) is that if we ever need more than "which PAKEs does
the client support" hints, then (2) will be insufficient.  Or perhaps
we'll have a bit of a cartesian explosion (PAKEs x curves).  Or perhaps
we'll end up with many pseudo-enctypes for hinting (one set for PAKEs,
another for curves, ...).

> required for clients implementing RFC 6806 FAST negotiation.

I don't mind this either.  It is decidedly more elegant.  The
1-round-trip penalty when talking to older KDCs will vanish when those
are upgraded.

> pseudo-enctypes would be, especially if the sub-negotiation parameters

I don't think this need be inevitable.  See comment above about
cartesian explosions in (2).

> could include multiple OID values.  If several preauth mechanisms come

If we use OIDs for PAKEs and curves, then yeah, the hints in (3) could
get large!  :)  (This is a bad joke about space inefficiency of OIDs.)

We've talked about using relative OIDs, but the problem with those (or
integers, bits in a bit string, ...) is that they really force use to
have a registry.

> properties as option 2, but without requiring any abuse of the enctype

If the only things the client has to send a priori were a set of PAKEs
and a set of curves, then the hints can be fairly space efficient.  If
we need a cartesian explosion (e.g., if some PAKEs are not orthogonal to
the choice of curve) then hints have to get large in the long run
anyways.

> three round trips.  What are other people's thoughts?

Why not (3)?  It too will cost 3 round trips _at first_, but will
eventually improve to 2 round trips as KDCs are upgraded.  Seems like a
win to me.

I don't mind (2) much either, but on the whole I prefer (3), mostly
because it will allow us to make registration optional (if we use OIDs)
and because it will allow the hint data structure to evolve in ways that
pseudo-enctypes simply can't.

Nico
--

---

From: Nico Williams <[email-masked]>
Date: Tue, 17 Feb 2015 11:30:17 -0600

> concerned that the AS_REQ will grow too much.

Ah, because they can always try multiple times, but with (1) each
additional attempt costs an additional round-trip, thus making any
trade-off of request size to round trip count seem much less worthwhile.

Nico
--

---

From: Nico Williams <[email-masked]>
Date: Tue, 17 Feb 2015 11:37:13 -0600

> parameters instead of using OIDs is a deal-breaker in my book.

I also prefer not to have to add registration of groups.  I'm not sure
that I want to have any support for negotiable group parameters though,
if that's what you meant.  I'd rather have well-known curves (groups)
suitable for discrete codepoint assignments regardless of whether we
have/need a registry.

However, a single popular use case for negotiable groups will make (2)
utterly inapplicable, and that's the best case for not considering (2),
IMO.

On the whole I prefer (3).  I agree that it's an optimization that could
come later though.  But it's also an optimization that clients could
implement immediately (with the fallback penalty); it's only the AS
where more work is needed.

Nico
--

---

From: Nathaniel McCallum <[email-masked]>
Date: Tue, 17 Feb 2015 12:58:19 -0500

On Tue, 2015-02-17 at 11:37 -0600, Nico Williams wrote:
> I also prefer not to have to add registration of groups.  I'm not 
> sure that I want to have any support for negotiable group parameters 
> though, if that's what you meant.  I'd rather have well-known curves 
> (groups) suitable for discrete codepoint assignments regardless of 
> whether we have/need a registry.

That was not what I meant. I meant parameters of the exchange. Current 
parameters are:
* PAKE method (currently: SPAKE and JPAKE; needs registration)
* Group (currently: only standardized elliptic curve groups)
* Hash (currently: MD5, SHA1, SHA2-*)

Currently, I advertise these as:

PAKEInfo ::= SEQUENCE {
    ptypes SEQUENCE (SIZE(1..MAX)) OF Int32,
    supports SEQUENCE (SIZE(1..MAX)) OF PAKESupport,
    ...
}

PAKESupport ::= SEQUENCE {
    etype Int32,
    groups SEQUENCE (SIZE(1..MAX)) OF OBJECT IDENTIFIER,
    hashes SEQUENCE (SIZE(1..MAX)) OF OBJECT IDENTIFIER,
    ...
}

The drawback to this approach is that groups or hashes supported by 
multiple enctypes get listed multiple times. However, this also 
captures that some groups/hashes are only usable for some enctypes. 
Generally this relates to key size and protects large keys from being 
generated by small curves.

I'm open to alternatives.

> However, a single popular use case for negotiable groups will make 
> (2) utterly inapplicable, and that's the best case for not 
> considering (2), IMO.

+1

> On the whole I prefer (3).  I agree that it's an optimization that 
> could come later though.  But it's also an optimization that clients 
> could implement immediately (with the fallback penalty); it's only 
> the AS where more work is needed.

Having implemented it, the AS side is easy. The client is harder. That 
is at least the case on the MIT codebase. I suspect it is true of all 
implementations.

Nathaniel

---

From: Nico Williams <[email-masked]>
Date: Tue, 17 Feb 2015 13:58:19 -0600

> * Hash (currently: MD5, SHA1, SHA2-*)

[I covered that elsewhere.]  Assuming these are all orthogonal (they
should be), then pseudo-enctypes work, but need a registry.  OIDs are
much better (though larger) because we can then outsource the registry
to CFRG and friends.

>     hashes SEQUENCE (SIZE(1..MAX)) OF OBJECT IDENTIFIER,

Why is etype not a sequence?

> captures that some groups/hashes are only usable for some enctypes. 

If all of these are orthogonal (they should be) then we should just send
sequences (sets, really, but ASN.1 SEQUENCEs) of enctypes, PAKEs, groups
(curves; we're not likely to bother with non-EC DH, right?), and hash
functions (and/or KDF??).

> generated by small curves.

I don't see why that should be a problem.  It should be possible to
generate a key for AES-256 from a 128-bit shared secret.  That's one
reason for PRFs/KDFs: so we can resolve such impedance mismatches.

> is at least the case on the MIT codebase. I suspect it is true of all 

Interesting.  All the better.  Let's go with (3), with the optimization
being optional.  Some clients will do (1), and that's OK.

Nico
--

---

From: Nathaniel McCallum <[email-masked]>
Date: Tue, 17 Feb 2015 16:40:00 -0500

On Tue, 2015-02-17 at 13:58 -0600, Nico Williams wrote:
> > > > I see 1 and 3 as the only good options. Having to register 
> > > > group parameters instead of using OIDs is a deal-breaker in my 
> > > > book.
> > > 
> > > I also prefer not to have to add registration of groups.  I'm 
> > > not sure that I want to have any support for negotiable group 
> > > parameters though, if that's what you meant.  I'd rather have 
> > > well-known curves (groups) suitable for discrete codepoint 
> > > assignments regardless of whether we have/need a registry.
> > 
> > That was not what I meant. I meant parameters of the exchange. 
> > Current parameters are:
> should be), then pseudo-enctypes work, but need a registry.  OIDs 
> are much better (though larger) because we can then outsource the 
> registry to CFRG and friends.

In the current code, the actual key is generated by a hash of:
1. the shared EC point: K
2. the client principal
3. the server principal
4. all padata sent or received

Currently, we do not truncate hashes to fit key size. So the hash 
output must exactly match the expected size of the key. This is the 
reason MD5 is enabled (to support 128bit keys). This is not a long 
term plan. However, we should not allow, for instance, SHA1 to be used 
to generate a 256bit key.

Given the above, hashes are supported per etype.

I currently do something similar for the groups. An elliptic curve 
group can only be used for an etype if its field size is >=1.75x the 
key size. For example, P-224 can be used for generating 128bit keys, 
but not for 256bit keys.

Given the above, groups are supported per etype.

> Why is etype not a sequence?

Because this contains the lists of supported groups and hashes for 
that specific etype.

> > The drawback to this approach is that groups or hashes supported 
> > by multiple enctypes get listed multiple times. However, this also 
> If all of these are orthogonal (they should be) then we should just 
> send sequences (sets, really, but ASN.1 SEQUENCEs) of enctypes, 
> PAKEs, groups (curves; we're not likely to bother with non-EC DH, 
> right?), and hash functions (and/or KDF??).

We don't need to send enctypes. This is already sent in etypes.

Having them all be orthogonal is how I originally designed it. But I 
changed it given the above considerations. Small hashes/ECs should not 
be used to generate larger keys.

> > Generally this relates to key size and protects large keys from 
> > being generated by small curves.
> 

What we can do and what we should do are different things. We can make 
large keys from small seeds. But I think allowing this makes for 
unclear security situations. I would prefer limiting the parameters 
for an etype to only those which do not degrade the security 
expectations of that etype.

> > > On the whole I prefer (3).  I agree that it's an optimization 
> > > that could come later though.  But it's also an optimization 
> > > that clients could implement immediately (with the fallback 
> > > penalty); it's only the AS where more work is needed.
> > 
> > Having implemented it, the AS side is easy. The client is harder. 
> > That is at least the case on the MIT codebase. I suspect it is 
> > true of all implementations.
> 
> Interesting.  All the better.  Let's go with (3), with the 
> optimization being optional.  Some clients will do (1), and that's 
> OK.

I think you mean 1 with the optimization (3) being optional. I only 
wish to add that it should be optional for clients but required for 
servers.

Nathaniel

---

From: Simo Sorce <[email-masked]>
Date: Wed, 18 Feb 2015 09:03:36 -0500

> 1. the shared EC point: K
I wonder ^^^ if this is problematic when canonicalization is requested ?

Simo.

> _______________________________________________
> Kitten mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/kitten

---

From: Nathaniel McCallum <[email-masked]>
Date: Wed, 18 Feb 2015 09:22:40 -0500

On Wed, 2015-02-18 at 09:03 -0500, Simo Sorce wrote:
> > > > > > group parameters instead of using OIDs is a deal-breaker 
> > > > > > in my book.
> > > > > 
> > > > > I also prefer not to have to add registration of groups.  
> > > > > I'm not sure that I want to have any support for negotiable 
> > > > > group parameters though, if that's what you meant.  I'd 
> > > > > rather have well-known curves (groups) suitable for discrete 
> > > > > codepoint
> > > [I covered that elsewhere.]  Assuming these are all orthogonal 
> > > (they should be), then pseudo-enctypes work, but need a 
> > > registry.  OIDs are much better (though larger) because we can 
> > > then outsource the registry to CFRG and friends.
> > 
> > In the current code, the actual key is generated by a hash of: 1. 
> > the shared EC point: K
> > 2. the client principal

I'm not sure. I hash whatever is in krb5_kdc_req.client.

> > 4. all padata sent or received

I forgot to mention:
5. The long term key used in the PAKE

> > output must exactly match the expected size of the key. This is 
> > the reason MD5 is enabled (to support 128bit keys). This is not a 
> > long term plan. However, we should not allow, for instance, SHA1 
> > to be used to generate a 256bit key.
> > 
> > group can only be used for an etype if its field size is >=1.75x 
> > the key size. For example, P-224 can be used for generating 128bit 
> > keys, but not for 256bit keys.
> > 
> > > > The drawback to this approach is that groups or hashes 
> > > > supported by multiple enctypes get listed multiple times. 
> > > > However, this also captures that some groups/hashes are only 
> > > > usable for some enctypes.
> > > 
> > > If all of these are orthogonal (they should be) then we should 
> > > just send sequences (sets, really, but ASN.1 SEQUENCEs) of 
> > > enctypes, PAKEs, groups (curves; we're not likely to bother with 
> > > non-EC DH, right?), and hash functions (and/or KDF??).
> > 
> > Having them all be orthogonal is how I originally designed it. But 
> > I changed it given the above considerations. Small hashes/ECs 
> > should not be used to generate larger keys.
> > 
> > > > Generally this relates to key size and protects large keys 
> > > > from being generated by small curves.
> > > 
> > > I don't see why that should be a problem.  It should be possible 
> > > to generate a key for AES-256 from a 128-bit shared secret.  
> > > That's one reason for PRFs/KDFs: so we can resolve such 
> > > impedance mismatches.
> > 
> > What we can do and what we should do are different things. We can 
> > make large keys from small seeds. But I think allowing this makes 
> > for unclear security situations. I would prefer limiting the 
> > parameters for an etype to only those which do not degrade the 
> > security expectations of that etype.
> > 
> > > > > On the whole I prefer (3).  I agree that it's an 
> > > > > optimization that could come later though.  But it's also an 
> > > > > optimization
> > > > Having implemented it, the AS side is easy. The client is 
> > > > harder. That is at least the case on the MIT codebase. I 
> > > > suspect it is true of all implementations.
> > > 
> > > optimization being optional.  Some clients will do (1), and 
> > > that's OK.
> > 
> > I think you mean 1 with the optimization (3) being optional. I 
> > only wish to add that it should be optional for clients but 
> > required for servers.
> > 
> > Nathaniel
> >

---

From: Simo Sorce <[email-masked]>
Date: Wed, 18 Feb 2015 09:35:32 -0500

> I'm not sure. I hash whatever is in krb5_kdc_req.client.

Ok, as long as client and server are using the same name it is fine, but
it should probably be spelled out clearly that this is not the canonical
principal name but whatever name the client used.

> 5. The long term key used in the PAKE

Thanks, I thought something was amiss here :)

Simo.

---

From: Nathaniel McCallum <[email-masked]>
Date: Wed, 18 Feb 2015 09:37:39 -0500

On Wed, 2015-02-18 at 09:35 -0500, Simo Sorce wrote:
> > > > > > > On Tue, Feb 17, 2015 at 11:14:35AM -0500, Nathaniel 
> > > > > > > McCallum
> > > > > > > wrote:
> > > > > > That was not what I meant. I meant parameters of the 
> > > > > > exchange. Current parameters are:
> > > > > [I covered that elsewhere.]  Assuming these are all 
> > > > > orthogonal (they should be), then pseudo-enctypes work, but 
> > > > > need a
> > > > > registry.  OIDs are much better (though larger) because we 
> > > > > can then outsource the registry to CFRG and friends.
> > > > 
> Ok, as long as client and server are using the same name it is fine, 
> but it should probably be spelled out clearly that this is not the 
> canonical principal name but whatever name the client used.
> 
> > > > 3. the server principal

Two private things go into the final key hash:
1. the shared EC point derived from the key exchange: K
2. the long term key

Successfully attacking #1 breaks either the PAKE method or the DDH 
assumption.

Nathaniel

---

From: Nico Williams <[email-masked]>
Date: Wed, 18 Feb 2015 10:28:00 -0600

> to generate a 256bit key.

Requiring that hash function outputs match enctype key sizes is
terrible.  Use a KDF, it's what it's there for; Kerberos has one.

> Given the above, hashes are supported per etype.

Don't do it that way :)

> Because this contains the lists of supported groups and hashes for 

See above and preceding reply.

> We don't need to send enctypes. This is already sent in etypes.

True.

> be used to generate larger keys.

That's not right.  Smaller amounts of entropy can be used to generate
larger keys.  We do it all the time.  It's what KDFs are for.

Granted, one should not use *too* small an amount of entropy, but this
is about setting a proper security floor.

The client (and the AS) should set a security floor, say, 128-bit,
192-bit, or 256-bit.  It should probably also set a ceiling (since we
have no ciphers stronger than 256-bit, there's no point using groups at
much higher security levels).

Above the security floor, anything goes.  Use a KDF to overcome
impedance mismatches.

> wish to add that it should be optional for clients but required for 

Sure.

Nico
--

---

From: Benjamin Kaduk <[email-masked]>
Date: Wed, 18 Feb 2015 13:34:16 -0500 (EST)

> MORE_PREAUTH_DATA_REQUIRED. Can we just always use the latter error?

It is safe to use MORE_PREAUTH_DATA_REQUIRED since we can document that
support for that error is a requirement of the new preauth mechanism.

Determining whether it is acceptable to ask for MORE_PREAUTH in response
to the initial AS-REQ (including the hints which we are calling optimistic
preauth here), as opposed to just PREAUTH_REQUIRED, will probably require
a close reading of the relevant RFCs.

> complexity of implementation; 3 can always be added later as an

That does seem like the best way forward, as the rest of the thread is
concluding.

-Ben

---

From: Greg Hudson <[email-masked]>
Date: Wed, 18 Feb 2015 15:16:29 -0500

I wrote (in summary):
>> 1. Add a third round trip
>> 2. Use pseudo-enctypes
>> 3. Use client preauth hints

> just 1 with optimistic preauth.

That's an interesting way of looking at things.  It means we wouldn't
have to amend RFC 6113, although we might be bending it a bit.  Here are
some considerations, which all seem manageable:

* Traditionally, optimistic preauth is only done with some prior
knowledge of what the KDC wants (see RFC 6113 section 2.3 paragraph 1).
 To get down to two round trips in the common case, an AS client  needs
to do optimistic PA-PAKE by default.

* Of course PA-PAKE would need to be specified such that the first
client message requires no knowledge from the KDC.  This is pretty
simple; the first client message can be defined to contain only
sub-negotiation parameters.

* Most KDC implementations will ignore the client's PA-PAKE padata if
they don't implement it, and respond with PREAUTH_REQUIRED with
METHOD-DATA.  Some older KDCs (like MIT krb5 pre-1.7) will instead
respond with PREAUTH_FAILED.  Clients already need to deal with this
behavior if they implement RFC 6112 encrypted padata negotiation or any
similar extension, so this is not really a concern.

* An optimistic PA-PAKE message should be cheap to compute (it's just
parameters), but is still wasted bytes if the exchange winds up settling
on a different mechanism or not using preauth at all.  The more
compactly we can represent client parameters, the less bandwidth we will
waste and the fewer problems we will have with AS-REQs exceeding UDP
limitations.

* Can a client optimistically preauthenticate with multiple mechanisms?
 RFC 6113 doesn't really say either way.  Without going into detail on
the arguments pro and con:

  - If we assume no, then a client which does optimistic PA-PAKE by
default can't do the same thing with any other mechanism.  This could be
a reasonable choice; the client implementation could always choose to
drop back to three round trips for PA-PAKE if it wants to do optimistic
PA-FUTURE-AWESOME by default in the future.

  - If we assume yes, then a client which does optimistic PA-PAKE is
still privileging that mechanism by choosing to spend bandwith on it
before it is negotiated.  But it wouldn't necessarily have to exclude
other mechanisms from doing the same thing.

---

From: Nico Williams <[email-masked]>
Date: Wed, 18 Feb 2015 14:43:44 -0600

> to do optimistic PA-PAKE by default.

When the client has only one pre-auth it's willing to do then it can be
optimistic.  That doesn't seem terribly likely in many cases, but for
environments where 2fa is used for protecting some resources and not
others, then it could be clear at AS-REQ time that the client only wants
to do 2fa.

Clients can also tell -sometimes- when they have credentials for
PKINIT.  And they can learn and cache -or have configured- whether a
realm's KDCs support FAST for protecting PA-ENC-TIMESTAMP, and so on.
It may not be such a stretch that a client will have just one pre-auth
method that it's willing to use in some cases.

> sub-negotiation parameters.

Yea, we're already there as to this proposal.

> similar extension, so this is not really a concern.

Good point.

> waste and the fewer problems we will have with AS-REQs exceeding UDP

We can greatly "compress" it by using bit sets (which could be
compressed if there are many contiguous zero bits in the bit string).

The trade-off is requiring a registry.  For PAKEs and groups, an OID
would do just fine, or we could use an existing (or upcoming) registry.

A middle of the road proposal would be to use a bit set for registered
PAKEs and groups and an optional set (sequence) of OIDs for all others.

But all this to save a bit of space?  Before we go there we should
determine that this really is a problem we need to address.

> the arguments pro and con:

A separate update to RFC6113 about this would be nice.

> PA-FUTURE-AWESOME by default in the future.

Well...  See above.  Also, a client could be somewhat abusive and send N
single-preauth AS-REQs concurrently, hoping one of them will succeed.

> other mechanisms from doing the same thing.

Yes, but hopefully the client knows from context that it will need this
PA method.

---

From: Nathaniel McCallum <[email-masked]>
Date: Mon, 23 Feb 2015 15:13:42 -0500

On Wed, 2015-02-18 at 14:43 -0600, Nico Williams wrote:
> > > exactly the same padata as the second AS-REQ in 1. That is to 
> > > say, 3 is an optimization of 1 where the first round-trip of 1, 
> > > which includes no meaningful data, is simply not used. Put 
> > > another way, 3 is just 1 with optimistic preauth.
> > 
> > That's an interesting way of looking at things.  It means we 
> > wouldn't have to amend RFC 6113, although we might be bending it a 
> > bit.  Here are some considerations, which all seem manageable:
> > 
> When the client has only one pre-auth it's willing to do then it can 
> be optimistic.  That doesn't seem terribly likely in many cases, but 
> for environments where 2fa is used for protecting some resources and 
> not others, then it could be clear at AS-REQ time that the client 
> only wants to do 2fa.
> 
> realm's KDCs support FAST for protecting PA-ENC-TIMESTAMP, and so 
> on. It may not be such a stretch that a client will have just one 
> pre-auth method that it's willing to use in some cases.
> 
> > respond with PREAUTH_FAILED.  Clients already need to deal with 
> > this behavior if they implement RFC 6112 encrypted padata 
> > negotiation or any similar extension, so this is not really a 
> > concern.
> 
> Good point.
> 
> > parameters), but is still wasted bytes if the exchange winds up 
> > settling on a different mechanism or not using preauth at all.  
> > The more compactly we can represent client parameters, the less 
> > bandwidth we will waste and the fewer problems we will have with 
> > AS-REQs exceeding UDP limitations.
> 
> A middle of the road proposal would be to use a bit set for 
> registered PAKEs and groups and an optional set (sequence) of OIDs 
> for all others.
> 

On the call last week there was a general consensus to move forward 
with SPAKE2 and not make PAKEs negotiable. SPAKE2 has all the 
properties we care about. It:
* has a formal security proof that is well regarded
* takes only a single roundtrip
* supports elliptic curves
* has wide deployment (via Chromium/Chrome)

We also had a general consensus that there is no need to negotiate 
hashes. There are three hash uses:
1. Transcript for message integrity
2. Key derivation
3. Key validation

For #1, we can just use the checksum method implicit in the enctype.

For #2, we can just use a KDF.

For #3, Greg had an idea, but I've since forgotten it and can't find 
it in my email. Greg, perhaps you can remind me?

Enctype negotiation is implicit from the existing exchange. This 
leaves only groups and second factors.

We also discussed making group negotiation have a note in the RFC 
about being careful regarding the number of groups exposed. I suspect 
sensible defaults will be:
* P-256
* P-384
* P-521
* Curve25519

OpenSSL does not support Curve25519 (yet) so it won't be offered in my 
implementation.

One reason I don't think it will be a problem is that no other data is 
sent in the group negotiation packet from the client to the server. 
The response from the server will contain just one group OID along 
with the public key and the 2FA negotiation parameters.

I suggest an empirical approach here. I'll be developing the RFC in 
parallel with the application itself. If we see this becoming a 
problem, we can address it at that time. I am open even to bit set 
negotiation if space becomes a serious concern. I would simply like to 
avoid a registry if it is not needed.

> > * Can a client optimistically preauthenticate with multiple > > mechanisms?
> > default can't do the same thing with any other mechanism.  This 
> > could be a reasonable choice; the client implementation could 
> > always choose to drop back to three round trips for PA-PAKE if it 
> > wants to do optimistic PA-FUTURE-AWESOME by default in the future.
> 
> Well...  See above.  Also, a client could be somewhat abusive and 
> send N single-preauth AS-REQs concurrently, hoping one of them will 
> succeed.
> 
> > still privileging that mechanism by choosing to spend bandwith on 
> > it before it is negotiated.  But it wouldn't necessarily have to 
> > exclude other mechanisms from doing the same thing.
> 
> Yes, but hopefully the client knows from context that it will need 
> this PA method.

---

From: Nico Williams <[email-masked]>
Date: Mon, 23 Feb 2015 15:12:11 -0600

> properties we care about. It:

Sure, a PAKE per-pre-auth.  If we want new PAKEs, we clone this
pre-auth, change the PAKE, give it a new number.

> it in my email. Greg, perhaps you can remind me?

Just use the enctype's authenticated encryption, natch.

> leaves only groups and second factors.

Making second factors negotiable is going to make the UI very fun :/
But it probably has to get done anyways.

Sure.

> OpenSSL does not support Curve25519 (yet) so it won't be offered in my

OpenSSL needs to add Curve25519 support ASAP (particularly now that
there is consensus in CFRG for Curve25519 as an RTI at the 128-bit
security level), but is a subject for a different list.

> One reason I don't think it will be a problem is that no other data is

What won't be a problem?

> avoid a registry if it is not needed.

Eh, if I understood correctly you're saying that the client shouldn't
send a list/set of groups.

Either the client does send a set/list of groups or the server must
return a PAKE message for each group.  The latter is not going to work
well for every PAKE.  Having the server choose one without any idea of
what the client supports just won't do.

Just have the client send a set (SEQUENCE) of OIDs.  If you really
hate the wire bloat, then send both, an enum bit string and a sequence
of OIDs, with the latter absent when only registered groups are
proposed and the former absent when no registered groups are proposed.

Nico
--

---

From: Nathaniel McCallum <[email-masked]>
Date: Mon, 23 Feb 2015 16:22:21 -0500

On Mon, 2015-02-23 at 15:12 -0600, Nico Williams wrote:
> On Mon, Feb 23, 2015 at 2:13 PM, Nathaniel McCallum <
> [email-masked]> wrote:
> > On the call last week there was a general consensus to move 
> > forward with SPAKE2 and not make PAKEs negotiable. SPAKE2 has all 
> > the
> Sure, a PAKE per-pre-auth.  If we want new PAKEs, we clone this pre-
> auth, change the PAKE, give it a new number.
> 
> > For #3, Greg had an idea, but I've since forgotten it and can't 
> > find it in my email. Greg, perhaps you can remind me?
> 
> > about being careful regarding the number of groups exposed. I 
> > suspect sensible defaults will be:
> > * P-256
> > * P-384
> > * P-521
> > * Curve25519
> 
> Sure.
> 
> > OpenSSL does not support Curve25519 (yet) so it won't be offered 
> > in my implementation.
> 

OID bloat.

> > sent in the group negotiation packet from the client to the 
> > server. The response from the server will contain just one group 
> > OID along with the public key and the 2FA negotiation parameters.
> > 
> > I suggest an empirical approach here. I'll be developing the RFC 
> > in parallel with the application itself. If we see this becoming a 
> > negotiation if space becomes a serious concern. I would simply 
> > like to avoid a registry if it is not needed.
> 
> Eh, if I understood correctly you're saying that the client 
> shouldn't send a list/set of groups.
> 
> return a PAKE message for each group.  The latter is not going to 
> work well for every PAKE.  Having the server choose one without any 
> idea of what the client supports just won't do.
> 
> hate the wire bloat, then send both, an enum bit string and a 
> sequence of OIDs, with the latter absent when only registered groups 
> are proposed and the former absent when no registered groups are 
> proposed.

No. I'm saying that the first message from the client to the server 
contains ONLY a SEQUENCE OF OBJECT IDENTIFIER. The reply contains the 
server's choice from that list, the public key from that chosen group, 
and 2FA parameters.

I'm saying the OID bloat isn't really a problem.

Nathaniel

---

From: Greg Hudson <[email-masked]>
Date: Mon, 23 Feb 2015 16:24:33 -0500

On 02/23/2015 03:13 PM, Nathaniel McCallum wrote:
> On the call last week there was a general consensus

Just to be clear on process, the call Nathaniel refers to here was not
an IETF conference call as described in
https://www.ietf.org/iesg/statement/interim-meetings.html
and did not establish a working group consensus.

> For #1, we can just use the checksum method implicit in the enctype.

The idea here (as I remember it) is to make an RFC 3961 keyed checksum,
at each step of the exchange, over the padata message and the previous
checksum, using the original client long-term key as the checksum key.
The final checksum is included in the derivation of the reply key.

> For #2, we can just use a KDF.

Specifically (as I remember it), we can do PRF+ (from either RFC 6112 or
RFC 4402bis), using the original client long-term key and a text input
containing the final transcript checksum, the point negotiated by the
PAKE algorithm, and the client and server principals.  The PRF+ output
can then be fed to the RFC 3961 random-to-key operation to produce the
reply key.

> it in my email. Greg, perhaps you can remind me?

I believe #3 refers to the client's proof of reply key possession at the
end of the PAKE exchange.  My idea was just to encrypt an empty string
if we don't have a second factor value to send.  (Alternatively we could
encrypt a timestamp; that should not really be necessary, as the KDC
cookie should be protected with a timestamp.)

> sensible defaults will be:

I would prefer an even more limited offering, but this decision can wait
until later.

---

From: Nico Williams <[email-masked]>
Date: Mon, 23 Feb 2015 15:37:54 -0600

> I'm saying the OID bloat isn't really a problem.

I agree.

BTW, if this were a GSS mech we might have a single mech OID for the
entire {enctype, PAKE, group} negotiation (but not second factor), and
for an IANA registry where one each of three arms of the OID
correspond to enctype, PAKE, group.

Here that would mean that the client advertises multiple PAs, and
would get us into the business of having a registry.

What you propose is fine.

Nico
--

---

From: Nathaniel McCallum <[email-masked]>
Date: Mon, 23 Feb 2015 16:40:25 -0500

On Mon, 2015-02-23 at 16:24 -0500, Greg Hudson wrote:
> Just to be clear on process, the call Nathaniel refers to here was 
> not an IETF conference call as described in
> The idea here (as I remember it) is to make an RFC 3961 keyed 
> checksum, at each step of the exchange, over the padata message and 
> the previous checksum, using the original client long-term key as 
> the checksum key. The final checksum is included in the derivation 
> of the reply key.
> 
> Specifically (as I remember it), we can do PRF+ (from either RFC 
> 6112 or RFC 4402bis), using the original client long-term key and a 
> text input containing the final transcript checksum, the point 
> negotiated by the PAKE algorithm, and the client and server 
> principals.  The PRF+ output can then be fed to the RFC 3961 random-
> to-key operation to produce the reply key.
> 
> I believe #3 refers to the client's proof of reply key possession at 
> the end of the PAKE exchange.  My idea was just to encrypt an empty 
> string if we don't have a second factor value to send.  
> (Alternatively we could encrypt a timestamp; that should not really 
> be necessary, as the KDC cookie should be protected with a 
> timestamp.)
> 
> I would prefer an even more limited offering, but this decision can 
> wait until later.

Thanks for all the clarifications! I agree with all of them.

---

From: Nico Williams <[email-masked]>
Date: Mon, 23 Feb 2015 15:41:22 -0600

> I would prefer an even more limited offering, but this decision can wait

I think two for the 128-bit level and one or two (preferably one) each
for the 192- and 256-bit levels.

Nico
--

---

From: Nathaniel McCallum <[email-masked]>
Date: Mon, 23 Feb 2015 16:59:46 -0500

On Mon, 2015-02-23 at 15:41 -0600, Nico Williams wrote:
> > > We also discussed making group negotiation have a note in the 
> > > RFC about being careful regarding the number of groups exposed. I
> > I would prefer an even more limited offering, but this decision 
> > can wait until later.
> 
> 
> I think two for the 128-bit level and one or two (preferably one) 
> each for the 192- and 256-bit levels.

I think this is an implementation detail that will change over time. :)

---

From: Nico Williams <[email-masked]>
Date: Mon, 23 Feb 2015 16:23:20 -0600

> I think this is an implementation detail that will change over time. :)

This is what we do here: we specify what must be implemented to get interop.

We can argue about whether some group that you can't implement _now_
should be required to implement.  We can argue about other groups that
others can't implement _now_.  We can't really have no
required-to-implement groups.  Well, we could, but not as an
Standards-Track RFC.

Nico
--