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