Feature: x448 and Ed448 by FAlbertDev · Pull Request #3933 · randombit/botan

FAlbertDev · 2024-03-06T15:21:15Z

This pull request adds support for the x448 key agreement and the ed448 signature scheme as defined in RFC 7748 and RFC 8032. Requested in #3895.

Pull Request Dependencies

Refactor: Final iteration on load/store #3869
Commit: eb243e4 (CI fix of master)

Features

X448 key agreement
Ed448 signature scheme without and with prehashing (Ed448 (default) and Ed448ph). As with Ed25519, the usage of custom contexts (i.e. Ed448ctx) is not supported.
FFI bindings for both algorithms
TLS support for both algorithms
Hybrid key exchange instances x448/eFrodoKEM-976-SHAKE, x448/eFrodoKEM-976-AES, and x448/Kyber-768-r3

Internals

The algorithms used for modular arithmetic in $GF(p)$, where $p = 2^{448} - 2^{224} - 1$, are based on the paper "Reduction Modulo 2^448 - 2^224 - 1" from Nath and Sarkar. These algorithms operate on 64-bit limbs and are implemented in the Gf448Elem class.

In addition, the Ed448 algorithm requires modular arithmetic on the group order of Curve448. To handle this, a Scalar448 class has been implemented, providing the necessary operations modulo the group order (L in RFC 8032).

Both implementations are designed to be constant-time. As the current big integer implementation is not constant-time for all required operations (especially reduction), the Gf448Elem and Scalar448 classes are independent of the big integer implementation and directly utilize the mp_core operations. This design may have future potential for an abstract GfElem class that can be used for other prime fields as well.

The test cases for these implementations are based on wycheproof.

Performance

$ ./botan speed --msec=3000 Curve448 Ed448
Curve448 3157 keygen/sec; 0.32 ms/op 528275 cycles/op (2 ops in 1 ms)
Curve448 3355 keygen/sec; 0.30 ms/op 503325 cycles/op (2 ops in 1 ms)
Curve448 3009 key agreements/sec; 0.33 ms/op 561397 cycles/op (9028 ops in 3000 ms)

Ed448 747 keygen/sec; 1.34 ms/op 2259032 cycles/op (1 op in 1 ms)
Ed448 Pure 1077 sign/sec; 0.93 ms/op 1568058 cycles/op (3233 ops in 3001 ms)
Ed448 Pure 550 verify/sec; 1.82 ms/op 3070291 cycles/op (1652 ops in 3002 ms)

coveralls · 2024-03-06T16:48:26Z

coverage: 92.082% (+0.04%) from 92.045%
when pulling a9a3d8b on Rohde-Schwarz:ec/448
into f03c6a9 on randombit:master.

reneme

First pass. Didn't look at the actual implementation of Ed/X448, yet. Mostly, higher-level API and design nits.

src/build-data/policy/modern.txt

src/lib/ffi/ffi.h

src/lib/ffi/ffi_pkey_algs.cpp

src/lib/pubkey/curve448/curve448_utils/curve448_scalar.cpp

src/python/botan3.py

src/scripts/run_tls_fuzzer.py

src/scripts/test_cli.py

reneme

Some more remarks mostly focussing on the utility classes.

src/lib/pubkey/curve448/curve448_utils/curve448_scalar.cpp

src/lib/pubkey/curve448/curve448_utils/curve448_gf.cpp

reneme · 2024-03-13T13:46:51Z

src/lib/pubkey/curve448/curve448_utils/curve448_gf.h

