The current signature-based module integrity checking has some drawbacks
in combination with reproducible builds:
Either the module signing key is generated at build time, which makes
the build unreproducible, or a static key is used, which precludes
rebuilds by third parties and makes the whole build and packaging
process much more complicated.
Introduce a new mechanism to ensure only well-known modules are loaded
by embedding a list of hashes of all modules built as part of the full
kernel build into vmlinux.

Interest has been proclaimed by NixOS, Arch Linux, Proxmox, SUSE and the
general reproducible builds community.

To properly test the reproducibility in combination with CONFIG_INFO_BTF
another patch or pahole v1.29 is needed:
"[PATCH bpf-next] kbuild, bpf: Enable reproducible BTF generation" [0]

Questions for current patch:
* Naming
* Can the number of built-in modules be retrieved while building
  kernel/module/hashes.o? This would remove the need for the
  preallocation step in link-vmlinux.sh.
* How should this interaction with IMA?

Further improvements:
* Use a LSM/IMA Keyring to store and validate hashes
* Use MODULE_SIG_HASH for configuration
* UAPI for discovery?
* Currently has a permanent memory overhead

[0] https://lore.kernel.org/lkml/20241211-pahole-reproducible-v1-1-22feae19bad9@weissschuh.net/

Signed-off-by: Thomas Weißschuh <linux@weissschuh.net>
---
Changes in v3:
- Rebase on v6.15-rc1
- Use openssl to calculate hash
- Avoid warning if no modules are built
- Simplify module_integrity_check() a bit
- Make incompatibility with INSTALL_MOD_STRIP explicit
- Update docs
- Add IMA cleanups
- Link to v2: https://lore.kernel.org/r/20250120-module-hashes-v2-0-ba1184e27b7f@weissschuh.net

Changes in v2:
- Drop RFC state
- Mention interested parties in cover letter
- Expand Kconfig description
- Add compatibility with CONFIG_MODULE_SIG
- Parallelize module-hashes.sh
- Update Documentation/kbuild/reproducible-builds.rst
- Link to v1: https://lore.kernel.org/r/20241225-module-hashes-v1-0-d710ce7a3fd1@weissschuh.net

---
Thomas Weißschuh (9):
      powerpc/ima: Drop unnecessary check for CONFIG_MODULE_SIG
      ima: efi: Drop unnecessary check for CONFIG_MODULE_SIG/CONFIG_KEXEC_SIG
      kbuild: add stamp file for vmlinux BTF data
      kbuild: generate module BTF based on vmlinux.unstripped
      module: Make module loading policy usable without MODULE_SIG
      module: Move integrity checks into dedicated function
      module: Move lockdown check into generic module loader
      lockdown: Make the relationship to MODULE_SIG a dependency
      module: Introduce hash-based integrity checking

 .gitignore                                   |  1 +
 Documentation/kbuild/reproducible-builds.rst |  5 ++-
 Makefile                                     |  8 +++-
 arch/powerpc/kernel/ima_arch.c               |  3 +-
 include/asm-generic/vmlinux.lds.h            | 11 ++++++
 include/linux/module.h                       |  8 ++--
 include/linux/module_hashes.h                | 17 +++++++++
 kernel/module/Kconfig                        | 21 ++++++++++-
 kernel/module/Makefile                       |  1 +
 kernel/module/hashes.c                       | 56 ++++++++++++++++++++++++++++
 kernel/module/internal.h                     |  8 +---
 kernel/module/main.c                         | 51 ++++++++++++++++++++++---
 kernel/module/signing.c                      | 24 +-----------
 scripts/Makefile.modfinal                    | 18 ++++++---
 scripts/Makefile.modinst                     |  4 ++
 scripts/Makefile.vmlinux                     |  5 +++
 scripts/link-vmlinux.sh                      | 31 ++++++++++++++-
 scripts/module-hashes.sh                     | 26 +++++++++++++
 security/integrity/ima/ima_efi.c             |  6 +--
 security/lockdown/Kconfig                    |  2 +-
 20 files changed, 250 insertions(+), 56 deletions(-)
---
base-commit: 0af2f6be1b4281385b618cb86ad946eded089ac8
change-id: 20241225-module-hashes-7a50a7cc2a30

Best regards,
-- 
Thomas Weißschuh <linux@weissschuh.net>

On Tue, 2025-04-29 at 15:04 +0200, Thomas Weißschuh wrote:
> The current signature-based module integrity checking has some
> drawbacks in combination with reproducible builds:
> Either the module signing key is generated at build time, which makes
> the build unreproducible,

I don't believe it does: as long as you know what the key was, which
you can get from the kernel keyring, you can exactly reproduce the core
build (it's a public key after all and really equivalent to built in
configuration).  Is the fact that you have to boot the kernel to get
the key the problem?  In which case we could insist it be shipped in
the kernel packaging.

>  or a static key is used, which precludes rebuilds by third parties
> and makes the whole build and packaging process much more
> complicated. 

No, it's the same as above ... as long as you have the public key you
can reproduce the core build with the same end to end hash.

However, is there also a corresponding question of how we verify
reproduceability of kernel builds (and the associated modules ... I
assume for the modules you do strip the appended signature)?  I assume
you're going by the secure boot hash (authenticode hash of the efi stub
and the compressed payload which includes the key).  However, if we had
the vmlinux.o we could do a much more nuanced hash to verify the build,
say by placing the keyring data in a section that isn't hashed.

Regards,

James

On 2025-04-29 10:05:04 [-0400], James Bottomley wrote:
> On Tue, 2025-04-29 at 15:04 +0200, Thomas Weißschuh wrote:
> > The current signature-based module integrity checking has some
> > drawbacks in combination with reproducible builds:
> > Either the module signing key is generated at build time, which makes
> > the build unreproducible,
> 
> I don't believe it does: as long as you know what the key was, which
> you can get from the kernel keyring, you can exactly reproduce the core
> build (it's a public key after all and really equivalent to built in
> configuration).  Is the fact that you have to boot the kernel to get
> the key the problem?  In which case we could insist it be shipped in
> the kernel packaging.

The kernel itself is signed. This is not a problem because distros have
the "unsigned" package which is used for comparison.
The modules are signed by an ephemeral key which is created at build
time. This is where the problem starts:
- the public key is embedded into the kernel. Extracting it with tooling
  is possible (or it is part of the kernel package). Adding this key
  into the build process while rebuilding the kernel should work.
  This will however alter the build process and is not *the* original
  one, which was used to build the image.

