Information about http://www.eecis.udel.edu/~mills/database/papers/atirp.pdf
AUTHENTICATION SCHEME FOR DISTRIBUTED, UBIQUITOUS, REAL-TIME…
Tags: archive repositories, authentication scheme, circularity, client populations, cryptographic authentication, cryptographic keys, delaware newark, intruder, lifetimes, network time service, resource provision, secu, server resources, substantial resources, time protocols, ubiquitous network, ubiquity, university of delaware, vices, web servers,Pages: 12
Language: english
Created: Tue Jul 28 21:01:12 1998
Display cached document
Page 1
Page 2
Page 3
Page 4
Page 5
Page 6
Page 7
Page 8
Page 9
Page 10
Page 11
Page 12
AUTHENTICATION SCHEME FOR DISTRIBUTED, UBIQUITOUS, REAL-TIME PROTOCOLS 1,2
David L. Mills
University of Delaware
Newark, DE 19716
ABSTRACT A reliable and ubiquitous network time service such as
NTP requires some provision to prevent accidental or mali-
Cryptographic authentication methodology proposed for cious attacks on the servers and their clients. Reliability
use in the Internet require substantial resources when very requires that clients can determine that received messages
large client populations are involved. Resource provision- are authentic; that is, were actually sent by the intended
ing becomes especially important when time-critical ser- server and not manufactured or modified by an intruder.
vices are involved. In the cast of time- synchronization Ubiquity requires that any client can verify the authenticity
services, a special case exists, since cryptographic keys of any server using only public information. The NTP secu-
must enforce valid lifetimes, but validating key lifetimes rity model and authentication scheme are designed with
requires cryptographic keys. This paper proposes a scheme these requirements in mind.
which minimizes server resources while resolving the
apparent circularity. In many ways, the NTP requirements are shared by other
ubiquitous, distributed applications, such as directory ser-
INTRODUCTION vices, web servers and archive repositories. However, an
effective design requires it operate efficiently in all modes
The Network Time Protocol (NTP) is widely used in the supported, including peer-peer, client-server and multicast
Internet to synchronize computer time to national stan- modes. Current IETF key-agreement schemes like Photuris
dards. The current NTP population includes well over 200 [3], SKIP [1] and ISAKMP [4] could be used with NTP as
primary (stratum-1) servers and 100,000 secondary (stra- with other protocols in peer-peer mode, but are unsuitable
tum-2 and above) servers and clients. It provides compre- for client-server mode, where persistent state cannot be
hensive mechanisms to access national time and frequency maintained by servers for client populations which may
dissemination services, organize the hierarchical time-syn- number in the thousands, and multicast mode, where clients
chronization subnet and adjust the clock in each participat- do not ordinarily send messages to the servers.
ing subnet peer. The protocol uses redundant servers,
diverse network paths and crafted algorithms which discard While the current NTP security model and authentication
bogus servers and minimize errors due to various causes. It scheme have been in use for well over a decade, they have
can operate in several modes, including peer-peer, client- several drawbacks, the most serious being the requirement
server and multicast. In most places of the Internet of today, that keys must be securely distributed in advance. There are
NTP provides accuracies of 1-20 ms, depending on the no provisions in the NTP architecture for key distribution
characteristics of the synchronization sources and subnet or management on the assumption these functions would be
paths. provided by a designated protocol other than NTP. Even if
such functions were available, the large number of associa-
The NTP architecture model and supporting algorithms are tions, well over 250,000 in the current NTP subnet, would
described in [5], the NTP Version 3 protocol specification make the management operations to distribute keys and
in RFC-1305 [6], and recent algorithm improvements in manage their lifetimes infeasible. In a truly survivable net-
[7]. Additional information can be found at the NTP home work, these functions cannot rely on centralized key man-
page http://www.eecis.udel.edu/~ntp and the author's home agement; they require a distributed network design with
page http://www.eecis.udel.edu/~mills. redundant paths and diverse servers.
1. Prepared through collaborative participation in the Advanced Telecommunications/Information Distribution Research
Program (ATIRP) sponsored by U.S. Army Research Laboratories Cooperative Agreement DAAL01-96-2-0002 This
work is also supported by DARPA Information Technology Office Contract DABT 63-95-C-0046, NSF Grant NCR
93-01002, and U.S. Navy Contract A303 276-93.
2. This paper has been accepted for publication in Advanced Telecommunications/Information Distribution
(ATIRP) Conference, College Park MD, January 1997. It should not be cited or redistributed prior to publica-
tion.
1
CURRENT NTP SECURITY MODEL AND its current rate for a time specified by the protocol or until
AUTHENTICATION SCHEME all key lifetimes have expired.
The authentication scheme described in the NTP Version 3 A client is usually configured with a number of servers,
specification RFC-1305 is the basis of the current NTP each identified by source and destination IP addresses and
security model. Its goal is to provide universal access to assigned a secret key and key identifier, which is stored in a
data products of the protocol, while preventing an intruder secure database. The key is used to construct a message
from modifying a message or manufacturing a fake mes- digest (one-way hash function) of the contents with either
sage which is acceptable to a client. It is not necessary, nor keyed MD5 [10] or DES-CBC [8]. The session key identi-
would it be politically expedient, to encrypt the timestamps fier and message digest form a message authentication code
or otherwise hide the data in NTP messages, since these are (MAC), which is transmitted with the message. A server is
public values. Furthermore, it is not the intent in the model usually stateless and does not retain data from one client
to include access controls; other mechanisms based on IP request to the next. It uses the key identifier in the client
address and UDP port filtering are available for that. It is message to retrieve the secret key from its own database
not necessarily the case that the model includes protections and construct the MAC in messages sent to the client. This
from message loss, duplication or corruption, since these assumes that the server has the same secret key as the client
protections are an intrinsic capability of the NTP protocol and uses the same key identifier.
itself. In the present scheme, it is possible to share a single key
among a set of servers and clients. It is also possible to
It is important to note that the NTP security model specifi- engineer some interesting and useful security topologies
cally recognizes that authentication service may not be con- using this scheme. For example, a closely cooperating
tinuously available. The model assumes that individual clique of primary servers operating in peer-peer modes can
peers can fail or operate incorrectly or even attempt to share a single key, in order to provide backup for each other
modify messages or jam the subnet in one form or another. if a radio clock fails. This avoids having to distribute a dif-
In addition, transmission lines can fail, routes can change ferent key for every pairwise association to every server in
or become congested, and cryptographic keys and even the clique. In another example, a set of servers can operate
security policies can change while the subnet is in regular, in multicast mode with a single key, so that a client popula-
continuous operation. This requires that clients utilize tion can synchronize to any of them without requiring sepa-
redundant servers and diverse paths for the authentication rate keys for each one. These examples point up the need to
function, as well as the synchronization function. authenticate an aggregate of servers as a unit, where it is
not necessary to distinguish among the servers in the aggre-
The hierarchical organization of the NTP subnet requires gate, at least not with respect to authentication.
the construction of an unbroken chain of authentication
from a given client via intermediate servers to the primary DESIGN ISSUES
(stratum 1) servers, which are assumed authenticated by In a perfect world with inexhaustible processing time and
external means. Each server at a given stratum level in the memory resources, a public-key cryptosystem such as RSA
hierarchy individually authenticates its assigned servers at [9] would be a good foundation on which to build the NTP
the next lower stratum level. If at least one of them is authentication scheme. In a public- key cryptosystem, each
authenticated, the server synchronizes with it and reports server computes a public/private key pair, or a clique of
itself as authenticated to its dependent servers at the next servers is assigned a public/private key pair using a secure
higher stratum level. Whether a server is authenticated or secondary channel. The private key is held by the server
not, the client maintains state variables for it, including its and never divulged. A necessary property of public-key
time offset relative to the client clock. cryptosystems is that knowledge of the public key and
ciphertext does not compromise the private key or plain-
As the synchronization subnet, evolves in response to
text. The user name, address, public key and related values
server failures and restarts, prevailing network delay paths,
are stored in a database maintained by directory servers.
etc., the authentication hierarchy evolves in response. It
may happen that protocol operations can proceed normally; In order to minimize the vulnerability to attack, public-key
but, due to temporary lack of cryptographic key material, cryptography requires every message to be individually
for example, individual servers may become isolated from signed using the server private key. The same technique
their sources, even if the timekeeping data itself remains can be used to construct a digital signature for a unit of data
valid. If a server ordinarily synchronized via authenticated or a message and later verify the signature. In order to min-
sources loses contact with all of these sources, it coasts at imize the processing required, the server constructs a digest
2
of the message contents using a one-way hash function must have enforceable lifetimes. Valid keys should be
such as MD5, then encrypts it using RSA and the server replaced from time to time, in order to frustrate potential
private key. The result is stored in the MAC and transmit- cryptanalysis. Once destroyed, a key should never be used
ted with the message. The client constructs the message again. This implies a specific vulnerability to an attack on
digest, then compares it with the MAC decrypted using the the timekeeping system, specifically NTP. If secure time-
server public key. keeping is dependent on reliable authentication and, which
itself requires keys sensitive to time, an interesting circular-
Public/private key pairs are normally generated by the ity results.
server. The public key, together with identification infor-
mation, is signed by one or more trusted agents functioning When a key with enforceable lifetime is created or used for
as notaries, to construct a certificate, which is then submit- cryptographic computations, the results of the computa-
ted to the directory service. Certificates bind the public key tions cannot be validated, unless the entity performing the
and related values to identification data, such as a digitized computations has been correctly synchronized to a source
photograph, handwritten signature or voiceprint. These which has been authenticated by a valid certificate trail.
data are not necessarily secure; only the server private key Thus, a digital signature cannot be generated, unless the
is considered secure, but it is never divulged. In order to server has authentic time. On the other hand, the signature
verify that an information source is authentic and that the can be verified at any time, but validated only when the cli-
source is in fact in possession of the private key, it is neces- ent has authentic time.
sary to verify all notary signatures on the certificate trail as
well. This raises the issue that NTP must function in scenarios
where reliable network timekeeping has not yet been estab-
Constructing the MD5 message digest is a relatively fast lished, or when the certificates have not yet been verified.
operation; for instance, the time to compute a NTP message The most common case occurs when a client is first started
digest on a Hewlett Packard 9000/735 is 31 us and 263 us and before its clock has been set. In this such cases, the
on a Sun Microsystems SPARC 1. However, even when the synchronization and authentication functions must operate
plaintext is a 128-bit MD5 hash, RSA encryption is pain- even before the clock has been reliably set. Thus, any pro-
fully slow. For instance, the mean time to sign a NTP mes- tocols used by NTP itself to initiate cryptographic associa-
sage ranges form 80 ms on a Digital 266-MHz Alpha to 2.1 tions must not depend on prior key exchanges which are
s on a Sun SPARC 1; while the mean time to verify the sig- themselves dependent on synchronized clocks. This design
nature ranges from 7.9 ms on the Alpha to 201 ms on the requirement is unique among all other known network ser-
SPARC 1. While the MD5 running times are independent vices.
of data and key, the RSA running times are highly variable,
depending on the population of one bits in the key and The client operations to synchronize the clock and authenti-
other factors. For example, with random bit strings as keys, cate the servers cannot depend on which of these functions
the verification time on a SPARC 1 ranges from 198 ms to is done first. In the present NTP protocol model, state vari-
273 ms. Variations as large as these would result in unac- ables are developed for each remote server separately,
ceptable loss of accuracy in many NTP applications. including its apparent time offset relative to the local clock.
This process takes from one to several packet exchanges, in
Another approach uses some variant of the Station-to-Sta- order to suppress outlyers and establish reliable offsets.
tion (STS) protocol, such as Photuris to compute a shared While this is going on, the client may be in process of
secret used as a session key. Since the numbers involved retrieving certificates from directory services and verifying
can be very large (512 bits is typical), these operations are signatures. As this process involves only public values, it
slow, but need to be computed only when the keys are can be performed while NTP is collecting data to set the
changed. However, these protocols require persistent state time. Only after reliable server time and authenticated
at the servers, thus are not appropriate for use in NTP cli- server identification have been achieved can the local clock
ent-server and multicast modes with large numbers of serv- be set.
ers and clients. Either the server must be able to regenerate
the session key as each client request is received, or some There is a subtle problem when considering the design of
means must be provided to authenticate the current session secure directory services and related transport protocols.
key with respect to a previously used session key which has Ordinarily, clients of these services assume the various
been cryptographically authenticated. cryptographic keys and certificates have enforceable life-
times; that is, the services will not themselves use keys or
A basic rule in all key distribution and management certificates, unless the lifetimes can be enforced. When
schemes is that cryptographic keys and associated values used with NTP, no assumption can be made about the life-
3
times, since the clocks may not yet be synchronized. In the to one or more trusted agents for signatures, then sends it to
present approach, this does not matter, since determining the directory service for public access. A client authenti-
the local clock offset and authenticating the server are per- cates a server by sending either its name or address,
formed independently. Designers of secure services must depending on how it first learned of its existence, and
be prepared to deliver the data requested, even if unable to retrieves the public key and related certificate media. It
securely authenticate it at the moment. then verifies the public key using the certificates as neces-
sary. This need be done only once, after which the public
NTP VERSION 4 SECURITY MODEL AND
key can be cached at the client. These operations use stan-
AUTHENTICATION SCHEME
dard procedures, so are not discussed further here.
The Version 4 security model and authentication scheme is
designed to be backwards compatible with previous ver- The scheme works differently for peer-peer, client-server
sions, except in a few unavoidable cases. The model adds and multicast modes; however, the message digest is calcu-
new features that provide for a self-keyed style of operation lated in the same way in all modes. The MD5 algorithm is
in conjunction with new directory and certificate retrieval used to hash the concatenated server private random value,
services now in the planning process in the IETF. The new private key, IP source address, IP destination address and
scheme uses cryptographic message digests in the same MAC key identifier fields. The resulting 16-octet value is
way as the original scheme. The contents of the NTP the session key used to construct the message digest, which
header are hashed with keyed MD5 and a 16-octet session is computed as in the original scheme. Note that the new
key, yielding a 16-octet message digest. The MAC trans- scheme in effect includes all significant fields of the mes-
mitted following the NTP header consists of a four-octet sage, not just the NTP header as in the original scheme, and
key identifier followed by a 16-octet message digest. thus provides additional security.
A client authenticates the server by first obtaining the The scheme adds new key-request and key-response mes-
server name, IP address, public key and related certificate sages to the suite of control messages already defined. The
media. Obtaining the public values may involve additional key-request message sent by a client includes a copy of the
network operations, such as traversing the directory tree, client public key. The key-response message sent by the
decrypting signatures, verifying certificates, etc. In princi- server includes the current session key encrypted first by
ple, provisions must be made to change any of the public the server private key and then by the public key in the key-
values; however, it is anticipated that the need to do this request message. Since the only use of the client public-pri-
will be relatively infrequent and the computational burden vate key pair is to verify and obscure the response, the pub-
will not affect the accuracy of ongoing NTP operations. lic key need not be certificated.
Should any of these values change, the natural result is to The three modes of NTP operation: peer-peer, client-server
fail the authentication test, timeout and terminate the asso- and multicast present quite different security models. In
ciation, then attempt to restart it. peer-peer modes, both peer associations are persistent, so
In the new scheme, each server maintains a private random predistributed session keys cause little additional burden
value which is used together with its private key and other other than as now with the current authentication scheme.
values to generate session keys. The private random value In the current reference implementation, the keys are stored
is replaced at relatively short intervals, such as a day, in a protected file. Presumably, the contents of this file can
depending on the needs of the security model, but never be accessed and updated by means external to the protocol
divulged. The private key is replaced at longer intervals, without impinging on the current NTP protocol specifica-
such as a week, since this requires all clients to indepen- tion or reference implementation. This can be done using
dently verify its authenticity using relatively tedious opera- schemes proposed by the IETF and are not discussed fur-
tions. The RSA public-key cryptosystem is used to encrypt ther here, other than to point out the scheme described
and decrypt data in some messages exchanged between the below for client- server modes can be used as well.
server and its clients. In addition, secure directory services
In client-server mode, the server maintains no per-client
are assumed available from which public keys and certifi-
state between client requests, either for timekeeping data or
cates can be obtained. The mechanisms used to obtain the
cryptographic media. Therefore, the session key must be
public keys and verify the certificates are the subject of cur-
regenerated for each received client request. In order to
rent proposals, but are not discussed further in this paper.
prevent forgery, it must not be possible for an intruder to
A server generates a public-private key pair using algo- eavesdrop on an exchange between a client and a legitimate
rithms well-known in the art. It then generates a certificate server to mimic the key generation process for that client or
binding the public key to identification values and sends it server. The scheme described below, which was originally
4
suggested by Steven Kent of BBN3, requires that the server putes the list. Each time the server uses an entry, it stores
regenerate a secret key upon each message arrival from the the low order four octets of the previous session key in the
client; however, the computations to regenerate the key are key identifier field.
relatively minor. A client authenticates each message relative to the message
First, the client sends a key-request message to the server, that immediately preceded it. It computes the session key
which then generates and encrypts the session key as above and message digest as described above. It then extracts the
and returns it in a key- response message to the client. The low order four octets of the session key and compares with
client decrypts the session key and caches it in its secure the key identifier field in the last message received. If the
database. This method prevents a man-in-the- middle values agree, the current message is considered valid. If
attack, but does consume significant server and client not, a message might have been discarded in transit, so the
resources. However, the exchange needs to be done only client hashes again. This procedure may continue for a
infrequently when the client is first started up and when the fixed number of hashes, following which the client aban-
server private values are changed. Alternatively, if the dan- dons the attempt and sends a key- request message to
ger of a man-in-the-middle attack can be avoided through obtain the current session key.
the use of secure address filtering, for example, the session The session key applies only to the current message and is
key can be considered a public value with controlled scope. not useful for any subsequent message. However, an
In this case, the session key can be transmitted as plaintext, intruder (man-in-the-middle) could intercept a query
since it is not useful for any other source address. response message and learn the current session key, from
The cached session key is used by the client to compute the which all session keys used prior to this message can be
message digest in the usual way. The server recomputes the determined. While these session keys will not be used
session key as each request is received. This is done exactly again, it is conceivable, although unlikely, that the intruder
as above when generating the hash returned to the client as could trick a client who has not yet heard a prior message
the session key. The session key and message digest are into accepting a bogus message. In order to succeed, the
then computed as above. The session key is unique to the intruder would have to impersonate at least the IP source
particular server and client involved and need not be address of any messages it sends to the unsuspecting client
retained by the server between requests. Note that an which, although possible, is unlikely.
intruder cannot modify and replay a message as valid, even It is important to understand that the session key obtained
if it forges the source address, since only the server and cli- in this way is not a secret in the ordinary sense, since any
ent can construct the correct session key. client can obtain it or forge it without cryptographic
In multicast mode, servers send messages at a controlled authentication or encryption of any kind. Its purpose is to
rate and respond only to key-request messages. A server provide a shared value dependent upon a secret value held
first calculates a list of 16-octet session keys for later use, only by the server and used in subsequent steps to generate
as in the S/KEY system [2]. It first computes the session the message digest of each transmitted message. Thus,
key as in client-server mode and uses this as the first entry while the shared value can be obtained by any intruder and
in the list. For this purpose, the IP source and destination used subsequently as a key to generate a message digest,
addresses are the server address and assigned multicast the actual secret used to generate the shared value is not
group address, respectively, and the key identifier is a ran- divulged and, presumably, cannot be obtained by an
dom roll. The low order four octets of this session key are intruder. Neither can future secrets be predicted by an
used to generate the next session key and become the key intruder. In this sense, the scheme has perfect forward
identifier associated with that key. The server uses the same secrecy.
IP addresses and this session key to generate the next ses- SUMMARY AND CONCLUSIONS
sion key. Continuing in this way, the server fills the list,
which may have from a few to several hundred entries. With relevance to Army battlefield systems, The level of
intricate dependencies in this paper confirms that good
The server uses the list in inverse order; that is, the last authentication scheme design is a tricky business and
entry is used first, then the next before that, and so on until invites vulnerabilities in surprising places. With particular
all entries except the first have been used. At this point, the relevance to network timekeeping, the most significant
server generates a new private random value and recom- requirement is that time synchronization and source
authentication must be decoupled and allowed to proceed
3. Personal communication. independently until a sufficient set of timely servers are
found and their authenticity confirmed.
5
The authentication schemes described for NTP client- (ISAKMP). Internet Draft, National Security
server and multicast modes have direct application to Army Agency, November 1995, 59 pp.
tactical networks and command/control networks, where
survivability and independence from centralized control is 5. Mills, D.L. Internet time synchronization: the
essential. Network Time Protocol. IEEE Trans. Communi-
REFERENCES cations COM-39, 10 (October 1991), 1482-1493.
1. Aziz, A., T. Markson, H. Prafullchandra. SKIP 6. Mills, D.L. Network Time Protocol (Version 3)
extensions for IP multicast. Internet Draft, Sun specification, implementation and analysis. Net-
Microsystems, December 1995, 11 pp. Eastlake, work Working Group Report RFC-1305, Univer-
D., 3rd., and C. Kaufman. Domain Name System sity of Delaware, March 1992, 113 pp.
security extensions. Internet Draft, CyberCash,
7. Mills, D.L. Improved algorithms for synchroniz-
December 1995, 45 pp.
ing computer network clocks. IEEE/ACM Trans.
2. Haller, N. The S/KEY one-time password sys- Networks (June 1995), 245-254.
tem. Network Working Group Report RFC-1760.
Bellcore, February 1995, 12 pp. 8. DES modes of operation. FIPS Publication 81,
National Bureau of Standards, December 1980.
3. Karn, P., and W.A. Simpson. The Photuris ses-
sion key management protocol. Network Work- 9. PKCS #1: RSA encryption standard, Version 1.5.
ing Group Internet Draft (ipsec-photuris), RSA Laboratories, November 1993.
Qualcomm, November 1995, 66 pp.
10. Rivest, R. The MD5 message-digest algorithm.
4. Maughan, D., M. Schertler. Internet security Network Working Group Report RFC-1321, MIT
association and key management protocol and RSA, April 1992, 21 pp.
6
AUTHENTICATION SCHEME FOR DISTRIBUTED, UBIQUITOUS, REAL-TIME PROTOCOLS 1,2
David L. Mills
University of Delaware
Newark, DE 19716
ABSTRACT A reliable and ubiquitous network time service such as
NTP requires some provision to prevent accidental or mali-
Cryptographic authentication methodology proposed for cious attacks on the servers and their clients. Reliability
use in the Internet require substantial resources when very requires that clients can determine that received messages
large client populations are involved. Resource provision- are authentic; that is, were actually sent by the intended
ing becomes especially important when time-critical ser- server and not manufactured or modified by an intruder.
vices are involved. In the cast of time- synchronization Ubiquity requires that any client can verify the authenticity
services, a special case exists, since cryptographic keys of any server using only public information. The NTP secu-
must enforce valid lifetimes, but validating key lifetimes rity model and authentication scheme are designed with
requires cryptographic keys. This paper proposes a scheme these requirements in mind.
which minimizes server resources while resolving the
apparent circularity. In many ways, the NTP requirements are shared by other
ubiquitous, distributed applications, such as directory ser-
INTRODUCTION vices, web servers and archive repositories. However, an
effective design requires it operate efficiently in all modes
The Network Time Protocol (NTP) is widely used in the supported, including peer-peer, client-server and multicast
Internet to synchronize computer time to national stan- modes. Current IETF key-agreement schemes like Photuris
dards. The current NTP population includes well over 200 [3], SKIP [1] and ISAKMP [4] could be used with NTP as
primary (stratum-1) servers and 100,000 secondary (stra- with other protocols in peer-peer mode, but are unsuitable
tum-2 and above) servers and clients. It provides compre- for client-server mode, where persistent state cannot be
hensive mechanisms to access national time and frequency maintained by servers for client populations which may
dissemination services, organize the hierarchical time-syn- number in the thousands, and multicast mode, where clients
chronization subnet and adjust the clock in each participat- do not ordinarily send messages to the servers.
ing subnet peer. The protocol uses redundant servers,
diverse network paths and crafted algorithms which discard While the current NTP security model and authentication
bogus servers and minimize errors due to various causes. It scheme have been in use for well over a decade, they have
can operate in several modes, including peer-peer, client- several drawbacks, the most serious being the requirement
server and multicast. In most places of the Internet of today, that keys must be securely distributed in advance. There are
NTP provides accuracies of 1-20 ms, depending on the no provisions in the NTP architecture for key distribution
characteristics of the synchronization sources and subnet or management on the assumption these functions would be
paths. provided by a designated protocol other than NTP. Even if
such functions were available, the large number of associa-
The NTP architecture model and supporting algorithms are tions, well over 250,000 in the current NTP subnet, would
described in [5], the NTP Version 3 protocol specification make the management operations to distribute keys and
in RFC-1305 [6], and recent algorithm improvements in manage their lifetimes infeasible. In a truly survivable net-
[7]. Additional information can be found at the NTP home work, these functions cannot rely on centralized key man-
page http://www.eecis.udel.edu/~ntp and the author's home agement; they require a distributed network design with
page http://www.eecis.udel.edu/~mills. redundant paths and diverse servers.
1. Prepared through collaborative participation in the Advanced Telecommunications/Information Distribution Research
Program (ATIRP) sponsored by U.S. Army Research Laboratories Cooperative Agreement DAAL01-96-2-0002 This
work is also supported by DARPA Information Technology Office Contract DABT 63-95-C-0046, NSF Grant NCR
93-01002, and U.S. Navy Contract A303 276-93.
2. This paper has been accepted for publication in Advanced Telecommunications/Information Distribution
(ATIRP) Conference, College Park MD, January 1997. It should not be cited or redistributed prior to publica-
tion.
1
CURRENT NTP SECURITY MODEL AND its current rate for a time specified by the protocol or until
AUTHENTICATION SCHEME all key lifetimes have expired.
The authentication scheme described in the NTP Version 3 A client is usually configured with a number of servers,
specification RFC-1305 is the basis of the current NTP each identified by source and destination IP addresses and
security model. Its goal is to provide universal access to assigned a secret key and key identifier, which is stored in a
data products of the protocol, while preventing an intruder secure database. The key is used to construct a message
from modifying a message or manufacturing a fake mes- digest (one-way hash function) of the contents with either
sage which is acceptable to a client. It is not necessary, nor keyed MD5 [10] or DES-CBC [8]. The session key identi-
would it be politically expedient, to encrypt the timestamps fier and message digest form a message authentication code
or otherwise hide the data in NTP messages, since these are (MAC), which is transmitted with the message. A server is
public values. Furthermore, it is not the intent in the model usually stateless and does not retain data from one client
to include access controls; other mechanisms based on IP request to the next. It uses the key identifier in the client
address and UDP port filtering are available for that. It is message to retrieve the secret key from its own database
not necessarily the case that the model includes protections and construct the MAC in messages sent to the client. This
from message loss, duplication or corruption, since these assumes that the server has the same secret key as the client
protections are an intrinsic capability of the NTP protocol and uses the same key identifier.
itself. In the present scheme, it is possible to share a single key
among a set of servers and clients. It is also possible to
It is important to note that the NTP security model specifi- engineer some interesting and useful security topologies
cally recognizes that authentication service may not be con- using this scheme. For example, a closely cooperating
tinuously available. The model assumes that individual clique of primary servers operating in peer-peer modes can
peers can fail or operate incorrectly or even attempt to share a single key, in order to provide backup for each other
modify messages or jam the subnet in one form or another. if a radio clock fails. This avoids having to distribute a dif-
In addition, transmission lines can fail, routes can change ferent key for every pairwise association to every server in
or become congested, and cryptographic keys and even the clique. In another example, a set of servers can operate
security policies can change while the subnet is in regular, in multicast mode with a single key, so that a client popula-
continuous operation. This requires that clients utilize tion can synchronize to any of them without requiring sepa-
redundant servers and diverse paths for the authentication rate keys for each one. These examples point up the need to
function, as well as the synchronization function. authenticate an aggregate of servers as a unit, where it is
not necessary to distinguish among the servers in the aggre-
The hierarchical organization of the NTP subnet requires gate, at least not with respect to authentication.
the construction of an unbroken chain of authentication
from a given client via intermediate servers to the primary DESIGN ISSUES
(stratum 1) servers, which are assumed authenticated by In a perfect world with inexhaustible processing time and
external means. Each server at a given stratum level in the memory resources, a public-key cryptosystem such as RSA
hierarchy individually authenticates its assigned servers at [9] would be a good foundation on which to build the NTP
the next lower stratum level. If at least one of them is authentication scheme. In a public- key cryptosystem, each
authenticated, the server synchronizes with it and reports server computes a public/private key pair, or a clique of
itself as authenticated to its dependent servers at the next servers is assigned a public/private key pair using a secure
higher stratum level. Whether a server is authenticated or secondary channel. The private key is held by the server
not, the client maintains state variables for it, including its and never divulged. A necessary property of public-key
time offset relative to the client clock. cryptosystems is that knowledge of the public key and
ciphertext does not compromise the private key or plain-
As the synchronization subnet, evolves in response to
text. The user name, address, public key and related values
server failures and restarts, prevailing network delay paths,
are stored in a database maintained by directory servers.
etc., the authentication hierarchy evolves in response. It
may happen that protocol operations can proceed normally; In order to minimize the vulnerability to attack, public-key
but, due to temporary lack of cryptographic key material, cryptography requires every message to be individually
for example, individual servers may become isolated from signed using the server private key. The same technique
their sources, even if the timekeeping data itself remains can be used to construct a digital signature for a unit of data
valid. If a server ordinarily synchronized via authenticated or a message and later verify the signature. In order to min-
sources loses contact with all of these sources, it coasts at imize the processing required, the server constructs a digest
2
of the message contents using a one-way hash function must have enforceable lifetimes. Valid keys should be
such as MD5, then encrypts it using RSA and the server replaced from time to time, in order to frustrate potential
private key. The result is stored in the MAC and transmit- cryptanalysis. Once destroyed, a key should never be used
ted with the message. The client constructs the message again. This implies a specific vulnerability to an attack on
digest, then compares it with the MAC decrypted using the the timekeeping system, specifically NTP. If secure time-
server public key. keeping is dependent on reliable authentication and, which
itself requires keys sensitive to time, an interesting circular-
Public/private key pairs are normally generated by the ity results.
server. The public key, together with identification infor-
mation, is signed by one or more trusted agents functioning When a key with enforceable lifetime is created or used for
as notaries, to construct a certificate, which is then submit- cryptographic computations, the results of the computa-
ted to the directory service. Certificates bind the public key tions cannot be validated, unless the entity performing the
and related values to identification data, such as a digitized computations has been correctly synchronized to a source
photograph, handwritten signature or voiceprint. These which has been authenticated by a valid certificate trail.
data are not necessarily secure; only the server private key Thus, a digital signature cannot be generated, unless the
is considered secure, but it is never divulged. In order to server has authentic time. On the other hand, the signature
verify that an information source is authentic and that the can be verified at any time, but validated only when the cli-
source is in fact in possession of the private key, it is neces- ent has authentic time.
sary to verify all notary signatures on the certificate trail as
well. This raises the issue that NTP must function in scenarios
where reliable network timekeeping has not yet been estab-
Constructing the MD5 message digest is a relatively fast lished, or when the certificates have not yet been verified.
operation; for instance, the time to compute a NTP message The most common case occurs when a client is first started
digest on a Hewlett Packard 9000/735 is 31 us and 263 us and before its clock has been set. In this such cases, the
on a Sun Microsystems SPARC 1. However, even when the synchronization and authentication functions must operate
plaintext is a 128-bit MD5 hash, RSA encryption is pain- even before the clock has been reliably set. Thus, any pro-
fully slow. For instance, the mean time to sign a NTP mes- tocols used by NTP itself to initiate cryptographic associa-
sage ranges form 80 ms on a Digital 266-MHz Alpha to 2.1 tions must not depend on prior key exchanges which are
s on a Sun SPARC 1; while the mean time to verify the sig- themselves dependent on synchronized clocks. This design
nature ranges from 7.9 ms on the Alpha to 201 ms on the requirement is unique among all other known network ser-
SPARC 1. While the MD5 running times are independent vices.
of data and key, the RSA running times are highly variable,
depending on the population of one bits in the key and The client operations to synchronize the clock and authenti-
other factors. For example, with random bit strings as keys, cate the servers cannot depend on which of these functions
the verification time on a SPARC 1 ranges from 198 ms to is done first. In the present NTP protocol model, state vari-
273 ms. Variations as large as these would result in unac- ables are developed for each remote server separately,
ceptable loss of accuracy in many NTP applications. including its apparent time offset relative to the local clock.
This process takes from one to several packet exchanges, in
Another approach uses some variant of the Station-to-Sta- order to suppress outlyers and establish reliable offsets.
tion (STS) protocol, such as Photuris to compute a shared While this is going on, the client may be in process of
secret used as a session key. Since the numbers involved retrieving certificates from directory services and verifying
can be very large (512 bits is typical), these operations are signatures. As this process involves only public values, it
slow, but need to be computed only when the keys are can be performed while NTP is collecting data to set the
changed. However, these protocols require persistent state time. Only after reliable server time and authenticated
at the servers, thus are not appropriate for use in NTP cli- server identification have been achieved can the local clock
ent-server and multicast modes with large numbers of serv- be set.
ers and clients. Either the server must be able to regenerate
the session key as each client request is received, or some There is a subtle problem when considering the design of
means must be provided to authenticate the current session secure directory services and related transport protocols.
key with respect to a previously used session key which has Ordinarily, clients of these services assume the various
been cryptographically authenticated. cryptographic keys and certificates have enforceable life-
times; that is, the services will not themselves use keys or
A basic rule in all key distribution and management certificates, unless the lifetimes can be enforced. When
schemes is that cryptographic keys and associated values used with NTP, no assumption can be made about the life-
3
times, since the clocks may not yet be synchronized. In the to one or more trusted agents for signatures, then sends it to
present approach, this does not matter, since determining the directory service for public access. A client authenti-
the local clock offset and authenticating the server are per- cates a server by sending either its name or address,
formed independently. Designers of secure services must depending on how it first learned of its existence, and
be prepared to deliver the data requested, even if unable to retrieves the public key and related certificate media. It
securely authenticate it at the moment. then verifies the public key using the certificates as neces-
sary. This need be done only once, after which the public
NTP VERSION 4 SECURITY MODEL AND
key can be cached at the client. These operations use stan-
AUTHENTICATION SCHEME
dard procedures, so are not discussed further here.
The Version 4 security model and authentication scheme is
designed to be backwards compatible with previous ver- The scheme works differently for peer-peer, client-server
sions, except in a few unavoidable cases. The model adds and multicast modes; however, the message digest is calcu-
new features that provide for a self-keyed style of operation lated in the same way in all modes. The MD5 algorithm is
in conjunction with new directory and certificate retrieval used to hash the concatenated server private random value,
services now in the planning process in the IETF. The new private key, IP source address, IP destination address and
scheme uses cryptographic message digests in the same MAC key identifier fields. The resulting 16-octet value is
way as the original scheme. The contents of the NTP the session key used to construct the message digest, which
header are hashed with keyed MD5 and a 16-octet session is computed as in the original scheme. Note that the new
key, yielding a 16-octet message digest. The MAC trans- scheme in effect includes all significant fields of the mes-
mitted following the NTP header consists of a four-octet sage, not just the NTP header as in the original scheme, and
key identifier followed by a 16-octet message digest. thus provides additional security.
A client authenticates the server by first obtaining the The scheme adds new key-request and key-response mes-
server name, IP address, public key and related certificate sages to the suite of control messages already defined. The
media. Obtaining the public values may involve additional key-request message sent by a client includes a copy of the
network operations, such as traversing the directory tree, client public key. The key-response message sent by the
decrypting signatures, verifying certificates, etc. In princi- server includes the current session key encrypted first by
ple, provisions must be made to change any of the public the server private key and then by the public key in the key-
values; however, it is anticipated that the need to do this request message. Since the only use of the client public-pri-
will be relatively infrequent and the computational burden vate key pair is to verify and obscure the response, the pub-
will not affect the accuracy of ongoing NTP operations. lic key need not be certificated.
Should any of these values change, the natural result is to The three modes of NTP operation: peer-peer, client-server
fail the authentication test, timeout and terminate the asso- and multicast present quite different security models. In
ciation, then attempt to restart it. peer-peer modes, both peer associations are persistent, so
In the new scheme, each server maintains a private random predistributed session keys cause little additional burden
value which is used together with its private key and other other than as now with the current authentication scheme.
values to generate session keys. The private random value In the current reference implementation, the keys are stored
is replaced at relatively short intervals, such as a day, in a protected file. Presumably, the contents of this file can
depending on the needs of the security model, but never be accessed and updated by means external to the protocol
divulged. The private key is replaced at longer intervals, without impinging on the current NTP protocol specifica-
such as a week, since this requires all clients to indepen- tion or reference implementation. This can be done using
dently verify its authenticity using relatively tedious opera- schemes proposed by the IETF and are not discussed fur-
tions. The RSA public-key cryptosystem is used to encrypt ther here, other than to point out the scheme described
and decrypt data in some messages exchanged between the below for client- server modes can be used as well.
server and its clients. In addition, secure directory services
In client-server mode, the server maintains no per-client
are assumed available from which public keys and certifi-
state between client requests, either for timekeeping data or
cates can be obtained. The mechanisms used to obtain the
cryptographic media. Therefore, the session key must be
public keys and verify the certificates are the subject of cur-
regenerated for each received client request. In order to
rent proposals, but are not discussed further in this paper.
prevent forgery, it must not be possible for an intruder to
A server generates a public-private key pair using algo- eavesdrop on an exchange between a client and a legitimate
rithms well-known in the art. It then generates a certificate server to mimic the key generation process for that client or
binding the public key to identification values and sends it server. The scheme described below, which was originally
4
suggested by Steven Kent of BBN3, requires that the server putes the list. Each time the server uses an entry, it stores
regenerate a secret key upon each message arrival from the the low order four octets of the previous session key in the
client; however, the computations to regenerate the key are key identifier field.
relatively minor. A client authenticates each message relative to the message
First, the client sends a key-request message to the server, that immediately preceded it. It computes the session key
which then generates and encrypts the session key as above and message digest as described above. It then extracts the
and returns it in a key- response message to the client. The low order four octets of the session key and compares with
client decrypts the session key and caches it in its secure the key identifier field in the last message received. If the
database. This method prevents a man-in-the- middle values agree, the current message is considered valid. If
attack, but does consume significant server and client not, a message might have been discarded in transit, so the
resources. However, the exchange needs to be done only client hashes again. This procedure may continue for a
infrequently when the client is first started up and when the fixed number of hashes, following which the client aban-
server private values are changed. Alternatively, if the dan- dons the attempt and sends a key- request message to
ger of a man-in-the-middle attack can be avoided through obtain the current session key.
the use of secure address filtering, for example, the session The session key applies only to the current message and is
key can be considered a public value with controlled scope. not useful for any subsequent message. However, an
In this case, the session key can be transmitted as plaintext, intruder (man-in-the-middle) could intercept a query
since it is not useful for any other source address. response message and learn the current session key, from
The cached session key is used by the client to compute the which all session keys used prior to this message can be
message digest in the usual way. The server recomputes the determined. While these session keys will not be used
session key as each request is received. This is done exactly again, it is conceivable, although unlikely, that the intruder
as above when generating the hash returned to the client as could trick a client who has not yet heard a prior message
the session key. The session key and message digest are into accepting a bogus message. In order to succeed, the
then computed as above. The session key is unique to the intruder would have to impersonate at least the IP source
particular server and client involved and need not be address of any messages it sends to the unsuspecting client
retained by the server between requests. Note that an which, although possible, is unlikely.
intruder cannot modify and replay a message as valid, even It is important to understand that the session key obtained
if it forges the source address, since only the server and cli- in this way is not a secret in the ordinary sense, since any
ent can construct the correct session key. client can obtain it or forge it without cryptographic
In multicast mode, servers send messages at a controlled authentication or encryption of any kind. Its purpose is to
rate and respond only to key-request messages. A server provide a shared value dependent upon a secret value held
first calculates a list of 16-octet session keys for later use, only by the server and used in subsequent steps to generate
as in the S/KEY system [2]. It first computes the session the message digest of each transmitted message. Thus,
key as in client-server mode and uses this as the first entry while the shared value can be obtained by any intruder and
in the list. For this purpose, the IP source and destination used subsequently as a key to generate a message digest,
addresses are the server address and assigned multicast the actual secret used to generate the shared value is not
group address, respectively, and the key identifier is a ran- divulged and, presumably, cannot be obtained by an
dom roll. The low order four octets of this session key are intruder. Neither can future secrets be predicted by an
used to generate the next session key and become the key intruder. In this sense, the scheme has perfect forward
identifier associated with that key. The server uses the same secrecy.
IP addresses and this session key to generate the next ses- SUMMARY AND CONCLUSIONS
sion key. Continuing in this way, the server fills the list,
which may h