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