- the private key remains unknown which means the modules can not be
  signed. The rebuilding would need to get past this limitation and the
  logic must not be affected by this "change". Then the modules need to
  be stripped of their signature for the comparison.

Doing all this requires additional handling/ tooling on the "validation"
infrastructure. This infrastructure works currently without special
care.
Adding special care will not build the package exactly like it has been
built originally _and_ the results need to be interpreted (as in we
remove this signature and do this and now it is fine).

Adding hashes of each module into the kernel image looks like a
reasonable thing to do. I don't see any downsides to this. Yes, you are
limited to the modules available at build time but this is also the case
today with the ephemeral key. It is meant for distros not for individual
developers testing their code.

With this change it is possible to build a kernel and its modules and
put the result in an archive such as tar/ deb/ rpm. You can build the
package _again_ following exactly the same steps as you did before and
the result will be the identical archive.
Bit by bit.
No need for interpreting the results, stripping signatures or altering
the build process.

I fully agree with this approach. I don't like the big hash array but I
have an idea how to optimize that part. So I don't see a problem in the
long term.

> Regards,
> 
> James

Sebastian

On 2025-11-19 16:48:34 [+0100], Sebastian Andrzej Siewior wrote:
> I fully agree with this approach. I don't like the big hash array but I
> have an idea how to optimize that part. So I don't see a problem in the
> long term.

The following PoC creates a merkle tree from a set files ending with .ko
within the specified directory. It will write a .hash files containing
the required hash for each file for its validation. The root hash is
saved as "hash_root" and "hash_root.h" in the directory.

The Debian kernel shipps 4256 modules:

| $ time ./compute_hashes mods_deb
| Files 4256 levels: 13 root hash: 97f8f439d63938ed74f48ec46dbd75c2b5e5b49f012a414e89b6f0e0f06efe84
| 
| real    0m0,732s
| user    0m0,304s
| sys     0m0,427s

This computes the hashes for all the modules it found in the mods_deb
folder.
The kernel needs the root hash (for sha256 32 bytes) and the depth of
the tree (4 bytes). That are 36 bytes regardless of the number of
modules that are built.
In this case, the attached hash for each module is 420 bytes. This is 4
bytes (position in the tree) + 13 (depth) * 32.
The verification process requires 13 hash operation to hash through the
tree and verify against the root hash.

For convience, the following PoC can also be found at
	https://git.kernel.org/pub/scm/linux/kernel/git/bigeasy/mtree-hashed-mods.git/

which also includes a small testsuite.