+ * the value might be larger than the prime modulus. When calling the to_bytes() method, the
+ * canonical representation is returned.
+ */
+class Gf448Elem {


Perhaps its worthwhile defining some commonly used types:

using byte_span = std::span<const uint8_t, to_bytes(448)>; using word_span = std::span<const uint64_t, to_words(448)>; // same for arrays, perhaps

I don't use such aliases because they hide the actual type from the user. Also, I would need one variant with and without const. However, I think using constants for 56 (bytes per 448) and 7 (words per 448) are sensible.

src/lib/pubkey/curve448/curve448_utils/curve448_gf.cpp

reneme

Comments regarding the actual implementation of x448. Looks really concise to me! 😃

src/lib/pubkey/curve448/curve448_internal.h

src/lib/pubkey/curve448/curve448_internal.cpp

src/lib/pubkey/curve448/curve448.cpp

reneme

Comments regarding Ed448.

src/lib/pubkey/ed448/ed448_internal.cpp

src/lib/pubkey/ed448/ed448.cpp

reneme · 2024-03-14T14:23:50Z

Generally, the implementation is well-structured and thought out. 😃 Don't be put off by the number of comments, most address small nits or potential memory inefficiencies. Some minor architectural things.

One thing, I'd really appreciate in general: Let's try to consolidate magic strings and magic numbers. First and foremost, the lengths of key material arrays (both in word length and byte length). But also the hash functions used. Please try to have as little "atomic" constants as possible and calculate dependent values were reasonably possible.

As mentioned before somewhere, sooner or later we should establish a standard interface to be able to access such constants statically from within the library.

FAlbertDev · 2024-03-18T13:18:52Z

Thank you very much for your helpful and detailed review, @reneme. I applied your suggestions and rebased to the current head of #3869.

reneme · 2024-03-18T16:37:10Z

src/lib/pubkey/curve448/curve448_scalar.cpp

+/// @return a word array for c = 0x8335dc163bb124b65129c96fde933d8d723a70aadc873d6d54a7bb0d
+consteval std::array<word, WORDS_C> c_words() {
+   // Currently load_le does not work with constexpr. Therefore, we have to use this workaround.
+   const std::array<uint8_t, WORDS_C * sizeof(word)> c_bytes{0x0d, 0xbb, 0xa7, 0x54, 0x6d, 0x3d, 0x87, 0xdc, 0xaa, 0x70,
+                                                             0x3a, 0x72, 0x8d, 0x3d, 0x93, 0xde, 0x6f, 0xc9, 0x29, 0x51,
+                                                             0xb6, 0x24, 0xb1, 0x3b, 0x16, 0xdc, 0x35, 0x83};
+   return load_le<std::array<word, WORDS_C>>(c_bytes);
+}


In a blunt nerd-sniping attempt: if we would manage to make Botan::hex_decode() constexpr, this could be:

Suggested change

/// @return a word array for c = 0x8335dc163bb124b65129c96fde933d8d723a70aadc873d6d54a7bb0d

consteval std::array<word, WORDS_C> c_words() {

// Currently load_le does not work with constexpr. Therefore, we have to use this workaround.

const std::array<uint8_t, WORDS_C * sizeof(word)> c_bytes{0x0d, 0xbb, 0xa7, 0x54, 0x6d, 0x3d, 0x87, 0xdc, 0xaa, 0x70,

0x3a, 0x72, 0x8d, 0x3d, 0x93, 0xde, 0x6f, 0xc9, 0x29, 0x51,

0xb6, 0x24, 0xb1, 0x3b, 0x16, 0xdc, 0x35, 0x83};

return load_le<std::array<word, WORDS_C>>(c_bytes);

}

consteval std::array<word, WORDS_C> c_words() {

return load_le<std::array<word, WORDS_C>>(Botan::hex_decode(

"0dbba7546d3d87dcaa703a728d3d93de6fc92951b624b13b16dc3583"));

}

... which would be quite fantastic.

src/lib/pubkey/curve448/curve448_scalar.cpp

src/lib/pubkey/curve448/curve448_utils/curve448_scalar.cpp

src/lib/pubkey/ed448/ed448_internal.cpp

src/lib/pubkey/ed448/ed448.h

src/lib/pubkey/ed448/ed448.cpp

FAlbertDev · 2024-03-19T07:33:17Z

Thanks for your re-review, @reneme! However, it seems that you somehow managed to review the files that were moved (i.e., the files in src/lib/pubkey/ed448/). Your last two suggestions are already addressed in my latest commit. I also cannot answer to these suggestions. Weird...

Regarding:

By any chance: Did you compile with the amalgamation?

No, I measured the default static build.

reneme · 2024-03-19T07:41:27Z

However, it seems that you somehow managed to review the files that were moved

Mhm, I replied to discussions that were already open, while having started a pending review. Apparently GitHub treats those comments in a funny way; half reply, half free-standing but unanswerable new threads. >.<

reneme · 2024-03-19T08:09:10Z

Mhh, on Windows the typecast_copy<StrongTypeOfStdArray> doesn't seem to work. :( I'm having a look.

reneme

One little nit, otherwise I'm happy. 👍

src/lib/pubkey/curve448/ed448/ed448_internal.cpp

randombit

Looks very good! Didn’t have time to finish review but here are some initial comments.

src/cli/speed.cpp

src/lib/pubkey/curve448/curve448_scalar.h

src/lib/pubkey/curve448/ed448/ed448_internal.cpp

randombit · 2024-03-19T22:04:22Z

src/lib/pubkey/curve448/ed448/ed448_internal.cpp

+Ed448Point Ed448Point::scalar_mul(const Scalar448& s) const {
+   Ed448Point res(0, 1);
+
+   // Square and multiply (double and add) in constant time.


Lots of room for optimization here if performance becomes an issue.

If you have any optimizations in mind, let me know 👍 Otherwise, I think the performance is currently acceptable.

Just that double-and-always-add is (literally) the worst case scenario for a multiplication algorithm since for scalar length l it performs l doublings and l additions. Easy optimization would be a fixed window with a constant time table lookup, eg a 4 bit window you instead do l doublings and l/4 additions.

Fine to use this if you consider current performance ok.

This sounds promising! I will leave it with the simple variant for now since the PR is already complex enough. Maybe we can speed it up in a follow-up PR.

src/lib/pubkey/curve448/info.txt

src/lib/pubkey/curve448/x448/curve448.cpp

FAlbertDev · 2024-03-20T08:45:15Z

Thanks for your comments, @randombit. Any suggestions are welcome :)
I renamed Curve448 to X448 and applied your other suggestions.

randombit · 2024-03-21T22:06:36Z

@FAlbertDev thanks. This needs a rebase post #3869 and possibly some history cleanup. I'll do a final review after.

FAlbertDev · 2024-03-22T08:10:28Z

This needs a rebase post #3869 and possibly some history cleanup.

Done :)

