Browse WireGuard specs (25 of 38)

Proofs / WireGuard / Earlier, longer properties

Session keys and their lifetime

Over any sequence of session starts, key use, expiry, clearing, and gets and puts of references, the three keypair slots, every keypair, its reference count (with the saturation of the kernel's refcount_t), the index table and the frees agree with a model after every step, with no bound on references or sessions.

  • The reference count is the kernel's refcount_t, saturation included, as the shim models it.
  • wg_noise_received_with_keypair is also covered on NULL, which receive.c never passes but whose behaviour is defined.
spec
x_keypairs
length
516 lines of C
own proof
18,522 lines of Rocq
status
Proved
25 of 38
On this page

The spec

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

C
int main(void)
{
	...
	for (i = 0; i < 5; i++)
	...
	now = draw_boottime();
	...
	wg_noise_init();
	nondet_bytes(raw, 32);
	nondet_bytes(pub, 32);
	...
	for (i = 0; i < n; i++) {
	...
	for (o = others; o; o = o->next) {
	...
	for (i = 0; i < 5; i++)
			...
			r = wg_noise_handshake_begin_session(&p.handshake, &p.keypairs);
				...
				CHECK(!r && hs_same(&snap, &p.handshake) && wg_shim_allocs == a0 && wg_shim_alloc_failures == f0);
					...
					CHECK(kp != NULL);
			...
			r = wg_noise_received_with_keypair(&p.keypairs, k != NULL ? k->kp : NULL);
				...
				CHECK(!r);
			...
			wg_noise_expire_current_peer_keypairs(&p);
			...
			r = wg_noise_keypair_get(k ? k->kp : NULL);
				...
				wg_noise_keypair_put(NULL, unref);
		...
		CHECK(check_all(&p, &t, &w));
	...
	wg_noise_keypairs_clear(&p.keypairs);
			...
			wg_noise_keypair_put(k->kp, false);
	...
	CHECK(wg_shim_refcount_warn[REFCOUNT_ADD_UAF] == warn0[REFCOUNT_ADD_UAF] &&
...
}

The full spec at commit 3c1fc13 ↗

The property as the spec's first comment states it
Law `keypairs`: keypair rotation and lifetime against a shadow model, over ANY sequence of operations.

One peer P of a device (any identity), with ANY other mutable state (common.h peer_randomize_rest);
ANY number of other peers of the device with ANY state (handshake, cookie, ...), their handshake entries in the
index table or not, and ANY number of keypairs of theirs (whole objects of ANY content, common.h kents_add) in the
table, possibly in their slots.  A sequence of ANY length of operations, each one of:
  - wg_noise_handshake_begin_session after setting P's handshake to ANY mutable state (common.h hs_randomize: any
    of the five states - CREATED_RESPONSE: responder, CONSUMED_RESPONSE: initiator -, any chaining key, remote
    index, ephemeral keys, hash, latest timestamp, last consumption), its index entry hashed or not, P dead or
    not; the allocation may fail;
  - wg_noise_received_with_keypair with ANY live keypair (current, previous, next or one only a reference
    holder keeps), a keypair of another peer, or NULL: receive.c
    always passes the keypair it looked up, but the function's behaviour on NULL is defined and claimed too (with
    no next keypair, NULL is the next keypair and the slots rotate);
  - wg_noise_expire_current_peer_keypairs;  - wg_noise_keypairs_clear;
  - wg_noise_keypair_get of NULL or any live keypair (the harness keeps the reference);
  - wg_noise_keypair_put of ANY kept reference (any keypair the harness holds one of), with unreference_now true
    or false, or of NULL;
  - the data path's use of ANY live keypair: its sending counter and its receiving counter set to
    ANY values (what send.c / receive.c do; out of scope themselves);
with the boot clock moving forward by any amount.  No bound on the number of operations, of sessions or of
references (as the kernel does it: the reference count is the kernel's refcount_t, which the
shim models exactly - quickproof_kref.h, S04 - and the 64-bit keypair counter wraps like the kernel's atomic).
Shadow model (in this file): the three slots (previous, current, next), every live keypair with its reference
count, index-table membership and index, keys, validity, birthdate, role, remote index and internal id; the
rotation rules of the WireGuard paper (initiator: the new keypair becomes current, the old current previous or,
if a next keypair was waiting, that one previous and the old current is dropped; responder: the new keypair
waits as next and previous is dropped; confirmation (received_with_keypair of next): next becomes current,
current previous, previous dropped); "dropped" = unhashed now and one reference less; the reference count as
include/linux/refcount.h documents refcount_t: +1 per get and -1 per put while it is below INT_MAX = 2^31 - 1,
a keypair is freed exactly when its last reference goes; a get that finds INT_MAX references SATURATES the
count (REFCOUNT_SATURATED = 0xc0000000, the kernel's warning "saturated; leaking memory"); a saturated count
never changes again (every later put is the kernel's warning "underflow; use-after-free" on the saturated
count, and does nothing else), and a saturated keypair is never freed: it is leaked, as the kernel leaks it.
Claims after EVERY operation: return values, slot pointers, every live keypair's fields, reference counts
(exactly the model's, the saturated value included) and table membership (the table holds exactly the hashed
live keypairs, P's handshake entry if hashed and the other peers' entries, with unique indices), P's handshake
(zeroed by begin_session and expire, else unchanged), expire invalidates the sending keys of current and next
and resets last_sent_handshake to now - 6 s; allocations minus frees = live keypairs; the kernel's refcount_t
warnings are exactly the model's: NEVER an increment from 0 ("addition on 0; use-after-free"), never an
underflow of a count that is not saturated, never kref_get's overflow or a decrement to 0 without release - the
only warnings are a get at INT_MAX (saturation) and the puts of an already saturated count.  A saturated keypair
stays readable and unchanged (the model compares its every field after every operation: it is never freed, so
never used after free).  At the end, clear and putting every kept reference free every keypair that never
saturated; the saturated ones (and only they) are leaked.
Also, after EVERY operation: a new keypair starts with fresh counters (sending counter 0, replay
window counter 0 with an empty bitmap); no operation ever changes the counters of a live keypair (rotation and
teardown never reset or rewind a nonce counter); P's handshake is checked after EVERY operation (whole, against
the model's copy); the rest of P (cookie state, dead flag, last sent handshake but by expire, internal id,
public-key table link) and its reference count, every other peer as a whole and its keypairs (every byte), and the
device (identity, cookie checker, public-key table), never change.

The code it is about

add_new_keypair in drivers/net/wireguard/noise.c, lines 198–251 (... marks lines left out):

C
static void add_new_keypair(struct noise_keypairs *keypairs,
			    struct noise_keypair *new_keypair)
{
	struct noise_keypair *previous_keypair, *next_keypair, *current_keypair;

	spin_lock_bh(&keypairs->keypair_update_lock);
	previous_keypair = rcu_dereference_protected(keypairs->previous_keypair,
		lockdep_is_held(&keypairs->keypair_update_lock));
	next_keypair = rcu_dereference_protected(keypairs->next_keypair,
		lockdep_is_held(&keypairs->keypair_update_lock));
	current_keypair = rcu_dereference_protected(keypairs->current_keypair,
		lockdep_is_held(&keypairs->keypair_update_lock));
	if (new_keypair->i_am_the_initiator) {
		/* If we're the initiator, it means we've sent a handshake, and
		 * received a confirmation response, which means this new
		 * keypair can now be used.
		 */
		if (next_keypair) {
			/* If there already was a next keypair pending, we
			 * demote it to be the previous keypair, and free the
			 * existing current. Note that this means KCI can result
			 * in this transition. It would perhaps be more sound to
			 * always just get rid of the unused next keypair
			 * instead of putting it in the previous slot, but this
			 * might be a bit less robust. Something to think about
			 * for the future.
			 */
			RCU_INIT_POINTER(keypairs->next_keypair, NULL);
			rcu_assign_pointer(keypairs->previous_keypair,
					   next_keypair);
			wg_noise_keypair_put(current_keypair, true);
		} else /* If there wasn't an existing next keypair, we replace
			* the previous with the current one.
			*/
			rcu_assign_pointer(keypairs->previous_keypair,
					   current_keypair);
		/* At this point we can get rid of the old previous keypair, and
		 * set up the new keypair.
		 */
		wg_noise_keypair_put(previous_keypair, true);
		rcu_assign_pointer(keypairs->current_keypair, new_keypair);
	} else {
		/* If we're the responder, it means we can't use the new keypair
		 * until we receive confirmation via the first data packet, so
		 * we get rid of the existing previous one, the possibly
		 * existing next one, and slide in the new next one.
		 */
		rcu_assign_pointer(keypairs->next_keypair, new_keypair);
...
}

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_keypairs.v:

Rocq
Theorem x_keypairs : 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_keypairs : harness_safe WgNoise.contracts.x_keypairs.whole_prog.
Proof. exact (proj1 (proj2 (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):

  • L04. wg_noise_received_with_keypair(keypairs, NULL) is covered: receive.c always passes the keypair it looked up, but the function's behaviour on NULL is defined (with no next keypair, NULL is the next keypair and the slots rotate) and the spec x_keypairs states it

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

How it was proved

src/proof/harness/keypairs/ holds 18,522 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 noise.c: see the list on the left, or the summary.