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 ++++++++++++++++++++++++++++++++++++++++++++++----- link/link-protocol.h | 61 +++++-- link/test-link.c | 112 +++++++++++-- 3 files changed, 560 insertions(+), 66 deletions(-) (limited to 'link') 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 #include @@ -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]; -- cgit v1.2.3