Merge "Fix instructions for building Go code."
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_