leendert@cs.vu.nl (Leendert van Doorn) (03/01/91)
The Kerberos authentication protocol is based on the Needham Schroeder protocol and uses timestamps as nonces. Time stamps are used to reduce the number of messages from the original protocol, and prevent (among other things) replay. In order to use timestamps, one ought to have the premise of synchronized clocks. Kerberos accommodates some deviation from this clock (in the magnitude of milliseconds), but on the whole it requires synchronized time for every participant in the authentication process. Its my opinion that this premise is very difficult to fulfill. There are two options here: the time server is un-authenticated, or is authenticated. In case of an un-authenticated time server it would be very simple to set the system clock back in time and resent, say, the message that increments my bank account by a (considerable:-) amount. The system on which the bank server operates wouldn't notice since its clock was reset to the time the message was originally sent (of course, this only works if you also resent the messages of the second half of the authentication protocol, i.e. exchanging the session key between client and server). It's possible to have an authenticated time server to circumvent the problem described above. This would work, except when a clock is running to far off it couldn't be synchronized (the authentication would fail). It depends on the synchronization rate of the time server and its time to respond to a sync request whether this would work. If the response time of sync rate exceeds the timestamp validity interval it becomes impossible to resync, and therefor all the authenticated requests made to the out-of-sync machine will fail. These are just some sunday morning thoughts, perhaps someone would like to comment on this ? For example, I don't see the point in using timestamps; using (unique:-) random numbers as nonces would do just as well. A lot of authentication protocols use random numbers as nonces, these seem to behave much cleaner (no hairy details like synchronized time). Although I'm referring to Kerberos other protocols that use timestamps are subject to this same problem as well. Is there any way out of this problem, while still using time stamps ? Leendert P.s. In the spring of this year Sape Mullender and I devised an authentication protocol for Amoeba which is rather similar to Kerberos but uses nonces instead of timestamps and is not redundant. For Amoeba we couldn't use timestamps since the concept of a synchronized clock per machine wasn't a valid one. -- Leendert van Doorn <leendert@cs.vu.nl> Vrije Universiteit / Dept. of Maths. & Comp. Sc. Amoeba project / De Boelelaan 1081 1081 HV Amsterdam / The Netherlands
paulf@shasta.Stanford.EDU (paulf) (03/01/91)
In article <9140@star.cs.vu.nl> leendert@cs.vu.nl (Leendert van Doorn) writes: >Its my opinion that this premise is very difficult to fulfill. There are >two options here: the time server is un-authenticated, or is authenticated. Actually, not so difficult. NTP accuracies of milliseconds are common, and NTP version 2 has a full encyption system for security (although some of the implementations are weak, leaving the DES keys out in the open) ("Nothing is so common as the incomplete execution of a Good Idea".). -=Paul Flaherty, N9FZX | "Think of it as evolution in action." ->paulf@shasta.Stanford.EDU | -- Larry Niven and Jerry Pournelle
mdl@B.GP.CS.CMU.EDU (Mark Lillibridge) (03/01/91)
> These are just some sunday morning thoughts, perhaps someone would like > to comment on this ? For example, I don't see the point in using timestamps; > using (unique:-) random numbers as nonces would do just as well. A lot > of authentication protocols use random numbers as nonces, these seem to > behave much cleaner (no hairy details like synchronized time). But... where do you get the random numbers from? There are no random numbers available on a public workstation before a user logs in. - Mark Lillibridge
smb@ulysses.att.com (03/01/91)
Actually, not so difficult. NTP accuracies of milliseconds are common, and NTP version 2 has a full encyption system for security (although some of the implementations are weak, leaving the DES keys out in the open) ("Nothing is so common as the incomplete execution of a Good Idea".). In fact, NTP's authentication code is not suitable for time distribution in a Kerberos-like environment. There are several reasons for this. First, from where would the workstation get the key to authenticate the time chime? You can't store it on the workstation itself. Rather, you can't store it securely, or J. Random Badguy can find it and use it to generate false ticks. Second, and almost a corollary, every pair of NTP hosts needs its own separate key. That doesn't scale well to thousands of workstations. (More precisely, every authentication domain, wherein every host trusts every other for that function, must have a separate key. But the real problem is the workstation arena, precisely where you need many keys, and where keys can't be shared.) NTP's authentication code does work well for controlling implementations, and for authentication among comparatively few low-stratum hosts. It doesn't help Kerberos, at least for workstations. --Steve Bellovin
don@ATHENA.MIT.EDU (03/01/91)
mr. van doorn, please see the paper, "limitations of kerberos," by bellovin and merrit, in the oct '90 computer communications review, for a good discussion of kerberos' need for authenticated time-service. to make a long story short, there are many ways to modify kerberos, that would avoid the need to synchronize, and time-synchronization wasn't a frivolous decision. the paper, if i remember correctly, discusses why kerberos moved to timestamps, and away from n & s' challenge/response (among other things). if bellovin and merritt don't describe the original problem to your satisfaction, there's an excellent paper on protocol-design, which i know does discuss kerberos' evolution from n & s in some detail: burrows, abadi, and needham, "a logic of authentication," proc. r. soc. lond. A 426(1989) pp. 233-271 . this paper is also available from digital systems research center, as a technical report; an abridged version of the paper appeared in sosp '90. -don davis, mit project athena staff
leendert@FLITS.CS.VU.NL (03/01/91)
#> These are just some sunday morning thoughts, perhaps someone would like #> to comment on this ? For example, I don't see the point in using timestamps; #> using (unique:-) random numbers as nonces would do just as well. A lot #> of authentication protocols use random numbers as nonces, these seem to #> behave much cleaner (no hairy details like synchronized time). # # But... where do you get the random numbers from? There are no #random numbers available on a public workstation before a user logs in. In my case (Amoeba) that wouldn't be too hard. Every kernel has its own random generator which is initialized with some hardware dependent values (clock, offset of the printbuf, etc). This mechanism should work equally well for other systems, I suppose. I know these number aren't perfect, but it all depends on the quality of your random generator and the seed. Leendert
mdl@B.GP.CS.CMU.EDU (Mark Lillibridge) (03/01/91)
Date: Fri, 01 Mar 91 11:15:13 +0100 From: leendert@flits.cs.vu.nl > # But... where do you get the random numbers from? There are no > #random numbers available on a public workstation before a user logs in. > > In my case (Amoeba) that wouldn't be too hard. Every kernel has its own > random generator which is initialized with some hardware dependent values > (clock, offset of the printbuf, etc). This mechanism should work equally well > for other systems, I suppose. I know these number aren't perfect, but it > all depends on the quality of your random generator and the seed. > > Leendert The big problem here is that these numbers aren't random, only pseudo-random which usually isn't good enough for security purposes. Moreover, suppose you did this. I walk up to a workstation, break in (via physical means if necessary), and change the pseudo-random number seed to a value of my choosing. I then log out and walk away. You then walk up and sit down & log in. You are now using non-random numbers (at least from my perspective) and worse, depending on the seed I choose, you may be reusing old numbers and hence be vulnerable to replay attacks. - Mark