diff options
| -rw-r--r-- | link/link-protocol.c | 453 | ||||
| -rw-r--r-- | link/link-protocol.h | 61 | ||||
| -rw-r--r-- | link/test-link.c | 112 | ||||
| -rw-r--r-- | research/experiments/019-idle-links/links.c | 7 | ||||
| -rw-r--r-- | serve/serve.c | 6 |
5 files changed, 568 insertions, 71 deletions
diff --git a/link/link-protocol.c b/link/link-protocol.c index 3cb8e07..1f43e6c 100644 --- a/link/link-protocol.c +++ b/link/link-protocol.c @@ -19,7 +19,11 @@ enum { DATAGRAM_MOST = PURE_LINK_DATAGRAM_MOST, BODY_MOST = DATAGRAM_MOST - HEAD * at least this much of it fits. */ enum { PART_LEAST = 64 }; enum { F_PADDING = 0, F_STREAM = 1, F_RECORD = 2, F_ACK = 3, F_STORED = 4, F_PING = 5, F_RECORDS = 6, F_CHALLENGE = 7, - F_RESPONSE = 8, STORED_GAP = 1 }; + F_RESPONSE = 8, F_OFFER = 9, F_ACCEPT = 10, STORED_GAP = 1 }; +/* A packet's first byte is VERSION with the sending side's epoch (mod 16) + * in its low four bits; OFFER and ACCEPT are an epoch's number (u32) and a + * public key made for it. */ +enum { EPOCH_MASK = 15, EPOCH_FRAME = 1 + 4 + PURE_SEAL_KEY }; enum { RECORDS_HEAD = 10 }; /* type, the first number, the count */ enum { RANGES = 32, RUNS = 2, UNITS = 64, CREDIT = 1024, BATCH = 256, RECORD_HEAD = 19 }; enum { WINDOW_FIRST = 10 * DATAGRAM, WINDOW_LEAST = 2 * DATAGRAM }; @@ -31,7 +35,11 @@ enum { REORDER_FIRST = 3, REORDER_PACKETS_MOST = 256, REORDER_QUARTERS_MOST = 8, enum { REACH_TRIES = 3 }; /* Challenges a sender keeps to say back, the newest first. */ enum { RESPONSES = 4 }; -enum { KEYINGS = 256 }; +/* Keys made for runs that do not open, and new epochs accepted: a second, + * and at once. */ +enum { KEYINGS = 256, ACCEPTS = 256, ACCEPTS_AT_ONCE = 8 }; +/* A receiver accepts a new epoch for a sender at most a second. */ +static const uint64_t ACCEPT_EVERY_NS = 1000000000u, OURS_LIFE = 1000000000u; /* CUBIC's constants (RFC 9438): the cubic's scale, and the window kept at a * congestion event. */ static const double CUBIC_C = 0.4, CUBIC_BETA = 0.7, RENO_PACE = 3 * (1 - 0.7) / (1 + 0.7); @@ -42,6 +50,10 @@ static const double CUBIC_C = 0.4, CUBIC_BETA = 0.7, RENO_PACE = 3 * (1 - 0.7) / static const uint64_t FIRST_RTT = 100 * MS, ACK_DELAY_MOST = 25 * MS, GRANULARITY = 1 * MS, PTO_MOST = 1000 * MS, STORED_WAIT = 1000 * MS, RECORD_MOST = UINT64_C(64) << 20, HELD_MOST = UINT64_C(16) << 20, REACH_AGAIN = 1000 * MS, REACH_RARELY = 600000 * MS; +/* An epoch lasts an hour or a GiB sent; a sender that hears nothing for 2 s + * with packets out, and four probes, takes its epoch for lost. */ +static const uint64_t EPOCH_EVERY = UINT64_C(3600000) * MS, EPOCH_MOST = UINT64_C(1) << 30, FALLBACK_WAIT = 2000 * MS; +enum { FALLBACK_PROBES = 4 }; /* and after as many probes unanswered in a row */ static void put16(unsigned char *p, uint32_t v) { p[0] = (unsigned char)v, p[1] = (unsigned char)(v >> 8); } static void put32(unsigned char *p, uint32_t v) { for (int i = 0; i < 4; ++i) p[i] = (unsigned char)(v >> 8 * i); } @@ -108,6 +120,18 @@ static bool derive(const unsigned char secret[32], const unsigned char from[PURE return true; } +/* The secret of epoch n: the X25519 of the two keys made for it (fresh), + * with the secret before it (epoch 0's is the nodes' static secret). */ +static bool epoch_secret_of(const unsigned char before[32], const unsigned char fresh[32], uint32_t n, unsigned char out[32]) { + unsigned char info[17 + 4 + 32]; + memcpy(info, "pure link 0 epoch", 17); + put32(info + 17, n); + memcpy(info + 21, before, 32); + bool ok = pure_link_derive(fresh, info, sizeof(info), out, 32); + explicit_bzero(info, sizeof(info)); + return ok; +} + /* The same as a context of its own, for a sender's one link. */ static PureAead *aead_of(const unsigned char secret[32], const unsigned char from[PURE_SEAL_KEY], const unsigned char to[PURE_SEAL_KEY], uint64_t from_run, uint64_t to_run, @@ -126,9 +150,10 @@ static void nonce_of(unsigned char out[PURE_AEAD_NONCE], const unsigned char bas /* A packet: the header, then body sealed (with key, or the context's own * when NULL); its size, or 0. */ static size_t seal_packet(PureAead *aead, const unsigned char *key, const unsigned char base[PURE_AEAD_NONCE], uint32_t id, - uint64_t run, uint64_t pn, const unsigned char *body, size_t size, unsigned char *out) { + uint32_t epoch, uint64_t run, uint64_t pn, const unsigned char *body, size_t size, + unsigned char *out) { unsigned char nonce[PURE_AEAD_NONCE]; - out[0] = VERSION; + out[0] = (unsigned char)(VERSION | (epoch & EPOCH_MASK)); put32(out + 1, id); put64(out + 5, run); put64(out + 13, pn); @@ -248,8 +273,26 @@ struct PureLinkSender { uint64_t unsent_from; /* no record before this number has a part unsent */ unsigned pto_count, probes; PureLinkCounts counts; + /* Epochs (forward secrecy). Keys come from the secret of the epoch it + * sends in (epoch 0's is the two nodes' static secret), each made from + * two keys made for it, whose private halves go once agreed; the one + * before stays for answers still in it. The pair it offers for the + * next; when its epoch began, and its bytes; how often and after how + * many bytes it moves on; when an answer last opened; renegotiating: + * the receiver lost the epoch, so only offers go (in epoch 0, no record + * under the static keys again) until a new one begins, the next at + * offer_again. Last: what a sender at rest is looked at for (its + * timers) stays in fewer cache lines. */ + uint32_t epoch, before_epoch, offer_epoch, in_epoch; + unsigned char epoch_secret[32], before_secret[32], offer_private[32], offer_public[PURE_SEAL_KEY]; + bool offering, renegotiating; + uint64_t epoch_at, epoch_bytes, epoch_every, epoch_most, heard_at, offer_again; }; +static bool out_keys(PureLinkSender *l); +static bool offer(PureLinkSender *l, uint32_t n); +static void begin_epoch(PureLinkSender *l, const unsigned char their[PURE_SEAL_KEY], uint64_t now); + static Record *record_at(PureLinkSender *l, size_t k) { return &l->records[(l->head + k) % l->capacity]; } /* The queued record numbered seq, or NULL (stored already, or not queued). */ @@ -625,20 +668,28 @@ static void on_stored(PureLinkSender *l, const unsigned char *p, size_t size, ui void pure_link_sender_take(PureLinkSender *l, const unsigned char *packet, size_t n, uint64_t now) { unsigned char plain[DATAGRAM_MOST], nonce[PURE_AEAD_NONCE]; - if (!l->out || n < HEADER + PURE_AEAD_TAG || n > DATAGRAM_MOST || packet[0] != VERSION || get32(packet + 1) != l->peer_id) + if (!l->out || n < HEADER + PURE_AEAD_TAG || n > DATAGRAM_MOST || (packet[0] & ~EPOCH_MASK) != VERSION || + get32(packet + 1) != l->peer_id) return; /* not ours, or an error from an earlier send (nobody listening) */ uint64_t run = get64(packet + 5), pn = get64(packet + 13); - if (!l->in || l->in_run != run) { + /* Answers come in its epoch or the one before. */ + unsigned e = packet[0] & EPOCH_MASK; + uint32_t epoch = e == (l->epoch & EPOCH_MASK) ? l->epoch : l->before_epoch; + if (e != (epoch & EPOCH_MASK)) return; + if (!l->in || l->in_run != run || l->in_epoch != epoch) { pure_aead_free(l->in); - l->in = aead_of(l->secret, l->peer, l->own_public, run, l->run, l->in_base); + l->in = aead_of(epoch == l->epoch ? l->epoch_secret : l->before_secret, l->peer, l->own_public, run, l->run, + l->in_base); ++l->counts.keyed; l->in_run = run; + l->in_epoch = epoch; if (!l->in) return; } nonce_of(nonce, l->in_base, pn); size_t size = n - HEADER - PURE_AEAD_TAG; if (!pure_aead_open(l->in, NULL, nonce, packet, HEADER, packet + HEADER, n - HEADER, plain)) return; ++l->counts.received; + l->heard_at = now; for (size_t at = 0; at < size;) { unsigned type = plain[at++]; if (type == F_ACK && at + 13 <= size && at + 13 + 16u * plain[at + 12] <= size) { @@ -661,6 +712,10 @@ void pure_link_sender_take(PureLinkSender *l, const unsigned char *packet, size_ if (l->responding < RESPONSES) ++l->responding; } at += 8; + } else if (type == F_ACCEPT) { /* the epoch offered begins */ + if (at + EPOCH_FRAME - 1 > size) break; + if (l->offering && get32(plain + at) == l->offer_epoch) begin_epoch(l, plain + at + 4, now); + at += EPOCH_FRAME - 1; } else if (type != F_PING) break; /* padding, or what this side does not know: the rest */ } @@ -684,6 +739,16 @@ static size_t fill(PureLinkSender *l, unsigned char *body, Flight *f, bool pad, body[at] = F_RESPONSE; put64(body + at + 1, l->respond[k]); } + if (l->offering) { /* the next epoch's key, until it is accepted */ + body[at] = F_OFFER; + put32(body + at + 1, l->offer_epoch); + memcpy(body + at + 5, l->offer_public, PURE_SEAL_KEY); + at += EPOCH_FRAME; + } + if (l->renegotiating) { /* no record under the static keys */ + l->responding = 0; + return at; + } /* The credit counts from the oldest record not stored: after a restart * the sender does not know yet how far the receiver stored. */ uint64_t base = l->count ? record_at(l, 0)->seq - 1 : l->stored; @@ -753,7 +818,7 @@ static size_t fill(PureLinkSender *l, unsigned char *body, Flight *f, bool pad, break; } } - if (!f->count && !(probe && l->responding)) return 0; + if (!f->count && !(probe && (l->responding || l->offering))) return 0; l->responding = 0; return at; } @@ -773,8 +838,9 @@ void pure_link_sender_refused(PureLinkSender *l, uint64_t pn) { * carried is then unsent again). Its number is spent either way. */ static size_t transmit(PureLinkSender *l, Flight *f, const unsigned char *body, size_t size, unsigned char *out, uint64_t now) { - size_t total = seal_packet(l->out, NULL, l->out_base, l->own_id, l->run, f->pn, body, size, out); + size_t total = seal_packet(l->out, NULL, l->out_base, l->own_id, l->epoch, l->run, f->pn, body, size, out); ++l->next_pn; + l->epoch_bytes += total; f->sent = now; f->bytes = (uint32_t)total; if (!total) { /* not sealed: what it carried is unsent again */ @@ -818,6 +884,12 @@ size_t pure_link_sender_packet(PureLinkSender *l, unsigned char out[PURE_LINK_DA if (!probe && l->in_flight + l->datagram > l->window) l->unused = false; if (!l->out || (!probe && l->in_flight + l->datagram > l->window) || !flight_room(l)) return 0; if (!probe && !paced(l, now)) return 0; + if (!l->offering && !l->renegotiating && (now - l->epoch_at >= l->epoch_every || l->epoch_bytes >= l->epoch_most)) + offer(l, l->epoch + 1); /* on to the next epoch: a key made for it goes in the packets until accepted */ + if (l->renegotiating) { /* an offer an RTT, no records */ + if (!probe && now < l->offer_again) return 0; + l->offer_again = now + most(rtt_now(l), 100 * MS); + } unsigned char body[BODY_MOST]; Flight f = {.pn = l->next_pn, .eliciting = true}; if (l->datagram < DATAGRAM_MOST && l->filled && !l->reaching && l->sampled && now >= l->reach_at && @@ -869,6 +941,20 @@ uint64_t pure_link_sender_due(const PureLinkSender *l) { } void pure_link_sender_tick(PureLinkSender *l, uint64_t now) { + if (l->epoch && !l->renegotiating && l->eliciting && l->heard_at && now - l->heard_at > FALLBACK_WAIT && + l->pto_count >= FALLBACK_PROBES) { + /* Nothing heard for long with packets out: the receiver lost the + * epoch (it started again without its memo), or its answers are + * kept from us. Offers only now, in epoch 0, until one begins. */ + memcpy(l->before_secret, l->epoch_secret, 32); + l->before_epoch = l->epoch; + memcpy(l->epoch_secret, l->secret, 32); + l->epoch = 0; + out_keys(l); + offer(l, 1); + l->renegotiating = true; + l->offer_again = 0; + } if (l->loss_time && l->loss_time <= now) detect_lost(l, now); else if (l->eliciting && l->last_eliciting + pto_period(l) <= now) { /* Nothing heard for a while: a probe, what flies longest sent again. */ @@ -913,9 +999,49 @@ PureLinkSender *pure_link_sender(const char *source, const char *input, uint32_t l->threshold = UINT64_MAX; l->reorder_packets = REORDER_FIRST; l->datagram = DATAGRAM; + l->epoch_every = EPOCH_EVERY; + l->epoch_most = EPOCH_MOST; return l; } +/* Keys of its packets in the epoch it is in. */ +static bool out_keys(PureLinkSender *l) { + pure_aead_free(l->out); + l->out = aead_of(l->epoch_secret, l->own_public, l->peer, l->run, 0, l->out_base); + ++l->counts.keyed; + return l->out != NULL; +} + +/* A pair for epoch n, offered in each packet until it is accepted. */ +static bool offer(PureLinkSender *l, uint32_t n) { + if (!pure_link_ephemeral(l->offer_private, l->offer_public)) return false; + l->offer_epoch = n; + l->offering = true; + return true; +} + +/* The receiver accepted the offer with its public key: the epoch begins, + * the private half gone. */ +static void begin_epoch(PureLinkSender *l, const unsigned char their[PURE_SEAL_KEY], uint64_t now) { + unsigned char fresh[32], next[32]; + bool ok = pure_link_agree(l->offer_private, their, fresh) && + epoch_secret_of(l->epoch_secret, fresh, l->offer_epoch, next); + explicit_bzero(l->offer_private, sizeof(l->offer_private)); + explicit_bzero(fresh, sizeof(fresh)); + l->offering = false; + l->epoch_at = now; /* failed: offered again a whole epoch on */ + if (!ok) return; + memcpy(l->before_secret, l->epoch_secret, 32); + l->before_epoch = l->epoch; + memcpy(l->epoch_secret, next, 32); + explicit_bzero(next, sizeof(next)); + l->epoch = l->offer_epoch; + l->epoch_bytes = 0; + l->renegotiating = false; + ++l->counts.epochs; + out_keys(l); +} + /* The receiver's key, with the secret made (or given) into l->secret: the * keys of packets to it. */ static bool keyed(PureLinkSender *l, const unsigned char peer[PURE_SEAL_KEY], const unsigned char *secret) { @@ -926,8 +1052,10 @@ static bool keyed(PureLinkSender *l, const unsigned char peer[PURE_SEAL_KEY], co l->out = l->in = NULL; if (secret) memcpy(l->secret, secret, 32); if (!secret) ++l->counts.secrets; - return (secret || (l->own && pure_link_secret(l->own, l->peer, l->secret))) && - (l->out = aead_of(l->secret, l->own_public, l->peer, l->run, 0, l->out_base)) && ++l->counts.keyed; + if (!secret && !(l->own && pure_link_secret(l->own, l->peer, l->secret))) return false; + memcpy(l->epoch_secret, l->secret, 32); + l->epoch = l->before_epoch = 0; + return out_keys(l) && offer(l, 1); } bool pure_link_sender_peer(PureLinkSender *l, const unsigned char peer[PURE_SEAL_KEY]) { return keyed(l, peer, NULL); } @@ -938,6 +1066,11 @@ bool pure_link_sender_shared(PureLinkSender *l, const unsigned char peer[PURE_SE uint64_t pure_link_sender_queued(const PureLinkSender *l) { return l->queued; } +void pure_link_sender_epochs(PureLinkSender *l, uint64_t every_ns, uint64_t bytes) { + l->epoch_every = every_ns; + l->epoch_most = bytes; +} + size_t pure_link_sender_datagram(const PureLinkSender *l) { return l->datagram; } uint64_t pure_link_sender_stored(const PureLinkSender *l) { return l->stored; } @@ -956,6 +1089,9 @@ void pure_link_sender_free(PureLinkSender *l) { pure_aead_free(l->out); pure_aead_free(l->in); explicit_bzero(l->secret, sizeof(l->secret)); + explicit_bzero(l->epoch_secret, sizeof(l->epoch_secret)); + explicit_bzero(l->before_secret, sizeof(l->before_secret)); + explicit_bzero(l->offer_private, sizeof(l->offer_private)); free(l); } @@ -984,12 +1120,26 @@ typedef struct { * bytes that came from it (RFC 9000 §8). */ bool checked; uint64_t challenge, bytes_in, bytes_out; + /* Epochs: the sender's, as its packets opened last (the keys in and out + * below are of it); the one before, whose packets may still come; an + * offer accepted and not yet used; an offer taken, accepted in the + * turn. Their secrets and keys are last. */ + uint32_t epoch, before_epoch, accept_epoch, waiting_epoch; + bool has_before, accepted, waits; unsigned char in_key[PURE_AEAD_KEY], out_key[PURE_AEAD_KEY], in_base[PURE_AEAD_NONCE], out_base[PURE_AEAD_NONCE]; uint64_t next_pn, largest_at; _Alignas(8) unsigned char address[PURE_LINK_ADDRESS]; /* where it sends from: a socket's address */ size_t address_size; Range got[RANGES]; /* the numbers received, newest first */ unsigned got_count; + /* The epoch's secret; the accepted one's, its keys in, the key offered + * and ours (the same offer again gets the same answer); the keys in of + * the epoch before; the offer taken: the epoch of the packet it came in, + * and its key. */ + unsigned char epoch_secret[32], accept_secret[32], offered[PURE_SEAL_KEY], accept_public[PURE_SEAL_KEY]; + unsigned char accept_in_key[PURE_AEAD_KEY], accept_in_base[PURE_AEAD_NONCE]; + unsigned char before_in_key[PURE_AEAD_KEY], before_in_base[PURE_AEAD_NONCE]; + unsigned char waiting_in, waiting[PURE_SEAL_KEY]; } Run; typedef struct { uint32_t from, to; } Span; /* bytes [from, to) */ typedef struct { @@ -1026,7 +1176,9 @@ typedef struct Stream { struct Active { uint32_t peer; /* its place among the peers */ unsigned char secret[32]; + bool remembered; /* its secret came from the memo */ uint64_t seen; + uint64_t accepted_at; /* its last new epoch: one a second, whatever its runs */ size_t place; /* among the active */ Run runs[RUNS]; Stream **streams; @@ -1057,6 +1209,22 @@ struct PureLinkReceiver { * whose packets open (a thousand waking at once) cost none. */ double key_tokens; uint64_t key_at; + /* The pair its epochs are accepted with: one for a second (the X25519 + * of making it shared by the offers of that second), then the private + * half is gone. An accept costs an X25519 on each side (220 µs on a + * Raspberry Pi 5), made in the turn after the answers, so it holds back + * no packet's answer. One of a sender with records to send costs a + * token (ACCEPTS a second, ACCEPTS_AT_ONCE at once) and waits for one + * (its next packet offers again), so ten thousand senders waking at + * once do not hold the others back; a sender with nothing else to send + * (its epoch lost) waits for none, one accept a second for it. */ + unsigned char ours_private[32], ours_public[PURE_SEAL_KEY]; + bool ours_ready; + uint64_t ours_at; + double accept_tokens; + uint64_t accept_at; + struct { Run *run; uint64_t id; } *offers; /* runs whose offers wait for the turn (a slot may hold another run by then) */ + size_t offer_count, offer_capacity; PureAead *aead; /* keyed by each packet's run */ unsigned char open_key[PURE_AEAD_KEY], seal_key[PURE_AEAD_KEY]; /* the keys it has now */ bool open_keyed, seal_keyed; @@ -1258,14 +1426,47 @@ static void drop_first(Stream *st) { /* The memo of secrets (pure_link_remember): a header, then a place a peer * in the order allowed, each the first 28 bytes of its key, a check (FNV-1a * of its whole key and the secret) and the secret. A place whose check - * fails (never made, another key, cut short by a crash) is made again. */ -enum { MEMO_HEAD = 64, MEMO_PLACE = 64 }; -static const unsigned char memo_magic[8] = {'P', 'L', 'M', '1', 0, 0, 0, 0}; + * fails (never made, another key, cut short by a crash) is made again. + * From MEMO_EPOCH on, the epoch last accepted for the peer's run: the run, + * the epoch, a check (FNV-1a of the rest), its secret, the one before, the + * key the sender offered and ours; written secrets first, the run last. A + * node that starts again goes on in the sender's epoch, no key made. */ +enum { MEMO_HEAD = 64, MEMO_PLACE = 256, MEMO_EPOCH = 64, MEMO_EPOCH_SIZE = 144 }; +static const unsigned char memo_magic[8] = {'P', 'L', 'M', '2', 0, 0, 0, 0}; static uint32_t memo_check(const unsigned char key[PURE_SEAL_KEY], const unsigned char secret[32]) { return fnv(fnv(2166136261u, key, PURE_SEAL_KEY), secret, 32); } +static unsigned char *memo_place(const PureLinkReceiver *s, uint32_t peer) { + return s->memo && MEMO_HEAD + ((size_t)peer + 1) * MEMO_PLACE <= s->memo_size ? s->memo + MEMO_HEAD + (size_t)peer * MEMO_PLACE + : NULL; +} + +static uint32_t epoch_check(const unsigned char *e) { return fnv(fnv(2166136261u, e, 12), e + 16, MEMO_EPOCH_SIZE - 16); } + +/* The epoch the memo has for the peer's run (its place's epoch part), or NULL. */ +static const unsigned char *memo_epoch(const PureLinkReceiver *s, uint32_t peer, uint64_t run) { + const unsigned char *place = memo_place(s, peer), *e = place ? place + MEMO_EPOCH : NULL; + return e && get64(e) == run && get32(e + 12) == epoch_check(e) ? e : NULL; +} + +static void remember_epoch(PureLinkReceiver *s, uint32_t peer, const Run *r) { + unsigned char *place = memo_place(s, peer); + if (!place) return; + unsigned char *e = place + MEMO_EPOCH; + memset(e, 0, 16); + __atomic_thread_fence(__ATOMIC_RELEASE); + memcpy(e + 16, r->accept_secret, 32); + memcpy(e + 48, r->epoch_secret, 32); + memcpy(e + 80, r->offered, PURE_SEAL_KEY); + memcpy(e + 112, r->accept_public, PURE_SEAL_KEY); + put64(e, r->run); + put32(e + 8, r->accept_epoch); + __atomic_thread_fence(__ATOMIC_RELEASE); + put32(e + 12, epoch_check(e)); +} + bool pure_link_remember(PureLinkReceiver *s, const char *path, char *error, size_t size) { int fd = open(path, O_RDWR | O_CREAT | O_NOFOLLOW | O_CLOEXEC, 0600); struct stat info; @@ -1303,12 +1504,10 @@ static Active *activate(PureLinkReceiver *s, Peer *peer, uint64_t now) { free(a); return NULL; } - size_t index = (size_t)(peer - s->peers); - unsigned char *place = s->memo && MEMO_HEAD + (index + 1) * MEMO_PLACE <= s->memo_size ? - s->memo + MEMO_HEAD + index * MEMO_PLACE : NULL; + unsigned char *place = memo_place(s, (uint32_t)(peer - s->peers)); if (place && !memcmp(place, peer->key, 28) && get32(place + 28) == memo_check(peer->key, place + 32)) { memcpy(a->secret, place + 32, 32); - ++s->counts.remembered; + a->remembered = true; } else if (++s->counts.secrets && pure_link_secret(s->own, peer->key, a->secret)) { if (place) { memset(place, 0, 28); @@ -1650,44 +1849,196 @@ static bool hand_over(PureLinkReceiver *s, Stream *st) { return true; } -/* A packet from peer, if it opens with the keys of peer's run (made for a - * run not seen yet, and for a peer at rest its active state): its frames. */ +/* Keys in (from the sender) and out (answers) of an epoch's secret. */ +static bool epoch_keys(const PureLinkReceiver *s, const Peer *peer, Run *r, const unsigned char secret[32]) { + return derive(secret, peer->key, s->own_public, r->run, 0, r->in_key, r->in_base) && + derive(secret, s->own_public, peer->key, r->answer_run, r->run, r->out_key, r->out_base); +} + +/* A run not seen: in the epoch the memo has for it (its accepted one, or the + * one before with that one accepted), or epoch 0. False when the packet's + * epoch is none of these. */ +static bool run_begun(PureLinkReceiver *s, const Peer *peer, const Active *a, Run *r, unsigned e) { + const unsigned char *memo = memo_epoch(s, (uint32_t)(peer - s->peers), r->run); + uint32_t n = memo ? get32(memo + 8) : 0; + const unsigned char *secret = a->secret; + if (memo && e == (n & EPOCH_MASK)) r->epoch = n, secret = memo + 16; + else if (memo && n && e == ((n - 1) & EPOCH_MASK)) { /* it had not used the one accepted yet */ + r->epoch = n - 1, secret = memo + 48; + r->accepted = true; + r->accept_epoch = n; + memcpy(r->accept_secret, memo + 16, 32); + memcpy(r->offered, memo + 80, PURE_SEAL_KEY); + memcpy(r->accept_public, memo + 112, PURE_SEAL_KEY); + if (!derive(r->accept_secret, peer->key, s->own_public, r->run, 0, r->accept_in_key, r->accept_in_base)) return false; + } else if (e) return false; + memcpy(r->epoch_secret, secret, 32); + if (memo && r->epoch == n && n && /* its packets of the epoch before may still come */ + derive(memo + 48, peer->key, s->own_public, r->run, 0, r->before_in_key, r->before_in_base)) + r->has_before = true, r->before_epoch = n - 1; + return epoch_keys(s, peer, r, secret); +} + +/* The sender uses the epoch accepted: it is its epoch now. */ +static void confirm(PureLinkReceiver *s, const Peer *peer, Run *r) { + memcpy(r->before_in_key, r->in_key, PURE_AEAD_KEY); + memcpy(r->before_in_base, r->in_base, PURE_AEAD_NONCE); + r->before_epoch = r->epoch; + r->has_before = true; + r->epoch = r->accept_epoch; + memcpy(r->epoch_secret, r->accept_secret, 32); + explicit_bzero(r->accept_secret, sizeof(r->accept_secret)); + r->accepted = false; + epoch_keys(s, peer, r, r->epoch_secret); + ++s->counts.epochs; +} + +/* A token of a bucket that fills rate a second, up to most: whether one is + * there. */ +static bool has_token(double *tokens, uint64_t *at, double rate, double most, uint64_t now) { + if (!*at) *tokens = most; + *tokens += (double)(now - *at) * rate / 1e9; + if (*tokens > most) *tokens = most; + *at = now; + return *tokens >= 1; +} + +/* An offer of epoch n (in a packet of epoch e): the next, or a chain begun + * again from epoch 0. The same offer again gets the same ACCEPT; a new one + * waits for the turn (accept_waiting). blocked: the packet had no records + * (the sender waits for the epoch). */ +static void offer_taken(PureLinkReceiver *s, Active *a, Run *r, uint32_t n, const unsigned char offered[PURE_SEAL_KEY], + unsigned e, bool blocked, uint64_t now) { + if (r->accepted && r->accept_epoch == n && !memcmp(r->offered, offered, PURE_SEAL_KEY)) { + mark_due(s, r); /* said again */ + return; + } + if (!(n == 1 && !e) && !(n == r->epoch + 1 && e == (r->epoch & EPOCH_MASK))) return; + if (r->waits || (a->accepted_at && now - a->accepted_at < ACCEPT_EVERY_NS)) return; + if (!blocked && !has_token(&s->accept_tokens, &s->accept_at, ACCEPTS, ACCEPTS_AT_ONCE, now)) return; /* it offers again */ + void *offers = room(s->offers, &s->offer_capacity, s->offer_count, sizeof(*s->offers), 16); + if (!offers) return; + s->offers = offers; + s->offers[s->offer_count].run = r; + s->offers[s->offer_count++].id = r->run; + if (!blocked) --s->accept_tokens; + a->accepted_at = now; + r->waits = true; + r->waiting_epoch = n; + r->waiting_in = (unsigned char)e; + memcpy(r->waiting, offered, PURE_SEAL_KEY); +} + +/* The offers taken, accepted (after the answers of the packets they came + * in): each one X25519. */ +static void accept_waiting(PureLinkReceiver *s, uint64_t now) { + for (size_t k = 0; k < s->offer_count; ++k) { + Run *r = s->offers[k].run; + if (r->run != s->offers[k].id || !r->waits) continue; /* its slot holds another run now */ + r->waits = false; + Active *a = r->active; + const Peer *peer = &s->peers[a->peer]; + uint32_t n = r->waiting_epoch; + const unsigned char *base = n == 1 && !r->waiting_in ? a->secret + : n == r->epoch + 1 && r->waiting_in == (r->epoch & EPOCH_MASK) ? r->epoch_secret + : NULL; + if (!base) continue; /* its epoch moved on since */ + if (!s->ours_ready || now - s->ours_at >= OURS_LIFE) { /* a new pair for this second's offers */ + explicit_bzero(s->ours_private, sizeof(s->ours_private)); + if (!(s->ours_ready = pure_link_ephemeral(s->ours_private, s->ours_public))) continue; + s->ours_at = now; + ++s->counts.secrets; + } + unsigned char fresh[32]; + ++s->counts.secrets; + bool ok = pure_link_agree(s->ours_private, r->waiting, fresh) && epoch_secret_of(base, fresh, n, r->accept_secret) && + derive(r->accept_secret, peer->key, s->own_public, r->run, 0, r->accept_in_key, r->accept_in_base); + explicit_bzero(fresh, sizeof(fresh)); + if (!ok) continue; + memcpy(r->accept_public, s->ours_public, PURE_SEAL_KEY); + memcpy(r->offered, r->waiting, PURE_SEAL_KEY); + r->accept_epoch = n; + r->accepted = true; + if (base == a->secret && r->epoch) { /* begun again from epoch 0: so are its answers, the old epoch before */ + memcpy(r->before_in_key, r->in_key, PURE_AEAD_KEY); + memcpy(r->before_in_base, r->in_base, PURE_AEAD_NONCE); + r->before_epoch = r->epoch; + r->has_before = true; + r->epoch = 0; + memcpy(r->epoch_secret, a->secret, 32); + epoch_keys(s, peer, r, r->epoch_secret); + } + remember_epoch(s, a->peer, r); + mark_due(s, r); + } + s->offer_count = 0; +} + /* Whether keys may be made for a run not seen (a token is there). */ static bool may_key(PureLinkReceiver *s, uint64_t now) { - if (!s->key_at) s->key_tokens = KEYINGS; - s->key_tokens += (double)(now - s->key_at) * KEYINGS / 1e9; - if (s->key_tokens > KEYINGS) s->key_tokens = KEYINGS; - s->key_at = now; - return s->key_tokens >= 1; + return has_token(&s->key_tokens, &s->key_at, KEYINGS, KEYINGS, now); } +enum { AS_NOW, AS_ACCEPTED, AS_BEFORE, AS_ZERO }; + +/* A packet from peer, if it opens with the keys of peer's run (made for a + * run not seen yet, and for a peer at rest its active state): its frames. */ static bool take_from(PureLinkReceiver *s, Peer *peer, const unsigned char *packet, size_t n, const void *from, size_t from_size, uint64_t now) { uint64_t pn = get64(packet + 13), run = get64(packet + 5); + unsigned e = packet[0] & EPOCH_MASK; Active *a = peer->active; Run *r = a ? run_found(a, run) : NULL; if (!r && !may_key(s, now)) return false; bool woke = !a; if (woke && !(a = activate(s, peer, now))) return false; Run made = {.active = a, .run = run, .seen = now, .used = true}; - if (!r) made.answer_run = random64(); - bool keyed = r || (++s->counts.keyed && derive(a->secret, peer->key, s->own_public, run, 0, made.in_key, made.in_base) && - derive(a->secret, s->own_public, peer->key, made.answer_run, run, made.out_key, made.out_base)); + /* The keys of the packet's epoch: the one accepted, its run's now, the + * one before, or epoch 0's for a sender that begins its epochs again; + * for a run not seen, as the memo has it. Two may share the four bits + * (a chain begun again): each is tried. */ + unsigned char zero_key[PURE_AEAD_KEY], zero_base[PURE_AEAD_NONCE]; + const unsigned char *keys[4], *bases[4]; + int as[4], tries = 0; + if (!r) { + made.answer_run = random64(); + ++s->counts.keyed; + if (run_begun(s, peer, a, &made, e)) { + if (made.accepted && e == (made.accept_epoch & EPOCH_MASK)) + keys[tries] = made.accept_in_key, bases[tries] = made.accept_in_base, as[tries++] = AS_ACCEPTED; + keys[tries] = made.in_key, bases[tries] = made.in_base, as[tries++] = AS_NOW; + } + } else { + if (r->accepted && e == (r->accept_epoch & EPOCH_MASK)) + keys[tries] = r->accept_in_key, bases[tries] = r->accept_in_base, as[tries++] = AS_ACCEPTED; + if (e == (r->epoch & EPOCH_MASK)) keys[tries] = r->in_key, bases[tries] = r->in_base, as[tries++] = AS_NOW; + if (r->has_before && e == (r->before_epoch & EPOCH_MASK)) + keys[tries] = r->before_in_key, bases[tries] = r->before_in_base, as[tries++] = AS_BEFORE; + if (!e && r->epoch && derive(a->secret, peer->key, s->own_public, run, 0, zero_key, zero_base)) + keys[tries] = zero_key, bases[tries] = zero_base, as[tries++] = AS_ZERO; + } unsigned char plain[DATAGRAM_MOST], nonce[PURE_AEAD_NONCE]; - nonce_of(nonce, r ? r->in_base : made.in_base, pn); size_t size = n - HEADER - PURE_AEAD_TAG; - const unsigned char *key = r ? r->in_key : made.in_key, *give = key; - if (s->open_keyed && !memcmp(s->open_key, key, PURE_AEAD_KEY)) give = NULL; /* the key it has */ - else if (keyed) memcpy(s->open_key, key, PURE_AEAD_KEY), s->open_keyed = true; - if (!keyed || !pure_aead_open(s->aead, give, nonce, packet, HEADER, packet + HEADER, n - HEADER, plain)) { + int opened = -1; + for (int t = 0; t < tries && opened < 0; ++t) { + const unsigned char *give = keys[t]; + nonce_of(nonce, bases[t], pn); + if (s->open_keyed && !memcmp(s->open_key, keys[t], PURE_AEAD_KEY)) give = NULL; /* the key it has */ + else memcpy(s->open_key, keys[t], PURE_AEAD_KEY), s->open_keyed = true; + if (pure_aead_open(s->aead, give, nonce, packet, HEADER, packet + HEADER, n - HEADER, plain)) opened = as[t]; + } + explicit_bzero(zero_key, sizeof(zero_key)); + if (opened < 0) { explicit_bzero(&made, sizeof(made)); if (!r) s->key_tokens = s->key_tokens > 1 ? s->key_tokens - 1 : 0; /* keys for nothing */ if (woke) let_go(s, a); return false; } - if (woke) ++s->counts.woken; + if (woke) ++s->counts.woken, s->counts.remembered += a->remembered; /* counted once it opens */ bool fresh = !r; if (!r) r = install_run(a, &made); + explicit_bzero(&made, sizeof(made)); + if (opened == AS_ACCEPTED) confirm(s, peer, r); if (!fresh && had(r, pn)) { /* again (opened first: nothing unsealed answers): its acknowledgment was lost, perhaps */ r->ack_due = true; mark_due(s, r); @@ -1710,7 +2061,8 @@ static bool take_from(PureLinkReceiver *s, Peer *peer, const unsigned char *pack if (!elsewhere || newest) r->bytes_in += n; ++s->counts.received; Stream *st = NULL; - bool eliciting = false; + bool eliciting = false, records = false; + const unsigned char *offer = NULL; /* taken after the frames: whether records came with it */ for (size_t at = 0; at < size;) { unsigned type = plain[at++]; if (type == F_STREAM) { @@ -1733,7 +2085,7 @@ static bool take_from(PureLinkReceiver *s, Peer *peer, const unsigned char *pack mark_ready(s, st); } at += RECORD_HEAD - 1 + length; - eliciting = true; + eliciting = records = true; } else if (type == F_RECORDS) { if (at + RECORDS_HEAD - 1 > size) break; uint64_t first = get64(plain + at), length = 0; @@ -1746,10 +2098,15 @@ static bool take_from(PureLinkReceiver *s, Peer *peer, const unsigned char *pack at += used + length; } if (st) mark_ready(s, st); - eliciting = true; + eliciting = records = true; if (i < count) break; /* cut short: the rest is not read */ } else if (type == F_PING) { eliciting = true; + } else if (type == F_OFFER) { /* the sender's key for its next epoch */ + if (at + EPOCH_FRAME - 1 > size) break; + offer = plain + at; + at += EPOCH_FRAME - 1; + eliciting = true; } else if (type == F_RESPONSE) { /* the challenge said back: the address is the sender's */ if (at + 8 > size) break; if (!r->checked && get64(plain + at) == r->challenge) r->checked = true; @@ -1758,6 +2115,7 @@ static bool take_from(PureLinkReceiver *s, Peer *peer, const unsigned char *pack } else break; /* padding, or what this side does not know: the rest */ } + if (offer) offer_taken(s, a, r, get32(offer), offer + 4, e, !records, now); if (eliciting) { r->ack_due = true; mark_due(s, r); @@ -1767,7 +2125,7 @@ static bool take_from(PureLinkReceiver *s, Peer *peer, const unsigned char *pack void pure_link_receiver_take(PureLinkReceiver *s, const unsigned char *packet, size_t n, const void *from, size_t from_size, uint64_t now) { - if (n < HEADER + PURE_AEAD_TAG || n > DATAGRAM_MOST || packet[0] != VERSION || !s->index_size) return; + if (n < HEADER + PURE_AEAD_TAG || n > DATAGRAM_MOST || (packet[0] & ~EPOCH_MASK) != VERSION || !s->index_size) return; uint32_t id = get32(packet + 1); size_t mask = s->index_size - 1; uint64_t run = get64(packet + 5); @@ -1803,6 +2161,12 @@ static void answer(PureLinkReceiver *s, uint64_t now, PureLinkSend *send, void * put64(body + at, r->challenge); at += 8; } + if (r->accepted) { /* the sender's next epoch, until it uses it */ + body[at] = F_ACCEPT; + put32(body + at + 1, r->accept_epoch); + memcpy(body + at + 5, r->accept_public, PURE_SEAL_KEY); + at += EPOCH_FRAME; + } if (r->ack_due && r->got_count) { body[at++] = F_ACK; put64(body + at, r->got[0].last); @@ -1833,7 +2197,8 @@ static void answer(PureLinkReceiver *s, uint64_t now, PureLinkSend *send, void * const unsigned char *give = r->out_key; if (s->seal_keyed && !memcmp(s->seal_key, r->out_key, PURE_AEAD_KEY)) give = NULL; /* the key it has */ else memcpy(s->seal_key, r->out_key, PURE_AEAD_KEY), s->seal_keyed = true; - size_t total = seal_packet(s->aead, give, r->out_base, s->own_id, r->answer_run, r->next_pn++, body, at, packet); + size_t total = + seal_packet(s->aead, give, r->out_base, s->own_id, r->epoch, r->answer_run, r->next_pn++, body, at, packet); if (total && send(context, packet, total, r->address, r->address_size)) { ++s->counts.packets; if (!r->checked) r->bytes_out += total; @@ -1878,9 +2243,17 @@ static void hand_over_ready(PureLinkReceiver *s) { void pure_link_receiver_turn(PureLinkReceiver *s, const PureLinkDone *done, size_t count, uint64_t now, PureLinkSend *send, void *context) { if (!s->swept) s->swept = s->trimmed = now; + if (s->ours_ready && now - s->ours_at >= OURS_LIFE) { /* its second is over: the private half goes */ + explicit_bzero(s->ours_private, sizeof(s->ours_private)); + s->ours_ready = false; + } apply_done(s, done, count); hand_over_ready(s); answer(s, now, send, context); + if (s->offer_count) { /* the offers' X25519 after the answers, then their ACCEPTs */ + accept_waiting(s, now); + answer(s, now, send, context); + } sweep(s, now); } @@ -1897,6 +2270,8 @@ void pure_link_receiver_free(PureLinkReceiver *s) { if (!s) return; while (s->active_count) let_go(s, s->actives[0]); pure_aead_free(s->aead); + explicit_bzero(s->ours_private, sizeof(s->ours_private)); + free(s->offers); if (s->memo) munmap(s->memo, s->memo_size); free(s->actives); free(s->peers); diff --git a/link/link-protocol.h b/link/link-protocol.h index f121b2e..f54514b 100644 --- a/link/link-protocol.h +++ b/link/link-protocol.h @@ -16,18 +16,35 @@ * * A packet is a header in the clear, then frames sealed with AES-128-GCM * (the header as associated data): - * u8 0x70 (version 0), u32le the key id of the node that sent it (FNV-1a - * of its public key; two keys may share an id, and a receiver tries the - * keys it allows with it), u64le that node's run (random, new each time it - * starts, so no nonce repeats under a key across restarts), u64le the - * packet's number in its run. - * Keys come from the secret the two nodes' keys share (X25519) by - * HKDF-SHA256, with both public keys and the sending node's run: a sender's - * packets use its own run. A receiver's answers use a run drawn for each - * sender's run it keeps (made again when a sender at rest comes back, so no - * nonce repeats), and add the run they answer, so an answer opens only in - * that run. The nonce is the key's base with the packet's number in its - * last eight bytes (XOR, big-endian, as QUIC does). + * u8 0x70 (version 0) with the low four bits of the epoch it is sealed + * in, u32le the key id of the node that sent it (FNV-1a of its public + * key; two keys may share an id, and a receiver tries the keys it allows + * with it), u64le that node's run (random, new each time it starts, so no + * nonce repeats under a key across restarts), u64le the packet's number in + * its run. + * Keys come from an epoch's secret by HKDF-SHA256, with both public keys and + * the sending node's run: a sender's packets use its own run. A receiver's + * answers use a run drawn for each sender's run it keeps (made again when a + * sender at rest comes back, so no nonce repeats), and add the run they + * answer, so an answer opens only in that run. The nonce is the key's base + * with the packet's number in its last eight bytes (XOR, big-endian, as QUIC + * does). + * + * Epoch 0's secret is the one the two nodes' keys share (X25519). A sender + * offers the public half of a pair made for the next epoch (OFFER) in its + * packets until the receiver accepts it with a half of its own (ACCEPT); the + * X25519 of the two halves and the epoch's secret make the next one's + * (HKDF, "pure link 0 epoch" and its number), and the private halves are let + * go. The sender seals in it from the ACCEPT on; the receiver takes it once + * a packet of it opens, and opens the late ones of the epoch before. So what + * went in epoch 1 and on cannot be opened by one who later has both nodes' + * keys: only a run's first packets, before its first answer, are sealed + * under the static keys. A new epoch every hour or GiB + * (pure_link_sender_epochs). A receiver that remembers (pure_link_remember) + * writes the epoch it accepted for each sender's run, and goes on in it after + * it starts again; a sender that hears nothing for 2 s over 4 probes (the + * receiver forgot) offers again in epoch 0, with no records, and the chain + * begins again from the nodes' keys. * * What an attacker on the path may do, and what it gets (link/test-link.c * does each): @@ -41,7 +58,11 @@ * three times the bytes that came from it (RFC 9000 §8). * - send as a key or a source not allowed: nothing opens or is delivered. * (Anyone who has the receiver's private key can seal as any sender to - * it: static-static keys, as Noise KK's first message.) + * it, in a run of its own: static-static keys, as Noise KK's first + * message. Epochs do not change this; they keep it out of others' + * runs.) + * - keep what went, and later get both nodes' keys: it opens only the + * packets of epoch 0. * - flood made-up packets under a known key's id, runs never seen: keys * made for a run that did not open cost a token, 256 a second, so at * most that many HKDFs a second; X25519 once a sender (remembered). @@ -70,6 +91,11 @@ * the address the answers go to * 0x08 RESPONSE u64: a challenge said back (the last few had), in the next * packet that goes (records, or a probe) + * 0x09 OFFER u32 epoch, a public key (X25519): the sender's half of that + * epoch's secret, until it is accepted + * 0x0a ACCEPT u32 epoch, a public key: the receiver's half, until a + * packet of that epoch opens (the same offer again gets the + * same; one a second for a run) * 0x00 PADDING to the end of the packet: a full packet sent in a burst is * a whole datagram * Losses are detected as RFC 9002 says, with RACK's patience for packets @@ -87,13 +113,13 @@ enum { PURE_LINK_DATAGRAM = 1200, PURE_LINK_DATAGRAM_MOST = 1452, PURE_LINK_NAME /* Counts for a host's report: packets and records sent, records sent again, * packets lost and acknowledged, packets received, deliveries handed over, * the last number stored; packets called lost that came late, and - * congestion events undone for it; runs keyed (keys made from a secret) - * and secrets made (X25519); a receiver's senders woken (their active + * congestion events undone for it; runs keyed (keys made from a secret), + * secrets made (X25519 of the nodes' keys), epochs begun; a receiver's senders woken (their active * state made), of them with a secret remembered (no X25519), let go when * idle, and active now. */ typedef struct { uint64_t packets, records, resent, lost, acknowledged, received, deliveries, stored, late, undone, keyed, secrets, - woken, remembered, swept, active; + epochs, woken, remembered, swept, active; } PureLinkCounts; /* ---- The sending side: one output's saved sends to a receiver's input, as @@ -132,6 +158,9 @@ size_t pure_link_sender_datagram(const PureLinkSender *); void pure_link_sender_refused(PureLinkSender *, uint64_t number); /* When the next timer is due (ns), or 0 for none. */ uint64_t pure_link_sender_due(const PureLinkSender *); +/* How often it moves on to a new epoch (ns), and after how many bytes sent + * (an hour and a GiB at first). */ +void pure_link_sender_epochs(PureLinkSender *, uint64_t every_ns, uint64_t bytes); /* The last number queued; the last the receiver stored. */ uint64_t pure_link_sender_queued(const PureLinkSender *); uint64_t pure_link_sender_stored(const PureLinkSender *); diff --git a/link/test-link.c b/link/test-link.c index c69af83..957c383 100644 --- a/link/test-link.c +++ b/link/test-link.c @@ -12,7 +12,13 @@ * attacker's own (none applied twice; nothing sent to the attacker beyond * three times what it sent), keys not allowed and sources not allowed * (nothing delivered), and a flood of made-up packets for a known key (few - * keys made). Under all of it no key and nonce seals twice. */ + * keys made). Under all of it no key and nonce seals twice. + * + * And later: one who then has both nodes' private keys, and every packet + * the sender sent. Once an epoch has begun, nothing it sent opens under + * the keys of the nodes' static secret, and no record went under them + * after that (forward secrecy), however often the epochs change and + * whether the receiver starts again with its memo or without. */ #include "link-protocol.h" #include <stdio.h> #include <stdlib.h> @@ -72,6 +78,8 @@ typedef struct { size_t nonce_count, nonce_capacity; Packet *history; size_t history_count; + Packet *sent_log; /* every packet the sender sent, for one who later has the keys */ + size_t sent_log_count, sent_log_capacity; uint64_t attacker_in, attacker_out, bent, replayed; unsigned loss, doubled, spread_ms; /* percent, percent, the most a packet is held back */ uint64_t now, sent; @@ -178,6 +186,8 @@ typedef struct { uint64_t pause_after, receiver_restart_after, sender_restart_after, idle_ms; unsigned replay; /* percent of steps that send a packet of the past again */ bool tamper; /* every packet comes changed three ways first */ + uint64_t epoch_ms; /* epochs this long (0: an hour) */ + bool forgetful; /* the receiver keeps no memo: it starts again knowing no epoch */ } Case; static bool nothing_sent(void *context, const unsigned char *packet, size_t size, const unsigned char *to, size_t to_size) { @@ -232,6 +242,64 @@ static void replay(World *w, PureLinkSender *s, PureLinkReceiver *r, const char typedef struct { PureLinkCounts sent, heard; uint64_t packets, seconds_ms; } Outcome; +/* One who later has both nodes' private keys: the keys of the sender's + * packets under the nodes' static secret (link-protocol.c's derive). */ +static bool static_keys(const unsigned char secret[32], const unsigned char *from, const unsigned char *to, uint64_t run, + unsigned char key[PURE_AEAD_KEY], unsigned char base[PURE_AEAD_NONCE]) { + unsigned char info[16 + 2 * PURE_SEAL_KEY + 16], out[PURE_AEAD_KEY + PURE_AEAD_NONCE]; + memcpy(info, "pure link 0 keys", 16); + memcpy(info + 16, from, PURE_SEAL_KEY); + memcpy(info + 16 + PURE_SEAL_KEY, to, PURE_SEAL_KEY); + for (int i = 0; i < 8; ++i) info[16 + 2 * PURE_SEAL_KEY + i] = (unsigned char)(run >> 8 * i); + memset(info + 24 + 2 * PURE_SEAL_KEY, 0, 8); + if (!pure_link_derive(secret, info, sizeof(info), out, sizeof(out))) return false; + memcpy(key, out, PURE_AEAD_KEY); + memcpy(base, out + PURE_AEAD_KEY, PURE_AEAD_NONCE); + return true; +} + +/* Each packet the sender sent, tried under the static keys: one of an epoch + * past 0 must not open, and one of epoch 0 sent after its run's first packet + * of a later epoch may carry no record. The number that opened. */ +static unsigned later_with_keys(World *w, const PureSealKey *a, const PureSealKey *b, const unsigned char *public_a, + const unsigned char *public_b, const char *name) { + unsigned char secret[32], again[32], key[PURE_AEAD_KEY], base[PURE_AEAD_NONCE], nonce[PURE_AEAD_NONCE], + plain[PURE_LINK_DATAGRAM_MOST]; + if (!pure_link_secret(a, public_b, secret) || !pure_link_secret(b, public_a, again) || memcmp(secret, again, 32)) exit(1); + PureAead *aead = pure_aead(secret); + unsigned opened = 0; + for (size_t k = 0; k < w->sent_log_count; ++k) { + const Packet *p = &w->sent_log[k]; + uint64_t run = get64le(p->bytes + 5), pn = get64le(p->bytes + 13), first_later = UINT64_MAX; + for (size_t j = 0; j < w->sent_log_count; ++j) /* its run's first packet of a later epoch */ + if (get64le(w->sent_log[j].bytes + 5) == run && (w->sent_log[j].bytes[0] & 15) && + get64le(w->sent_log[j].bytes + 13) < first_later) + first_later = get64le(w->sent_log[j].bytes + 13); + if (!static_keys(secret, public_a, public_b, run, key, base)) exit(1); + memcpy(nonce, base, PURE_AEAD_NONCE); + for (int i = 0; i < 8; ++i) nonce[4 + i] ^= (unsigned char)(pn >> (56 - 8 * i)); + if (!pure_aead_open(aead, key, nonce, p->bytes, 21, p->bytes + 21, p->size - 21, plain)) continue; + ++opened; + CHECK(!(p->bytes[0] & 15), "%s: a packet of epoch %u opened under the static keys", name, p->bytes[0] & 15); + if (pn < first_later) continue; + size_t size = p->size - 21 - 16; + for (size_t at = 0; at < size;) { /* its frames: none a record */ + unsigned type = plain[at++]; + if (type == 1) at += 2 + plain[at] + plain[at + 1 + plain[at]] + 4; /* STREAM */ + else if (type == 8) at += 8; /* RESPONSE */ + else if (type == 9) at += 36; /* OFFER */ + else { + CHECK(type != 2 && type != 6, "%s: a record under the static keys after the epoch began (packet %llu)", name, + (unsigned long long)pn); + break; + } + } + } + pure_aead_free(aead); + explicit_bzero(secret, sizeof(secret)), explicit_bzero(again, sizeof(again)); + return opened; +} + static int by_nonce(const void *x, const void *y) { const Nonce *a = x, *b = y; return a->whose != b->whose ? (a->whose < b->whose ? -1 : 1) @@ -245,7 +313,7 @@ static PureLinkReceiver *receiver_of(World *w, const PureSealKey *b, const unsig char error[256]; PureLinkReceiver *r = pure_link_receiver(b, public_b, &(PureLinkHost){input_of, deliver, w}, error, sizeof(error)); if (!r || !pure_link_allow(r, "test.ordered", public_a, error, sizeof(error)) || - !pure_link_remember(r, memo, error, sizeof(error))) { + (memo && !pure_link_remember(r, memo, error, sizeof(error)))) { fprintf(stderr, "test-link: %s\n", error); exit(1); } @@ -255,6 +323,8 @@ static PureLinkReceiver *receiver_of(World *w, const PureSealKey *b, const unsig /* The sender as its app makes it: the sends its outbox keeps, from the one * after the last stored, up to limit. */ +static uint64_t epoch_ms; /* the senders' epochs, as the case says */ + static PureLinkSender *sender_of(const PureSealKey *a, const unsigned char *public_a, const unsigned char *public_b, uint64_t from, uint64_t limit) { PureLinkSender *s = pure_link_sender("test.ordered", "order", 0x5eed, a, public_a); @@ -262,6 +332,7 @@ static PureLinkSender *sender_of(const PureSealKey *a, const unsigned char *publ fprintf(stderr, "test-link: cannot make a sender\n"); exit(1); } + if (epoch_ms) pure_link_sender_epochs(s, epoch_ms * MS, UINT64_C(1) << 30); static unsigned char bytes[20200]; for (uint64_t seq = from; seq <= limit; ++seq) { size_t size = record_size(seq); @@ -285,10 +356,12 @@ static Outcome run(const Case *c, const char *dir) { .history = malloc(HISTORY * sizeof(Packet))}; if (!w.packets || !w.history) exit(1); char from[8] = "sender0"; + epoch_ms = c->epoch_ms; + const char *keep = c->forgetful ? NULL : memo; seed = c->seed; uint64_t queued = c->pause_after ? c->pause_after : c->records, resumed = 0; PureLinkSender *s = sender_of(a, public_a, public_b, 1, queued); - PureLinkReceiver *r = receiver_of(&w, b, public_b, public_a, memo, c->idle_ms); + PureLinkReceiver *r = receiver_of(&w, b, public_b, public_a, keep, c->idle_ms); PureLinkCounts sent_before = {0}, heard_before = {0}; bool receiver_restarted = !c->receiver_restart_after, sender_restarted = !c->sender_restart_after; unsigned char out[PURE_LINK_DATAGRAM_MOST]; @@ -299,6 +372,12 @@ static Outcome run(const Case *c, const char *dir) { uint64_t number; for (size_t size; (size = pure_link_sender_packet(s, out, false, w.now, &number));) { used(&w, 0, out); + if (w.sent_log_count == w.sent_log_capacity) { + w.sent_log_capacity = w.sent_log_capacity ? 2 * w.sent_log_capacity : 1024; + if (!(w.sent_log = realloc(w.sent_log, w.sent_log_capacity * sizeof(Packet)))) exit(1); + } + w.sent_log[w.sent_log_count] = (Packet){.size = size}; + memcpy(w.sent_log[w.sent_log_count++].bytes, out, size); put_packet(&w, true, out, size); } /* Then the next thing to happen. */ @@ -348,7 +427,7 @@ static Outcome run(const Case *c, const char *dir) { pure_link_receiver_counts(r, &heard_before); pure_link_receiver_free(r); w.done_count = 0; - r = receiver_of(&w, b, public_b, public_a, memo, c->idle_ms); + r = receiver_of(&w, b, public_b, public_a, keep, c->idle_ms); } if (!sender_restarted && pure_link_sender_stored(s) >= c->sender_restart_after) { sender_restarted = true; @@ -362,7 +441,7 @@ static Outcome run(const Case *c, const char *dir) { Outcome o = {.packets = w.sent, .seconds_ms = w.now / MS}; pure_link_sender_counts(s, &o.sent); pure_link_receiver_counts(r, &o.heard); - o.sent.packets += sent_before.packets, o.sent.resent += sent_before.resent; + o.sent.packets += sent_before.packets, o.sent.resent += sent_before.resent, o.sent.epochs += sent_before.epochs; o.heard.woken += heard_before.woken, o.heard.swept += heard_before.swept; CHECK(w.heard == c->records && w.applied == c->records, "%s: applied %llu, heard %llu of %llu", c->name, (unsigned long long)w.applied, (unsigned long long)w.heard, (unsigned long long)c->records); @@ -379,14 +458,15 @@ static Outcome run(const Case *c, const char *dir) { } CHECK(w.attacker_out <= 3 * w.attacker_in, "%s: %llu bytes to the attacker for its %llu", c->name, (unsigned long long)w.attacker_out, (unsigned long long)w.attacker_in); + unsigned opened_later = later_with_keys(&w, a, b, public_a, public_b, c->name); printf("{\"case\":\"%s\",\"records\":%llu,\"virtual_ms\":%llu,\"packets\":%llu,\"resent\":%llu,\"lost\":%llu," "\"deliveries\":%llu,\"woken\":%llu,\"remembered\":%llu,\"swept\":%llu,\"changed\":%llu,\"replayed\":%llu," - "\"attacker_in\":%llu,\"attacker_out\":%llu}\n", + "\"attacker_in\":%llu,\"attacker_out\":%llu,\"epochs\":%llu,\"opened_later\":%u}\n", c->name, (unsigned long long)c->records, (unsigned long long)o.seconds_ms, (unsigned long long)o.sent.packets, (unsigned long long)o.sent.resent, (unsigned long long)o.sent.lost, (unsigned long long)w.deliveries, (unsigned long long)o.heard.woken, (unsigned long long)o.heard.remembered, (unsigned long long)o.heard.swept, (unsigned long long)w.bent, (unsigned long long)w.replayed, (unsigned long long)w.attacker_in, - (unsigned long long)w.attacker_out); + (unsigned long long)w.attacker_out, (unsigned long long)o.sent.epochs, opened_later); pure_link_sender_free(s); pure_link_receiver_free(r); pure_seal_key_free(a); @@ -394,6 +474,7 @@ static Outcome run(const Case *c, const char *dir) { free(w.packets); free(w.history); free(w.nonces); + free(w.sent_log); return o; } @@ -524,7 +605,7 @@ int main(void) { return 1; } /* A clean network: nothing is sent twice. */ - Case clean = {"clean", 3000, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, false}; + Case clean = {"clean", 3000, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, false, 0, false}; Outcome o = run(&clean, dir); CHECK(o.sent.resent == 0 && o.sent.lost == 0, "clean: %llu sent again, %llu lost", (unsigned long long)o.sent.resent, (unsigned long long)o.sent.lost); @@ -533,7 +614,7 @@ int main(void) { * starting again: the receiver remembers its secret, so it wakes the * sender without an X25519. */ for (uint64_t s = 1; s <= 4; ++s) { - Case rough = {"rough", 3000, s * 7919, 10, 3, 20, 37, 1500, 800, 2200, 300, 0, false}; + Case rough = {"rough", 3000, s * 7919, 10, 3, 20, 37, 1500, 800, 2200, 300, 0, false, 0, false}; o = run(&rough, dir); CHECK(o.sent.resent > 0 && o.heard.swept >= 1 && o.heard.woken >= 1 && o.heard.remembered >= 1, "rough: sent again %llu, swept %llu, woken %llu, remembered %llu", (unsigned long long)o.sent.resent, @@ -543,12 +624,21 @@ int main(void) { /* An attacker on the path: packets changed on the way, and packets of * the past sent again, from the sender's address and its own, across the * same restarts and pause. */ - Case changed = {"changed", 1500, 31, 3, 0, 5, 0, 0, 0, 0, 0, 0, true}; + Case changed = {"changed", 1500, 31, 3, 0, 5, 0, 0, 0, 0, 0, 0, true, 0, false}; run(&changed, dir); for (uint64_t s = 1; s <= 2; ++s) { - Case again = {"replayed", 3000, s * 104729, 5, 3, 20, 37, 1500, 800, 2200, 300, 25, false}; + Case again = {"replayed", 3000, s * 104729, 5, 3, 20, 37, 1500, 800, 2200, 300, 25, false, 0, false}; run(&again, dir); } + /* Epochs a fifth of a second long (a new one a second, as the receiver + * accepts), and a receiver that starts again with no memo: it knows no + * epoch, and the sender begins them again. */ + Case epochs = {"epochs", 3000, 271, 5, 3, 20, 37, 1500, 800, 2200, 300, 10, false, 200, false}; + o = run(&epochs, dir); + CHECK(o.sent.epochs >= 10, "epochs: %llu begun", (unsigned long long)o.sent.epochs); + Case forgetful = {"forgetful", 3000, 409, 5, 3, 20, 37, 0, 800, 0, 0, 0, false, 0, true}; + o = run(&forgetful, dir); + CHECK(o.sent.epochs >= 2, "forgetful: %llu epochs begun (none again)", (unsigned long long)o.sent.epochs); impostors(dir); flood(dir); char command[600]; diff --git a/research/experiments/019-idle-links/links.c b/research/experiments/019-idle-links/links.c index 0378109..d6cc28b 100644 --- a/research/experiments/019-idle-links/links.c +++ b/research/experiments/019-idle-links/links.c @@ -370,11 +370,11 @@ static int run_all(char **argv) { fprintf(stderr, "{\"t\":%.1f,\"made\":%" PRIu64 ",\"stored\":%" PRIu64 "}\n", (double)(now - began) / 1e9, made, stored); } } - uint64_t again = 0, keyed = 0, secrets = 0; + uint64_t again = 0, keyed = 0, secrets = 0, epochs = 0; for (size_t k = 0; k < count; ++k) { PureLinkCounts c; pure_link_sender_counts(devices[k].sender, &c); - again += c.resent, keyed += c.keyed, secrets += c.secrets; + again += c.resent, keyed += c.keyed, secrets += c.secrets, epochs += c.epochs; } /* The p50 and p99 of the records made in each second: where the slow ones are. */ size_t seconds_made = (size_t)seconds + 1; @@ -404,7 +404,8 @@ static int run_all(char **argv) { latency_count ? latency[latency_count * 99 / 100] : 0, latency_count ? latency[latency_count - 1] : 0, longest * 100, gap * 100); for (size_t b = 0; b <= last; ++b) printf("%s%u", b ? "," : "", timeline[b]); - printf("],\"keyed\":%" PRIu64 ",\"secrets\":%" PRIu64 ",\"p50_ms_by_second_made\":[", keyed, secrets); + printf("],\"keyed\":%" PRIu64 ",\"secrets\":%" PRIu64 ",\"epochs\":%" PRIu64 ",\"p50_ms_by_second_made\":[", keyed, + secrets, epochs); for (size_t second = 0; second < seconds_made; ++second) printf("%s%.2f", second ? "," : "", p50_by_second[second]); printf("],\"p99_ms_by_second_made\":["); for (size_t second = 0; second < seconds_made; ++second) printf("%s%.2f", second ? "," : "", p99_by_second[second]); diff --git a/serve/serve.c b/serve/serve.c index f466ee6..969bf89 100644 --- a/serve/serve.c +++ b/serve/serve.c @@ -2760,11 +2760,13 @@ int main(int argc, char **argv) { ",\"link_lost\":%" PRIu64 ",\"link_acknowledged\":%" PRIu64 ",\"link_stored\":%" PRIu64 ",\"listener_packets\":%" PRIu64 ",\"listener_received\":%" PRIu64 ",\"listener_deliveries\":%" PRIu64 ",\"listener_woken\":%" PRIu64 ",\"listener_remembered\":%" PRIu64 ",\"listener_swept\":%" PRIu64 - ",\"listener_active\":%" PRIu64 "}\n", + ",\"listener_active\":%" PRIu64 ",\"listener_keyed\":%" PRIu64 ",\"listener_secrets\":%" PRIu64 + ",\"listener_epochs\":%" PRIu64 "}\n", active, retained, accepted, requests, bursts, events, ticks, expired, threads, owned ? "true" : "false", owner.executor.publications, shown, delivered, attempts, owner.executor.answers, groups, grouped, checkpoints, sent.packets, sent.records, sent.resent, sent.lost, sent.acknowledged, sent.stored, - heard.packets, heard.received, heard.deliveries, heard.woken, heard.remembered, heard.swept, heard.active); + heard.packets, heard.received, heard.deliveries, heard.woken, heard.remembered, heard.swept, heard.active, + heard.keyed, heard.secrets, heard.epochs); free(hosts); free(thread); return 0; |