Add roughtime protocol

Signed-off-by: Nuno Goncalves <[email protected]>

4 files changed, 605 insertions, 0 deletions

diff --git a/src/lib/misc/roughtime/info.txt b/src/lib/misc/roughtime/info.txt
new file mode 100644
index 000000000..560f52666
--- /dev/null
+++ b/src/lib/misc/roughtime/info.txt
@@ -0,0 +1,10 @@
+<defines>
+ROUGHTIME -> 20190220
+</defines>
+
+<requires>
+ed25519
+rng
+sha2_64
+socket
+</requires>
diff --git a/src/lib/misc/roughtime/roughtime.cpp b/src/lib/misc/roughtime/roughtime.cpp
new file mode 100644
index 000000000..c9767546a
--- /dev/null
+++ b/src/lib/misc/roughtime/roughtime.cpp
@@ -0,0 +1,429 @@
+/*
+* Roughtime
+* (C) 2019 Nuno Goncalves <[email protected]>
+*
+* Botan is released under the Simplified BSD License (see license.txt)
+*/
+
+#include <botan/roughtime.h>
+
+#include <botan/base64.h>
+#include <botan/hash.h>
+#include <botan/internal/socket_udp.h>
+#include <botan/pubkey.h>
+#include <botan/rng.h>
+
+#include <cmath>
+#include <map>
+#include <sstream>
+
+namespace Botan {
+
+namespace {
+
+template<typename T>
+std::map<std::string, std::vector<uint8_t>> unpack_roughtime_packet(T bytes)
+   {
+   if(bytes.size() < 8)
+      { throw Roughtime::Roughtime_Error("Map length is under minimum of 8 bytes"); }
+   const auto buf = bytes.data();
+   const uint32_t num_tags = buf[0];
+   const uint32_t start_content = num_tags * 8;
+   if(start_content > bytes.size())
+      { throw Roughtime::Roughtime_Error("Map length too small to contain all tags"); }
+   uint32_t start = start_content;
+   std::map<std::string, std::vector<uint8_t>> tags;
+   for(uint32_t i=0; i<num_tags; ++i)
+      {
+      const uint32_t end = ((i+1) == num_tags) ? bytes.size() : start_content + typecast_copy<uint32_t>(buf + 4 + i*4);
+      if(end > bytes.size())
+         { throw Roughtime::Roughtime_Error("Tag end index out of bounds"); }
+      if(end < start)
+         { throw Roughtime::Roughtime_Error("Tag offset must be more than previous tag offset"); }
+      const char* label_ptr = cast_uint8_ptr_to_char(buf) + (num_tags+i)*4;
+      const char label[] = {label_ptr[0], label_ptr[1], label_ptr[2], label_ptr[3], 0};
+      auto ret = tags.emplace(label, std::vector<uint8_t>(buf+start, buf+end));
+      if(!ret.second)
+         { throw Roughtime::Roughtime_Error(std::string("Map has duplicated tag: ") + label); }
+      start = end;
+      }
+   return tags;
+   }
+
+template<typename T>
+T get(const std::map<std::string, std::vector<uint8_t>>& map, const std::string& label)
+   {
+   const auto& tag = map.find(label);
+   if(tag == map.end())
+      { throw Roughtime::Roughtime_Error("Tag " + label + " not found"); }
+   if(tag->second.size() != sizeof(T))
+      { throw Roughtime::Roughtime_Error("Tag " + label + " has unexpected size"); }
+   return typecast_copy<T>(tag->second.data());
+   }
+
+const std::vector<uint8_t>& get_v(const std::map<std::string, std::vector<uint8_t>>& map, const std::string& label)
+   {
+   const auto& tag = map.find(label);
+   if(tag == map.end())
+      { throw Roughtime::Roughtime_Error("Tag " + label + " not found"); }
+   return tag->second;
+   }
+
+bool verify_signature(const std::array<uint8_t, 32>& pk, const std::vector<uint8_t>& payload,
+                      const std::array<uint8_t, 64>& signature)
+   {
+   const char context[] = "RoughTime v1 response signature";
+   Ed25519_PublicKey key(std::vector<uint8_t>(pk.data(), pk.data()+pk.size()));
+   PK_Verifier verifier(key, "Pure");
+   verifier.update(cast_char_ptr_to_uint8(context), sizeof(context)); //add context including \0
+   verifier.update(payload);
+   return verifier.check_signature(signature.data(), signature.size());
+   }
+
+std::array<uint8_t, 64> hashLeaf(const std::array<uint8_t, 64>& leaf)
+   {
+   std::array<uint8_t, 64> ret;
+   std::unique_ptr<HashFunction> hash(HashFunction::create_or_throw("SHA-512"));
+   hash->update(0);
+   hash->update(leaf.data(), leaf.size());
+   hash->final(ret.data());
+   return ret;
+   }
+
+void hashNode(std::array<uint8_t, 64>& hash, const std::array<uint8_t, 64>& node, bool reverse)
+   {
+   std::unique_ptr<HashFunction> h(HashFunction::create_or_throw("SHA-512"));
+   h->update(1);
+   if(reverse)
+      {
+      h->update(node.data(), node.size());
+      h->update(hash.data(), hash.size());
+      }
+   else
+      {
+      h->update(hash.data(), hash.size());
+      h->update(node.data(), node.size());
+      }
+   h->final(hash.data());
+   }
+
+template<size_t N, typename T>
+std::array<uint8_t, N> vector_to_array(std::vector<uint8_t,T> vec)
+   {
+   if(vec.size() != N)
+      { throw std::logic_error("Invalid vector size"); }
+   return typecast_copy<std::array<uint8_t, N>>(vec.data());
+   }
+}
+
+namespace Roughtime {
+
+Nonce::Nonce(const std::vector<uint8_t>& nonce)
+   {
+   if(nonce.size() != 64)
+      { throw Invalid_Argument("Nonce lenght must be 64"); }
+   m_nonce = typecast_copy<std::array<uint8_t, 64>>(nonce.data());
+   }
+Nonce::Nonce(RandomNumberGenerator& rng)
+   {
+   rng.randomize(m_nonce.data(), m_nonce.size());
+   }
+
+std::array<uint8_t, request_min_size> encode_request(const Nonce& nonce)
+   {
+   std::array<uint8_t, request_min_size> buf = {2, 0, 0, 0, 64, 0, 0, 0, 'N', 'O', 'N', 'C', 'P', 'A', 'D', 0xff};
+   std::memcpy(buf.data() + 16, nonce.get_nonce().data(), nonce.get_nonce().size());
+   std::memset(buf.data() + 16 + nonce.get_nonce().size(), 0, buf.size() - 16 - nonce.get_nonce().size());
+   return buf;
+   }
+
+Response Response::from_bits(const std::vector<uint8_t>& response,
+                             const Nonce& nonce)
+   {
+   const auto response_v = unpack_roughtime_packet(response);
+   const auto cert = unpack_roughtime_packet(get_v(response_v, "CERT"));
+   const auto cert_dele = get<std::array<uint8_t, 72>>(cert, "DELE");
+   const auto cert_sig =  get<std::array<uint8_t, 64>>(cert, "SIG");
+   const auto cert_dele_v = unpack_roughtime_packet(cert_dele);
+   const auto srep = get_v(response_v, "SREP");
+   const auto srep_v = unpack_roughtime_packet(srep);
+
+   const auto cert_dele_pubk = get<std::array<uint8_t, 32>>(cert_dele_v, "PUBK");
+   const auto sig  = get<std::array<uint8_t, 64>>(response_v, "SIG");
+   if(!verify_signature(cert_dele_pubk, srep, sig))
+      { throw Roughtime_Error("Response signature invalid"); }
+
+   const auto indx = get<uint32_t>(response_v, "INDX");
+   const auto path = get_v(response_v, "PATH");
+   const auto srep_root = get<std::array<uint8_t, 64>>(srep_v, "ROOT");
+   const auto size = path.size();
+   const auto levels = size/64;
+
+   if(size % 64)
+      { throw Roughtime_Error("Merkle tree path size must be multiple of 64 bytes"); }
+   if(indx >= (1u << levels))
+      { throw Roughtime_Error("Merkle tree path is too short"); }
+
+   auto hash = hashLeaf(nonce.get_nonce());
+   auto index = indx;
+   auto level = 0u;
+   while(level < levels)
+      {
+      hashNode(hash, typecast_copy<std::array<uint8_t, 64>>(path.data() + level*64), index&1);
+      ++level;
+      index>>=1;
+      }
+
+   if(srep_root != hash)
+      { throw Roughtime_Error("Nonce verification failed"); }
+
+   const auto cert_dele_maxt = sys_microseconds64(get<microseconds64>(cert_dele_v, "MAXT"));
+   const auto cert_dele_mint = sys_microseconds64(get<microseconds64>(cert_dele_v, "MINT"));
+   const auto srep_midp = sys_microseconds64(get<microseconds64>(srep_v, "MIDP"));
+   const auto srep_radi = get<microseconds32>(srep_v, "RADI");
+   if(srep_midp < cert_dele_mint)
+      { throw Roughtime_Error("Midpoint earlier than delegation start"); }
+   if(srep_midp > cert_dele_maxt)
+      { throw Roughtime_Error("Midpoint later than delegation end"); }
+   return {cert_dele, cert_sig, srep_midp, srep_radi};
+   }
+
+bool Response::validate(const Ed25519_PublicKey& pk) const
+   {
+   const char context[] = "RoughTime v1 delegation signature--";
+   PK_Verifier verifier(pk, "Pure");
+   verifier.update(cast_char_ptr_to_uint8(context), sizeof(context)); //add context including \0
+   verifier.update(m_cert_dele.data(), m_cert_dele.size());
+   return verifier.check_signature(m_cert_sig.data(), m_cert_sig.size());
+   }
+
+Nonce nonce_from_blind(const std::vector<uint8_t>& previous_response,
+                       const Nonce& blind)
+   {
+   std::array<uint8_t, 64> ret;
+   const auto blind_arr = blind.get_nonce();
+   std::unique_ptr<Botan::HashFunction> hash(Botan::HashFunction::create_or_throw("SHA-512"));
+   hash->update(previous_response);
+   hash->update(hash->final());
+   hash->update(blind_arr.data(), blind_arr.size());
+   hash->final(ret.data());
+
+   return ret;
+   }
+
+Chain::Chain(const std::string& str)
+   {
+   std::stringstream ss(str);
+   const std::string ERROR_MESSAGE = "Line does not have 4 space separated fields";
+   for(std::string s; std::getline(ss, s);)
+      {
+      size_t start = 0, end = 0;
+      end = s.find(' ', start);
+      if(end == std::string::npos)
+         {
+         throw Decoding_Error(ERROR_MESSAGE);
+         }
+      const auto publicKeyType = s.substr(start, end-start);
+      if(publicKeyType != "ed25519")
+         { throw Not_Implemented("Only ed25519 publicKeyType is implemented"); }
+
+      start = end + 1;
+      end = s.find(' ', start);
+      if(end == std::string::npos)
+         {
+         throw Decoding_Error(ERROR_MESSAGE);
+         }
+      const auto serverPublicKey = Botan::Ed25519_PublicKey(Botan::base64_decode(s.substr(start, end-start)));
+
+      start = end + 1;
+      end = s.find(' ', start);
+      if(end == std::string::npos)
+         {
+         throw Decoding_Error(ERROR_MESSAGE);
+         }
+      if((end - start) != 88)
+         {
+         throw Decoding_Error("Nonce has invalid length");
+         }
+      const auto vec = Botan::base64_decode(s.substr(start, end-start));
+      const auto nonceOrBlind = Nonce(vector_to_array<64>(Botan::base64_decode(s.substr(start, end-start))));
+
+      start = end + 1;
+      end = s.find(' ', start);
+      if(end != std::string::npos)
+         {
+         throw Decoding_Error(ERROR_MESSAGE);
+         }
+      const auto response = Botan::unlock(Botan::base64_decode(s.substr(start)));
+
+      m_links.push_back({response, serverPublicKey, nonceOrBlind});
+      }
+   }
+std::vector<Response> Chain::responses() const
+   {
+   std::vector<Response> responses;
+   for(unsigned i = 0; i < m_links.size(); ++i)
+      {
+      const auto& l = m_links[i];
+      const auto nonce = i ? nonce_from_blind(m_links[i-1].response(), l.nonce_or_blind()) : l.nonce_or_blind();
+      const auto response = Response::from_bits(l.response(), nonce);
+      if(!response.validate(l.public_key()))
+         { throw Roughtime_Error("Invalid signature or public key"); }
+      responses.push_back(response);
+      }
+   return responses;
+   }
+Nonce Chain::next_nonce(const Nonce& blind) const
+   {
+   return m_links.empty()
+          ? blind
+          : nonce_from_blind(m_links.back().response(), blind);
+   }
+void Chain::append(const Link& new_link, size_t max_chain_size)
+   {
+   if(max_chain_size <= 0)
+      { throw Invalid_Argument("Max chain size must be positive"); }
+
+   while(m_links.size() >= max_chain_size)
+      {
+      if(m_links.size() == 1)
+         {
+         auto new_link_updated = new_link;
+         new_link_updated.nonce_or_blind() =
+            nonce_from_blind(m_links[0].response(), new_link.nonce_or_blind()); //we need to convert blind to nonce
+         m_links.clear();
+         m_links.push_back(new_link_updated);
+         return;
+         }
+      if(m_links.size() >= 2)
+         {
+         m_links[1].nonce_or_blind() =
+            nonce_from_blind(m_links[0].response(), m_links[1].nonce_or_blind()); //we need to convert blind to nonce
+         }
+      m_links.erase(m_links.begin());
+      }
+   m_links.push_back(new_link);
+   }
+
+std::string Chain::to_string() const
+   {
+   std::string s;
+   s.reserve((7+1 + 88+1 + 44+1 + 480)*m_links.size());
+   for(const auto& link : m_links)
+      {
+      s += "ed25519";
+      s += ' ';
+      s += Botan::base64_encode(link.public_key().get_public_key());
+      s += ' ';
+      s += Botan::base64_encode(link.nonce_or_blind().get_nonce().data(), link.nonce_or_blind().get_nonce().size());
+      s += ' ';
+      s += Botan::base64_encode(link.response());
+      s += '\n';
+      }
+   return s;
+   }
+
+std::vector<uint8_t> online_request(const std::string& uri,
+                                    const Nonce& nonce,
+                                    std::chrono::milliseconds timeout)
+   {
+   const std::chrono::system_clock::time_point start_time = std::chrono::system_clock::now();
+   auto socket = OS::open_socket_udp(uri, timeout);
+   if(!socket)
+      { throw Not_Implemented("No socket support enabled in build"); }
+
+   const auto encoded = encode_request(nonce);
+   socket->write(encoded.data(), encoded.size());
+
+   if(std::chrono::system_clock::now() - start_time > timeout)
+      { throw System_Error("Timeout during socket write"); }
+
+   std::vector<uint8_t> buffer;
+   buffer.resize(360+64*10+1); //response basic size is 360 bytes + 64 bytes for each level of merkle tree
+                               //add one additional byte to be able to differentiate if datagram got truncated
+   const auto n = socket->read(buffer.data(), buffer.size());
+
+   if(!n || std::chrono::system_clock::now() - start_time > timeout)
+      { throw System_Error("Timeout waiting for response"); }
+
+   if(n == buffer.size())
+      { throw System_Error("Buffer too small"); }
+
+   buffer.resize(n);
+   return buffer;
+   }
+
+std::vector<Server_Information> servers_from_str(const std::string& str)
+   {
+   std::vector<Server_Information> servers;
+   std::stringstream ss(str);
+   const std::string ERROR_MESSAGE = "Line does not have at least 5 space separated fields";
+   for(std::string s; std::getline(ss, s);)
+      {
+      size_t start = 0, end = 0;
+      end = s.find(' ', start);
+      if(end == std::string::npos)
+         {
+         throw Decoding_Error(ERROR_MESSAGE);
+         }
+      const auto name = s.substr(start, end-start);
+
+      start = end + 1;
+      end = s.find(' ', start);
+      if(end == std::string::npos)
+         {
+         throw Decoding_Error(ERROR_MESSAGE);
+         }
+      const auto publicKeyType = s.substr(start, end-start);
+      if(publicKeyType != "ed25519")
+         { throw Not_Implemented("Only ed25519 publicKeyType is implemented"); }
+
+      start = end + 1;
+      end = s.find(' ', start);
+
+      if(end == std::string::npos)
+         {
+         throw Decoding_Error(ERROR_MESSAGE);
+         }
+      const auto publicKeyBase64 = s.substr(start, end-start);
+      const auto publicKey = Botan::Ed25519_PublicKey(Botan::base64_decode(publicKeyBase64));
+
+      start = end + 1;
+      end = s.find(' ', start);
+      if(end == std::string::npos)
+         {
+         throw Decoding_Error(ERROR_MESSAGE);
+         }
+      const auto protocol = s.substr(start, end-start);
+      if(protocol != "udp")
+         { throw Not_Implemented("Only UDP protocol is implemented"); }
+
+      const auto addresses = [&]()
+         {
+         std::vector<std::string> addresses;
+         for(;;)
+            {
+            start = end + 1;
+            end = s.find(' ', start);
+            const auto address = s.substr(start, (end == std::string::npos) ? std::string::npos : end-start);
+            if(address.empty())
+               { return addresses; }
+            addresses.push_back(address);
+            if(end == std::string::npos)
+               { return addresses; }
+            }
+         }
+      ();
+      if(addresses.size() == 0)
+         {
+         throw Decoding_Error(ERROR_MESSAGE);
+         }
+
+      servers.push_back({name, publicKey, std::move(addresses)});
+      }
+   return servers;
+   }
+
+}
+
+}
diff --git a/src/lib/misc/roughtime/roughtime.h b/src/lib/misc/roughtime/roughtime.h
new file mode 100644
index 000000000..595e693b9
--- /dev/null
+++ b/src/lib/misc/roughtime/roughtime.h
@@ -0,0 +1,164 @@
+/*
+* Roughtime
+* (C) 2019 Nuno Goncalves <[email protected]>
+*
+* Botan is released under the Simplified BSD License (see license.txt)
+*/
+
+#ifndef BOTAN_ROUGHTIME_H_
+#define BOTAN_ROUGHTIME_H_
+
+#include <array>
+#include <chrono>
+#include <vector>
+
+#include <botan/ed25519.h>
+
+namespace Botan {
+
+class RandomNumberGenerator;
+
+namespace Roughtime {
+
+constexpr unsigned request_min_size = 1024;
+
+class BOTAN_PUBLIC_API(2, 13) Roughtime_Error final : public Decoding_Error
+   {
+   public:
+      explicit Roughtime_Error(const std::string& s) : Decoding_Error("Roughtime " + s) {}
+      ErrorType error_type() const noexcept override { return ErrorType::RoughtimeError; }
+   };
+
+class BOTAN_PUBLIC_API(2, 13) Nonce final
+   {
+   public:
+      Nonce() = default;
+      Nonce(const std::vector<uint8_t>& nonce);
+      Nonce(RandomNumberGenerator& rng);
+      Nonce(const std::array<uint8_t, 64>& nonce)
+         {
+         m_nonce = nonce;
+         }
+      bool operator==(const Nonce& rhs) const { return m_nonce == rhs.m_nonce; }
+      const std::array<uint8_t, 64>& get_nonce() const { return m_nonce; }
+   private:
+      std::array<uint8_t, 64> m_nonce;
+   };
+
+
+/**
+* An Roughtime request.
+*/
+BOTAN_PUBLIC_API(2, 13)
+std::array<uint8_t, request_min_size> encode_request(const Nonce& nonce);
+
+/**
+* An Roughtime response.
+*/
+class BOTAN_PUBLIC_API(2, 13) Response final
+   {
+   public:
+      using microseconds32 = std::chrono::duration<uint32_t, std::micro>;
+      using microseconds64 = std::chrono::duration<uint64_t, std::micro>;
+      using sys_microseconds64 = std::chrono::time_point<std::chrono::system_clock, microseconds64>;
+
+      static Response from_bits(const std::vector<uint8_t>& response, const Nonce& nonce);
+
+      bool validate(const Ed25519_PublicKey& pk) const;
+
+      sys_microseconds64 utc_midpoint() const { return m_utc_midpoint; }
+
+      microseconds32 utc_radius() const { return m_utc_radius; }
+   private:
+      Response(std::array<uint8_t, 72> dele, std::array<uint8_t, 64> sig, sys_microseconds64 utc_midp,
+               microseconds32 utc_radius)
+         : m_cert_dele(dele)
+         , m_cert_sig(sig)
+         , m_utc_midpoint {utc_midp}
+         , m_utc_radius {utc_radius}
+         {}
+      const std::array<uint8_t, 72> m_cert_dele;
+      const std::array<uint8_t, 64> m_cert_sig;
+      const sys_microseconds64 m_utc_midpoint;
+      const microseconds32 m_utc_radius;
+   };
+
+class BOTAN_PUBLIC_API(2, 13) Link final
+   {
+   public:
+      Link(const std::vector<uint8_t>& response,
+           const Ed25519_PublicKey& public_key,
+           const Nonce& nonce_or_blind)
+         : m_response{response}
+         , m_public_key{public_key}
+         , m_nonce_or_blind{nonce_or_blind}
+         {}
+      const std::vector<uint8_t>& response() const { return m_response; }
+      const Ed25519_PublicKey& public_key() const { return m_public_key; }
+      const Nonce& nonce_or_blind() const { return m_nonce_or_blind; }
+      Nonce& nonce_or_blind() { return m_nonce_or_blind; }
+
+   private:
+      std::vector<uint8_t> m_response;
+      Ed25519_PublicKey m_public_key;
+      Nonce m_nonce_or_blind;
+   };
+
+class BOTAN_PUBLIC_API(2, 13) Chain final
+   {
+   public:
+      Chain() = default; //empty
+      Chain(const std::string& str);
+      const std::vector<Link>& links() const { return m_links; }
+      std::vector<Response> responses() const;
+      Nonce next_nonce(const Nonce& blind) const;
+      void append(const Link& new_link, size_t max_chain_size);
+      std::string to_string() const;
+   private:
+      std::vector<Link> m_links;
+   };
+
+/**
+*/
+BOTAN_PUBLIC_API(2, 13)
+Nonce nonce_from_blind(const std::vector<uint8_t>& previous_response,
+                       const Nonce& blind);
+
+/**
+* Makes an online Roughtime request via UDP and returns the Roughtime response.
+* @param url Roughtime server UDP endpoint (host:port)
+* @param timeout a timeout on the UDP request
+* @return Roughtime response
+*/
+BOTAN_PUBLIC_API(2, 13)
+std::vector<uint8_t> online_request(const std::string& uri,
+                                    const Nonce& nonce,
+                                    std::chrono::milliseconds timeout = std::chrono::seconds(3));
+
+struct BOTAN_PUBLIC_API(2, 13) Server_Information final
+   {
+public:
+   Server_Information(const std::string& name,
+                      const Botan::Ed25519_PublicKey& public_key,
+                      const std::vector<std::string>& addresses)
+      : m_name { name }
+      , m_public_key { public_key }
+      , m_addresses { addresses }
+      {}
+   const std::string& name() const {return m_name;}
+   const Botan::Ed25519_PublicKey& public_key() const {return m_public_key;}
+   const std::vector<std::string>& addresses() const {return m_addresses;}
+
+private:
+   std::string m_name;
+   Botan::Ed25519_PublicKey m_public_key;
+   std::vector<std::string> m_addresses;
+   };
+
+BOTAN_PUBLIC_API(2, 13)
+std::vector<Server_Information> servers_from_str(const std::string& str);
+
+}
+}
+
+#endif
diff --git a/src/lib/utils/exceptn.h b/src/lib/utils/exceptn.h
index 0259a225b..442ec91e6 100644
--- a/src/lib/utils/exceptn.h
+++ b/src/lib/utils/exceptn.h
@@ -53,6 +53,8 @@ enum class ErrorType {
    HttpError,
    /** A message with an invalid authentication tag was detected */
    InvalidTag,
+   /** An error during Roughtime validation */
+   RoughtimeError,
 
    /** An error when calling OpenSSL */
    OpenSSLError = 200,