Subject: servers, passwords, and key generation

From: Ken Raeburn <[email-masked]>
Date: Tue, 29 Jul 2003 17:49:29 -0400

Larry Zhu (at Microsoft) and I have been talking about a possible 
problem, made more visible by some of the stuff we've been talking 
about on this list regarding AES.

Currently -- ignoring preauthentication for simplicity -- clients 
acquiring tickets generate encryption keys using a supplied password, a 
salt string and "opaque string-to-key parameters" (i.e., anything else) 
supplied by the KDC.  Note that I don't describe these as "optional" -- 
the specification of them in the KDC exchange is optional, but there 
are specified ways of getting the values to use if the KDC omits them; 
some value is always used.

For AES, the opaque parameters describe an iteration count to be passed 
to the PBKDF2 function.  We've discussed the issues of CPU time use for 
a legitimate client versus for an attacker trying a dictionary attack.  
Somewhere in that email, I believe, I suggested that randomizing the 
salt string at each password change would reduce the amount of 
pre-computed data the attacker could generate that would be valid 
across password changes.

Paul suggested that different iteration counts could be used depending 
on whether additional security is provided for the AS-REQ exchange, 
whether through preauthentication schemes, IPsec, or other means.  For 
example, the iteration count might be 40 if the host key is used to 
protect the exchange, or 40000 if it's sent entirely in the clear.  The 
KDC doesn't need to do lots of computation at AS-REQ processing time, 
if it computed multiple keys with different parameters when the 
password was set for the principal.

However, the AS-REQ exchange is currently the only standardized means 
of acquiring the salt and opaque parameters.

In the MIT implementation, a service is expected to have a "keytab" 
file that stores the keys for that principal, in binary form.

Some Microsoft server principals store passwords instead.  As I 
understand it, a ticket is sent to the server; the server looks up its 
password and generates a key of the appropriate type, so it can decrypt 
the ticket.  Since there is no exchange between the server and the KDC, 
there is no way to supply any additional parameters for key generation.

Under RC4, as described in draft-brezak-win2k-krb-rc4-04 (since 
expired), no string-to-key parameters are used, not even a salt string. 
  Hence the problems wouldn't have shown up under RC4.  But if we start 
actively making use of non-default salt strings and other parameters, 
with encryption types that actually use these parameters, we'll need a 
way of dealing with them.

