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:

quoted

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