J175 DARPA Progress Report 2000

Survivable Real-Time Network Services

Objectives

Develop robust heuristic algorithms for the automatic configuration and source authentication of distributed algorithms in very large networks.

Approach

When networks with many thousands and even millions of servers and clients become fragmented, some distributed network services, such as authentication and time synchronization, may be degraded or lost. Our approach to survivability in such scenarios is based on the ability of these services to survive by automatically reconfiguring substitute servers in surviving fragments, then coalescing them with other servers when connectivity is restored.

We are specifically concerned with authenticated network time synchronization, since this service is fundamental to secure timestamping and transaction ordering. The project extends the autoconfigure and autokey technology developed in previous work to very large networks that may suffer significant damage due to failures and hostile attack. Autoconfigure uses Internet multicasting and heuristic algorithms to discover and configure redundant, diverse time servers in a topology optimized for a constrained accuracy metric. Autokey uses backward hashing and timestamped public-key signatures to provide secure source authentication with automatic and dynamic key management and distribution.

Recent Accomplishments

  1. An informal description of the beta version of the autokey protocol and algorithms, as well as a security vulnerability analysis, has been published as a technical report. Subsequently, major modifications intended to provide completely automatic key generation, refreshment, distribution, installation and verification were developed for version 1 of the protocol. An Internet Draft on the current protocol specification has been provided to the IETF for review. Both the report and draft can be found via the Project URL along with all previously published work.

  2. Version 1 of the autokey protocol and algorithms for the Network Time Protocol (NTP) Version 4 has been implemented, tested and deployed in our DCnet experiment network, the CAIRN testbed routers in the US and UK, and selected time servers operated by NIST. One of the more interesting NTPv4 deployments is operated by the Australian government in Antarctica. The NTP software distribution can be found at www.ntp.org along with background information, briefing slides and software documentation.

  3. An experiment involving four CAIRN routers and several DCnet routers is in progress to assess the resiliency of the autokey protocol to intermittent failures and intentional misconfiguration, as well as replay and clogging attacks. All routers participating in the experiment are equipped with nanosecond-resolution kernels and radio or satellite receivers so that timekeeping errors can be precisely quantified and calibrated.

  4. In order to study the behavior of very large networks (10,000 nodes or more), a special purpose simulator and random topology generator based on the Waxman model has been constructed. The generator routines have recently been enhanced to produce fractile-like topologies more typical of the current Internet. In shakedown cruises simulations have been run with as many as 3,500 nodes using both unicast and multicast distance vector routing protocols.

  5. As NTP is the principal tool used to evaluate the performance of autokey and autoconfigure, a continuing effort is under way to improve the performance of the NTP protocol and algorithms. In particular, this has led to an improvement in performance of the synchronized clock to the level of nanoseconds in time and nanoseconds per second in stability. An RFC has been published on an API for the nanokernel algorithms. It has been implemented both in NTPv4 and in the FreeBSD platform now popular within the CAIRN community. Both the RFC and nanokernel software distribution can be found via the Project URL along with all previously published work.

Current Plan

  1. The autoconfigure protocol and manycast algorithms, while refined, simulated and evaluated, have not yet been completely implemented in NTP and tested under real world conditions. These algorithms must be augmented with additional span-limited and implosion-resistant mechanisms to be truly effective in damaged networks. Our planned approach is based on a statistical whisper campaign between candidate servers.

  2. The current autokey security model and authentication scheme will be extended to operate with Internet certificate authorities, including Secure DNS and related ubiquitous services as they become available.

  3. Incorporate the new algorithms in the NTPv4 software distribution for Unix, Windows and VMS. Test and evaluate them in the context of the CAIRN testbed and local experiment networks, then in NIST and USNO subnetworks and, eventually, the general Internet population.

  4. Develop formal specifications for the NTPv4 and Autokey protocols as extensions of the current NTPv3 specification RFC-1305. Update the current NTP Control and Monitoring Protocol and SNMP MIB to include the new features.

  5. Continue investigation of the behavior of very large networks, in particular, extend the algorithm set to include the autoconfigure model in the context of core-centric multicasting protocols.

Technology Transition

  1. Research findings, including results from analysis, simulation and experiment, as well as hardware and software descriptions, will be published in the open scientific literature and on the web.

  2. Current status and briefing presentations will be made available on the web.

  3. Sources and documentation for designated operating system software deliverables, including the Network Time Protocol Version 4 and Autokey Protocol Version 1, will be freely available from Internet archive servers.

  4. Hardware documentation in the form of circuit schematics, PCB artwork and drill templates will be freely available from Internet archive servers.

  5. Protocol specifications and associated documentation will be published in RFC form for consideration by the IETF standards apparatus.

  6. Research findings will be presented to the DoD and NGI community in regular meetings sponsored wholly or in part by DARPA.

  7. Assistance will be provided to government agencies of the US and other countries in setting up and operating networks of NTP servers.
David L. Mills (mills@udel.edu)