Roughtime
draft-roughtime-aanchal-00
This document is an Internet-Draft (I-D).
Anyone may submit an I-D to the IETF.
This I-D is not endorsed by the IETF and has no formal standing in the
IETF standards process.
The information below is for an old version of the document.
| Document | Type |
This is an older version of an Internet-Draft whose latest revision state is "Replaced".
|
|
|---|---|---|---|
| Authors | Aanchal Malhotra , Adam Langly, Watson Ladd | ||
| Last updated | 2019-02-08 | ||
| Replaced by | draft-ietf-ntp-roughtime | ||
| RFC stream | Internet Engineering Task Force (IETF) | ||
| Formats | |||
| Additional resources | Mailing list discussion | ||
| Stream | WG state | Candidate for WG Adoption | |
| Document shepherd | (None) | ||
| IESG | IESG state | I-D Exists | |
| Consensus boilerplate | Unknown | ||
| Telechat date | (None) | ||
| Responsible AD | (None) | ||
| Send notices to | (None) |
draft-roughtime-aanchal-00
Internet Engineering Task Force A. Malhotra
Internet-Draft Boston University
Intended status: Informational A. Langly
Expires: August 12, 2019 Google
W. Ladd
Cloudflare
February 8, 2019
Roughtime
draft-roughtime-aanchal-00
Abstract
This document specifies Roughtime - a protocol that aims to achieve
rough time synchronization while detecting servers that provide
inaccurate time and providing cryptographic proof of their
malfeasance.
Status of This Memo
This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet-
Drafts is at https://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
This Internet-Draft will expire on August 12, 2019.
Copyright Notice
Copyright (c) 2019 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(https://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of
Malhotra, et al. Expires August 12, 2019 [Page 1]
Internet-Draft Roughtime February 2019
the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License.
1. Motivation
Time synchronization is essential to Internet security as many
security protocols and other applications require synchronization
[RFC7384][MCBG]. Unfortunately widely deployed protocols such as the
Network Time Protocol (NTP) [RFC5905] lack essential security
features, and even newer protocols like Network Time Security (NTS)
[I-D.ietf-ntp-using-nts-for-ntp] fail to ensure that the servers
behave correctly. Authenticating time servers prevents network
adversaries from modifying time packets. An authenticated time
server still has full control over the contents of time packet and
may go rogue. Roughtime protocol provides cryptographic proof of
malfeasance, enabling clients to detect and prove to a third party
server's attempts to influence the time a client computes.
+--------------+----------------------+-----------------------------+
| Protocol | Authenticated Server | Server Malfeasance Evidence |
+--------------+----------------------+-----------------------------+
| NTP, Chronos | N | N |
| NTP-MD5 | Y* | N |
| NTP-Autokey | Y** | N |
| NTS | Y | N |
| Roughtime | Y | Y |
+--------------+----------------------+-----------------------------+
Security Properties of current protocols
Table 1
Y* For security issues with symmetric-key based NTP-MD5
authentication, please refer to Message Authentication Code for the
Network Time Protocol draft [I-D.ietf-ntp-mac]
Y** For security issues with Autokey Public Key Authentication, refer
to [Autokey]
2. Requirements Language
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
"OPTIONAL" in this document are to be interpreted as described in BCP
14 [RFC2119] [RFC8174] when, and only when, they appear in all
capitals, as shown here.
Malhotra, et al. Expires August 12, 2019 [Page 2]
Internet-Draft Roughtime February 2019
3. Protocol Overview
Roughtime is a protocol for rough time synchronization that enables
clients to provide cryptographic proof of server malfeasance. It
does so by having responses from servers include a signature with a
certificate rooted in long term public/private key pair over a
portion of the initial request, thus providing cryptographic proof
that the timestamp was issued after previous responses and before
future ones.
Single server mode: At its most basic level, Roughtime is a one round
protocol in which a completely fresh client requests the current time
and the server sends a signed response. The response inculdes a
timestamp (the number of microseconds since the Unix epoch) and a
radius (in microseconds) used to indicate the servers certainty about
the reported time. For example, a radius of 1,000,000 microseconds
means the server is absolutely confident that the true time is within
one second of the reported time.
The server proves freshness of its response as follows: The request
contains a random challenge. The server incorporates the challenge
into its signed response so that its needed to verify the signature.
This proves that the signed response could only have been generated
after the challenge was issued if the challenge has sufficient
entropy.
Chaining multiple servers: For subsequent requests, the client
generates its nonce by hashing the reply from the first server with a
random value. This proves that the nonce was created after the reply
from the first server. It sends that to the second server and
receives a signature from it covering that nonce and the time from
the second server.
Cryptographic proof of misbehavior: If the time from the second
server is before the first, then the client has proof of misbehavior;
the reply from the second server implicitly shows that it was created
later because of the way that the client constructed the nonce. If
the time from the second server is after, then the client can contact
the first server again and get a signature that was provably created
afterwards, but with an earlier timestamp.
With only two servers, the client can end up with proof that
something is wrong, but no idea what the correct time is. But with
half a dozen or more independent servers, the client will end up with
chain of proof of any servers misbehavior, signed by several others,
and (presumably) enough accurate replies to establish what the
correct time is. Furthermore this proof may be validated by third
Malhotra, et al. Expires August 12, 2019 [Page 3]
Internet-Draft Roughtime February 2019
parties ultimately leading to a revocation of trust in the
misbehaving server.
4. Message Format
A Roughtime packet is a UDP packet whose contents are interpreted as
a map from uint32s to strings of bytes. The byte strings must all
have lengths a multiple of four. All uint32 are encoded with the
least significant byte first. The keys of this map are called tags,
and we speak of the value of a tag as the string of bytes it is
mapped to.
A Roughtime packet is serialized as follows: First there is a header,
The first four bytes in the header are the uint32 number of tags N,
and hence of (tag, value) pairs. 4*(N-1) bytes are offsets, each
offset a uint32. The last 4*N bytes are the tags.
Tags are in ascending order, and no tag can be repeated. Offsets are
all a multiple of four and MUST be strictly increasing. The offset
array is considered to have a not explicitly encoded value of 0 as
its zeroeth entry.
Immediately following the header is a concatenation of all the
strings. The first post-header byte is at offset 0, and the end of
the final byte string is indicated by the end of the packet. The ith
byte string ends at offset[i+1]-1, counting of course from 0, and
begins at offset[i]. It is the value associated to the ith tag.
This encoding may be recursive: a value may be said to be in
Roughtime format and thus have a header, etc. Tags may be listed as
four ASCII characters [RFC0020]. In this case the tag when
serialized will be those four ASCII characters. Exempli gratia NONC
would be the numeric value 0x434e4f4e. They may also be listed as
fewer then four ASCII characters with hex escape codes at the end.
5. Protocol
5.1. Queries
A query is a Roughtime packet with the tag NONC. The contents of
NONC are 64 bytes. The request packet MUST be a minimum of 1024
bytes. To attain this size the tag PAD\xff MAY be added at the end
of the packet with a conent of all zeros. Other tags MUST be ignored
by the server. Future versions may specify additional tags and their
semantics, so clients MUST NOT add other tags.
Malhotra, et al. Expires August 12, 2019 [Page 4]
Internet-Draft Roughtime February 2019
5.2. Responses
A response contains the following tags: SREP, SIG\x00, CERT, INDX,
PATH, SREP value is itself in Roughtime format that contains the
folowing tags: ROOT, MIDP, RADI. SIG\x00 is an Ed25519 signature
[RFC8032] over the SREP value using the public key contained in CERT
as explained later.
CERT in Roughtime format and contains the following tags: DELE,
SIG\x00. This SIG\x00 is an Ed25519 signature over DELE using the
long term public key of the server. DELE is itself in Roughtime
format containing tags MINT, MAXT, PUBK.
5.2.1. SREP
ROOT contains the root hash value of a Merkle tree using SHA512 as
described when we reach the PATH and INDX blocks MIDP contains an
uint64 value consisting of the number of microseconds since the Unix
epoch in the smeared scale. RADI contains the server's estimate of
the accuracy of MIDP. Servers MUST ensure the true time is within
(MIDP-RADI, MIDP+RADI) at the time they compose the response packet.
5.2.2. DELE
MINT is the minimum uint64 timestamp at which the key in PUBK is
trusted to begin signing time. MIDP > MINT for validity. MAXT is
the maximum uint64 timestamp at which PUBK may sign. MIDP < MAXT for
validity. PUBK is a temporary Ed25519 public key. The use of this
field is to enable seperation of a root public key from keys on
devices exposed to the public Internet.
5.2.3. INDX and PATH
INDX is a uint32 determining the position of NONC in a Merkle tree.
PATH determines the values to be hashed with the running hash as one
ascends the tree. The final value MUST be equal to ROOT. PATH is a
multiple of 64 bytes long. One starts by computing the hash of the
NONC value from the request, with \x00 preappended. Then one walks
from the least significant bit of INDX to the most significant bit,
and also walks towards the end of PATH. If PATH ends then the
remaining bits of the INDX MUST be all zero. This indicates the
termination of the walk. If the current bit is 0, one hashes \x01,
the current hash, and the value from PATH. If the current bit is 1
one hashes \x01, the value from PATH, and the current HASH. This
enables servers to batch signing when busy.
Malhotra, et al. Expires August 12, 2019 [Page 5]
Internet-Draft Roughtime February 2019
5.3. Validity of response
A client MUST check the following properties when it receives a
response. We assume the long term server public key is known to the
client through other means.
The signature in CERT was made with the long-term key of the
server
The DELE timestamps and the MIDP value are consistent
The INDX and PATH values prove NONC was included in the Merkle
tree with value ROOT
The signature of SREP in SIG\x00 validates with the public key in
DELE
A response that passes these checks is said to be valid. Validity of
a response does not prove the time is correct, but merely that the
server signed it, and more specifically began to compute the
signature at a time in between (MIDP-RADI, MIDP+RADI).
6. The smeared scale
Every day in Roughtime has 86400 seconds. A day without a leap
second is a day where all seconds are SI seconds. A day with a
positive leap second is one where every second is 86401/86400 SI
seconds long. A day with a negative leap second is a day where every
second is 86399/86400 SI seconds long. Days begin and end at noon,
and when a leap-second is added or removed from UTC it is smeared out
over the course of a day.
Arithemtic on the smeared scale requires knowing when the seconds
changed length and thus requires a leap second table.
7. Cheater detection
A chain of responses is a series of responses where the SHA-512 hash
of the preceding response H, is concatenated with a 64 bit blind X,
and then SHA-512(H, X) is the NONC used in the subsequent response.
These may be represented in JSON as TBD
A pair of responses (r_1, r_2) is invalid if MIDP_1-RADI_1 >
MIDP_2+RADI_2. A chain of longer length is invalid if for any i, j
such that i < j, (r_i, r_j) is an invalid pair.
Invalidity of a chain is proof that causality has been violated if
all servers were reporting correct time. An invalid chain where all
Malhotra, et al. Expires August 12, 2019 [Page 6]
Internet-Draft Roughtime February 2019
individual responses are valid is cryptographic proof of malfeasance
of at least one server: if all servers had the correct time in the
chain, causality would imply that MIDP_1-RADI_1 < MIDP_2+RADI_2.
8. Grease
Servers MAY send back a fraction of responses that are syntactically
invalid or contain invalid signatures as well as incorrect times.
Clients MUST properly reject such responses.
9. Roughtime Servers
The below list contains a list of servers with their public keys in
either Base64 or hexidecimal format.
roughtime.int08h.com:2002;
016e6e0284d24c37c6e4d7d8d5b4e1d3c1949ceaa545bf875616c9dce0
roughtime.cloudflare.com:2002; gD63hSj3ScS+wuOeGrubXlq35N1c5Lby/
S+T7MNTjxo=
roughtime.sandbox.google.com:2002;
etPaaIxcBMY1oUeGpwvPMCJMwlRVNxv51KK/tktoJTQ=
10. Acknowledgements
TBD
11. IANA Considerations
This memo includes no request to IANA.
12. Security Considerations
This protocol will not survive the advent of quantum computers.
Currently only one signature scheme is supported. Maintaining a list
of trusted servers and adjudicating violations of the rules by
servers are not discussed in this document and are essential for
security. Arithmetic on the adjusted timescale is interesting with
intervals, and this may impact the interpretation of the MAXT and
MINT fields. Servers carry out a significant amount of computation
in response to clients, and thus may experience vulnerability to
denial of service attacks.
This protocol does not provide any confidentiality, and given the
nature of timestamps such impact is minor. The compromise of a
PUBK's private key, even past MAXT, is a problem as the private key
Malhotra, et al. Expires August 12, 2019 [Page 7]
Internet-Draft Roughtime February 2019
can be used to sign invalid times that are in the range MINT to MAXT,
and thus violate the good behavior guarantee of the server.
13. Privacy Considerations
This protocol is designed to obscure all client identifiers. Servers
necessarily have persistent long term identities essential to
enforcing correct behavior.
14. Informative References
[Autokey] Rottger, S., "Analysis of the NTP Autokey Procedures",
2012, <https://zero-entropy.de/autokey_analysis.pdf>.
[I-D.ietf-ntp-mac]
Malhotra, A. and S. Goldberg, "Message Authentication Code
for the Network Time Protocol", draft-ietf-ntp-mac-06
(work in progress), January 2019.
[I-D.ietf-ntp-using-nts-for-ntp]
Franke, D., Sibold, D., Teichel, K., Dansarie, M., and R.
Sundblad, "Network Time Security for the Network Time
Protocol", draft-ietf-ntp-using-nts-for-ntp-16 (work in
progress), February 2019.
[MCBG] Malhotra, A., Cohen, I., Brakke, E., and S. Goldberg,
"Attacking the Network Time Protocol", 2015,
<https://eprint.iacr.org/2015/1020>.
[RFC0020] Cerf, V., "ASCII format for network interchange", STD 80,
RFC 20, DOI 10.17487/RFC0020, October 1969,
<https://www.rfc-editor.org/info/rfc20>.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119,
DOI 10.17487/RFC2119, March 1997,
<https://www.rfc-editor.org/info/rfc2119>.
[RFC5280] Cooper, D., Santesson, S., Farrell, S., Boeyen, S.,
Housley, R., and W. Polk, "Internet X.509 Public Key
Infrastructure Certificate and Certificate Revocation List
(CRL) Profile", RFC 5280, DOI 10.17487/RFC5280, May 2008,
<https://www.rfc-editor.org/info/rfc5280>.
[RFC5905] Mills, D., Martin, J., Ed., Burbank, J., and W. Kasch,
"Network Time Protocol Version 4: Protocol and Algorithms
Specification", RFC 5905, DOI 10.17487/RFC5905, June 2010,
<https://www.rfc-editor.org/info/rfc5905>.
Malhotra, et al. Expires August 12, 2019 [Page 8]
Internet-Draft Roughtime February 2019
[RFC7384] Mizrahi, T., "Security Requirements of Time Protocols in
Packet Switched Networks", RFC 7384, DOI 10.17487/RFC7384,
October 2014, <https://www.rfc-editor.org/info/rfc7384>.
[RFC8032] Josefsson, S. and I. Liusvaara, "Edwards-Curve Digital
Signature Algorithm (EdDSA)", RFC 8032,
DOI 10.17487/RFC8032, January 2017,
<https://www.rfc-editor.org/info/rfc8032>.
[RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC
2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174,
May 2017, <https://www.rfc-editor.org/info/rfc8174>.
Authors' Addresses
Aanchal Malhotra
Boston University
111 Cummington Mall
Boston 02215
USA
Email: aanchal4@bu.edu
Adam Langly
Google
Watson Ladd
Cloudflare
101 Townsend St
San Francisco
USA
Email: watson@cloudflare.com
Malhotra, et al. Expires August 12, 2019 [Page 9]