Add UOV #2094

mkannwischer · 2025-03-05T05:59:35Z

This PR adds the UOV signature scheme which is a second-round candidate in the NIST digital signature competition.
The implementation is sourced from pqov and implements the round 2 specification.

CI (full tests + extended tests) is passing in my fork of liboqs.

This PR includes the reference, AVX2, and Neon implementations for all 12 parameter sets. There are additional 12 parameter sets using 4-round AES128 instead of the default 10 rounds. I have not included those yet - if there is interest in them, I'm happy to add them later.

I had to make a few changes to the implementation to make it through CI and I'm porting them back to the main code base here: pqov/pqov#58.
~~Once that is merged no further patches are required for the implementation. Once that is merged, I will update this PR and mark it as ready for review.~~
The changes have been merged upstream by now.

The import is entirely done via the copy_from_upstream.py script. I have integrated the required META files upstream.

There are two small changes to the liboqs code base:

Allow the pqov_ namespace (377232e)
Do not rely on SPHINCS+ being the last item in an alphabetically ordered list in update_docs_from_yaml.py (3fafba1)

Resolves #2028.

Does this PR change the input/output behaviour of a cryptographic algorithm (i.e., does it change known answer test values)? (If so, a version bump will be required from x.y.z to x.(y+1).0.)
Does this PR change the list of algorithms available -- either adding, removing, or renaming? Does this PR otherwise change an API? (If so, PRs in fully supported downstream projects dependent on these, i.e., oqs-provider will also need to be ready for review and merge by the time this is merged.)

This PR was prepared jointly with @potsrevennil.

Signed-off-by: Matthias J. Kannwischer <[email protected]>

mkannwischer · 2025-03-05T11:26:30Z

The Travis CI found two interesting problems that I have fixed by now:

Was a -Waggressive-loop-optimization warning with gcc 10 or older. gcc11 and later seems to work. I think it is a compiler bug. I refactored the affected code a bit to work around that and funnily that gave quite a speed-up for verification.
There was an endianness assumption in my OQS glue code that's calling AES-CTR. I have fixed that now.

Unless I broke something in the meantime, CI should be all green now.

mkannwischer · 2025-03-05T12:25:20Z

None of the zephyr tests would work for me even for the parameter sets with the smallest memory footprint. I suspect that memory is rather limited in these tests?

zephyr/Kconfig

dstebila · 2025-03-05T19:40:09Z

None of the zephyr tests would work for me even for the parameter sets with the smallest memory footprint. I suspect that memory is rather limited in these tests?

Tagging @Frauschi about the Zephyr question.

bhess

Thank you @mkannwischer for contributing UOV!

One minor thing, we have a config option that builds only the onramp candidates. The UOV variants should be added to this list as well:

liboqs/.CMake/alg_support.cmake

Lines 217 to 219 in d4eb7a6

    
           elseif(${OQS_ALGS_ENABLED} STREQUAL "NIST_SIG_ONRAMP") 
        
           	filter_algs("SIG_mayo_1;SIG_mayo_2;SIG_mayo_3;SIG_mayo_5;SIG_cross_rsdp_128_balanced;SIG_cross_rsdp_128_fast;SIG_cross_rsdp_128_small;SIG_cross_rsdp_192_balanced;SIG_cross_rsdp_192_fast;SIG_cross_rsdp_192_small;SIG_cross_rsdp_256_balanced;SIG_cross_rsdp_256_fast;SIG_cross_rsdp_256_small;SIG_cross_rsdpg_128_balanced;SIG_cross_rsdpg_128_fast;SIG_cross_rsdpg_128_small;SIG_cross_rsdpg_192_balanced;SIG_cross_rsdpg_192_fast;SIG_cross_rsdpg_192_small;SIG_cross_rsdpg_256_balanced;SIG_cross_rsdpg_256_fast;SIG_cross_rsdpg_256_small") 
        
           else()

The zephyr config is limited to 512K stack size

liboqs/zephyr/samples/Signatures/prj.conf

Line 14 in d4eb7a6

CONFIG_MAIN_STACK_SIZE=524288

and 256K malloc size

liboqs/zephyr/samples/Signatures/prj.conf

Line 18 in d4eb7a6

CONFIG_COMMON_LIBC_MALLOC_ARENA_SIZE=262144

I am not certain if these values can be safely increased.

