From 9791a1e70979ee4ba832851912f0de20301343a8 Mon Sep 17 00:00:00 2001 From: eunhhu Date: Tue, 29 Sep 2026 13:57:58 +0100 Subject: Move a link to a new epoch now and then, so keys that leak later open nothing past MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit A sender offers the public half of a pair made for the next epoch (OFFER) until the receiver accepts with a half of its own (ACCEPT); their X25519 and the epoch's secret make the next one's, and the private halves go. The header's low four bits say a packet's epoch; epoch 0 is the nodes' static secret, as the keys were. The first epoch is offered in the run's first packet (it begins with the first answer when the receiver is not busy), then one an hour or GiB. One who later has both nodes' keys opens only epoch 0, and no record went there after an epoch began: test-link tries every packet sent under the static keys, with epochs a second long, loss, reordering, restarts and replays. The receiver writes the epoch it accepted in its memo (a place is 256 bytes now), so it goes on without an X25519 when it starts again; one that forgot is not heard from, and its senders, after 2 s and four probes unanswered, offer again in epoch 0 with no records until an epoch begins. Keys of four epochs are tried (accepted, now, before, zero), as two may share the four bits. An accept costs an X25519 on each side, 220 µs on this Pi: one of a sender with records costs a token (256 a second, 8 at once) and the next packet offers again when there is none; one of a sender with nothing else to send waits for none, one a second for it. The X25519 is made after the turn's answers, never between a packet and its answer. serve's report and M2's generator count keys, X25519s and epochs. --- link/link-protocol.c | 453 ++++++++++++++++++++++++++++++++++++++++++++++----- 1 file changed, 414 insertions(+), 39 deletions(-) (limited to 'link/link-protocol.c') 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); -- cgit v1.2.3