diff --git a/Makefile b/Makefile
new file mode 100644
index 0000000000000..e4a35c15f0a94
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,7 @@
+CC := gcc
+CFLAGS := -O2 -g -Wall
+LDLIBS := -lcrypto
+
+all: compute_hashes mk-files verify_hash
+test: compute_hashes mk-files verify_hash
+	./verify_test.sh
diff --git a/compute_hashes.c b/compute_hashes.c
new file mode 100644
index 0000000000000..da61b214137b8
--- /dev/null
+++ b/compute_hashes.c
@@ -0,0 +1,407 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/*
+ * Compute hashes for individual files and build a merkle tree.
+ *
+ * Author: Sebastian Andrzej Siewior <sebastian@breakpoint.cc>
+ *
+ */
+#define _GNU_SOURCE 1
+#include <ftw.h>
+#include <unistd.h>
+#include <fcntl.h>
+#include <stdio.h>
+#include <string.h>
+#include <stdlib.h>
+
+#include <sys/stat.h>
+#include <sys/mman.h>
+
+#include <openssl/evp.h>
+
+#include "helpers.h"
+
+struct file_entry {
+	char *name;
+	size_t fsize;
+	unsigned int pos;
+	unsigned char hash[EVP_MAX_MD_SIZE];
+};
+
+static struct file_entry *fh_list;
+static size_t num_files;
+
+struct leaf_hash {
+	unsigned char hash[EVP_MAX_MD_SIZE];
+};
+
+struct mtree {
+	struct leaf_hash **l;
+	unsigned int *entries;
+	unsigned int levels;
+};
+
+static unsigned int get_pow2(unsigned int val)
+{
+	return 31 - __builtin_clz(val);
+}
+
+static unsigned int roundup_pow2(unsigned int val)
+{
+	return 1 << (get_pow2(val - 1) + 1);
+}
+
+static unsigned int log2_roundup(unsigned int val)
+{
+	return get_pow2(roundup_pow2(val));
+}
+
+static int str_endswith(const char *s, const char *suffix)
+{
+	size_t ls, lf;
+
+	ls = strlen(s);
+	lf = strlen(suffix);
+
+	if (ls <= lf)
+		return -1;
+	return strcmp(s + ls - lf, suffix);
+}
+
+static void __print_hash(unsigned char *h)
+{
+	int i;
+
+	for (i = 0; i < hash_size; i++)
+		printf("%02x", h[i]);
+}
+
+static void print_hash(unsigned char *h)
+{
+	__print_hash(h);
+	printf("\n");
+}
+
+static int hash_file(struct file_entry *fe)
+{
+	void *mem;
+	int fd;
+
+	fd = open(fe->name, O_RDONLY);
+	if (fd < 0) {
+		printf("Failed to open %s: %m\n", fe->name);
+		exit(1);
+	}
+
+	mem = mmap(NULL, fe->fsize, PROT_READ, MAP_SHARED, fd, 0);
+	close(fd);
+
+	if (mem == MAP_FAILED) {
+		printf("Failed to mmap %s: %m\n", fe->name);
+		exit(1);
+	}
+
+	hash_data(mem, fe->pos, fe->fsize, fe->hash);
+
+	munmap(mem, fe->fsize);
+	return 0;
+}
+
+static int add_files_cb(const char *fpath, const struct stat *sb, int tflag,
+			struct FTW *ftwbuf)
+{
+	if (tflag != FTW_F)
+		return 0;
+
+	if (str_endswith(fpath, ".ko"))
+		return 0;
+
+	fh_list = xrealloc(fh_list, (num_files + 1) * sizeof (struct file_entry));
+
+	fh_list[num_files].name = strdup(fpath);
+	if (!fh_list[num_files].name) {
+		printf("Failed to allocate memory\n");
+		exit(1);
+	}
+
+	fh_list[num_files].fsize = sb->st_size;
+
+	num_files++;
+	return 0;
+}
+
+static int cmp_file_entry(const void *p1, const void *p2)
+{
+	const struct file_entry *f1, *f2;
+
+	f1 = p1;
+	f2 = p2;
+
+	return strcmp(f1->name, f2->name);
+}
+
+static struct mtree *build_merkle(struct file_entry *fh, size_t num)
+{
+	unsigned int i, le;
+	struct mtree *mt;
+
+	mt = xmalloc(sizeof(struct mtree));
+	mt->levels = log2_roundup(num);
+	mt->l = xcalloc(sizeof(struct leaf_hash *), mt->levels);
+
+	mt->entries = xcalloc(sizeof(unsigned int), mt->levels);
+	le = num / 2;
+	if (num & 1)
+		le++;
+	mt->entries[0] = le;
+	mt->l[0] = xcalloc(sizeof(struct leaf_hash), le);
+
+	/* First level of pairs */
+	for (i = 0; i < num; i+= 2) {
+		if (i == num - 1) {
+			/* Odd number of files, no pair. Hash with itself */
+			hash_entry(fh[i].hash, fh[i].hash, mt->l[0][i/2].hash);
+		} else {
+			hash_entry(fh[i].hash, fh[i + 1].hash, mt->l[0][i/2].hash);
+		}
+	}
+	for (i = 1; i < mt->levels; i++) {
+		int n;
+		int odd = 0;
+
+		if (le & 1) {
+			le++;
+			odd++;
+		}
+
+		mt->entries[i] = le / 2;
+		mt->l[i] = xcalloc(sizeof(struct leaf_hash), le);
+
+		for (n = 0; n < le; n += 2) {
+			if (n == le - 2 && odd) {
+				/* Odd number of pairs, no pair. Hash with itself */
+				hash_entry(mt->l[i - 1][n].hash, mt->l[i - 1][n].hash,
+					   mt->l[i][n/2].hash);
+			} else {
+				hash_entry(mt->l[i - 1][n].hash, mt->l[i - 1][n +1].hash,
+					   mt->l[i][n/2].hash);
+			}
+		}
+		le =  mt->entries[i];
+	}
+	return mt;
+}
+
+static void free_mtree(struct mtree *mt)
+{
+	int i;
+
+	for (i = 0; i < mt->levels; i++)
+		free(mt->l[i]);
+
+	free(mt->l);
+	free(mt->entries);
+	free(mt);
+}
+
+static void write_be_int(int fd, unsigned int v)
+{
+	unsigned int be_val = host_to_be32(v);
+
+	if (write(fd, &be_val, sizeof(be_val)) != sizeof(be_val)) {
+		printf("Failed writting to file: %m\n");
+		exit(1);
+	}
+}
+
+static void write_hash(int fd, const void *h)
+{
+	ssize_t wr;
+
+	wr = write(fd, h, hash_size);
+	if (wr != hash_size) {
+		printf("Failed writting to file: %m\n");
+		exit(1);
+	}
+}
+
+static void build_proof(struct mtree *mt, unsigned int n, int fd)
+{
+	unsigned char cur[EVP_MAX_MD_SIZE];
+	unsigned char tmp[EVP_MAX_MD_SIZE];
+	struct file_entry *fe, *fe_sib;
+	unsigned int i;
+
+	fe = &fh_list[n];
+
+	if ((n & 1) == 0) {
+		/* No pair, hash with itself */
+		if (n + 1 == num_files)
+			fe_sib = fe;
+		else
+			fe_sib = &fh_list[n + 1];
+	} else {
+		fe_sib = &fh_list[n - 1];
+	}
+	/* First comes the node position into the file */
+	write_be_int(fd, n);
+
+	if ((n & 1) == 0)
+		hash_entry(fe->hash, fe_sib->hash, cur);
+	else
+		hash_entry(fe_sib->hash, fe->hash, cur);
+
+	/* Next is the sibling hash, followed by hashes in the tree */
+	write_hash(fd, fe_sib->hash);
+
+	for (i = 0; i < mt->levels - 1; i++) {
+		n >>= 1;
+		if ((n & 1) == 0) {
+			void *h;
+
+			/* No pair, hash with itself */
+			if (n + 1 == mt->entries[i])
+				h = cur;
+			else
+				h = mt->l[i][n + 1].hash;
+
+			hash_entry(cur, h, tmp);
+			write_hash(fd, h);
+		} else {
+			hash_entry(mt->l[i][n - 1].hash, cur, tmp);
+			write_hash(fd, mt->l[i][n - 1].hash);
+		}
+		memcpy(cur, tmp, hash_size);
+	}
+
+	 /* After all that, the end hash should match the root hash */
+	if (memcmp(cur, mt->l[mt->levels - 1][0].hash, hash_size))
+		printf("MISS-MATCH\n");
+}
+
+static void write_merkle_root(struct mtree *mt, const char *fp)
+{
+	char buf[1024];
+	int fd;
+
+	if (snprintf(buf, sizeof(buf), "%s/hash_root", fp) >= sizeof(buf)) {
+		printf("Root dir too long\n");
+		exit(1);
+	}
+	fd = open(buf, O_WRONLY | O_CREAT | O_TRUNC, DEF_F_PERM);
+	if (fd < 0) {
+		printf("Failed to create %s: %m\n", buf);
+		exit(1);
+	}
+
+	write_be_int(fd, mt->levels);
+	write_hash(fd, mt->l[mt->levels - 1][0].hash);
+	close(fd);
+	printf("Files %ld levels: %d root hash: ", num_files, mt->levels);
+	print_hash(mt->l[mt->levels - 1][0].hash);
+}
+
+static void write_merkle_root_h(struct mtree *mt, const char *fp)
+{
+	char buf[1024];
+	unsigned int i;
+	unsigned char *h;
+	FILE *f;
+
+	if (snprintf(buf, sizeof(buf), "%s/hash_root.h", fp) >= sizeof(buf)) {
+		printf("Root dir too long\n");
+		exit(1);
+	}
+	f = fopen(buf, "w");
+	if (!f) {
+		printf("Failed to create %s: %m\n", buf);
+		exit(1);
+	}
+	h = mt->l[mt->levels - 1][0].hash;
+
+	fprintf(f, "#ifndef __HASH_ROOT_TREE_H__\n");
+	fprintf(f, "#define __HASH_ROOT_TREE_H__\n\n");
+	fprintf(f, "unsigned int hashed_mods_levels = %u;\n", mt->levels);
+	fprintf(f, "unsigned char hashed_mods_root[%d] = {", hash_size);
+	for (i = 0; i < hash_size; i++) {
+		char *space = "";
+
+		if (!(i % 8))
+			fprintf(f, "\n\t");
+
+		if ((i + 1) % 8)
+			space = " ";
+
+		fprintf(f, "0x%02x,%s", h[i], space);
+	}
+	fprintf(f, "\n};\n#endif\n");
+	fclose(f);
+}
+
+int main(int argc, char *argv[])
+{
+	const EVP_MD *hash_evp;
+	char *fp;
+	struct mtree *mt;
+	int i;
+
+	ctx = EVP_MD_CTX_new();
+	if (!ctx)
+		goto err_ossl;
+
+	if (argc != 2) {
+		printf("%s: folder\n", argv[0]);
+		return 1;
+	}
+	fp = argv[1];
+
+	hash_evp = EVP_sha256();
+	hash_size = EVP_MD_get_size(hash_evp);
+	if (hash_size <= 0)
+		goto err_ossl;
+
+	if (EVP_DigestInit_ex(ctx, hash_evp, NULL) != 1)
+		goto err_ossl;
+
+	nftw(fp, add_files_cb, 64, 0);
+
+	qsort(fh_list, num_files, sizeof(struct file_entry), cmp_file_entry);
+
+	for (i = 0; i < num_files; i++) {
+		fh_list[i].pos = i;
+		hash_file(&fh_list[i]);
+	}
+
+	mt = build_merkle(fh_list, num_files);
+	write_merkle_root(mt, fp);
+	write_merkle_root_h(mt, fp);
+	for (i = 0; i < num_files; i++) {
+		char signame[1024];
+		int fd;
+		int ret;
+
+		ret = snprintf(signame, sizeof(signame), "%s.hash", fh_list[i].name);
+		if (ret >= sizeof(signame)) {
+			printf("path + name too long\n");
+			return 1;
+		}
+		fd = open(signame, O_WRONLY | O_CREAT | O_TRUNC, DEF_F_PERM);
+		if (fd < 0) {
+			printf("Can't create %s: %m\n", signame);
+			return 1;
+		}
+		build_proof(mt, i, fd);
+		close(fd);
+	}
+
+	free_mtree(mt);
+	for (i = 0; i < num_files; i++)
+		free(fh_list[i].name);
+	free(fh_list);
+
+	EVP_MD_CTX_free(ctx);
+	return 0;
+
+err_ossl:
+	printf("libssl operation failed\n");
+	return 1;
+}
diff --git a/helpers.h b/helpers.h
new file mode 100644
index 0000000000000..f52ad3543f890
--- /dev/null
+++ b/helpers.h
@@ -0,0 +1,109 @@
+#ifndef __HELPERS_H__
+#define __HELPERS_H__
+
+static EVP_MD_CTX *ctx;
+static int hash_size;
+
+#define DEF_F_PERM (S_IRUSR|S_IWUSR|S_IRGRP|S_IROTH) /* 0644*/
+#define DEF_D_PERM (S_IRUSR|S_IWUSR|S_IXUSR|S_IRGRP|S_IXGRP|S_IROTH|S_IXOTH) /* 0755*/
+
+static unsigned int host_to_be32(unsigned int v)
+{
+#if __BYTE_ORDER__ == __LITTLE_ENDIAN
+	return __builtin_bswap32(v);
+#elif __BYTE_ORDER__ == __BIG_ENDIAN
+	return  v;
+#else
+#error Missing endian define
+#endif
+}
+
+static inline void *xcalloc(size_t n, size_t size)
+{
+	void *p;
+
+	p = calloc(n, size);
+	if (p)
+		return p;
+	printf("Memory allocation failed\n");
+	exit(1);
+}
+
+static void *xmalloc(size_t size)
+{
+	void *p;
+
+	p = malloc(size);
+	if (p)
+		return p;
+	printf("Memory allocation failed\n");
+	exit(1);
+}
+
+static inline void *xrealloc(void *oldp, size_t size)
+{
+	void *p;
+
+	p = realloc(oldp, size);
+	if (p)
+		return p;
+	printf("Memory allocation failed\n");
+	exit(1);
+}
+
+static void hash_data(void *p, unsigned int pos, size_t size, void *ret_hash)
+{
+	unsigned char magic = 0x01;
+	unsigned int pos_be;
+
+	pos_be = host_to_be32(pos);
+	if (EVP_DigestInit_ex(ctx, NULL, NULL) != 1)
+		goto err;
+
+	if (EVP_DigestUpdate(ctx, &magic, sizeof(magic)) != 1)
+		goto err;
+
+	if (EVP_DigestUpdate(ctx, &pos_be, sizeof(pos_be)) != 1)
+		goto err;
+
+	if (EVP_DigestUpdate(ctx, p, size) != 1)
+		goto err;
+
+	if (EVP_DigestFinal_ex(ctx, ret_hash, NULL) != 1)
+		goto err;
+
+	return;
+
+err:
+	printf("libssl operation failed\n");
+	exit(1);
+}
+static void hash_entry(void *left, void *right, void *ret_hash)
+{
+	unsigned char magic = 0x02;
+
+	if (EVP_DigestInit_ex(ctx, NULL, NULL) != 1)
+		goto err;
+
+	if (EVP_DigestUpdate(ctx, &magic, sizeof(magic)) != 1)
+		goto err;
+
+	if (EVP_DigestUpdate(ctx, left, hash_size) != 1)
+		goto err;
+
+	if (EVP_DigestUpdate(ctx, right, hash_size) != 1)
+		goto err;
+
+	if (EVP_DigestFinal_ex(ctx, ret_hash, NULL) != 1)
+		goto err;
+
+	return;
+
+err:
+	printf("libssl operation failed\n");
+	exit(1);
+}
+
+
+
+#endif
diff --git a/verify_hash.c b/verify_hash.c
new file mode 100644
index 0000000000000..0a842f27f1ebc
--- /dev/null
+++ b/verify_hash.c
@@ -0,0 +1,206 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/*
+ * Verify a file against and its hash against a merkle tree hash.
+ *
+ * Author: Sebastian Andrzej Siewior <sebastian@breakpoint.cc>
+ *
+ */
+#define _GNU_SOURCE 1
+#include <unistd.h>
+#include <fcntl.h>
+#include <string.h>
+#include <stdlib.h>
+
+#include <sys/stat.h>
+#include <sys/mman.h>
+
+#include <openssl/evp.h>
+
+#include "helpers.h"
+
+struct hash_root {
+	unsigned int level;
+	unsigned char hash[EVP_MAX_MD_SIZE];
+};
+
+struct verify_sig {
+	unsigned int pos;
+	char hash_sigs[];
+};
+
+static int hash_file(const char *f, unsigned char *hash, unsigned int pos)
+{
+	struct stat sb;
+	int fd, ret;
+	void *mem;
+
+	fd = open(f, O_RDONLY);
+	if (fd < 0) {
+		printf("Failed to open %s: %m\n", f);
+		exit(1);
+	}
+
+	ret = fstat(fd, &sb);
+	if (ret) {
+		printf("stat failed %m\n");
+		exit(1);
+	}
+
+	mem = mmap(NULL, sb.st_size, PROT_READ, MAP_SHARED, fd, 0);
+	close(fd);
+
+	if (mem == MAP_FAILED) {
+		printf("Failed to mmap file: %m\n");
+		exit(1);
+	}
+
+	hash_data(mem, pos, sb.st_size, hash);
+
+	munmap(mem, sb.st_size);
+	return 0;
+}
+
+static void verify_hash(struct hash_root *hr, struct verify_sig *vs, unsigned char *cur,
+			const char *fn)
+{
+	unsigned char tmp[EVP_MAX_MD_SIZE];
+	unsigned sig_ofs = 0;
+	unsigned int i, n;
+
+	n = vs->pos;
+	if ((n & 1) == 0)
+		hash_entry(cur, &vs->hash_sigs[sig_ofs], tmp);
+	else
+		hash_entry(&vs->hash_sigs[sig_ofs], cur, tmp);
+
+	memcpy(cur, tmp, hash_size);
+	sig_ofs += hash_size;
+	for (i = 0; i < hr->level - 1; i++) {
+		n >>= 1;
+		if ((n & 1) == 0) {
+			hash_entry(cur, &vs->hash_sigs[sig_ofs], tmp);
+		} else {
+			hash_entry(&vs->hash_sigs[sig_ofs], cur, tmp);
+		}
+		memcpy(cur, tmp, hash_size);
+		sig_ofs += hash_size;
+	}
+
+	if (!memcmp(cur, hr->hash, hash_size)) {
+		exit(0);
+	} else {
+		printf("MISS-MATCH on %s\n", fn);
+		exit(1);
+	}
+}
+
+static void read_be_int(int fd, unsigned int *val)
+{
+	unsigned int val_be;
+
+	if (read(fd, &val_be, sizeof(val_be)) != sizeof(val_be)) {
+		printf("Can't read from file\n");
+		exit(1);
+	}
+	*val = host_to_be32(val_be);
+}
+
+struct hash_root *read_root_hash(const char *f)
+{
+	int fd;
+	struct hash_root *hr;
+
+	hr = xmalloc(sizeof(*hr));
+	fd = open(f, O_RDONLY);
+	if (fd < 0) {
+		printf("Can't open %s: %m\n", f);
+		exit(1);
+	}
+	read_be_int(fd, &hr->level);
+	if (read(fd, hr->hash, hash_size) != hash_size) {
+		printf("Can't read complete hash (%u): %m\n",
+		       hash_size);
+		exit(1);
+	}
+	close(fd);
+	return hr;
+}
+
+static void load_hash_sig(const char *f, struct verify_sig *verify_sig,
+			  unsigned int sig_num)
+{
+	ssize_t total_hash_size;
+	struct stat sb;
+	char buf[1024];
+	int fd;
+	int ret;
+
+	total_hash_size = sig_num * hash_size;
+
+	ret = snprintf(buf, sizeof(buf), "%s.hash", f);
+	if (ret >= sizeof(buf)) {
+		printf("Too long\n");
+		exit(1);
+	}
+	fd = open(buf, O_RDONLY);
+	if (fd < 0) {
+		printf("Failed to open %s\n", buf);
+		exit(1);
+	}
+	read_be_int(fd, &verify_sig->pos);
+
+	ret = fstat(fd, &sb);
+	if (ret < 0) {
+		printf("Failed to stat %s: %m\n", f);
+		exit(1);
+	}
+
+	if (sb.st_size != total_hash_size + 4) {
+		printf("Unexpected signature size: Expected %ld vs found %ld\n",
+		       total_hash_size + 4, sb.st_size);
+		exit(1);
+	}
+	if (read(fd, verify_sig->hash_sigs, total_hash_size) != total_hash_size) {
+		printf("Failed to read the signature: %m\n");
+		exit(1);
+	}
+	close(fd);
+}
+
+int main(int argc, char *argv[])
+{
+	struct hash_root *hash_root;
+	struct verify_sig *vsig;
+	unsigned char fhash[EVP_MAX_MD_SIZE];
+	const EVP_MD *hash_evp;
+
+	ctx = EVP_MD_CTX_new();
+	if (!ctx)
+		goto err;
+
+	if (argc != 3) {
+		printf("%s: hash_root module\n", argv[0]);
+		return 1;
+	}
+
+	hash_evp = EVP_sha256();
+	hash_size = EVP_MD_get_size(hash_evp);
+	if (hash_size <= 0)
+		goto err;
+
+	if (EVP_DigestInit_ex(ctx, hash_evp, NULL) != 1)
+		goto err;
+
+	hash_root = read_root_hash(argv[1]);
+	vsig = xmalloc(sizeof(struct verify_sig) + hash_root->level * hash_size);
+
+	load_hash_sig(argv[2], vsig, hash_root->level);
+	hash_file(argv[2], fhash, vsig->pos);
+	verify_hash(hash_root, vsig, fhash, argv[2]);
+
+	EVP_MD_CTX_free(ctx);
+	return 0;
+err:
+	printf("libssl operation failed\n");
+	return 1;
+}
-- 
2.51.0


