protocol.h - roughtime - Git at Google

 /* 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_
	/* 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_