diff options
| -rw-r--r-- | link/link-protocol.c | 141 | ||||
| -rw-r--r-- | link/link-protocol.h | 46 | ||||
| -rw-r--r-- | link/test-link.c | 274 |
3 files changed, 412 insertions, 49 deletions
diff --git a/link/link-protocol.c b/link/link-protocol.c index 55062f3..92cd149 100644 --- a/link/link-protocol.c +++ b/link/link-protocol.c @@ -18,7 +18,8 @@ enum { DATAGRAM_MOST = PURE_LINK_DATAGRAM_MOST, BODY_MOST = DATAGRAM_MOST - HEAD /* A record that does not fit what is left of a packet goes in part, when * 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, STORED_GAP = 1 }; +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 }; 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 }; @@ -28,6 +29,9 @@ enum { REORDER_FIRST = 3, REORDER_PACKETS_MOST = 256, REORDER_QUARTERS_MOST = 8, /* A probe of a larger datagram lost is tried again a second on, three * times, then ten minutes on. */ enum { REACH_TRIES = 3 }; +/* Challenges a sender keeps to say back, the newest first. */ +enum { RESPONSES = 4 }; +enum { KEYINGS = 256 }; /* 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); @@ -198,7 +202,14 @@ struct PureLinkSender { uint64_t in_flight, window, threshold, recovery_start, eliciting; uint64_t largest_acked, latest_rtt, smoothed_rtt, rtt_var, min_rtt; bool acked_any, sampled; - uint64_t loss_time, last_eliciting, credit, stored_changed; + /* limit: the highest number the receiver takes (the last it stored and + * its credit past that, the most it said: a word of the past sent again + * lowers nothing; 0 before it said any). Challenges to say back in the + * next packet (the receiver checks the path so): the last few, as an + * answer of the past sent again may bring an old one. */ + uint64_t loss_time, last_eliciting, limit, stored_changed; + uint64_t respond[RESPONSES]; + unsigned responding; /* Reordering: later packets acknowledged before a packet is lost (3 at * first), and the time past the RTT, in quarters of the least RTT (0: * RFC 9002's eighth of the RTT); both grow when a packet called lost @@ -603,13 +614,13 @@ static void on_stored(PureLinkSender *l, const unsigned char *p, size_t size, ui l->stored = heard; l->stored_changed = now; } - if (flags & STORED_GAP) /* it did not keep what came after a gap: send it again */ + if ((flags & STORED_GAP) && heard >= l->stored) /* it did not keep what came after a gap: send it again */ for (size_t k = 0; k < l->count && l->received; ++k) { Record *r = record_at(l, k); for (uint32_t i = 0; i < r->parts; ++i) if (part_of(r, i)->state == RECEIVED) set_part(l, r, part_of(r, i), UNSENT); } - l->credit = credit ? least(credit, 65536) : 1; + l->limit = most(l->limit, heard + (credit ? least(credit, 65536) : 1)); } void pure_link_sender_take(PureLinkSender *l, const unsigned char *packet, size_t n, uint64_t now) { @@ -620,6 +631,7 @@ void pure_link_sender_take(PureLinkSender *l, const unsigned char *packet, size_ if (!l->in || l->in_run != run) { pure_aead_free(l->in); l->in = aead_of(l->secret, l->peer, l->own_public, run, l->run, l->in_base); + ++l->counts.keyed; l->in_run = run; if (!l->in) return; } @@ -638,6 +650,17 @@ void pure_link_sender_take(PureLinkSender *l, const unsigned char *packet, size_ if (!names || at + names + 13 > size) break; on_stored(l, plain + at, size - at, now); at += names + 13; + } else if (type == F_CHALLENGE) { /* said back in the next packet */ + if (at + 8 > size) break; + uint64_t challenge = get64(plain + at); + unsigned k = 0; + while (k < l->responding && l->respond[k] != challenge) ++k; + if (k == l->responding) { /* not had yet: first, the oldest let go */ + memmove(&l->respond[1], &l->respond[0], (RESPONSES - 1) * sizeof(uint64_t)); + l->respond[0] = challenge; + if (l->responding < RESPONSES) ++l->responding; + } + at += 8; } else if (type != F_PING) break; /* padding, or what this side does not know: the rest */ } @@ -651,6 +674,12 @@ static size_t fill(PureLinkSender *l, unsigned char *body, Flight *f, bool pad) at += put_names(body + at, l->source, l->input); put32(body + at, l->shape); at += 4; + bool responded = l->responding; + for (unsigned k = 0; k < l->responding; ++k, at += 9) { /* the receiver's challenges, said back */ + body[at] = F_RESPONSE; + put64(body + at + 1, l->respond[k]); + } + l->responding = 0; /* 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; @@ -666,7 +695,7 @@ static size_t fill(PureLinkSender *l, unsigned char *body, Flight *f, bool pad) uint64_t next = 0; for (; k < l->count && f->count < UNITS; ++k) { Record *r = record_at(l, k); - if (r->seq > base + l->credit) break; + if (r->seq > (l->limit ? l->limit : base + CREDIT)) break; bool full = false, fresh = !r->more && r->one.state == UNSENT, joins = run && r->seq == next; size_t whole = (joins ? 0 : RECORDS_HEAD) + varint_size(r->size) + r->size; if (fresh && at + whole <= most) { @@ -719,7 +748,7 @@ static size_t fill(PureLinkSender *l, unsigned char *body, Flight *f, bool pad) break; } } - return f->count ? at : 0; + return f->count || responded ? at : 0; } /* Its number is spent all the same. */ @@ -875,7 +904,6 @@ PureLinkSender *pure_link_sender(const char *source, const char *input, uint32_t l->run = random64(); l->window = WINDOW_FIRST; l->threshold = UINT64_MAX; - l->credit = CREDIT; l->reorder_packets = REORDER_FIRST; l->datagram = DATAGRAM; return l; @@ -890,8 +918,9 @@ static bool keyed(PureLinkSender *l, const unsigned char peer[PURE_SEAL_KEY], co pure_aead_free(l->in); 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->out = aead_of(l->secret, l->own_public, l->peer, l->run, 0, l->out_base)) && ++l->counts.keyed; } bool pure_link_sender_peer(PureLinkSender *l, const unsigned char peer[PURE_SEAL_KEY]) { return keyed(l, peer, NULL); } @@ -938,7 +967,16 @@ typedef struct Active Active; typedef struct { Active *active; uint64_t run, seen; /* the sender's run; when it last sent */ + /* The run its answers are sealed in, drawn when the slot is made: a + * slot made again for the same sender's run (after it rested) never + * seals under a key and nonce used before. */ + uint64_t answer_run; bool used, ack_due, due; + /* The address answers go to is checked once the sender says back the + * challenge sent there; until then they are at most three times the + * bytes that came from it (RFC 9000 §8). */ + bool checked; + uint64_t challenge, bytes_in, bytes_out; 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 */ @@ -1005,7 +1043,13 @@ struct PureLinkReceiver { const PureSealKey *own; unsigned char own_public[PURE_SEAL_KEY]; uint32_t own_id; - uint64_t run, idle, swept, trimmed, untrimmed; + uint64_t idle, swept, trimmed, untrimmed; + /* Keys made for a run that then did not open cost a token; tokens come + * back KEYINGS a second, up to KEYINGS. Under a flood of made-up + * packets keys are made for that many a second at most, while senders + * whose packets open (a thousand waking at once) cost none. */ + double key_tokens; + uint64_t key_at; 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; @@ -1048,7 +1092,6 @@ PureLinkReceiver *pure_link_receiver(const PureSealKey *own, const unsigned char s->own = own; memcpy(s->own_public, own_public, PURE_SEAL_KEY); s->own_id = key_id(own_public); - s->run = random64(); s->idle = IDLE_FIRST; return s; } @@ -1259,7 +1302,7 @@ static Active *activate(PureLinkReceiver *s, Peer *peer, uint64_t now) { 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; - } else if (pure_link_secret(s->own, peer->key, a->secret)) { + } else if (++s->counts.secrets && pure_link_secret(s->own, peer->key, a->secret)) { if (place) { memset(place, 0, 28); __atomic_thread_fence(__ATOMIC_RELEASE); @@ -1571,11 +1614,15 @@ static bool hand_over(PureLinkReceiver *s, Stream *st) { ++s->counts.deliveries; return true; } - if (!st->held_count || (st->known && held_at(st, 0)->seq != st->heard + 1)) return true; + /* From the first whole record held: one held before it in part may be + * of the past (a packet sent again) and never come whole; the host's + * word on this delivery says how far it heard, and lets that go. */ + size_t first = 0; + while (first < st->held_count && !held_at(st, first)->whole) ++first; size_t n = 0, bytes = 0; - while (n < st->held_count && n < BATCH && held_at(st, n)->whole && - held_at(st, n)->seq == held_at(st, 0)->seq + n) - bytes += 4 + held_at(st, n++)->size; + while (first + n < st->held_count && n < BATCH && held_at(st, first + n)->whole && + held_at(st, first + n)->seq == held_at(st, first)->seq + n) + bytes += 4 + held_at(st, first + n++)->size; if (!n) return true; if (bytes > s->batch_capacity) { unsigned char *grown = realloc(s->batch, bytes); @@ -1584,12 +1631,12 @@ static bool hand_over(PureLinkReceiver *s, Stream *st) { s->batch_capacity = bytes; } size_t at = 0; - for (size_t k = 0; k < n; ++k) { + for (size_t k = first; k < first + n; ++k) { put32(s->batch + at, held_at(st, k)->size); memcpy(s->batch + at + 4, held_at(st, k)->bytes, held_at(st, k)->size); at += 4 + held_at(st, k)->size; } - PureLinkDelivery d = {st->input, st->source, held_at(st, 0)->seq, (unsigned)n, s->batch, bytes, st}; + PureLinkDelivery d = {st->input, st->source, held_at(st, first)->seq, (unsigned)n, s->batch, bytes, st}; if (!s->host.deliver(s->host.context, &d)) return false; st->out = true; ++s->counts.deliveries; @@ -1598,21 +1645,27 @@ static bool hand_over(PureLinkReceiver *s, Stream *st) { /* 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. */ +/* 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; +} + 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); Active *a = peer->active; Run *r = a ? run_found(a, run) : NULL; - if (r && had(r, pn)) { - r->ack_due = true; /* its acknowledgment was lost, perhaps */ - mark_due(s, r); - return true; - } + 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}; - bool keyed = r || (derive(a->secret, peer->key, s->own_public, run, 0, made.in_key, made.in_base) && - derive(a->secret, s->own_public, peer->key, s->run, run, made.out_key, made.out_base)); + 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)); 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; @@ -1621,15 +1674,33 @@ static bool take_from(PureLinkReceiver *s, Peer *peer, const unsigned char *pack 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)) { 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; + bool fresh = !r; if (!r) r = install_run(a, &made); + if (!fresh && had(r, pn)) { /* again (opened first: nothing unsealed answers): its acknowledgment was lost, perhaps */ + r->ack_due = true; + mark_due(s, r); + return true; + } + bool newest = fresh || !r->got_count || pn > r->got[0].last; a->seen = r->seen = now; note(r, pn, now); - r->address_size = from_size <= sizeof(r->address) ? from_size : sizeof(r->address); - memcpy(r->address, from, r->address_size); /* where it is now: answers go there */ + /* Where it is now, if this is its newest packet (one of the past sent + * again moves nothing): answers go there, the address checked first. */ + size_t at_size = from_size <= sizeof(r->address) ? from_size : sizeof(r->address); + bool elsewhere = r->address_size != at_size || memcmp(r->address, from, at_size); + if (elsewhere && newest) { + memcpy(r->address, from, at_size); + r->address_size = at_size; + r->checked = false; + r->challenge = random64(); + r->bytes_in = r->bytes_out = 0; + } + if (!elsewhere || newest) r->bytes_in += n; ++s->counts.received; Stream *st = NULL; bool eliciting = false; @@ -1672,6 +1743,11 @@ static bool take_from(PureLinkReceiver *s, Peer *peer, const unsigned char *pack if (i < count) break; /* cut short: the rest is not read */ } else if (type == F_PING) { 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; + at += 8; + eliciting = true; } else break; /* padding, or what this side does not know: the rest */ } @@ -1715,6 +1791,11 @@ static void answer(PureLinkReceiver *s, uint64_t now, PureLinkSend *send, void * r->due = false; if (!r->used) continue; size_t at = 0; + if (!r->checked) { /* the address not checked yet: a challenge */ + body[at++] = F_CHALLENGE; + put64(body + at, r->challenge); + at += 8; + } if (r->ack_due && r->got_count) { body[at++] = F_ACK; put64(body + at, r->got[0].last); @@ -1741,11 +1822,15 @@ static void answer(PureLinkReceiver *s, uint64_t now, PureLinkSend *send, void * } r->ack_due = false; if (!at) continue; + if (!r->checked && r->bytes_out + HEADER + at + PURE_AEAD_TAG > 3 * r->bytes_in) continue; /* no amplifier */ 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, s->run, r->next_pn++, body, at, packet); - if (total && send(context, packet, total, r->address, r->address_size)) ++s->counts.packets; + size_t total = seal_packet(s->aead, give, r->out_base, s->own_id, 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; + } } s->due_count = 0; } diff --git a/link/link-protocol.h b/link/link-protocol.h index f51260b..9b4e63d 100644 --- a/link/link-protocol.h +++ b/link/link-protocol.h @@ -23,9 +23,28 @@ * 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 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). + * 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). + * + * What an attacker on the path may do, and what it gets (link/test-link.c + * does each): + * - change a packet: it does not open, and it is answered by nothing + * (a packet is opened before it is looked at). + * - send a packet of the past again: its records are applied once (the + * heard numbers), its word is taken only as the most said (STORED's + * limit), and it moves nothing: answers go where the newest packet of + * the run came from. A new address is sent a challenge the sender says + * back (the attacker cannot); until then answers there are at most + * 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.) + * - 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). * * Frames (numbers little-endian): * 0x01 STREAM source (u8 length, bytes), input (u8 length, bytes), u32 the @@ -40,16 +59,20 @@ * 0x04 STORED source, input (as STREAM), u64 the last number heard * (applied and saved), u8 flags (1: a record after a gap was * not taken: send what follows it again), u32 credit (records - * it takes past that) + * it takes past that: the sender sends up to the most heard + * and credit it was told) * 0x05 PING to be acknowledged * 0x06 RECORDS u64 the first one's number, u8 count, then whole records one * after another (numbers following on), each its size (a * varint: LEB128) and its bytes: a send that fits the packet * whole, with 1 to 3 bytes of framing, not the 19 of RECORD + * 0x07 CHALLENGE u64: a receiver's, until its sender says it back from + * the address the answers go to + * 0x08 RESPONSE u64: a challenge said back (the last few had) * 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; congestion control is its NewReno - * (RFC 9002 §7). */ + * Losses are detected as RFC 9002 says, with RACK's patience for packets + * that come late; congestion control is CUBIC (RFC 9438), paced. */ /* A packet is PURE_LINK_DATAGRAM bytes at most at first, and up to * PURE_LINK_DATAGRAM_MOST once the path is found to carry that many (a @@ -61,12 +84,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; a receiver's senders woken (their - * active state made), of them with a secret remembered (no X25519), let go - * when idle, and active now. */ + * congestion events undone for it; runs keyed (keys made from a secret) + * and secrets made (X25519); 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, woken, remembered, - swept, active; + uint64_t packets, records, resent, lost, acknowledged, received, deliveries, stored, late, undone, keyed, secrets, + woken, remembered, swept, active; } PureLinkCounts; /* ---- The sending side: one output's saved sends to a receiver's input, as diff --git a/link/test-link.c b/link/test-link.c index a05f8bc..4f68aa9 100644 --- a/link/test-link.c +++ b/link/test-link.c @@ -5,7 +5,14 @@ * record once, from the one after its last heard, and says so a turn later, * now and then failing a save; the receiver and the sender start again * midway, each from what its app kept. Every record must be applied once, - * in order, as it was sent. */ + * in order, as it was sent. + * + * And an attacker on the path: packets changed on the way (none may open), + * packets of the past sent again, from the sender's address or the + * 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. */ #include "link-protocol.h" #include <stdio.h> #include <stdlib.h> @@ -13,7 +20,7 @@ #include <unistd.h> #define MS UINT64_C(1000000) -enum { PACKETS = 1 << 16 }; +enum { PACKETS = 1 << 16, HISTORY = 4096 }; static uint64_t seed; static uint64_t next_random(void) { @@ -48,10 +55,24 @@ typedef struct { unsigned char bytes[PURE_LINK_DATAGRAM_MOST]; } Packet; +/* A nonce used: whose key (0: the sender's; 1 + n: answers to the sender's + * n-th start), the packet's run and number. */ +typedef struct { uint64_t whose, run, pn; } Nonce; + typedef struct { /* The network: packets on their way, each arriving at its time. */ Packet *packets; size_t count; + /* The sender's start (its address is "sender" and it); the nonces used; + * packets of the past (a ring), sent again now and then (percent a + * step); packets changed on the way; the attacker's bytes, in and out. */ + unsigned gen, replay; + bool tamper; + Nonce *nonces; + size_t nonce_count, nonce_capacity; + Packet *history; + size_t history_count; + uint64_t attacker_in, attacker_out; unsigned loss, doubled, spread_ms; /* percent, percent, the most a packet is held back */ uint64_t now, sent; /* The receiving app: its last heard (kept across the receiver's @@ -74,9 +95,32 @@ static void put_packet(World *w, bool to_receiver, const unsigned char *bytes, s } } +static uint64_t get64le(const unsigned char *p) { + uint64_t v = 0; + for (int i = 7; i >= 0; --i) v = v << 8 | p[i]; + return v; +} + +static void used(World *w, uint64_t whose, const unsigned char *packet) { + if (w->nonce_count == w->nonce_capacity) { + w->nonce_capacity = w->nonce_capacity ? 2 * w->nonce_capacity : 4096; + if (!(w->nonces = realloc(w->nonces, w->nonce_capacity * sizeof(Nonce)))) exit(1); + } + w->nonces[w->nonce_count++] = (Nonce){whose, get64le(packet + 5), get64le(packet + 13)}; +} + +/* An answer: to the sender's start it names (an earlier start's goes + * nowhere), or to the attacker. */ static bool answer(void *context, const unsigned char *packet, size_t size, const unsigned char *to, size_t to_size) { - CHECK(to_size == 6 && !memcmp(to, "sender", 6), "an answer to an address no packet came from"); - put_packet(context, false, packet, size); + World *w = context; + if (to_size == 8 && !memcmp(to, "attacker", 8)) { + w->attacker_out += size; + return true; + } + CHECK(to_size == 7 && !memcmp(to, "sender", 6), "an answer to an address no packet came from"); + unsigned gen = (unsigned)(to[6] - '0'); + used(w, 1 + gen, packet); + if (gen == w->gen) put_packet(w, false, packet, size); return true; } @@ -132,10 +176,68 @@ typedef struct { uint64_t records, seed; unsigned loss, doubled, spread_ms, fail_every; 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 */ } Case; +static bool nothing_sent(void *context, const unsigned char *packet, size_t size, const unsigned char *to, size_t to_size) { + (void)packet, (void)size, (void)to, (void)to_size; + ++*(unsigned *)context; + return true; +} + +/* A packet changed on the way (a byte, cut short, one byte more) must not + * open, and must make no answer. */ +static void tamper(World *w, PureLinkSender *s, PureLinkReceiver *r, const Packet *p, const char *from) { + unsigned char bent[PURE_LINK_DATAGRAM_MOST + 1]; + pure_link_receiver_turn(r, NULL, 0, w->now, answer, w); /* what is due goes first */ + for (int change = 0; change < 3; ++change) { + size_t size = p->size; + memcpy(bent, p->bytes, size); + if (change == 0) bent[next_random() % size] ^= (unsigned char)(1 + next_random() % 255); + else if (change == 1) size -= 1 + next_random() % 16; + else bent[size++] = (unsigned char)next_random(); + PureLinkCounts before, after; + unsigned answers = 0; + if (p->to_receiver) { + pure_link_receiver_counts(r, &before); + pure_link_receiver_take(r, bent, size, from, 7, w->now); + pure_link_receiver_turn(r, NULL, 0, w->now, nothing_sent, &answers); + pure_link_receiver_counts(r, &after); + } else { + pure_link_sender_counts(s, &before); + pure_link_sender_take(s, bent, size, w->now); + pure_link_sender_counts(s, &after); + } + CHECK(after.received == before.received && !answers, "a packet changed on the way (%d, to the %s) %s", change, + p->to_receiver ? "receiver" : "sender", answers ? "made an answer" : "opened"); + } +} + +/* A packet of the past, again: to the receiver from the sender's address or + * the attacker's, or to the sender. */ +static void replay(World *w, PureLinkSender *s, PureLinkReceiver *r, const char *from) { + const Packet *h = &w->history[next_random() % (w->history_count < HISTORY ? w->history_count : HISTORY)]; + const char *only = getenv("TEST_LINK_REPLAY"); + if (only && strcmp(only, h->to_receiver ? (chance(50) ? "receiver-sender" : "receiver-attacker") : "sender")) return; + if (!h->to_receiver) pure_link_sender_take(s, h->bytes, h->size, w->now); + else if (only ? !strcmp(only, "receiver-sender") : chance(50)) pure_link_receiver_take(r, h->bytes, h->size, from, 7, w->now); + else { + w->attacker_in += h->size; + pure_link_receiver_take(r, h->bytes, h->size, "attacker", 8, w->now); + } +} + typedef struct { PureLinkCounts sent, heard; uint64_t packets, seconds_ms; } Outcome; +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) + : a->run != b->run ? (a->run < b->run ? -1 : 1) + : a->pn != b->pn ? (a->pn < b->pn ? -1 : 1) + : 0; +} + static PureLinkReceiver *receiver_of(World *w, const PureSealKey *b, const unsigned char *public_b, const unsigned char *public_a, const char *memo, uint64_t idle_ms) { char error[256]; @@ -177,8 +279,10 @@ static Outcome run(const Case *c, const char *dir) { snprintf(memo, sizeof(memo), "%s/b.key.links", dir); unlink(memo); World w = {.packets = malloc(PACKETS * sizeof(Packet)), .loss = c->loss, .doubled = c->doubled, - .spread_ms = c->spread_ms, .fail_every = c->fail_every}; - if (!w.packets) exit(1); + .spread_ms = c->spread_ms, .fail_every = c->fail_every, .replay = c->replay, .tamper = c->tamper, + .history = malloc(HISTORY * sizeof(Packet))}; + if (!w.packets || !w.history) exit(1); + char from[8] = "sender0"; 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); @@ -191,8 +295,10 @@ static Outcome run(const Case *c, const char *dir) { (unsigned long long)w.heard, (unsigned long long)c->records); if (w.now >= 600000 * MS) break; uint64_t number; - for (size_t size; (size = pure_link_sender_packet(s, out, false, w.now, &number));) + for (size_t size; (size = pure_link_sender_packet(s, out, false, w.now, &number));) { + used(&w, 0, out); put_packet(&w, true, out, size); + } /* Then the next thing to happen. */ uint64_t next = UINT64_MAX, due = pure_link_sender_due(s), turn = pure_link_receiver_due(r); for (size_t k = 0; k < w.count; ++k) @@ -223,10 +329,13 @@ static Outcome run(const Case *c, const char *dir) { ++k; continue; } - if (p->to_receiver) pure_link_receiver_take(r, p->bytes, p->size, "sender", 6, w.now); + if (w.tamper) tamper(&w, s, r, p, from); + if (p->to_receiver) pure_link_receiver_take(r, p->bytes, p->size, from, 7, w.now); else pure_link_sender_take(s, p->bytes, p->size, w.now); + w.history[w.history_count++ % HISTORY] = *p; *p = w.packets[--w.count]; } + if (w.replay && w.history_count && chance(w.replay)) replay(&w, s, r, from); pure_link_sender_tick(s, w.now); size_t told = w.done_count; memcpy(w.told, w.done, told * sizeof(*w.done)); @@ -245,6 +354,7 @@ static Outcome run(const Case *c, const char *dir) { uint64_t stored = pure_link_sender_stored(s); pure_link_sender_free(s); s = sender_of(a, public_a, public_b, stored + 1, queued); + snprintf(from, sizeof(from), "sender%u", ++w.gen); /* a new process: another address */ } } Outcome o = {.packets = w.sent, .seconds_ms = w.now / MS}; @@ -256,6 +366,17 @@ static Outcome run(const Case *c, const char *dir) { (unsigned long long)w.applied, (unsigned long long)w.heard, (unsigned long long)c->records); CHECK(pure_link_sender_stored(s) == c->records, "%s: the sender knows %llu stored of %llu", c->name, (unsigned long long)pure_link_sender_stored(s), (unsigned long long)c->records); + /* No key sealed two packets with one nonce. */ + qsort(w.nonces, w.nonce_count, sizeof(Nonce), by_nonce); + for (size_t k = 1; k < w.nonce_count; ++k) + if (!by_nonce(&w.nonces[k - 1], &w.nonces[k])) { + CHECK(false, "%s: a nonce used twice (%s, run %llx, number %llu)", c->name, + w.nonces[k].whose ? "an answer" : "the sender", (unsigned long long)w.nonces[k].run, + (unsigned long long)w.nonces[k].pn); + break; + } + 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); printf("{\"case\":\"%s\",\"records\":%llu,\"virtual_ms\":%llu,\"packets\":%llu,\"resent\":%llu,\"lost\":%llu," "\"deliveries\":%llu,\"woken\":%llu,\"remembered\":%llu,\"swept\":%llu}\n", c->name, (unsigned long long)c->records, (unsigned long long)o.seconds_ms, (unsigned long long)o.sent.packets, @@ -266,9 +387,131 @@ static Outcome run(const Case *c, const char *dir) { pure_seal_key_free(a); pure_seal_key_free(b); free(w.packets); + free(w.history); + free(w.nonces); return o; } +static uint32_t key_id(const unsigned char key[PURE_SEAL_KEY]) { + uint32_t h = 2166136261u; + for (int i = 0; i < PURE_SEAL_KEY; ++i) h = (h ^ key[i]) * 16777619u; + return h; +} + +/* Senders the receiver must not hear: a key it does not allow, a packet of + * that key under an allowed key's id, and an allowed key sending as a + * source it is not allowed. Nothing opens but the last's, and nothing is + * delivered (deliver would say whose). */ +static void impostors(const char *dir) { + unsigned char public_a[PURE_SEAL_KEY], public_b[PURE_SEAL_KEY], public_c[PURE_SEAL_KEY], out[PURE_LINK_DATAGRAM_MOST]; + PureSealKey *a = key(dir, "a.key", public_a), *b = key(dir, "b.key", public_b), *c = key(dir, "c.key", public_c); + char memo[512]; + snprintf(memo, sizeof(memo), "%s/b.key.links", dir); + unlink(memo); + World w = {0}; + PureLinkReceiver *r = receiver_of(&w, b, public_b, public_a, memo, 0); + PureLinkSender *stranger = sender_of(c, public_c, public_b, 1, 20); + PureLinkSender *other = pure_link_sender("other.source", "order", 0x5eed, a, public_a); + unsigned char bytes[64] = {0}; + if (!other || !pure_link_sender_peer(other, public_b)) exit(1); + for (uint64_t seq = 1; seq <= 20; ++seq) pure_link_sender_queue(other, seq, bytes, sizeof(bytes)); + uint32_t id = key_id(public_a); + uint64_t number, opened = 0; + unsigned answers = 0; + for (int round = 0; round < 50; ++round, w.now += 10 * MS) { + PureLinkCounts before, after; + for (size_t size; (size = pure_link_sender_packet(stranger, out, false, w.now, &number));) { + pure_link_receiver_take(r, out, size, "sender0", 7, w.now); + for (int i = 0; i < 4; ++i) out[1 + i] = (unsigned char)(id >> 8 * i); /* an allowed key's id */ + pure_link_receiver_take(r, out, size, "sender0", 7, w.now); + } + pure_link_receiver_counts(r, &before); + CHECK(before.received == opened, "a key not allowed was heard (%llu packets)", + (unsigned long long)(before.received - opened)); + for (size_t size; (size = pure_link_sender_packet(other, out, false, w.now, &number));) + pure_link_receiver_take(r, out, size, "sender0", 7, w.now); + pure_link_receiver_counts(r, &after); + opened = after.received; + pure_link_receiver_turn(r, NULL, 0, w.now, nothing_sent, &answers); + pure_link_sender_tick(stranger, w.now), pure_link_sender_tick(other, w.now); + } + CHECK(!w.deliveries, "impostors: %llu deliveries", (unsigned long long)w.deliveries); + printf("{\"case\":\"impostors\",\"opened\":%llu,\"answers\":%u,\"deliveries\":%llu}\n", (unsigned long long)opened, + answers, (unsigned long long)w.deliveries); + pure_link_sender_free(stranger); + pure_link_sender_free(other); + pure_link_receiver_free(r); + pure_seal_key_free(a), pure_seal_key_free(b), pure_seal_key_free(c); +} + +/* Made-up packets under an allowed key's id, each of a run never seen, as + * fast as 100,000 a second: they cost the receiver few keys (a rate + * limited), no X25519 past the first, and no answer; and the sender, heard + * after, is heard all the same. */ +static void flood(const char *dir) { + unsigned char public_a[PURE_SEAL_KEY], public_b[PURE_SEAL_KEY], packet[PURE_LINK_DATAGRAM_MOST]; + PureSealKey *a = key(dir, "a.key", public_a), *b = key(dir, "b.key", public_b); + char memo[512]; + snprintf(memo, sizeof(memo), "%s/b.key.links", dir); + unlink(memo); + World w = {.packets = malloc(PACKETS * sizeof(Packet))}; + if (!w.packets) exit(1); + PureLinkReceiver *r = receiver_of(&w, b, public_b, public_a, memo, 0); + uint32_t id = key_id(public_a); + for (int i = 0; i < (getenv("TEST_LINK_NO_FLOOD") ? 0 : 10000); ++i, w.now += 10000) { + size_t size = 64 + next_random() % 1100; + for (size_t k = 0; k < size; ++k) packet[k] = (unsigned char)next_random(); + packet[0] = 0x70; + for (int j = 0; j < 4; ++j) packet[1 + j] = (unsigned char)(id >> 8 * j); + w.attacker_in += size; + pure_link_receiver_take(r, packet, size, "attacker", 8, w.now); + if (i % 64 == 0) pure_link_receiver_turn(r, NULL, 0, w.now, answer, &w); + } + PureLinkCounts flooded; + pure_link_receiver_counts(r, &flooded); + /* Then the sender: its records all delivered. */ + PureLinkSender *s = sender_of(a, public_a, public_b, 1, 200); + unsigned char out[PURE_LINK_DATAGRAM_MOST]; + uint64_t number; + for (int step = 0; step < 20000 && w.heard < 200; ++step, w.now += MS) { + for (size_t size; (size = pure_link_sender_packet(s, out, false, w.now, &number));) + pure_link_receiver_take(r, out, size, "sender0", 7, w.now); + size_t told = w.done_count; + memcpy(w.told, w.done, told * sizeof(*w.done)); + w.done_count = 0; + pure_link_receiver_turn(r, w.told, told, w.now, answer, &w); + for (size_t k = 0; k < w.count; ++k) pure_link_sender_take(s, w.packets[k].bytes, w.packets[k].size, w.now); + w.count = 0; + pure_link_sender_tick(s, w.now); + if (getenv("TEST_LINK_DEBUG") && step < 40) { + PureLinkCounts rc, sc; + pure_link_receiver_counts(r, &rc), pure_link_sender_counts(s, &sc); + fprintf(stderr, "step %d: sent %llu answers %llu received %llu delivered %llu heard %llu due %llu\n", step, + (unsigned long long)sc.packets, (unsigned long long)sc.received, (unsigned long long)rc.received, + (unsigned long long)rc.deliveries, (unsigned long long)w.heard, + (unsigned long long)pure_link_sender_due(s)); + } + } + CHECK(flooded.keyed <= 300 && flooded.secrets <= 1 && !w.attacker_out, /* 256 at once, 256 a second after */ + "flood: %llu runs keyed, %llu secrets made, %llu bytes to the attacker", (unsigned long long)flooded.keyed, + (unsigned long long)flooded.secrets, (unsigned long long)w.attacker_out); + CHECK(w.heard == 200, "flood: the sender heard after it: %llu of 200", (unsigned long long)w.heard); + if (getenv("TEST_LINK_DEBUG")) { + PureLinkCounts rc, sc; + pure_link_receiver_counts(r, &rc), pure_link_sender_counts(s, &sc); + fprintf(stderr, "receiver received %llu woken %llu deliveries %llu keyed %llu active %llu; sender packets %llu received %llu stored %llu\n", + (unsigned long long)rc.received, (unsigned long long)rc.woken, (unsigned long long)rc.deliveries, + (unsigned long long)rc.keyed, (unsigned long long)rc.active, (unsigned long long)sc.packets, + (unsigned long long)sc.received, (unsigned long long)sc.stored); + } + printf("{\"case\":\"flood\",\"packets\":10000,\"keyed\":%llu,\"secrets\":%llu,\"heard_after\":%llu}\n", + (unsigned long long)flooded.keyed, (unsigned long long)flooded.secrets, (unsigned long long)w.heard); + pure_link_sender_free(s); + pure_link_receiver_free(r); + pure_seal_key_free(a), pure_seal_key_free(b); + free(w.packets); +} + int main(void) { char dir[] = "/tmp/pure-test-link-XXXXXX", error[256]; if (!mkdtemp(dir) || !pure_seal_ready(error, sizeof(error))) { @@ -276,7 +519,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}; + Case clean = {"clean", 3000, 1, 0, 0, 0, 0, 0, 0, 0, 0, 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); @@ -285,13 +528,24 @@ 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}; + Case rough = {"rough", 3000, s * 7919, 10, 3, 20, 37, 1500, 800, 2200, 300, 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, (unsigned long long)o.heard.swept, (unsigned long long)o.heard.woken, (unsigned long long)o.heard.remembered); } + /* 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}; + 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}; + run(&again, dir); + } + impostors(dir); + flood(dir); char command[600]; snprintf(command, sizeof(command), "rm -rf %s", dir); if (system(command)) { /* left behind in /tmp */ } |