Compile secp256 in U-boot

tmagik commented at 4:48 pm on March 26, 2019: none

This pull request is more for discussion, and get some commentary on the value of having device firmware (such as u-boot) that can verify DSA signatures of kernel and userspace payloads.

Things that I need are some help with the simplest example code to check DSA signatures, and any pointers to any other smaller embedded DSA signature codes, or some discussion on whether adapting secp256k to this application is even a good idea.

In particular, maybe @laanwj might find this interesting for a riscv-laptop

Adds about ~36k or so (big for a bootloader)

Also needs the following in u-boot:

diff –git a/lib/Kconfig b/lib/Kconfig index 622f3c26c33..38c2f6493a1 100644 — a/lib/Kconfig +++ b/lib/Kconfig @@ -175,2 +175,3 @@ config AES source lib/rsa/Kconfig +source lib/secp256k1/Kconfig

diff –git a/lib/Makefile b/lib/Makefile index 5f583aed37d..02ec35e8201 100644 — a/lib/Makefile +++ b/lib/Makefile @@ -51,2 +51,3 @@ endif obj-$(CONFIG_RSA) += rsa/ +obj-$(CONFIG_DSA) += secp256k1/ obj-$(CONFIG_SHA1) += sha1.o

Compile secp256 in U-boot

Adds about ~36k or so (big for a bootloader)

diff --git a/lib/Kconfig b/lib/Kconfig
index 622f3c26c33..38c2f6493a1 100644
--- a/lib/Kconfig
+++ b/lib/Kconfig
@@ -175,2 +175,3 @@ config AES
 source lib/rsa/Kconfig
+source lib/secp256k1/Kconfig

diff --git a/lib/Makefile b/lib/Makefile
index 5f583aed37d..02ec35e8201 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -51,2 +51,3 @@ endif
 obj-$(CONFIG_RSA) += rsa/
+obj-$(CONFIG_DSA) += secp256k1/
 obj-$(CONFIG_SHA1) += sha1.o

8186725c7d

laanwj commented at 8:25 am on May 7, 2019: member

Sorry, I didn’t see this PR before. This is very interesting!

For reducing the code size, it would make sense to include only the verification parts, not signing, which would not be necessary. I don’t think there is currently a define for this.

Also you’re using the basic configuration,

0#define USE_FIELD_10X26 1
1#define USE_SCALAR_8X32 1

For RV64 you can use the 64-bit code for the field and scalar operations, which have fewer steps thus shorter (and faster):

0USE_SCALAR_4X64
1USE_FIELD_5X52

Note that secp256k1 precomputes a large table in the context at initialization (in secp256k1_ecmult_context_build, for faster verification). With the default settings this is about 1.25MB:

0/** One table for window size 16: 1.375 MiB. */
1#define WINDOW_G 16
2
3… scales exponentially: …
4#define ECMULT_TABLE_SIZE(w) (1 << ((w)-2))

For bootloader use, you’d want to a) reduce the size of the table and b) embed the table statically (which unfortunately increases the code size). It can be set arbitrarily small. I don’t know what is the smallest table size that still leads to acceptable verification performance for your use case. There’s a PR that makes the window configurable and has some benchmarks: #596. There hasn’t been work yet on embedding the table statically AFAIK.

gmaxwell commented at 8:35 am on May 7, 2019: contributor

Signing uses a static table, its more or less trivial to do. (usually people who have wanted to use the library in embedded contexts have wanted signing, not verification… :) ). There are also a whole bunch of easy size optimizations where we have several different versions of a function optimized for different cases which could all be substituted by the most general.

Re leaving out signing, the linker should strip the signing parts if they’re not used.

laanwj commented at 9:25 am on May 7, 2019: member

I liked the idea (also by @gmaxwell) to hardcode the table the for a few small WINDOW_G sizes. It’d not make much sense for the general case anyhow (virtually no one wants 1.5MB larger binary at the expense of a little bit less startup time), and avoids needing scripts to generate code during build.

Re leaving out signing, the linker should strip the signing parts if they’re not used.

Are you sure? Unless using full program optimization, or -ffunction-sections, or a compilation unit per function (which is not the case, everything ends up in libsecp256k1_la-secp256k1.o), I don’t think the linker is allowed to remove code.

laanwj commented at 7:21 pm on May 7, 2019: member

