Re: Should we automatically generate a module signing key at all?

["George Spelvin" <linux@horizon.com>]

Andy Lutomirski wrote:
> Bonus exercise for the reader: find the security hole in this
> simplified scheme :)  Hint: you can construct a proof of validity for
> a sequence of bytes that isn't a module at all.

Well, does the kernel store the number of levels in the hash tree along
with the hash, or believe the module?

The other practical issue is whether 2x256 bits = 64 bytes of concatenated
hashes can look enough like an ELF header to be loaded.  Or contain
enough payload do anything "interesting".

But that sort of cheap trick is putting the ELF header parsing on the
front lines (i.e. it's now part of the attack surface).  I fully agree
that it's bad crypto design and the crypto should fully validate
the input before passing it on.

>> Andy, an easier indexing scheme might use, instead the depth
>> and index separately, the implicit heap numbering.  The root is
>> node 1, its children are 2 and 3, their children are 4 through 7, etc.

> That could work, too.  I think it kills my xor-1 trick, though.

Not at all; if anything it's inspired by the xor-1 trick.  It works
exactly the same, you just omit the level beccause it's derivable from
i^1, i>>1^1, i>>2^1, etc.

All you're doing is storing (i | 1<<level).  The position of the msbit
gives the level, while the lsbits are unmodified, so the XOR trick is
also unmodified.


> Long-term, I think it would be neat if NIST standardized something
> like the Sakura tree coding system, and we'd just use that.

> (It would be extra neat if they standardized an encoding of Sakura proofs,
> but I'll take a standard and correct hash tree as a very good start.)

It would also take some hacking on the spec to cover hashing separate
messages; Sakura is specified to cover various ways of breaking up a
single message into pieces which are logically concatenated.