reneme · 2024-03-22T12:39:24Z

I'm guessing this caused botan3.py to conflict with master. Could you rebase once more, please?

randombit

Looks very good, thanks

FAlbertDev · 2024-03-25T07:32:41Z

Could you rebase once more, please?

Done. Should be ready to merge.

Co-authored-by: René Meusel <rene.meusel@rohde-schwarz.com>

The test can be re-enabled when we support Botan 3 due to: randombit/botan#3933 Signed-off-by: Björn Svensson <bjorn.a.svensson@est.tech>

FAlbertDev requested a review from reneme March 6, 2024 15:21

FAlbertDev force-pushed the ec/448 branch from 28cdd16 to 9e3aa32 Compare March 8, 2024 11:02

reneme requested changes Mar 13, 2024

View reviewed changes

reneme mentioned this pull request Mar 13, 2024

Improve API of asymmetric algorithms #3706

Open

5 tasks

reneme requested changes Mar 13, 2024

View reviewed changes

reneme added this to the Botan 3.4.0 milestone Mar 13, 2024

reneme assigned FAlbertDev Mar 13, 2024

reneme added the enhancement Enhancement or new feature label Mar 13, 2024

reneme linked an issue Mar 13, 2024 that may be closed by this pull request

Support for Ed448 and X448 #3895

Closed

reneme requested changes Mar 14, 2024