Sebastian

Hi Sebastian,

On 2025-11-23 18:05:02+0100, Sebastian Andrzej Siewior wrote:
> On 2025-11-19 16:48:34 [+0100], Sebastian Andrzej Siewior wrote:
> > I fully agree with this approach. I don't like the big hash array but I
> > have an idea how to optimize that part. So I don't see a problem in the
> > long term.
> 
> The following PoC creates a merkle tree from a set files ending with .ko
> within the specified directory. It will write a .hash files containing
> the required hash for each file for its validation. The root hash is
> saved as "hash_root" and "hash_root.h" in the directory.

Thanks a lot!

> The Debian kernel shipps 4256 modules:
> 
> | $ time ./compute_hashes mods_deb
> | Files 4256 levels: 13 root hash: 97f8f439d63938ed74f48ec46dbd75c2b5e5b49f012a414e89b6f0e0f06efe84
> | 
> | real    0m0,732s
> | user    0m0,304s
> | sys     0m0,427s
> 
> This computes the hashes for all the modules it found in the mods_deb
> folder.
> The kernel needs the root hash (for sha256 32 bytes) and the depth of
> the tree (4 bytes). That are 36 bytes regardless of the number of
> modules that are built.
> In this case, the attached hash for each module is 420 bytes. This is 4
> bytes (position in the tree) + 13 (depth) * 32.
> The verification process requires 13 hash operation to hash through the
> tree and verify against the root hash.

