Add UOV

[mkannwischer]

https://github.com/mupq/mupq/pull/118 https://github.com/mupq/pqm4/issues/296

This add the UOV implementations from

• https://www.uovsig.org/
• https://github.com/pqov/pqov

The M4 implementation is from

• https://eprint.iacr.org/2023/059
• https://github.com/pqov/pqov-paper

Only ov-Ip fits within 640 KB of RAM:

• ov-Is requires 412160 bytes pk + 348704 bytes sk
• ov-III requires over 2 MB pk + sk
• ov-V requires over 5 MB pk + sk

Note that ov-Is does have an M4 implementation, but it is storing keys in flash which is not supported by mupq/pqm4.

Two comments:

• UOV requires a non-standard API for AES in counter mode (it needs to take the initial counter value as an argument). I don't want to modify the API as it would require changing it in PQClean and probably OQS as well and I am not sure how welcome that would be. For now I have added a local implementation. We still want to benefit from the optimized M4 implementation, so we switch between assembly and the reference implementation depending on a flag defining if it is compiled for the host or the M4. Not very pretty.
• Our current tests have a failure test case where it generates two key pairs, signs with one, and tries to veify with the other which should fail. This reuires to store two public keys on the stack which won't work for schemes with very big public keys (like classic OV). I added the option to switch to a low-RAM variant which instead of generating two key pairs, only generates one and sets the public key to random bytes before verifying. This variant is behind a flag "BIG_PUBLIC_KEY_TESTS" which has to be set to the config.mk of the respective schemes.

[rpls]

Since this also uses the possibly problematic util_prng.c from mupq/mupq#118, I'll way. But otherwise, this seems ok. Maybe worth a general discussion: Should PRs including new schemes also include performance measurements? Right now it's somewhat superfluous, since a lot of schemes will be added and at some point we'll run a large batch of measurements. And for PRs from third parties, we should test ourselves anyway :-)

But otherwise it looks fine, I'll merge this together with the corresponding mupq/mupq#118, once that's through.

[mkannwischer]

You are right. Let's not add benchmarking results for now to keep it easier. Still important to make sure they run sucesssfully (-i 1) to make sure everything is fine.

Do you have any suggestions regarding util_prng.c? I don't really have any ideas that are not just as terrible as what we have now.

[rpls]

Do you have any suggestions regarding util_prng.c? I don't really have any ideas that are not just as terrible as what we have now.

I think more schemes will come at some point, that do sampling/rng with reduced round primitives, or some that make use of calculating multiple (possibly unrelated) blocks. We can't really support them all, so my approach would be the same as you did: Add the PROFILE_HASHING ifdefs where relevant and leave them as is for now. Once we have an overview, we can push for a cleaner solution. Right now I'd say we concentrate on benchmarking.

So for now, just fix the bug I noted in the review in mupq/mupq#118 and I'll merge it.

[mkannwischer]

I rebased everything on top of #304 and included the much cleaner AES128CTR. I think this is ready to be merged now.

I also updated the skiplists with the new stack benchmarks.