mkannwischer · 2025-03-06T08:55:49Z

Thank you @mkannwischer for contributing UOV!

One minor thing, we have a config option that builds only the onramp candidates. The UOV variants should be added to this list as well:

liboqs/.CMake/alg_support.cmake

Lines 217 to 219 in d4eb7a6

elseif(${OQS_ALGS_ENABLED} STREQUAL "NIST_SIG_ONRAMP")

filter_algs("SIG_mayo_1;SIG_mayo_2;SIG_mayo_3;SIG_mayo_5;SIG_cross_rsdp_128_balanced;SIG_cross_rsdp_128_fast;SIG_cross_rsdp_128_small;SIG_cross_rsdp_192_balanced;SIG_cross_rsdp_192_fast;SIG_cross_rsdp_192_small;SIG_cross_rsdp_256_balanced;SIG_cross_rsdp_256_fast;SIG_cross_rsdp_256_small;SIG_cross_rsdpg_128_balanced;SIG_cross_rsdpg_128_fast;SIG_cross_rsdpg_128_small;SIG_cross_rsdpg_192_balanced;SIG_cross_rsdpg_192_fast;SIG_cross_rsdpg_192_small;SIG_cross_rsdpg_256_balanced;SIG_cross_rsdpg_256_fast;SIG_cross_rsdpg_256_small")

else()

I added UOV there.

The zephyr config is limited to 512K stack size

liboqs/zephyr/samples/Signatures/prj.conf

Line 14 in d4eb7a6

CONFIG_MAIN_STACK_SIZE=524288

and 256K malloc size

liboqs/zephyr/samples/Signatures/prj.conf

Line 18 in d4eb7a6

CONFIG_COMMON_LIBC_MALLOC_ARENA_SIZE=262144

I am not certain if these values can be safely increased.

I think there is no hope that this is going to work with the current implementations.
The smallest parameter set has 278432-byte public keys and 237896-byte. That already 512 KB. You can compress both, but the current implementations still stores the full expanded keys in memory.
We are working on more stack friendly implementations - but those are not yet ready.

Frauschi · 2025-03-06T09:09:14Z

Regarding the Zephyr problems: The CI tests emulate different Zephyr boards via QEMU. Technically, we can increase the stack and heap sizes for these tests to make them run successfully (as in QEMU, available memory is much larger).

However, the current values are already quite large considering the actual hardware Zephyr is intended for (smaller microcontrollers). Hence, I am not sure if this would be a real benefit, as UOV (in its current implementation with the memory usage) would never run on a real microcontroller target anyway (as they typically have available RAM in the kilobyte or small megabyte region). So, maybe we disable UOV for Zephyr completely at the moment? This can be revisited once an implementation with less memory usage is available.

mkannwischer · 2025-03-06T09:34:49Z

Regarding the Zephyr problems: The CI tests emulate different Zephyr boards via QEMU. Technically, we can increase the stack and heap sizes for these tests to make them run successfully (as in QEMU, available memory is much larger).

However, the current values are already quite large considering the actual hardware Zephyr is intended for (smaller microcontrollers). Hence, I am not sure if this would be a real benefit, as UOV (in its current implementation with the memory usage) would never run on a real microcontroller target anyway (as they typically have available RAM in the kilobyte or small megabyte region). So, maybe we disable UOV for Zephyr completely at the moment? This can be revisited once an implementation with less memory usage is available.

Thanks!
Makes sense to me. That is what is currently implemented, too.

docs/algorithms/sig/uov.md

Signed-off-by: Matthias J. Kannwischer <[email protected]>

Signed-off-by: Douglas Stebila <[email protected]>

Signed-off-by: Matthias J. Kannwischer <[email protected]>

bhess

LGTM

dstebila · 2025-03-07T18:42:25Z

We have two approving merges so I think we can go ahead and merge this. However there is a merge conflict in cbom.json; I don't know enough about the CBOM file to know how to resolve this. Can anyone help?

bhess · 2025-03-07T18:50:05Z

We have two approving merges so I think we can go ahead and merge this. However there is a merge conflict in cbom.json; I don't know enough about the CBOM file to know how to resolve this. Can anyone help?

I'll have a look at the CBOM merge conflict and try to resolve it.

Signed-off-by: Basil Hess <[email protected]>

bhess · 2025-03-07T22:47:55Z