We'll need to store the proof together with the modules somewhere.
Regular module signatures are stored as PKCS#7 and appended to the module
file. If we can also encode the merkle proof as PKCS#7, the integration
into the existing infrastructure should be much easier.
It will require some changes to this series, but honestly the Merkle
tree aproach looks like the clear winner here.

> For convience, the following PoC can also be found at
> 	https://git.kernel.org/pub/scm/linux/kernel/git/bigeasy/mtree-hashed-mods.git/
> 
> which also includes a small testsuite.

(...)


Thomas

Hi James,

On 2025-04-29 10:05:04-0400, James Bottomley wrote:
> On Tue, 2025-04-29 at 15:04 +0200, Thomas Weißschuh wrote:
> > The current signature-based module integrity checking has some
> > drawbacks in combination with reproducible builds:
> > Either the module signing key is generated at build time, which makes
> > the build unreproducible,
> 
> I don't believe it does: as long as you know what the key was, which
> you can get from the kernel keyring, you can exactly reproduce the core
> build (it's a public key after all and really equivalent to built in
> configuration).  Is the fact that you have to boot the kernel to get
> the key the problem?  In which case we could insist it be shipped in
> the kernel packaging.

See below.

> >  or a static key is used, which precludes rebuilds by third parties
> > and makes the whole build and packaging process much more
> > complicated. 
> 
> No, it's the same as above ... as long as you have the public key you
> can reproduce the core build with the same end to end hash.

