Initial commit
diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..ac51a05
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1 @@
+bazel-*
diff --git a/AUTHORS b/AUTHORS
new file mode 100644
index 0000000..16eaae3
--- /dev/null
+++ b/AUTHORS
@@ -0,0 +1,7 @@
+# This is the list of Roughtime authors for copyright purposes.
+#
+# This does not necessarily list everyone who has contributed code, since in
+# some cases, their employer may be the copyright holder. To see the full list
+# of contributors, see the revision history in source control.
+Google Inc.
+and other contributors
diff --git a/BUILD b/BUILD
new file mode 100644
index 0000000..4e03973
--- /dev/null
+++ b/BUILD
@@ -0,0 +1,137 @@
+load(
+ "@protobuf//:protobuf.bzl",
+ "cc_proto_library",
+)
+
+cc_library(
+ name = "protocol",
+ srcs = ["protocol.cc"],
+ hdrs = ["protocol.h"],
+ deps = [
+ "@boringssl//:crypto",
+ "@protobuf//:protobuf",
+ ],
+)
+
+cc_test(
+ name = "protocol_test",
+ srcs = ["protocol_test.cc"],
+ copts = ["-Iexternal/gtest/include"],
+ deps = [
+ ":protocol",
+ "@gtest//:main",
+ ],
+)
+
+cc_library(
+ name = "client",
+ srcs = ["client.cc"],
+ hdrs = ["client.h"],
+ deps = [":protocol"],
+)
+
+cc_test(
+ name = "client_test",
+ srcs = ["client_test.cc"],
+ copts = ["-Iexternal/gtest/include"],
+ deps = [
+ ":client",
+ ":open_source_fillins",
+ "@gtest//:main",
+ ],
+)
+
+cc_library(
+ name = "time_source",
+ hdrs = ["time_source.h"],
+)
+
+cc_library(
+ name = "server",
+ srcs = ["server.cc"],
+ hdrs = ["server.h"],
+ deps = [
+ ":protocol",
+ ":time_source",
+ "@boringssl//:crypto",
+ ],
+)
+
+cc_proto_library(
+ name = "config_proto",
+ srcs = ["config.proto"],
+ default_runtime = "@protobuf//:protobuf",
+ protoc = "@protobuf//:protoc",
+)
+
+cc_binary(
+ name = "simple_client",
+ srcs = [
+ "clock_linux.cc",
+ "clock_macos.cc",
+ "simple_client.cc",
+ ],
+ deps = [
+ ":client",
+ ":config_proto",
+ "@boringssl//:crypto",
+ "@protobuf//:protobuf",
+ ],
+)
+
+cc_library(
+ name = "simple_server_lib",
+ srcs = ["simple_server.cc"],
+ hdrs = ["simple_server.h"],
+ deps = [
+ ":server",
+ ":sys_time",
+ ":udp_processor",
+ ],
+)
+
+cc_binary(
+ name = "simple_server",
+ srcs = ["simple_server_main.cc"],
+ deps = [":simple_server_lib"],
+)
+
+cc_library(
+ name = "open_source_fillins",
+ hdrs = ["open_source_fillins.h"],
+ defines = ["ROUGHTIME_OPEN_SOURCE"],
+)
+
+cc_test(
+ name = "server_test",
+ srcs = ["server_test.cc"],
+ copts = ["-Iexternal/gtest/include"],
+ deps = [
+ ":open_source_fillins",
+ ":server",
+ "@boringssl//:crypto",
+ "@gtest//:main",
+ ],
+)
+
+cc_library(
+ name = "udp_processor",
+ srcs = ["udp_processor.cc"],
+ hdrs = ["udp_processor.h"],
+ deps = [
+ ":open_source_fillins",
+ ":protocol",
+ ":server",
+ ":time_source",
+ ],
+)
+
+cc_library(
+ name = "sys_time",
+ srcs = ["sys_time.cc"],
+ hdrs = ["sys_time.h"],
+ deps = [
+ ":time_source",
+ "@protobuf//:protobuf",
+ ],
+)
diff --git a/BUILDING.md b/BUILDING.md
new file mode 100644
index 0000000..dc70f55
--- /dev/null
+++ b/BUILDING.md
@@ -0,0 +1,19 @@
+# Building Roughtime
+
+## C++
+
+The Roughtime C++ code is built using [Bazel](https://www.bazel.io/). Everything should build on Linux. On MacOS, `simple_client` should build.
+
+In order to build, install Bazel and run `bazel build ... && bazel test ...`. That should download and build BoringSSL, gTest and Protocol Buffers automatically.
+
+After doing that you should be able to play with `simple_client` by running `./bazel-bin/simple_client roughtime-servers.json`.
+
+### Known Issues
+
+If, on Arch Linux, Bazel complains about the version of Java but you have Java 8 installed, you may need to export `JAVA_HOME=/usr/lib/jvm/java-8-openjdk`.
+
+If you see an error about `_FORTIFY_SOURCE requires compiling with optimization`, pass `--copt=-U_FORTIFY_SOURCE` to Bazel.
+
+## Go
+
+The Roughtime Go code works with `go get`, as is typical for Go code. For example, `go get https://roughtime.googlesource.com/roughtime/go/client` and run `client --servers-file=roughtime/roughtime-servers.json --chain-file=~/roughtime-chain.json`.
diff --git a/CONTRIBUTING.md b/CONTRIBUTING.md
new file mode 100644
index 0000000..cb8be98
--- /dev/null
+++ b/CONTRIBUTING.md
@@ -0,0 +1,49 @@
+Want to contribute? Great! First, read this page (including the small print at the end).
+
+### Before you contribute
+Before we can use your code, you must sign the
+[Google Individual Contributor License Agreement](https://cla.developers.google.com/about/google-individual)
+(CLA), which you can do online. The CLA is necessary mainly because you own the
+copyright to your changes, even after your contribution becomes part of our
+codebase, so we need your permission to use and distribute your code. We also
+need to be sure of various other things—for instance that you'll tell us if you
+know that your code infringes on other people's patents. You don't have to sign
+the CLA until after you've submitted your code for review and a member has
+approved it, but you must do it before we can put your code into our codebase.
+Before you start working on a larger contribution, you should get in touch with
+us first via email with your idea so that we can help out and possibly guide
+you. Coordinating up front makes it much easier to avoid frustration later on.
+
+### Code reviews
+All submissions, including submissions by project members, require review. We
+use [Gerrit](https://roughtime-review.googlesource.com) for this purpose.
+
+#### Setup
+If you have not done so on this machine, you will need to set up a password for
+Gerrit. Sign in with a Google account, visit
+[this link](https://roughtime.googlesource.com/), and click the "Generate
+Password" link in the top right. You will also need to prepare your checkout to
+[add Change-Ids](https://gerrit-review.googlesource.com/Documentation/cmd-hook-commit-msg.html)
+on commit. Run:
+
+ curl -Lo .git/hooks/commit-msg https://roughtime-review.googlesource.com/tools/hooks/commit-msg
+ chmod u+x .git/hooks/commit-msg
+
+#### Uploading changes
+To upload a change, push it to the special `refs/for/master` target:
+
+ git push origin HEAD:refs/for/master
+
+The output will then give you a link to the change. Add `agl@google.com` and
+`mab@google.com` as reviewers.
+
+Pushing a commit with the same Change-Id as an existing change will upload a new
+version of it. (Use the `git rebase` or `git commit --amend` commands.)
+
+For more detailed instructions, see the
+[Gerrit User Guide](https://gerrit-review.googlesource.com/Documentation/intro-user.html).
+
+### The small print
+Contributions made by corporations are covered by a different agreement than
+the one above, the
+[Software Grant and Corporate Contributor License Agreement](https://cla.developers.google.com/about/google-corporate).
diff --git a/ECOSYSTEM.md b/ECOSYSTEM.md
new file mode 100644
index 0000000..5d81d96
--- /dev/null
+++ b/ECOSYSTEM.md
@@ -0,0 +1,27 @@
+# Roughtime Ecosystem
+
+The [protocol](/PROTOCOL.md) document specifies the nuts and bolts of how to query a Roughtime server but more structure is needed in order to use Roughtime fully.
+
+## Chaining requests
+
+As explained in the [introduction](/README.md), once there are multiple Roughtime servers a client can query several of them. If one of them provides a bogus answer then the replies of later servers can provide proof of misbehaviour.
+
+The way this is implemented is to form the client's nonce by hashing the response from the previous request and a random, 64-byte blinding value. Specifically, a client calculates its nonce as SHA-512(SHA-512(previous-reply) + blind). By using this construction, a client can prove that a request was created after the previous reply was received. Therefore, if the next reply contains a timestamp prior to that of the previous reply, the client would have proof of a server's misbehaviour.
+
+(Although, in that situation, it wouldn't be possible to tell which server was misbehaving without more chained requests.)
+
+It's envisioned that a fully operational Roughtime ecosystem would involve clients that maintain “chain files”—a chain of past requests and replies. In the event that a reply from a server is sufficiently divergent from the replies from other servers, the client would make a number of additional requests (to provide additional evidence) and then upload the chain file to an auditor. The auditor service would confirm that some misbehaviour was observed in the chain and then flag it for human analysis.
+
+A standard, JSON-based, format for chain files is specified in `config.proto`.
+
+## Maintaining a healthy software ecosystem
+
+A healthy software ecosystem doesn't arise by specifying how software should behave and then assuming that implementations will do the right thing. Rather we plan on having Roughtime servers return invalid, bogus answers to a small fraction of requests. These bogus answers would contain the wrong time, but would also be invalid in another way. For example, one of the signatures might be incorrect, or the tags in the message might be in the wrong order. Client implementations that don't implement all the necessary checks would find that they get nonsense answers and, hopefully, that will be sufficient to expose bugs before they turn into a Blackhat talk.
+
+## Curating server lists
+
+Assuming that there ever are multiple Roughtime servers, there will be a need for a canonical list of “known good” servers. For this we envision a system similar to the one for Certificate Transparency, where candidate servers are monitored for a period of time and, if they meet the published criteria around uptime and accuracy, they will be included in the list.
+
+We also need to ensure that we can remove servers from the list. Not just for poor timekeeping, but also because services come and go. It's a problem with NTP that some devices will hardcode NTP server addresses and assume that they'll never change. There have been enough cases of this that it has it's own [Wikipedia page](https://en.wikipedia.org/wiki/NTP_server_misuse_and_abuse).
+
+So, instead, Roughtime is only available for products that can be updated. The server lists have an explicit expiry time in them and we will actively seek to break clients that try to use old information in order to maintain ecosystem health. At the moment changing the hostname or port of a server is the easiest way to enforce this but we expect to add a per-server id in the future that clients would need to send in order to prove to the server that they have a current server list.
diff --git a/LICENSE b/LICENSE
new file mode 100644
index 0000000..d645695
--- /dev/null
+++ b/LICENSE
@@ -0,0 +1,202 @@
+
+ Apache License
+ Version 2.0, January 2004
+ http://www.apache.org/licenses/
+
+ TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION
+
+ 1. Definitions.
+
+ "License" shall mean the terms and conditions for use, reproduction,
+ and distribution as defined by Sections 1 through 9 of this document.
+
+ "Licensor" shall mean the copyright owner or entity authorized by
+ the copyright owner that is granting the License.
+
+ "Legal Entity" shall mean the union of the acting entity and all
+ other entities that control, are controlled by, or are under common
+ control with that entity. For the purposes of this definition,
+ "control" means (i) the power, direct or indirect, to cause the
+ direction or management of such entity, whether by contract or
+ otherwise, or (ii) ownership of fifty percent (50%) or more of the
+ outstanding shares, or (iii) beneficial ownership of such entity.
+
+ "You" (or "Your") shall mean an individual or Legal Entity
+ exercising permissions granted by this License.
+
+ "Source" form shall mean the preferred form for making modifications,
+ including but not limited to software source code, documentation
+ source, and configuration files.
+
+ "Object" form shall mean any form resulting from mechanical
+ transformation or translation of a Source form, including but
+ not limited to compiled object code, generated documentation,
+ and conversions to other media types.
+
+ "Work" shall mean the work of authorship, whether in Source or
+ Object form, made available under the License, as indicated by a
+ copyright notice that is included in or attached to the work
+ (an example is provided in the Appendix below).
+
+ "Derivative Works" shall mean any work, whether in Source or Object
+ form, that is based on (or derived from) the Work and for which the
+ editorial revisions, annotations, elaborations, or other modifications
+ represent, as a whole, an original work of authorship. For the purposes
+ of this License, Derivative Works shall not include works that remain
+ separable from, or merely link (or bind by name) to the interfaces of,
+ the Work and Derivative Works thereof.
+
+ "Contribution" shall mean any work of authorship, including
+ the original version of the Work and any modifications or additions
+ to that Work or Derivative Works thereof, that is intentionally
+ submitted to Licensor for inclusion in the Work by the copyright owner
+ or by an individual or Legal Entity authorized to submit on behalf of
+ the copyright owner. For the purposes of this definition, "submitted"
+ means any form of electronic, verbal, or written communication sent
+ to the Licensor or its representatives, including but not limited to
+ communication on electronic mailing lists, source code control systems,
+ and issue tracking systems that are managed by, or on behalf of, the
+ Licensor for the purpose of discussing and improving the Work, but
+ excluding communication that is conspicuously marked or otherwise
+ designated in writing by the copyright owner as "Not a Contribution."
+
+ "Contributor" shall mean Licensor and any individual or Legal Entity
+ on behalf of whom a Contribution has been received by Licensor and
+ subsequently incorporated within the Work.
+
+ 2. Grant of Copyright License. Subject to the terms and conditions of
+ this License, each Contributor hereby grants to You a perpetual,
+ worldwide, non-exclusive, no-charge, royalty-free, irrevocable
+ copyright license to reproduce, prepare Derivative Works of,
+ publicly display, publicly perform, sublicense, and distribute the
+ Work and such Derivative Works in Source or Object form.
+
+ 3. Grant of Patent License. Subject to the terms and conditions of
+ this License, each Contributor hereby grants to You a perpetual,
+ worldwide, non-exclusive, no-charge, royalty-free, irrevocable
+ (except as stated in this section) patent license to make, have made,
+ use, offer to sell, sell, import, and otherwise transfer the Work,
+ where such license applies only to those patent claims licensable
+ by such Contributor that are necessarily infringed by their
+ Contribution(s) alone or by combination of their Contribution(s)
+ with the Work to which such Contribution(s) was submitted. If You
+ institute patent litigation against any entity (including a
+ cross-claim or counterclaim in a lawsuit) alleging that the Work
+ or a Contribution incorporated within the Work constitutes direct
+ or contributory patent infringement, then any patent licenses
+ granted to You under this License for that Work shall terminate
+ as of the date such litigation is filed.
+
+ 4. Redistribution. You may reproduce and distribute copies of the
+ Work or Derivative Works thereof in any medium, with or without
+ modifications, and in Source or Object form, provided that You
+ meet the following conditions:
+
+ (a) You must give any other recipients of the Work or
+ Derivative Works a copy of this License; and
+
+ (b) You must cause any modified files to carry prominent notices
+ stating that You changed the files; and
+
+ (c) You must retain, in the Source form of any Derivative Works
+ that You distribute, all copyright, patent, trademark, and
+ attribution notices from the Source form of the Work,
+ excluding those notices that do not pertain to any part of
+ the Derivative Works; and
+
+ (d) If the Work includes a "NOTICE" text file as part of its
+ distribution, then any Derivative Works that You distribute must
+ include a readable copy of the attribution notices contained
+ within such NOTICE file, excluding those notices that do not
+ pertain to any part of the Derivative Works, in at least one
+ of the following places: within a NOTICE text file distributed
+ as part of the Derivative Works; within the Source form or
+ documentation, if provided along with the Derivative Works; or,
+ within a display generated by the Derivative Works, if and
+ wherever such third-party notices normally appear. The contents
+ of the NOTICE file are for informational purposes only and
+ do not modify the License. You may add Your own attribution
+ notices within Derivative Works that You distribute, alongside
+ or as an addendum to the NOTICE text from the Work, provided
+ that such additional attribution notices cannot be construed
+ as modifying the License.
+
+ You may add Your own copyright statement to Your modifications and
+ may provide additional or different license terms and conditions
+ for use, reproduction, or distribution of Your modifications, or
+ for any such Derivative Works as a whole, provided Your use,
+ reproduction, and distribution of the Work otherwise complies with
+ the conditions stated in this License.
+
+ 5. Submission of Contributions. Unless You explicitly state otherwise,
+ any Contribution intentionally submitted for inclusion in the Work
+ by You to the Licensor shall be under the terms and conditions of
+ this License, without any additional terms or conditions.
+ Notwithstanding the above, nothing herein shall supersede or modify
+ the terms of any separate license agreement you may have executed
+ with Licensor regarding such Contributions.
+
+ 6. Trademarks. This License does not grant permission to use the trade
+ names, trademarks, service marks, or product names of the Licensor,
+ except as required for reasonable and customary use in describing the
+ origin of the Work and reproducing the content of the NOTICE file.
+
+ 7. Disclaimer of Warranty. Unless required by applicable law or
+ agreed to in writing, Licensor provides the Work (and each
+ Contributor provides its Contributions) on an "AS IS" BASIS,
+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
+ implied, including, without limitation, any warranties or conditions
+ of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A
+ PARTICULAR PURPOSE. You are solely responsible for determining the
+ appropriateness of using or redistributing the Work and assume any
+ risks associated with Your exercise of permissions under this License.
+
+ 8. Limitation of Liability. In no event and under no legal theory,
+ whether in tort (including negligence), contract, or otherwise,
+ unless required by applicable law (such as deliberate and grossly
+ negligent acts) or agreed to in writing, shall any Contributor be
+ liable to You for damages, including any direct, indirect, special,
+ incidental, or consequential damages of any character arising as a
+ result of this License or out of the use or inability to use the
+ Work (including but not limited to damages for loss of goodwill,
+ work stoppage, computer failure or malfunction, or any and all
+ other commercial damages or losses), even if such Contributor
+ has been advised of the possibility of such damages.
+
+ 9. Accepting Warranty or Additional Liability. While redistributing
+ the Work or Derivative Works thereof, You may choose to offer,
+ and charge a fee for, acceptance of support, warranty, indemnity,
+ or other liability obligations and/or rights consistent with this
+ License. However, in accepting such obligations, You may act only
+ on Your own behalf and on Your sole responsibility, not on behalf
+ of any other Contributor, and only if You agree to indemnify,
+ defend, and hold each Contributor harmless for any liability
+ incurred by, or claims asserted against, such Contributor by reason
+ of your accepting any such warranty or additional liability.
+
+ END OF TERMS AND CONDITIONS
+
+ APPENDIX: How to apply the Apache License to your work.
+
+ To apply the Apache License to your work, attach the following
+ boilerplate notice, with the fields enclosed by brackets "[]"
+ replaced with your own identifying information. (Don't include
+ the brackets!) The text should be enclosed in the appropriate
+ comment syntax for the file format. We also recommend that a
+ file or class name and description of purpose be included on the
+ same "printed page" as the copyright notice for easier
+ identification within third-party archives.
+
+ Copyright [yyyy] [name of copyright owner]
+
+ Licensed under the Apache License, Version 2.0 (the "License");
+ you may not use this file except in compliance with the License.
+ You may obtain a copy of the License at
+
+ http://www.apache.org/licenses/LICENSE-2.0
+
+ Unless required by applicable law or agreed to in writing, software
+ distributed under the License is distributed on an "AS IS" BASIS,
+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ See the License for the specific language governing permissions and
+ limitations under the License.
diff --git a/PROTOCOL.md b/PROTOCOL.md
new file mode 100644
index 0000000..5d13fae
--- /dev/null
+++ b/PROTOCOL.md
@@ -0,0 +1,157 @@
+# Roughtime protocol
+
+## Messages
+
+Roughtime messages are a map from uint32s to byte-strings. The number of elements in the map and the sum of the lengths of all the byte-strings are, at most, 2\*\*32-1. All the byte strings must have lengths that are a multiple of four.
+
+All values are encoded in little-endian form because every platform that Google software runs on is little-endian.
+
+The header of a message looks like:
+
+```
+uint32 num_tags
+uint32 offsets[min(0, num_tags-1)]
+uint32 tags[num_tags]
+```
+
+Following the header are the contents of the byte-strings. The first byte after the header is considered be offset zero and is the start of the value for the first tag. The `offsets` array gives the offset of the value for all tags after the first.
+
+Tags must be in strictly ascending order and offsets must be a multiple of four. Parsers must require this.
+
+Here are some example messages, given in hex:
+
+The empty message consists of four, zero bytes:
+
+```
+00000000 # num_tags = 0
+```
+
+A message with a single tag (0x1020304) with value 80808080:
+
+```
+01000000 # num_tags = 1
+# No offsets
+04030201 # tag 0x1020304
+80808080 # value starts immediately after the header
+```
+
+A message with two tags:
+
+```
+02000000 # num_tags = 2
+04000000 # offset 4 for the value of the second tag
+05030200 # tag 0x020305
+04030201 # tag 0x1020304
+00000000 # value for 0x020305 starts immediately after the header
+80808080 # value for 0x1020304 starts at offset four
+```
+
+Note that the ordering of the tags is based on their numerical order, not on the lexicographic order of their encodings.
+
+When processing messages, unknown tags are ignored.
+
+## Tag values
+
+Tags can be arbitrary 32-bit values but in this document they will often be written as three or four capital letters, e.g. `NONC`. In these cases, the numeric value of the tag is such that the little-endian encoding of it causes that string to be written out. So the numeric value of `NONC` is 0x434e4f4e. For three-letter tags, the last byte will be given explicitly, e.g. `SIG\x00`.
+
+## Requests
+
+A Roughtime request is a message with at least the tag `NONC`. The value of `NONC` is 64, arbitrary bytes that form a nonce in the protocol. Other tags must be ignored.
+
+(The simplest clients can just generate random values for the nonce. Clients that participate in the [wider ecosystem](/ECOSYSTEM.md) generate nonces in a different way.)
+
+Request messages sent over UDP must be at least 1024 bytes long in order to ensure that a Roughtime server cannot act as an amplifier. The canonical way to ensure this is to include a `PAD\xff` tag, whose value is an arbitrary number of zero bytes. It's expected that a UDP request contain exactly 1024 bytes as there's no point padding the request to more than the minimum.
+
+## Responses
+
+Responses are messages that contain at least the following tags:
+ * `SREP`: signed response bytes, the value of which is itself a message.
+ * `SIG\x00`: the signature, an opaque byte-string that authenticates the value of `SREP`. At the moment, Ed25519 is the only supported signature algorithm and so this will be a 64-byte value.
+ * `CERT`: the server's certificate, which contains a time-limited online key authenticated by the server's long-term key.
+ * `INDX` and `PATH`: the position and upwards path for this response in a Merkle tree. See the section on signatures, below.
+
+### The signed response and Roughtime UTC.
+
+The signed portion of a response is a message that contains the timestamp from the server as well as the root of a Merkle tree for authenticating it. It's contained in the value of the `SREP` tag.
+
+The timestamp is expressed in two tags: `MIDP` and `RADI`. The `MIDP` tag contains a uint64 which is the midpoint, in microseconds, of a span of time, while the `RADI` tag contains the radius of that span in microseconds, expressed as a uint32. The server asserts that the true time, at the point of processing, lies within that span.
+
+The “true time” for Roughtime is defined as being UTC with a 24-hour linear leap-second smear. That is, when a leap-second is added or removed from UTC it is smeared out over the course of a day. So UTC noon to noon on the date in question will consist of 86,399 or 86,401 SI seconds, with all the smeared seconds being the same length.
+
+As noted, the signed response message also includes the root of a Merkle tree in a `ROOT` tag. The semantics of this are detailed in the next section.
+
+### Authenticating replies
+
+In order to authenticate the response and ensure freshness, the nonce provided in a request must be bound into the signed response. In order to allow a server to sign a batch of responses the nonces are built into a tree and only the root of the tree is included in the signed message.
+
+A signature of the encoded, signed response message is included as the value of the top-level `SIG\x00` tag. This signature must be checked with respect to the online key that's included in the certificate. (See next section.)
+
+Additionally, a client must ensure that their nonce is included the tree. To do so, the values of the `INDX` and `PATH` tags from the top-level response are needed, as well as the value of the `ROOT` tag from the signed response message.
+
+The value of the `INDX` tag is a uint32 and specifies the position of the client's nonce in the tree. The value of the `PATH` tag is a series of hashes on the path from the client's nonce to the root of the tree. The value of the `ROOT` tag is the claimed root of the tree. The hash function used throughout is SHA-512 so the length of the root is 64 bytes and the length of the path is a multiple of 64 bytes.
+
+A client can verify that its nonce is included in a tree using the following pseudo code:
+
+```
+index = top-level-response.getU32("INDX")
+path = top-level-response.getMultipleOf64Bytes("PATH")
+hash = hashLeaf(nonce-from-request)
+
+while len(path) > 0 {
+ if index&1 == 0 {
+ hash = hashNode(hash, path[:64])
+ } else {
+ hash = hashNode(path[:64], hash)
+ }
+
+ index >>= 1
+ path = path[64:]
+}
+
+if hash != signed-response-message.Get64Bytes("ROOT") {
+ return error;
+}
+
+function hashLeaf(leaf) {
+ return SHA-512("\x00" + leaf)
+}
+
+function hashNode(left, right) {
+ return SHA-512("\x01" + left + right)
+}
+```
+
+### Certificates
+
+In order to allow a server to keep its long-term identity key offline, a response includes a ‘certificate’, which is a limited delegation from the long-term key to an online key. This certificate is contained in a message which is the value of the `CERT` tag in a response.
+
+The certificate message contains two tags: `SIG\x00` and `DELE`. The value of the `SIG\x00` tag is a signature of the value of the `DELE` tag, made by the server's long-term key. (Clients must know the server's public key a priori.) Since Ed25519 is currently the only supported signature algorithm, this value will be 64 bytes long.
+
+The contents of the value of the `DELE` tag are a message containing:
+ * `PUBK`: the online public key. This key is used to produce the signature of the signed response message in the top-level of the response.
+ * `MINT` and `MAXT`: these uint64s limit the times that the online key can authenticate. The midpoint of any time span using that key must be greater than (or equal to) the value of `MINT` and less than (or equal to) the value of `MAXT`.
+
+### Processing a response
+
+To summarise the above, the full structure of a response (when considering nested messages) looks like this:
+
+ * `SREP`
+ * `ROOT`
+ * `MIDP`
+ * `RADI`
+ * `SIG\x00`
+ * `INDX`
+ * `PATH`
+ * `CERT`
+ * `SIG\x00`
+ * `DELE`
+ * `MINT`
+ * `MAXT`
+ * `PUBK`
+
+The procedure to fully process a response results in an authenticated midpoint and radius and contains roughly these steps:
+ 1. Verify the signature in the certificate of the delegation message.
+ 1. Verify the top-level signature of the signed response message using the public key from the delegation.
+ 1. Verify that the nonce from the request is included in the Merkle tree.
+ 1. Verify that the midpoint is within the valid bounds of the delegation.
+ 1. Return the midpoint and radius.
diff --git a/README.md b/README.md
new file mode 100644
index 0000000..2683a47
--- /dev/null
+++ b/README.md
@@ -0,0 +1,76 @@
+# Roughtime
+
+Roughtime is a project that aims to provide secure time synchronisation.
+
+ * [BUILDING.md](/BUILDING.md): how to build the Roughtime sources.
+ * [PROTOCOL.md](/PROTOCOL.md): details of the protocol.
+ * [ECOSYSTEM.md](/ECOSYSTEM.md): wider implementation concerns.
+ * [CONTRIBUTING.md](/CONTRIBUTING.md): how to contribute to Roughtime.
+
+Roughtime is discussed on the [mailing list](https://groups.google.com/a/chromium.org/forum/#!forum/proto-roughtime).
+
+## Secure, rough time.
+
+One often needs to ensure that information is “fresh” in secure protocols: certificates need to be current, software updates need to return the latest version etc. There are essentially only two ways to achieve this: nonces or synchronised clocks.
+
+Nonces are large, random numbers that are included in a request. Any subsequent reply has to integrate the nonce somehow to link it to the request; usually by signing it. Since the space of nonces is so vast, we can assume that they'll never be reused. Thus a reply that incorporates a nonce must have been generated after the request that triggered it.
+
+Nonces are inherently interactive. To ensure freshness without interaction we can use synchronised clocks and expiry times. If the “current” time is before the (signed) expiry time then the information can be considered fresh. This is so useful that it pops up all over the place. Certificates obviously have expiration times, but so do OCSP responses, Kerberos tickets, DNSSEC replies and PGP keys. Chrome's built-in certificate pins have an expiry time in the Chrome binary.
+
+So lots of security properties depend on knowing the correct time, but that assumption is used to a far greater extent than the reality of time synchronisation warrants.
+
+NTP is the dominant protocol used for time synchronisation and, although recent versions provide for the possibility of authentication, in practice that's not used. Most computers will trust an unauthenticated NTP reply to set the system clock meaning that a MITM attacker can control a victim's clock and, probably, violate the security properties of some of the protocols listed above. Existing defenses against this are generally heuristic: for example, Windows won't accept an NTP reply that moves the clock more than 15 hours and will typically only synchronise once every nine hours.
+
+Mobile phones might be a little better as they often get their time from their cellular network. However, as numerous researchers keep showing, cellular network security isn't a good as we would like it to be either.
+
+## So, secure NTP?
+
+The obvious answer to this problem is to authenticate NTP replies. Indeed, if you want to do this there's [NTPv4 Autokey](https://tools.ietf.org/html/rfc5906) from six years ago and [NTS](https://tools.ietf.org/html/draft-ietf-ntp-network-time-security-14), which is in development. [A paper](https://www.usenix.org/conference/usenixsecurity16/technical-sessions/presentation/dowling) at USENIX Security this year detailed how to do it so that it's stateless at the server and still mostly using fast, symmetric cryptography.
+
+But that's what NTP *should* have been, 15 years ago—it just allows the network to be untrusted. We aim higher these days.
+
+## Roughtime
+
+Roughtime is a protocol that aims to achieve rough time synchronisation in a secure way that doesn't depend on any particular time server, and in such a way that, if a time server does misbehave, clients end up with cryptographic proof of it.
+
+“Rough” time synchronisation means that, at this stage, we would be happy with time synchronisation to within 10 seconds of the correct time. If you have *serious* time synchronisation needs you'll want the [machinery in NTP](https://www.eecis.udel.edu/~mills/ntp/html/discipline.html) or even [PTP](https://en.wikipedia.org/wiki/Precision_Time_Protocol) (which needs hardware support to do right). There's no reason why Roughtime shouldn't be (almost) as precise as NTP, but the use cases that we have in mind for now don't need much precision. For example, about 25% of certificate errors shown by Chrome appear to be caused by bad local clocks and we don't need much precision to fix that.
+
+The word “secure” means that Roughtime servers sign every reply. That sounds a lot like the various secure NTP schemes, but the difference is that they negotiate a symmetric key (or hash value) with their clients, while Roughtime uses a public-key signature for every reply. (We'll get back to how to do that quickly.)
+
+A public-key signature can be verified by anyone as coming from the server, as opposed to a symmetric signature which can be created by either the client or the server. This means that Roughtime replies can be used as a time-stamping service, and thus that Roughtime servers can be used to check each other.
+
+The design looks like this: a completely fresh client generates a random nonce and sends it to a Roughtime server. The reply from the server includes the current time, the client's nonce, and a signature of them both. If the server is completely trusted, the client can stop there: it knows that the reply from the server is fresh because it includes the nonce that the client generated. It knows that it's authentic because it has a signature from the server. But if it doesn't completely trust the server it can ask another for the time:
+
+For the second request, 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. Let's assume that the times from the two servers are significantly different. If the time from the server second server is before the first, then the client has proof of misbehaviour: 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 server's misbehaviour, signed by several others, and (presumably) enough accurate replies to establish what the correct time is.
+
+We envision that clients will maintain a rolling window of signature chains and will be able to upload any proofs of misbehaviour.
+
+## Signing many requests
+
+The reason that secure NTP protocols have tried to use symmetric cryptography wherever possible is because it's much faster. As a server, having to do public-key signing on demand is daunting, especially when those demands come from UDP packets with spoofable source IP addresses. But, with a couple of key tools, we believe that it's quite viable. Firstly, elliptic-curve signature schemes can be very fast and, secondly, it's possible to sign requests in batches.
+
+According to [SUPERCOP](http://bench.cr.yp.to/results-sign.html), a Skylake chip can do an Ed25519 signature in 48,898 cycles. At 3.3GHz, that's 67,000 signatures per second, <i>per core</i>. Additionally, we can batch a number of requests together and sign all the nonces with a single signature by building a [Merkle tree](https://en.wikipedia.org/wiki/Merkle_tree) of them and signing the root. Under light load, each signature might only cover a single nonce but, if overloaded, the sizes of the batches can be allowed to increase. If batches of 64 requests are allowed then a Skylake chip can sign 4.3 million requests per core-second.
+
+At that rate, the CPU time for public-key signatures becomes insignificant compared to the work needed to handle that number of packets. Since we require that requests be padded to 1KB to avoid becoming a DDoS amplifier, a 10Gbps network link could only deliver 1.2 million requests per second anyway.
+
+It is the case that the signature, even assuming one request per batch, will add some number of microseconds of latency to the reply. Roughtime is not going to displace PTP for people who care about microseconds.
+
+## Current state of the project
+
+We currently provide implementations of the core of the protocol in both C++ and Go. The C++ code also includes a simple client (which doesn't implement [ecosystem](/ECOSYSTEM.md) features) and a simple server (which doesn't do things like automatic certificate rotation.)
+
+The Go code includes a simple server and much more complete client implementation that can query multiple servers and maintain a reply chain.
+
+(Note that the clients don't actually set the system clock yet because this is still experimental.)
+
+Google currently operates a public Roughtime server, although without any uptime assurances.
+
+Google has need of a secure time protocol in some of its products. At the moment we use [tlsdate](https://github.com/ioerror/tlsdate) in some cases but that is incompatible with TLS 1.3. We are testing the waters with this release of Roughtime to see whether there exists sufficient interest in the wider community to justify building an ecosystem around it. Although Roughtime can work in the case where a client simply trusts a single, specific server it's not the optimal design for that problem.
+
+We would be interested in (either privately or via the [mailing list](https://groups.google.com/a/chromium.org/forum/#!forum/proto-roughtime)):
+ * Expressions of interest relating to sizable clients.
+ * Expressions of interest in running high-availibility servers.
+ * Any external monitoring tools.
+ * Perhaps a time-sync daemon.
diff --git a/WORKSPACE b/WORKSPACE
new file mode 100644
index 0000000..1d303db
--- /dev/null
+++ b/WORKSPACE
@@ -0,0 +1,21 @@
+workspace(name = "roughtime")
+
+git_repository(
+ name = "boringssl",
+ commit = "9712e98fd90609a97e255eeaa5ae13c2db022620", # Sept 1st, 2016.
+ remote = "https://boringssl.googlesource.com/boringssl",
+)
+
+git_repository(
+ name = "protobuf",
+ commit = "v3.0.0",
+ remote = "https://github.com/google/protobuf",
+)
+
+new_http_archive(
+ name = "gtest",
+ url = "https://github.com/google/googletest/archive/release-1.7.0.tar.gz",
+ sha256 = "f73a6546fdf9fce9ff93a5015e0333a8af3062a152a9ad6bcb772c96687016cc",
+ build_file = "gtest.BUILD",
+ strip_prefix = "googletest-release-1.7.0",
+)
diff --git a/client.cc b/client.cc
new file mode 100644
index 0000000..68b1953
--- /dev/null
+++ b/client.cc
@@ -0,0 +1,199 @@
+/* Copyright 2016 The Roughtime Authors.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License. */
+
+#include <string>
+
+#include <stdint.h>
+
+#include <google/protobuf/stubs/logging.h>
+#include <openssl/curve25519.h>
+
+#include "client.h"
+
+namespace roughtime {
+
+std::string CreateRequest(const uint8_t nonce[kNonceLength]) {
+ uint8_t query_bytes[kMinRequestSize];
+ size_t query_len;
+
+ Builder query(query_bytes, sizeof(query_bytes), 2);
+
+ uint8_t* padding;
+
+ static_assert(kTagNONC < kTagPAD, "Tags must be written in order");
+ GOOGLE_CHECK(query.AddTagData(kTagNONC, nonce, kNonceLength) &&
+ query.AddTag(&padding, kTagPAD, kPaddingLen) &&
+ query.Finish(&query_len));
+ GOOGLE_CHECK_EQ(query_len, sizeof(query_bytes));
+
+ memset(padding, 0, kPaddingLen);
+
+ return std::string(reinterpret_cast<char*>(query_bytes), query_len);
+}
+
+bool ParseResponse(uint64_t* out_time, uint32_t* out_radius,
+ std::string* out_error,
+ const uint8_t root_public_key[ED25519_PUBLIC_KEY_LEN],
+ const uint8_t* response_bytes, size_t response_len,
+ const uint8_t nonce[kNonceLength]) {
+ *out_time = 0;
+ *out_radius = 0;
+
+ Parser response(response_bytes, response_len);
+ if (!response.is_valid()) {
+ *out_error = "structural error";
+ return false;
+ }
+
+ const uint8_t* cert_bytes;
+ size_t cert_len;
+ if (!response.GetTag(&cert_bytes, &cert_len, kTagCERT)) {
+ *out_error = "no certificate provided";
+ return false;
+ }
+
+ Parser cert(cert_bytes, cert_len);
+ if (!cert.is_valid()) {
+ *out_error = "structural error in certificate";
+ return false;
+ }
+
+ const uint8_t* signature;
+ if (!cert.GetFixedLen(&signature, kTagSIG, ED25519_SIGNATURE_LEN)) {
+ *out_error = "no signature in certificate";
+ return false;
+ }
+
+ const uint8_t* delegation_bytes;
+ size_t delegation_len;
+ if (!cert.GetTag(&delegation_bytes, &delegation_len, kTagDELE)) {
+ *out_error = "no delegation in certificate";
+ return false;
+ }
+
+ std::string signed_message =
+ std::string(kCertContextString, sizeof(kCertContextString)) +
+ std::string(reinterpret_cast<const char*>(delegation_bytes),
+ delegation_len);
+
+ if (!ED25519_verify(reinterpret_cast<const uint8_t*>(signed_message.data()),
+ signed_message.size(), signature, root_public_key)) {
+ *out_error = "bad signature in certificate";
+ return false;
+ }
+
+ const uint8_t* delegated_public_key;
+ uint64_t min_time, max_time;
+ Parser delegation(delegation_bytes, delegation_len);
+ if (!delegation.is_valid() ||
+ !delegation.Get(&min_time, kTagMINT) ||
+ !delegation.Get(&max_time, kTagMAXT) ||
+ !delegation.GetFixedLen(&delegated_public_key, kTagPUBK,
+ ED25519_PUBLIC_KEY_LEN)) {
+ *out_error = "delegation missing required value";
+ return false;
+ }
+
+ if (max_time < min_time) {
+ *out_error = "invalid delegation validity period";
+ return false;
+ }
+
+ const uint8_t* signed_response_bytes;
+ size_t signed_response_len;
+ if (!response.GetTag(&signed_response_bytes, &signed_response_len,
+ kTagSREP)) {
+ *out_error = "no signed response";
+ return false;
+ }
+
+ const uint8_t* response_signature;
+ if (!response.GetFixedLen(&response_signature, kTagSIG,
+ ED25519_SIGNATURE_LEN)) {
+ *out_error = "no signature in response";
+ return false;
+ }
+
+ signed_message =
+ std::string(kContextString, sizeof(kContextString)) +
+ std::string(reinterpret_cast<const char*>(signed_response_bytes),
+ signed_response_len);
+
+ if (!ED25519_verify(reinterpret_cast<const uint8_t*>(signed_message.data()),
+ signed_message.size(), response_signature,
+ delegated_public_key)) {
+ *out_error = "bad signature in response";
+ return false;
+ }
+
+ Parser signed_response(signed_response_bytes, signed_response_len);
+ if (!signed_response.is_valid()) {
+ *out_error = "invalid signed response in response";
+ return false;
+ }
+
+ const uint8_t* root;
+ uint64_t timestamp;
+ uint32_t radius;
+ if (!signed_response.GetFixedLen(&root, kTagROOT, kNonceLength) ||
+ !signed_response.Get(×tamp, kTagMIDP) ||
+ !signed_response.Get(&radius, kTagRADI)) {
+ *out_error = "signed response missing required values";
+ return false;
+ }
+
+ if (timestamp < min_time || max_time < timestamp) {
+ *out_error = "timestamp out of range for delegation";
+ return false;
+ }
+
+ const uint8_t* path;
+ size_t path_len;
+ uint32_t tree_index;
+ if (!response.Get(&tree_index, kTagINDX) ||
+ !response.GetTag(&path, &path_len, kTagPATH)) {
+ *out_error = "response missing required values";
+ return false;
+ }
+
+ uint8_t hash[kNonceLength];
+ HashLeaf(hash, nonce);
+
+ if (path_len % kNonceLength != 0) {
+ *out_error = "tree path is not a multiple of the hash size";
+ return false;
+ }
+
+ for (size_t i = 0; i < path_len; i += kNonceLength) {
+ const bool path_element_is_right = tree_index & 1;
+ if (path_element_is_right) {
+ HashNode(hash, hash, path + i);
+ } else {
+ HashNode(hash, path + i, hash);
+ }
+ tree_index /= 2;
+ }
+
+ if (memcmp(root, hash, kNonceLength) != 0) {
+ *out_error = "calculated tree root doesn't match signed root";
+ return false;
+ }
+
+ *out_time = timestamp;
+ *out_radius = radius;
+
+ return true;
+}
+
+} // namespace roughtime
diff --git a/client.h b/client.h
new file mode 100644
index 0000000..fbe22ac
--- /dev/null
+++ b/client.h
@@ -0,0 +1,39 @@
+/* Copyright 2016 The Roughtime Authors.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License. */
+
+#ifndef SECURITY_ROUGHTIME_CLIENT_H_
+#define SECURITY_ROUGHTIME_CLIENT_H_
+
+#include <string>
+
+#include "protocol.h"
+
+namespace roughtime {
+
+// Creates a client time request with the supplied |nonce|.
+std::string CreateRequest(const uint8_t nonce[kNonceLength]);
+
+// If the supplied |response_bytes| can be parsed, sets |*out_time| and
+// |*out_radius| and returns true. Otherwise returns false and sets
+// |*out_error|. The response must contain a path from the supplied |nonce|
+// and a certificate signed with a private key that matches |root_public_key|.
+bool ParseResponse(uint64_t *out_time, uint32_t *out_radius,
+ std::string *out_error,
+ const uint8_t root_public_key[ED25519_PUBLIC_KEY_LEN],
+ const uint8_t *response_bytes, size_t response_len,
+ const uint8_t nonce[kNonceLength]);
+
+} // namespace roughtime
+
+#endif // SECURITY_ROUGHTIME_CLIENT_H_
diff --git a/client_test.cc b/client_test.cc
new file mode 100644
index 0000000..45c3569
--- /dev/null
+++ b/client_test.cc
@@ -0,0 +1,274 @@
+/* Copyright 2016 The Roughtime Authors.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License. */
+
+#include <string>
+
+#include "gtest/gtest.h"
+#include <openssl/curve25519.h>
+#include <openssl/rand.h>
+
+#include "client.h"
+#include "open_source_fillins.h"
+
+namespace roughtime {
+
+TEST(CreateRequest, RequestIsValid) {
+ uint8_t nonce[kNonceLength];
+ memset(nonce, 'a', kNonceLength);
+
+ std::string request = CreateRequest(nonce);
+ EXPECT_EQ(kMinRequestSize, request.size());
+ Parser parser(reinterpret_cast<const uint8_t*>(request.data()),
+ request.size());
+ ASSERT_TRUE(parser.is_valid());
+
+ const uint8_t* request_nonce;
+ EXPECT_TRUE(parser.GetFixedLen(&request_nonce, kTagNONC, kNonceLength));
+ EXPECT_EQ(0, memcmp(nonce, request_nonce, kNonceLength));
+
+ const uint8_t* pad;
+ size_t pad_len;
+ EXPECT_TRUE(parser.GetTag(&pad, &pad_len, kTagPAD));
+ EXPECT_GE(pad_len, 0);
+}
+
+struct ResponseBuilder {
+ uint8_t nonce[kNonceLength]; // Client's nonce.
+
+ // Delegation.
+ uint8_t delegated_private_key[ED25519_PRIVATE_KEY_LEN];
+ uint8_t delegated_public_key[ED25519_PUBLIC_KEY_LEN];
+ uint8_t delegation[kMinRequestSize];
+ size_t delegation_len;
+
+ // Certificate (incorporates the delegation).
+ uint8_t root_private_key[ED25519_PRIVATE_KEY_LEN];
+ uint8_t root_public_key[ED25519_PUBLIC_KEY_LEN];
+ uint8_t public_key_signature[ED25519_SIGNATURE_LEN];
+ uint8_t cert[kMinRequestSize];
+ size_t cert_len;
+
+ // The signed portion of the response (tree root and timestamp), signed by the
+ // delegated key.
+ uint8_t tree_root[kNonceLength];
+ uint8_t signed_response[kMinRequestSize];
+ size_t signed_response_len;
+
+ // The final response, consisting of the signed portion, signature, Merkle
+ // tree path, and certificate.
+ uint32_t tree_index;
+ uint8_t tree_path[32 * kNonceLength];
+ size_t tree_path_len;
+ uint8_t response[kMinRequestSize];
+ uint8_t response_signature[ED25519_SIGNATURE_LEN];
+ size_t response_len;
+
+ std::string out_error;
+ uint64_t out_time;
+ uint32_t out_radius;
+
+ // Call the below functions in order to create a response.
+ ResponseBuilder();
+ void MakeDelegation(uint64_t mint, uint64_t maxt);
+ void MakeDelegation() { MakeDelegation(999, 1001); }
+ void MakeCertificate(const uint8_t* private_key);
+ void MakeCertificate() { MakeCertificate(root_private_key); }
+ void MakeTree(uint32_t index);
+ void MakeTree() { MakeTree(0); }
+ void MakeSigned(uint64_t now);
+ void MakeSigned() { MakeSigned(1000); }
+ void MakeResponse(const uint8_t* private_key);
+ void MakeResponse() { MakeResponse(delegated_private_key); }
+ bool ParseResponse(uint8_t nonce[kNonceLength]);
+ bool ParseResponse() { return ParseResponse(nonce); }
+};
+
+ResponseBuilder::ResponseBuilder() {
+ memset(nonce, 'a', kNonceLength);
+ ED25519_keypair(delegated_public_key, delegated_private_key);
+ ED25519_keypair(root_public_key, root_private_key);
+}
+
+void ResponseBuilder::MakeDelegation(uint64_t mint, uint64_t maxt) {
+ Builder builder(delegation, arraysize(delegation), 3);
+ ASSERT_TRUE(builder.AddTagData(kTagPUBK, delegated_public_key,
+ arraysize(delegated_public_key)));
+ ASSERT_TRUE(builder.AddTagData(
+ kTagMINT, reinterpret_cast<const uint8_t*>(&mint), sizeof(mint)));
+ ASSERT_TRUE(builder.AddTagData(
+ kTagMAXT, reinterpret_cast<const uint8_t*>(&maxt), sizeof(maxt)));
+ ASSERT_TRUE(builder.Finish(&delegation_len));
+}
+
+void ResponseBuilder::MakeCertificate(const uint8_t* private_key) {
+ size_t context_len = arraysize(kCertContextString);
+ uint8_t to_sign[kMinRequestSize];
+ ASSERT_LE(delegation_len + context_len, sizeof(to_sign));
+ memcpy(to_sign, kCertContextString, context_len);
+ memcpy(to_sign + context_len, delegation, delegation_len);
+ ASSERT_TRUE(ED25519_sign(public_key_signature, to_sign,
+ context_len + delegation_len, private_key));
+ Builder builder(cert, arraysize(cert), 2);
+ ASSERT_TRUE(builder.AddTagData(kTagSIG, public_key_signature,
+ arraysize(public_key_signature)));
+ ASSERT_TRUE(builder.AddTagData(kTagDELE, delegation, delegation_len));
+ ASSERT_TRUE(builder.Finish(&cert_len));
+}
+
+void ResponseBuilder::MakeTree(uint32_t i) {
+ tree_index = i;
+ HashLeaf(tree_root, nonce);
+ for (tree_path_len = 0; i > 0; i >>= 1) {
+ const bool path_element_is_right = i & 1;
+ uint8_t* sibling = tree_path + tree_path_len;
+ RAND_bytes(sibling, kNonceLength);
+ if (path_element_is_right) {
+ HashNode(tree_root, tree_root, sibling);
+ } else {
+ HashNode(tree_root, sibling, tree_root);
+ }
+ tree_path_len += kNonceLength;
+ }
+}
+
+void ResponseBuilder::MakeSigned(uint64_t now) {
+ Builder builder(signed_response, arraysize(signed_response), 3);
+ static const uint32_t kRadius = 1000000;
+ builder.AddTagData(kTagRADI, reinterpret_cast<const uint8_t*>(&kRadius),
+ sizeof(kRadius));
+ builder.AddTagData(kTagMIDP, reinterpret_cast<const uint8_t*>(&now),
+ sizeof(now));
+ builder.AddTagData(kTagROOT, tree_root, arraysize(tree_root));
+ builder.Finish(&signed_response_len);
+}
+
+void ResponseBuilder::MakeResponse(const uint8_t* private_key) {
+ size_t context_len = arraysize(kContextString);
+ uint8_t to_sign[kMinRequestSize];
+ ASSERT_LE(signed_response_len + context_len, sizeof(to_sign));
+ memcpy(to_sign, kContextString, context_len);
+ memcpy(to_sign + context_len, signed_response, signed_response_len);
+ ASSERT_TRUE(ED25519_sign(response_signature, to_sign,
+ context_len + signed_response_len, private_key));
+ Builder builder(response, arraysize(response), 5);
+ ASSERT_TRUE(builder.AddTagData(kTagSIG, response_signature,
+ arraysize(response_signature)));
+ ASSERT_TRUE(builder.AddTagData(kTagPATH, tree_path, tree_path_len));
+ ASSERT_TRUE(
+ builder.AddTagData(kTagSREP, signed_response, signed_response_len));
+ ASSERT_TRUE(builder.AddTagData(kTagCERT, cert, cert_len));
+ ASSERT_TRUE(builder.AddTagData(kTagINDX,
+ reinterpret_cast<const uint8_t*>(&tree_index),
+ sizeof(tree_index)));
+ ASSERT_TRUE(builder.Finish(&response_len));
+}
+
+bool ResponseBuilder::ParseResponse(uint8_t nonce[kNonceLength]) {
+ return ::roughtime::ParseResponse(&out_time, &out_radius, &out_error,
+ root_public_key, response, response_len,
+ nonce);
+}
+
+TEST(ParseResponse, ValidResponse) {
+ ResponseBuilder builder;
+ builder.MakeDelegation();
+ builder.MakeCertificate();
+ builder.MakeTree();
+ builder.MakeSigned();
+ builder.MakeResponse();
+ EXPECT_TRUE(builder.ParseResponse()) << builder.out_error;
+ EXPECT_EQ(1000, builder.out_time);
+}
+
+TEST(ParseResponse, BadTreeRoot) {
+ ResponseBuilder builder;
+ builder.MakeDelegation();
+ builder.MakeCertificate();
+ builder.MakeTree();
+ memset(builder.tree_root, 0, kNonceLength);
+ builder.MakeSigned();
+ builder.MakeResponse();
+ EXPECT_FALSE(builder.ParseResponse());
+}
+
+TEST(ParseResponse, TestAllTreeIndices) {
+ for (uint32_t i = 0; i <= 32; i++) {
+ ResponseBuilder builder;
+ builder.MakeDelegation();
+ builder.MakeCertificate();
+ builder.MakeTree(i);
+ builder.MakeSigned();
+ builder.MakeResponse();
+ EXPECT_TRUE(builder.ParseResponse()) << "failed at index " << i;
+ EXPECT_EQ(1000, builder.out_time);
+ }
+}
+
+TEST(ParseResponse, WrongKeyUsedToSignResponse) {
+ ResponseBuilder builder;
+ builder.MakeDelegation();
+ builder.MakeCertificate();
+ builder.MakeTree();
+ builder.MakeSigned();
+ uint8_t garbage[ED25519_PRIVATE_KEY_LEN];
+ memset(garbage, 0, arraysize(garbage));
+ builder.MakeResponse(garbage);
+ EXPECT_FALSE(builder.ParseResponse());
+}
+
+TEST(ParseResponse, WrongKeyUsedToSignCert) {
+ ResponseBuilder builder;
+ builder.MakeDelegation();
+ uint8_t garbage[ED25519_PRIVATE_KEY_LEN];
+ memset(garbage, 0, arraysize(garbage));
+ builder.MakeCertificate(garbage);
+ builder.MakeTree();
+ builder.MakeSigned();
+ builder.MakeResponse();
+ EXPECT_FALSE(builder.ParseResponse());
+}
+
+TEST(ParseResponse, InvalidDelegationTimes) {
+ ResponseBuilder builder;
+ builder.MakeDelegation(1001, 999); // Order reversed.
+ builder.MakeCertificate();
+ builder.MakeTree();
+ builder.MakeSigned();
+ builder.MakeResponse();
+ EXPECT_FALSE(builder.ParseResponse());
+}
+
+TEST(ParseResponse, TimeOutsideDelegation) {
+ ResponseBuilder builder;
+ builder.MakeDelegation();
+ builder.MakeCertificate();
+ builder.MakeTree();
+ builder.MakeSigned(1002); // Outside bounds.
+ builder.MakeResponse();
+ EXPECT_FALSE(builder.ParseResponse());
+}
+
+TEST(ParseResponse, NonceNotInTree) {
+ ResponseBuilder builder;
+ builder.MakeDelegation();
+ builder.MakeCertificate();
+ builder.MakeTree();
+ builder.MakeSigned();
+ builder.MakeResponse();
+ uint8_t nonce[kNonceLength];
+ memset(nonce, 'b', arraysize(nonce));
+ EXPECT_FALSE(builder.ParseResponse(nonce)); // Not the nonce in the request.
+}
+
+} // namespace roughtime
diff --git a/clock_linux.cc b/clock_linux.cc
new file mode 100644
index 0000000..cdd17f8
--- /dev/null
+++ b/clock_linux.cc
@@ -0,0 +1,45 @@
+/* Copyright 2016 The Roughtime Authors.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License. */
+
+
+#if defined(__linux)
+
+#include <stdint.h>
+#include <stdlib.h>
+#include <time.h>
+
+namespace roughtime {
+
+// TimeUs returns the current value of the specified clock in microseconds.
+static uint64_t TimeUs(clockid_t clock) {
+ struct timespec tv;
+ if (clock_gettime(clock, &tv)) {
+ abort();
+ }
+
+ uint64_t ret = tv.tv_sec;
+ ret *= 1000000;
+ ret += tv.tv_nsec / 1000;
+ return ret;
+}
+
+// MonotonicUs returns the value of the monotonic clock in microseconds.
+uint64_t MonotonicUs() { return TimeUs(CLOCK_MONOTONIC); }
+
+// MonotonicUs returns the value of the realtime clock in microseconds.
+uint64_t RealtimeUs() { return TimeUs(CLOCK_REALTIME); }
+
+} // namespace roughtime
+
+#endif // __linux
diff --git a/clock_macos.cc b/clock_macos.cc
new file mode 100644
index 0000000..a6cdf5d
--- /dev/null
+++ b/clock_macos.cc
@@ -0,0 +1,52 @@
+/* Copyright 2016 The Roughtime Authors.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License. */
+
+
+#if defined(__APPLE__)
+
+#include <mach/clock.h>
+#include <mach/mach.h>
+#include <stdint.h>
+#include <stdlib.h>
+#include <time.h>
+
+namespace roughtime {
+
+// TimeUs returns the current value of the specified clock in microseconds.
+static uint64_t TimeUs(clock_id_t clock) {
+ clock_serv_t clock_ref;
+ mach_timespec_t tv;
+
+ if (host_get_clock_service(mach_host_self(), clock, &clock_ref) !=
+ KERN_SUCCESS ||
+ clock_get_time(clock_ref, &tv) != KERN_SUCCESS ||
+ mach_port_deallocate(mach_task_self(), clock_ref) != KERN_SUCCESS) {
+ abort();
+ }
+
+ uint64_t ret = tv.tv_sec;
+ ret *= 1000000;
+ ret += tv.tv_nsec / 1000;
+ return ret;
+}
+
+// MonotonicUs returns the value of the monotonic clock in microseconds.
+uint64_t MonotonicUs() { return TimeUs(REALTIME_CLOCK); }
+
+// MonotonicUs returns the value of the realtime clock in microseconds.
+uint64_t RealtimeUs() { return TimeUs(CALENDAR_CLOCK); }
+
+} // namespace roughtime
+
+#endif // __linux
diff --git a/config.proto b/config.proto
new file mode 100644
index 0000000..bd70816
--- /dev/null
+++ b/config.proto
@@ -0,0 +1,59 @@
+syntax = "proto3";
+package roughtime.config;
+
+// These protobufs are only used with JSON serialisation so we attempt to emit
+// as little C++ code as possible.
+option optimize_for = CODE_SIZE;
+
+// ServersJSON represents a JSON format for distributing information about
+// Roughtime servers.
+message ServersJSON {
+ // created contains the RFC3339 time when the JSON file was created.
+ string created = 1;
+ // expires contains the RFC3339 time when the information in this JSON file
+ // expires.
+ string expires = 2;
+ repeated Server servers = 3;
+}
+
+// Server represents a Roughtime server in a JSON configuration.
+message Server {
+ string name = 1;
+ // public_key_type specifies the type of the public key contained in
+ // |PublicKey|. Normally this will be "ed25519" but implementations should
+ // ignore entries with unknown key types.
+ string public_key_type = 2;
+ bytes public_key = 3;
+ repeated ServerAddress addresses = 4;
+}
+
+// ServerAddress represents the address of a Roughtime server in a JSON
+// configuration.
+message ServerAddress {
+ string protocol = 1;
+ // address contains a protocol specific address. For the protocol "udp", the
+ // address has the form "host:port" where host is either a DNS name, an IPv4
+ // literal, or an IPv6 literal in square brackets.
+ string address = 2;
+}
+
+// Chain represents a history of Roughtime queries where each provably follows
+// the previous one.
+message Chain {
+ repeated Link links = 1;
+}
+
+// Link represents an entry in a Chain.
+message Link {
+ // public_key_type specifies the type of public key contained in
+ // |PublicKey|. See the same field in |Server| for details.
+ string public_key_type = 1;
+ bytes server_public_key = 2;
+ // nonce_or_blind contains either the full nonce (only for the first |Link|
+ // in a |Chain|) or else contains a blind value that is combined with the
+ // previous reply to make the next nonce. In either case, the value is 64
+ // bytes long.
+ bytes nonce_or_blind = 3;
+ // reply contains the reply from the server.
+ bytes reply = 4;
+}
diff --git a/go/client/client.go b/go/client/client.go
new file mode 100644
index 0000000..19d6bf4
--- /dev/null
+++ b/go/client/client.go
@@ -0,0 +1,534 @@
+// Copyright 2016 The Roughtime Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License. */
+
+// client is a somewhat featured Roughtime client.
+package main
+
+import (
+ "crypto/rand"
+ "encoding/binary"
+ "encoding/json"
+ "errors"
+ "fmt"
+ "io"
+ "net"
+ "time"
+
+ "math/big"
+ mathrand "math/rand"
+
+ "golang.org/x/crypto/ed25519"
+ "roughtime.googlesource.com/go/client/monotime"
+ "roughtime.googlesource.com/go/config"
+ "roughtime.googlesource.com/go/protocol"
+)
+
+const (
+ // defaultMaxRadius is the maximum radius that we'll accept from a
+ // server.
+ defaultMaxRadius = 10 * time.Second
+
+ // defaultMaxDifference is the maximum difference in time between any
+ // sample from a server and the quorum-agreed time before we believe
+ // that the server might be misbehaving.
+ defaultMaxDifference = 60 * time.Second
+
+ // defaultTimeout is the default maximum time that a server has to
+ // answer a query.
+ defaultTimeout = 2 * time.Second
+
+ // defaultNumQueries is the default number of times we will try to
+ // query a server.
+ defaultNumQueries = 3
+)
+
+// Client represents a Roughtime client and exposes a number of members that
+// can be set in order to configure it. The zero value of a Client is always
+// ready to use and will set sensible defaults.
+type Client struct {
+ // Permutation returns a random permutation of [0‥n) that is used to
+ // query servers in a random order. If nil, a sensible default is used.
+ Permutation func(n int) []int
+
+ // MaxRadiusUs is the maximum interval radius that will be accepted
+ // from a server. If zero, a sensible default is used.
+ MaxRadius time.Duration
+
+ // MaxDifference is the maximum difference in time between any sample
+ // from a server and the quorum-agreed time before that sample is
+ // considered suspect. If zero, a sensible default is used.
+ MaxDifference time.Duration
+
+ // QueryTimeout is the amount of time a server has to reply to a query.
+ // If zero, a sensible default will be used.
+ QueryTimeout time.Duration
+
+ // NumQueries is the maximum number of times a query will be sent to a
+ // specific server before giving up. If <= zero, a sensible default
+ // will be used.
+ NumQueries int
+
+ // now returns a monotonic duration from some unspecified epoch. If
+ // nil, the system monotonic time will be used.
+ nowFunc func() time.Duration
+}
+
+func (c *Client) now() time.Duration {
+ if c.nowFunc != nil {
+ return c.nowFunc()
+ }
+ return monotime.Now()
+}
+
+func (c *Client) permutation(n int) []int {
+ if c.Permutation != nil {
+ return c.Permutation(n)
+ }
+
+ var randBuf [8]byte
+ if _, err := io.ReadFull(rand.Reader, randBuf[:]); err != nil {
+ panic(err)
+ }
+
+ seed := binary.LittleEndian.Uint64(randBuf[:])
+ rand := mathrand.New(mathrand.NewSource(int64(seed)))
+
+ return rand.Perm(n)
+}
+
+func (c *Client) maxRadius() time.Duration {
+ if c.MaxRadius != 0 {
+ return c.MaxRadius
+ }
+
+ return defaultMaxRadius
+}
+
+func (c *Client) maxDifference() time.Duration {
+ if c.MaxDifference != 0 {
+ return c.MaxDifference
+ }
+
+ return defaultMaxDifference
+}
+
+func (c *Client) queryTimeout() time.Duration {
+ if c.QueryTimeout != 0 {
+ return c.QueryTimeout
+ }
+
+ return defaultTimeout
+}
+
+func (c *Client) numQueries() int {
+ if c.NumQueries > 0 {
+ return c.NumQueries
+ }
+
+ return defaultNumQueries
+}
+
+// LoadChain loads a JSON-format chain from the given JSON data.
+func LoadChain(jsonData []byte) (chain *config.Chain, err error) {
+ chain = new(config.Chain)
+ if err := json.Unmarshal(jsonData, chain); err != nil {
+ return nil, err
+ }
+
+ for i, link := range chain.Links {
+ if link.PublicKeyType != "ed25519" {
+ return nil, fmt.Errorf("client: link #%d in chain file has unknown public key type %q", i, link.PublicKeyType)
+ }
+
+ if l := len(link.PublicKey); l != ed25519.PublicKeySize {
+ return nil, fmt.Errorf("client: link #%d in chain file has bad public key of length %d", i, l)
+ }
+
+ if l := len(link.NonceOrBlind); l != protocol.NonceSize {
+ return nil, fmt.Errorf("client: link #%d in chain file has bad nonce/blind of length %d", i, l)
+ }
+
+ var nonce [protocol.NonceSize]byte
+ if i == 0 {
+ copy(nonce[:], link.NonceOrBlind[:])
+ } else {
+ nonce = protocol.CalculateChainNonce(chain.Links[i-1].Reply, link.NonceOrBlind[:])
+ }
+
+ if _, _, err := protocol.VerifyReply(link.Reply, link.PublicKey, nonce); err != nil {
+ return nil, fmt.Errorf("client: failed to verify link #%d in chain file", i)
+ }
+ }
+
+ return chain, nil
+}
+
+// timeSample represents a time sample from the network.
+type timeSample struct {
+ // server references the server that was queried.
+ server *config.Server
+
+ // base is a monotonic clock sample that is taken at a time before the
+ // network could have answered the query.
+ base *big.Int
+
+ // min is the minimum real-time (in Roughtime UTC microseconds) that
+ // could correspond to |base| (i.e. midpoint - radius).
+ min *big.Int
+
+ // max is the maximum real-time (in Roughtime UTC microseconds) that
+ // could correspond to |base| (i.e. midpoint + radius + query time).
+ max *big.Int
+}
+
+// midpoint returns the average of the min and max times.
+func (s *timeSample) midpoint() *big.Int {
+ ret := new(big.Int).Add(s.min, s.max)
+ return ret.Rsh(ret, 1)
+}
+
+// alignTo updates s so that its base value matches that from reference.
+func (s *timeSample) alignTo(reference *timeSample) {
+ delta := new(big.Int).Sub(s.base, reference.base)
+ s.base.Sub(s.base, delta)
+ s.min.Sub(s.min, delta)
+ s.max.Sub(s.max, delta)
+}
+
+// overlaps returns true iff s and other have any timespan in common.
+func (s *timeSample) overlaps(other *timeSample) bool {
+ return s.max.Cmp(other.min) >= 0 && other.max.Cmp(s.min) >= 0
+}
+
+// overlapsAll returns true iff s has s timespan in common with all of the
+// elements of others.
+func (s *timeSample) overlapsAll(others []*timeSample) bool {
+ for _, other := range others {
+ if !s.overlaps(other) {
+ return false
+ }
+ }
+
+ return true
+}
+
+// query sends a request to s, appends it to chain, and returns the resulting
+// timeSample.
+func (c *Client) query(server *config.Server, chain *config.Chain) (*timeSample, error) {
+ var prevReply []byte
+ if len(chain.Links) > 0 {
+ prevReply = chain.Links[len(chain.Links)-1].Reply
+ }
+
+ var baseTime, replyTime time.Duration
+ var reply []byte
+ var nonce, blind [protocol.NonceSize]byte
+
+ for attempts := 0; attempts < c.numQueries(); attempts++ {
+ var request []byte
+ var err error
+ if nonce, blind, request, err = protocol.CreateRequest(rand.Reader, prevReply); err != nil {
+ return nil, err
+ }
+ if len(request) < protocol.MinRequestSize {
+ panic("internal error: bad request length")
+ }
+
+ udpAddr, err := serverUDPAddr(server)
+ if err != nil {
+ panic(err)
+ }
+
+ conn, err := net.DialUDP("udp", nil, udpAddr)
+ if err != nil {
+ return nil, err
+ }
+
+ conn.SetReadDeadline(time.Now().Add(c.queryTimeout()))
+ baseTime = c.now()
+ conn.Write(request)
+
+ var replyBytes [1024]byte
+ n, err := conn.Read(replyBytes[:])
+ if err == nil {
+ replyTime = c.now()
+ reply = replyBytes[:n]
+ break
+ }
+
+ if netErr, ok := err.(net.Error); ok {
+ if !netErr.Timeout() {
+ return nil, errors.New("client: error reading from UDP socket: " + err.Error())
+ }
+ }
+ }
+
+ if reply == nil {
+ return nil, fmt.Errorf("client: no reply from server %q", server.Name)
+ }
+
+ if replyTime < baseTime {
+ panic("broken monotonic clock")
+ }
+ queryDuration := replyTime - baseTime
+
+ midpoint, radius, err := protocol.VerifyReply(reply, server.PublicKey, nonce)
+ if err != nil {
+ return nil, err
+ }
+
+ if time.Duration(radius)*time.Microsecond > c.maxRadius() {
+ return nil, fmt.Errorf("client: radius (%d) too large", radius)
+ }
+
+ nonceOrBlind := blind[:]
+ if len(prevReply) == 0 {
+ nonceOrBlind = nonce[:]
+ }
+
+ chain.Links = append(chain.Links, config.Link{
+ PublicKeyType: "ed25519",
+ PublicKey: server.PublicKey,
+ NonceOrBlind: nonceOrBlind,
+ Reply: reply,
+ })
+
+ bigRadius := new(big.Int).SetUint64(uint64(radius))
+ min := new(big.Int).SetUint64(midpoint)
+ min.Sub(min, bigRadius)
+
+ max := new(big.Int).SetUint64(midpoint)
+ max.Add(max, bigRadius)
+ max.Add(max, new(big.Int).SetInt64(int64(queryDuration/time.Microsecond)))
+
+ return &timeSample{
+ server: server,
+ base: new(big.Int).SetInt64(int64(baseTime)),
+ min: min,
+ max: max,
+ }, nil
+}
+
+func serverUDPAddr(server *config.Server) (*net.UDPAddr, error) {
+ for _, addr := range server.Addresses {
+ if addr.Protocol != "udp" {
+ continue
+ }
+
+ return net.ResolveUDPAddr("udp", addr.Address)
+ }
+
+ return nil, nil
+}
+
+// LoadServers loads information about known servers from the given JSON data.
+// It only extracts information about servers with Ed25519 public keys and UDP
+// address. The number of servers skipped because of unsupported requirements
+// is returned in numSkipped.
+func LoadServers(jsonData []byte) (servers []config.Server, numSkipped int, err error) {
+ var serversJSON config.ServersJSON
+ if err := json.Unmarshal(jsonData, &serversJSON); err != nil {
+ return nil, 0, err
+ }
+
+ seenNames := make(map[string]struct{})
+
+ for _, candidate := range serversJSON.Servers {
+ if _, ok := seenNames[candidate.Name]; ok {
+ return nil, 0, fmt.Errorf("client: duplicate server name %q", candidate.Name)
+ }
+ seenNames[candidate.Name] = struct{}{}
+
+ if candidate.PublicKeyType != "ed25519" {
+ numSkipped++
+ continue
+ }
+
+ udpAddr, err := serverUDPAddr(&candidate)
+
+ if err != nil {
+ return nil, 0, fmt.Errorf("client: server %q lists invalid UDP address: %s", candidate.Name, err)
+ }
+
+ if udpAddr == nil {
+ numSkipped++
+ continue
+ }
+
+ servers = append(servers, candidate)
+ }
+
+ if len(servers) == 0 {
+ return nil, 0, errors.New("client: no usable servers found")
+ }
+
+ return servers, 0, nil
+}
+
+// trimChain drops elements from the beginning of chain, as needed, so that its
+// length is <= n.
+func trimChain(chain *config.Chain, n int) {
+ if n <= 0 {
+ chain.Links = nil
+ return
+ }
+
+ if len(chain.Links) <= n {
+ return
+ }
+
+ numToTrim := len(chain.Links) - n
+ for i := 0; i < numToTrim; i++ {
+ // The NonceOrBlind of the first element is special because
+ // it's an nonce. All the others are blinds and are combined
+ // with the previous reply to make the nonce. That's not
+ // possible for the first element because there is no previous
+ // reply. Therefore, when removing the first element the blind
+ // of the next element needs to be converted to an nonce.
+ nonce := protocol.CalculateChainNonce(chain.Links[0].Reply, chain.Links[1].NonceOrBlind[:])
+ chain.Links[1].NonceOrBlind = nonce[:]
+ chain.Links = chain.Links[1:]
+ }
+}
+
+// intersection returns the timespan common to all the elements in samples,
+// which must be aligned to the same base. The caller must ensure that such a
+// timespan exists.
+func intersection(samples []*timeSample) *timeSample {
+ ret := &timeSample{
+ base: samples[0].base,
+ min: new(big.Int).Set(samples[0].min),
+ max: new(big.Int).Set(samples[0].max),
+ }
+
+ for _, sample := range samples[1:] {
+ if ret.min.Cmp(sample.min) < 0 {
+ sample.min.Set(ret.min)
+ }
+ if ret.max.Cmp(sample.max) > 0 {
+ sample.max.Set(ret.max)
+ }
+ }
+
+ return ret
+}
+
+// findNOverlapping finds an n-element subset of samples where all the
+// members overlap. It returns the intersection if such a subset exists.
+func findNOverlapping(samples []*timeSample, n int) (sampleIntersection *timeSample, ok bool) {
+ switch {
+ case n <= 0:
+ return nil, false
+ case n == 1:
+ return samples[0], true
+ }
+
+ overlapping := make([]*timeSample, 0, n)
+
+ for i, initial := range samples {
+ overlapping = append(overlapping, initial)
+
+ for _, candidate := range samples[i+1:] {
+ if candidate.overlapsAll(overlapping) {
+ overlapping = append(overlapping, candidate)
+ }
+
+ if len(overlapping) == n {
+ return intersection(overlapping), true
+ }
+ }
+
+ overlapping = overlapping[:0]
+ }
+
+ return nil, false
+}
+
+// TimeResult is the result of trying to establish the current time by querying
+// a number of servers.
+type TimeResult struct {
+ // MonoUTCDelta may be nil, in which case a time could not be
+ // established. Otherwise it contains the difference between the
+ // Roughtime epoch and the monotonic clock.
+ MonoUTCDelta *time.Duration
+
+ // ServerErrors maps from server name to query error.
+ ServerErrors map[string]error
+
+ // OutOfRangeAnswer is true if one or more of the queries contained a
+ // significantly incorrect time, as defined by MaxDifference. In this
+ // case, the reply will have been recorded in the chain.
+ OutOfRangeAnswer bool
+}
+
+// EstablishTime queries a number of servers until it has a quorum of
+// overlapping results, or it runs out of servers. Results from the querying
+// the servers are appended to chain.
+func (c *Client) EstablishTime(chain *config.Chain, quorum int, servers []config.Server) (TimeResult, error) {
+ perm := c.permutation(len(servers))
+ var samples []*timeSample
+ var intersection *timeSample
+ var result TimeResult
+
+ for len(perm) > 0 {
+ server := &servers[perm[0]]
+ perm = perm[1:]
+
+ sample, err := c.query(server, chain)
+ if err != nil {
+ if result.ServerErrors == nil {
+ result.ServerErrors = make(map[string]error)
+ }
+ result.ServerErrors[server.Name] = err
+ continue
+ }
+
+ if len(samples) > 0 {
+ sample.alignTo(samples[0])
+ }
+ samples = append(samples, sample)
+
+ var ok bool
+ if intersection, ok = findNOverlapping(samples, quorum); ok {
+ break
+ }
+ intersection = nil
+ }
+
+ if intersection == nil {
+ return result, nil
+ }
+ midpoint := intersection.midpoint()
+
+ maxDifference := new(big.Int).SetUint64(uint64(c.maxDifference() / time.Microsecond))
+ for _, sample := range samples {
+ delta := new(big.Int).Sub(midpoint, sample.midpoint())
+ delta.Abs(delta)
+
+ if delta.Cmp(maxDifference) > 0 {
+ result.OutOfRangeAnswer = true
+ break
+ }
+ }
+
+ midpoint.Mul(midpoint, big.NewInt(1000))
+ delta := new(big.Int).Sub(midpoint, intersection.base)
+ if delta.BitLen() > 63 {
+ return result, errors.New("client: cannot represent difference between monotonic and UTC time")
+ }
+ monoUTCDelta := time.Duration(delta.Int64())
+ result.MonoUTCDelta = &monoUTCDelta
+
+ return result, nil
+}
diff --git a/go/client/client_test.go b/go/client/client_test.go
new file mode 100644
index 0000000..bebec9f
--- /dev/null
+++ b/go/client/client_test.go
@@ -0,0 +1,335 @@
+// Copyright 2016 The Roughtime Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License. */
+
+package main
+
+import (
+ "crypto/rand"
+ "encoding/json"
+ "net"
+ "strconv"
+ "sync"
+ "testing"
+ "time"
+
+ "golang.org/x/crypto/ed25519"
+ "roughtime.googlesource.com/go/config"
+ "roughtime.googlesource.com/go/protocol"
+)
+
+const (
+ nonsenseReply = ^time.Duration(0)
+ maxRadius = 10 * time.Second
+)
+
+type timeSpan struct {
+ midpoint uint64
+ radius time.Duration
+}
+
+var timeEstablishmentTests = []struct {
+ quorum int
+ times []timeSpan
+ shouldEstablish bool
+ shouldSignalMisbehaviour bool
+ shouldHaveErrors []int
+}{
+ {
+ quorum: 1,
+ times: []timeSpan{
+ timeSpan{10, 5},
+ },
+ shouldEstablish: true,
+ },
+ {
+ quorum: 1,
+ times: []timeSpan{
+ timeSpan{10, 5},
+ timeSpan{20, 5},
+ },
+ shouldEstablish: true,
+ },
+ {
+ quorum: 2,
+ times: []timeSpan{
+ timeSpan{100e6, maxRadius},
+ timeSpan{200e6, maxRadius},
+ },
+ shouldEstablish: false,
+ },
+ {
+ quorum: 2,
+ times: []timeSpan{
+ timeSpan{175e6, maxRadius},
+ timeSpan{200e6, maxRadius},
+ timeSpan{201e6, maxRadius},
+ },
+ shouldEstablish: true,
+ },
+ {
+ quorum: 3,
+ times: []timeSpan{
+ timeSpan{100e6, maxRadius},
+ timeSpan{101e6, maxRadius},
+ timeSpan{102e6, maxRadius},
+ },
+ shouldEstablish: true,
+ },
+ {
+ quorum: 3,
+ times: []timeSpan{
+ timeSpan{175e6, maxRadius},
+ timeSpan{175e6, maxRadius},
+ timeSpan{200e6, maxRadius},
+ timeSpan{200e6, maxRadius},
+ timeSpan{200e6, maxRadius},
+ timeSpan{200e6, maxRadius},
+ timeSpan{200e6, maxRadius},
+ timeSpan{200e6, maxRadius},
+ timeSpan{200e6, maxRadius},
+ timeSpan{175e6, maxRadius},
+ },
+ shouldEstablish: true,
+ },
+ {
+ // An excessive radius should be rejected as invalid.
+ quorum: 3,
+ times: []timeSpan{
+ timeSpan{200e6, 1 * time.Hour},
+ timeSpan{200e6, maxRadius},
+ timeSpan{200e6, maxRadius},
+ },
+ shouldHaveErrors: []int{0},
+ shouldEstablish: false,
+ },
+ {
+ // A zero radius is acceptable if the midpoint is reasonable.
+ quorum: 3,
+ times: []timeSpan{
+ timeSpan{200e6, 0},
+ timeSpan{200e6, maxRadius},
+ timeSpan{200e6, maxRadius},
+ },
+ shouldEstablish: true,
+ },
+ {
+ quorum: 3,
+ times: []timeSpan{
+ timeSpan{201e6, 1 * time.Second},
+ timeSpan{201e6, 2 * time.Second},
+ timeSpan{201e6, 3 * time.Second},
+ },
+ shouldEstablish: true,
+ },
+ {
+ quorum: 2,
+ times: []timeSpan{
+ timeSpan{100e6, maxRadius},
+ timeSpan{200e6, maxRadius},
+ timeSpan{200e6, maxRadius},
+ },
+ shouldEstablish: true,
+ shouldSignalMisbehaviour: true,
+ },
+ {
+ quorum: 2,
+ times: []timeSpan{
+ timeSpan{0, nonsenseReply},
+ timeSpan{0, nonsenseReply},
+ timeSpan{200e6, maxRadius},
+ timeSpan{200e6, maxRadius},
+ },
+ shouldEstablish: true,
+ shouldHaveErrors: []int{0, 1},
+ },
+}
+
+func TestEstablishment(t *testing.T) {
+ client := &Client{
+ nowFunc: func() time.Duration {
+ // The monotonic clock always returns zero to avoid
+ // query latency affecting the results.
+ return 0
+ },
+
+ Permutation: func(n int) []int {
+ // The permutation is fixed so that "servers" will be
+ // queried in the order given.
+ ret := make([]int, n)
+ for i := range ret {
+ ret[i] = i
+ }
+
+ return ret
+ },
+
+ MaxRadius: maxRadius,
+ MaxDifference: 60 * time.Second,
+ QueryTimeout: 30 * time.Second,
+ NumQueries: 1,
+ }
+
+ var waitGroup sync.WaitGroup
+ defer waitGroup.Wait()
+
+ for i, test := range timeEstablishmentTests {
+ var handles []*serverHandle
+ var servers []config.Server
+
+ for j, span := range test.times {
+ handle, err := startServer(&waitGroup, span)
+ if err != nil {
+ t.Fatal(err)
+ }
+
+ handles = append(handles, handle)
+ servers = append(servers, config.Server{
+ Name: strconv.Itoa(j),
+ PublicKey: handle.publicKey,
+ Addresses: []config.ServerAddress{
+ config.ServerAddress{
+ Protocol: "udp",
+ Address: handle.addr.String(),
+ },
+ },
+ })
+ defer handle.Close()
+ }
+
+ var chain config.Chain
+ result, err := client.EstablishTime(&chain, test.quorum, servers)
+ if err != nil {
+ t.Fatal(err)
+ }
+
+ if test.shouldEstablish != (result.MonoUTCDelta != nil) {
+ t.Errorf("#%d: time establishment mismatch, wanted: %t", i, test.shouldEstablish)
+ }
+
+ if test.shouldEstablish && len(chain.Links) < test.quorum {
+ t.Errorf("#%d: chain too short (%d) to be valid", i, len(chain.Links))
+ }
+
+ // Serialize and reparse chain to ensure that it's valid.
+ chainBytes, err := json.MarshalIndent(chain, "", " ")
+ if err != nil {
+ t.Fatal(err)
+ }
+
+ if _, err := LoadChain(chainBytes); err != nil {
+ t.Errorf("#%d: resulting chain does not parse: %s", i, err)
+ }
+
+ if test.shouldSignalMisbehaviour != result.OutOfRangeAnswer {
+ t.Errorf("#%d: misbehaviour mismatch, wanted: %t", i, test.shouldSignalMisbehaviour)
+ }
+
+ if len(result.ServerErrors) != len(test.shouldHaveErrors) {
+ t.Errorf("#%d: server errors mismatch, got %#v but wanted errors from #%v", i, result.ServerErrors, test.shouldHaveErrors)
+ }
+
+ for _, serverNumber := range test.shouldHaveErrors {
+ if _, ok := result.ServerErrors[strconv.Itoa(serverNumber)]; !ok {
+ t.Errorf("#%d: missing error for server %d", i, serverNumber)
+ }
+ }
+ }
+}
+
+type serverHandle struct {
+ publicKey []byte
+ addr *net.UDPAddr
+}
+
+func (handle *serverHandle) Close() {
+ conn, err := net.DialUDP("udp", nil, handle.addr)
+ if err != nil {
+ panic(err)
+ }
+
+ conn.Write([]byte{0})
+}
+
+func startServer(wg *sync.WaitGroup, span timeSpan) (*serverHandle, error) {
+ rootPublic, rootPrivate, err := ed25519.GenerateKey(rand.Reader)
+ if err != nil {
+ return nil, err
+ }
+
+ onlinePublicKey, onlinePrivateKey, err := ed25519.GenerateKey(rand.Reader)
+ if err != nil {
+ return nil, err
+ }
+
+ cert, err := protocol.CreateCertificate(0, ^uint64(0), onlinePublicKey, rootPrivate)
+ if err != nil {
+ return nil, err
+ }
+
+ conn, err := net.ListenUDP("udp", &net.UDPAddr{IP: net.IPv4(127, 0, 0, 1), Port: 0})
+ if err != nil {
+ return nil, err
+ }
+
+ localAddr, ok := conn.LocalAddr().(*net.UDPAddr)
+ if !ok {
+ panic("not a UDP address")
+ }
+
+ wg.Add(1)
+
+ go func() {
+ var packetBuf [protocol.MinRequestSize]byte
+ defer wg.Done()
+
+ for {
+ n, sourceAddr, err := conn.ReadFromUDP(packetBuf[:])
+ if err != nil {
+ panic(err)
+ }
+
+ if n == 1 && packetBuf[0] == 0 {
+ return
+ }
+
+ if span.radius == nonsenseReply {
+ conn.WriteToUDP([]byte{1, 2, 3, 4, 5}, sourceAddr)
+ continue
+ }
+
+ packet, err := protocol.Decode(packetBuf[:n])
+ if err != nil {
+ println(n)
+ panic(err)
+ }
+
+ nonce, ok := packet[protocol.TagNonce]
+ if !ok || len(nonce) != protocol.NonceSize {
+ panic("missing nonce")
+ }
+
+ replies, err := protocol.CreateReplies([][]byte{nonce}, span.midpoint, uint32(span.radius/time.Microsecond), cert, onlinePrivateKey)
+ if err != nil {
+ panic(err)
+ }
+
+ conn.WriteToUDP(replies[0], sourceAddr)
+ }
+ }()
+
+ return &serverHandle{
+ publicKey: rootPublic,
+ addr: localAddr,
+ }, nil
+}
diff --git a/go/client/main.go b/go/client/main.go
new file mode 100644
index 0000000..b74e95b
--- /dev/null
+++ b/go/client/main.go
@@ -0,0 +1,127 @@
+// Copyright 2016 The Roughtime Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License. */
+
+package main
+
+import (
+ "encoding/json"
+ "flag"
+ "fmt"
+ "io/ioutil"
+ "os"
+ "path/filepath"
+ "time"
+
+ "roughtime.googlesource.com/go/client/monotime"
+ "roughtime.googlesource.com/go/config"
+)
+
+var (
+ chainFile = flag.String("chain-file", "roughtime-chain.json", "The name of a file in which the query chain will be maintained")
+ maxChainSize = flag.Int("max-chain-size", 128, "The maximum number of entries to maintain in the chain file")
+ serversFile = flag.String("servers-file", "roughtime-servers.json", "The name of a file that lists trusted Roughtime servers")
+)
+
+const (
+ // defaultServerQuorum is the default number of overlapping responses
+ // that are required to establish the current time.
+ defaultServerQuorum = 3
+)
+
+func do() error {
+ flag.Parse()
+
+ serversData, err := ioutil.ReadFile(*serversFile)
+ if err != nil {
+ return err
+ }
+
+ servers, numServersSkipped, err := LoadServers(serversData)
+ if err != nil {
+ return err
+ }
+ if numServersSkipped > 0 {
+ fmt.Fprintf(os.Stderr, "Ignoring %d unsupported servers\n", numServersSkipped)
+ }
+
+ chain := &config.Chain{}
+ chainData, err := ioutil.ReadFile(*chainFile)
+ if err == nil {
+ if chain, err = LoadChain(chainData); err != nil {
+ return err
+ }
+ } else if !os.IsNotExist(err) {
+ return err
+ }
+
+ quorum := defaultServerQuorum
+ if quorum > len(servers) {
+ fmt.Fprintf(os.Stderr, "Quorum set to %d servers because not enough valid servers were found to meet the default (%d)!\n", len(servers), quorum)
+ quorum = len(servers)
+ }
+
+ var client Client
+ result, err := client.EstablishTime(chain, quorum, servers)
+ if err != nil {
+ return err
+ }
+
+ for serverName, err := range result.ServerErrors {
+ fmt.Fprintf(os.Stderr, "Failed to query %q: %s\n", serverName, err)
+ }
+
+ if result.MonoUTCDelta == nil {
+ fmt.Fprintf(os.Stderr, "Failed to get %d servers to agree on the time.\n", quorum)
+ } else {
+ nowUTC := time.Unix(0, int64(monotime.Now()+*result.MonoUTCDelta))
+ nowRealTime := time.Now()
+
+ fmt.Printf("real-time delta: %s\n", nowRealTime.Sub(nowUTC))
+ }
+
+ // TODO: if result.OutOfRangeAnswer is set then cap the chain and
+ // upload it.
+ if result.OutOfRangeAnswer {
+ fmt.Fprintf(os.Stderr, "One or more of the answers was significantly out of range.\n")
+ }
+
+ trimChain(chain, *maxChainSize)
+ chainBytes, err := json.MarshalIndent(chain, "", " ")
+ if err != nil {
+ return err
+ }
+
+ tempFile, err := ioutil.TempFile(filepath.Dir(*chainFile), filepath.Base(*chainFile))
+ if err != nil {
+ return err
+ }
+ defer tempFile.Close()
+
+ if _, err := tempFile.Write(chainBytes); err != nil {
+ return err
+ }
+
+ if err := os.Rename(tempFile.Name(), *chainFile); err != nil {
+ return err
+ }
+
+ return nil
+}
+
+func main() {
+ if err := do(); err != nil {
+ fmt.Fprintf(os.Stderr, "%s\n", err)
+ os.Exit(1)
+ }
+}
diff --git a/go/client/monotime/empty.s b/go/client/monotime/empty.s
new file mode 100644
index 0000000..ebf6c96
--- /dev/null
+++ b/go/client/monotime/empty.s
@@ -0,0 +1 @@
+// This is an empty assembly file to allow go:linkname to be used.
diff --git a/go/client/monotime/monotime.go b/go/client/monotime/monotime.go
new file mode 100644
index 0000000..0c2ddec
--- /dev/null
+++ b/go/client/monotime/monotime.go
@@ -0,0 +1,32 @@
+// Copyright 2016 The Roughtime Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License. */
+
+// Package monotime provides access to the system's monotonic clock.
+package monotime
+
+import (
+ "unsafe"
+ "time"
+)
+
+var _ = unsafe.Sizeof(0)
+
+//go:noescape
+//go:linkname nanotime runtime.nanotime
+func nanotime() int64
+
+// Now returns the monotonic duration since an unspecified epoch.
+func Now() time.Duration {
+ return time.Duration(nanotime()) * time.Nanosecond
+}
diff --git a/go/config/config.go b/go/config/config.go
new file mode 100644
index 0000000..a5c8fe2
--- /dev/null
+++ b/go/config/config.go
@@ -0,0 +1,65 @@
+// Copyright 2016 The Roughtime Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License. */
+
+// Package config contains JSON structs for encoding information about
+// Roughtime servers.
+package config
+
+// ServersJSON represents a JSON format for distributing information about
+// Roughtime servers.
+type ServersJSON struct {
+ Servers []Server `json:"servers"`
+}
+
+// Server represents a Roughtime server in a JSON configuration.
+type Server struct {
+ Name string `json:"name"`
+ // PublicKeyType specifies the type of the public key contained in
+ // |PublicKey|. Normally this will be "ed25519" but implementations
+ // should ignore entries with unknown key types.
+ PublicKeyType string `json:"publicKeyType"`
+ PublicKey []byte `json:"publicKey"`
+ Addresses []ServerAddress `json:"addresses"`
+}
+
+// ServerAddress represents the address of a Roughtime server in a JSON
+// configuration.
+type ServerAddress struct {
+ Protocol string `json:"protocol"`
+ // Address contains a protocol specific address. For the protocol
+ // "udp", the address has the form "host:port" where host is either a
+ // DNS name, an IPv4 literal, or an IPv6 literal in square brackets.
+ Address string `json:"address"`
+}
+
+// Chain represents a history of Roughtime queries where each provably follows
+// the previous one.
+type Chain struct {
+ Links []Link `json:"links"`
+}
+
+// Link represents an entry in a Chain.
+type Link struct {
+ // PublicKeyType specifies the type of public key contained in
+ // |PublicKey|. See the same field in |Server| for details.
+ PublicKeyType string `json:"publicKeyType"`
+ PublicKey []byte `json:"serverPublicKey"`
+ // NonceOrBlind contains either the full nonce (only for the first
+ // |Link| in a |Chain|) or else contains a blind value that is combined
+ // with the previous reply to make the next nonce. In either case, the
+ // value is 64 bytes long.
+ NonceOrBlind []byte `json:"nonceOrBlind"`
+ // Reply contains the reply from the server.
+ Reply []byte `json:"reply"`
+}
diff --git a/go/protocol/protocol.go b/go/protocol/protocol.go
new file mode 100644
index 0000000..ba33dde
--- /dev/null
+++ b/go/protocol/protocol.go
@@ -0,0 +1,613 @@
+// Copyright 2016 The Roughtime Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License. */
+
+// Package protocol implements the core of the Roughtime protocol.
+package protocol
+
+import (
+ "bytes"
+ "crypto/sha512"
+ "encoding/binary"
+ "errors"
+ "io"
+ "sort"
+
+ "golang.org/x/crypto/ed25519"
+)
+
+const (
+ // NonceSize is the number of bytes in a nonce.
+ NonceSize = sha512.Size
+ // MinRequestSize is the minimum number of bytes in a request.
+ MinRequestSize = 1024
+
+ certificateContext = "RoughTime v1 delegation signature--\x00"
+ signedResponseContext = "RoughTime v1 response signature\x00"
+)
+
+// makeTag converts a four character string into a Roughtime tag value.
+func makeTag(tag string) uint32 {
+ if len(tag) != 4 {
+ panic("makeTag: len(tag) != 4: " + tag)
+ }
+
+ return uint32(tag[0]) | uint32(tag[1])<<8 | uint32(tag[2])<<16 | uint32(tag[3])<<24
+}
+
+var (
+ // Various tags used in the Roughtime protocol.
+ tagCERT = makeTag("CERT")
+ tagDELE = makeTag("DELE")
+ tagINDX = makeTag("INDX")
+ tagMAXT = makeTag("MAXT")
+ tagMIDP = makeTag("MIDP")
+ tagMINT = makeTag("MINT")
+ tagNONC = makeTag("NONC")
+ tagPAD = makeTag("PAD\xff")
+ tagPATH = makeTag("PATH")
+ tagPUBK = makeTag("PUBK")
+ tagRADI = makeTag("RADI")
+ tagROOT = makeTag("ROOT")
+ tagSIG = makeTag("SIG\x00")
+ tagSREP = makeTag("SREP")
+
+ // TagNonce names the bytestring containing the client's nonce.
+ TagNonce = tagNONC
+)
+
+// tagsSlice is the type of an array of tags. It provides utility functions so
+// that they can be sorted.
+type tagsSlice []uint32
+
+func (t tagsSlice) Len() int { return len(t) }
+func (t tagsSlice) Less(i, j int) bool { return t[i] < t[j] }
+func (t tagsSlice) Swap(i, j int) { t[i], t[j] = t[j], t[i] }
+
+// Encode converts a map of tags to bytestrings into an encoded message. The
+// number of elements in msg and the sum of the lengths of all the bytestrings
+// must be ≤ 2**32.
+func Encode(msg map[uint32][]byte) ([]byte, error) {
+ if len(msg) == 0 {
+ return make([]byte, 4), nil
+ }
+
+ if len(msg) >= 1<<32 {
+ return nil, errors.New("encode: too many tags")
+ }
+
+ var payloadSum uint64
+ for _, payload := range msg {
+ if len(payload) % 4 != 0 {
+ return nil, errors.New("encode: length of value is not a multiple of four")
+ }
+ payloadSum += uint64(len(payload))
+ }
+ if payloadSum >= 1<<32 {
+ return nil, errors.New("encode: payloads too large")
+ }
+
+ tags := tagsSlice(make([]uint32, 0, len(msg)))
+ for tag := range msg {
+ tags = append(tags, tag)
+ }
+ sort.Sort(tags)
+
+ numTags := uint64(len(tags))
+
+ encoded := make([]byte, 4*(1+numTags-1+numTags)+payloadSum)
+ binary.LittleEndian.PutUint32(encoded, uint32(len(tags)))
+ offsets := encoded[4:]
+ tagBytes := encoded[4*(1+(numTags-1)):]
+ payloads := encoded[4*(1+(numTags-1)+numTags):]
+
+ currentOffset := uint32(0)
+
+ for i, tag := range tags {
+ payload := msg[tag]
+ if i > 0 {
+ binary.LittleEndian.PutUint32(offsets, currentOffset)
+ offsets = offsets[4:]
+ }
+
+ binary.LittleEndian.PutUint32(tagBytes, tag)
+ tagBytes = tagBytes[4:]
+
+ if len(payload) > 0 {
+ copy(payloads, payload)
+ payloads = payloads[len(payload):]
+ currentOffset += uint32(len(payload))
+ }
+ }
+
+ return encoded, nil
+}
+
+// Decode parses the output of encode back into a map of tags to bytestrings.
+func Decode(bytes []byte) (map[uint32][]byte, error) {
+ if len(bytes) < 4 {
+ return nil, errors.New("decode: message too short to be valid")
+ }
+ if len(bytes) % 4 != 0 {
+ return nil, errors.New("decode: message is not a multiple of four bytes")
+ }
+
+ numTags := uint64(binary.LittleEndian.Uint32(bytes))
+
+ if numTags == 0 {
+ return make(map[uint32][]byte), nil
+ }
+
+ if uint64(len(bytes)) < 4*((numTags-1)+numTags) {
+ return nil, errors.New("decode: message too short to be valid")
+ }
+
+ offsets := bytes[4:]
+ tags := bytes[4*(1+numTags-1):]
+ payloads := bytes[4*(1+(numTags-1)+numTags):]
+
+ if len(payloads) > 1<<32 {
+ return nil, errors.New("decode: message too large")
+ }
+ payloadLength := uint32(len(payloads))
+
+ currentOffset := uint32(0)
+ var lastTag uint32
+ ret := make(map[uint32][]byte)
+
+ for i := uint64(0); i < numTags; i++ {
+ tag := binary.LittleEndian.Uint32(tags)
+ tags = tags[4:]
+
+ if i > 0 && lastTag >= tag {
+ return nil, errors.New("decode: tags out of order")
+ }
+
+ var nextOffset uint32
+ if i < numTags-1 {
+ nextOffset = binary.LittleEndian.Uint32(offsets)
+ offsets = offsets[4:]
+ } else {
+ nextOffset = payloadLength
+ }
+
+ if nextOffset%4 != 0 {
+ return nil, errors.New("decode: payload length is not a multiple of four bytes")
+ }
+
+ if nextOffset < currentOffset {
+ return nil, errors.New("decode: offsets out of order")
+ }
+
+ length := nextOffset - currentOffset
+ if uint32(len(payloads)) < length {
+ return nil, errors.New("decode: message truncated")
+ }
+
+ payload := payloads[:length]
+ payloads = payloads[length:]
+ ret[tag] = payload
+ currentOffset = nextOffset
+ }
+
+ return ret, nil
+}
+
+// messageOverhead returns the number of bytes needed for Encode to encode the
+// given number of tags.
+func messageOverhead(numTags int) int {
+ return 4 * 2 * numTags
+}
+
+// CalculateChainNonce calculates the nonce to be used in the next request in a
+// chain given a reply and a blinding factor.
+func CalculateChainNonce(prevReply, blind []byte) (nonce [NonceSize]byte) {
+ h := sha512.New()
+ h.Write(prevReply)
+ prevReplyHash := h.Sum(nil)
+
+ h.Reset()
+ h.Write(prevReplyHash)
+ h.Write(blind)
+ h.Sum(nonce[:0])
+
+ return nonce
+}
+
+// CreateRequest creates a Roughtime request given an entropy source and the
+// contents of a previous reply for chaining. If this request is the first of a
+// chain, prevReply can be empty. It returns the nonce (needed to verify the
+// reply), the blind (needed to prove correct chaining to an external party)
+// and the request itself.
+func CreateRequest(rand io.Reader, prevReply []byte) (nonce, blind [NonceSize]byte, request []byte, err error) {
+ if _, err := io.ReadFull(rand, blind[:]); err != nil {
+ return nonce, blind, nil, err
+ }
+
+ nonce = CalculateChainNonce(prevReply, blind[:])
+
+ padding := make([]byte, MinRequestSize-messageOverhead(2)-len(nonce))
+ msg, err := Encode(map[uint32][]byte{
+ tagNONC: nonce[:],
+ tagPAD: padding,
+ })
+ if err != nil {
+ return nonce, blind, nil, err
+ }
+
+ return nonce, blind, msg, nil
+}
+
+// tree represents a Merkle tree of nonces. Each element of values is a layer
+// in the tree, with the widest layer first.
+type tree struct {
+ values [][][NonceSize]byte
+}
+
+var (
+ hashLeafTweak = []byte{0}
+ hashNodeTweak = []byte{1}
+)
+
+// hashLeaf hashes an nonce to form the leaf of the Merkle tree.
+func hashLeaf(out *[sha512.Size]byte, in []byte) {
+ h := sha512.New()
+ h.Write(hashLeafTweak)
+ h.Write(in)
+ h.Sum(out[:0])
+}
+
+// hashNode hashes two child elements of the Merkle tree to produce an interior
+// node.
+func hashNode(out *[sha512.Size]byte, left, right []byte) {
+ h := sha512.New()
+ h.Write(hashNodeTweak)
+ h.Write(left)
+ h.Write(right)
+ h.Sum(out[:0])
+}
+
+// newTree creates a Merkle tree given one or more nonces.
+func newTree(nonces [][]byte) *tree {
+ if len(nonces) == 0 {
+ panic("newTree: passed empty slice")
+ }
+
+ levels := 1
+ width := len(nonces)
+ for width > 1 {
+ width = (width + 1) / 2
+ levels++
+ }
+
+ ret := &tree{
+ values: make([][][NonceSize]byte, 0, levels),
+ }
+
+ leaves := make([][NonceSize]byte, ((len(nonces)+1)/2)*2)
+ for i, nonce := range nonces {
+ var leaf [NonceSize]byte
+ hashLeaf(&leaf, nonce)
+ leaves[i] = leaf
+ }
+ ret.values = append(ret.values, leaves)
+
+ for i := 1; i < levels; i++ {
+ lastLevel := ret.values[i-1]
+ width := len(lastLevel) / 2
+ if width%2 == 1 {
+ width++
+ }
+ level := make([][NonceSize]byte, width)
+ for j := 0; j < len(lastLevel)/2; j++ {
+ hashNode(&level[j], lastLevel[j*2][:], lastLevel[j*2+1][:])
+ }
+ ret.values = append(ret.values, level)
+ }
+
+ return ret
+}
+
+// Root returns the root value of t.
+func (t *tree) Root() *[NonceSize]byte {
+ return &t.values[len(t.values)-1][0]
+}
+
+// Levels returns the number of levels in t.
+func (t *tree) Levels() int {
+ return len(t.values)
+}
+
+// Path returns elements from t needed to prove, given the root, that the leaf
+// at the given index is in the tree.
+func (t *tree) Path(index int) (path [][]byte) {
+ path = make([][]byte, 0, len(t.values))
+
+ for level := 0; level < len(t.values)-1; level++ {
+ if index%2 == 1 {
+ path = append(path, t.values[level][index-1][:])
+ } else {
+ path = append(path, t.values[level][index+1][:])
+ }
+
+ index /= 2
+ }
+
+ return path
+}
+
+// CreateReplies signs, using privateKey, a batch of nonces along with the
+// given time and radius in microseconds. It returns one reply for each nonce
+// using that signature and includes cert in each.
+func CreateReplies(nonces [][]byte, midpoint uint64, radius uint32, cert []byte, privateKey []byte) ([][]byte, error) {
+ if len(nonces) == 0 {
+ return nil, nil
+ }
+
+ tree := newTree(nonces)
+
+ var midpointBytes [8]byte
+ binary.LittleEndian.PutUint64(midpointBytes[:], midpoint)
+ var radiusBytes [4]byte
+ binary.LittleEndian.PutUint32(radiusBytes[:], radius)
+
+ signedReply := map[uint32][]byte{
+ tagMIDP: midpointBytes[:],
+ tagRADI: radiusBytes[:],
+ tagROOT: tree.Root()[:],
+ }
+ signedReplyBytes, err := Encode(signedReply)
+ if err != nil {
+ return nil, err
+ }
+
+ toBeSigned := signedResponseContext + string(signedReplyBytes)
+ sig := ed25519.Sign(privateKey, []byte(toBeSigned))
+
+ reply := map[uint32][]byte{
+ tagSREP: signedReplyBytes,
+ tagSIG: sig,
+ tagCERT: cert,
+ }
+
+ replies := make([][]byte, 0, len(nonces))
+
+ for i := range nonces {
+ var indexBytes [4]byte
+ binary.LittleEndian.PutUint32(indexBytes[:], uint32(i))
+ reply[tagINDX] = indexBytes[:]
+
+ path := tree.Path(i)
+ pathBytes := make([]byte, 0, NonceSize*len(path))
+ for _, pathStep := range path {
+ pathBytes = append(pathBytes, pathStep...)
+ }
+ reply[tagPATH] = pathBytes
+
+ replyBytes, err := Encode(reply)
+ if err != nil {
+ return nil, err
+ }
+
+ replies = append(replies, replyBytes)
+ }
+
+ return replies, nil
+}
+
+// CreateCertificate returns a signed certificate, using rootPrivateKey,
+// delegating authority for the given timestamp to publicKey.
+func CreateCertificate(minTime, maxTime uint64, publicKey, rootPrivateKey []byte) (certBytes []byte, err error) {
+ if maxTime < minTime {
+ return nil, errors.New("protocol: maxTime < minTime")
+ }
+
+ var minTimeBytes, maxTimeBytes [8]byte
+ binary.LittleEndian.PutUint64(minTimeBytes[:], minTime)
+ binary.LittleEndian.PutUint64(maxTimeBytes[:], maxTime)
+
+ signed := map[uint32][]byte{
+ tagPUBK: publicKey,
+ tagMINT: minTimeBytes[:],
+ tagMAXT: maxTimeBytes[:],
+ }
+
+ signedBytes, err := Encode(signed)
+ if err != nil {
+ return nil, err
+ }
+
+ toBeSigned := certificateContext + string(signedBytes)
+ sig := ed25519.Sign(rootPrivateKey, []byte(toBeSigned))
+
+ cert := map[uint32][]byte{
+ tagSIG: sig,
+ tagDELE: signedBytes,
+ }
+
+ return Encode(cert)
+}
+
+func getValue(msg map[uint32][]byte, tag uint32, name string) (value []byte, err error) {
+ value, ok := msg[tag]
+ if !ok {
+ return nil, errors.New("protocol: missing " + name)
+ }
+ return value, nil
+}
+
+func getFixedLength(msg map[uint32][]byte, tag uint32, name string, length int) (value []byte, err error) {
+ value, err = getValue(msg, tag, name)
+ if err != nil {
+ return nil, err
+ }
+ if len(value) != length {
+ return nil, errors.New("protocol: incorrect length for " + name)
+ }
+ return value, nil
+}
+
+func getUint32(msg map[uint32][]byte, tag uint32, name string) (result uint32, err error) {
+ valueBytes, err := getFixedLength(msg, tag, name, 4)
+ if err != nil {
+ return 0, err
+ }
+ return binary.LittleEndian.Uint32(valueBytes), nil
+}
+
+func getUint64(msg map[uint32][]byte, tag uint32, name string) (result uint64, err error) {
+ valueBytes, err := getFixedLength(msg, tag, name, 8)
+ if err != nil {
+ return 0, err
+ }
+ return binary.LittleEndian.Uint64(valueBytes), nil
+}
+
+func getSubmessage(msg map[uint32][]byte, tag uint32, name string) (result map[uint32][]byte, err error) {
+ valueBytes, err := getValue(msg, tag, name)
+ if err != nil {
+ return nil, err
+ }
+
+ result, err = Decode(valueBytes)
+ if err != nil {
+ return nil, errors.New("protocol: failed to parse " + name + ": " + err.Error())
+ }
+
+ return result, nil
+}
+
+// VerifyReply parses the Roughtime reply in replyBytes, authenticates it using
+// publicKey and verifies that nonce is included in it. It returns the included
+// timestamp and radius.
+func VerifyReply(replyBytes, publicKey []byte, nonce [NonceSize]byte) (time uint64, radius uint32, err error) {
+ reply, err := Decode(replyBytes)
+ if err != nil {
+ return 0, 0, errors.New("protocol: failed to parse top-level reply: " + err.Error())
+ }
+
+ cert, err := getSubmessage(reply, tagCERT, "certificate")
+ if err != nil {
+ return 0, 0, err
+ }
+
+ signatureBytes, err := getFixedLength(cert, tagSIG, "signature", ed25519.SignatureSize)
+ if err != nil {
+ return 0, 0, err
+ }
+
+ delegationBytes, err := getValue(cert, tagDELE, "delegation")
+ if err != nil {
+ return 0, 0, err
+ }
+
+ if !ed25519.Verify(publicKey, []byte(certificateContext+string(delegationBytes)), signatureBytes) {
+ return 0, 0, errors.New("protocol: invalid delegation signature")
+ }
+
+ delegation, err := Decode(delegationBytes)
+ if err != nil {
+ return 0, 0, errors.New("protocol: failed to parse delegation: " + err.Error())
+ }
+
+ minTime, err := getUint64(delegation, tagMINT, "minimum time")
+ if err != nil {
+ return 0, 0, err
+ }
+
+ maxTime, err := getUint64(delegation, tagMAXT, "maximum time")
+ if err != nil {
+ return 0, 0, err
+ }
+
+ delegatedPublicKey, err := getFixedLength(delegation, tagPUBK, "public key", ed25519.PublicKeySize)
+ if err != nil {
+ return 0, 0, err
+ }
+
+ responseSigBytes, err := getFixedLength(reply, tagSIG, "signature", ed25519.SignatureSize)
+ if err != nil {
+ return 0, 0, err
+ }
+
+ signedResponseBytes, ok := reply[tagSREP]
+ if !ok {
+ return 0, 0, errors.New("protocol: response is missing signed portion")
+ }
+
+ if !ed25519.Verify(delegatedPublicKey, []byte(signedResponseContext+string(signedResponseBytes)), responseSigBytes) {
+ return 0, 0, errors.New("protocol: invalid response signature")
+ }
+
+ signedResponse, err := Decode(signedResponseBytes)
+ if err != nil {
+ return 0, 0, errors.New("protocol: failed to parse signed response: " + err.Error())
+ }
+
+ root, err := getFixedLength(signedResponse, tagROOT, "root", sha512.Size)
+ if err != nil {
+ return 0, 0, err
+ }
+
+ midpoint, err := getUint64(signedResponse, tagMIDP, "midpoint")
+ if err != nil {
+ return 0, 0, err
+ }
+
+ radius, err = getUint32(signedResponse, tagRADI, "radius")
+ if err != nil {
+ return 0, 0, err
+ }
+
+ if maxTime < minTime {
+ return 0, 0, errors.New("protocol: invalid delegation range")
+ }
+
+ if midpoint < minTime || maxTime < midpoint {
+ return 0, 0, errors.New("protocol: timestamp out of range for delegation")
+ }
+
+ index, err := getUint32(reply, tagINDX, "index")
+ if err != nil {
+ return 0, 0, err
+ }
+
+ path, err := getValue(reply, tagPATH, "path")
+ if err != nil {
+ return 0, 0, err
+ }
+ if len(path)%sha512.Size != 0 {
+ return 0, 0, errors.New("protocol: path is not a multiple of the hash size")
+ }
+
+ var hash [sha512.Size]byte
+ hashLeaf(&hash, nonce[:])
+
+ for len(path) > 0 {
+ pathElementIsRight := index&1 == 0
+ if pathElementIsRight {
+ hashNode(&hash, hash[:], path[:sha512.Size])
+ } else {
+ hashNode(&hash, path[:sha512.Size], hash[:])
+ }
+
+ index >>= 1
+ path = path[sha512.Size:]
+ }
+
+ if !bytes.Equal(hash[:], root) {
+ return 0, 0, errors.New("protocol: calculated tree root doesn't match signed root")
+ }
+
+ return midpoint, radius, nil
+}
diff --git a/go/protocol/protocol_test.go b/go/protocol/protocol_test.go
new file mode 100644
index 0000000..c6a9c50
--- /dev/null
+++ b/go/protocol/protocol_test.go
@@ -0,0 +1,200 @@
+// Copyright 2016 The Roughtime Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License. */
+
+package protocol
+
+import (
+ "bytes"
+ "crypto/rand"
+ "encoding/binary"
+ "testing"
+ "testing/quick"
+
+ "golang.org/x/crypto/ed25519"
+)
+
+func testEncodeDecodeRoundtrip(msg map[uint32][]byte) bool {
+ encoded, err := Encode(msg)
+ if err != nil {
+ return true
+ }
+
+ decoded, err := Decode(encoded)
+ if err != nil {
+ return false
+ }
+
+ if len(msg) != len(decoded) {
+ return false
+ }
+
+ for tag, payload := range msg {
+ otherPayload, ok := decoded[tag]
+ if !ok {
+ return false
+ }
+ if !bytes.Equal(payload, otherPayload) {
+ return false
+ }
+ }
+
+ return true
+}
+
+func TestEncodeDecode(t *testing.T) {
+ quick.Check(testEncodeDecodeRoundtrip, &quick.Config{
+ MaxCountScale: 10,
+ })
+}
+
+func TestRequestSize(t *testing.T) {
+ _, _, request, err := CreateRequest(rand.Reader, nil)
+ if err != nil {
+ t.Fatal(err)
+ }
+ if len(request) != MinRequestSize {
+ t.Errorf("got %d byte request, want %d bytes", len(request), MinRequestSize)
+ }
+}
+
+func createServerIdentity(t *testing.T) (cert, rootPublicKey, onlinePrivateKey []byte) {
+ rootPublicKey, rootPrivateKey, err := ed25519.GenerateKey(rand.Reader)
+ if err != nil {
+ t.Fatal(err)
+ }
+
+ onlinePublicKey, onlinePrivateKey, err := ed25519.GenerateKey(rand.Reader)
+ if err != nil {
+ t.Fatal(err)
+ }
+
+ if cert, err = CreateCertificate(0, 100, onlinePublicKey, rootPrivateKey); err != nil {
+ t.Fatal(err)
+ }
+
+ return cert, rootPublicKey, onlinePrivateKey
+}
+
+func TestRoundtrip(t *testing.T) {
+ cert, rootPublicKey, onlinePrivateKey := createServerIdentity(t)
+
+ for _, numRequests := range []int{1, 2, 3, 4, 5, 15, 16, 17} {
+ nonces := make([][NonceSize]byte, numRequests)
+ for i := range nonces {
+ binary.LittleEndian.PutUint32(nonces[i][:], uint32(i))
+ }
+
+ noncesSlice := make([][]byte, 0, numRequests)
+ for i := range nonces {
+ noncesSlice = append(noncesSlice, nonces[i][:])
+ }
+
+ const (
+ expectedMidpoint = 50
+ expectedRadius = 5
+ )
+
+ replies, err := CreateReplies(noncesSlice, expectedMidpoint, expectedRadius, cert, onlinePrivateKey)
+ if err != nil {
+ t.Fatal(err)
+ }
+
+ for i, reply := range replies {
+ midpoint, radius, err := VerifyReply(reply, rootPublicKey, nonces[i])
+ if err != nil {
+ t.Errorf("error parsing reply #%d: %s", i, err)
+ continue
+ }
+
+ if midpoint != expectedMidpoint {
+ t.Errorf("reply #%d gave a midpoint of %d, want %d", i, midpoint, expectedMidpoint)
+ }
+ if radius != expectedRadius {
+ t.Errorf("reply #%d gave a radius of %d, want %d", i, radius, expectedRadius)
+ }
+ }
+ }
+}
+
+func TestChaining(t *testing.T) {
+ // This test demonstrates how a claim of misbehaviour from a client
+ // would be checked. The client creates a two element chain in this
+ // example where the first server says that the time is 10 and the
+ // second says that it's 5.
+ certA, rootPublicKeyA, onlinePrivateKeyA := createServerIdentity(t)
+ certB, rootPublicKeyB, onlinePrivateKeyB := createServerIdentity(t)
+
+ nonce1, _, _, err := CreateRequest(rand.Reader, nil)
+ if err != nil {
+ t.Fatal(err)
+ }
+
+ replies1, err := CreateReplies([][]byte{nonce1[:]}, 10, 0, certA, onlinePrivateKeyA)
+ if err != nil {
+ t.Fatal(err)
+ }
+
+ nonce2, blind2, _, err := CreateRequest(rand.Reader, replies1[0])
+ if err != nil {
+ t.Fatal(err)
+ }
+
+ replies2, err := CreateReplies([][]byte{nonce2[:]}, 5, 0, certB, onlinePrivateKeyB)
+ if err != nil {
+ t.Fatal(err)
+ }
+
+ // The client would present a series of tuples of (server identity,
+ // nonce/blind, reply) as its claim of misbehaviour. The first element
+ // contains a nonce where as all other elements contain just the
+ // blinding value, as the nonce used for that request is calculated
+ // from that and the previous reply.
+ type claimStep struct {
+ serverPublicKey []byte
+ nonceOrBlind [NonceSize]byte
+ reply []byte
+ }
+
+ claim := []claimStep{
+ claimStep{rootPublicKeyA, nonce1, replies1[0]},
+ claimStep{rootPublicKeyB, blind2, replies2[0]},
+ }
+
+ // In order to verify a claim, one would check each of the replies
+ // based on the calculated nonce.
+ var lastMidpoint uint64
+ var misbehaviourFound bool
+ for i, step := range claim {
+ var nonce [NonceSize]byte
+ if i == 0 {
+ copy(nonce[:], step.nonceOrBlind[:])
+ } else {
+ nonce = CalculateChainNonce(claim[i-1].reply, step.nonceOrBlind[:])
+ }
+ midpoint, _, err := VerifyReply(step.reply, step.serverPublicKey, nonce)
+ if err != nil {
+ t.Fatal(err)
+ }
+
+ // This example doesn't take the radius into account.
+ if i > 0 && midpoint < lastMidpoint {
+ misbehaviourFound = true
+ }
+ lastMidpoint = midpoint
+ }
+
+ if !misbehaviourFound {
+ t.Error("did not find expected misbehaviour")
+ }
+}
diff --git a/go/server/server.go b/go/server/server.go
new file mode 100644
index 0000000..8998397
--- /dev/null
+++ b/go/server/server.go
@@ -0,0 +1,167 @@
+// Copyright 2016 The Roughtime Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License. */
+
+// server is a very basic Roughtime server.
+//
+// First, run with the flag -generate-key. This will print out a private key
+// and a JSON template for the server. Put the private key (as hex) in a file
+// named "priv" and then run with no arguments.
+package main
+
+// TODO(agl): add a test once the client functionality has landed.
+
+import (
+ "bytes"
+ "crypto/rand"
+ "encoding/hex"
+ "encoding/json"
+ "errors"
+ "flag"
+ "fmt"
+ "io/ioutil"
+ "log"
+ "net"
+ "os"
+ "time"
+
+ "golang.org/x/crypto/ed25519"
+ "roughtime.googlesource.com/go/config"
+ "roughtime.googlesource.com/go/protocol"
+)
+
+var (
+ genKey = flag.Bool("generate-key", false, "Generate a new key pair")
+ privateKeyFile = flag.String("private-key", "priv", "Filename of the private key (hex encoded)")
+ port = flag.Int("port", 5333, "Port number to listen on")
+)
+
+func main() {
+ flag.Parse()
+
+ var err error
+ if *genKey {
+ err = generateKeyPair()
+ } else {
+ err = serveForever()
+ }
+
+ if err != nil {
+ fmt.Fprintf(os.Stderr, "%s\n", err)
+ os.Exit(1)
+ }
+}
+
+func serveForever() error {
+ privateKeyHex, err := ioutil.ReadFile(*privateKeyFile)
+ if err != nil {
+ return errors.New("Cannot open private key: " + err.Error())
+ }
+
+ privateKey, err := hex.DecodeString(string(bytes.TrimSpace(privateKeyHex)))
+ if err != nil {
+ return errors.New("Cannot parse private key: " + err.Error())
+ }
+
+ conn, err := net.ListenUDP("udp", &net.UDPAddr{IP: net.IPv4(0, 0, 0, 0), Port: *port})
+ if err != nil {
+ return errors.New("Cannot listen on port: " + err.Error())
+ }
+
+ onlinePublicKey, onlinePrivateKey, err := ed25519.GenerateKey(rand.Reader)
+ if err != nil {
+ return errors.New("Cannot generate private key: " + err.Error())
+ }
+
+ // As this is just an example, the certificate is created covering the
+ // maximum possible range.
+ cert, err := protocol.CreateCertificate(0, ^uint64(0), onlinePublicKey, privateKey)
+ if err != nil {
+ return errors.New("Cannot generate certificate: " + err.Error())
+ }
+
+ log.Printf("Processing requests on port %d", *port)
+
+ var packetBuf [protocol.MinRequestSize]byte
+
+ for {
+ n, sourceAddr, err := conn.ReadFromUDP(packetBuf[:])
+ if err != nil {
+ log.Print(err)
+ }
+
+ if n < protocol.MinRequestSize {
+ continue
+ }
+
+ packet, err := protocol.Decode(packetBuf[:n])
+ if err != nil {
+ continue
+ }
+
+ nonce, ok := packet[protocol.TagNonce]
+ if !ok || len(nonce) != protocol.NonceSize {
+ continue
+ }
+
+ midpoint := uint64(time.Now().UnixNano() / 1000)
+ radius := uint32(1000000)
+
+ replies, err := protocol.CreateReplies([][]byte{nonce}, midpoint, radius, cert, onlinePrivateKey)
+ if err != nil {
+ log.Print(err)
+ continue
+ }
+
+ if len(replies) != 1 {
+ continue
+ }
+
+ conn.WriteToUDP(replies[0], sourceAddr)
+ }
+}
+
+func generateKeyPair() error {
+ rootPublic, rootPrivate, err := ed25519.GenerateKey(rand.Reader)
+ if err != nil {
+ return err
+ }
+
+ fmt.Printf("Private key: %x\n\n", rootPrivate)
+
+ exampleConfig := config.ServersJSON{
+ Servers: []config.Server{
+ config.Server{
+ Name: "FIXME",
+ PublicKeyType: "ed25519",
+ PublicKey: rootPublic,
+ Addresses: []config.ServerAddress{
+ config.ServerAddress{
+ Protocol: "udp",
+ Address: "FIXME",
+ },
+ },
+ },
+ },
+ }
+
+ jsonBytes, err := json.MarshalIndent(exampleConfig, "", " ")
+ if err != nil {
+ return err
+ }
+
+ os.Stdout.Write(jsonBytes)
+ os.Stdout.WriteString("\n")
+
+ return nil
+}
diff --git a/gtest.BUILD b/gtest.BUILD
new file mode 100644
index 0000000..3e68a1d
--- /dev/null
+++ b/gtest.BUILD
@@ -0,0 +1,14 @@
+cc_library(
+ name = "main",
+ srcs = glob(
+ ["src/*.cc"],
+ exclude = ["src/gtest-all.cc"]
+ ),
+ hdrs = glob([
+ "include/**/*.h",
+ "src/*.h"
+ ]),
+ copts = ["-Iexternal/gtest/include"],
+ linkopts = ["-pthread"],
+ visibility = ["//visibility:public"],
+)
diff --git a/open_source_fillins.h b/open_source_fillins.h
new file mode 100644
index 0000000..5ca49c3
--- /dev/null
+++ b/open_source_fillins.h
@@ -0,0 +1,39 @@
+/* Copyright 2016 The Roughtime Authors.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License. */
+
+#ifndef SECURITY_ROUGHTIME_OPEN_SOURCE_FILLINS_H_
+#define SECURITY_ROUGHTIME_OPEN_SOURCE_FILLINS_H_
+
+#if defined(ROUGHTIME_OPEN_SOURCE)
+
+#include <errno.h>
+#include <memory>
+
+#include <google/protobuf/stubs/logging.h>
+#include <google/protobuf/stubs/macros.h>
+
+#define GOOGLE_PLOG(level) GOOGLE_LOG(level) << strerror(errno) << ": "
+#define GOOGLE_LOG_IF_EVERY_N_SEC(level, condition, time) \
+ GOOGLE_LOG_IF(level, condition)
+
+#if !defined(arraysize)
+template <typename T, size_t N>
+char (&ArraySizeHelper(T (&array)[N]))[N];
+
+#define arraysize(array) (sizeof(ArraySizeHelper(array)))
+#endif
+
+#endif // ROUGHTIME_OPEN_SOURCE
+
+#endif // SECURITY_ROUGHTIME_OPEN_SOURCE_FILLINS_H_
diff --git a/protocol.cc b/protocol.cc
new file mode 100644
index 0000000..44afcad
--- /dev/null
+++ b/protocol.cc
@@ -0,0 +1,247 @@
+/* Copyright 2016 The Roughtime Authors.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License. */
+
+#include "protocol.h"
+
+#if defined(__APPLE__)
+#include <machine/endian.h>
+#else
+#include <endian.h>
+#endif
+
+#include <stdlib.h>
+#include <string.h>
+
+#include <google/protobuf/stubs/logging.h>
+#include <openssl/sha.h>
+
+namespace roughtime {
+
+static_assert(BYTE_ORDER == LITTLE_ENDIAN,
+ "This code assumes little-endian processors");
+
+static void advance(const uint8_t **ptr, size_t *len, size_t bytes) {
+ *ptr += bytes;
+ *len -= bytes;
+}
+
+Parser::Parser(const uint8_t *req, size_t len) {
+ if (len < sizeof(uint32_t)) {
+ return;
+ }
+
+ // Read number of tags.
+ uint32_t num_tags_32;
+ memcpy(&num_tags_32, req, sizeof(uint32_t));
+ num_tags_ = num_tags_32;
+ advance(&req, &len, sizeof(uint32_t));
+
+ if (0xffff < num_tags_) { // Avoids any subsequent overflows.
+ return;
+ }
+
+ // Validate table of offsets.
+ const size_t num_offsets = NumMessageOffsets(num_tags_);
+ if (len < num_offsets * sizeof(uint32_t)) {
+ return;
+ }
+ offsets_ = req;
+ advance(&req, &len, num_offsets * sizeof(uint32_t));
+
+ uint32_t previous_offset = 0;
+ for (size_t i = 0; i < num_offsets; i++) {
+ // A tag may have no data. Hence, subsequent offsets may be equal.
+ uint32_t offset;
+ memcpy(&offset, offsets_ + sizeof(uint32_t)*i, sizeof(uint32_t));
+
+ if (offset < previous_offset ||
+ offset % 4 != 0) {
+ return;
+ }
+ previous_offset = offset;
+ }
+ uint32_t last_offset = previous_offset;
+
+ // Validate list of tags. Tags must be in increasing order.
+ if (len < num_tags_ * sizeof(tag_t)) {
+ return;
+ }
+ tags_ = req;
+ advance(&req, &len, num_tags_ * sizeof(tag_t));
+
+ tag_t previous_tag = 0;
+ for (size_t i = 0; i < num_tags_; i++) {
+ tag_t tag;
+ memcpy(&tag, tags_ + sizeof(tag_t) * i, sizeof(tag_t));
+ if (i > 0 && tag <= previous_tag) {
+ return;
+ }
+ previous_tag = tag;
+ }
+
+ // Make sure the offset table doesn't point past the end of the data.
+ if (len < last_offset) {
+ return;
+ }
+
+ data_ = req;
+ len_ = len;
+ is_valid_ = true;
+}
+
+static int tag_cmp(const void *keyp, const void *memberp) {
+ tag_t key, member;
+ memcpy(&key, keyp, sizeof(uint32_t));
+ memcpy(&member, memberp, sizeof(uint32_t));
+
+ if (key == member) {
+ return 0;
+ }
+ return key < member ? -1 : 1;
+}
+
+bool Parser::GetTag(const uint8_t **out_data, size_t *out_len,
+ tag_t tag) const {
+ uint8_t *tagp = reinterpret_cast<uint8_t *>(
+ bsearch(&tag, tags_, num_tags_, sizeof(tag_t), tag_cmp));
+ if (tagp == nullptr) {
+ return false;
+ }
+ size_t tag_number = (tagp - tags_) / sizeof(uint32_t);
+
+ uint32_t offset = 0;
+ if (tag_number != 0) {
+ memcpy(&offset, offsets_ + sizeof(uint32_t) * (tag_number - 1),
+ sizeof(uint32_t));
+ }
+
+ *out_data = data_ + offset;
+ if (tag_number == num_tags_ - 1) {
+ *out_len = len_ - offset;
+ } else {
+ uint32_t next_offset;
+ memcpy(&next_offset, offsets_ + sizeof(uint32_t) * tag_number,
+ sizeof(uint32_t));
+ *out_len = next_offset - offset;
+ }
+ return true;
+}
+
+bool Parser::GetFixedLen(const uint8_t **out_data, tag_t tag,
+ size_t expected_len) const {
+ size_t len;
+ return GetTag(out_data, &len, tag) && len == expected_len;
+}
+
+template <typename T>
+bool Parser::Get(T *out_value, tag_t tag) const {
+ const uint8_t *data;
+ size_t len;
+ if (!GetTag(&data, &len, tag) ||
+ len != sizeof(T)) {
+ return false;
+ }
+ *out_value = *reinterpret_cast<const T *>(data);
+ return true;
+}
+
+template bool Parser::Get(uint32_t *, tag_t) const;
+template bool Parser::Get(uint64_t *, tag_t) const;
+
+Builder::Builder(uint8_t *out, size_t out_len, size_t num_tags)
+ : num_tags_(num_tags),
+ header_len_(MessageHeaderLen(num_tags)),
+ offsets_(out + sizeof(uint32_t)),
+ tags_(out + sizeof(uint32_t) * (1 + NumMessageOffsets(num_tags))) {
+ if (out_len < sizeof(uint32_t) ||
+ out_len < header_len_ ||
+ 0xffff < num_tags) {
+ return;
+ }
+
+ const uint32_t num_tags_32 = num_tags;
+ memcpy(out, &num_tags_32, sizeof(uint32_t));
+
+ data_ = out + header_len_;
+ len_ = out_len - header_len_;
+ valid_ = true;
+}
+
+bool Builder::AddTag(uint8_t **out_data, tag_t tag, size_t len) {
+ if (!valid_ ||
+ len%4 != 0 ||
+ len_ < len ||
+ tag_i_ >= num_tags_ ||
+ (have_previous_tag_ && tag <= previous_tag_)) {
+ return false;
+ }
+
+ memcpy(tags_ + sizeof(uint32_t)*tag_i_, &tag, sizeof(tag_t));
+ if (tag_i_ > 0) {
+ const uint32_t offset_32 = offset_;
+ memcpy(offsets_ + sizeof(uint32_t) * (tag_i_ - 1), &offset_32,
+ sizeof(uint32_t));
+ }
+ tag_i_++;
+ previous_tag_ = tag;
+ have_previous_tag_ = true;
+
+ *out_data = data_;
+
+ offset_ += len;
+ len_ -= len;
+ data_ += len;
+
+ return true;
+}
+
+bool Builder::AddTagData(tag_t tag, const uint8_t *data, size_t len) {
+ uint8_t *out;
+ if (!AddTag(&out, tag, len)) {
+ return false;
+ }
+ memcpy(out, data, len);
+ return true;
+}
+
+bool Builder::Finish(size_t *out_len) {
+ if (!valid_ || tag_i_ != num_tags_) {
+ return false;
+ }
+ *out_len = header_len_ + offset_;
+ valid_ = false;
+ return true;
+}
+
+constexpr uint8_t kHashLeafTweak[] = {0x00};
+constexpr uint8_t kHashNodeTweak[] = {0x01};
+
+void HashLeaf(uint8_t *out, const uint8_t *in) {
+ SHA512_CTX ctx;
+ SHA512_Init(&ctx);
+ SHA512_Update(&ctx, kHashLeafTweak, 1);
+ SHA512_Update(&ctx, in, kNonceLength);
+ SHA512_Final(out, &ctx);
+}
+
+void HashNode(uint8_t *out, const uint8_t *left, const uint8_t *right) {
+ SHA512_CTX ctx;
+ SHA512_Init(&ctx);
+ SHA512_Update(&ctx, kHashNodeTweak, 1);
+ SHA512_Update(&ctx, left, SHA512_DIGEST_LENGTH);
+ SHA512_Update(&ctx, right, SHA512_DIGEST_LENGTH);
+ SHA512_Final(out, &ctx);
+}
+
+} // namespace roughtime
diff --git a/protocol.h b/protocol.h
new file mode 100644
index 0000000..d0a8515
--- /dev/null
+++ b/protocol.h
@@ -0,0 +1,244 @@
+/* Copyright 2016 The Roughtime Authors.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License. */
+
+#ifndef SECURITY_ROUGHTIME_PROTOCOL_H_
+#define SECURITY_ROUGHTIME_PROTOCOL_H_
+
+#include <stdint.h>
+#include <string.h>
+
+#include <google/protobuf/stubs/macros.h>
+#include <openssl/curve25519.h>
+
+namespace roughtime {
+
+// Minimum size of a time request. Requests must be padded to larger than their
+// contents in order to reduce the value of a time server as a DDOS amplifier.
+constexpr size_t kMinRequestSize = 1024;
+
+constexpr size_t kNonceLength = 64; // Size of the client's nonce.
+
+constexpr size_t kTimestampSize = 8; // Size of the server's time.
+
+constexpr size_t kRadiusSize = 4; // Size of the server's uncertainty.
+
+typedef uint32_t tag_t;
+
+// MakeTag creates an integer value representing a tag. Requests and responses
+// in the time protocol are made up of tagged data, QUIC-style. Tags are 4
+// bytes long and meant to be readable-ish, but they cannot be chosen with
+// complete freedom, because they must be strictly increasing within a message
+// to permit binary searches.
+constexpr tag_t MakeTag(char a, char b, char c, char d) {
+ return static_cast<uint32_t>(a) | static_cast<uint32_t>(b) << 8 |
+ static_cast<uint32_t>(c) << 16 | static_cast<uint32_t>(d) << 24;
+}
+
+// kTagNONC ("nonce") is used in client requests. It tags the request's nonce.
+constexpr tag_t kTagNONC = MakeTag('N', 'O', 'N', 'C');
+// kTagPAD ("padding") is used in client requests. It tags the padding that
+// fills out the request to at least |kMinRequestSize|.
+constexpr tag_t kTagPAD = MakeTag('P', 'A', 'D', '\xff');
+
+// kTagMIDP is used in the signed portion of server responses. It tags the
+// midpoint of the server's time in Unix epoch-microseconds.
+constexpr tag_t kTagMIDP = MakeTag('M', 'I', 'D', 'P');
+// kTagRADI contains the radius of uncertainty (in microseconds) of the
+// server's time.
+constexpr tag_t kTagRADI = MakeTag('R', 'A', 'D', 'I');
+// kTagROOT is used in the signed portion of server responses. It tags the root
+// of a Merkle tree that contains the nonces from a batch of client requests.
+constexpr tag_t kTagROOT = MakeTag('R', 'O', 'O', 'T');
+
+// kTagSIG ("signature") is used in in the unsigned portion of server responses.
+// It tags a signature made using the key from the server's certificate.
+constexpr tag_t kTagSIG = MakeTag('S', 'I', 'G', '\0');
+// kTagPATH is used in the unsigned portion of server responses. It tags the
+// path from the client's nonce, a leaf node, to the root of the Merkle tree, so
+// that the client can verify the inclusion of its nonce in the tree.
+constexpr tag_t kTagPATH = MakeTag('P', 'A', 'T', 'H');
+// kTagSREP ("signed response") is used in the unsigned portion
+// of server responses. It tags the signed portion of the response.
+constexpr tag_t kTagSREP = MakeTag('S', 'R', 'E', 'P');
+// kTagCERT ("certificate") is used in the unsigned portion of server responses.
+// It tags a (not X.509) certificate. The tagged value is the public key whose
+// private key the server uses to sign its response. The public key is signed
+// offline by another keypair, whose public key is baked into the client.
+constexpr tag_t kTagCERT = MakeTag('C', 'E', 'R', 'T');
+// kTagINDX ("index") is used in the unsigned portion of server responses. It
+// tells the client the index that was assigned to its nonce when generating the
+// Merkle tree.
+constexpr tag_t kTagINDX = MakeTag('I', 'N', 'D', 'X');
+
+// kTagPUBK ("public key") is used in server certificates. It tags the public
+// key whose private key was used to sign the server's response.
+constexpr tag_t kTagPUBK = MakeTag('P', 'U', 'B', 'K');
+// kTagMINT ("minimum validity timestamp") is used in server certificates. It
+// tags the beginning of the certificate's validity period.
+constexpr tag_t kTagMINT = MakeTag('M', 'I', 'N', 'T');
+// kTagMAXT ("maximum validity timestamp") is used in server certificates. It
+// tags the end of the certificate's validity period.
+constexpr tag_t kTagMAXT = MakeTag('M', 'A', 'X', 'T');
+// kTagDELE ("delegation") is used in server certificates. It tags the data
+// signed by the server's offline key.
+constexpr tag_t kTagDELE = MakeTag('D', 'E', 'L', 'E');
+
+// kContextString is prefixed to the server's response before generating or
+// verifying the server's signature.
+static const char kContextString[] = "RoughTime v1 response signature";
+static_assert(sizeof(kContextString) % 4 == 0,
+ "Context strings must be a multiple of four bytes long");
+
+// kCertContextString is added as a prefix to the server's certificate before
+// generating or verifying the certificate's signature.
+static const char kCertContextString[] = "RoughTime v1 delegation signature--";
+static_assert(sizeof(kCertContextString) % 4 == 0,
+ "Context strings must be a multiple of four bytes long");
+
+// NumMessageOffsets gives the size in entries of the table of offsets for a
+// time protocol message having |num_tags| tags. (Since the length of messages
+// in the time protocol is known, a message with only one tag does not need a
+// table of offsets.)
+constexpr size_t NumMessageOffsets(size_t num_tags) {
+ return num_tags == 0 ? 0 : num_tags - 1;
+}
+
+// MessageHeaderLen gives the size in bytes of a message header, which consists
+// of a tag count, a table of offsets (if there are least two tags), and a list
+// of 0 or more tags.
+constexpr size_t MessageHeaderLen(size_t num_tags) {
+ return sizeof(uint32_t) /* tag count */ +
+ sizeof(uint32_t) * NumMessageOffsets(num_tags) /* offsets */ +
+ sizeof(tag_t) * num_tags /* tag values */;
+}
+
+// kPaddingLen is the number of padding bytes necessary to make a client request
+// sufficiently long.
+constexpr size_t kPaddingLen =
+ kMinRequestSize - (MessageHeaderLen(2) + kNonceLength);
+
+// Parser decodes requests from a time server client.
+//
+// 0 1 2 3
+// 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
+// +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+// | Number of tags |
+// +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+// | Offset, Tag 1 Data |
+// +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+// | ... |
+// +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+// | Offset, Tag N Data |
+// +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+// | Tag 0 |
+// +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+// | ... |
+// +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+// | Tag N |
+// +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+// | Data... |
+// | (indexed by offsets) |
+// | |
+// +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+class Parser {
+ public:
+ // Parses the supplied data. No copies are made, so the data pointed to by
+ // |req| must live as long as the |Parser| object. Callers should check
+ // |is_valid| before calling any other method.
+ Parser(const uint8_t* req, size_t len);
+
+ Parser() = delete;
+ Parser(const Parser&) = delete;
+ Parser& operator=(const Parser&) = delete;
+
+ bool is_valid() const { return is_valid_; }
+
+ // GetTag sets |*out_data| and |*out_len| to reflect the location (within the
+ // data supplied to the constructor) of the tag |tag|, if found. Returns true
+ // if |tag| is found.
+ bool GetTag(const uint8_t** out_data, size_t* out_len, tag_t tag) const;
+
+ // GetFixedLen is a specialization of |GetTag| that returns true only if the
+ // data tagged by |tag| is |expected_len| bytes long.
+ bool GetFixedLen(const uint8_t** out_data, tag_t tag,
+ size_t expected_len) const;
+
+ // Get is a specialization of |GetFixedLen| that expects |tag| to tag a value
+ // of type |T|. The tagged value is assigned to |*out_value|.
+ template <typename T>
+ bool Get(T* out_value, tag_t tag) const;
+
+ private:
+ bool is_valid_ = false;
+ size_t num_tags_;
+ const uint8_t* offsets_; // |NumMessageOffsets| offsets into |data_|.
+ const uint8_t* tags_; // |num_tags_| 32-bit tags.
+ const uint8_t* data_; // |len_| bytes.
+ size_t len_;
+};
+
+// Builder creates a time server response.
+class Builder {
+ public:
+ Builder() = delete;
+ Builder(const Builder&) = delete;
+ Builder& operator=(const Builder&) = delete;
+
+ // Prepares to write tags and data to a buffer |out| of |out_len| bytes.
+ Builder(uint8_t* out, size_t out_len, size_t num_tags);
+
+ // AddTag adds the tag |tag| to the response, which must be greater than any
+ // previously added tag, and sets |*out_data| to an address where |len| bytes
+ // may be written. Returns true iff the tag may be written.
+ bool AddTag(uint8_t** out_data, tag_t tag, size_t len);
+
+ // AddTagData is a specialization of |AddTag| that copies the |len| bytes
+ // pointed to by |data| into the response. Returns true iff the tag was
+ // written.
+ bool AddTagData(tag_t tag, const uint8_t* data, size_t len);
+
+ // Finish returns true if the response is valid, and sets |out_len| to the
+ // size of the response. After calling |Finish| all subsequent calls will
+ // fail.
+ bool Finish(size_t* out_len);
+
+ private:
+ const size_t num_tags_;
+ const size_t header_len_;
+ uint8_t* const offsets_;
+ uint8_t* const tags_;
+
+ uint8_t* data_; // Offset of next |AddTag|.
+ size_t len_; // Bytes remaining in the output buffer.
+ size_t offset_ = 0; // Offset of data for next tag.
+
+ size_t tag_i_ = 0; // Index of next tag.
+ tag_t previous_tag_;
+ bool have_previous_tag_ = false;
+
+ bool valid_ = false;
+};
+
+// Computes the SHA-512 hash of a Merkle tree leaf, i.e. a client's nonce, as
+// 0||nonce. |in| is assumed to point to |kNonceLength| bytes and |out| is
+// assumed to have space for |SHA512_DIGEST_LENGTH| bytes.
+void HashLeaf(uint8_t* out, const uint8_t* in);
+
+// Computes the SHA-512 hash of a Merkle tree node as 1||left||right. |left|,
+// |right|, and |out| are assumed to point to |SHA512_DIGEST_LENGTH| bytes.
+void HashNode(uint8_t* out, const uint8_t* left, const uint8_t* right);
+
+} // namespace roughtime
+
+#endif // SECURITY_ROUGHTIME_PROTOCOL_H_
diff --git a/protocol_test.cc b/protocol_test.cc
new file mode 100644
index 0000000..a912fcf
--- /dev/null
+++ b/protocol_test.cc
@@ -0,0 +1,289 @@
+/* Copyright 2016 The Roughtime Authors.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License. */
+
+#include "protocol.h"
+#include "gtest/gtest.h"
+
+#include <openssl/sha.h>
+
+namespace roughtime {
+
+constexpr tag_t kTagTAG1 = MakeTag('T', 'A', 'G', '1');
+constexpr tag_t kTagTAG2 = MakeTag('T', 'A', 'G', '2');
+constexpr tag_t kTagTAG3 = MakeTag('T', 'A', 'G', '3');
+constexpr tag_t kTagTAG4 = MakeTag('T', 'A', 'G', '4');
+
+TEST(ParserTest, Success) {
+ alignas(4) uint8_t buffer[] = {
+ 0x00, // misalign the buffer
+ 0x03, 0x00, 0x00, 0x00, // 3 tags
+ 0x04, 0x00, 0x00, 0x00, // tag #2 has offset 4
+ 0x08, 0x00, 0x00, 0x00, // tag #3 has offset 8
+ 0x54, 0x41, 0x47, 0x31, // TAG1
+ 0x54, 0x41, 0x47, 0x32, // TAG2
+ 0x54, 0x41, 0x47, 0x33, // TAG3
+ 0x11, 0x11, 0x11, 0x11, // data for tag #1
+ 0x22, 0x22, 0x22, 0x22, // data for tag #2
+ 0x33, 0x33, 0x33, 0x33, // data for tag #3
+ };
+
+ Parser parser(buffer + 1, sizeof(buffer) - 1);
+ EXPECT_TRUE(parser.is_valid());
+ const uint8_t* datap;
+ size_t len;
+
+ EXPECT_TRUE(parser.GetTag(&datap, &len, kTagTAG1));
+ EXPECT_EQ(4, len);
+ EXPECT_TRUE(memcmp("\x11\x11\x11\x11", datap, len) == 0);
+ datap = nullptr;
+ EXPECT_TRUE(parser.GetFixedLen(&datap, kTagTAG1, 4));
+ EXPECT_TRUE(memcmp("\x11\x11\x11\x11", datap, len) == 0);
+ datap = nullptr;
+
+ EXPECT_TRUE(parser.GetTag(&datap, &len, kTagTAG2));
+ EXPECT_EQ(4, len);
+ EXPECT_TRUE(memcmp("\x22\x22\x22\x22", datap, len) == 0);
+ datap = nullptr;
+ EXPECT_TRUE(parser.GetFixedLen(&datap, kTagTAG2, 4));
+ EXPECT_TRUE(memcmp("\x22\x22\x22\x22", datap, len) == 0);
+ datap = nullptr;
+
+ EXPECT_TRUE(parser.GetTag(&datap, &len, kTagTAG3));
+ EXPECT_EQ(4, len);
+ EXPECT_TRUE(memcmp("\x33\x33\x33\x33", datap, len) == 0);
+ datap = nullptr;
+ EXPECT_TRUE(parser.GetFixedLen(&datap, kTagTAG3, 4));
+ EXPECT_TRUE(memcmp("\x33\x33\x33\x33", datap, len) == 0);
+ datap = nullptr;
+
+ EXPECT_FALSE(parser.GetTag(&datap, &len, kTagTAG4));
+ EXPECT_FALSE(parser.GetFixedLen(&datap, kTagTAG4, 1));
+}
+
+TEST(ParserTest, IntegerTypes) {
+ uint8_t buffer[128];
+ Builder builder(buffer, sizeof(buffer), 2);
+ uint64_t big = 0xdeaddeaddeaddeadULL;
+ uint32_t little = 0xbeefbeef;
+
+ ASSERT_TRUE(builder.AddTagData(kTagTAG1, reinterpret_cast<uint8_t*>(&big),
+ sizeof(big)));
+ ASSERT_TRUE(builder.AddTagData(kTagTAG2, reinterpret_cast<uint8_t*>(&little),
+ sizeof(little)));
+ size_t out_len;
+ ASSERT_TRUE(builder.Finish(&out_len));
+
+ Parser parser(buffer, out_len);
+ EXPECT_TRUE(parser.is_valid());
+ big = 0;
+ little = 0;
+
+ EXPECT_FALSE(parser.Get(&big, kTagTAG2)); // Wrong tag.
+ EXPECT_TRUE(parser.Get(&big, kTagTAG1));
+ EXPECT_EQ(0xdeaddeaddeaddeadULL, big);
+
+ EXPECT_FALSE(parser.Get(&little, kTagTAG1)); // Wrong tag.
+ EXPECT_TRUE(parser.Get(&little, kTagTAG2));
+ EXPECT_EQ(0xbeefbeef, little);
+}
+
+TEST(ParserTest, EmptyMessage) {
+ uint8_t buffer[] = {
+ 0x00, 0x00, 0x00, 0x00, // 0 tags.
+ };
+ Parser parser(buffer, sizeof(buffer));
+ EXPECT_TRUE(parser.is_valid());
+}
+
+TEST(ParserTest, TooManyTags) {
+ uint8_t buffer[] = {
+ 0xff, 0xff, 0xff, 0xff, // hella tags.
+ };
+ Parser parser(buffer, sizeof(buffer));
+ EXPECT_FALSE(parser.is_valid());
+}
+
+TEST(ParserTest, TwoEmptyTags) {
+ uint8_t buffer[] = {
+ 0x02, 0x00, 0x00, 0x00, // 2 tags.
+ 0x00, 0x00, 0x00, 0x00, // tag #2 has offset 0
+ 0x01, 0x00, 0x00, 0x00, // tag #1
+ 0x02, 0x00, 0x00, 0x00, // tag #2
+ };
+ Parser parser(buffer, sizeof(buffer));
+ EXPECT_TRUE(parser.is_valid());
+}
+
+TEST(ParserTest, OffsetNotAMultipleOf4) {
+ uint8_t buffer[] = {
+ 0x02, 0x00, 0x00, 0x00, // 2 tags.
+ 0x03, 0x00, 0x00, 0x00, // tag #2 has offset 3
+ 0x54, 0x41, 0x47, 0x31, // TAG1
+ 0x55, 0x41, 0x47, 0x31, // TAG2
+ 0x00, 0x00, 0x00, 0x00,
+ 0x00, 0x00, 0x00, 0x00,
+ };
+ Parser parser(buffer, sizeof(buffer));
+ EXPECT_FALSE(parser.is_valid());
+}
+
+TEST(ParserTest, OffsetsOutOfOrder) {
+ uint8_t buffer[] = {
+ 0x03, 0x00, 0x00, 0x00, // 3 tags.
+ 0x08, 0x00, 0x00, 0x00, // tag #2 has offset 8
+ 0x04, 0x00, 0x00, 0x00, // tag #3 has offset 4
+ };
+ Parser parser(buffer, sizeof(buffer));
+ EXPECT_FALSE(parser.is_valid());
+}
+
+TEST(ParserTest, TagsOutOfOrder) {
+ uint8_t buffer[] = {
+ 0x02, 0x00, 0x00, 0x00, // 2 tags.
+ 0x00, 0x00, 0x00, 0x00, // tag #2 has offset 0
+ 0x01, 0x00, 0x00, 0x00, // tag #1
+ 0x01, 0x00, 0x00, 0x00, // tag #2, same as #1 (out of order)
+ };
+ Parser parser(buffer, sizeof(buffer));
+ EXPECT_FALSE(parser.is_valid());
+}
+
+TEST(ParserTest, InvalidOffset) {
+ uint8_t buffer[] = {
+ 0x02, 0x00, 0x00, 0x00, // 2 tags.
+ 0x04, 0x00, 0x00, 0x00, // tag #2 has offset 4 (past end of message)
+ 0x01, 0x00, 0x00, 0x00, // tag #1
+ 0x02, 0x00, 0x00, 0x00, // tag #2
+ };
+ Parser parser(buffer, sizeof(buffer));
+ EXPECT_FALSE(parser.is_valid());
+}
+
+TEST(BuilderTest, Success) {
+ uint8_t buffer[128];
+ Builder builder(buffer, sizeof(buffer), 3);
+ const uint8_t* data = reinterpret_cast<const uint8_t*>("1234");
+
+ EXPECT_TRUE(builder.AddTagData(kTagTAG1, data, 4));
+ EXPECT_TRUE(builder.AddTagData(kTagTAG2, data, 4));
+ EXPECT_TRUE(builder.AddTagData(kTagTAG3, data, 4));
+ size_t out_len = 0;
+ EXPECT_TRUE(builder.Finish(&out_len));
+ constexpr uint8_t kExpected[] = {
+ 0x03, 0x00, 0x00, 0x00, // 3 tags
+ 0x04, 0x00, 0x00, 0x00, // tag #2 has offset 4
+ 0x08, 0x00, 0x00, 0x00, // tag #3 has offset 8
+ 0x54, 0x41, 0x47, 0x31, // TAG1
+ 0x54, 0x41, 0x47, 0x32, // TAG2
+ 0x54, 0x41, 0x47, 0x33, // TAG3
+ 0x31, 0x32, 0x33, 0x34,
+ 0x31, 0x32, 0x33, 0x34,
+ 0x31, 0x32, 0x33, 0x34,
+ };
+ EXPECT_EQ(sizeof(kExpected), out_len);
+ EXPECT_EQ(0, memcmp(kExpected, buffer, sizeof(kExpected)));
+}
+
+TEST(BuilderTest, ExtraTag) {
+ uint8_t buffer[128];
+ Builder builder(buffer, sizeof(buffer), 1);
+ uint32_t data = 42;
+ EXPECT_TRUE(builder.AddTagData(
+ kTagTAG1, reinterpret_cast<const uint8_t*>(&data), sizeof(data)));
+ EXPECT_FALSE(builder.AddTagData(
+ kTagTAG2, reinterpret_cast<const uint8_t*>(&data), sizeof(data)));
+}
+
+TEST(BuilderTest, AddAfterFinish) {
+ uint8_t buffer[128];
+ Builder builder(buffer, sizeof(buffer), 1);
+ uint32_t data = 42;
+ EXPECT_TRUE(builder.AddTagData(
+ kTagTAG1, reinterpret_cast<const uint8_t*>(&data), sizeof(data)));
+ size_t out_len = 0;
+ EXPECT_TRUE(builder.Finish(&out_len));
+ EXPECT_FALSE(builder.AddTagData(
+ kTagTAG2, reinterpret_cast<const uint8_t*>(&data), sizeof(data)));
+}
+
+TEST(BuilderTest, EmptyMessage) {
+ uint8_t buffer[4];
+ Builder builder(buffer, sizeof(buffer), 0);
+ size_t len;
+ EXPECT_TRUE(builder.Finish(&len));
+}
+
+TEST(BuilderTest, FinishAfterFinish) {
+ uint8_t buffer[4];
+ Builder builder(buffer, sizeof(buffer), 0);
+ size_t len;
+ EXPECT_TRUE(builder.Finish(&len));
+ EXPECT_FALSE(builder.Finish(&len));
+}
+
+TEST(BuilderTest, MissingTag) {
+ uint8_t buffer[4];
+ Builder builder(buffer, sizeof(buffer), 1);
+ size_t len;
+ EXPECT_FALSE(builder.Finish(&len));
+}
+
+TEST(BuilderTest, ShortBuffer) {
+ uint8_t buffer[3];
+ Builder builder(buffer, sizeof(buffer), 0);
+ size_t len;
+ EXPECT_FALSE(builder.Finish(&len));
+}
+
+TEST(HashTest, SimpleTree) {
+ uint8_t zeros[kNonceLength];
+ memset(zeros, 0, sizeof(zeros));
+ uint8_t left[SHA512_DIGEST_LENGTH];
+ HashLeaf(left, zeros);
+ constexpr uint8_t kExpectedLeftHash[SHA512_DIGEST_LENGTH] = {
+ 0x19, 0xdc, 0x6a, 0xe1, 0x2d, 0xe0, 0x8b, 0x21, 0xb3, 0x6c, 0x1e,
+ 0xc7, 0xf3, 0x53, 0xce, 0x9e, 0x7c, 0xef, 0x73, 0xfa, 0x4d, 0x13,
+ 0x54, 0xc4, 0x36, 0x23, 0x41, 0x67, 0xf0, 0x84, 0x7b, 0xc9, 0xe2,
+ 0xb8, 0x5e, 0x2f, 0x36, 0x20, 0x8f, 0x77, 0x3e, 0xf3, 0x24, 0xe2,
+ 0xd7, 0x9e, 0x6a, 0xf1, 0xbe, 0xca, 0x44, 0x70, 0xe4, 0x4b, 0x86,
+ 0x72, 0xb4, 0x7d, 0x07, 0x7e, 0xfe, 0x33, 0xa1, 0xf8};
+ EXPECT_EQ(0, memcmp(kExpectedLeftHash, left, SHA512_DIGEST_LENGTH));
+
+ uint8_t nonzeros[kNonceLength];
+ memset(nonzeros, 'a', sizeof(nonzeros));
+ uint8_t right[SHA512_DIGEST_LENGTH];
+ HashLeaf(right, nonzeros);
+ constexpr uint8_t kExpectedRightHash[SHA512_DIGEST_LENGTH] = {
+ 0x3d, 0x3a, 0xb5, 0x8a, 0x53, 0xc4, 0x57, 0x2a, 0x2a, 0x47, 0xeb,
+ 0x04, 0xd3, 0x22, 0x18, 0x5a, 0x7b, 0x47, 0xe6, 0x85, 0xd2, 0xa6,
+ 0x8f, 0x3b, 0xb8, 0xee, 0x4d, 0x34, 0x78, 0xa3, 0x34, 0x2a, 0xa7,
+ 0xe1, 0x06, 0xb7, 0x28, 0xb6, 0x06, 0xbd, 0x73, 0x17, 0xf0, 0x8f,
+ 0x37, 0xd9, 0xb0, 0xb5, 0x46, 0x90, 0x0b, 0x6e, 0x02, 0xa4, 0x01,
+ 0x7e, 0x77, 0xce, 0xbc, 0x63, 0xc4, 0x77, 0xb6, 0x7f,
+ };
+ EXPECT_EQ(0, memcmp(kExpectedRightHash, right, SHA512_DIGEST_LENGTH));
+
+ uint8_t root[SHA512_DIGEST_LENGTH];
+ HashNode(root, left, right);
+ constexpr uint8_t kExpectedRootHash[SHA512_DIGEST_LENGTH] = {
+ 0x6a, 0xcd, 0xdd, 0x50, 0x32, 0x56, 0xc3, 0x53, 0x6c, 0x19, 0xe5,
+ 0x79, 0x20, 0xf3, 0xeb, 0xa9, 0x81, 0xb8, 0x8a, 0x1b, 0x25, 0x10,
+ 0x88, 0x97, 0xb4, 0x4a, 0x9a, 0x39, 0xc7, 0x58, 0x0d, 0x33, 0x87,
+ 0xab, 0x4f, 0x1e, 0x91, 0x49, 0x7d, 0xd7, 0xb7, 0xc3, 0xa9, 0xf5,
+ 0xa2, 0x24, 0xe1, 0x77, 0x50, 0x50, 0xa4, 0x69, 0xf1, 0x68, 0xcf,
+ 0x51, 0x0a, 0xac, 0xd2, 0x04, 0x39, 0x1a, 0x48, 0x7e};
+ EXPECT_EQ(0, memcmp(kExpectedRootHash, root, SHA512_DIGEST_LENGTH));
+}
+
+} // namespace roughtime
diff --git a/roughtime-servers.json b/roughtime-servers.json
new file mode 100644
index 0000000..4ae9bad
--- /dev/null
+++ b/roughtime-servers.json
@@ -0,0 +1,17 @@
+{
+ "created": "2016-08-30T23:09:00Z",
+ "expires": "2017-03-01T00:00:00Z",
+ "servers": [
+ {
+ "name": "Google",
+ "publicKeyType": "ed25519",
+ "publicKey": "etPaaIxcBMY1oUeGpwvPMCJMwlRVNxv51KK/tktoJTQ=",
+ "addresses": [
+ {
+ "protocol": "udp",
+ "address": "roughtime.sandbox.google.com:2002"
+ }
+ ]
+ }
+ ]
+}
diff --git a/server.cc b/server.cc
new file mode 100644
index 0000000..85443db
--- /dev/null
+++ b/server.cc
@@ -0,0 +1,231 @@
+/* Copyright 2016 The Roughtime Authors.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License. */
+
+#include <errno.h>
+#include <stdint.h>
+#include <string.h>
+#include <sys/types.h>
+#include <unistd.h>
+
+#include <google/protobuf/stubs/logging.h>
+#include <openssl/curve25519.h>
+
+#include "protocol.h"
+#include "server.h"
+
+namespace roughtime {
+
+static_assert(kMaxRecvPacketSize % 4 == 0,
+ "kMaxRecvPacketSize must be a multiple of four");
+static_assert(kBatchSize != 0 && (kBatchSize & (kBatchSize - 1)) == 0,
+ "kBatchSize must be a power of two");
+static_assert(1u << kBatchSizeLog2 == kBatchSize,
+ "kBatchSizeLog2 is incorrect");
+static_assert(kMinRequestSize <= kMaxRecvPacketSize,
+ "Miniumum request size must be <= to the maximum packet size");
+
+static_assert(kMaxResponseSize <= kMinRequestSize,
+ "This design could be a DDoS amplifier");
+
+static_assert(ED25519_SIGNATURE_LEN == 64, "crypto constant mismatch");
+static_assert(ED25519_PUBLIC_KEY_LEN == 32, "crypto constant mismatch");
+static_assert(ED25519_PRIVATE_KEY_LEN == 64, "crypto constant mismatch");
+
+Server::Server(std::unique_ptr<Identity> identity,
+ std::unique_ptr<TimeSource> time_source)
+ : time_source_(std::move(time_source)),
+ identity_(std::move(identity)),
+ num_leaves_(0),
+ to_be_signed_(to_be_signed_with_context_ + sizeof(kContextString)) {
+ memcpy(to_be_signed_with_context_, kContextString, sizeof(kContextString));
+}
+
+bool Server::AddRequest(const uint8_t *packet, size_t len) {
+ GOOGLE_DCHECK_LE(num_leaves_, kBatchSize);
+
+ if (len < kMinRequestSize) {
+ return false;
+ }
+
+ Parser request(packet, len);
+ if (!request.is_valid()) {
+ return false;
+ }
+
+ const uint8_t *nonce;
+ if (!request.GetFixedLen(&nonce, kTagNONC, kNonceLength)) {
+ return false;
+ }
+
+ // kTagPAD lives here too, but we don't bother to check for it. The check
+ // above against |kMinRequestSize| is sufficient.
+ tree_.AddLeaf(num_leaves_++, nonce);
+
+ return true;
+}
+
+bool Server::Sign() {
+ GOOGLE_DCHECK_GT(num_leaves_, 0);
+
+ // The signature is over the root hash and the timestamp---that's it!
+ tree_.Build(num_leaves_);
+ const auto interval = time_source_->Now();
+ const uint64_t now = interval.first;
+ const uint32_t radius = interval.second;
+
+ Builder to_be_signed(to_be_signed_, kToBeSignedSize, 3);
+ size_t to_be_signed_len;
+
+ static_assert(kTagRADI < kTagMIDP, "Tags must be written in order");
+ static_assert(kTagMIDP < kTagROOT, "Tags must be written in order");
+ if (!to_be_signed.AddTagData(kTagRADI,
+ reinterpret_cast<const uint8_t *>(&radius),
+ sizeof(radius)) ||
+ !to_be_signed.AddTagData(
+ kTagMIDP, reinterpret_cast<const uint8_t *>(&now), sizeof(now)) ||
+ !to_be_signed.AddTagData(kTagROOT, tree_.GetRoot(), kNonceLength) ||
+ !to_be_signed.Finish(&to_be_signed_len)) {
+ GOOGLE_LOG(ERROR) << "failed to construct to_be_signed";
+ return false;
+ }
+ GOOGLE_CHECK_EQ(to_be_signed_len, kToBeSignedSize);
+
+ if (!ED25519_sign(signature_, to_be_signed_with_context_,
+ sizeof(to_be_signed_with_context_),
+ identity_->private_key)) {
+ GOOGLE_LOG(ERROR) << "signature failure";
+ return false;
+ }
+ return true;
+}
+
+bool Server::MakeResponse(uint8_t *out_response, size_t *out_len,
+ uint32_t index) {
+ GOOGLE_DCHECK_LT(index, num_leaves_);
+ static_assert(kMaxResponseSize <= kMaxRecvPacketSize,
+ "Receive buffers are too small to use as send buffers");
+ Builder response(out_response, kMaxResponseSize, 5);
+ static_assert(kTagSIG < kTagPATH, "Tags must be written in order");
+ static_assert(kTagPATH < kTagSREP, "Tags must be written in order");
+ static_assert(kTagSREP < kTagCERT, "Tags must be written in order");
+ static_assert(kTagCERT < kTagINDX, "Tags must be written in order");
+
+ uint8_t *path;
+ uint8_t *pindex = reinterpret_cast<uint8_t *>(&index);
+ if (!response.AddTagData(kTagSIG, signature_, sizeof(signature_)) ||
+ !response.AddTag(&path, kTagPATH, kNonceLength * tree_.GetPathLength()) ||
+ !response.AddTagData(kTagSREP, to_be_signed_, kToBeSignedSize) ||
+ !response.AddTagData(kTagCERT, identity_->certificate, kCertSize) ||
+ !response.AddTagData(kTagINDX, pindex, sizeof(index)) ||
+ !response.Finish(out_len)) {
+ GOOGLE_LOG(ERROR) << "failed to construct response";
+ return false;
+ }
+
+ tree_.GetPath(path, index);
+ return true;
+}
+
+// static
+bool CreateCertificate(uint8_t out_cert[kCertSize],
+ const uint8_t root_private_key[ED25519_PRIVATE_KEY_LEN],
+ uint64_t start_time, uint64_t end_time,
+ const uint8_t public_key[ED25519_PUBLIC_KEY_LEN]) {
+ GOOGLE_CHECK_LT(start_time, end_time);
+ uint8_t to_be_signed_bytes[sizeof(kCertContextString) + kToBeSignedCertSize];
+ size_t to_be_signed_len;
+ memcpy(to_be_signed_bytes, kCertContextString, sizeof(kCertContextString));
+
+ Builder to_be_signed(to_be_signed_bytes + sizeof(kCertContextString),
+ kToBeSignedCertSize, 3);
+ static_assert(kTagPUBK < kTagMINT, "Tags must be written in order");
+ static_assert(kTagMINT < kTagMAXT, "Tags must be written in order");
+ if (!to_be_signed.AddTagData(kTagPUBK, public_key, ED25519_PUBLIC_KEY_LEN) ||
+ !to_be_signed.AddTagData(kTagMINT,
+ reinterpret_cast<uint8_t *>(&start_time),
+ sizeof(start_time)) ||
+ !to_be_signed.AddTagData(kTagMAXT, reinterpret_cast<uint8_t *>(&end_time),
+ sizeof(end_time)) ||
+ !to_be_signed.Finish(&to_be_signed_len)) {
+ GOOGLE_LOG(ERROR) << "failed to construct signed portion of certificate";
+ return false;
+ }
+ GOOGLE_CHECK_EQ(to_be_signed_len, kToBeSignedCertSize);
+
+ uint8_t signature[ED25519_SIGNATURE_LEN];
+ if (!ED25519_sign(signature, to_be_signed_bytes, sizeof(to_be_signed_bytes),
+ root_private_key)) {
+ GOOGLE_LOG(ERROR) << "failed to sign certificate";
+ return false;
+ }
+
+ size_t cert_len;
+ Builder cert(out_cert, kCertSize, 2);
+
+ static_assert(kTagSIG < kTagDELE, "Tags must be written in order");
+ if (!cert.AddTagData(kTagSIG, signature, sizeof(signature)) ||
+ !cert.AddTagData(kTagDELE,
+ to_be_signed_bytes + sizeof(kCertContextString),
+ to_be_signed_len) ||
+ !cert.Finish(&cert_len)) {
+ GOOGLE_LOG(ERROR) << "failed to construct certificate";
+ return false;
+ }
+ GOOGLE_CHECK_EQ(cert_len, kCertSize);
+ return true;
+}
+
+void Tree::Build(size_t num_nodes) {
+ GOOGLE_DCHECK_GT(num_nodes, 0);
+ size_t level;
+ for (level = 0; num_nodes > 1; level++, num_nodes /= 2) {
+ // Even out the level with a dummy node, if need be.
+ if (num_nodes % 2 == 1) {
+ memset(tree_[level][num_nodes], 0, kNonceLength);
+ num_nodes++;
+ }
+ for (size_t i = 0; i < num_nodes; i += 2) {
+ HashNode(tree_[level + 1][i / 2], tree_[level][i], tree_[level][i + 1]);
+ }
+ }
+ GOOGLE_DCHECK_EQ(1, num_nodes); // Root node.
+ levels_ = level + 1;
+}
+
+void Tree::GetPath(uint8_t *out_path, size_t index) {
+ // At the lowest level, the client knows its own leaf hash, so send it only
+ // that leaf's sibling, and so on up the tree.
+ for (size_t level = 0; level < levels_ - 1; level++) {
+ if (index % 2 == 1) {
+ memcpy(out_path, tree_[level][index - 1], kNonceLength);
+ } else {
+ memcpy(out_path, tree_[level][index + 1], kNonceLength);
+ }
+ out_path += kNonceLength;
+ index /= 2;
+ }
+ GOOGLE_DCHECK_EQ(0, index);
+}
+
+BrokenReplyGenerator::~BrokenReplyGenerator() {}
+
+uint16_t BrokenReplyGenerator::probability_1024() const {
+ return probability_1024_;
+}
+
+void BrokenReplyGenerator::set_probability_1024(uint16_t probability) {
+ probability_1024_ = probability;
+}
+
+} // namespace roughtime
diff --git a/server.h b/server.h
new file mode 100644
index 0000000..7953a38
--- /dev/null
+++ b/server.h
@@ -0,0 +1,197 @@
+/* Copyright 2016 The Roughtime Authors.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License. */
+
+#ifndef SECURITY_ROUGHTIME_SERVER_H_
+#define SECURITY_ROUGHTIME_SERVER_H_
+
+#include <memory>
+#include <utility>
+
+#include <google/protobuf/stubs/macros.h>
+
+#include "protocol.h"
+#include "time_source.h"
+
+namespace roughtime {
+
+// kToBeSignedCertSize is the size of the signed portion (DELE) of a
+// certificate. Its tags are (PUBK, MINT, MAXT).
+constexpr size_t kToBeSignedCertSize = MessageHeaderLen(3) +
+ ED25519_PUBLIC_KEY_LEN + kTimestampSize +
+ kTimestampSize;
+
+// kCertSize is the size of the entire certificate. Its tags are (DELE, SIG).
+constexpr size_t kCertSize =
+ MessageHeaderLen(2) + ED25519_SIGNATURE_LEN + kToBeSignedCertSize;
+
+// CreateCertificate signs the supplied |public_key| using |root_private_key|,
+// and sets |out_cert| to a certificate containing the public key, the
+// signature, and the supplied validity interval. Returns true if successful,
+// otherwise false.
+// TODO(mab): Find better home for this, likely in an offline tool.
+bool CreateCertificate(uint8_t out_cert[kCertSize],
+ const uint8_t root_private_key[ED25519_PRIVATE_KEY_LEN],
+ uint64_t start_time, uint64_t end_time,
+ const uint8_t public_key[ED25519_PUBLIC_KEY_LEN]);
+
+// Identity is a server's private key and certificate. (The certificate is the
+// server's public key signed by an offline private master key.)
+struct Identity {
+ uint8_t private_key[ED25519_PRIVATE_KEY_LEN];
+ uint8_t certificate[kCertSize];
+};
+
+// kBatchSizeLog2 is one less than the number of levels in the Merkle tree of
+// client nonces. The response packet must have room for this many hashes.
+// This value was taken because it's too easy to saturate batches of size 32 in
+// load testing so 64 seems like a reasonable number for now. We may revisit
+// this if the non-crypto parts of processing become less expensive.
+constexpr size_t kBatchSizeLog2 = 6;
+
+// kBatchSize is the most requests we'll process at a time, a.k.a. the number of
+// leaves in the Merkle tree.
+constexpr size_t kBatchSize = 1 << kBatchSizeLog2;
+
+// Tree encapsulates the Merkle tree of client nonces. The tree is too large
+// (2**13 bytes) to be sent to each client, so each client is sent the part of
+// the tree necessary to verify the inclusion of its nonce.
+class Tree {
+ public:
+ Tree() {}
+ Tree(const Tree&) = delete;
+ Tree& operator=(const Tree&) = delete;
+
+ // AddLeaf adds a new client nonce at the specified index.
+ void AddLeaf(size_t index, const uint8_t nonce[kNonceLength]) {
+ HashLeaf(tree_[0][index], nonce);
+ }
+
+ // Build constructs the Merkle tree. The existing |num_leaves| leaf hashes in
+ // levels_[0] are left alone, and the tree is built by (possibly adding a
+ // dummy leaf node and) creating levels 1 and higher.
+ //
+ // If |num_leaves| is 1, this is a no-op. In that case, the root is the same
+ // node as the one leaf.
+ void Build(size_t num_leaves);
+
+ // GetPathLength returns the number of nodes necessary to represent a path to
+ // the root. This may be zero.
+ size_t GetPathLength() { return levels_ - 1; }
+
+ // GetPath sets |*out_path| to the data needed to verify inclusion in the root
+ // hash of the leaf at |index|. The path consists of one node for each
+ // sub-root level. So, for example, the first element is the leaf that is the
+ // sibling of the leaf at |index|.
+ //
+ // The data are intended for consumption by a client that knows the leaf at
+ // |index|, because it is that client's nonce.
+ void GetPath(uint8_t* out_path, size_t index);
+
+ // GetRoot returns a pointer to the root hash, which is |kNonceLength| bytes
+ // long.
+ const uint8_t* GetRoot() { return tree_[levels_ - 1][0]; }
+
+ private:
+ // tree_ is a Merkle tree. The first index is the level of the tree, with
+ // leaves at level 0.
+ uint8_t tree_[kBatchSizeLog2 + 1][kBatchSize][kNonceLength];
+
+ // Level is the number of levels in the tree, including the root. Hence,
+ // after calling |Build|, the root lives at |tree_[levels_-1][0]|.
+ size_t levels_;
+};
+
+constexpr size_t kMaxRecvPacketSize = kMinRequestSize;
+
+constexpr size_t kToBeSignedSize =
+ MessageHeaderLen(3) + kTimestampSize + kRadiusSize + kNonceLength;
+
+// kMaxResponseSize is the size of the largest possible server response.
+constexpr size_t kMaxResponseSize =
+ MessageHeaderLen(5) + kCertSize + kToBeSignedSize + ED25519_SIGNATURE_LEN +
+ (kBatchSizeLog2 * kNonceLength) + sizeof(uint32_t) /* index */;
+
+class Server {
+ public:
+ Server() = delete;
+ Server(const Server&) = delete;
+ Server& operator=(const Server&) = delete;
+
+ Server(std::unique_ptr<Identity> identity,
+ std::unique_ptr<TimeSource> time_source);
+
+ // AddRequest decodes |packet|. If the packet is valid, it is added to
+ // |tree_| and true is returned. Otherwise, false is returned.
+ bool AddRequest(const uint8_t* packet, size_t len);
+
+ // Sign creates a signed response (Merkle tree root and timestamp) and a
+ // signature.
+ bool Sign();
+
+ // MakeResponse creates a response for the |index|'th leaf node of the Merkle
+ // tree, where the indices correspond to successful calls to |AddRequest|.
+ bool MakeResponse(uint8_t* out_response, size_t* out_len, uint32_t index);
+
+ void Reset() { num_leaves_ = 0; }
+
+ private:
+ std::unique_ptr<TimeSource> time_source_;
+
+ std::unique_ptr<Identity> identity_;
+
+ Tree tree_;
+ // num_leaves is the number of leaf nodes inserted
+ size_t num_leaves_;
+
+ // to_be_signed_with_context_ is the signed portion of the server's response,
+ // prefixed by |kContextString|.
+ uint8_t to_be_signed_with_context_[kToBeSignedSize + sizeof(kContextString)];
+
+ // to_be_signed_ points |sizeof(kContextStringBytes)| into
+ // |to_be_signed_with_context_|, for convenience. It contains tags (ROOT,
+ // TIME).
+ uint8_t* const to_be_signed_;
+
+ // Signature is the ED25519 signature over |to_be_signed_with_context_|.
+ uint8_t signature_[ED25519_SIGNATURE_LEN];
+};
+
+// BrokenReplyGenerator is an interface for generating replies that are broken
+// in a variety of ways. This is used to ensure that clients correctly handle
+// various corner cases.
+class BrokenReplyGenerator {
+ public:
+ virtual ~BrokenReplyGenerator();
+
+ // probability_1024 returns the probability, in parts-per-1024, that this
+ // generator should be used for a given request.
+ uint16_t probability_1024() const;
+ void set_probability_1024(uint16_t probabilty);
+
+ // Process takes a valid request in |request| and the standard response in
+ // |normal_response|. If it wishes to substitute an alternative reply then it
+ // may write up to |max_out_len| bytes to |out|, set |*out_len| to the number
+ // of bytes written and return true. Otherwise it must return false.
+ virtual bool Process(uint8_t* out, size_t* out_len, size_t max_out_len,
+ const uint8_t* normal_response,
+ size_t normal_response_len, const uint8_t* request,
+ size_t request_len) = 0;
+
+ protected:
+ uint16_t probability_1024_ = 0;
+};
+
+} // namespace roughtime
+
+#endif // SECURITY_ROUGHTIME_SERVER_H_
diff --git a/server_test.cc b/server_test.cc
new file mode 100644
index 0000000..aad38c5
--- /dev/null
+++ b/server_test.cc
@@ -0,0 +1,294 @@
+/* Copyright 2016 The Roughtime Authors.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License. */
+
+#include <string.h>
+#include <sys/types.h>
+#include <unistd.h>
+
+#include "gtest/gtest.h"
+#include <openssl/curve25519.h>
+#include <openssl/rand.h>
+
+#include "open_source_fillins.h"
+#include "server.h"
+
+namespace roughtime {
+
+TEST(CreateCertificate, Create) {
+ uint8_t delegated_private_key[ED25519_PRIVATE_KEY_LEN]; // Not used.
+ uint8_t delegated_public_key[ED25519_PUBLIC_KEY_LEN];
+ uint8_t root_private_key[ED25519_PRIVATE_KEY_LEN];
+ uint8_t root_public_key[ED25519_PUBLIC_KEY_LEN];
+ ED25519_keypair(delegated_public_key, delegated_private_key);
+ ED25519_keypair(root_public_key, root_private_key);
+
+ uint8_t cert[kCertSize];
+ EXPECT_TRUE(
+ CreateCertificate(cert, root_private_key, 0, 1, delegated_public_key));
+ Parser cert_parser(cert, sizeof(cert));
+ const uint8_t* delegation;
+ const uint8_t* signature;
+ EXPECT_TRUE(
+ cert_parser.GetFixedLen(&delegation, kTagDELE, kToBeSignedCertSize));
+ EXPECT_TRUE(
+ cert_parser.GetFixedLen(&signature, kTagSIG, ED25519_SIGNATURE_LEN));
+
+ Parser delegation_parser(delegation, kToBeSignedCertSize);
+ uint64_t mint, maxt;
+ const uint8_t* pubk;
+ EXPECT_TRUE(delegation_parser.Get(&mint, kTagMINT));
+ EXPECT_TRUE(delegation_parser.Get(&maxt, kTagMAXT));
+ EXPECT_TRUE(
+ delegation_parser.GetFixedLen(&pubk, kTagPUBK, ED25519_PUBLIC_KEY_LEN));
+ EXPECT_EQ(0, mint);
+ EXPECT_EQ(1, maxt);
+ EXPECT_EQ(0,
+ memcmp(pubk, delegated_public_key, sizeof(delegated_public_key)));
+
+ uint8_t verify[sizeof(kCertContextString) + kToBeSignedCertSize];
+ memcpy(verify, kCertContextString, sizeof(kCertContextString));
+ memcpy(verify + sizeof(kCertContextString), delegation, kToBeSignedCertSize);
+ EXPECT_TRUE(
+ ED25519_verify(verify, sizeof(verify), signature, root_public_key));
+}
+
+TEST(Tree, OneNode) {
+ std::unique_ptr<Tree> tree(new Tree);
+ uint8_t nonce[kNonceLength];
+ RAND_bytes(nonce, sizeof(nonce));
+ tree->AddLeaf(0, nonce);
+ tree->Build(1);
+
+ uint8_t hash[kNonceLength];
+ HashLeaf(hash, nonce);
+ EXPECT_EQ(0, memcmp(hash, tree->GetRoot(), kNonceLength));
+ EXPECT_EQ(0, tree->GetPathLength());
+}
+
+TEST(Tree, ManyNodes) {
+ std::unique_ptr<Tree> tree(new Tree);
+ size_t sizes[] = {2, 3, 4, 5, 6, kBatchSize - 1, kBatchSize};
+ for (size_t i = 0; i < arraysize(sizes); i++) {
+ size_t size = sizes[i];
+ uint8_t nonces[kBatchSize][kNonceLength];
+ for (size_t j = 0; j < size; ++j) {
+ RAND_bytes(nonces[j], sizeof(nonces[j]));
+ tree->AddLeaf(j, nonces[j]);
+ }
+ tree->Build(size);
+
+ // Verify the inclusion of each nonce.
+ for (size_t j = 0; j < size; ++j) {
+ uint8_t hash[kNonceLength];
+ HashLeaf(hash, nonces[j]);
+
+ uint8_t path[kBatchSize][kNonceLength];
+ tree->GetPath(reinterpret_cast<uint8_t*>(path), j);
+ size_t index = j;
+ for (size_t elem = 0; elem < tree->GetPathLength(); elem++) {
+ if (index % 2 == 0) {
+ HashNode(hash, hash, path[elem]);
+ } else {
+ HashNode(hash, path[elem], hash);
+ }
+ index /= 2;
+ }
+ ASSERT_EQ(0, index);
+ EXPECT_EQ(0, memcmp(hash, tree->GetRoot(), kNonceLength));
+ }
+ }
+}
+
+class DummyTimeSource : public TimeSource {
+ public:
+ ~DummyTimeSource() override {}
+ std::pair<uint64_t, uint32_t> Now() override {
+ return std::make_pair(1000000000, 0);
+ }
+};
+
+// MakeServer is a helper function to create a new server. The server's public
+// key is written to |*root_public_key|, but its certificate remains hidden.
+static std::unique_ptr<Server> MakeServer(uint8_t* root_public_key) {
+ auto identity = std::unique_ptr<Identity>(new Identity());
+ uint8_t delegated_private_key[ED25519_PRIVATE_KEY_LEN]; // Not used.
+ uint8_t delegated_public_key[ED25519_PUBLIC_KEY_LEN];
+ uint8_t root_private_key[ED25519_PRIVATE_KEY_LEN];
+ ED25519_keypair(delegated_public_key, delegated_private_key);
+ ED25519_keypair(root_public_key, root_private_key);
+ CreateCertificate(identity->certificate, root_private_key, 1000000000,
+ 2000000000 /* 2033-05-17 */, delegated_public_key);
+ memcpy(identity->private_key, delegated_private_key,
+ sizeof(delegated_private_key));
+ std::unique_ptr<TimeSource> time_source(new DummyTimeSource);
+ Server* server = new Server(std::move(identity), std::move(time_source));
+ return std::unique_ptr<Server>(server);
+}
+
+// VerifyResponse is a helper function to verify a that the supplied |response|
+// is valid and includes the supplied |nonce|.
+static void VerifyResponse(const uint8_t* nonce, const uint8_t* response,
+ size_t len) {
+ // Parse the top-level response.
+ Parser parser(response, len);
+ ASSERT_TRUE(parser.is_valid());
+ uint8_t to_be_verified_with_context[kToBeSignedSize + sizeof(kContextString)];
+ const uint8_t* to_be_verified;
+ const uint8_t* signature;
+ const uint8_t* cert;
+ const uint8_t* path;
+ uint32_t index;
+ size_t path_len;
+ size_t path_elems;
+ ASSERT_TRUE(parser.GetFixedLen(&to_be_verified, kTagSREP, kToBeSignedSize));
+ ASSERT_TRUE(parser.GetFixedLen(&signature, kTagSIG, ED25519_SIGNATURE_LEN));
+ ASSERT_TRUE(parser.GetFixedLen(&cert, kTagCERT, kCertSize));
+ ASSERT_TRUE(parser.Get(&index, kTagINDX));
+ ASSERT_TRUE(parser.GetTag(&path, &path_len, kTagPATH));
+
+ // Parse the signed portion.
+ Parser srep_parser(to_be_verified, kToBeSignedSize);
+ ASSERT_TRUE(srep_parser.is_valid());
+ const uint8_t* root;
+ uint64_t time;
+ ASSERT_TRUE(srep_parser.GetFixedLen(&root, kTagROOT, kNonceLength));
+ ASSERT_TRUE(srep_parser.Get(&time, kTagMIDP));
+
+ // Parse the certificate.
+ Parser cert_parser(cert, kCertSize);
+ ASSERT_TRUE(cert_parser.is_valid());
+ const uint8_t* delegation;
+ ASSERT_TRUE(
+ cert_parser.GetFixedLen(&delegation, kTagDELE, kToBeSignedCertSize));
+
+ // Parse the delegation.
+ Parser delegation_parser(delegation, kToBeSignedCertSize);
+ ASSERT_TRUE(delegation_parser.is_valid());
+ const uint8_t* public_key;
+ uint64_t maxt, mint;
+ ASSERT_TRUE(delegation_parser.GetFixedLen(&public_key, kTagPUBK,
+ ED25519_PUBLIC_KEY_LEN));
+ ASSERT_TRUE(delegation_parser.Get(&mint, kTagMINT));
+ ASSERT_TRUE(delegation_parser.Get(&maxt, kTagMAXT));
+
+ // Verify that delegation is valid for the supplied time.
+ EXPECT_GE(time, mint);
+ EXPECT_LE(time, maxt);
+
+ // Verify the signature.
+ memcpy(to_be_verified_with_context, kContextString, sizeof(kContextString));
+ memcpy(to_be_verified_with_context + sizeof(kContextString), to_be_verified,
+ kToBeSignedSize);
+ EXPECT_TRUE(ED25519_verify(to_be_verified_with_context,
+ sizeof(to_be_verified_with_context), signature,
+ public_key));
+
+ // Verify the inclusion of |nonce|.
+ ASSERT_EQ(0, path_len % kNonceLength);
+ path_elems = path_len / kNonceLength;
+ uint8_t hash[kNonceLength];
+ HashLeaf(hash, nonce);
+ for (size_t i = 0; i < path_elems; i++) {
+ if (index % 2 == 1) {
+ HashNode(hash, path, hash);
+ } else {
+ HashNode(hash, hash, path);
+ }
+ path += kNonceLength;
+ index /= 2;
+ }
+ EXPECT_EQ(0, memcmp(hash, root, kNonceLength));
+}
+
+// MakeRequest, a helper function, writes a new client request with the given
+// |nonce| to |*request|.
+void MakeRequest(uint8_t* request, uint8_t* nonce) {
+ Builder builder(request, kMinRequestSize, 2);
+ RAND_bytes(nonce, sizeof(nonce));
+ ASSERT_TRUE(builder.AddTagData(kTagNONC, nonce, kNonceLength));
+ uint8_t* padding;
+ ASSERT_TRUE(builder.AddTag(&padding, kTagPAD, kPaddingLen));
+ size_t len;
+ ASSERT_TRUE(builder.Finish(&len));
+ ASSERT_EQ(kMinRequestSize, len);
+}
+
+TEST(Server, BadRequest) {
+ uint8_t root_public_key[ED25519_PUBLIC_KEY_LEN];
+ auto server = MakeServer(root_public_key);
+ uint8_t garbage[kMinRequestSize];
+ memset(garbage, 'a', sizeof(garbage));
+ EXPECT_FALSE(server->AddRequest(garbage, sizeof(garbage)));
+}
+
+TEST(Server, GoodRequests) {
+ uint8_t root_public_key[ED25519_PUBLIC_KEY_LEN];
+ auto server = MakeServer(root_public_key);
+
+ size_t batch_sizes[] = {1, 2, 3, 4, 5, 6, kBatchSize - 1, kBatchSize};
+ for (size_t i = 0; i < arraysize(batch_sizes); ++i) {
+ std::unique_ptr<uint8_t[]> requests(
+ new uint8_t[kBatchSize * kMinRequestSize]);
+ std::unique_ptr<uint8_t[]> nonces(new uint8_t[kBatchSize * kNonceLength]);
+ memset(nonces.get(), 0, kBatchSize * kNonceLength);
+ for (size_t j = 0; j < batch_sizes[i]; ++j) {
+ MakeRequest(&requests[j * kMinRequestSize], &nonces[j * kNonceLength]);
+ EXPECT_TRUE(
+ server->AddRequest(&requests[j * kMinRequestSize], kMinRequestSize));
+ }
+ EXPECT_TRUE(server->Sign());
+
+ for (size_t j = 0; j < batch_sizes[i]; ++j) {
+ uint8_t response[kMaxResponseSize];
+ size_t response_len;
+ EXPECT_TRUE(server->MakeResponse(response, &response_len, j));
+ VerifyResponse(&nonces[j * kNonceLength], response, response_len);
+ }
+ server->Reset();
+ }
+}
+
+TEST(Server, MixedGoodAndBadRequests) {
+ uint8_t root_public_key[ED25519_PUBLIC_KEY_LEN];
+ auto server = MakeServer(root_public_key);
+
+ std::unique_ptr<uint8_t[]> requests(
+ new uint8_t[kBatchSize * kMinRequestSize]);
+ std::unique_ptr<uint8_t[]> nonces(new uint8_t[kBatchSize * kNonceLength]);
+ memset(nonces.get(), 0, kBatchSize * kNonceLength);
+
+ MakeRequest(&requests[0 * kMinRequestSize], &nonces[0 * kNonceLength]);
+ MakeRequest(&requests[1 * kMinRequestSize], &nonces[1 * kNonceLength]);
+ MakeRequest(&requests[2 * kMinRequestSize], &nonces[2 * kNonceLength]);
+ memset(&requests[1 * kMinRequestSize], 'a', kMinRequestSize);
+
+ EXPECT_TRUE(
+ server->AddRequest(&requests[0 * kMinRequestSize], kMinRequestSize));
+ EXPECT_FALSE(
+ server->AddRequest(&requests[1 * kMinRequestSize], kMinRequestSize));
+ EXPECT_TRUE(
+ server->AddRequest(&requests[2 * kMinRequestSize], kMinRequestSize));
+ server->Sign();
+
+ uint8_t response[kMaxResponseSize];
+ size_t response_len;
+
+ EXPECT_TRUE(server->MakeResponse(response, &response_len, 0));
+ VerifyResponse(&nonces[0 * kNonceLength], response, response_len);
+ EXPECT_TRUE(server->MakeResponse(response, &response_len, 1));
+ // index #1 -> nonce #2
+ VerifyResponse(&nonces[2 * kNonceLength], response, response_len);
+}
+
+} // namespace roughtime
diff --git a/simple_client.cc b/simple_client.cc
new file mode 100644
index 0000000..145227a
--- /dev/null
+++ b/simple_client.cc
@@ -0,0 +1,303 @@
+/* Copyright 2016 The Roughtime Authors.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License. */
+
+// simple_client is the most basic Roughtime client possible. Given a filename
+// containing a servers list as the sole argument it prints the time obtained
+// from a single server and the offset from the current system clock.
+
+#include <arpa/inet.h>
+#include <assert.h>
+#include <errno.h>
+#include <inttypes.h>
+#include <netdb.h>
+#include <netinet/udp.h>
+#include <sys/socket.h>
+#include <sys/types.h>
+#include <unistd.h>
+
+#include <string>
+
+#include <google/protobuf/stubs/status.h>
+#include <google/protobuf/util/json_util.h>
+#include <openssl/rand.h>
+
+#include "client.h"
+#include "config.pb.h"
+#include "protocol.h"
+
+// kTimeoutSeconds is the number of seconds that we will wait for a reply
+// from the server.
+static const int kTimeoutSeconds = 3;
+
+namespace roughtime {
+
+// MonotonicUs returns the value of the monotonic clock in microseconds.
+uint64_t MonotonicUs();
+
+// MonotonicUs returns the value of the realtime clock in microseconds.
+uint64_t RealtimeUs();
+
+// GetUsableServer parses the JSON-encoded server information from
+// |servers_contents| and looks for the first server with an Ed25519 public key
+// and UDP address. If it finds one, it sets |*out_name|, |*out_address| and
+// |*out_public_key| and returns true. Otherwise it returns false.
+static bool GetUsableServer(std::string* out_name, std::string* out_address,
+ std::string* out_public_key,
+ const std::string& servers_contents) {
+ config::ServersJSON servers;
+ google::protobuf::util::Status status =
+ google::protobuf::util::JsonStringToMessage(servers_contents, &servers);
+ if (!status.ok()) {
+ std::string error_message(status.error_message().data(),
+ status.error_message().size());
+ fprintf(stderr, "Failed to parse servers JSON: %s\n",
+ error_message.c_str());
+ return false;
+ }
+
+ for (int i = 0; i < servers.servers_size(); i++) {
+ const config::Server& server = servers.servers(i);
+
+ if (server.public_key_type() != "ed25519") {
+ continue;
+ }
+
+ for (int j = 0; j < server.addresses_size(); j++) {
+ const config::ServerAddress& address = server.addresses(j);
+
+ if (address.protocol() != "udp") {
+ continue;
+ }
+
+ *out_name = server.name();
+ *out_address = address.address();
+ *out_public_key = server.public_key();
+ return true;
+ }
+ }
+
+ fprintf(stderr, "Failed to find any usable servers.\n");
+ return false;
+}
+
+} // namespace roughtime
+
+// ReadServersFile reads the contents of |filename| and sets |*out_contents| to
+// contain them. It returns true on success and false on error.
+static bool ReadServersFile(std::string* out_contents, const char* filename) {
+ FILE* servers_file = fopen(filename, "r");
+ if (servers_file == nullptr) {
+ fprintf(stderr, "Failed to open JSON servers file.\n");
+ return false;
+ }
+
+ if (fseek(servers_file, 0, SEEK_END) != 0) {
+ fprintf(stderr, "Failed to seek within JSON servers file.\n");
+ fclose(servers_file);
+ return false;
+ }
+
+ const long length = ftell(servers_file); // NOLINT
+ if (length < 0) {
+ fprintf(stderr, "Failed to get offset within JSON servers file.\n");
+ fclose(servers_file);
+ return false;
+ }
+
+ if (fseek(servers_file, 0, SEEK_SET) != 0) {
+ fprintf(stderr, "Failed to seek within JSON servers file.\n");
+ fclose(servers_file);
+ return false;
+ }
+
+ std::unique_ptr<uint8_t[]> buf(new uint8_t[length]);
+ if (fread(buf.get(), static_cast<size_t>(length), 1, servers_file) != 1) {
+ fprintf(stderr, "Failed to read JSON servers file.\n");
+ fclose(servers_file);
+ return false;
+ }
+
+ fclose(servers_file);
+ out_contents->assign(reinterpret_cast<const char*>(buf.get()), length);
+ return true;
+}
+
+// CreateSocket resolves the given address (which must be of the form
+// "host:port") and sets |*out_socket| to reference a fresh socket connected to
+// that address. It returns true on success and false on error.
+static bool CreateSocket(int* out_socket, const std::string& address) {
+ const size_t colon_offset = address.rfind(':');
+ if (colon_offset == std::string::npos) {
+ fprintf(stderr, "No port number in server address: %s\n", address.c_str());
+ return false;
+ }
+ std::string host(address.substr(0, colon_offset));
+ const std::string port_str(address.substr(colon_offset + 1));
+
+ struct addrinfo hints;
+ memset(&hints, 0, sizeof(hints));
+ hints.ai_socktype = SOCK_DGRAM;
+ hints.ai_protocol = IPPROTO_UDP;
+ hints.ai_flags = AI_NUMERICSERV;
+
+ if (!host.empty() && host[0] == '[' && host[host.size() - 1] == ']') {
+ host = host.substr(1, host.size() - 1);
+ hints.ai_family = AF_INET6;
+ hints.ai_flags |= AI_NUMERICHOST;
+ }
+
+ struct addrinfo* addrs;
+ int r = getaddrinfo(host.c_str(), port_str.c_str(), &hints, &addrs);
+ if (r != 0) {
+ fprintf(stderr, "Failed to resolve %s: %s", address.c_str(),
+ gai_strerror(r));
+ return false;
+ }
+
+ int sock = socket(addrs->ai_family, addrs->ai_socktype, addrs->ai_protocol);
+ if (sock < 0) {
+ perror("Failed to create UDP socket");
+ freeaddrinfo(addrs);
+ return false;
+ }
+
+ if (connect(sock, addrs->ai_addr, addrs->ai_addrlen)) {
+ perror("Failed to connect UDP socket");
+ freeaddrinfo(addrs);
+ close(sock);
+ return false;
+ }
+
+ char dest_str[INET6_ADDRSTRLEN];
+ r = getnameinfo(addrs->ai_addr, addrs->ai_addrlen, dest_str, sizeof(dest_str),
+ NULL /* don't want port information */, 0, NI_NUMERICHOST);
+ freeaddrinfo(addrs);
+
+ if (r != 0) {
+ fprintf(stderr, "getnameinfo: %s", gai_strerror(r));
+ close(sock);
+ return false;
+ }
+
+ printf("Sending request to %s, port %s.\n", dest_str, port_str.c_str());
+ *out_socket = sock;
+ return true;
+}
+
+enum ExitCode {
+ kExitBadSystemTime = 1,
+ kExitBadArguments = 2,
+ kExitNoServer = 3,
+ kExitNetworkError = 4,
+ kExitTimeout = 5,
+ kExitBadReply = 6,
+};
+
+int main(int argc, char** argv) {
+ if (argc != 2) {
+ fprintf(stderr, "Usage: %s <roughtime-servers.json>\n", argv[0]);
+ return kExitBadArguments;
+ }
+
+ std::string servers_contents;
+ if (!ReadServersFile(&servers_contents, argv[1])) {
+ return kExitBadArguments;
+ }
+
+ std::string name, address, public_key;
+ if (!roughtime::GetUsableServer(&name, &address, &public_key,
+ servers_contents)) {
+ return kExitNoServer;
+ }
+
+ int fd = 0;
+ if (!CreateSocket(&fd, address)) {
+ return kExitNetworkError;
+ }
+
+ uint8_t nonce[roughtime::kNonceLength];
+ RAND_bytes(nonce, sizeof(nonce));
+ const std::string request = roughtime::CreateRequest(nonce);
+
+ struct timeval timeout;
+ timeout.tv_sec = kTimeoutSeconds;
+ timeout.tv_usec = 0;
+ setsockopt(fd, SOL_SOCKET, SO_RCVTIMEO, &timeout, sizeof(timeout));
+
+ ssize_t r;
+ do {
+ r = send(fd, request.data(), request.size(), 0 /* flags */);
+ } while (r == -1 && errno == EINTR);
+ const uint64_t start_us = roughtime::MonotonicUs();
+
+ if (r < 0 || static_cast<size_t>(r) != request.size()) {
+ perror("send on UDP socket");
+ close(fd);
+ return kExitNetworkError;
+ }
+
+ uint8_t recv_buf[roughtime::kMinRequestSize];
+ ssize_t buf_len;
+ do {
+ buf_len = recv(fd, recv_buf, sizeof(recv_buf), 0 /* flags */);
+ } while (buf_len == -1 && errno == EINTR);
+
+ const uint64_t end_us = roughtime::MonotonicUs();
+ const uint64_t end_realtime_us = roughtime::RealtimeUs();
+
+ close(fd);
+
+ if (buf_len == -1) {
+ if (errno == EINTR) {
+ fprintf(stderr, "No response from %s with %d seconds.\n", name.c_str(),
+ kTimeoutSeconds);
+ return kExitTimeout;
+ }
+
+ perror("recv from UDP socket");
+ return kExitNetworkError;
+ }
+
+ uint64_t timestamp;
+ uint32_t radius;
+ std::string error;
+ if (!roughtime::ParseResponse(
+ ×tamp, &radius, &error,
+ reinterpret_cast<const uint8_t*>(public_key.data()), recv_buf,
+ buf_len, nonce)) {
+ fprintf(stderr, "Response from %s failed verification: %s", name.c_str(),
+ error.c_str());
+ return kExitBadReply;
+ }
+
+ // We assume that the path to the Roughtime server is symmetric and thus add
+ // half the round-trip time to the server's timestamp to produce our estimate
+ // of the current time.
+ timestamp += (end_us - start_us) / 2;
+
+ printf("Received reply in %" PRIu64 "μs.\n", end_us - start_us);
+ printf("Current time is %" PRIu64 "μs from the epoch, ±%uμs \n", timestamp,
+ static_cast<unsigned>(radius));
+ int64_t system_offset =
+ static_cast<int64_t>(timestamp) - static_cast<int64_t>(end_realtime_us);
+ printf("System clock differs from that estimate by %" PRId64 "μs.\n",
+ system_offset);
+
+ static const int64_t kTenMinutes = 10 * 60 * 1000000;
+ if (imaxabs(system_offset) > kTenMinutes) {
+ return kExitBadSystemTime;
+ }
+
+ return 0;
+}
diff --git a/simple_server.cc b/simple_server.cc
new file mode 100644
index 0000000..c0c2261
--- /dev/null
+++ b/simple_server.cc
@@ -0,0 +1,56 @@
+/* Copyright 2016 The Roughtime Authors.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License. */
+
+#include "simple_server.h"
+
+#include <google/protobuf/stubs/logging.h>
+#include <openssl/curve25519.h>
+
+#include "server.h"
+
+namespace roughtime {
+
+SimpleServer::SimpleServer(std::unique_ptr<Identity> identity,
+ std::unique_ptr<TimeSource> time_source, int fd)
+ : fd_(fd), server_(std::move(identity), std::move(time_source)) {}
+
+bool SimpleServer::ProcessBatch() {
+ UdpProcessor::Stats stats;
+ return udp_processor_.ProcessBatch(fd_, &server_, &stats);
+}
+
+void SimpleServer::RunUntilError() {
+ UdpProcessor::Stats stats;
+ while (udp_processor_.ProcessBatch(fd_, &server_, &stats)) {
+ }
+}
+
+// static
+std::unique_ptr<Identity> SimpleServer::MakeIdentity(
+ const uint8_t root_private_key[ED25519_PRIVATE_KEY_LEN], uint64_t mint,
+ uint64_t maxt) {
+ GOOGLE_CHECK(mint <= maxt);
+ uint8_t delegated_private_key[ED25519_PRIVATE_KEY_LEN];
+ uint8_t delegated_public_key[ED25519_PUBLIC_KEY_LEN];
+ ED25519_keypair(delegated_public_key, delegated_private_key);
+
+ auto identity = std::unique_ptr<Identity>(new Identity());
+ CreateCertificate(identity->certificate, root_private_key, mint, maxt,
+ delegated_public_key);
+ memcpy(identity->private_key, delegated_private_key,
+ sizeof(delegated_private_key));
+ return identity;
+}
+
+} // namespace roughtime
diff --git a/simple_server.h b/simple_server.h
new file mode 100644
index 0000000..159e7ff
--- /dev/null
+++ b/simple_server.h
@@ -0,0 +1,61 @@
+/* Copyright 2016 The Roughtime Authors.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License. */
+
+#ifndef SECURITY_ROUGHTIME_SIMPLE_SERVER_H_
+#define SECURITY_ROUGHTIME_SIMPLE_SERVER_H_
+
+#include <arpa/inet.h>
+#include <netinet/in.h>
+
+#include "server.h"
+#include "time_source.h"
+#include "udp_processor.h"
+
+namespace roughtime {
+
+// SimpleServer wraps |Server| with enough intelligence to read requests from,
+// and write requests to, a supplied socket. There's no reason in principle
+// that one couldn't run multiple instances per socket.
+//
+// This class exists for testing and to provide an example rather than as a
+// basis for a production-quality server.
+class SimpleServer {
+ public:
+ // |identity| is the server's certificate. |fd| is the socket to be used to
+ // receive requests and send responses.
+ SimpleServer(std::unique_ptr<Identity> identity,
+ std::unique_ptr<TimeSource> time_source, int fd);
+
+ // RunUntilError receives and responds to a batches of requests until an
+ // unexpected error occurs.
+ void RunUntilError();
+
+ // ProcessBatch calls UdpProcessor::ProcessBatch.
+ bool ProcessBatch();
+
+ // MakeIdentity creates a dummy server certificate that is valid for the
+ // given time range.
+ static std::unique_ptr<Identity> MakeIdentity(
+ const uint8_t root_private_key[ED25519_PRIVATE_KEY_LEN], uint64_t mint,
+ uint64_t maxt);
+
+ private:
+ const int fd_;
+ Server server_;
+ UdpProcessor udp_processor_;
+};
+
+} // namespace roughtime
+
+#endif // SECURITY_ROUGHTIME_SIMPLE_SERVER_H_
diff --git a/simple_server_main.cc b/simple_server_main.cc
new file mode 100644
index 0000000..bc3002a
--- /dev/null
+++ b/simple_server_main.cc
@@ -0,0 +1,70 @@
+/* Copyright 2016 The Roughtime Authors.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License. */
+
+#include <arpa/inet.h>
+#include <netinet/in.h>
+#include <stdlib.h>
+#include <sys/socket.h>
+#include <sys/types.h>
+#include <unistd.h>
+
+#include "simple_server.h"
+#include "sys_time.h"
+
+// root_private_key is an Ed25519 private key used by simple_server. The
+// private part consists of all zeros and so is only for use in this example.
+constexpr uint8_t root_private_key[ED25519_PRIVATE_KEY_LEN] = {
+ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x3b, 0x6a, 0x27, 0xbc,
+ 0xce, 0xb6, 0xa4, 0x2d, 0x62, 0xa3, 0xa8, 0xd0, 0x2a, 0x6f, 0x0d, 0x73,
+ 0x65, 0x32, 0x15, 0x77, 0x1d, 0xe2, 0x43, 0xa6, 0x3a, 0xc0, 0x48, 0xa1,
+ 0x8b, 0x59, 0xda, 0x29,
+};
+
+int main(int argc, char **argv) {
+ int requested_port = -1;
+
+ if (argc == 2) {
+ char *endptr;
+ requested_port = strtoul(argv[1], &endptr, 10);
+ if (*endptr != 0) {
+ requested_port = -1;
+ }
+ }
+
+ if (requested_port < 0 || requested_port > 65535) {
+ fprintf(stderr, "Usage: %s <port number>\n", argv[0]);
+ return 1;
+ }
+
+ int fd;
+ uint16_t port;
+ if (!roughtime::UdpProcessor::MakeSocket(requested_port, &fd, &port)) {
+ return 1;
+ }
+
+ fprintf(stderr, "Listening on port %d.\n", port);
+
+ std::unique_ptr<roughtime::Identity> identity =
+ roughtime::SimpleServer::MakeIdentity(root_private_key, 0,
+ 2147483647000000);
+ std::unique_ptr<TimeSource> time_source(new roughtime::SystemTimeSource);
+
+ auto server =
+ std::unique_ptr<roughtime::SimpleServer>(new roughtime::SimpleServer(
+ std::move(identity), std::move(time_source), fd));
+ server->RunUntilError();
+ return 1;
+}
diff --git a/sys_time.cc b/sys_time.cc
new file mode 100644
index 0000000..b0eca57
--- /dev/null
+++ b/sys_time.cc
@@ -0,0 +1,37 @@
+/* Copyright 2016 The Roughtime Authors.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License. */
+
+#include "sys_time.h"
+
+#include <time.h>
+
+#include <google/protobuf/stubs/logging.h>
+
+namespace roughtime {
+
+SystemTimeSource::SystemTimeSource() {}
+
+SystemTimeSource::~SystemTimeSource() {}
+
+std::pair<uint64_t, uint32_t> SystemTimeSource::Now() {
+ struct timespec ts;
+ GOOGLE_CHECK_EQ(0, clock_gettime(CLOCK_REALTIME_COARSE, &ts));
+ uint64_t now = ts.tv_sec;
+ now *= 1000000;
+ now += ts.tv_nsec / 1000;
+
+ return std::make_pair(now, 1000000);
+}
+
+} // namespace roughtime
diff --git a/sys_time.h b/sys_time.h
new file mode 100644
index 0000000..ad3c513
--- /dev/null
+++ b/sys_time.h
@@ -0,0 +1,39 @@
+/* Copyright 2016 The Roughtime Authors.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License. */
+
+#ifndef SECURITY_ROUGHTIME_SYS_TIME_H_
+#define SECURITY_ROUGHTIME_SYS_TIME_H_
+
+#include <stdint.h>
+
+#include "time_source.h"
+
+namespace roughtime {
+
+// SystemTimeSource uses gettimeofday to provide the current time and has a
+// fixed uncertainly of one second. Roughtime defines time to include smeared
+// leap seconds but it's unlikely that the system clock respects that. Thus
+// the radius is meant to reflect that and this time source is only provided as
+// an example.
+class SystemTimeSource : public TimeSource {
+ public:
+ SystemTimeSource();
+ ~SystemTimeSource() override;
+
+ std::pair<uint64_t, uint32_t> Now() override;
+};
+
+} // namespace roughtime
+
+#endif // SECURITY_ROUGHTIME_SYS_TIME_H_
diff --git a/time_source.h b/time_source.h
new file mode 100644
index 0000000..929faaa
--- /dev/null
+++ b/time_source.h
@@ -0,0 +1,32 @@
+/* Copyright 2016 The Roughtime Authors.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License. */
+
+#ifndef SECURITY_ROUGHTIME_TIME_SOURCE_H_
+#define SECURITY_ROUGHTIME_TIME_SOURCE_H_
+
+#include <stdint.h>
+
+#include <utility>
+
+// TimeSource is an interface that can provide the current time.
+class TimeSource {
+ public:
+ virtual ~TimeSource() {}
+
+ // Now returns the midpoint time in epoch-microseconds and a radius of
+ // uncertainty.
+ virtual std::pair<uint64_t, uint32_t> Now() = 0;
+};
+
+#endif // SECURITY_ROUGHTIME_TIME_SOURCE_H_
diff --git a/udp_processor.cc b/udp_processor.cc
new file mode 100644
index 0000000..6d8cbb4
--- /dev/null
+++ b/udp_processor.cc
@@ -0,0 +1,221 @@
+/* Copyright 2016 The Roughtime Authors.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License. */
+
+#include "udp_processor.h"
+
+#include <fcntl.h>
+#include <unistd.h>
+
+#include <google/protobuf/stubs/logging.h>
+
+#include "open_source_fillins.h"
+
+namespace roughtime {
+
+UdpProcessor::UdpProcessor() {
+ // These never change. We can set them up just once and reuse them forever.
+ memset(recv_mmsghdrs_, 0, sizeof(recv_mmsghdrs_));
+ for (size_t i = 0; i < kBatchSize; i++) {
+ recv_iov_[i].iov_base = recv_buf_[i];
+ recv_iov_[i].iov_len = sizeof(recv_buf_[i]);
+ recv_mmsghdrs_[i].msg_hdr.msg_name = &sockaddrs_[i];
+ recv_mmsghdrs_[i].msg_hdr.msg_namelen = sizeof(struct sockaddr_storage);
+ recv_mmsghdrs_[i].msg_hdr.msg_iov = &recv_iov_[i];
+ recv_mmsghdrs_[i].msg_hdr.msg_iovlen = 1;
+ }
+
+ memset(send_mmsghdrs_, 0, sizeof(send_mmsghdrs_));
+ for (size_t i = 0; i < kBatchSize; i++) {
+ send_iov_[i].iov_base = send_buf_[i];
+ send_mmsghdrs_[i].msg_hdr.msg_iov = &send_iov_[i];
+ send_mmsghdrs_[i].msg_hdr.msg_iovlen = 1;
+ // iov_len varies per batch, as does msg_name.
+ }
+}
+
+UdpProcessor::~UdpProcessor() {}
+
+bool UdpProcessor::AddBrokenReplyGenerator(
+ std::unique_ptr<BrokenReplyGenerator> broken_reply_generator) {
+ const uint16_t new_sum =
+ broken_reply_generator_sum_ + broken_reply_generator->probability_1024();
+ if (new_sum > 1024) {
+ return false;
+ }
+
+ broken_reply_generator_sum_ = new_sum;
+ broken_reply_generators_.push_back(std::move(broken_reply_generator));
+
+ return true;
+}
+
+// static
+bool UdpProcessor::MakeSocket(int port, int *out_sock, uint16_t *out_port) {
+ *out_sock = -1;
+ *out_port = 0;
+
+ const int fd = socket(AF_INET6, SOCK_DGRAM, 0);
+ if (fd == -1) {
+ GOOGLE_PLOG(ERROR) << "socket";
+ return false;
+ }
+
+ struct sockaddr_in6 sin6;
+ memset(&sin6, 0, sizeof(sin6));
+ sin6.sin6_family = AF_INET6;
+ sin6.sin6_addr = in6addr_any;
+ sin6.sin6_port = htons(port);
+ if (bind(fd, reinterpret_cast<sockaddr *>(&sin6), sizeof(sin6))) {
+ GOOGLE_PLOG(ERROR) << "bind";
+ close(fd);
+ return false;
+ }
+
+ socklen_t sin6_len = sizeof(sin6);
+ if (getsockname(fd, reinterpret_cast<sockaddr *>(&sin6), &sin6_len)) {
+ GOOGLE_PLOG(ERROR) << "getsockname";
+ close(fd);
+ return false;
+ }
+
+ *out_sock = fd;
+ *out_port = ntohs(sin6.sin6_port);
+ return true;
+}
+
+void UdpProcessor::PrepareResponse(struct msghdr *out_send_header,
+ const struct msghdr &recv_header) {
+ out_send_header->msg_name = recv_header.msg_name;
+ out_send_header->msg_namelen = recv_header.msg_namelen;
+}
+
+void UdpProcessor::Reset() {
+ // Clear out the addresses from last time. (Without this |recvmmsg| thinks
+ // we are trying to receive from these addresses.)
+ memset(sockaddrs_, 0, sizeof(sockaddrs_));
+ for (size_t i = 0; i < kBatchSize; i++) {
+ recv_mmsghdrs_[i].msg_hdr.msg_flags = 0;
+ recv_mmsghdrs_[i].msg_hdr.msg_namelen = sizeof(struct sockaddr_storage);
+ }
+}
+
+bool UdpProcessor::ProcessBatch(int fd, Server *server, Stats *out_stats) {
+ server->Reset();
+ memset(out_stats, 0, sizeof(Stats));
+ Reset();
+
+ int r;
+ do {
+ r = recvmmsg(fd, recv_mmsghdrs_, kBatchSize, MSG_WAITFORONE,
+ nullptr /* timeout */);
+ } while (r == -1 && errno == EINTR);
+
+ if (r < 0) {
+ GOOGLE_PLOG(ERROR) << "recvmmsg";
+ return false;
+ } else if (r == 0) {
+ return true;
+ }
+
+ out_stats->packets_in = r;
+
+ size_t index = 0;
+ for (size_t i = 0; i < static_cast<size_t>(r); i++) {
+ const msghdr *recv_header = &recv_mmsghdrs_[i].msg_hdr;
+ out_stats->bytes_in += recv_mmsghdrs_[i].msg_len;
+ if ((recv_header->msg_flags & (MSG_CTRUNC | MSG_TRUNC)) != 0) {
+ out_stats->requests_truncated++;
+ continue;
+ }
+ if (!server->AddRequest(recv_buf_[i], recv_mmsghdrs_[i].msg_len)) {
+ out_stats->requests_invalid++;
+ continue;
+ }
+
+ // Fill in the destination address for this response. The data and its
+ // length will be set below.
+ msghdr *send_header = &send_mmsghdrs_[index].msg_hdr;
+ PrepareResponse(send_header, *recv_header);
+ index++;
+ }
+
+ if (index == 0) {
+ return true;
+ }
+
+ server->Sign();
+
+ out_stats->packets_out = index;
+ for (size_t i = 0; i < index; i++) {
+ size_t reply_len;
+ if (!server->MakeResponse(send_buf_[i], &reply_len, i)) {
+ GOOGLE_LOG(ERROR) << "failed to assemble responses";
+ return false;
+ }
+ requests_processed_++;
+
+ uint8_t broken_output_buf[kMaxResponseSize];
+ if (MaybeBreakResponse(broken_output_buf, &reply_len,
+ sizeof(broken_output_buf), send_buf_[i], reply_len,
+ recv_buf_[i], recv_mmsghdrs_[i].msg_len)) {
+ GOOGLE_DCHECK_LE(reply_len, sizeof(broken_output_buf));
+ memcpy(send_buf_[i], broken_output_buf, reply_len);
+ }
+
+ out_stats->bytes_out += reply_len;
+ send_iov_[i].iov_len = reply_len;
+ }
+
+ int messages_sent;
+ do {
+ messages_sent = sendmmsg(fd, send_mmsghdrs_, index, 0);
+ } while (messages_sent == -1 && errno == EINTR);
+
+ if (messages_sent == -1) {
+ GOOGLE_PLOG(ERROR) << "sendmmsg";
+ return false;
+ }
+ GOOGLE_LOG_IF_EVERY_N_SEC(ERROR, (static_cast<size_t>(messages_sent) < index),
+ 30)
+ << "only " << messages_sent << " of " << index << " messages were sent";
+
+ return true;
+}
+
+bool UdpProcessor::MaybeBreakResponse(uint8_t *out, size_t *out_len,
+ size_t max_out_len,
+ const uint8_t *normal_response,
+ size_t normal_response_len,
+ const uint8_t *request,
+ size_t request_len) {
+ const uint16_t rand = requests_processed_ & 1023;
+ if (rand >= broken_reply_generator_sum_) {
+ return false;
+ }
+
+ uint16_t sum = 0;
+ BrokenReplyGenerator *selected = nullptr;
+ for (const auto &i : broken_reply_generators_) {
+ sum += i->probability_1024();
+ if (rand < sum) {
+ selected = i.get();
+ break;
+ }
+ }
+
+ return selected->Process(out, out_len, max_out_len, normal_response,
+ normal_response_len, request, request_len);
+}
+
+} // namespace roughtime
diff --git a/udp_processor.h b/udp_processor.h
new file mode 100644
index 0000000..ba96dea
--- /dev/null
+++ b/udp_processor.h
@@ -0,0 +1,107 @@
+/* Copyright 2016 The Roughtime Authors.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License. */
+
+#ifndef SECURITY_ROUGHTIME_UDP_PROCESSOR_H_
+#define SECURITY_ROUGHTIME_UDP_PROCESSOR_H_
+
+#include <arpa/inet.h>
+#include <netinet/in.h>
+
+#include <memory>
+#include <vector>
+
+#include "server.h"
+
+namespace roughtime {
+
+// UdpProcessor manages a set of receive buffers for processing UDP requests.
+class UdpProcessor {
+ public:
+ // Stats contains various counters for a single batch.
+ struct Stats {
+ size_t bytes_in;
+ size_t bytes_out;
+ unsigned packets_in;
+ unsigned packets_out;
+ unsigned requests_invalid;
+ unsigned requests_truncated;
+ };
+
+ UdpProcessor();
+ virtual ~UdpProcessor();
+
+ // AddBrokenReplyGenerator adds a BrokenReplyGenerator that will be used for
+ // a fraction of single-request batches. It can answer the request with
+ // replies that are designed to test edge cases in clients. The sum of
+ // probabilities of all generators passed to |AddBrokenReplyGenerator| must
+ // be ≤ 1024.
+ bool AddBrokenReplyGenerator(std::unique_ptr<BrokenReplyGenerator> generator);
+
+ // ProcessBatch reads zero or more requests from |fd|, has |server| process
+ // them and sends out the replies. It returns false if there was an
+ // unexpected error during processing and true otherwise. (Reading zero
+ // packets, finding invalid requests etc are not counted as unexpected
+ // errors.)
+ virtual bool ProcessBatch(int fd, Server* server, Stats* out_stats);
+
+ // MakeSocket sets |*out_sock| to a UDP socket bound to the given port and
+ // sets |*out_port| to the bound port number. If |port| is zero then a free
+ // port number is used. It returns true on success or false on error.
+ static bool MakeSocket(int port, int* out_sock, uint16_t* out_port);
+
+ protected:
+ // See recvmmsg(2) for help understanding these. Note that indices in the
+ // sending arrays don't correspond 1:1 with indices in the receiving arrays,
+ // due to the possibility of invalid requests.
+ mmsghdr recv_mmsghdrs_[kBatchSize];
+ iovec recv_iov_[kBatchSize];
+ uint8_t recv_buf_[kBatchSize][kMaxRecvPacketSize];
+
+ mmsghdr send_mmsghdrs_[kBatchSize];
+ iovec send_iov_[kBatchSize];
+ uint8_t send_buf_[kBatchSize][kMaxResponseSize];
+
+ // PrepareResponse sets up |send_mmsghdrs[index]|.
+ virtual void PrepareResponse(struct msghdr* out_send_header,
+ const struct msghdr& recv_header);
+
+ // Reset clears state in order to prepare for recvmmsg(2).
+ virtual void Reset();
+
+ private:
+ // MaybeBreakResponse takes a valid request in |request| and the standard
+ // response in |normal_response|. If any element of
+ // |broken_reply_generators_| should be applied then it does so. It returns
+ // true if the response in |out| should be sent and false if not.
+ bool MaybeBreakResponse(uint8_t* out, size_t* out_len, size_t max_out_len,
+ const uint8_t* normal_response,
+ size_t normal_response_len, const uint8_t* request,
+ size_t request_len);
+
+ sockaddr_storage sockaddrs_[kBatchSize];
+
+ // requests_processed_ is the total number of valid requests that have been
+ // processed.
+ uint64_t requests_processed_ = 0;
+
+ std::vector<std::unique_ptr<BrokenReplyGenerator>> broken_reply_generators_;
+
+ // broken_reply_generator_sum_ is the sum of the probabilities of
+ // |broken_reply_generators_|.
+ uint16_t broken_reply_generator_sum_ = 0;
+};
+
+} // namespace roughtime
+
+#endif // SECURITY_ROUGHTIME_UDP_PROCESSOR_H_