View reviewed changes

FAlbertDev force-pushed the ec/448 branch from 9e3aa32 to 5b73e83 Compare March 18, 2024 13:15

reneme reviewed Mar 18, 2024

View reviewed changes

reneme approved these changes Mar 19, 2024

View reviewed changes

src/lib/pubkey/curve448/ed448/ed448_internal.cpp Outdated Show resolved Hide resolved

randombit reviewed Mar 19, 2024

View reviewed changes

FAlbertDev force-pushed the ec/448 branch from 0d59e0b to 5d0e324 Compare March 22, 2024 08:08

randombit approved these changes Mar 23, 2024

View reviewed changes

FAlbertDev added 2 commits March 25, 2024 08:28

Curve448 Utils

cd66c3c

X448 Implementation

4c54efa

FAlbertDev force-pushed the ec/448 branch from 5d0e324 to 13254aa Compare March 25, 2024 07:31

FAlbertDev and others added 2 commits March 25, 2024 08:56

Ed448 Implementation

6ac72f5

x448 and Ed448 Integration

a9a3d8b

Co-authored-by: René Meusel <rene.meusel@rohde-schwarz.com>

FAlbertDev force-pushed the ec/448 branch from 13254aa to a9a3d8b Compare March 25, 2024 07:57

FAlbertDev merged commit 850b267 into randombit:master Mar 25, 2024

FAlbertDev deleted the ec/448 branch March 25, 2024 08:31

TJ-91 mentioned this pull request Mar 26, 2024

Implement X448, Ed448 when available in Botan pqc-thunderbird/rnp#59

Closed

reneme mentioned this pull request Apr 8, 2024

HSS-LMS Signature Algorithm Implementation #3716

Merged

bjosv added a commit to Nordix/SoftHSMv2 that referenced this pull request Nov 29, 2024

Remove testing of unsupported ED448 in Botan 2

5a84dcf

The test can be re-enabled when we support Botan 3 due to: randombit/botan#3933 Signed-off-by: Björn Svensson <bjorn.a.svensson@est.tech>

bjosv added a commit to Nordix/SoftHSMv2 that referenced this pull request Nov 29, 2024

Remove testing of unsupported ED448 in Botan 2

69cea51

The test can be re-enabled when we support Botan 3 due to: randombit/botan#3933 Signed-off-by: Björn Svensson <bjorn.a.svensson@est.tech>

bjosv added a commit to Nordix/SoftHSMv2 that referenced this pull request Nov 29, 2024

Remove testing of unsupported ED448 in Botan 2

9f55044

The test can be re-enabled when we support Botan 3 due to: randombit/botan#3933 Signed-off-by: Björn Svensson <bjorn.a.svensson@est.tech>

bjosv added a commit to Nordix/SoftHSMv2 that referenced this pull request Nov 29, 2024

Remove testing of unsupported ED448 in Botan 2

152cece

The test can be re-enabled when we support Botan 3 due to: randombit/botan#3933 Signed-off-by: Björn Svensson <bjorn.a.svensson@est.tech>

bjosv mentioned this pull request Nov 29, 2024

Fix Botan build and test failures softhsm/SoftHSMv2#771

Merged

Conversation

FAlbertDev commented Mar 6, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Pull Request Dependencies

Features

Internals

Performance

Uh oh!

coveralls commented Mar 6, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

reneme left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

reneme left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

reneme Mar 13, 2024

Choose a reason for hiding this comment

Uh oh!

FAlbertDev Mar 15, 2024

Choose a reason for hiding this comment

Uh oh!

Uh oh!

reneme left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

reneme left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

reneme commented Mar 14, 2024

Uh oh!

FAlbertDev commented Mar 18, 2024

Uh oh!

reneme Mar 18, 2024

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

FAlbertDev commented Mar 6, 2024 •

edited

Loading

coveralls commented Mar 6, 2024 •

edited

Loading

FAlbertDev commented Mar 19, 2024 •

edited

Loading