While the scheme you propose does allow verification of rebuildability,
it does not satisfy the requirements for a reproducible build as
understood by the general reproducible builds community:

	When is a build reproducible?

	A build is reproducible if given the same source code, build environment
	and build instructions, any party can recreate bit-by-bit identical
	copies of all specified artifacts.

	The relevant attributes of the build environment, the build instructions
	and the source code as well as the expected reproducible artifacts are
	defined by the authors or distributors. The artifacts of a build are the
	parts of the build results that are the desired primary output.

https://reproducible-builds.org/docs/definition/

Specifically the output of a previous build (the public key, module
signatures) is not available during the rebuild or verification.

> However, is there also a corresponding question of how we verify
> reproduceability of kernel builds (and the associated modules ... I
> assume for the modules you do strip the appended signature)?

Currently distros either don't enforce the reproducibility of the
kernel package at all or disable MODULE_SIG.
With the proposed scheme there would be no signatures on builtin modules.

> I assume
> you're going by the secure boot hash (authenticode hash of the efi stub
> and the compressed payload which includes the key).  However, if we had
> the vmlinux.o we could do a much more nuanced hash to verify the build,
> say by placing the keyring data in a section that isn't hashed.

The currently existing tooling does not have any nuance in its
verifications. It just compares bit-by-bit.
I think this is intentional as any bespoke per-package logic would
introduce possible failure modes and stand in the way of implementing
multiple completely independent verification toolsets.
While bespoke tools like diffoscope exist, these are only for
development and debugging. Not not for the reproducibiliy check itself.

How to handle secure-boot with distro keys is not yet clearly defined.
I see two possibilities, which should be possible with the proposed
scheme, both starting with the build of an unsigned kernel package.
Then a signature would be computed on private infrastructure and either
* shipped in a standalone package, to be combined with the kernel when
  that is installed to the ESP/flash etc.
* used as input of a signed kernel package where it is combined with the
  unsigned kernel image.


Thomas

On Fri, 2025-05-02 at 08:53 +0200, Thomas Weißschuh wrote:
> Hi James,
> 
> On 2025-04-29 10:05:04-0400, James Bottomley wrote:
> > On Tue, 2025-04-29 at 15:04 +0200, Thomas Weißschuh wrote:
> > > The current signature-based module integrity checking has some
> > > drawbacks in combination with reproducible builds:
> > > Either the module signing key is generated at build time, which
> > > makes the build unreproducible,
> > 
> > I don't believe it does: as long as you know what the key was,
> > which you can get from the kernel keyring, you can exactly
> > reproduce the core build (it's a public key after all and really
> > equivalent to built in configuration).  Is the fact that you have
> > to boot the kernel to get the key the problem?  In which case we
> > could insist it be shipped in the kernel packaging.
> 
> See below.
> 
> > >  or a static key is used, which precludes rebuilds by third
> > > parties and makes the whole build and packaging process much more
> > > complicated. 
> > 
> > No, it's the same as above ... as long as you have the public key
> > you can reproduce the core build with the same end to end hash.
> 
> While the scheme you propose does allow verification of
> rebuildability, it does not satisfy the requirements for a
> reproducible build as understood by the general reproducible builds
> community:
> 
> 	When is a build reproducible?
> 
> 	A build is reproducible if given the same source code, build
> environment
> 	and build instructions, any party can recreate bit-by-bit
> identical
> 	copies of all specified artifacts.
> 
> 	The relevant attributes of the build environment, the build
> instructions
> 	and the source code as well as the expected reproducible
> artifacts are
> 	defined by the authors or distributors. The artifacts of a
> build are the
> 	parts of the build results that are the desired primary
> output.
> 
> https://reproducible-builds.org/docs/definition/

