Browse WireGuard specs (30 of 38)

Proofs / WireGuard / Earlier, longer properties

Handshake packets on the receive path

Over any sequence of packets of any bytes and lengths, receive.c's validate_header_len and wg_receive_handshake_packet let only messages of the right type and length reach the handshake code, check mac1 (and under load mac2) before any of them, send exactly one cookie reply under load, and update the endpoint, timers and statistics only of the authenticated peer; a rejected packet changes nothing.

  • validate_header_len and wg_receive_handshake_packet are copied out of receive.c byte for byte. A shim records and checks their calls into send.c, socket.c and timers.c.
  • Not covered: receive.c's parsing of UDP and IP headers, its type switch, which the spec restates, and the handshake queue. The queue length is an input of the property.
  • A rejected packet can still renew the cookie secret when it is 120 seconds old, and under load the time of the overload is recorded.
spec
x_handshake_receive
length
622 lines of C
own proof
43,927 lines of Rocq
status
Proved
30 of 38
On this page

The spec

The property is stated by the C program harness/x_handshake_receive.c, 622 lines. Here is its main cut down to the inputs it draws, the calls into the code under test and the checks (lines 201–622; ... marks lines left out). The checks call helpers and the model in the spec and in harness/common.h.

C
int main(void)
{
	...
	now = draw_boottime();
	...
	wg_noise_init();
	nondet_bytes(raw_d, 32);
	nondet_bytes(raw_k, 32);
	...
	for (i = 0; i < n; i++) {
	...
	for (nd = peers; nd; nd = nd->next) {
	...
	for (i = 0; i < steps; i++) {
				...
				xchacha20poly1305_encrypt(mc->encrypted_cookie, ck, 16, x->p->latest_cookie.last_mac1_sent, 16,
			     ...
			     !xchacha20poly1305_decrypt(pt, mc->encrypted_cookie, 32, target->rest.cookie.last_mac1_sent, 16,
				...
				CHECK(bytes_eq(secret, path == 2 ? wg_shim_random_log_prev : wg_shim_random_log, 32));
			...
			CHECK(rx_authenticated(target->p, &skb, 1, 0));
			...
			CHECK(hnodes_same_except(peers, target->p) && itd.head == head0 && kents_same(kes) && shim_same(&ss));
				...
				CHECK(wg_shim_allocs == ss.allocs && wg_shim_frees == ss.frees &&
				...
				CHECK(hs_zeroed_from(s, h) && wg_shim_allocs == ss.allocs + 1 &&
					...
					wg_noise_keypairs_clear(&target->p->keypairs);   // back to a state of the same shape
					...
					CHECK(h->entry.hashed && h->entry.index == s->index && wg_shim_frees == ss.frees + 1);
					...
					CHECK(table_has(&itd, &nd->p->handshake.entry));
			...
			CHECK(rx_only_cookie(0));
				...
				CHECK(rx_only_cookie(1));
			...
			CHECK(hnodes_same_except(peers, NULL) && itd.head == head0 && kents_same(kes) && shim_same(&ss));
...
}

The full spec at commit 3c1fc13 ↗

The property as the spec's first comment states it
Law `handshake_receive`: the receive side of the handshake gates the consume functions exactly as
the protocol requires, over ANY sequence of packets of ANY bytes and ANY length.  Code under test besides the
units: receive.c's validate_header_len and wg_receive_handshake_packet, extracted byte for byte
(patch/receive_handshake.c, compiled into this harness only; its calls to send.c / socket.c / timers.c are a
recording shim: DEVIATIONS.md S22, S23).

State: device D with ANY static key, ANY cookie secret and secret age; ANY number of peers (unique public keys)
with ANY handshake state (common.h hs_randomize) and other state (peer_randomize_rest), any reference count below
INT_MAX (common.h draw_peer_refs), entries hashed or not, ANY number of keypairs (whole objects of ANY content,
common.h kents_add; not in the slots, which begin_session rotates) of ANY peers in the table; one peer K whose
private key the harness knows. A sequence of ANY length of packets, with the boot clock moving forward by any
amount, ANY handshake-queue length (the load), ANY rate-limiter answer and ANY source address/port, each packet
one of: ANY bytes of ANY length (other than 148, 92, 64; possibly beginning with K's initiation or response, i.e.
with bytes after a valid message; the type word drawn, or set to 1..4 with or without nonzero reserved bytes; the
last 32 bytes possibly a correct mac1 / mac2 of the rest); 148 bytes with ANY fields or K's initiation to D (the
model's); 92 bytes with ANY fields or K's response to D's current handshake with K (the model's); 64 bytes with
ANY fields (receiver index drawn or one of the table's) or a cookie reply that decrypts for any peer that sent a
mac1; the type word exact, with nonzero reserved bytes, or any; mac1 the correct one (D's mac1 key) or any; mac2
the correct one for D's current cookie of the source, zero or any.  The harness hands a packet to
wg_receive_handshake_packet as wg_packet_receive does: when validate_header_len accepts it and its type word is 1,
2 or 3 (receive.c's UDP/IP parsing and the handshake queue are not covered: DEVIATIONS.md L14).
Claims, for every packet (the model: whitepaper 5.3 / 5.4 and receive.c's load logic):
 - unless the type word is exactly 1, 2 or 3 (reserved bytes zero) and the length exactly 148, 92 or 64
   accordingly, NOTHING changes: every peer as a whole, the device (cookie secret included), the index table;
   nothing is allocated; no call leaves the verified units (a message of type 1 / 2 / 3 with nonzero reserved
   bytes, or of a length that is not exact - also with valid content followed by extra bytes - is dropped);
 - a cookie reply (type 3): exactly law cookie_reply's acceptance and update, nothing else, no call;
 - an initiation or response (type 1 / 2): D is "under load" when the queue holds at least
   MAX_QUEUED_INCOMING_HANDSHAKES / 8 = 512 packets (then last_under_load = now), or else when it last was less
   than 1 s ago, exactly as receive.c decides it: still under load iff NOT (s64)(last_under_load + 1 s) <=
   (s64)now, so exactly 1 s after the last overload D is no longer under load (and last_under_load is reset to
   0) - modelled across the sequence; the verdict on mac1 / mac2 is law cookie_mac's model, with the cookie
   secret replaced by a fresh random one when (s64)(secret birthdate + 120 s) <= (s64)now, i.e. at EXACTLY
   120 s (wireguard-go: only after 120 s); then
     * no valid mac1, or valid macs but rate limited: NOTHING changes but that rotation, no call;
     * under load without a valid mac2: exactly one cookie reply is sent, for the message's sender index, and
       nothing else changes (no consume);
     * otherwise the consume function runs and the result is exactly the model's (laws consume_initiation_any,
       consume_response_any: identity, DH, decryption, known peer, timestamp newer, at least 20 ms since the
       last initiation - accepted at exactly 20 ms -, state CREATED_INITIATION, tag): rejected -> NOTHING
       changes, no call; accepted (peer P) -> P's handshake is the model's (an initiation: CONSUMED_INITIATION
       with the model's hash, chaining key, remote ephemeral, timestamp, indices; a response: the session begins,
       begin_session zeroing it and, unless the allocation fails or P is dead, moving its index to the new current
       keypair), the endpoint is set from THIS packet, a response is sent (initiation) or, if a session was made,
       the session timers run and a keepalive is sent (response), the rx statistics get the packet's length,
       both authenticated-packet timers run - each exactly once, all for P; every other peer unchanged;
       references balanced; nothing allocated but the keypair; no reference count saturates or warns;
 - the packet is never modified.
(After a session is made the harness clears P's keypairs, so that every packet starts from a state of the same
shape; law keypairs covers what sessions do.  The harness draws the boundaries on purpose: queue lengths
510..514, the clock exactly 1 s +- 2 ns after the last overload, 120 s +- 2 ns after the cookie secret's birth,
20 ms +- 2 ns after K's last initiation.)

The code it is about

wg_receive_handshake_packet in patch/receive_handshake.c, lines 153–265 (... marks lines left out):

C
static void wg_receive_handshake_packet(struct wg_device *wg,
					struct sk_buff *skb)
{
	enum cookie_mac_state mac_state;
	struct wg_peer *peer = NULL;
	/* This is global, so that our load calculation applies to the whole
	 * system. We don't care about races with it at all.
	 */
	static u64 last_under_load;
	bool packet_needs_cookie;
	bool under_load;

	if (SKB_TYPE_LE32(skb) == cpu_to_le32(MESSAGE_HANDSHAKE_COOKIE)) {
		net_dbg_skb_ratelimited("%s: Receiving cookie response from %pISpfsc\n",
					wg->dev->name, skb);
		wg_cookie_message_consume(
			(struct message_handshake_cookie *)skb->data, wg);
		return;
	}

	under_load = atomic_read(&wg->handshake_queue_len) >=
			MAX_QUEUED_INCOMING_HANDSHAKES / 8;
	if (under_load) {
		last_under_load = ktime_get_coarse_boottime_ns();
	} else if (last_under_load) {
		under_load = !wg_birthdate_has_expired(last_under_load, 1);
		if (!under_load)
			last_under_load = 0;
	}
	mac_state = wg_cookie_validate_packet(&wg->cookie_checker, skb,
					      under_load);
	if ((under_load && mac_state == VALID_MAC_WITH_COOKIE) ||
	    (!under_load && mac_state == VALID_MAC_BUT_NO_COOKIE)) {
		packet_needs_cookie = false;
	} else if (under_load && mac_state == VALID_MAC_BUT_NO_COOKIE) {
		packet_needs_cookie = true;
	} else {
		net_dbg_skb_ratelimited("%s: Invalid MAC of handshake, dropping packet from %pISpfsc\n",
					wg->dev->name, skb);
		return;
	}

	switch (SKB_TYPE_LE32(skb)) {
	case cpu_to_le32(MESSAGE_HANDSHAKE_INITIATION): {
		struct message_handshake_initiation *message =
...
}

This is the code under test as the proof sees it: Linux at 551c722f with the two lib/crypto patches, and with the idiom rewrites that VST needs, each marked QUICKPROOF in the code and listed in DEVIATIONS.md.

The theorem

QuickProof generated this statement from the spec in src/contracts/x_handshake_receive.v:

Rocq
Theorem x_handshake_receive : harness_safe whole_prog.

whole_prog is the spec linked with the code under test. The 19 x_ specs are proved together, as the theorem suite_x, from one specification of every function of the code. src/contracts/laws.v states each spec on its own program and takes it from suite_x:

Rocq
Theorem x_handshake_receive : harness_safe WgNoise.contracts.x_handshake_receive.whole_prog.
Proof. exact (proj1 (proj2 (proj2 (proj2 (proj2 (proj2 (proj2 (proj2 (proj2 (proj2 WgNoise.contracts.suite.suite_x)))))))))). Qed.

qp verify checks that this statement is the one generated from the spec at the contract commit, and that its proof uses no axiom beyond the 13 that every spec here uses: standard logical axioms and VST's abstract malloc library.

The C files (units) its program links
  • drivers/net/wireguard/noise.c
  • drivers/net/wireguard/cookie.c
  • patch/counter_validate.c
  • lib/crypto/blake2s.c
  • lib/crypto/chacha.c
  • lib/crypto/chacha-block-generic.c
  • lib/crypto/poly1305.c
  • lib/crypto/poly1305-donna32.c
  • lib/crypto/chacha20poly1305.c
  • lib/crypto/curve25519.c
  • lib/crypto/curve25519-fiat32.c
  • patch/wg_shim.c
  • quickproof/libc/libc.c
  • quickproof/libc/malloc_unit.c

What it leaves out

  • Like every spec of this proof: runs of more than one thread (locks and RCU are those of a single thread), termination (a run that never returns is not a counterexample), and binaries built by a compiler (the theorem is about the code as CompCert defines C for 64-bit x86).
  • The kernel around the code is a shim of plain C for one thread, and the code carries rewrites of idioms that VST cannot handle. Both are tested against the kernel's code, not proved.

Recorded for this property in DEVIATIONS.md (section L, what the properties exclude or assume):

  • L14. Of receive.c's handshake path, prepare_skb_header (UDP and IP parsing, length trim, pskb_may_pull) and the handshake queue (ptr_ring, worker, queue-length accounting) are not verified: harness/x_handshake_receive.c hands a packet over as wg_packet_receive's type switch does (validate_header_len, then types 1 to 3), and the queue length is an input Why: the queue is concurrent, and the parsing is the network stack

The summary page lists what the proof as a whole does not cover.

How it was proved

src/proof/harness/handshake_receive/ holds 43,927 lines of Rocq (formerly Coq) that are specific to this spec. It builds on the specifications and proofs of the functions of noise.c, cookie.c and lib/crypto, the protocol model, and the Diffie-Hellman agreement of X25519. The whole proof of the 38 specs is about 300,000 lines. AI agents wrote it, Rocq checks all of it, and nobody has to read it. What people have to read is the spec above, with harness/common.h, and the kernel shim that DEVIATIONS.md describes.

Other specs about receive.c: see the list on the left, or the summary.