Implement generic signature Traits

[jhbruhn]

To be able to write programs which can use different kinds of signature algorithms, there is the signature crate in the RustCrypto ecosystem.

I would be nice if this crates structs could implement the Signer, Verifier and Signature traits to be able to easily use it in said programs. I know too little about LMS to judge it, but maybe the Signature trait can be left out if it does not fit the implementation here.

As an example, we are currently developing a bare-metal bootloader which checks signatures and would like to be able to use this library, but leave the option to replace it with another algorithm easily.

[hieronymusma]

Unfortunately, that's not possible yet. I already tried to implement them but they're not compatible with our implementation.

The reason is the following: To prevent unnecessary bytes copying at signature verification, our signature struct keeps a reference to the original data instead of copying it. But the Signature::from_bytes method expects that the data is copied, otherwise we would have a lifetime violation.

We are already in contact with the Rust Crypto group, to solve this issue. However, I cannot give you a concrete time horizont when this issue will be solved.

[jhbruhn]

I see, and providing a second type only for serialization/conversion that can be convert from/to is not an option? As long as the signature size is deterministic (is it?), this should work.
To quote from Signature:

For signature systems which require a more advanced internal representation (e.g. involving decoded scalars or decompressed elliptic curve points) it’s recommended that “provider” libraries maintain their own internal signature type and use From bounds to provide automatic conversions.

[hieronymusma]

Unfortunately, the signatures are not deterministic in size. They are dependent on the used parameters (winternitz parameter and tree height).
What's possible would be to create a wrapper struct that can contain the largest possible signature via a pre-allocated array (which is around 75kb -> can be found in constants.rs:MAX_HSS_SIGNATURE_LENGTH). This wrapper struct can then be used to implement the traits.

But I'm not sure if that's useful at the moment, as we already plan to implement the traits in the future. So I'm afraid, but if you need the traits, you have to implement them yourself.

[jhbruhn]

Just a suggestion, this was not yet fully planned out: It might make sense to introduce a marker trait for the tree height and winternitz parameter (assuming they are a limited set of values) and adding those to these signature type:

trait WinternitzParameter {}
struct W1;
struct W2;
impl WinternitzParameter for W1 {}
impl WinternitzParameter for W2 {}
// etc.

Those can then be added to the signature type:

struct Signature<W: WinternitzParameter, TH: TreeHeight> {
  // ...
}

Those markers can then be used for a conversion to a signature type or array with a specific length (I think).

This also allows further optimizations for code size and/or efficiency if (and only if) only one set of parameters is used in a system.

[hieronymusma]

I totally forgot about a third parameter: We can have up to 8 HSS Levels, where each level can have a different Winternitz parameter and tree height. I'm wondering if we can still solve that with marker traits...

[jhbruhn]

AFAIK not without introducing generic types for each level and thus having a type with 16 generic type parameters. This could potentially be made ergonomic by using macros which generate the definitions for those types.

[hieronymusma]

That sounds like a nice solution. I like it.

Unfortunately, I don't have much time right now... I can only work on it in my spare time. But I will let you know, when I start working on it.

[aewag]

FYI, I have started the implementation. the current state works, but I need to clean it up a bit more.

It is implemented a bit differently using environment variables as it seemed a bit simpler and as well allows to optimize the lower layers of the library without requiring bigger changes.

If you want to test it with your firmware, I could release a new alpha version with the traits implementation.

[aewag]

FYI: A good documentation about the possiblities using the available environment variables is still lacking, but I just started #5.