MIT's code also has an option for adding a keytab entry given a 
password.  But it's not the normal way of dealing with service 
principals, and (at least in MIT's deployment) we generally use the 
default (principal-name-derived) salt string, and the ktutil program 
assumes the default salt string is used for this case.

I don't think it would be right to require that all service principals 
using passwords must use the salt string and other parameters that 
would be used if the KDC failed to provide them in an AS-REQ exchange.

Actually performing an AS-REQ exchange (and confirming that the 
resulting tickets are valid, of course) would give the service a set of 
parameters, and it might be practical to save away those parameters at 
password change time and re-use them later.  However, that doesn't 
really seem compatible with Paul's suggestion of having multiple sets 
of parameters.  (If the KDC stores two sets of parameters for the 
service principal, a "more secure" and a "less secure" set, which set 
will it use when that service principal is actually used as a service?)

There are a few possible approaches for dealing with this.

One is to turn off the multiple-parameter-set option for any principal 
that might be used as a service principal.  That only deals with the 
multiple-parameters problem; we'd still have to get the actual 
parameters by some other means, such as requesting tickets with the 
service principal used as the client principal.  In the MIT 
implementation, it's possible to configure a service principal with a 
flag indicating that it's not allowed to request any initial tickets, 
to prevent brute-force attacks in some circumstances.  It seems like a 
desirable feature to me, even if the very concern about it suggests 
that you may be using too weak an encryption system.  Maybe a new KDC 
exchange to get the parameters but explicitly not useable to get 
anything encrypted with the "client's" long-term key?

Another option might be to have the change-password protocol optionally 
supply the parameters that would be used when the principal is used as 
a service principal.  (This would be per encryption type, as the opaque 
parameters, at least, are defined per encryption type.)  I must 
confess, I haven't looked very much at the latest change-password 
draft, but I expect it wouldn't be too hard to add this, if people 
think it's the right approach.  It doesn't really support a KDC 
implementation that stores the actual password, where the server 
software and KDC may be updated after the password change to add 
support for newer encryption types, in that such an implementation 
could immediately support the use of the new encryption types except 
for not being able to pass off the needed parameters; however, I don't 
like the idea of having the actual passwords stored, so that doesn't 
worry me too much.  And it shouldn't be that hard to have the service 
change its password after it gets updated, to enable support for the 
new type.

Another, which I don't expect Microsoft to like, is to assert that 
we're not going to deal with this, that we expect service keys to be 
handled in binary form, and that it's up to the implementors to fix it 
themselves.  Binary form does have the advantage of allowing, say, an 
AES 256-bit key with 256 bits of randomness, as opposed to the 160-ish 
we can get now.  (See my recent exchanges with Joel regarding the AES 
draft.)  But refusing to deal with services having passwords, if the 
implementors or administrators prefer it that way?  Not very nice.

How about finding a place in the ticket to stuff the extra parameters?  
Obviously they can't go into the encrypted part, since they have to be 
available before decryption.  I'm not going to suggest Yet Another 
Gross Enctype Hack....

There may be other ways to solve this.  These are just some ideas 
kicking around, I haven't really got a good suggestion.  I suppose I 
kind of favor the alteration to the change-password protocol.

Other ideas?  Comments?

Ken

---

From: "Joel N. Weber II" <[email-masked]>
Date: Tue, 29 Jul 2003 22:26:08 -0400

> pre-computed data the attacker could generate that would be valid 

If we're really going to ignore preauthentication, isn't it the case
that an attacker doing a MitM attack can tell the client to use a salt
string and iteration count value for which the attacker happens to
have precomputed data?  It seems like the protocol ``feature'' that
lets you specify the salt has the effect of destroying most of the
potential for it to provide a security benefit.

(I think any preauth method which is effective at preventing the
client from encrypting ciphertext using the user's password and an
iteration count and salt supplied by the attacker is going to also be
effective at preventing the attacker from getting any ciphertext
encrypted using only in the user's password as the key.)

I think it's the case that a randomized salt has value if you think
MitM attacks don't exist, and you have either no preauth or merely an
encrypted timestamp.  Looking at the ASN.1 in clarifications, I also
get the impression that it would probably be relatively trivial to
implement.

> to prevent brute-force attacks in some circumstances.

What is an example of an attack that this flag protects against?

> available before decryption.  I'm not going to suggest Yet Another 

``You can't do that until after extensions'' seems to be a popular
refrain in this working group.

> kind of favor the alteration to the change-password protocol.

But I thought the two problems you cared about solving were that you
didn't want to have to use the change password protocol to make a new
enctype usable, and you wanted to be able to use different strength
string to key functions, and it seems like using the change password
protocol means that you don't solve one of those problems.  Did I miss
some other problem you wanted to solve?

(Being able to use different iteration counts for the service key also
strikes me as stupid.  I keep hearing that the KDC can cache the
result of the string to key function and therefore it's not a huge
performance hit for the KDC.  You're storing the service key password
on disk, right?  Why not store the result of running the string to key
function on disk as well?  Also, part of the reason that using
different ``strengths'' is hard is that while the KDC might know
whether there's IPsec running between it and the client, how does it
know if there's IPsec between it and the server?)

The concern I have with passwords as server keys is that if I use a
password with 40 or so bits of entropy as a server key, that means
that the ticket is encrypted with that much entropy.  Pretty soon you
find yourself wanting something like preauthentication for the service
key used by the ticket.

Perhaps the right answer is to say that user to user tickets should be
used in this case.  And maybe extensions should add a message that the
server sends to the client with authorization-data that the client
sends to the KDC before the client gets a ticket and sends the AP-REQ;
then we could have an authorization-data type for passing a user to
user ticket.  A message that's a container for authorization-data like
that is also useful if you want to not rely on clock sync in checking
ticket validity...

Or, maybe we should just say that service keys shouldn't be passwords
(which I suspect is the right answer, though I suspect that's one
Microsoft isn't going to like).

---

From: Sam Hartman <[email-masked]>
Date: Wed, 30 Jul 2003 13:15:52 -0400

First, it would be nice to see people supporting random keys rather
than passwords.

For services, the KDC already needs to know the set of encryption
types that are supported.  It seems that at the same time that the
password is changed, the KDC could just return the sets of opaque
parameters and salt strings that may be used for tickets.

Ken raises the concern that the KDC will need to save additional state
if it stores the password rather than a set of keys.  I think this is
acceptable because it will already need to store the set of supported
enctypes.

---

From: Nicolas Williams <[email-masked]>
Date: Wed, 30 Jul 2003 10:33:22 -0700

I'm not terribly enthused about services with non-random passwords
instead of randomized keys.  If you randomize the password you might as
well store randomized keys.

I see three ways to deal with this:

1a) Have the change password protocol include the corresponding
    ETYPE-INFO2 items for each enctype for which it derived a key from
    the new password (or, if it stores the passwords, that it would use
    to derive keys on the fly);

1b) Define ETYPE-INFO2 defaults per-enctype for service keys and let a
    principal tell the password changing service that it wants to use
    its password for deriving service keys - this way we don't need to
    include ETYPE-INFO2 in the password changing protocol;

or

2) Don't deal with it.  Once there's a decent password/key changing
   protocol why would anyone choose to use lame passwords for services?

   [Perhaps I'm missing some case where one would only have a password
    for a service, but if such a case involves using a user principal as
    a service then the answer is to use user-to-user authentication
    (which brings up the need to get GSS mech specified that is able to
    do Kerberos U2U).]

I'd much rather go with (2).

Cheers,

Nico
--

---

From: Ken Raeburn <[email-masked]>
Date: Wed, 30 Jul 2003 20:36:57 -0400

"Joel N. Weber II" <[email-masked]> writes:
> have precomputed data?

Without preauth, the only thing sent around encrypted in the client's
long-term key is the AS-REP from the KDC, and it'll always use the
right key.  This MitM attack would just be a denial of service, no
different than if the EncryptedData were modified en route.  However,
if the salt (and, for AES, iteration count) isn't varied when the
password is changed, that's one (or two) inputs to string-to-key that
can be held constant while doing pre-computation of keys.

Combine the MitM attack with timestamp preauth, though, and you've got
a way to weaken the key used and attack the user's current password,
yes.

>  It seems like the protocol ``feature'' that

Depends how it's used.  Timestamp preauth is, in some ways, better
than nothing, but I wouldn't describe it as good protection for the
key.

> encrypted using only in the user's password as the key.)

The attacker could simply communicate with the KDC, attempting to
authenticate as the user, using any of the (non-hardware) preauth
schemes, just as if the attacker walked up to a keyboard and started
typing in random passwords.

With pre-computed keys, the 1sec CPU time penalty is removed during
the actual attack.  Varying the salt string brings it back for the
whole dictionary at every password change.  Selecting a set of salt
strings and saving a bunch of keys multiplies the pre-computation
cost.

>>   In the MIT 

With this flag unset, and without preauthentication being required, an
attacker could send a request to the KDC and get back something
encrypted in the long-term key, with the relevant parameters for the
string-to-key operation, and begin a dictionary attack.  No traffic
interception required.

With this flag set, the attacker must at least authenticate to the KDC
before it can get anything encrypted in the target key.  If an attack
is used that requires large amounts of ciphertext, anomalous behavior
may be noticed in the KDC logs, and certain client principals can be
shut out, or have their accounts deactivated.

> refrain in this working group.

"Let's just hack it in in this field that wasn't intended to be used
this way" is pretty popular too.

> some other problem you wanted to solve?

Not having to use change-password I think is kind of secondary.

> strikes me as stupid.

It doesn't gain you anything.  But that's not the same as saying it
should be prohibited.

>   You're storing the service key password
> function on disk as well?

I don't know.  Perhaps because of application constraints you need to
be able to enter a password.  Maybe you're dealing with an automated
invocation of some programs that was written to ask for a password so
that it can acquire tickets with special flags set, and use them.

>  Also, part of the reason that using

I think that's an open question, but one others may be looking into
already.  See, for example, the GSSAPI CCM mech work in the NFSv4
working group, where they want to turn off encryption at the RPC/GSS
layer if they know that IPsec is in use.

> well store randomized keys.

I don't know that they're non-random in the Microsoft case, only that
they're stored as passwords.  Larry or someone else from the Microsoft
team might be able to provide more specifics.  Even in the MIT case,
one could generate a long, random printable-ASCII password and save it
away.

>     to derive keys on the fly);