We have two approving merges so I think we can go ahead and merge this. However there is a merge conflict in cbom.json; I don't know enough about the CBOM file to know how to resolve this. Can anyone help?

I'll have a look at the CBOM merge conflict and try to resolve it.

Resolved.

mkannwischer added 2 commits March 5, 2025 14:00

update_docs_from_yaml.py: Do not rely on SPHINCS being last

3fafba1

Signed-off-by: Matthias J. Kannwischer <[email protected]>

allow pqov namespace

377232e

Signed-off-by: Matthias J. Kannwischer <[email protected]>

mkannwischer force-pushed the uov branch 4 times, most recently from f4c00e3 to f7ed2ad Compare March 5, 2025 11:21

mkannwischer marked this pull request as ready for review March 5, 2025 12:22

mkannwischer requested review from baentsch, bhess, alexrow, praveksharma and dstebila as code owners March 5, 2025 12:22

dstebila reviewed Mar 5, 2025

View reviewed changes

zephyr/Kconfig Outdated Show resolved Hide resolved

dstebila approved these changes Mar 5, 2025

View reviewed changes

dstebila added this to the 0.13.0 milestone Mar 5, 2025

bhess reviewed Mar 6, 2025

View reviewed changes

baentsch reviewed Mar 6, 2025

View reviewed changes

docs/algorithms/sig/uov.md Outdated Show resolved Hide resolved

potsrevennil and others added 3 commits March 6, 2025 18:52

add uov implementations [full tests] [extended tests]

4447954

Signed-off-by: Matthias J. Kannwischer <[email protected]>

Typo [skip ci]

fd33c4a

Signed-off-by: Douglas Stebila <[email protected]>

add UOV to NIST_SIG_ONRAMP

56aa83c

Signed-off-by: Matthias J. Kannwischer <[email protected]>

mkannwischer force-pushed the uov branch from 613abe6 to 56aa83c Compare March 6, 2025 10:52

bhess approved these changes Mar 6, 2025

View reviewed changes

Merge branch 'main' into uov

73a1548

Signed-off-by: Basil Hess <[email protected]>

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Add UOV #2094

Add UOV #2094

mkannwischer commented Mar 5, 2025 •

edited

Loading

mkannwischer commented Mar 5, 2025

mkannwischer commented Mar 5, 2025

dstebila commented Mar 5, 2025

bhess left a comment

mkannwischer commented Mar 6, 2025

Frauschi commented Mar 6, 2025

mkannwischer commented Mar 6, 2025

bhess left a comment

dstebila commented Mar 7, 2025

bhess commented Mar 7, 2025

bhess commented Mar 7, 2025

	elseif(${OQS_ALGS_ENABLED} STREQUAL "NIST_SIG_ONRAMP")
	filter_algs("SIG_mayo_1;SIG_mayo_2;SIG_mayo_3;SIG_mayo_5;SIG_cross_rsdp_128_balanced;SIG_cross_rsdp_128_fast;SIG_cross_rsdp_128_small;SIG_cross_rsdp_192_balanced;SIG_cross_rsdp_192_fast;SIG_cross_rsdp_192_small;SIG_cross_rsdp_256_balanced;SIG_cross_rsdp_256_fast;SIG_cross_rsdp_256_small;SIG_cross_rsdpg_128_balanced;SIG_cross_rsdpg_128_fast;SIG_cross_rsdpg_128_small;SIG_cross_rsdpg_192_balanced;SIG_cross_rsdpg_192_fast;SIG_cross_rsdpg_192_small;SIG_cross_rsdpg_256_balanced;SIG_cross_rsdpg_256_fast;SIG_cross_rsdpg_256_small")
	else()

Add UOV #2094

Are you sure you want to change the base?

Add UOV #2094

Conversation

mkannwischer commented Mar 5, 2025 • edited Loading

mkannwischer commented Mar 5, 2025

mkannwischer commented Mar 5, 2025

dstebila commented Mar 5, 2025

bhess left a comment

Choose a reason for hiding this comment

mkannwischer commented Mar 6, 2025

Frauschi commented Mar 6, 2025

mkannwischer commented Mar 6, 2025

bhess left a comment

Choose a reason for hiding this comment

dstebila commented Mar 7, 2025

bhess commented Mar 7, 2025

bhess commented Mar 7, 2025

mkannwischer commented Mar 5, 2025 •

edited

Loading