Message-ID: <CACYkzJ6VQUExfyt0=-FmXz46GHJh3d=FXh5j4KfexcEFbHV-vg@mail.gmail.com>
Date: Sun, 11 May 2025 04:01:25 +0200
From: KP Singh <kpsingh@...nel.org>
To: Paul Moore <paul@...l-moore.com>
Cc: bboscaccy@...ux.microsoft.com, James.Bottomley@...senpartnership.com, 
	bpf@...r.kernel.org, code@...icks.com, corbet@....net, davem@...emloft.net, 
	dhowells@...hat.com, gnoack@...gle.com, herbert@...dor.apana.org.au, 
	jarkko@...nel.org, jmorris@...ei.org, jstancek@...hat.com, 
	justinstitt@...gle.com, keyrings@...r.kernel.org, 
	linux-crypto@...r.kernel.org, linux-doc@...r.kernel.org, 
	linux-kbuild@...r.kernel.org, linux-kernel@...r.kernel.org, 
	linux-kselftest@...r.kernel.org, linux-security-module@...r.kernel.org, 
	llvm@...ts.linux.dev, masahiroy@...nel.org, mic@...ikod.net, morbo@...gle.com, 
	nathan@...nel.org, neal@...pa.dev, nick.desaulniers+lkml@...il.com, 
	nicolas@...sle.eu, nkapron@...gle.com, roberto.sassu@...wei.com, 
	serge@...lyn.com, shuah@...nel.org, teknoraver@...a.com, 
	xiyou.wangcong@...il.com, kysrinivasan@...il.com
Subject: Re: [PATCH v3 0/4] Introducing Hornet LSM

> > I think we need a more detailed explanation of this approach on-list.
> > There has been a lot of vague guidance on BPF signature validation
> > from the BPF community which I believe has partly led us into the
> > situation we are in now.  If you are going to require yet another
> > approach, I think we all need to see a few paragraphs on-list
> > outlining the basic design.
>
> Definitely, happy to share design / code.

Here’s the design that Alexei and I have been discussing. It's
extensible, independent of ELF formats, handles all identified
use-cases, paves the way for signed unprivileged eBPF, and meets the
requirements of anyone who wants to run signed eBPF programs.

# Trusted Hash Chain

The key idea of the design is to use a signing algorithm that allows
us to integrity-protect a number of future payloads, including their
order, by creating a chain of trust.

Consider that Alice needs to send messages M_1, M_2, ..., M_n to Bob.
We define blocks of data such that:

    B_n = M_n || H(termination_marker)

(Each block contains its corresponding message and the hash of the
*next* block in the chain.)

    B_{n-1} = M_{n-1} || H(B_n)
    B_{n-2} = M_{n-2} || H(B_{n-1})

  ...

    B_2 = M_2 || H(B_3)
    B_1 = M_1 || H(B_2)

Alice does the following (e.g., on a build system where all payloads
are available):

  * Assembles the blocks B_1, B_2, ..., B_n.
  * Calculates H(B_1) and signs it, yielding Sig(H(B_1)).

Alice sends the following to Bob:

    M_1, H(B_2), Sig(H(B_1))

Bob receives this payload and does the following:

    * Reconstructs B_1 as B_1' using the received M_1 and H(B_2)