That's a doctor doctor problem, and also if we adopted your
interpretation would mean that most kernel packages can never be
reproducible.  The clue is even in the "any party can recreate bit-by-
bit identical copies of all specified artifacts".

Under a your interpretation of the above, any signed binary isn't
"reproducible" even if the underlying build was, which means any secure
boot kernel would never be reproducible because it also has to be a
signed binary.  The solution is simple: can you strip the signature and
reproduce the build?  If yes, then the build is reproducible and even
fits with the "any party can recreate ..." above.   This is the
interpretation pretty much everyone else has been using.  It's why
people like Intel with source only availability and Intel build only
signing tout reproduceability: they only issue signed confidential VM
firmware, but you can technically reproduce the build of the firmware
minus the signature but you can never sign it.

> Specifically the output of any party can recreate bit-by-bit
> identical copies of all specified artifacta previous build (the
> public key, module signatures) is not available during the rebuild or
> verification.

You just strip the signatures before verifying reproducibility.

> > However, is there also a corresponding question of how we verify
> > reproduceability of kernel builds (and the associated modules ... I
> > assume for the modules you do strip the appended signature)?
> 
> Currently distros either don't enforce the reproducibility of the
> kernel package at all or disable MODULE_SIG.
> With the proposed scheme there would be no signatures on builtin
> modules.

If you take off the appended signature off the module, you can verify
reproduceability.

> > I assume you're going by the secure boot hash (authenticode hash of
> > the efi stub and the compressed payload which includes the key). 
> > However, if we had the vmlinux.o we could do a much more nuanced
> > hash to verify the build, say by placing the keyring data in a
> > section that isn't hashed.
> 
> The currently existing tooling does not have any nuance in its
> verifications. It just compares bit-by-bit.

So I think fixing that might be what you want.  All current secure
build processes (hermetic builds, SLSA and the like) are requiring
output provenance (i.e. signed artifacts).  If you try to stand like
Canute against this tide saying "no signed builds", you're simply
opposing progress for the sake of it, particularly when stripping the
signatures for comparison is easy.

> I think this is intentional as any bespoke per-package logic would
> introduce possible failure modes and stand in the way of implementing
> multiple completely independent verification toolsets.
> While bespoke tools like diffoscope exist, these are only for
> development and debugging. Not not for the reproducibiliy check
> itself.

So you think stripping signatures is failure prone?  If that were the
case then so would be verifying signatures upon which our whole secure
boot and signed module loading is based.


> How to handle secure-boot with distro keys is not yet clearly
> defined. I see two possibilities, which should be possible with the
> proposed scheme, both starting with the build of an unsigned kernel
> package. Then a signature would be computed on private infrastructure
> and either
> * shipped in a standalone package, to be combined with the kernel
> when that is installed to the ESP/flash etc.
> * used as input of a signed kernel package where it is combined with
> the unsigned kernel image.

Or you simply ship tools to remove the signature;

sbattach --remove <signed efi variable>

already does this for you ...

Regards,

James

On 5/2/25 3:30 PM, James Bottomley wrote:
> Under a your interpretation of the above, any signed binary isn't
> "reproducible" even if the underlying build was, which means any secure
> boot kernel would never be reproducible because it also has to be a
> signed binary.  The solution is simple: can you strip the signature and
> reproduce the build?  If yes, then the build is reproducible and even
> fits with the "any party can recreate ..." above.   This is the
> interpretation pretty much everyone else has been using.  It's why
> people like Intel with source only availability and Intel build only
> signing tout reproduceability: they only issue signed confidential VM
> firmware, but you can technically reproduce the build of the firmware
> minus the signature but you can never sign it.

The secure-boot signature is easier to deal with, I also think there'd 
be one package that contains just the unsigned kernel+modules (with the 
modules being pinned by a cryptographic hashset), and a second one that 
takes the kernel secure-boot signature as a source-code input, that is 
calculated after the first package was successfully built.

Arch Linux has also considered patching the module-signing-script into 
some kind of oracle that doesn't use any private key and instead selects 
the right pre-computed signature for the given content, but:

- that would be terribly annoying to maintain/operate
- any reproducible builds regression would make the build fail, because 
the kernel wouldn't be bootable

> You just strip the signatures before verifying reproducibility.
> 
[...]
> 
> If you take off the appended signature off the module, you can verify
> reproduceability.
> 
[...]
> 
> So you think stripping signatures is failure prone?  If that were the
> case then so would be verifying signatures upon which our whole secure
> boot and signed module loading is based.
> 
[...]
> 
> Or you simply ship tools to remove the signature;
> 
> sbattach --remove <signed efi variable>
> 
> already does this for you ...

It reads like you assume somebody sits down and explicitly looks at the 
linux package manually, but the reproducible builds tooling considers 
the package content to be fully opaque and doesn't have any 
special-casing of any package:

https://github.com/archlinux/archlinux-repro
https://salsa.debian.org/debian/devscripts/-/blob/main/scripts/debrebuild.pl?ref_type=heads

I'd rather not deal with the consequences of weakening the comparison 
and possibly introducing exploitable loop-holes in any of the layers we 
wouldn't be able to bit-for-bit compare anymore (like e.g. tar).

It would also break the concept of `f(source) -> binary`, "you can 
deterministically derive the binary packages from the documented build 
inputs", and instead you'd always need to fuzzy-match against what 
somebody else built.

cheers,
kpcyrd

On Sat, 2025-05-03 at 01:43 +0200, kpcyrd wrote:
> On 5/2/25 3:30 PM, James Bottomley wrote:
[...]
> > Or you simply ship tools to remove the signature;
> > 
> > sbattach --remove <signed efi variable>
> > 
> > already does this for you ...
> 
> It reads like you assume somebody sits down and explicitly looks at
> the linux package manually, but the reproducible builds tooling
> considers the package content to be fully opaque and doesn't have any
> special-casing of any package:
> 
> https://github.com/archlinux/archlinux-repro
> https://salsa.debian.org/debian/devscripts/-/blob/main/scripts/debrebuild.pl?ref_type=heads

