< draft-roughtime-aanchal-02.txt   draft-roughtime-aanchal-03.txt >
Internet Engineering Task Force A. Malhotra Internet Engineering Task Force A. Malhotra
Internet-Draft Boston University Internet-Draft Boston University
Intended status: Informational A. Langley Intended status: Informational A. Langley
Expires: November 28, 2019 Google Expires: January 9, 2020 Google
W. Ladd W. Ladd
Cloudflare Cloudflare
May 27, 2019 July 8, 2019
Roughtime Roughtime
draft-roughtime-aanchal-02 draft-roughtime-aanchal-03
Abstract Abstract
This document specifies Roughtime - a protocol that aims to achieve This document specifies Roughtime - a protocol that aims to achieve
rough time synchronization while detecting servers that provide rough time synchronization while detecting servers that provide
inaccurate time and providing cryptographic proof of their inaccurate time and providing cryptographic proof of their
malfeasance. malfeasance.
Status of This Memo Status of This Memo
skipping to change at page 1, line 36 skipping to change at page 1, line 36
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet- working documents as Internet-Drafts. The list of current Internet-
Drafts is at https://datatracker.ietf.org/drafts/current/. Drafts is at https://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
This Internet-Draft will expire on November 28, 2019. This Internet-Draft will expire on January 9, 2020.
Copyright Notice Copyright Notice
Copyright (c) 2019 IETF Trust and the persons identified as the Copyright (c) 2019 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents Provisions Relating to IETF Documents
(https://trustee.ietf.org/license-info) in effect on the date of (https://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License. described in the Simplified BSD License.
1. Motivation Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2
2. Requirements Language . . . . . . . . . . . . . . . . . . . . 4
3. Protocol Overview . . . . . . . . . . . . . . . . . . . . . . 4
4. The guarantee . . . . . . . . . . . . . . . . . . . . . . . . 5
5. Message Format . . . . . . . . . . . . . . . . . . . . . . . 5
5.1. Data Types . . . . . . . . . . . . . . . . . . . . . . . 6
5.1.1. uint32 . . . . . . . . . . . . . . . . . . . . . . . 6
5.1.2. uint64 . . . . . . . . . . . . . . . . . . . . . . . 6
5.1.3. Tag . . . . . . . . . . . . . . . . . . . . . . . . . 6
5.1.4. Timestamp . . . . . . . . . . . . . . . . . . . . . . 7
5.2. Header . . . . . . . . . . . . . . . . . . . . . . . . . 7
6. Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . 7
6.1. Requests . . . . . . . . . . . . . . . . . . . . . . . . 7
6.2. Responses . . . . . . . . . . . . . . . . . . . . . . . . 8
6.3. The Merkle Tree . . . . . . . . . . . . . . . . . . . . . 9
6.3.1. Root value validity check algorithm . . . . . . . . . 10
6.4. Validity of response . . . . . . . . . . . . . . . . . . 10
7. Cheater Detection . . . . . . . . . . . . . . . . . . . . . . 10
8. Grease . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
9. Roughtime Servers . . . . . . . . . . . . . . . . . . . . . . 11
10. Trust anchors and policies . . . . . . . . . . . . . . . . . 12
11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 12
12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 12
12.1. Service Name and Transport Protocol Port Number Registry 12
12.2. Roughtime Tag Registry . . . . . . . . . . . . . . . . . 13
13. Security Considerations . . . . . . . . . . . . . . . . . . . 13
14. Privacy Considerations . . . . . . . . . . . . . . . . . . . 14
15. References . . . . . . . . . . . . . . . . . . . . . . . . . 14
15.1. Normative References . . . . . . . . . . . . . . . . . . 14
15.2. Informative References . . . . . . . . . . . . . . . . . 15
Appendix A. Terms and Abbreviations . . . . . . . . . . . . . . 16
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 16
1. Introduction
Time synchronization is essential to Internet security as many Time synchronization is essential to Internet security as many
security protocols and other applications require synchronization security protocols and other applications require synchronization
[RFC7384][MCBG]. Unfortunately widely deployed protocols such as the [RFC7384] [MCBG]. Unfortunately widely deployed protocols such as
Network Time Protocol (NTP) [RFC5905] lack essential security the Network Time Protocol (NTP) [RFC5905] lack essential security
features, and even newer protocols like Network Time Security (NTS) features, and even newer protocols like Network Time Security (NTS)
[I-D.ietf-ntp-using-nts-for-ntp] fail to ensure that the servers [I-D.ietf-ntp-using-nts-for-ntp] fail to ensure that the servers
behave correctly. Authenticating time servers prevents network behave correctly. Authenticating time servers prevents network
adversaries from modifying time packets, but an authenticated time adversaries from modifying time packets, but an authenticated time
server still has full control over the contents of time packet and server still has full control over the contents of the time packet
may go rogue. The Roughtime protocol provides cryptographic proof of and may go rogue. The Roughtime protocol provides cryptographic
malfeasance, enabling clients to detect and prove to a third party proof of malfeasance, enabling clients to detect and prove to a third
server's attempts to influence the time a client computes. party a server's attempts to influence the time a client computes.
+--------------+----------------------+-----------------------------+ +--------------+----------------------+-----------------------------+
| Protocol | Authenticated Server | Server Malfeasance Evidence | | Protocol | Authenticated Server | Server Malfeasance Evidence |
+--------------+----------------------+-----------------------------+ +--------------+----------------------+-----------------------------+
| NTP, Chronos | N | N | | NTP, Chronos | N | N |
| NTP-MD5 | Y* | N | | NTP-MD5 | Y* | N |
| NTP-Autokey | Y** | N | | NTP-Autokey | Y** | N |
| NTS | Y | N | | NTS | Y | N |
| Roughtime | Y | Y | | Roughtime | Y | Y |
+--------------+----------------------+-----------------------------+ +--------------+----------------------+-----------------------------+
Security Properties of current protocols Security Properties of current protocols
Table 1 Table 1
Y* For security issues with symmetric-key based NTP-MD5 Y* For security issues with symmetric-key based NTP-MD5
authentication, please refer to Message Authentication Code for the authentication, please refer to RFC 8573 [RFC8573].
Network Time Protocol draft [I-D.ietf-ntp-mac]
Y** For security issues with Autokey Public Key Authentication, refer Y** For security issues with Autokey Public Key Authentication, refer
to [Autokey] to [Autokey].
More specifically, More specifically,
If a server's timestamps do not fit into the time context of other o If a server's timestamps do not fit into the time context of other
servers' responses, then a Roughtime client can cryptographically servers' responses, then a Roughtime client can cryptographically
prove this misbehaviour to third parties. This helps detect "bad" prove this misbehavior to third parties. This helps detect "bad"
servers. servers.
A Roughtime client can roughly detect (with no absolute guarantee) o A Roughtime client can roughly detect (with no absolute guarantee)
a delay attack [DelayAttacks] but can not cryptographically prove a delay attack [DelayAttacks] but can not cryptographically prove
this to a third party. However, the absence of proof of this to a third party. However, the absence of proof of
malfeasance SHOULD not be considered a proof of absence of malfeasance should not be considered a proof of absence of
malfeasance. So Roughtime SHOULD not be used as a witness that a malfeasance. So Roughtime should not be used as a witness that a
server is overall "good". server is overall "good".
Note that the delay attacks cannot be detected/stopped by any o Note that delay attacks cannot be detected/stopped by any
protocol. Delay attacks can not, however, undermine the security protocol. Delay attacks can not, however, undermine the security
guarantees provided by Roughtime. guarantees provided by Roughtime.
o Although delay attacks cannot be prevented, they can be limited to
a predetermined upper bound. This can be done by defining a
maximal tolerable Round Trip Time (RTT) value, MAX-RTT, that a
Roughtime client is willing to accept. A Roughtime client can
measure the RTT of every request-response handshake and compare it
to MAX-RTT. If the RTT exceeds MAX-RTT, the corresponding server
is assumed to be a falseticker. When this approach is used the
maximal time error that can be caused by a delay attack is MAX-
RTT/2. It should be noted that this approach assumes that the
nature of the system is known to the client, including reasonable
upper bounds on the RTT value.
2. Requirements Language 2. Requirements Language
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
"OPTIONAL" in this document are to be interpreted as described in BCP "OPTIONAL" in this document are to be interpreted as described in BCP
14 [RFC2119] [RFC8174] when, and only when, they appear in all 14 [RFC2119] [RFC8174] when, and only when, they appear in all
capitals, as shown here. capitals, as shown here.
3. Protocol Overview 3. Protocol Overview
Roughtime is a protocol for rough time synchronization that enables Roughtime is a protocol for rough time synchronization that enables
clients to provide cryptographic proof of server malfeasance. It clients to provide cryptographic proof of server malfeasance. It
does so by having responses from servers include a signature with a does so by having responses from servers include a signature with a
certificate rooted in long term public/private key pair over a certificate rooted in a long-term public/private key pair over a
portion of the initial request, thus providing cryptographic proof value derived from a nonce provided by the client in its request.
that the timestamp was issued after previous responses and before This provides cryptographic proof that the timestamp was issued after
future ones. the server received the client's request. The derived value included
in the server's response is the root of a Merkle tree which includes
the hash of the client's nonce as the value of one of its leaf nodes.
This enables the server to amortize the relatively costly signing
operation over a number of client requests.
Single server mode: At its most basic level, Roughtime is a one round Single server mode: At its most basic level, Roughtime is a one round
protocol in which a completely fresh client requests the current time protocol in which a completely fresh client requests the current time
and the server sends a signed response. The response includes a and the server sends a signed response. The response includes a
timestamp (the number of microseconds since the Unix epoch) and a timestamp and a radius used to indicate the server's certainty about
radius (in microseconds) used to indicate the server's certainty the reported time. For example, a radius of 1,000,000 microseconds
about the reported time. For example, a radius of 1,000,000 means the server is absolutely confident that the true time is within
microseconds means the server is absolutely confident that the true one second of the reported time.
time is within one second of the reported time.
The server proves freshness of its response as follows: The request The server proves freshness of its response as follows: The client's
contains a random challenge. The server incorporates the challenge request contains a nonce. The server incorporates the nonce into its
into its signed response so that its needed to verify the signature. signed response so that the client can verify the server's signatures
This proves that the signed response could only have been generated covering the nonce issued by the client. Provided that the nonce has
after the challenge was issued if the challenge has sufficient sufficient entropy, this proves that the signed response could only
entropy. have been generated after the nonce.
Chaining multiple servers: For subsequent requests, the client Chaining multiple servers: For subsequent requests, the client
generates its nonce by hashing the reply from the first server with a generates a new nonce by hashing the reply from the previous server
random value. This proves that the nonce was created after the reply with a random value (a blind). This proves that the nonce was
from the first server. It sends that to the second server and created after the reply from the previous server. It sends the new
receives a signature from it covering that nonce and the time from nonce in a request to the next server and receives a response that
the second server. includes a signature covering the nonce.
Cryptographic proof of misbehavior: If the time from the second Cryptographic proof of misbehavior: If the time from the second
server is before the first, then the client has proof of misbehavior; server is before the first, then the client has proof that at least
the reply from the second server implicitly shows that it was created one of the servers is misbehaving; the reply from the second server
later because of the way that the client constructed the nonce. If implicitly shows that it was created later because of the way that
the time from the second server is after, then the client can contact the client constructed the nonce. If the time from the second server
the first server again and get a signature that was provably created is too far in the future, the client can contact the first server
afterwards, but with an earlier timestamp. again with a new nonce generated from the second server's response
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 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 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 half a dozen or more independent servers, the client will end up with
chain of proof of any server's misbehavior, signed by several others, chain of proof of any server's misbehavior, signed by several others,
and (presumably) enough accurate replies to establish what the and (presumably) enough accurate replies to establish what the
correct time is. Furthermore this proof may be validated by third correct time is. Furthermore, this proof may be validated by third
parties ultimately leading to a revocation of trust in the parties ultimately leading to a revocation of trust in the
misbehaving server. misbehaving server.
4. The guarantee 4. The guarantee
A Roughtime response to a query sent at t_1, received at t_2, and A Roughtime server guarantees that a response to a query sent at t_1,
with timestamp t_3 is guaranteed to have been created between the received at t_2, and with timestamp t_3 has been created between the
transmission of the query and its reception. If t_3 is not within transmission of the query and its reception. If t_3 is not within
that interval, a server inconsistency may be detected and used to that interval, a server inconsistency may be detected and used to
impeach the server. The use of such a guarantee in synchronization impeach the server. The use of such a guarantee in synchronization
is currently beyond the grasp of this document. is currently beyond the grasp of this document.
5. Message Format 5. Message Format
A uint32 is a 32 bit unsigned integer. It is serialized in bytes Roughtime messages are maps consisting of one or more (tag, value)
with the least significant byte first. A uint64 is a 64 bit unsigned pairs. They start with a header, which contains the number of pairs,
integer. It is also seralized with the least significant byte first. the tags, and value offsets. The header is followed by a message
8 byte timestamps are described in Section 7. values section which contains the values associated with the tags in
the header. Messages MUST be formatted according to Figure 1 as
described in the following sections.
A Roughtime packet is a UDP packet whose contents are interpreted as Messages may be recursive, i.e. the value of a tag can itself be a
a map from uint32s to strings of bytes. The byte strings must all Roughtime message.
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, 0 1 2 3
The first four bytes in the header are the uint32 number of tags N, 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
and hence of (tag, value) pairs. 4*(N-1) bytes are offsets, each +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
offset a uint32. The last 4*N bytes are the tags. | Number of pairs (uint32) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
. .
. N-1 offsets (uint32) .
. .
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
. .
. N tags (uint32) .
. .
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
. .
. Values .
. .
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Tags are in ascending order, and no tag can be repeated. Offsets are Figure 1: Roughtime Message Format
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 5.1. Data Types
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 5.1.1. uint32
Roughtime format and thus have a header, etc. Tags may be listed as
four ASCII characters [RFC0020]. In this case the tag when A uint32 is a 32 bit unsigned integer. It is serialized with the
serialized will be those four ASCII characters. For example NONC least significant byte first.
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.1.2. uint64
A uint64 is a 64 bit unsigned integer. It is serialized with the
least significant byte first.
5.1.3. Tag
Tags are used to identify values in Roughtime packets. A tag is a
uint32 but may also be listed as a sequence of up to four ASCII
characters [RFC0020]. ASCII strings shorter than four characters can
be unambiguously converted to tags by padding them with zero bytes.
For example, the ASCII string "NONC" would correspond to the tag
0x434e4f4e and "PAD" would correspond to 0x00444150.
5.1.4. Timestamp
A timestamp is a uint64 interpreted in the following way. The most
significant 3 bytes contain the integer part of a Modified Julian
Date (MJD). The least significant 5 bytes is a count of the number
of Coordinated Universal Time (UTC) microseconds [ITU-R_TF.460-6]
since midnight on that day.
The MJD is the number of UTC days since 17 November 1858
[ITU-R_TF.457-2].
Note that, unlike NTP, this representation does not use the full
number of bits in the fractional part and that days with leap seconds
will have more or fewer than the nominal 86,400,000,000 microseconds.
5.2. Header
All Roughtime messages start with a header. The first four bytes of
the header is the uint32 number of tags N, and hence of (tag, value)
pairs. The following 4*(N-1) bytes are offsets, each a uint32. The
last 4*N bytes in the header are tags.
Offsets refer to the positions of the values in the message values
section. All offsets MUST be multiples of four and placed in
increasing order. The first post-header byte is at offset 0. The
offset array is considered to have a not explicitly encoded value of
0 as its zeroth entry. The value associated with the ith tag begins
at offset[i] and ends at offset[i+1]-1, with the exception of the
last value which ends at the end of the packet. Values may have zero
length.
Tags MUST be listed in the same order as the offsets of their values.
A tag MUST NOT appear more than once in a header.
6. Protocol 6. Protocol
6.1. Queries Roughtime messages are sent between clients and servers as UDP
packets. As described in Section 3, clients initiate time
synchronization by sending request packets containing a nonce to
servers who send signed time responses in return.
A query is a Roughtime packet with the tag NONC. The contents of 6.1. Requests
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 A request is a Roughtime message with the tag NONC. The size of the
of the packet with a conent of all zeros. Other tags MUST be ignored request message SHOULD be at least 1024 bytes. To attain this size
by the server. Future versions may specify additional tags and their the PAD tag SHOULD be added to the message. Tags other than NONC
semantics, so clients MUST NOT add other tags. SHOULD be ignored by the server. Responding to requests shorter than
1024 bytes is OPTIONAL and servers MUST NOT send responses larger
than the requests they are replying to.
The value of the NONC tag is a 64 byte nonce. It SHOULD be generated
by hashing a previous Roughtime response message together with a
blind as described in Section 7. If no previous responses are
avaiable to the client, the nonce SHOULD be generated at random.
The PAD tag SHOULD be used by clients to ensure their request
messages are at least 1024 bytes in size. Its value SHOULD be all
zeros.
6.2. Responses 6.2. Responses
A response contains the following tags: SREP, SIG\x00, CERT, INDX, A response contains the tags SREP, SIG, CERT, INDX, and PATH. The
PATH, SREP value is itself in Roughtime format that contains the SIG tag is a signature over the SREP value using the public key
folowing tags: ROOT, MIDP, RADI. SIG\x00 is an Ed25519 signature contained in CERT, as explained below.
[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, The SREP tag contains a time response. Its value is a Roughtime
SIG\x00. This SIG\x00 is an Ed25519 signature over DELE that can be message with the tags ROOT, MIDP, and RADI.
verified using the long term public key of the server. DELE is
itself in Roughtime format containing tags MINT, MAXT, PUBK.
6.2.1. SREP The ROOT tag contains a 32 byte value of a Merkle tree root as
described in Section 6.3.
o ROOT contains the root hash value of a Merkle tree using SHA512 as The MIDP tag value is a timestamp of the moment of processing.
described when we reach the PATH and INDX blocks
o MIDP contains an 8 byte timestamp of the moment of processing The RADI tag value is a uint32 representing the server's estimate of
o RADI is a u32 contains the server's estimate of the accuracy of the accuracy of MIDP in microseconds. Servers MUST ensure that the
MIDP in microseconds. Servers MUST ensure the true time is within true time is within (MIDP-RADI, MIDP+RADI) at the time they compose
(MIDP-RADI, MIDP+RADI) at the time they compose the response the response packet.
packet.
6.2.2. DELE The SIG tag value is a 64 byte Ed25519 signature [RFC8032] over a
signature context concatenated with the entire value of a DELE or
SREP tag. Signatures of DELE tags use the ASCII string "RoughTime v1
delegation signature--" and signatures of SREP tags use the ASCII
string "RoughTime v1 response signature" as signature context. Both
strings include a terminating zero byte.
MINT is the minimum 8 byte timestamp at which the key in PUBK is The CERT tag contains a public-key certificate signed with the
trusted to begin signing time. MIDP > MINT for validity. server's long-term key. Its value is a Roughtime message with the
tags DELE and SIG, where SIG is a signature over the DELE value.
MAXT is the maximum 8 byte timestamp at which PUBK may sign. MIDP The DELE tag contains a delegated public-key certificate used by the
< MAXT for validity. server to sign the SREP tag. Its value is a Roughtime message with
the tags MINT, MAXT, and PUBK. The purpose of the DELE tag is to
enable separation of a long-term public key from keys on devices
exposed to the public Internet.
PUBK is a temporary Ed25519 public key. The use of this field is The MINT tag is the minimum timestamp for which the key in PUBK is
to enable seperation of a root public key from keys on devices trusted to sign responses. MIDP MUST be more than or equal to MINT
exposed to the public Internet. for a response to be considered valid.
6.2.3. INDX and PATH The MAXT tag is the maximum timestamp for which the key in PUBK is
trusted to sign responses. MIDP MUST be less than or equal to MAXT
for a response to be considered valid.
INDX is a uint32 determining the position of NONC in a Merkle tree. The PUBK tag contains a temporary 32 byte Ed25519 public key which is
PATH contains the values to be hashed with the running hash as one used to sign the SREP tag.
ascends the tree. PATH is a multiple of 64 bytes long. The
following algorithm verifies inclusion in the Merkle tree: The INDX tag value is a uint32 determining the position of NONC in
the Merkle tree used to generate the ROOT value as described in
Section 6.3.
The PATH tag value is a multiple of 32 bytes long and represents a
path of 32 byte hash values in the Merkle tree used to generate the
ROOT value as described in Section 6.3. In the case where a response
is prepared for a single request and the Merkle tree contains only
the root node, the size of PATH is zero.
6.3. The Merkle Tree
A Merkle tree is a binary tree where the value of each non-leaf node
is a hash value derived from its two children. The root of the tree
is thus dependent on all leaf nodes.
In Roughtime, each leaf node in the Merkle tree represents the nonce
of one request that a response message is sent in reply to. Leaf
nodes are indexed left to right, beginning with zero.
The values of all nodes are calculated from the leaf nodes and up
towards the root node using the first 32 bytes of the output of the
SHA-512 hash algorithm [RFC6234]. For leaf nodes, the byte 0x00 is
prepended to the nonce before applying the hash function. For all
other nodes, the byte 0x01 is concatenated with first the left and
then the right child node value before applying the hash function.
The value of the Merkle tree's root node is included in the ROOT tag
of the response.
The index of a request's nonce node is included in the INDX tag of
the response.
The values of all sibling nodes in the path between a request's nonce
node and the root node is stored in the PATH tag so that the client
can reconstruct and validate the value in the ROOT tag using its
nonce.
6.3.1. Root value validity check algorithm
One starts by computing the hash of the NONC value from the request, One starts by computing the hash of the NONC value from the request,
with \x00 preappended. Then one walks from the least significant bit with 0x00 prepended. Then one walks from the least significant bit
of INDX to the most significant bit, and also walks towards the end of INDX to the most significant bit, and also walks towards the end
of PATH. of PATH.
If PATH ends then the remaining bits of the INDX MUST be all zero. If PATH ends then the remaining bits of the INDX MUST be all zero.
This indicates the termination of the walk, and the current value This indicates the termination of the walk, and the current value
MUST equal ROOT if the response is valid. MUST equal ROOT if the response is valid.
If the current bit is 0, one hashes \x01, the current hash, and the If the current bit is 0, one hashes 0x01, the current hash, and the
value from PATH. value from PATH.
If the current bit is 1 one hashes \x01, the value from PATH, and the If the current bit is 1 one hashes 0x01, the value from PATH, and the
current hash. current hash.
6.3. Validity of response 6.4. Validity of response
A client MUST check the following properties when it receives a A client MUST check the following properties when it receives a
response. We assume the long term server public key is known to the response. We assume the long-term server public key is known to the
client through other means. client through other means.
The signature in CERT was made with the long-term key of the o The signature in CERT was made with the long-term key of the
server server.
The DELE timestamps and the MIDP value are consistent
The INDX and PATH values prove NONC was included in the Merkle o The DELE timestamps and the MIDP value are consistent.
tree with value ROOT
The signature of SREP in SIG\x00 validates with the public key in o The INDX and PATH values prove NONC was included in the Merkle
DELE tree with value ROOT using the algorithm in Section 6.3.1.
o The signature of SREP in SIG validates with the public key in
DELE.
A response that passes these checks is said to be valid. Validity of 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 a response does not prove the time is correct, but merely that the
server signed it, and more specifically began to compute the server signed it, and thus guarantees that it began to compute the
signature at a time in between (MIDP-RADI, MIDP+RADI). signature at a time in the interval (MIDP-RADI, MIDP+RADI).
7. Time
An 8 byte timestamp contains a 4 byte Modified Julian Date (as in
[MJD] followed by a 4 byte count of the number of microseconds since
midnight on that day. This is not a unique representation: leap
seconds are handled by changing the day number early or late, and
hence having the number of microseconds increase even more. Unlike
NTP this is not a representation that uses the full number of bits in
the fraction part.
8. Cheater detection 7. Cheater Detection
A chain of responses is a series of responses where the SHA-512 hash A chain of responses is a series of responses where the SHA-512 hash
of the preceding response H, is concatenated with a 64 byte blind X, of the preceding response H, is concatenated with a 64 byte blind X,
and then SHA-512(H, X) is the NONC used in the subsequent response. and then SHA-512(H, X) is the nonce used in the subsequent response.
These may be represented as an array of objects in JSON where each These may be represented as an array of objects in JavaScript Object
object may have keys "blind" and "packet". Packet has the base64 Notation (JSON) format [RFC8259] where each object may have keys
encoded bytes of the packet and blind is the blind used for the next "blind" and "response_packet". Packet has the Base64 [RFC4648]
nonce. The last packet needs no blind. encoded bytes of the packet and blind is the Base64 encoded blind
used for the next nonce. The last packet needs no blind.
A pair of responses (r_1, r_2) is invalid if MIDP_1-RADI_1 > 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 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. such that i < j, (r_i, r_j) is an invalid pair.
Invalidity of a chain is proof that causality has been violated if Invalidity of a chain is proof that causality has been violated if
all servers were reporting correct time. An invalid chain where all all servers were reporting correct time. An invalid chain where all
individual responses are valid is cryptographic proof of malfeasance individual responses are valid is cryptographic proof of malfeasance
of at least one server: if all servers had the correct time in the 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. chain, causality would imply that MIDP_1-RADI_1 < MIDP_2+RADI_2.
In conducting the comparison of timestamps one must know the length In conducting the comparison of timestamps one must know the length
of a day and hence have historical leap second data for the days in of a day and hence have historical leap second data for the days in
question. However if violations are greater then a second the loss question. However if violations are greater then a second the loss
of leap second data doesn't impede their detection. of leap second data doesn't impede their detection.
9. Grease 8. Grease
Servers MAY send back a fraction of responses that are syntactically Servers MAY send back a fraction of responses that are syntactically
invalid or contain invalid signatures as well as incorrect times. invalid or contain invalid signatures as well as incorrect times.
Clients MUST properly reject such responses. Servers MUST NOT send Clients MUST properly reject such responses. Servers MUST NOT send
back responses with incorrect times and valid signatures. Either back responses with incorrect times and valid signatures. Either
signature MAY be invalid for this application. signature MAY be invalid for this application.
10. Roughtime Servers 9. Roughtime Servers
The below list contains a list of servers with their public keys in The below list contains a list of servers with their public keys in
Base64 format. These servers implement an older version of this Base64 format. These servers may implement older versions of this
specification. specification.
roughtime.int08h.com:2002; address: roughtime.cloudflare.com
AW5uAoTSTDfG5NfY1bTh08GUnOqlRb+HVhbJ3ODJvsE= port: 2002
long-term key: gD63hSj3ScS+wuOeGrubXlq35N1c5Lby/S+T7MNTjxo=
roughtime.cloudflare.com:2002; gD63hSj3ScS+wuOeGrubXlq35N1c5Lby/ address: roughtime.int08h.com
S+T7MNTjxo= port: 2002
long-term key: AW5uAoTSTDfG5NfY1bTh08GUnOqlRb+HVhbJ3ODJvsE=
roughtime.sandbox.google.com:2002; address: roughtime.sandbox.google.com
etPaaIxcBMY1oUeGpwvPMCJMwlRVNxv51KK/tktoJTQ= port: 2002
long-term key: etPaaIxcBMY1oUeGpwvPMCJMwlRVNxv51KK/tktoJTQ=
11. Trust anchors and policies address: roughtime.se
port: 2002
long-term key: S3AzfZJ5CjSdkJ21ZJGbxqdYP/SoE8fXKY0+aicsehI=
10. Trust anchors and policies
A trust anchor is any distributor of a list of trusted servers. It A trust anchor is any distributor of a list of trusted servers. It
is RECOMMENDED that trust anchors subscribe to a common public forum is RECOMMENDED that trust anchors subscribe to a common public forum
where evidence of malfeasance may be shared and discussed. Trust where evidence of malfeasance may be shared and discussed. Trust
anchors SHOULD subscribe to a zero-tolerance policy: any generation anchors SHOULD subscribe to a zero-tolerance policy: any generation
of incorrect timestamps will result in removal. To enable this trust of incorrect timestamps will result in removal. To enable this trust
anchors SHOULD list a wide variety of servers so the removal of a anchors SHOULD list a wide variety of servers so the removal of a
server does not result in operational issues for clients. Clients server does not result in operational issues for clients. Clients
SHOULD attempt to detect malfeasance and have a way to report it to SHOULD attempt to detect malfeasance and have a way to report it to
trust anchors. trust anchors.
Because only a single roughtime server is required for successful Because only a single roughtime server is required for successful
synchronization, Roughtime does not have the incentive problems that synchronization, Roughtime does not have the incentive problems that
have prevented effective enforcement of discipline on the web PKI. have prevented effective enforcement of discipline on the web PKI.
We expect that some clients will aggressively monitor server We expect that some clients will aggressively monitor server
behavior. behavior.
12. Acknowledgements 11. Acknowledgements
Thomas Peterson corrected multiple nits. Marcus Dansarie, Kristof Thomas Peterson corrected multiple nits. Marcus Dansarie, Peter
Teichel, Tal Mizrahi, and the other members of the NTP working group Loethberg (Lothberg), Tal Mizrahi, Ragnar Sundblad, Kristof Teichel,
contributed comments and suggestions. and the other members of the NTP working group contributed comments
and suggestions.
13. IANA Considerations 12. IANA Considerations
We request IANA assign a UDP port and create a new registry for 12.1. Service Name and Transport Protocol Port Number Registry
Roughtime tags.
14. Security Considerations IANA is requested to allocate the following entry in the Service Name
and Transport Protocol Port Number Registry [RFC6335]:
This protocol will not survive the advent of quantum computers. Service Name: Roughtime
Currently only one signature scheme is supported. Maintaining a list
of trusted servers and adjudicating violations of the rules by Transport Protocol: udp
servers are not discussed in this document and are essential for
security. Arithmetic on the adjusted timescale is interesting with Assignee: IESG <iesg@ietf.org>
intervals, and this may impact the interpretation of the MAXT and
MINT fields. Servers carry out a significant amount of computation Contact: IETF Chair <chair@ietf.org>
in response to clients, and thus may experience vulnerability to
denial of service attacks. Description: Roughtime time synchronization
Reference: [[this memo]]
Port Number: [[TBD1]], selected by IANA from the User Port range
12.2. Roughtime Tag Registry
IANA is requested to create a new registry entitled "Roughtime Tag
Registry". Entries SHALL have the following fields:
Tag (REQUIRED): A 32-bit unsigned integer in hexadecimal format.
ASCII Representation (OPTIONAL): The ASCII representation of the
tag in accordance with Section 5.1.3 of this memo, if applicable.
Reference (REQUIRED): A reference to a relevant specification
document.
The policy for allocation of new entries in this registry SHOULD be:
Specification Required.
The initial contents of this registry SHALL be as follows:
+------------+----------------------+---------------+
| Tag | ASCII Representation | Reference |
+------------+----------------------+---------------+
| 0x00444150 | PAD | [[this memo]] |
| 0x00474953 | SIG | [[this memo]] |
| 0x434e4f48 | NONC | [[this memo]] |
| 0x454c4544 | DELE | [[this memo]] |
| 0x48544150 | PATH | [[this memo]] |
| 0x49444152 | RADI | [[this memo]] |
| 0x4b425550 | PUBK | [[this memo]] |
| 0x5044494d | MIDP | [[this memo]] |
| 0x50455253 | SREP | [[this memo]] |
| 0x544e494d | MINT | [[this memo]] |
| 0x544f4f52 | ROOT | [[this memo]] |
| 0x54524543 | CERT | [[this memo]] |
| 0x5458414d | MAXT | [[this memo]] |
| 0x58444e49 | INDX | [[this memo]] |
+------------+----------------------+---------------+
13. Security Considerations
Since the only supported signature scheme, Ed25519, is not quantum
resistant, this protocol will not survive the advent of quantum
computers.
Maintaining a list of trusted servers and adjudicating violations of
the rules by servers is not discussed in this document and is
essential for security. Roughtime clients MUST update their view of
which servers are trustworthy in order to benefit from the detection
of misbehavior.
Validating timestamps made on different dates requires knowledge of
leap seconds in order to calculate time intervals correctly.
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 This protocol does not provide any confidentiality, and given the
nature of timestamps such impact is minor. The compromise of a nature of timestamps such impact is minor.
PUBK's private key, even past MAXT, is a problem as the private key
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.
Roughtime clients MUST update their view of which servers are The compromise of a PUBK's private key, even past MAXT, is a problem
trustworthy in order to benefit from the detection of misbehavior. as the private key 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.
Packets sent by the client MUST be at least 1024 bytes in length in Servers MUST NOT send response packets larger than the request
order to mitigate amplification attacks, and servers MUST ignore packets sent by clients, in order to prevent amplification attacks.
request packets that are smaller than this length.
15. Privacy Considerations 14. Privacy Considerations
This protocol is designed to obscure all client identifiers. Servers This protocol is designed to obscure all client identifiers. Servers
necessarily have persistent long term identities essential to necessarily have persistent long-term identities essential to
enforcing correct behavior. enforcing correct behavior. Generating nonces from previous
responses without using a blind can enable tracking of clients as
they move between networks.
16. References 15. References
16.1. Normative References 15.1. Normative References
[ITU-R_TF.457-2]
ITU-R, "Use of the Modified Julian Date by the Standard-
Frequency and Time-Signal Services", ITU-R
Recommendation TF.457-2, October 1997.
[ITU-R_TF.460-6]
ITU-R, "Standard-Frequency and Time-Signal Emissions",
ITU-R Recommendation TF.460-6, February 2002.
[RFC0020] Cerf, V., "ASCII format for network interchange", STD 80, [RFC0020] Cerf, V., "ASCII format for network interchange", STD 80,
RFC 20, DOI 10.17487/RFC0020, October 1969, RFC 20, DOI 10.17487/RFC0020, October 1969,
<https://www.rfc-editor.org/info/rfc20>. <https://www.rfc-editor.org/info/rfc20>.
[RFC4648] Josefsson, S., "The Base16, Base32, and Base64 Data
Encodings", RFC 4648, DOI 10.17487/RFC4648, October 2006,
<https://www.rfc-editor.org/info/rfc4648>.
[RFC6234] Eastlake 3rd, D. and T. Hansen, "US Secure Hash Algorithms
(SHA and SHA-based HMAC and HKDF)", RFC 6234,
DOI 10.17487/RFC6234, May 2011,
<https://www.rfc-editor.org/info/rfc6234>.
[RFC6335] Cotton, M., Eggert, L., Touch, J., Westerlund, M., and S.
Cheshire, "Internet Assigned Numbers Authority (IANA)
Procedures for the Management of the Service Name and
Transport Protocol Port Number Registry", BCP 165,
RFC 6335, DOI 10.17487/RFC6335, August 2011,
<https://www.rfc-editor.org/info/rfc6335>.
[RFC8032] Josefsson, S. and I. Liusvaara, "Edwards-Curve Digital [RFC8032] Josefsson, S. and I. Liusvaara, "Edwards-Curve Digital
Signature Algorithm (EdDSA)", RFC 8032, Signature Algorithm (EdDSA)", RFC 8032,
DOI 10.17487/RFC8032, January 2017, DOI 10.17487/RFC8032, January 2017,
<https://www.rfc-editor.org/info/rfc8032>. <https://www.rfc-editor.org/info/rfc8032>.
16.2. Informative References [RFC8259] Bray, T., Ed., "The JavaScript Object Notation (JSON) Data
Interchange Format", STD 90, RFC 8259,
DOI 10.17487/RFC8259, December 2017,
<https://www.rfc-editor.org/info/rfc8259>.
15.2. Informative References
[Autokey] Rottger, S., "Analysis of the NTP Autokey Procedures", [Autokey] Rottger, S., "Analysis of the NTP Autokey Procedures",
2012, <https://zero-entropy.de/autokey_analysis.pdf>. 2012, <https://zero-entropy.de/autokey_analysis.pdf>.
[DelayAttacks] [DelayAttacks]
Mizrahi, T., "A Game Theoretic Analysis of Delay Attacks Mizrahi, T., "A Game Theoretic Analysis of Delay Attacks
Against Time Synchronization Protocols", 2012, Against Time Synchronization Protocols",
DOI 10.1109/ISPCS.2012.6336612, 2012,
<https://ieeexplore.ieee.org/document/6336612>. <https://ieeexplore.ieee.org/document/6336612>.
[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] [I-D.ietf-ntp-using-nts-for-ntp]
Franke, D., Sibold, D., Teichel, K., Dansarie, M., and R. Franke, D., Sibold, D., Teichel, K., Dansarie, M., and R.
Sundblad, "Network Time Security for the Network Time Sundblad, "Network Time Security for the Network Time
Protocol", draft-ietf-ntp-using-nts-for-ntp-19 (work in Protocol", draft-ietf-ntp-using-nts-for-ntp-19 (work in
progress), April 2019. progress), April 2019.
[MCBG] Malhotra, A., Cohen, I., Brakke, E., and S. Goldberg, [MCBG] Malhotra, A., Cohen, I., Brakke, E., and S. Goldberg,
"Attacking the Network Time Protocol", 2015, "Attacking the Network Time Protocol", 2015,
<https://eprint.iacr.org/2015/1020>. <https://eprint.iacr.org/2015/1020>.
[MJD] Moyer, G., "The Origin of the Julian Day System", 1981. [RFC0768] Postel, J., "User Datagram Protocol", STD 6, RFC 768,
DOI 10.17487/RFC0768, August 1980,
[resolution] <https://www.rfc-editor.org/info/rfc768>.
International Earth Rotation and Reference Systems
Service, "Resolution B1", 2000.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, Requirement Levels", BCP 14, RFC 2119,
DOI 10.17487/RFC2119, March 1997, DOI 10.17487/RFC2119, March 1997,
<https://www.rfc-editor.org/info/rfc2119>. <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, [RFC5905] Mills, D., Martin, J., Ed., Burbank, J., and W. Kasch,
"Network Time Protocol Version 4: Protocol and Algorithms "Network Time Protocol Version 4: Protocol and Algorithms
Specification", RFC 5905, DOI 10.17487/RFC5905, June 2010, Specification", RFC 5905, DOI 10.17487/RFC5905, June 2010,
<https://www.rfc-editor.org/info/rfc5905>. <https://www.rfc-editor.org/info/rfc5905>.
[RFC7384] Mizrahi, T., "Security Requirements of Time Protocols in [RFC7384] Mizrahi, T., "Security Requirements of Time Protocols in
Packet Switched Networks", RFC 7384, DOI 10.17487/RFC7384, Packet Switched Networks", RFC 7384, DOI 10.17487/RFC7384,
October 2014, <https://www.rfc-editor.org/info/rfc7384>. October 2014, <https://www.rfc-editor.org/info/rfc7384>.
[RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC
2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174,
May 2017, <https://www.rfc-editor.org/info/rfc8174>. May 2017, <https://www.rfc-editor.org/info/rfc8174>.
Authors' Addresses [RFC8573] Malhotra, A. and S. Goldberg, "Message Authentication Code
for the Network Time Protocol", RFC 8573,
DOI 10.17487/RFC8573, June 2019,
<https://www.rfc-editor.org/info/rfc8573>.
Appendix A. Terms and Abbreviations
ASCII American Standard Code for Information Interchange
IANA Internet Assigned Numbers Authority
JSON JavaScript Object Notation [RFC8259]
MJD Modified Julian Date
NTP Network Time Protocol [RFC5905]
NTS Network Time Security [I-D.ietf-ntp-using-nts-for-ntp]
UDP User Datagram Protocol [RFC0768]
UTC Coordinated Universal Time [ITU-R_TF.460-6]
Authors' Addresses
Aanchal Malhotra Aanchal Malhotra
Boston University Boston University
111 Cummington Mall 111 Cummington Mall
Boston 02215 Boston 02215
USA USA
Email: aanchal4@bu.edu Email: aanchal4@bu.edu
Adam Langley Adam Langley
Google Google
 End of changes. 80 change blocks. 
205 lines changed or deleted 470 lines changed or added

This html diff was produced by rfcdiff 1.47. The latest version is available from http://tools.ietf.org/tools/rfcdiff/