I was curious so I created a list of function/data objects and their sizes—on RV64—that are used from secp256k1_context_create (verify only) and secp256k1_ecdsa_verify. This was done using -Os -ffunction-sections -fdata-sections -Wl,--gc-sections:

 012    .text    secp256k1_callback_call
 1858   .text    secp256k1_fe_mul_inner
 2652   .text    secp256k1_fe_sqr_inner
 3188   .text    secp256k1_fe_normalize
 494    .text    secp256k1_fe_normalize_weak
 5186   .text    secp256k1_fe_normalize_var
 6146   .text    secp256k1_fe_normalizes_to_zero_var
 722    .text    secp256k1_fe_clear
 8352   .text    secp256k1_fe_set_b32
 966    .text    secp256k1_fe_negate
1042    .text    secp256k1_fe_mul_int
1142    .text    secp256k1_fe_add
1248    .text    secp256k1_fe_to_storage
1366    .text    secp256k1_fe_from_storage
14558   .text    secp256k1_fe_inv
1586    .text    secp256k1_scalar_check_overflow
1688    .text    secp256k1_scalar_reduce
17288   .text    secp256k1_scalar_set_b32
18250   .text    secp256k1_scalar_get_b32
1920    .text    secp256k1_scalar_is_zero
20150   .text    secp256k1_scalar_negate
21100   .text    secp256k1_scalar_is_high
22590   .text    secp256k1_scalar_reduce_512
23434   .text    secp256k1_scalar_mul
24454   .text    secp256k1_scalar_sqr
25952   .text    secp256k1_scalar_inverse
2670    .text    secp256k1_ge_set_gej_zinv
2770    .text    secp256k1_gej_set_ge
2876    .text    secp256k1_ge_to_storage
2942    .text    secp256k1_ge_from_storage
3026    .text    default_error_callback_fn
3126    .text    default_illegal_callback_fn
3246    .text    checked_malloc
3382    .text    secp256k1_pubkey_load
34280   .text    secp256k1_gej_double_var
35436   .text    secp256k1_gej_add_ge_var
3644    .text    secp256k1_ecdsa_signature_load.isra.0
37270   .text    secp256k1_ecmult_wnaf.constprop.0
38186   .text    secp256k1_ecmult_odd_multiples_table.constprop.0
391502  .text    secp256k1_ecmult
4080    .text    secp256k1_gej_eq_x_var
4116    .rodata  default_error_callback
4240    .rodata  secp256k1_ecdsa_const_order_as_fe
4340    .rodata  secp256k1_ecdsa_const_p_minus_order
4488    .rodata  secp256k1_ge_const_g
45496   .text    secp256k1_context_create
46324   .text    secp256k1_ecdsa_verify
47
4810984 (total)

This can be considered a lower bound on the size added to the bootloader for verification only. Of course, any hardcoded precomputed WINDOW_G table size will need to be added to this.

gmaxwell cross-referenced this on May 10, 2019 from issue Use a static constant table for small ecmult WINDOW_G sizes. by gmaxwell

gmaxwell commented at 11:19 pm on May 11, 2019: contributor

we should be able to get a 3.8% size reduction with negligible impact in performance by having something to use the strongest normalize function for all normalize uses…. but I dunno if it’s worth having a define to shrink the code if that’s all that it does.

Some of the larger functions like scalar inverse and fe_inverse could probably be shrank a whole lot with a small performance hit by un-unrolling them by adding a small state machine.

I notice the sqrt isn’t in your list, this is because you don’t have a pubkey load. The sqrt is only needed if a compressed pubkey is used. For a bootloader, you’d be best off using an uncompressed pubkey, then the code doesn’t need the big and somewhat slow sqrt function.

sipa commented at 7:12 pm on July 23, 2019: contributor

What are the next steps here? The patch as-is isn’t acceptable as it introduces Linux-specific includes in the source code, as well as adding a static Makefile that would be confusing to other builders. Those things should, if necessary, at least move to some contrib directory or perhaps even a separate repository.

However, there are perhaps things that can be done to the codebase itself to help its use in this setting? Maybe a way to configure while dropping things that aren’t relevant to verification? Since #596 the WINDOW_G size is configurable to reduce the size of the static table.

sipa closed this on May 8, 2023

Compile secp256 in U-boot #603