How something is packaged for consumers and what the outputs of a build
are are two entirely different things.  But if you control packaging,
you could actually strip the signatures and place them in an unchecked
section as long as you make sure to combine them on installation.

> I'd rather not deal with the consequences of weakening the comparison
> and possibly introducing exploitable loop-holes in any of the layers
> we wouldn't be able to bit-for-bit compare anymore (like e.g. tar).

To repeat the point: what everyone would like to do to make life easy
is a bit different from what has to be done in the modern era of  build
provenance requirements.

> It would also break the concept of `f(source) -> binary`, "you can 
> deterministically derive the binary packages from the documented
> build inputs", and instead you'd always need to fuzzy-match against
> what somebody else built.

I think you'll find

f -> strip signature ° build

Works in the above equation.  The point being it's deterministic, not
fuzzy.

Regards,

James

Hi Thomas,

On Tue, 2025-04-29 at 15:04 +0200, Thomas Weißschuh wrote:
> The current signature-based module integrity checking has some drawbacks
> in combination with reproducible builds:
> Either the module signing key is generated at build time, which makes
> the build unreproducible, or a static key is used, which precludes
> rebuilds by third parties and makes the whole build and packaging
> process much more complicated.
> Introduce a new mechanism to ensure only well-known modules are loaded
> by embedding a list of hashes of all modules built as part of the full
> kernel build into vmlinux.

From a very high level, I like the idea of including the kernel module hashes
in the kernel image, which is signed, and falling back to verifying other
kernel modules based on signatures.

Removing the CONFIG_MODULE_SIG and CONFIG_KEXEC_SIG checks in the first two
patches is correct, as previously mentioned.  However without these Kconfigs
being enabled, the IMA arch specific policy defines and enforces signature
verification based on the signatures stored in security.ima.  I doubt this is
what was intended.

Changes would be needed in ima_appraise_measurement().  It's not enough to
test whether the policy permits appended signatures (modsig), but to detect
whether CONFIG_MODULE_SIG is enabled.  In addition, similar support to
try_modsig, needs to be added for CONFIG_MODULE_HASHES.

thanks,

Mimi

> 
> Interest has been proclaimed by NixOS, Arch Linux, Proxmox, SUSE and the
> general reproducible builds community.
> 
> To properly test the reproducibility in combination with CONFIG_INFO_BTF
> another patch or pahole v1.29 is needed:
> "[PATCH bpf-next] kbuild, bpf: Enable reproducible BTF generation" [0]
> 
> Questions for current patch:
> * Naming
> * Can the number of built-in modules be retrieved while building
>   kernel/module/hashes.o? This would remove the need for the
>   preallocation step in link-vmlinux.sh.
> * How should this interaction with IMA?
> 
> Further improvements:
> * Use a LSM/IMA Keyring to store and validate hashes
> * Use MODULE_SIG_HASH for configuration
> * UAPI for discovery?
> * Currently has a permanent memory overhead
> 
> [0]
> https://lore.kernel.org/lkml/20241211-pahole-reproducible-v1-1-22feae19bad9@weissschuh.net/
> 
> Signed-off-by: Thomas Weißschuh <linux@weissschuh.net>
> ---
> Changes in v3:
> - Rebase on v6.15-rc1
> - Use openssl to calculate hash
> - Avoid warning if no modules are built
> - Simplify module_integrity_check() a bit
> - Make incompatibility with INSTALL_MOD_STRIP explicit
> - Update docs
> - Add IMA cleanups
> - Link to v2:
> https://lore.kernel.org/r/20250120-module-hashes-v2-0-ba1184e27b7f@weissschuh.net
> 
> Changes in v2:
> - Drop RFC state
> - Mention interested parties in cover letter
> - Expand Kconfig description
> - Add compatibility with CONFIG_MODULE_SIG
> - Parallelize module-hashes.sh
> - Update Documentation/kbuild/reproducible-builds.rst
> - Link to v1:
> https://lore.kernel.org/r/20241225-module-hashes-v1-0-d710ce7a3fd1@weissschuh.net
> 
> ---
> Thomas Weißschuh (9):
>       powerpc/ima: Drop unnecessary check for CONFIG_MODULE_SIG
>       ima: efi: Drop unnecessary check for
> CONFIG_MODULE_SIG/CONFIG_KEXEC_SIG
>       kbuild: add stamp file for vmlinux BTF data
>       kbuild: generate module BTF based on vmlinux.unstripped
>       module: Make module loading policy usable without MODULE_SIG
>       module: Move integrity checks into dedicated function
>       module: Move lockdown check into generic module loader
>       lockdown: Make the relationship to MODULE_SIG a dependency
>       module: Introduce hash-based integrity checking
> 
>  .gitignore                                   |  1 +
>  Documentation/kbuild/reproducible-builds.rst |  5 ++-
>  Makefile                                     |  8 +++-
>  arch/powerpc/kernel/ima_arch.c               |  3 +-
>  include/asm-generic/vmlinux.lds.h            | 11 ++++++
>  include/linux/module.h                       |  8 ++--
>  include/linux/module_hashes.h                | 17 +++++++++
>  kernel/module/Kconfig                        | 21 ++++++++++-
>  kernel/module/Makefile                       |  1 +
>  kernel/module/hashes.c                       | 56
> ++++++++++++++++++++++++++++
>  kernel/module/internal.h                     |  8 +---
>  kernel/module/main.c                         | 51 ++++++++++++++++++++++---
>  kernel/module/signing.c                      | 24 +-----------
>  scripts/Makefile.modfinal                    | 18 ++++++---
>  scripts/Makefile.modinst                     |  4 ++
>  scripts/Makefile.vmlinux                     |  5 +++
>  scripts/link-vmlinux.sh                      | 31 ++++++++++++++-
>  scripts/module-hashes.sh                     | 26 +++++++++++++
>  security/integrity/ima/ima_efi.c             |  6 +--
>  security/lockdown/Kconfig                    |  2 +-
>  20 files changed, 250 insertions(+), 56 deletions(-)
> ---
> base-commit: 0af2f6be1b4281385b618cb86ad946eded089ac8
> change-id: 20241225-module-hashes-7a50a7cc2a30
> 
> Best regards,