Botan  2.15.0
Crypto and TLS for C++11
roughtime.cpp
Go to the documentation of this file.
1 /*
2 * Roughtime
3 * (C) 2019 Nuno Goncalves <nunojpg@gmail.com>
4 *
5 * Botan is released under the Simplified BSD License (see license.txt)
6 */
7 
8 #include <botan/roughtime.h>
9 
10 #include <botan/base64.h>
11 #include <botan/hash.h>
12 #include <botan/internal/socket_udp.h>
13 #include <botan/pubkey.h>
14 #include <botan/rng.h>
15 
16 #include <cmath>
17 #include <map>
18 #include <sstream>
19 
20 namespace Botan {
21 
22 namespace {
23 
24 // This exists to work around a LGTM false positive
25 static_assert(Roughtime::request_min_size == 1024, "Expected minimum size");
26 
27 template< bool B, class T = void >
28 using enable_if_t = typename std::enable_if<B,T>::type;
29 
30 template<class T>
31 struct is_array : std::false_type {};
32 
33 template<class T, std::size_t N>
34 struct is_array<std::array<T,N>>:std::true_type{};
35 
36 template<typename T>
37 T impl_from_little_endian(const uint8_t* t, const size_t i)
38  {
39  static_assert(sizeof(T) <= sizeof(int64_t), "");
40  return T(static_cast<int64_t>(t[i]) << i * 8) + (i == 0 ? T(0) : impl_from_little_endian<T>(t, i - 1));
41  }
42 
43 template<typename T>
44 T from_little_endian(const uint8_t* t)
45  {
46  return impl_from_little_endian<T>(t, sizeof(T) - 1);
47  }
48 
49 template<typename T, enable_if_t<is_array<T>::value>* = nullptr>
50 T copy(const uint8_t* t)
51  {
52  return typecast_copy<T>(t); //arrays are endianess indepedent, so we do a memcpy
53  }
54 
55 template<typename T, enable_if_t<!is_array<T>::value>* = nullptr>
56 T copy(const uint8_t* t)
57  {
58  return from_little_endian<T>(t); //other types are arithmetic, so we account that roughtime serializes as little endian
59  }
60 
61 template<typename T>
62 std::map<std::string, std::vector<uint8_t>> unpack_roughtime_packet(T bytes)
63  {
64  if(bytes.size() < 8)
65  { throw Roughtime::Roughtime_Error("Map length is under minimum of 8 bytes"); }
66  const auto buf = bytes.data();
67  const uint32_t num_tags = buf[0];
68  const uint32_t start_content = num_tags * 8;
69  if(start_content > bytes.size())
70  { throw Roughtime::Roughtime_Error("Map length too small to contain all tags"); }
71  uint32_t start = start_content;
72  std::map<std::string, std::vector<uint8_t>> tags;
73  for(uint32_t i=0; i<num_tags; ++i)
74  {
75  const size_t end = ((i+1) == num_tags) ? bytes.size() : start_content + from_little_endian<uint32_t>(buf + 4 + i*4);
76  if(end > bytes.size())
77  { throw Roughtime::Roughtime_Error("Tag end index out of bounds"); }
78  if(end < start)
79  { throw Roughtime::Roughtime_Error("Tag offset must be more than previous tag offset"); }
80  const char* label_ptr = cast_uint8_ptr_to_char(buf) + (num_tags+i)*4;
81  const char label[] = {label_ptr[0], label_ptr[1], label_ptr[2], label_ptr[3], 0};
82  auto ret = tags.emplace(label, std::vector<uint8_t>(buf+start, buf+end));
83  if(!ret.second)
84  { throw Roughtime::Roughtime_Error(std::string("Map has duplicated tag: ") + label); }
85  start = static_cast<uint32_t>(end);
86  }
87  return tags;
88  }
89 
90 template<typename T>
91 T get(const std::map<std::string, std::vector<uint8_t>>& map, const std::string& label)
92  {
93  const auto& tag = map.find(label);
94  if(tag == map.end())
95  { throw Roughtime::Roughtime_Error("Tag " + label + " not found"); }
96  if(tag->second.size() != sizeof(T))
97  { throw Roughtime::Roughtime_Error("Tag " + label + " has unexpected size"); }
98  return copy<T>(tag->second.data());
99  }
100 
101 const std::vector<uint8_t>& get_v(const std::map<std::string, std::vector<uint8_t>>& map, const std::string& label)
102  {
103  const auto& tag = map.find(label);
104  if(tag == map.end())
105  { throw Roughtime::Roughtime_Error("Tag " + label + " not found"); }
106  return tag->second;
107  }
108 
109 bool verify_signature(const std::array<uint8_t, 32>& pk, const std::vector<uint8_t>& payload,
110  const std::array<uint8_t, 64>& signature)
111  {
112  const char context[] = "RoughTime v1 response signature";
113  Ed25519_PublicKey key(std::vector<uint8_t>(pk.data(), pk.data()+pk.size()));
114  PK_Verifier verifier(key, "Pure");
115  verifier.update(cast_char_ptr_to_uint8(context), sizeof(context)); //add context including \0
116  verifier.update(payload);
117  return verifier.check_signature(signature.data(), signature.size());
118  }
119 
120 std::array<uint8_t, 64> hashLeaf(const std::array<uint8_t, 64>& leaf)
121  {
122  std::array<uint8_t, 64> ret;
123  std::unique_ptr<HashFunction> hash(HashFunction::create_or_throw("SHA-512"));
124  hash->update(0);
125  hash->update(leaf.data(), leaf.size());
126  hash->final(ret.data());
127  return ret;
128  }
129 
130 void hashNode(std::array<uint8_t, 64>& hash, const std::array<uint8_t, 64>& node, bool reverse)
131  {
132  std::unique_ptr<HashFunction> h(HashFunction::create_or_throw("SHA-512"));
133  h->update(1);
134  if(reverse)
135  {
136  h->update(node.data(), node.size());
137  h->update(hash.data(), hash.size());
138  }
139  else
140  {
141  h->update(hash.data(), hash.size());
142  h->update(node.data(), node.size());
143  }
144  h->final(hash.data());
145  }
146 
147 template<size_t N, typename T>
148 std::array<uint8_t, N> vector_to_array(std::vector<uint8_t,T> vec)
149  {
150  if(vec.size() != N)
151  { throw std::logic_error("Invalid vector size"); }
152  return typecast_copy<std::array<uint8_t, N>>(vec.data());
153  }
154 }
155 
156 namespace Roughtime {
157 
158 Nonce::Nonce(const std::vector<uint8_t>& nonce)
159  {
160  if(nonce.size() != 64)
161  { throw Invalid_Argument("Nonce lenght must be 64"); }
162  m_nonce = typecast_copy<std::array<uint8_t, 64>>(nonce.data());
163  }
165  {
166  rng.randomize(m_nonce.data(), m_nonce.size());
167  }
168 
169 std::array<uint8_t, request_min_size> encode_request(const Nonce& nonce)
170  {
171  std::array<uint8_t, request_min_size> buf = {{2, 0, 0, 0, 64, 0, 0, 0, 'N', 'O', 'N', 'C', 'P', 'A', 'D', 0xff}};
172  std::memcpy(buf.data() + 16, nonce.get_nonce().data(), nonce.get_nonce().size());
173  std::memset(buf.data() + 16 + nonce.get_nonce().size(), 0, buf.size() - 16 - nonce.get_nonce().size());
174  return buf;
175  }
176 
177 Response Response::from_bits(const std::vector<uint8_t>& response,
178  const Nonce& nonce)
179  {
180  const auto response_v = unpack_roughtime_packet(response);
181  const auto cert = unpack_roughtime_packet(get_v(response_v, "CERT"));
182  const auto cert_dele = get<std::array<uint8_t, 72>>(cert, "DELE");
183  const auto cert_sig = get<std::array<uint8_t, 64>>(cert, "SIG");
184  const auto cert_dele_v = unpack_roughtime_packet(cert_dele);
185  const auto srep = get_v(response_v, "SREP");
186  const auto srep_v = unpack_roughtime_packet(srep);
187 
188  const auto cert_dele_pubk = get<std::array<uint8_t, 32>>(cert_dele_v, "PUBK");
189  const auto sig = get<std::array<uint8_t, 64>>(response_v, "SIG");
190  if(!verify_signature(cert_dele_pubk, srep, sig))
191  { throw Roughtime_Error("Response signature invalid"); }
192 
193  const auto indx = get<uint32_t>(response_v, "INDX");
194  const auto path = get_v(response_v, "PATH");
195  const auto srep_root = get<std::array<uint8_t, 64>>(srep_v, "ROOT");
196  const auto size = path.size();
197  const auto levels = size/64;
198 
199  if(size % 64)
200  { throw Roughtime_Error("Merkle tree path size must be multiple of 64 bytes"); }
201  if(indx >= (1u << levels))
202  { throw Roughtime_Error("Merkle tree path is too short"); }
203 
204  auto hash = hashLeaf(nonce.get_nonce());
205  auto index = indx;
206  auto level = 0u;
207  while(level < levels)
208  {
209  hashNode(hash, typecast_copy<std::array<uint8_t, 64>>(path.data() + level*64), index&1);
210  ++level;
211  index>>=1;
212  }
213 
214  if(srep_root != hash)
215  { throw Roughtime_Error("Nonce verification failed"); }
216 
217  const auto cert_dele_maxt = sys_microseconds64(get<microseconds64>(cert_dele_v, "MAXT"));
218  const auto cert_dele_mint = sys_microseconds64(get<microseconds64>(cert_dele_v, "MINT"));
219  const auto srep_midp = sys_microseconds64(get<microseconds64>(srep_v, "MIDP"));
220  const auto srep_radi = get<microseconds32>(srep_v, "RADI");
221  if(srep_midp < cert_dele_mint)
222  { throw Roughtime_Error("Midpoint earlier than delegation start"); }
223  if(srep_midp > cert_dele_maxt)
224  { throw Roughtime_Error("Midpoint later than delegation end"); }
225  return {cert_dele, cert_sig, srep_midp, srep_radi};
226  }
227 
229  {
230  const char context[] = "RoughTime v1 delegation signature--";
231  PK_Verifier verifier(pk, "Pure");
232  verifier.update(cast_char_ptr_to_uint8(context), sizeof(context)); //add context including \0
233  verifier.update(m_cert_dele.data(), m_cert_dele.size());
234  return verifier.check_signature(m_cert_sig.data(), m_cert_sig.size());
235  }
236 
237 Nonce nonce_from_blind(const std::vector<uint8_t>& previous_response,
238  const Nonce& blind)
239  {
240  std::array<uint8_t, 64> ret;
241  const auto blind_arr = blind.get_nonce();
242  std::unique_ptr<Botan::HashFunction> hash(Botan::HashFunction::create_or_throw("SHA-512"));
243  hash->update(previous_response);
244  hash->update(hash->final());
245  hash->update(blind_arr.data(), blind_arr.size());
246  hash->final(ret.data());
247 
248  return ret;
249  }
250 
251 Chain::Chain(const std::string& str)
252  {
253  std::stringstream ss(str);
254  const std::string ERROR_MESSAGE = "Line does not have 4 space separated fields";
255  for(std::string s; std::getline(ss, s);)
256  {
257  size_t start = 0, end = 0;
258  end = s.find(' ', start);
259  if(end == std::string::npos)
260  {
261  throw Decoding_Error(ERROR_MESSAGE);
262  }
263  const auto publicKeyType = s.substr(start, end-start);
264  if(publicKeyType != "ed25519")
265  { throw Not_Implemented("Only ed25519 publicKeyType is implemented"); }
266 
267  start = end + 1;
268  end = s.find(' ', start);
269  if(end == std::string::npos)
270  {
271  throw Decoding_Error(ERROR_MESSAGE);
272  }
273  const auto serverPublicKey = Botan::Ed25519_PublicKey(Botan::base64_decode(s.substr(start, end-start)));
274 
275  start = end + 1;
276  end = s.find(' ', start);
277  if(end == std::string::npos)
278  {
279  throw Decoding_Error(ERROR_MESSAGE);
280  }
281  if((end - start) != 88)
282  {
283  throw Decoding_Error("Nonce has invalid length");
284  }
285  const auto vec = Botan::base64_decode(s.substr(start, end-start));
286  const auto nonceOrBlind = Nonce(vector_to_array<64>(Botan::base64_decode(s.substr(start, end-start))));
287 
288  start = end + 1;
289  end = s.find(' ', start);
290  if(end != std::string::npos)
291  {
292  throw Decoding_Error(ERROR_MESSAGE);
293  }
294  const auto response = Botan::unlock(Botan::base64_decode(s.substr(start)));
295 
296  m_links.push_back({response, serverPublicKey, nonceOrBlind});
297  }
298  }
299 std::vector<Response> Chain::responses() const
300  {
301  std::vector<Response> responses;
302  for(unsigned i = 0; i < m_links.size(); ++i)
303  {
304  const auto& l = m_links[i];
305  const auto nonce = i ? nonce_from_blind(m_links[i-1].response(), l.nonce_or_blind()) : l.nonce_or_blind();
306  const auto response = Response::from_bits(l.response(), nonce);
307  if(!response.validate(l.public_key()))
308  { throw Roughtime_Error("Invalid signature or public key"); }
309  responses.push_back(response);
310  }
311  return responses;
312  }
313 Nonce Chain::next_nonce(const Nonce& blind) const
314  {
315  return m_links.empty()
316  ? blind
317  : nonce_from_blind(m_links.back().response(), blind);
318  }
319 void Chain::append(const Link& new_link, size_t max_chain_size)
320  {
321  if(max_chain_size <= 0)
322  { throw Invalid_Argument("Max chain size must be positive"); }
323 
324  while(m_links.size() >= max_chain_size)
325  {
326  if(m_links.size() == 1)
327  {
328  auto new_link_updated = new_link;
329  new_link_updated.nonce_or_blind() =
330  nonce_from_blind(m_links[0].response(), new_link.nonce_or_blind()); //we need to convert blind to nonce
331  m_links.clear();
332  m_links.push_back(new_link_updated);
333  return;
334  }
335  if(m_links.size() >= 2)
336  {
337  m_links[1].nonce_or_blind() =
338  nonce_from_blind(m_links[0].response(), m_links[1].nonce_or_blind()); //we need to convert blind to nonce
339  }
340  m_links.erase(m_links.begin());
341  }
342  m_links.push_back(new_link);
343  }
344 
345 std::string Chain::to_string() const
346  {
347  std::string s;
348  s.reserve((7+1 + 88+1 + 44+1 + 480)*m_links.size());
349  for(const auto& link : m_links)
350  {
351  s += "ed25519";
352  s += ' ';
353  s += Botan::base64_encode(link.public_key().get_public_key());
354  s += ' ';
355  s += Botan::base64_encode(link.nonce_or_blind().get_nonce().data(), link.nonce_or_blind().get_nonce().size());
356  s += ' ';
357  s += Botan::base64_encode(link.response());
358  s += '\n';
359  }
360  return s;
361  }
362 
363 std::vector<uint8_t> online_request(const std::string& uri,
364  const Nonce& nonce,
365  std::chrono::milliseconds timeout)
366  {
367  const std::chrono::system_clock::time_point start_time = std::chrono::system_clock::now();
368  auto socket = OS::open_socket_udp(uri, timeout);
369  if(!socket)
370  { throw Not_Implemented("No socket support enabled in build"); }
371 
372  const auto encoded = encode_request(nonce);
373  socket->write(encoded.data(), encoded.size());
374 
375  if(std::chrono::system_clock::now() - start_time > timeout)
376  { throw System_Error("Timeout during socket write"); }
377 
378  std::vector<uint8_t> buffer;
379  buffer.resize(360+64*10+1); //response basic size is 360 bytes + 64 bytes for each level of merkle tree
380  //add one additional byte to be able to differentiate if datagram got truncated
381  const auto n = socket->read(buffer.data(), buffer.size());
382 
383  if(!n || std::chrono::system_clock::now() - start_time > timeout)
384  { throw System_Error("Timeout waiting for response"); }
385 
386  if(n == buffer.size())
387  { throw System_Error("Buffer too small"); }
388 
389  buffer.resize(n);
390  return buffer;
391  }
392 
393 std::vector<Server_Information> servers_from_str(const std::string& str)
394  {
395  std::vector<Server_Information> servers;
396  std::stringstream ss(str);
397  const std::string ERROR_MESSAGE = "Line does not have at least 5 space separated fields";
398  for(std::string s; std::getline(ss, s);)
399  {
400  size_t start = 0, end = 0;
401  end = s.find(' ', start);
402  if(end == std::string::npos)
403  {
404  throw Decoding_Error(ERROR_MESSAGE);
405  }
406  const auto name = s.substr(start, end-start);
407 
408  start = end + 1;
409  end = s.find(' ', start);
410  if(end == std::string::npos)
411  {
412  throw Decoding_Error(ERROR_MESSAGE);
413  }
414  const auto publicKeyType = s.substr(start, end-start);
415  if(publicKeyType != "ed25519")
416  { throw Not_Implemented("Only ed25519 publicKeyType is implemented"); }
417 
418  start = end + 1;
419  end = s.find(' ', start);
420 
421  if(end == std::string::npos)
422  {
423  throw Decoding_Error(ERROR_MESSAGE);
424  }
425  const auto publicKeyBase64 = s.substr(start, end-start);
426  const auto publicKey = Botan::Ed25519_PublicKey(Botan::base64_decode(publicKeyBase64));
427 
428  start = end + 1;
429  end = s.find(' ', start);
430  if(end == std::string::npos)
431  {
432  throw Decoding_Error(ERROR_MESSAGE);
433  }
434  const auto protocol = s.substr(start, end-start);
435  if(protocol != "udp")
436  { throw Not_Implemented("Only UDP protocol is implemented"); }
437 
438  const auto addresses = [&]()
439  {
440  std::vector<std::string> addr;
441  for(;;)
442  {
443  start = end + 1;
444  end = s.find(' ', start);
445  const auto address = s.substr(start, (end == std::string::npos) ? std::string::npos : end-start);
446  if(address.empty())
447  { return addr; }
448  addr.push_back(address);
449  if(end == std::string::npos)
450  { return addr; }
451  }
452  }
453  ();
454  if(addresses.size() == 0)
455  {
456  throw Decoding_Error(ERROR_MESSAGE);
457  }
458 
459  servers.push_back({name, publicKey, std::move(addresses)});
460  }
461  return servers;
462  }
463 
464 }
465 
466 }
std::unique_ptr< SocketUDP > BOTAN_TEST_API open_socket_udp(const std::string &hostname, const std::string &service, std::chrono::microseconds timeout)
Definition: socket_udp.cpp:318
static std::unique_ptr< HashFunction > create_or_throw(const std::string &algo_spec, const std::string &provider="")
Definition: hash.cpp:344
virtual void randomize(uint8_t output[], size_t length)=0
const uint8_t * cast_char_ptr_to_uint8(const char *s)
Definition: mem_ops.h:190
Nonce nonce_from_blind(const std::vector< uint8_t > &previous_response, const Nonce &blind)
Definition: roughtime.cpp:237
const unsigned request_min_size
Definition: roughtime.h:23
bool validate(const Ed25519_PublicKey &pk) const
Definition: roughtime.cpp:228
Definition: bigint.h:1142
MechanismType type
std::array< uint8_t, request_min_size > encode_request(const Nonce &nonce)
Definition: roughtime.cpp:169
void update(uint8_t in)
Definition: pubkey.h:347
std::vector< Response > responses() const
Definition: roughtime.cpp:299
std::vector< Server_Information > servers_from_str(const std::string &str)
Definition: roughtime.cpp:393
void typecast_copy(uint8_t out[], T in[], size_t N)
Definition: mem_ops.h:145
std::string name
size_t base64_encode(char out[], const uint8_t in[], size_t input_length, size_t &input_consumed, bool final_inputs)
Definition: base64.cpp:166
static Response from_bits(const std::vector< uint8_t > &response, const Nonce &nonce)
Definition: roughtime.cpp:177
const std::array< uint8_t, 64 > & get_nonce() const
Definition: roughtime.h:43
Definition: alg_id.cpp:13
std::vector< T > unlock(const secure_vector< T > &in)
Definition: secmem.h:72
std::vector< uint8_t > online_request(const std::string &uri, const Nonce &nonce, std::chrono::milliseconds timeout)
Definition: roughtime.cpp:363
size_t base64_decode(uint8_t out[], const char in[], size_t input_length, size_t &input_consumed, bool final_inputs, bool ignore_ws)
Definition: base64.cpp:181
bool check_signature(const uint8_t sig[], size_t length)
Definition: pubkey.cpp:336
std::string to_string() const
Definition: roughtime.cpp:345
const char * cast_uint8_ptr_to_char(const uint8_t *b)
Definition: mem_ops.h:195
std::chrono::time_point< std::chrono::system_clock, microseconds64 > sys_microseconds64
Definition: roughtime.h:63
fe T
Definition: ge.cpp:37
Nonce next_nonce(const Nonce &blind) const
Definition: roughtime.cpp:313
void append(const Link &new_link, size_t max_chain_size)
Definition: roughtime.cpp:319
MechanismType hash