(i.e., B_1' = M_1 || H(B_2)).
    * Recomputes H(B_1') and verifies the signature against the
received Sig(H(B_1)).
    * If the signature verifies, it establishes the integrity of M_1
and H(B_2) (and transitively, the integrity of the entire chain). Bob
now stores the verified H(B_2) until it receives the next message.
    * When Bob receives M_2 (and H(B_3) if n > 2), it reconstructs
B_2' (e.g., B_2' = M_2 || H(B_3), or if n=2, B_2' = M_2 ||
H(termination_marker)). Bob then computes H(B_2') and compares it
against the stored H(B_2) that was verified in the previous step.

This process continues until the last block is received and verified.

Now, applying this to the BPF signing use-case, we simplify to two messages:

    M_1 = I_loader (the instructions of the loader program)
    M_2 = M_metadata (the metadata for the loader program, passed in a
map, which includes the programs to be loaded and other context)

For this specific BPF case, we will directly sign a composite of the
first message and the hash of the second. Let H_meta = H(M_metadata).
The block to be signed is effectively:

    B_signed = I_loader || H_meta

The signature generated is Sig(B_signed).

The process then follows a similar pattern to the Alice and Bob model,
where the kernel (Bob) verifies I_loader and H_meta using the
signature. Then, the trusted I_loader is responsible for verifying
M_metadata against the trusted H_meta.

>From an implementation standpoint:

# Build

bpftool (or some other tool in the user's build environment) knows
about the metadata (M_metadata) and the loader program (I_loader). It
first calculates H_meta = H(M_metadata). Then it constructs the object
to be signed and computes the signature:

    Sig(I_loader || H_meta)

# Loader

bpftool generates the loader program. The initial instructions of this
loader program are designed to verify the SHA256 hash of the metadata
(M_metadata) that will be passed in a map. These instructions
effectively embed the precomputed H_meta as immediate values.

    ld_imm64 r1, const_ptr_to_map // insn[0].src_reg == BPF_PSEUDO_MAP_IDX
    r2 = *(u64 *)(r1 + 0);
    ld_imm64 r3, sha256_of_map_part1 // constant precomputed by
bpftool (part of H_meta)
    if r2 != r3 goto out;

    r2 = *(u64 *)(r1 + 8);
    ld_imm64 r3, sha256_of_map_part2 // (part of H_meta)
    if r2 != r3 goto out;

    r2 = *(u64 *)(r1 + 16);
    ld_imm64 r3, sha256_of_map_part3 // (part of H_meta)
    if r2 != r3 goto out;

    r2 = *(u64 *)(r1 + 24);
    ld_imm64 r3, sha256_of_map_part4 // (part of H_meta)
    if r2 != r3 goto out;
    ...

This implicitly makes the payload equivalent to the signed block (B_signed)

    I_loader || H_meta

bpftool then generates the signature of this I_loader payload (which
now contains the expected H_meta) using a key (system or user) with
new flags that work in combination with bpftool -L

This signature is stored in bpf_attr, which is extended as follows for
the BPF_PROG_LOAD command:

    __aligned_u64 signature;
    __u32 signature_size;
    __u32 user_keyring_serial;
    __u64 system_keyring_id;

# New BPF Commands

## BPF_MAP_GET_HASH args: (map_fd, &sha256_output, output_size)

This command instructs the kernel to compute the SHA256 hash of the
map's data. If sha256_output is non-NULL, the hash is returned to
userspace. (While not strictly needed for this specific signing
use-case to function, it's a useful utility for userspace debugging or
other applications.)

The kernel also stores this computed hash internally within its struct bpf_map:

    struct bpf_map {
    +   u64 sha[4];
        const struct bpf_map_ops *ops;
        struct bpf_map *inner_map_meta;
    };

## BPF_MAP_MAKE_EXCLUSIVE args: (map_fd, sha256_of_future_prog)

Exclusivity ensures that the map can only be used by a future BPF
program whose SHA256 hash matches sha256_of_future_prog.

First, bpf_prog_calc_tag() is updated to compute the SHA256 instead of
SHA1, and this hash is stored in struct bpf_prog_aux:

    @@ -1588,6 +1588,7 @@ struct bpf_prog_aux {
         int cgroup_atype; /* enum cgroup_bpf_attach_type */
         struct bpf_map *cgroup_storage[MAX_BPF_CGROUP_STORAGE_TYPE];
         char name[BPF_OBJ_NAME_LEN];
    +    u64 sha[4];
         u64 (*bpf_exception_cb)(u64 cookie, u64 sp, u64 bp, u64, u64);
         // ...
    };

Once BPF_MAP_MAKE_EXCLUSIVE is called with map_fd and the target
program's SHA256 hash, the kernel marks the map as exclusive. When a
BPF program is subsequently loaded, if it attempts to use this map,
the kernel will compare the program's own SHA256 hash against the one
registered with the map, if matching, it will be added to
prog->used_maps[]. The program load will fail if the hashes do not
match or if the map is already in use by another (non-matching)
exclusive program.

Any program with a different SHA256 will fail to load if it attempts
to use the exclusive map.

NOTE: Exclusive maps cannot be added as inner maps.

# Light Skeleton Sequence (Userspace Example)

    // Create and populate the metadata map

    map_fd = skel_map_create(BPF_MAP_TYPE_ARRAY, "__loader.map", 4,
opts->data_sz, 1);
    skel_map_update_elem(map_fd, &key, opts->data, 0);

    // Freeze the map to prevent further userspace modifications.
    // This makes its content immutable from userspace.

    skel_map_freeze(map_fd);

    // Make the map exclusive to the intended loader program.
    // sha256_of_loader_prog is the hash of the I_loader binary
    skel_map_make_exclusive(map_fd, sha256_of_loader_prog);

    skel_map_get_hash(map_fd, NULL, 0);

    // Load the loader program (I_loader) with its signature.
    opts.ctx = (struct bpf_loader_ctx *)skel;
    opts.data_sz = sizeof(opts_data) - 1;
    opts.data = (void *)opts_data;
    opts.insns_sz = sizeof(opts_insn) - 1;
    opts.insns = (void *)opts_insn;

    opts.signature = … signature of the opts_insn[] bytes…
    opts.signature_size = sizeof(..);
    opts. system_keyring_id  = ...

    OR

    opts.user_keyring_serial = … depending on what flag was used in bpftool.
    err = bpf_load_and_run(&opts);

The kernel verifier will:

    * Compute the hash of the provided I_loader bytecode.
    * Verify the signature against this computed hash.
    * Check if the metadata map (now exclusive) is intended for this
program's hash.

The signature check in the verifier (during BPF_PROG_LOAD):

    verify_pkcs7_signature(prog->aux->sha, sizeof(prog->aux->sha),
sig_from_bpf_attr, …);

This ensures that the loaded loader program (I_loader), including the
embedded expected hash of the metadata (H_meta), is trusted.
Since the loader program is now trusted, it can be entrusted to verify
the actual metadata (M_metadata) read from the (now exclusive and
frozen) map against the embedded (and trusted) H_meta. There is no
Time-of-Check-Time-of-Use (TOCTOU) vulnerability here because:

    * The signature covers the I_loader and its embedded H_meta.
    * The metadata map M_metadata is frozen before the loader program
is loaded and associated with it.
    * The map is made exclusive to the specific (signed and verified)
loader program.

Powered by blists - more mailing lists