jik@PIT-MANAGER.MIT.EDU ("Jonathan I. Kamens") (06/14/90)
While at Usenix, I had a discussion with someone about the way Kerberos does its initial user authentication, and the discussion raised some questions of which I am not sure the answers, so I'd like to ask the people who know more about Kerberos than I do what the story is. As I understand things now, here's what happens when a user wants to authenticate himself to Kerberos (please correct me if I'm wrong): 1. A tgt request is sent to the Kerberos server. 2. The server sends back a tgt, including a session key, encrypted in the user's key. 3. The user's key (which is usually obtained by prompting for a password and then running it through string_to_key, is used to decrypt the encrypted tgt. 4. If the decryption succeeds, then the user has a tgt which he can use to request future services from Kerberos. The person with whom I spoke at Usenix raised the concern that the scheme above is vulnerable to the following attack: 1. A tgt request for a person whom a malicious individual wants to nail is sent to the Kerberos server by the malicious individual. 2. The server sends back a tgt, including a session key, encrypted in the user's key. 3. The malicious individual has already prepared a database by running string-to-key over all of the words in /usr/dict/words, and over some other common passwords, or some such thing. 4. Decryption attempts are made with each of the trial passwords, until one succeeds. At this point, the malicious individual has the password of the person he's trying to nail. The first question is, is this a reasonable scenario? If so, then the second question is, why wasn't the original user authentication transaction implemented like this? 1. The user creates some request structure with the appropriate data in it, and encrypts that structure in his key. Then, the structure (along with a plaintext header to tell the server what principle the request is for) is sent to the server. 2. The server performs a decryption on the structure using the user's key, and if it succeeds, then the server knows that it really is talking to the user. 3. The server sends back a tgt encrypted in the user's key. 4. The user decrypts the tgt with his key. The advantage of this scenario is that the user only gets something encrypted in his key if he has already proven himself to be who he is claiming to be. Therefore, a malicious invididual can't get his hands on an encrypted piece of text to bang on until he figures out its key. Furthermore, if the malicious individual makes repeated attempts to prove that he is the user he's trying to nail, this can be detected on the server. One disadvantage of this scenario is that there is an extra encryption envolved. Are there any other disadvantages I'm not seeing? If not, why weren't things implemented this way? Thanks. Jonathan Kamens USnail: MIT Project Athena 11 Ashford Terrace jik@Athena.MIT.EDU Allston, MA 02134 Office: 617-253-8495 Home: 617-782-0710
smb@ulysses.att.com (06/14/90)
As far as I'm concerned, you're quite right -- that is a signficant weakness, and your proposed correction helps. It's by no means perfect, though -- an intruder could tap the Ethernet and wait for you to log in, collecting your password that way. For one solution, see %A T.M.A. Lomas %A L. Gong %A J.H. Saltzer %A R.M. Needham %T Reducing Risks from Poorly Chosen Keys %P 14-18 %B Proceedings of the Twelfth ACM Symposium on Operating Systems Principles %D December 1989 %I ACM %V 23 %N 5 %J Operating Systems Review
Saltzer@MIT.EDU (Jerome H Saltzer) (06/14/90)
Jonathan, The weakness you describe is real, and we recognized it from the beginning of the design. At the time we didn't see a straightforward fix (your suggestion reduces the weakness by a little, but it doesn't eliminate it) and we figured that the best solution was that any user can avoid the weakness by choosing a password that isn't in the dictionary. Last Spring, I described the problem to a group of graduate students at the University of Cambridge, and two of them were convinced that there must be a way to solve it. They did, and the resulting protocol (the essence of which is that the tgt must contain only information that looks random to anyone but the legitimate inquirer, even when correctly decrypted) appeared in a paper in the 12th SOSP. There was some discussion among the Kerberos developers about including the protocol as an option in Kerberos Version V, but as I recall the people doing that revision had enough on their hands and didn't want to throw that into the pot, too. Jerry
lunt@ctt.bellcore.com (Steve Lunt) (06/14/90)
In this case, the workstation is still vulnerable to someone spoofing the authentication server. That is, the workstation has no way of knowing if it is talking to the real Kerberos. The real Kerberos could be down, and the user could simply send an appropriate reply to the workstation's TGT request as if it were coming from Kerberos. You have this vulnerability with the current Kerberos TGT
request protocol if you configure your login program to use the reply from Kerberos rather than the password in /etc/passwd for authentication. The workstation needs some way of knowing that it is talking to the real Kerberos. It could use it's secret (in /etc/srvtab) for this purpose (requiring a change in the TGT request protocol.
-- Steve
Steven J. Lunt | lunt@ctt.bellcore.com | RRC 1L-213
Computer Security Technology |-------------------------| 444 Hoes Lane
Bellcore | (201) 699-4244 | Piscataway, NJ 08854
----- Begin Included Message -----
From: "Jonathan I. Kamens" <jik@pit-manager.MIT.EDU>
Subject: Why is initial user authentication done the way it is?
While at Usenix, I had a discussion with someone about the way
Kerberos does its initial user authentication, and the discussion
raised some questions of which I am not sure the answers, so I'd like
to ask the people who know more about Kerberos than I do what the
story is.
As I understand things now, here's what happens when a user wants to
authenticate himself to Kerberos (please correct me if I'm wrong):
1. A tgt request is sent to the Kerberos server.
2. The server sends back a tgt, including a session key, encrypted in
the user's key.
3. The user's key (which is usually obtained by prompting for a
password and then running it through string_to_key, is used to
decrypt the encrypted tgt.
4. If the decryption succeeds, then the user has a tgt which he can
use to request future services from Kerberos.
The person with whom I spoke at Usenix raised the concern that the
scheme above is vulnerable to the following attack:
1. A tgt request for a person whom a malicious individual wants to
nail is sent to the Kerberos server by the malicious individual.
2. The server sends back a tgt, including a session key, encrypted in
the user's key.
3. The malicious individual has already prepared a database by running
string-to-key over all of the words in /usr/dict/words, and over
some other common passwords, or some such thing.
4. Decryption attempts are made with each of the trial passwords,
until one succeeds. At this point, the malicious individual has
the password of the person he's trying to nail.
The first question is, is this a reasonable scenario?
If so, then the second question is, why wasn't the original user
authentication transaction implemented like this?
1. The user creates some request structure with the appropriate data
in it, and encrypts that structure in his key. Then, the structure
(along with a plaintext header to tell the server what principle
the request is for) is sent to the server.
2. The server performs a decryption on the structure using the user's
key, and if it succeeds, then the server knows that it really is
talking to the user.
3. The server sends back a tgt encrypted in the user's key.
4. The user decrypts the tgt with his key.
The advantage of this scenario is that the user only gets something
encrypted in his key if he has already proven himself to be who he is
claiming to be. Therefore, a malicious invididual can't get his hands
on an encrypted piece of text to bang on until he figures out its key.
Furthermore, if the malicious individual makes repeated attempts to
prove that he is the user he's trying to nail, this can be detected on
the server.
One disadvantage of this scenario is that there is an extra
encryption envolved. Are there any other disadvantages I'm not
seeing? If not, why weren't things implemented this way?
Thanks.
Jonathan Kamens USnail:
MIT Project Athena 11 Ashford Terrace
jik@Athena.MIT.EDU Allston, MA 02134
Office: 617-253-8495 Home: 617-782-0710
----- End Included Message -----billdo@IFS.UMICH.EDU (Bill Doster) (06/15/90)
> The short answer: Because this scenario is also vulnerable to a > dictionary attack. Suppose I wanted to break your password under the > new scheme. I just wait until you log in, recording your data request > in part 1. I now pretend to be Kerberos, and try and decrypt your > initial request with each possible key until I succeed. Once I have a > key that successfully decodes your request, I have found your key. While it's true that this scenario is also vulnerable to a dictionary attack, it reduces the possibilty of attack from Anyone anywhere that speaks IP can at anytime attack any account at any installation that uses Kerberos. to Anyone able to listen on the involved subnets must first wait for the targeted individual to sign-on and then record the that user's request. While in absolute terms these may be equivalent, in terms of potential likelihood, I think the number of probable attacks has been greatly reduced. There may be even better solutions to these type of problems and I'm not particularly attached to any one solution so long as it gets implemented. My question then is what is the current solution that Kerberos 5 *is* going to use? Bill Doster Univ. of Mich. -- Research Systems billdo@ifs.umich.edu
pato@APOLLO.COM (Joe Pato) (06/15/90)
In this case, the workstation is still vulnerable to someone spoofing the
authentication server. That is, the workstation has no way of knowing if it is
talking to the real Kerberos. The real Kerberos could be down, and the user
could simply send an appropriate reply to the workstation's TGT request as if
it were coming from Kerberos. You have this vulnerability with the current
Kerberos TGT request protocol if you configure your login program to use
the reply from Kerberos rather than the password in /etc/passwd for
authentication. The workstation needs some way of knowing that it is talking
to the real Kerberos. It could use it's secret (in /etc/srvtab) for this
purpose (requiring a change in the TGT request protocol.
-- Steve
Steven J. Lunt | lunt@ctt.bellcore.com | RRC 1L-213
Computer Security Technology |-------------------------| 444 Hoes Lane
Bellcore | (201) 699-4244 | Piscataway, NJ 08854
There is no need to change the TGT request protocol to work around this
problem. Simply have the login program request a ticket to the local machine
once the TGT has been acquired. It is the proper acquisition of this second
ticket that informs login that the user is valid and should be granted access
to the machine. The OSF DCE login code uses this strategy to validate both the
user and the KDC (I believe that this is also in the bsd4.4 login code)
-- Joe Pato
Cooperative Object Computing Operation
Hewlett-Packard Company
pato@apollo.hp.com
-------jik@PIT-MANAGER.MIT.EDU ("Jonathan I. Kamens") (06/15/90)
From: Mark Lillibridge <mdl@B.GP.CS.CMU.EDU> Date: Thu, 14 Jun 90 11:06:42 EDT The short answer: Because this scenario is also vulnerable to a dictionary attack. Suppose I wanted to break your password under the new scheme. I just wait until you log in, recording your data request in part 1. I now pretend to be Kerberos, and try and decrypt your initial request with each possible key until I succeed. Once I have a key that successfully decodes your request, I have found your key. This assumes that you have the ability to monitor transactions going over the network. The way things stands now, you do not need to be able to do this in order to get an encrypted packet to hack on, whereas in the proposed system I described, you do; therefore, my system provides at least some level of increased security. Incidentally, it seems to me that the way the Kerberos protocol is currently written, Kerberos is even *more* vulnerable to dictionary attack than is /etc/passwd encryption. This is because there are no seeds involved, so it's possible to build up a large database of encrypted keys, because the decryption is faster than crypt() (or at least I think it is; I'm not really sure about this one, so someone correct me if I'm wrong), and because it's possible to request an encrypted tgt for anyone in any realm, thus eliminating the security (albeit slight) of passwd files not being available for cracking on. Given all this, it would seem to me that the issue of making the protocol more secure should have been a high priority in the Kerberos V5 design. Is there a particular reason why it wasn't? Jonathan Kamens USnail: MIT Project Athena 11 Ashford Terrace jik@Athena.MIT.EDU Allston, MA 02134 Office: 617-253-8495 Home: 617-782-0710
lunt@ctt.bellcore.com (Steve Lunt) (06/15/90)
Joe,
Correct. I should have mentioned this.
This requires that the workstation make two requests of the Kerberos server. An alternative would be for the workstation to use *its* TGT (which it
could get at boot time) to request a ticket for the user, which it could then try to decrypt with the user's password. Of course, the user wouldn't get a TGT. This opens a whole other can of worms with the question: should the user himself or the workstation itself authenticate to other network services?
-- Steve
----- Begin Included Message -----
From pato@apollo.com Thu Jun 14 14:25:13 1990
From: pato@apollo.com (Joe Pato)
Date: Thu, 14 Jun 90 14:12:24 EDT
Subject: Re: Why is initial user authentication done the way it is?
To: lunt@ctt.bellcore.com (Steve Lunt)
Cc: athena.mit.edu!kerberos@bellcore.bellcore.com
In-Reply-To: lunt@ctt.bellcore.com (Steve Lunt), thu, 14 jun 90 13:59:49
In this case, the workstation is still vulnerable to someone spoofing the
authentication server. That is, the workstation has no way of knowing if it is
talking to the real Kerberos. The real Kerberos could be down, and the user
could simply send an appropriate reply to the workstation's TGT request as if
it were coming from Kerberos. You have this vulnerability with the current
Kerberos TGT request protocol if you configure your login program to use
the reply from Kerberos rather than the password in /etc/passwd for
authentication. The workstation needs some way of knowing that it is talking
to the real Kerberos. It could use it's secret (in /etc/srvtab) for this
purpose (requiring a change in the TGT request protocol.
-- Steve
Steven J. Lunt | lunt@ctt.bellcore.com | RRC 1L-213
Computer Security Technology |-------------------------| 444 Hoes Lane
Bellcore | (201) 699-4244 | Piscataway, NJ 08854
There is no need to change the TGT request protocol to work around this
problem. Simply have the login program request a ticket to the local machine
once the TGT has been acquired. It is the proper acquisition of this second
ticket that informs login that the user is valid and should be granted access
to the machine. The OSF DCE login code uses this strategy to validate both the
user and the KDC (I believe that this is also in the bsd4.4 login code)
-- Joe Pato
Cooperative Object Computing Operation
Hewlett-Packard Company
pato@apollo.hp.com
-------
----- End Included Message -----jon@MIT.EDU (Jon A. Rochlis) (06/15/90)
You have this vulnerability with the current Kerberos TGT request protocol if you configure your login program to use the reply from Kerberos rather than the password in /etc/passwd for authentication. The workstation needs some way of knowing that it is talking to the real Kerberos. It could use it's secret (in /etc/srvtab) for this purpose (requiring a change in the TGT request protocol. Making use of the TGT so a workstation knows it's not been spoofed by a fake KDC is quite reasonable, *if* the workstation has a secret (i.e. a srvtab). It doesn't work well in a public workstation model, where there are no secrets on workstations. -- Jon
bcn@CS.WASHINGTON.EDU (Clifford Neuman) (06/15/90)
Date: Thu, 14 Jun 90 14:29:39 -0400
From: "Jonathan I. Kamens" <jik@pit-manager.MIT.EDU>
Subject: Why is initial user authentication done the way it is?
Given all this, it would seem to me that the issue of making the
protocol more secure should have been a high priority in the Kerberos
V5 design. Is there a particular reason why it wasn't?
Keeping the protocol secure WAS a high priority in the design of
Kerberos V5. Here's what is done in V5, and the rationale behind it.
Dictionary and brute force attacks were considered. There is only one
way we know of to avoid brute force attacks, and that is to eliminate
verifiable plaintext as described in "Reducing Risks from Poorly
Chosen Keys" cited earlier. We felt that this was a good approach,
but it had to be the basis of design for a protocol, not added on
later.
The design of a production authentication system such as Kerberos
involves many tradeoffs. While a protocol without verifiable
plaintext has advantages, those advantages don't come without cost.
The overall structure of the protocol would be changed (not just
extended), the simple nature of the Kerberos protocol would be lost,
and additional state would have to be maintained by all parties. Much
of what would be lost are those features we considered important for
the environment in which Kerberos was to operate.
Even if we did adopt such a protocol, I do not believe that the result
could properly be considered a new "version" of the original protocol.
Although we decided not to pursue a non-verifiable plaintext approach,
we did learn from the paper. In particular, we have added a confounder
to the front of all encrypted data. The confounder serves a purpose
similar to the salt in Unix passwords and eliminates pre-computed
dictionary attacks. It does not, however, prevent real-time, brute
force attacks (which may use a dictionary for its guesses).
We also considered adopting some form of pre-authentication before
credentials were returned by the KDC as a way to reduce the likelihood
of brute force attacks. We decided that there was not a significant
increase in security from such an approach. As has already been
pointed out, an attacker would still be able to obtain ciphertext to
work on by listening for a request from (or response to) the targeted
client(s). We made minimal assumptions about the security of the
underlying network. Without a secure underlying network, a determined
attacker would have little difficulty obtaining ciphertext to work on.
Our conclusion: without eliminating verifiable plaintext, the only
real countermeasure to a brute force attack is a well chosen password.
Passwords in Kerberos can be of any length. The longer the password,
or the more randomly chosen, the greater the portion of the 56 bit (DES)
keyspace that is used.
~ Cliffpato@APOLLO.COM (Joe Pato) (06/15/90)
From: Mark Lillibridge <mdl@B.GP.CS.CMU.EDU>
Date: Thu, 14 Jun 90 11:06:42 EDT
The short answer: Because this scenario is also vulnerable to a
dictionary attack. Suppose I wanted to break your password under the
new scheme. I just wait until you log in, recording your data request
in part 1. I now pretend to be Kerberos, and try and decrypt your
initial request with each possible key until I succeed. Once I have a
key that successfully decodes your request, I have found your key.
From: jik@pit-manager.MIT.EDU ("Jonathan I. Kamens")
This assumes that you have the ability to monitor transactions going
over the network. The way things stands now, you do not need to be
able to do this in order to get an encrypted packet to hack on,
whereas in the proposed system I described, you do; therefore, my
system provides at least some level of increased security.
There is no substitute for well selected passwords. Even if the TGT
acquisition protocol were made more "secure" by forcing the initiator to
transmit an encrypted request there are still simple dictionary attacks. If
you want to attack another principal's passwords simply request a ticket for
that principal. The ticket you receive from the KDC includes verifiable
plaintext that is encrypted in the target principal's key.
-- Joe Pato
Cooperative Object Computing Operation
Hewlett-Packard Company
pato@apollo.hp.com
-------jik@PIT-MANAGER.MIT.EDU ("Jonathan I. Kamens") (06/15/90)
Date: Thu, 14 Jun 90 12:50:15 -0700 From: bcn@cs.washington.edu (Clifford Neuman) Keeping the protocol secure WAS a high priority in the design of Kerberos V5. Here's what is done in V5, and the rationale behind it. "Keeping the protocol secure" is the wrong terminology. The problem I described in my original message is present in Version 4. Therefore, it's not a question of keeping the protocol secure, it's a question of making the protocol more secure in Version 5 than it was in Version 4. Dictionary and brute force attacks were considered. There is only one way we know of to avoid brute force attacks, and that is to eliminate verifiable plaintext as described in "Reducing Risks from Poorly Chosen Keys" cited earlier. We felt that this was a good approach, but it had to be the basis of design for a protocol, not added on later. I am aware that verifiable plaintext in the encrypted messages sent over the network poses a problem that is not easily solveable. However, I have always found the claim, "We can't fix everything, so we aren't going to be fix anything," to be remarkably bogus. The modification to the protocol which I proposed in my original message makes it impossible for someone to get an encrypted tgt to work on unless they are eavesdropping on the network. As someone has already pointed out, this makes a large portion of dictionary attacks impossible. Furthermore, the code to implement the change I proposed (or a similar one) is negligible, and can be plugged into the library and server code without modifying any application code. Why, then, was not such a change considered? The design of a production authentication system such as Kerberos involves many tradeoffs. While a protocol without verifiable plaintext has advantages, those advantages don't come without cost. The overall structure of the protocol would be changed (not just extended), the simple nature of the Kerberos protocol would be lost, and additional state would have to be maintained by all parties. Much of what would be lost are those features we considered important for the environment in which Kerberos was to operate. I have not proposed that all verifiable plaintext be removed from the protocol. The proposal I've made is much simpler than that, and yet even though it's simple, it makes a dictionary attack on the Kerberos server much more difficult. I ask again, why do so many people appear to be rejecting this change, or the possibility of one like it to make the protocol more secure, out-of-hand? Although we decided not to pursue a non-verifiable plaintext approach, we did learn from the paper. In particular, we have added a confounder to the front of all encrypted data. The confounder serves a purpose similar to the salt in Unix passwords and eliminates pre-computed dictionary attacks. It does not, however, prevent real-time, brute force attacks (which may use a dictionary for its guesses). Even with the confounder, it's still easier to use a dictionary attack on a Kerberos server than it is to do so on an /etc/passwd file. Adding pre-authentication would make it no easier to do the fomrmer than to do the latter, and possibly make it harder to do the former. We also considered adopting some form of pre-authentication before credentials were returned by the KDC as a way to reduce the likelihood of brute force attacks. We decided that there was not a significant increase in security from such an approach. As has already been pointed out, an attacker would still be able to obtain ciphertext to work on by listening for a request from (or response to) the targeted client(s). We made minimal assumptions about the security of the underlying network. Without a secure underlying network, a determined attacker would have little difficulty obtaining ciphertext to work on. I really think you've underestimated the effect of adding pre-authentication. Fine, you can assume that in at least some cases, the network is insecure. Let me ask you this question, however: let's say someone in California wants to break into my Athena account. Under the current protocol, they don't have to be able to monitor the Athena subnet (and, indeed, they probably can't) -- all they have to do is ask kerberos.mit.edu for an encrypted tgt for me, and bang on it in California. If you add pre-authentication, then they can't get that encrypted tgt, and since they can't monitor the Athena subnet, they can't get it that way either. It's a big step to conclude from "This change won't fix all of our problems" that "This change won't do any significant amount of good." I agree with the former, but I most certainly do not agree with the latter. Our conclusion: without eliminating verifiable plaintext, the only real countermeasure to a brute force attack is a well chosen password. Passwords in Kerberos can be of any length. The longer the password, or the more randomly chosen, the greater the portion of the 56 bit (DES) keyspace that is used. I see many people on this list saying, "This is not a relevant danger because people should choose good passwords." The problem is that PEOPLE DON'T CHOOSE GOOD PASSWORDS. The people on this mailing list/in this newsgroup (well, at least some of them) are supposed to be experts in the field of authentication. I'm not, and yet it seems obvious to me that authentication systems shoulde be written in a way that attempts to behave reasonably EVEN IN THE FACE OF USER STUPIDITY. Using "people should choose good passwords" as an excuse for why we don't have to improve the Kerberos security is just that, an excuse. jik
jik@PIT-MANAGER.MIT.EDU ("Jonathan I. Kamens") (06/15/90)
From: pato@apollo.com (Joe Pato) Date: Thu, 14 Jun 90 16:05:18 EDT There is no substitute for well selected passwords. Even if the TGT acquisition protocol were made more "secure" by forcing the initiator to transmit an encrypted request there are still simple dictionary attacks. If you want to attack another principal's passwords simply request a ticket for that principal. The ticket you receive from the KDC includes verifiable plaintext that is encrypted in the target principal's key. First of all, see the message I just sent in response to Cliff for my response to the "There is no substitute ofr well selected passwsords" argument. I won't bother to repeat it here. Second, you appear to be misunderstanding what I am proposing. If the user has to send the server a pre-authenticated (e.g. encrypted in the user's key) piece of data before the server will send back a tgt, then there is no way to get an encrypted ticket to bang on without first proving to the server that you are who you claim to be. Brute force becomes unuseable in this context because a brute force attempt to convince the server that you are the right person would require you to send thousands (if not tens, or hundreds, or thousands of thousands) of pre-authenticated requests to the server, and such repeated failing requests would show up in the logs. Jonathan Kamens USnail: MIT Project Athena 11 Ashford Terrace jik@Athena.MIT.EDU Allston, MA 02134 Office: 617-253-8495 Home: 617-782-0710
bcn@CS.WASHINGTON.EDU (Clifford Neuman) (06/15/90)
In my last message, I gave the general rationale behind our decisions for V5. Unfortunately, I only included part of the reasoning behind rejecting the pre-authentication scheme you described. Let me elaborate here. Like everything else, tradeoffs are involved; two in particular. One of our concerns in the initial design of Kerberos (V1) was that the password be vulnerable for as short a period as possible. As a result, we did not prompt for a password until a response had been received from the KDC. To perform pre-authentication, we would have to prompt for the password before the request was made, and store it until the response was received (if at all). I will admit that the increase in exposure is practically negligible, but it must be compared with the gain in security due to pre-authentication, which I also feel is pretty small (though perhaps not negligible). More importantly, Kerberos does not distinguish between types of principals. A principal can play the role of either a client or a server. The distinction is not made in the Kerberos database. We felt that doing so would make the Kerberos model less clear. If clients and servers are equivalent your argument about an attacker in California being unable to obtain ciphertext to work on would no longer hold. The attacker could request a set of credentials with the target of his attack listed as the server. He could then apply the brute force attack to decrypt the ticket. ~ Cliff
jik@PIT-MANAGER.MIT.EDU ("Jonathan I. Kamens") (06/15/90)
Date: Thu, 14 Jun 90 17:03:18 -0700 From: bcn@cs.washington.edu (Clifford Neuman) One of our concerns in the initial design of Kerberos (V1) was that the password be vulnerable for as short a period as possible. As a result, we did not prompt for a password until a response had been received from the KDC. To perform pre-authentication, we would have to prompt for the password before the request was made, and store it until the response was received (if at all). I will admit that the increase in exposure is practically negligible, but it must be compared with the gain in security due to pre-authentication, which I also feel is pretty small (though perhaps not negligible). Apparently, we disagree on the relative dangers of someone grabbing a password froom a program doing authentication, and someone grabbing a tgt from the server. Frankly, I don't think it's possible to justify the trade-off you describe in the paragraph above. In order to grab a password out of a process, you've got to get a memory dump of some sort of that process during the very short window of time during which the procedss has the password stored. This means that you have to be aware of exactly when that window occurs, that you have to have a way of grabbing a memory image instantly when the window happens, and that you have to have access to the machine in question in order to grab the memory image. Oh, yes, you also usually have to have root access since a properly configured machine won't allow non-root users to get access to the memory images of processes run by other users. On the other hand, all I have to do in order to grab someone's tgt and hack on it is to ask the server for it. Do you really believe that it's more likely that someone is going to steal a password in the second or so more it is stored, if we do preauthentication, than it is that someone is going to be able to figure out someone's password from a tgt they've requests from the server? Sorry, but I don't believe it. I hope the people I talked to at Usenix post the source code to their program which hacks on tgt's, just to show how easy it is to get a password from a tgt. More importantly, Kerberos does not distinguish between types of principals. A principal can play the role of either a client or a server. The distinction is not made in the Kerberos database. We felt that doing so would make the Kerberos model less clear. If clients and servers are equivalent your argument about an attacker in California being unable to obtain ciphertext to work on would no longer hold. The attacker could request a set of credentials with the target of his attack listed as the server. He could then apply the brute force attack to decrypt the ticket. It is extremely, extremely likely that the Kerberos server itself is going to have a very good password. The pre-authentication scheme I've described, as I have already said several times, is not meant to prevent every possible attack against the kerberos server. It is meant to prevent EASY attacks on the kerberos server. As you have already pointed out, deciding on how to do authentication is a matter of making various trade-offs. None of the trade-offs provide COMPLETE security, so you've got to choose which ones give you the best security for the least amount of effort. The preauthentcation scheme I've described, in my opinion, gives you a much higher level of security (For heaven's sake, breaking into Kerberos now is easier than breaking into any Unix box! Does that mean so little to you? Are you so eager to take a step backward in Unix security when you push Kerberos? I'm bewildered by that, really bewildered.), for an extremely low cost (the only disadvantage you've mentioned that is even worth considering is the extra time the key stays in memory, and I would argue that it isn't worth considering that either). Jonathan Kamens USnail: MIT Project Athena 11 Ashford Terrace jik@Athena.MIT.EDU Allston, MA 02134 Office: 617-253-8495 Home: 617-782-0710
smb@ulysses.att.com (06/15/90)
Michael Merritt and I have just finished a paper on the limitations and
weakness of Kerberos. We're doing a rewrite now, and will make it
available via anonymous ftp as soon as possible. For the moment, let
me list our recommendations. The last point is quite relevant to this
discussion, and the paper discusses a number of alternatives.
A challenge/response protocol should be offered as an optional
alternative to time-based authentication.
Use a standard message encoding, such as ASN.1, which includes
identification of the message type within the encrypted data.
Alter the basic login protocol to allow for handheld
authenticators, in which {R}KC, for a random R, is used to
encrypt the server's reply to the user, in place of the key KC
obtained from the user password. This allows the login
procedure to prompt the user with R, who obtains {R}KC from the
handheld device and returns that value instead of the password
itself.
Mechanisms such as random initial vectors (in place of
confounders), block chaining and message authentication codes
should be left to a separate encryption layer, whose
information-hiding requirements are clearly explicated.
Specific mechanisms based on DES should be validated and
implemented.
The client/server protocol should be modified so that the
multi-session key is used to negotiate a true session key,
which is then used to protect the remainder of the session.
Support for optional extensions should be included. In
particular, an option to protect against dictionary attacks on
/etc/passwd may be a desirable extension.
It is, however, worth stating loudly and clearly that even without
these changes, we do think that Kerberos is vastly superior to the
current situation. We just think it could be better still.
--Steve Bellovinwesommer@ATHENA.MIT.EDU (Bill Sommerfeld) (06/15/90)
Jon claims in his revised protocol that: there is no way to get an encrypted ticket to bang on without first proving to the server that you are who you claim to be. Sure there is. All I have to do is get a valid TGT, and then ask the KDC for a ticket to jik@ATHENA.MIT.EDU. The response will include a "ticket to jik", which will contain my name (and other things) encrypted in your key. I can then bang on the ticket all I want in the privacy of my own CPU. Remember that in Kerberos there is no difference between users and servers. - Bill
bede@LINUS.MITRE.ORG (06/15/90)
Posted-Date: Thu, 14 Jun 90 21:24:14 EDT
From: smb@ulysses.att.com
Date: Thu, 14 Jun 90 21:24:14 EDT
[ . . . ]
Support for optional extensions should be included. In
particular, an option to protect against dictionary attacks on
/etc/passwd may be a desirable extension.
[ . . . ]
At the risk of carrying the discussion off on a tangent: the issue of
dictionary-based password attacks is, at many sites, moot. For
example, we've rigidly enforced a rule here for about two years
prohibiting dictionary and various other "trivial" passwords for user
logins. The muscle behind the policy is provided by a rather simple
password cracker I wrote, plus a modified version of passwd (and Real
Soon Now, kpasswd).
In a sense, support for extensions is already in Kerberos, just as it
is for passwd, assuming you have the source code. In our case, aside
from the locally-produced lookup code, the total modification to
(k)passwd amounts to less than 50 lines, but could be *much* less than
that, of course.
Regardless of the merits of the encryption/authentication scheme used,
it just makes sense to discourage trivial attacks right from the start,
if at all possible.
-Bede McCall
Research Computing Facility
MITRE Corp. Internet: bede@mitre.org
MS A114 UUCP: {decvax,philabs}!linus!bede
Burlington Rd.
Bedford, MA 01730 (617) 271-2839jik@PIT-MANAGER.MIT.EDU ("Jonathan I. Kamens") (06/15/90)
Date: Thu, 14 Jun 90 21:26:25 -0400
From: Bill Sommerfeld <wesommer@ATHENA.MIT.EDU>
Sure there is. All I have to do is get a valid TGT, and then ask the
KDC for a ticket to jik@ATHENA.MIT.EDU. The response will include a
"ticket to jik", which will contain my name (and other things)
encrypted in your key. I can then bang on the ticket all I want in
the privacy of my own CPU.
Remember that in Kerberos there is no difference between users and
servers.
Indeed. Cliff Neuman and Tim Shepard have both managed to make this
clear to me (I had been overlooking it) in private E-mail, and I have
explained it to the people who originally raised this point to me.
After spending about as much time explaining it to them as Cliff and
Tim had to spend explaining it to me before I realized the problem
:-), their response was, "Oh, you're right." They couldn't come up
with any solution to this problem, and neither can I, at this point.
Several people have challenged my claim that it's easier to break
into a Kerberos-authenticated machine than it is to break into a
machine using standard Unix security, both here and in private E-mail.
I still claim that this is the case, and I will respond here to the
various points that people have made.
First of all, let me reiterate why I still think this is a problem.
In the description below, "Unix" is short for the tradiitional Unix
authentication system:
1. Under Unix, you have to have an account on a properly configured
machine in order to get a hole of the passwd file. Under Kerberos,
anyone on the Internet can request an encrypted sample of anyone to
bang on it.
2. Under Unix, every possible password must be encrypted using every
possible seed in order to match against strings in the passwd file.
Under Kerberos, this isn't necessary -- just run string_to_key over
all of your possible passwords and they can immediately be used for
decryption attempts.
3. The crypt() function under Unix is meant to be slow. Kerberos'
decryption of the tgt is faster, significantly. Furthermore, it's
straight DES, so anyone who is serious about cracking passwords can
use all of the available DES hardware to do his cracking.
In summary, it's easier to get a hold of encrypted Kerberos data to
play with than it is to get a hold of /etc/passwd data, and playing
with it is faster.
Now, to answer the various questions people have asked. Cliff
Neuman says:
Although I havn't contested that claim, I am not quite sure that I
understand it. I believe that with confounders at the start of
all ciphertext (as will be the case in V5), a pre-computed
dictionary attack is ruled out, and the difficulty of a brute
force attack on verifiable plaintext is of the same order of
difficulty (constant factor) as a brute force attack on a Unix
password.
The confounder does make it impossible to encrypt lots of copies of
the tgt that you think you'll get, and then compare it to the tgt you
actually get. However, the counfounder does not (as I understand it;
please correct me if I'm wrong) change the fact that passwords need
only be run through string_to_key (i.e. you don't have to change the
encryption of the password based on the confounder), and that DES is,
or can be made, much faster than crypt().
One of the main objections to traditional Unix security is that when
it was designed, machines were slow enough that the crypt() function
provided somewhat adequate protection, while nowadays things are so
much faster that it is possible to employ a brute-force attack on
Unix. It is my claim that it is *even easier* to employ a brute-force
attack against Kerberos.
Jerry Saltzer says:
1. Dictionary attacks originated when people discovered that they
could ftp or otherwise steal a copy of /etc/passwd and get a whole
bunch of user names and encrypted passwords to work on; they pay
off because out of several hundred or thousand candidates a few
will probably yield. With Kerberos you have to know the name of
the user you want to attack. A random hacker in California may be
able to attack jik, because he saw your id on a usenet bulletin
board, but he can't tackle all 10000 Athena user id's looking for
a few that yield to the dictionary. So the available attack is a
different one from the one the hackers use, and in some ways less
useful.
My response is two-fold. First of all, it is my opinion that it is
unreasonable to base the security of a system on whether or not it is
easy to get usernames for that system. What happens when your school
publishes a student directory with usernames in it? What happens when
the directory gets put on line (For an example of this, try typing
"finger John@athena.mit.edu" or "finger Wu@mit.edu".)? Second, a
recent examination of the passwords in Athena's Kerberos database
revealed that over 30% of the passwords were guessable. This included
all machine service keys, which means that an even higher percentage
of actual user passwords were guessable. This means that if I can get
ten Athena usernames (through the mechanisms I described above or
perhaps just by guessing common usernames based on the way Athena
usernames are formed by default and on other methods), I will on
average be able to break three of those usernames easily. What all
this means is that whether or not I can read the whole passwd file is
irrelevant -- I remind you that there are lots of ways to get
usernames, and besides that, Kerberos *tells* you when you ask for a
username that isn't valid.
Jerry continues:
BSD-supplied security system has holes you can drive a Mack truck
through (passwords on the net in the clear, .rhosts files in
private directories, wide-open NFS, etc.). Kerberos cleans all
that up and provides a huge improvement in system security in a
dozen areas; it provides essentially no improvement in some other
areas. And here are people (not you, but some of the others
responding to this discussion) claiming that Kerberos might as
well be trashed because it is no better than the original UNIX
security! Somehow we need to get some perspective back into the
picture.
Then, in another message to me, he says:
In my previous message, I guess I let you off the hook too easily.
You are a little over the edge with that comment! I assume you
mean only that dictionary attacks can go faster?
Yes, Jerry, I'm talking only about dictionary attacks here, and I do
believe that they can go significantly faster and are more vulnerable
than are dictionary attacks under Unix. And yes, I agree with you
that Kerberos has claned up the garbage in BSD protections and
provided huge improvements in many areas; I just think that this
particular area is much too vulnerable.
Jonathan Kamens USnail:
MIT Project Athena 11 Ashford Terrace
jik@Athena.MIT.EDU Allston, MA 02134
Office: 617-253-8495 Home: 617-782-0710smb@ulysses.att.com (06/15/90)
3. The crypt() function under Unix is meant to be slow. Kerberos' decryption of the tgt is faster, significantly. You've fallen into the trap that you were intended to fall into. Crypt() was *coded* to be slow, in the hope that naive crackers would use it instead of rewriting it. Apart from the E-box juggling, crypt() is straight DES. You could copy most of the code from Kerberos. You could even save time by precomputing all 4K E-boxes. The speed issue boils down to who is doing the most encryptions. crypt() iterates 25 times; however, the initial permutation and its inverse, when composed together, are the identity permutation; thus, they can be omitted. And they're one of the slowest parts of software DES. If you're not repeatedly encrypting the same string in DES, you can't do that optimization. I'd call it a wash on speed. Furthermore, it's straight DES, so anyone who is serious about cracking passwords can use all of the available DES hardware to do his cracking. Not clear that that actually works here. The strings are comparatively short, as I recall, and the setup time for DES hardware can be significant. This is especially true if you're using a UNIX system and have the OS and device driver overhead. A dedicated PC with a DES chip wouldn't have as much overhead, of course.
lunt@ctt.bellcore.com (Steve Lunt) (06/15/90)
Although with a modified kpasswd you can screen passwords which are set from your system, you cannot prevent a user from contacting the Kerberos server independent of your kpasswd and changing his password to something trivial.
If the user has a copy of the old kpasswd, he can simply use that. Notice that kpasswd is not setuid.
-- Steve
----- Begin Included Message -----
Date: Thu, 14 Jun 90 23:43:18 -0400
From: bede@linus.mitre.org
Subject: RE: Why is initial user authentication done the way it is?
...
At the risk of carrying the discussion off on a tangent: the issue of
dictionary-based password attacks is, at many sites, moot. For
example, we've rigidly enforced a rule here for about two years
prohibiting dictionary and various other "trivial" passwords for user
logins. The muscle behind the policy is provided by a rather simple
password cracker I wrote, plus a modified version of passwd (and Real
Soon Now, kpasswd).
In a sense, support for extensions is already in Kerberos, just as it
is for passwd, assuming you have the source code. In our case, aside
from the locally-produced lookup code, the total modification to
(k)passwd amounts to less than 50 lines, but could be *much* less than
that, of course.
Regardless of the merits of the encryption/authentication scheme used,
it just makes sense to discourage trivial attacks right from the start,
if at all possible.
-Bede McCall
Research Computing Facility
MITRE Corp. Internet: bede@mitre.org
MS A114 UUCP: {decvax,philabs}!linus!bede
Burlington Rd.
Bedford, MA 01730 (617) 271-2839
----- End Included Message -----lunt@ctt.bellcore.com (Steve Lunt) (06/15/90)
I would add to this list below (arguably most important) that under Unix, /etc/passwd is protected by the Unix access control mechanism, so that Unix may enforce password screening, whereas the Kerberos database is protected by a mechanism which doesn't allow it to know by what password its keys are based.
-- Steve
Steven J. Lunt | lunt@ctt.bellcore.com | RRC 1L-213
Computer Security Technology |-------------------------| 444 Hoes Lane
Bellcore | (201) 699-4244 | Piscataway, NJ 08854
From: "Jonathan I. Kamens" <jik@pit-manager.MIT.EDU>
First of all, let me reiterate why I still think this is a problem.
In the description below, "Unix" is short for the tradiitional Unix
authentication system:
1. Under Unix, you have to have an account on a properly configured
machine in order to get a hole of the passwd file. Under Kerberos,
anyone on the Internet can request an encrypted sample of anyone to
bang on it.
2. Under Unix, every possible password must be encrypted using every
possible seed in order to match against strings in the passwd file.
Under Kerberos, this isn't necessary -- just run string_to_key over
all of your possible passwords and they can immediately be used for
decryption attempts.
3. The crypt() function under Unix is meant to be slow. Kerberos'
decryption of the tgt is faster, significantly. Furthermore, it's
straight DES, so anyone who is serious about cracking passwords can
use all of the available DES hardware to do his cracking.
In summary, it's easier to get a hold of encrypted Kerberos data to
play with than it is to get a hold of /etc/passwd data, and playing
with it is faster.ZBEN@UMD2.UMD.EDU (Ben Cranston) (06/15/90)
It occurs to me that the tgt could initially return something that is encrypted and cannot be "validated" even if the correct password be guessed. The client would be forced to do one more interaction with the tgt server, a sort of "ok, this is something you gave me decrypted with the user's password -- does it make sense to you?". The advantage of this is that a dictionary approach would have to do one of these additional interactions for every try, and the tgt could arrange to notify human security personnel if the number of "bad password" replies exceeds a certain number within a predetermined time interval. The disadvantage is requiring one more packet interchange per login, and the fact that it does NOT address the aforementioned tgt-spoofing attack.
jmc@PacBell.COM (Jerry M. Carlin) (06/15/90)
In article <9006150549.AA24093@PIT-MANAGER.MIT.EDU> jik@PIT-MANAGER.MIT.EDU ("Jonathan I. Kamens") writes: ... >1. Under Unix, you have to have an account on a properly configured > machine in order to get a hole of the passwd file. Under Kerberos, > anyone on the Internet can request an encrypted sample of anyone to > bang on it. Kerberos is necessary but not sufficient for enhanced security. A gateway machine (or router) serving as a "firewall" can disallow packets coming in from j.random.cyberpunk@never.never.land whilst still allowing legitimate machines access. -- Jerry M. Carlin (415) 823-2441 jmc@srv.pacbell.com To dream the impossible dream. To fight the unbeatable foe.
bede@LINUS.MITRE.ORG (06/15/90)
Date: Fri, 15 Jun 90 09:30:20 -0400 From: Steve Lunt <lunt@ctt.bellcore.com> Although with a modified kpasswd you can screen passwords which are set from your system, you cannot prevent a user from contacting the Kerberos server independent of your kpasswd and changing his password to something trivial. If the user has a copy of the old kpasswd, he can simply use that. Notice that kpasswd is not setuid. Valid point, but I'm playing the game of preventing the Bad Guys from trivially breaking password protection, as opposed to preventing a user from doing something stupid. So if a user cobs up a back yard version of (k)passwd for the sake of having a trivial password, there's not much I can do but keep running my password cracker and freezing the login in the hope that s/he eventually gets the message. In point of fact, I do this already. But we're drifting into general system administration matters here, and Ted Anderson and others have raised some interesting questions more germane to kerberos proper. -Bede
wes@terminator.cc.umich.edu (Wesley Craig) (06/15/90)
In article <1990Jun15.152103.15241@PacBell.COM> jmc@PacBell.COM (Jerry M. Carlin) writes: >Kerberos is necessary but not sufficient for enhanced security. A gateway >machine (or router) serving as a "firewall" can disallow packets coming >in from j.random.cyberpunk@never.never.land whilst still allowing legitimate >machines access. Thus making it extreemly difficult to use in a wide area network (like from usenix, for example). Moreover, if kerberos is accepted by DCE and ISO for an extension to X.500, how are you going to "keep the bad guy out". wes
wes@terminator.cc.umich.edu (Wesley Craig) (06/16/90)
In article <9006150126.AA22710@E40-008-10.MIT.EDU> wesommer@ATHENA.MIT.EDU (Bill Sommerfeld) writes: >Jon claims in his revised protocol that: > > there is no way to get an encrypted ticket to bang on without > first proving to the server that you are who you claim to be. > >Sure there is. All I have to do is get a valid TGT, and then ask the >KDC for a ticket to jik@ATHENA.MIT.EDU. The response will include a >"ticket to jik", which will contain my name (and other things) >encrypted in your key. I can then bang on the ticket all I want in >the privacy of my own CPU. This is interesting, but really not as bad as the problem Jon and I talked about. The above *does* require a valid TGT, first. Biff, of course, doesn't have a valid TGT. Unfortuately he doesn't need one, either. >Remember that in Kerberos there is no difference between users and >servers. If it weren't for the design flaws, getting a "ticket to jik" wouldn't be a problem. I can't think of any added security you'd get be splitting users and servers, under a working authentication protocol. wes
tytso@ATHENA.MIT.EDU (Theodore Ts'o) (06/16/90)
>Sure there is. All I have to do is get a valid TGT, and then ask the >KDC for a ticket to jik@ATHENA.MIT.EDU. The response will include a >"ticket to jik", which will contain my name (and other things) >encrypted in your key. I can then bang on the ticket all I want in >the privacy of my own CPU. This is interesting, but really not as bad as the problem Jon and I talked about. The above *does* require a valid TGT, first. Biff, of course, doesn't have a valid TGT. Unfortuately he doesn't need one, either. Getting a valid TGT is pretty trivial. Athena's Kerberos setup has several guest/test principals whose passwords are eminently guessable. In addition, anybody who has a principal (or who can crack a guest/test principal) in a Kerberos realm who has exchanged keys with the target's Kerberos server can also get a cross-realm TGT. As you can see, it *isn't* hard to get a TGT, and so it *won't* be hard to request a ticket for jik@ATHENA.MIT.EDU. So for this reason, I don't think there's any point in complicating the protocol with a pre-authentication step for an initial ticket-granting-ticket, as long as there's another similar "hole" which cannot be closed without doing major revisions to the entire Kerberos concept. In addition, I think people are going a bit rabid screaming "dictionary attack". Granted, you can pre-compute the string_to_key() to obtain a "dictionary", and this process does involve a DES encryption step, so it would save a bit of time. But you still have to use the resultant key to attempt a DES decryption for every single key in your "dictionary" on the sealed TGT which you got from the server, and this decryption can not be done in parallel for many different users. (This is assuming that the confounders in V5 Kerberos prevent the optimization which Ted Anderson pointed out.) And as Steve Bellovin has asserted, the speed difference involved between the DES decyption and something like fcrypt() are probably very close to each other. - Ted P.S. I've always wondered what would happen if someone were to create a DES chip with the modified E-boxes (and optimized it for Unix password cracking) in an VLSI design course... :-)
jik@PIT-MANAGER.MIT.EDU ("Jonathan I. Kamens") (06/16/90)
Perhaps I'm confused, but it seems to me that if crypt() is doing 25 encryptions, and Kerberos DES is doing 1, then crypt() is going to be slower than Kerberos DES. Furthermore, if you have a database of passwords you want to try in your attack, crypt() requires you to encrypt each of them 4096 times (64 characters are legal in the seed, and there are two seed characters), which means you've got 4096 times as many passwords to store in your password database. Granted, Unix encryption does have the added problem that once you *do* do all of those crypt()s, the database you have needs only be compared to the passwords you're trying to crack using strcmp() (or its equivalent), rather than having to do an encryption using them as the key. However, I'm not sure how relevant this is, since the type of atack I'm going to do on a Kerberos tgt isn't really the same as the type of attack I'm going to use on a Unix password. One final note -- one of the big mistakes made in the design of Unix authentication is that it assumed that machines were slow enough that brute-force attacks would not be feasible. We all know that nowadays, this is more and more no longer the case. Therefore, do we want to make the same assumption, and same mistake, in the design of the Kerberos authentication scheme? Jonathan Kamens USnail: MIT Project Athena 11 Ashford Terrace jik@Athena.MIT.EDU Allston, MA 02134 Office: 617-253-8495 Home: 617-782-0710
smb@ulysses.att.com (06/16/90)
Perhaps I'm confused, but it seems to me that if crypt() is doing 25 encryptions, and Kerberos DES is doing 1, then crypt() is going to be slower than Kerberos DES. It depends on how much ciphertext you have to decrypt before you can determine if you've succeeded in cracking it. And the ratio isn't 25:1, because one can omit the IP and IP^-1 steps between each pair of encryptions, and can in fact omit the initial IP because the constant string is 0. Matt Bishop wrote a lovely paper describing all sorts of optimizations.... Furthermore, if you have a database of passwords you want to try in your attack, crypt() requires you to encrypt each of them 4096 times (64 characters are legal in the seed, and there are two seed characters), which means you've got 4096 times as many passwords to store in your password database. That's not a significant problem in practice. Even with the seed, a dictionary of 10K passwords takes only 400M bytes -- not a trivial amount of storage, but hardly outrageously expensive. Granted, Unix encryption does have the added problem that once you *do* do all of those crypt()s, the database you have needs only be compared to the passwords you're trying to crack using strcmp() (or its equivalent), rather than having to do an encryption using them as the key. However, I'm not sure how relevant this is, since the type of atack I'm going to do on a Kerberos tgt isn't really the same as the type of attack I'm going to use on a Unix password. A key point, incidentally, is the availability of subsidiary information about the user -- say, the stuff that fingerd spits out. One final note -- one of the big mistakes made in the design of Unix authentication is that it assumed that machines were slow enough that brute-force attacks would not be feasible. We all know that nowadays, this is more and more no longer the case. Therefore, do we want to make the same assumption, and same mistake, in the design of the Kerberos authentication scheme? I do not agree that mistake was made. The mistake was in not enforcing better password standards years ago. I'll leave the arithmetic as an exercise for the reader, but my calculations show that for an 8-character password composed of mixed upper/lower case -- i.e., 52 characters -- and an encryption time of 1 microsecond (better than I've seen any hardware designs), a brute-force attack would take about 2 years.