The current MIT implementation allows for more than one key per
enctype; see the "salt type" parameter that mostly influences the
choice of salt string and occasionally the use of the AFS
string-to-key algorithm.  So this would have to be specified as
choosing the one that would be used as a service key.

>     include ETYPE-INFO2 in the password changing protocol;

You mean, go back and add more stuff to the crypto framework now?

Ken

---

From: Nicolas Williams <[email-masked]>
Date: Thu, 31 Jul 2003 09:03:16 -0700

> one could generate a long, random printable-ASCII password and save it

I think that if you're using random passwords you can use random keys...

I'd like to hear from Microsoft as to why storing service passwords
instead of service keys is so important.  I can imagine some decent
reasons, but I don't want to speculate.

> choosing the one that would be used as a service key.

Oh yeah, but no big deal, s/enctype/key/ above.  It can be done.

> You mean, go back and add more stuff to the crypto framework now?

Or do it in a separate I-D - why should it be done in the same document?

Anyways, if we have to address this problem we ought to do it as (1a),
methinks.

I see you didn't address solution (2) :)

I think we'll need input from Microsoft in order to reach consensus on
this.

Cheers,

Nico
--

---

From: Nicolas Williams <[email-masked]>
Date: Thu, 31 Jul 2003 12:14:01 -0500

I just realized that if we add a change service password operation to
the change password protocol that returns a SEQUENCE OF etype-info2
entries then any service that stores passwords instead of keys will now
have to store passwords *and* etype-info2 data.

What's the difference between storing keys and storing passwords +
etype-info2?  I don't see any.  You can't use the passwords as passwords
anymore.

So if anyone wants to store service passwords they'll have to use AS
exchanges to discover the etype-info2 data and cache it, or we'll have
to specify default s2kparams for use with service passwords, or we'll
have to say no more storing of service passwords instead of keys.

Cheers,

Nico
--