Merge "Fix typo in PROTOCOL.md"
diff --git a/BUILD b/BUILD
index 4e03973..1d3c2e1 100644
--- a/BUILD
+++ b/BUILD
@@ -44,6 +44,7 @@
cc_library(
name = "time_source",
hdrs = ["time_source.h"],
+ deps = [":protocol"],
)
cc_library(
diff --git a/client.cc b/client.cc
index 68b1953..8543e0d 100644
--- a/client.cc
+++ b/client.cc
@@ -42,7 +42,7 @@
return std::string(reinterpret_cast<char*>(query_bytes), query_len);
}
-bool ParseResponse(uint64_t* out_time, uint32_t* out_radius,
+bool ParseResponse(rough_time_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,
@@ -94,7 +94,7 @@
}
const uint8_t* delegated_public_key;
- uint64_t min_time, max_time;
+ rough_time_t min_time, max_time;
Parser delegation(delegation_bytes, delegation_len);
if (!delegation.is_valid() ||
!delegation.Get(&min_time, kTagMINT) ||
@@ -144,7 +144,7 @@
}
const uint8_t* root;
- uint64_t timestamp;
+ rough_time_t timestamp;
uint32_t radius;
if (!signed_response.GetFixedLen(&root, kTagROOT, kNonceLength) ||
!signed_response.Get(×tamp, kTagMIDP) ||
diff --git a/client_test.cc b/client_test.cc
index 45c3569..8204de2 100644
--- a/client_test.cc
+++ b/client_test.cc
@@ -75,18 +75,18 @@
size_t response_len;
std::string out_error;
- uint64_t out_time;
+ rough_time_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(rough_time_t mint, rough_time_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(rough_time_t now);
void MakeSigned() { MakeSigned(1000); }
void MakeResponse(const uint8_t* private_key);
void MakeResponse() { MakeResponse(delegated_private_key); }
@@ -100,7 +100,7 @@
ED25519_keypair(root_public_key, root_private_key);
}
-void ResponseBuilder::MakeDelegation(uint64_t mint, uint64_t maxt) {
+void ResponseBuilder::MakeDelegation(rough_time_t mint, rough_time_t maxt) {
Builder builder(delegation, arraysize(delegation), 3);
ASSERT_TRUE(builder.AddTagData(kTagPUBK, delegated_public_key,
arraysize(delegated_public_key)));
@@ -142,7 +142,7 @@
}
}
-void ResponseBuilder::MakeSigned(uint64_t now) {
+void ResponseBuilder::MakeSigned(rough_time_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),
diff --git a/go/client/client.go b/go/client/client.go
index 4a9db0b..7938e72 100644
--- a/go/client/client.go
+++ b/go/client/client.go
@@ -206,23 +206,16 @@
s.max.Sub(s.max, delta)
}
+// contains returns true iff p belongs to s
+func (s *timeSample) contains(p *big.Int) bool {
+ return s.max.Cmp(p) >= 0 && s.min.Cmp(p) <= 0
+}
+
// 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) {
@@ -415,10 +408,10 @@
for _, sample := range samples[1:] {
if ret.min.Cmp(sample.min) < 0 {
- sample.min.Set(ret.min)
+ ret.min.Set(sample.min)
}
if ret.max.Cmp(sample.max) > 0 {
- sample.max.Set(ret.max)
+ ret.max.Set(sample.max)
}
}
@@ -437,11 +430,13 @@
overlapping := make([]*timeSample, 0, n)
- for i, initial := range samples {
- overlapping = append(overlapping, initial)
+ for _, initial := range samples {
+ // An intersection of any subset of intervals will be an interval that contains
+ // the starting point of one of the intervals (possibly as its own starting point).
+ point := initial.min
- for _, candidate := range samples[i+1:] {
- if candidate.overlapsAll(overlapping) {
+ for _, candidate := range samples {
+ if candidate.contains(point) {
overlapping = append(overlapping, candidate)
}
diff --git a/go/client/client_test.go b/go/client/client_test.go
index bebec9f..d08d955 100644
--- a/go/client/client_test.go
+++ b/go/client/client_test.go
@@ -17,6 +17,7 @@
import (
"crypto/rand"
"encoding/json"
+ "math/big"
"net"
"strconv"
"sync"
@@ -333,3 +334,56 @@
addr: localAddr,
}, nil
}
+
+func TestFindNOverlapping(t *testing.T) {
+ type sample struct {
+ min int64
+ max int64
+ }
+ testcases := []struct {
+ samples []sample
+ maxN int
+ }{
+ {
+ samples: []sample{
+ {0, 2},
+ {1, 3},
+ },
+ maxN: 2,
+ },
+ {
+ samples: []sample{
+ {0, 2},
+ {1, 3},
+ {4, 5},
+ },
+ maxN: 2,
+ },
+ {
+ samples: []sample{
+ {0, 10},
+ {1, 2},
+ {5, 10},
+ {6, 10},
+ },
+ maxN: 3,
+ },
+ }
+ for i, tc := range testcases {
+ samples := make([]*timeSample, len(tc.samples))
+ for j, s := range tc.samples {
+ samples[j] = &timeSample{
+ base: big.NewInt(0),
+ min: big.NewInt(s.min),
+ max: big.NewInt(s.max),
+ }
+ }
+ for n := 1; n <= len(samples); n++ {
+ expectedOk := n <= tc.maxN
+ _, ok := findNOverlapping(samples, n)
+ if ok != expectedOk {
+ t.Errorf("#%d: findNOverlapping(n=%d) returned %v, wanted %v", i, n, ok, expectedOk)
+ }
+ }
+ }
+}
diff --git a/protocol.cc b/protocol.cc
index 44afcad..358755e 100644
--- a/protocol.cc
+++ b/protocol.cc
@@ -102,7 +102,7 @@
static int tag_cmp(const void *keyp, const void *memberp) {
tag_t key, member;
- memcpy(&key, keyp, sizeof(uint32_t));
+ memcpy(&key, keyp, sizeof(tag_t));
memcpy(&member, memberp, sizeof(uint32_t));
if (key == member) {
diff --git a/protocol.h b/protocol.h
index d0a8515..1ae044d 100644
--- a/protocol.h
+++ b/protocol.h
@@ -35,6 +35,13 @@
typedef uint32_t tag_t;
+// rough_time_t is the type of a time stamp. Time is UTC and is given as
+// milliseconds since the UNIX epoch (00:00:00 UTC on 1 January 1970). Leap
+// seconds are linearly smeared over a 24-hour period. That is, the smear
+// extends from UTC noon to noon over 86,401 or 86,399 SI seconds, and all the
+// smeared seconds are the same length.
+typedef uint64_t rough_time_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
diff --git a/protocol_test.cc b/protocol_test.cc
index a912fcf..306e327 100644
--- a/protocol_test.cc
+++ b/protocol_test.cc
@@ -25,8 +25,7 @@
constexpr tag_t kTagTAG4 = MakeTag('T', 'A', 'G', '4');
TEST(ParserTest, Success) {
- alignas(4) uint8_t buffer[] = {
- 0x00, // misalign the buffer
+ const uint8_t 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
@@ -38,7 +37,7 @@
0x33, 0x33, 0x33, 0x33, // data for tag #3
};
- Parser parser(buffer + 1, sizeof(buffer) - 1);
+ Parser parser(buffer, sizeof(buffer));
EXPECT_TRUE(parser.is_valid());
const uint8_t* datap;
size_t len;
@@ -71,6 +70,42 @@
EXPECT_FALSE(parser.GetFixedLen(&datap, kTagTAG4, 1));
}
+TEST(ParserTest, UnalignedInput) {
+ alignas(4) const uint8_t buffer[] = {
+ 0x00, // unalign input.
+ 0x02, 0x00, 0x00, 0x00, // 2 tags
+ 0x04, 0x00, 0x00, 0x00, // tag #2 has offset 4
+ 0x54, 0x41, 0x47, 0x31, // TAG1
+ 0x54, 0x41, 0x47, 0x32, // TAG2
+ 0x11, 0x11, 0x11, 0x11, // data for tag #1
+ 0x22, 0x22, 0x22, 0x22, // data for tag #2
+ };
+
+ 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_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);
diff --git a/server.cc b/server.cc
index 85443db..e10a956 100644
--- a/server.cc
+++ b/server.cc
@@ -81,7 +81,7 @@
// 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 rough_time_t now = interval.first;
const uint32_t radius = interval.second;
Builder to_be_signed(to_be_signed_, kToBeSignedSize, 3);
@@ -140,7 +140,7 @@
// 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,
+ rough_time_t start_time, rough_time_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];
diff --git a/server.h b/server.h
index 7953a38..d10a2e3 100644
--- a/server.h
+++ b/server.h
@@ -42,7 +42,7 @@
// 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,
+ rough_time_t start_time, rough_time_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
diff --git a/simple_client.cc b/simple_client.cc
index 145227a..ab04061 100644
--- a/simple_client.cc
+++ b/simple_client.cc
@@ -269,7 +269,7 @@
return kExitNetworkError;
}
- uint64_t timestamp;
+ roughtime::rough_time_t timestamp;
uint32_t radius;
std::string error;
if (!roughtime::ParseResponse(
diff --git a/simple_server.cc b/simple_server.cc
index c0c2261..8b3a764 100644
--- a/simple_server.cc
+++ b/simple_server.cc
@@ -38,8 +38,8 @@
// static
std::unique_ptr<Identity> SimpleServer::MakeIdentity(
- const uint8_t root_private_key[ED25519_PRIVATE_KEY_LEN], uint64_t mint,
- uint64_t maxt) {
+ const uint8_t root_private_key[ED25519_PRIVATE_KEY_LEN], rough_time_t mint,
+ rough_time_t maxt) {
GOOGLE_CHECK(mint <= maxt);
uint8_t delegated_private_key[ED25519_PRIVATE_KEY_LEN];
uint8_t delegated_public_key[ED25519_PUBLIC_KEY_LEN];
diff --git a/simple_server.h b/simple_server.h
index 159e7ff..30f09f7 100644
--- a/simple_server.h
+++ b/simple_server.h
@@ -47,8 +47,8 @@
// 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);
+ const uint8_t root_private_key[ED25519_PRIVATE_KEY_LEN],
+ rough_time_t mint, rough_time_t maxt);
private:
const int fd_;
diff --git a/simple_server_main.cc b/simple_server_main.cc
index bc3002a..99048ef 100644
--- a/simple_server_main.cc
+++ b/simple_server_main.cc
@@ -60,7 +60,8 @@
std::unique_ptr<roughtime::Identity> identity =
roughtime::SimpleServer::MakeIdentity(root_private_key, 0,
2147483647000000);
- std::unique_ptr<TimeSource> time_source(new roughtime::SystemTimeSource);
+ std::unique_ptr<roughtime::TimeSource> time_source(
+ new roughtime::SystemTimeSource);
auto server =
std::unique_ptr<roughtime::SimpleServer>(new roughtime::SimpleServer(
diff --git a/sys_time.cc b/sys_time.cc
index b0eca57..5fa9532 100644
--- a/sys_time.cc
+++ b/sys_time.cc
@@ -24,7 +24,7 @@
SystemTimeSource::~SystemTimeSource() {}
-std::pair<uint64_t, uint32_t> SystemTimeSource::Now() {
+std::pair<rough_time_t, uint32_t> SystemTimeSource::Now() {
struct timespec ts;
GOOGLE_CHECK_EQ(0, clock_gettime(CLOCK_REALTIME_COARSE, &ts));
uint64_t now = ts.tv_sec;
diff --git a/time_source.h b/time_source.h
index 929faaa..022ce86 100644
--- a/time_source.h
+++ b/time_source.h
@@ -19,6 +19,10 @@
#include <utility>
+#include "protocol.h"
+
+namespace roughtime {
+
// TimeSource is an interface that can provide the current time.
class TimeSource {
public:
@@ -26,7 +30,9 @@
// Now returns the midpoint time in epoch-microseconds and a radius of
// uncertainty.
- virtual std::pair<uint64_t, uint32_t> Now() = 0;
+ virtual std::pair<rough_time_t, uint32_t> Now() = 0;
};
+} // namespace roughtime
+
#endif // SECURITY_ROUGHTIME_TIME_SOURCE_H_
