nettle-bugs January 2022

nettle-bugs@lists.lysator.liu.se

4 participants
10 discussions

Add RSA-OAEP encryption/decryption to Nettle
by Nicolas Mora 09 Mar '24

09 Mar '24

Hello, I've made a new Merge Request in the nettle gitlab repo to provide RSA-OAEP encryption and decryption: https://git.lysator.liu.se/nettle/nettle/-/merge_requests/20 It adds 2 new functions: int pkcs1_oaep_encrypt (size_t key_size, void *random_ctx, nettle_random_func *random, size_t hlen, size_t label_length, const uint8_t *label, size_t message_length, const uint8_t *message, mpz_t m); int pkcs1_oaep_decrypt (size_t key_size, const mpz_t m, size_t hlen, size_t label_length, const uint8_t *label, size_t *length, uint8_t *message); The parameter hlen is the output length of the SHA function used for masking data: - SHA1_DIGEST_SIZE - SHA256_DIGEST_SIZE - SHA384_DIGEST_SIZE - SHA512_DIGEST_SIZE Is it possible to get feedback for this MR and eventually push it to the master branch? Thanks in advance /Nicolas

4 21

[PATCH 0/7] Introduce SM4 symmetric cipher algorithm
by Tianjia Zhang 21 Feb '22

21 Feb '22

SM4 is a block cipher standard published by the government of the People's Republic of China, and it was issued by the State Cryptography Administration on March 21, 2012. The standard is GM/T 0002-2012 "SM4 block cipher algorithm". SM4 algorithm is a symmetric cipher algorithm in ShangMi cryptosystems. The block length and key length are both 128 bits. Both the encryption algorithm and the key derivation algorithm use 32 rounds of non-linear iterative structure, and the S box is a fixed 8 bits. The RFC 8998 specification defines the usage of ShangMi algorithm suite in TLS 1.3, etc. According to the State Cryptography Administration of China, its security and efficiency are equivalent to AES-128. Reference specification: 1. http://www.gmbz.org.cn/upload/2018-04-04/1522788048733065051.pdf 2. http://gmbz.org.cn/main/viewfile/20180108015408199368.html 3. https://tools.ietf.org/id/draft-ribose-cfrg-sm4-10.html 4. https://datatracker.ietf.org/doc/html/rfc8998 Tianjia Zhang (7): doc: Add Copyright of SM3 hash algorithm Introduce SM4 symmetric cipher algorithm testsuite: add test for SM4 symmetric algorithm nettle-benchmark: bench SM4 symmetric algorithm doc: documentation for SM4 cipher algorithm gcm: Add SM4 as the GCM underlying cipher doc: documentation for GCM using SM4 cipher Makefile.in | 2 + examples/nettle-benchmark.c | 2 + gcm-sm4-meta.c | 60 ++++++++++ gcm-sm4.c | 81 +++++++++++++ gcm.h | 25 +++- nettle-meta-aeads.c | 1 + nettle-meta-ciphers.c | 1 + nettle-meta.h | 3 + nettle.texinfo | 81 +++++++++++++ sm4-meta.c | 49 ++++++++ sm4.c | 225 +++++++++++++++++++++++++++++++++++ sm4.h | 71 +++++++++++ testsuite/.gitignore | 1 + testsuite/Makefile.in | 2 +- testsuite/gcm-test.c | 18 +++ testsuite/meta-aead-test.c | 1 + testsuite/meta-cipher-test.c | 3 +- testsuite/sm4-test.c | 19 +++ 18 files changed, 642 insertions(+), 3 deletions(-) create mode 100644 gcm-sm4-meta.c create mode 100644 gcm-sm4.c create mode 100644 sm4-meta.c create mode 100644 sm4.c create mode 100644 sm4.h create mode 100644 testsuite/sm4-test.c -- 2.32.0

2 9

Feature request: OCB mode
by Justus Winter 16 Feb '22

16 Feb '22

Hello, we (Sequoia PGP) would love to see OCB being implemented in Nettle. The OpenPGP working group is working on a revision of RFC4880, which will mostly be a cryptographic refresh, and will bring AEAD to OpenPGP. The previous -now abandoned- draft called for EAX being mandatory, and OCB being optional [0]. This was motivated by OCB being encumbered by patents. However, said patents were waived by the holder [1]. 0: https://datatracker.ietf.org/doc/html/draft-ietf-openpgp-rfc4880bis-10#sect… 1: https://mailarchive.ietf.org/arch/msg/cfrg/qLTveWOdTJcLn4HP3ev-vrj05Vg/ With OCB being no longer patent-encumbered, it seems preferable over the two-pass EAX construction. Therefore, it seems plausible that the WG makes OCB mandatory to implement. To support that in Sequoia, we'd need support for that in Nettle (Nettle is our main cryptographic backend). Unfortunately, we don't have the expertise in our team to contribute a patch, and we currently aren't in a position to offer funding for the implementation. Thanks, Justus

2 5

Latency in polynomial evaluation
by nisse＠lysator.liu.se 07 Feb '22

07 Feb '22

Hi, I've been thinking a bit more on the structure of polynomial evaluation, which at a high level is rather similar for ghash and gcm. ** Intro ** The function to be computed is R_j = K (R_{j-1} + M_j) where K is the secret key and M_j are the message blocks. Operations take place in some finite field. With n message blocks, M_0, ..., M_{n-1}, and initial R_{-1} = 0, we get R_{n-1} = m_{n-1} K + m_{n-2} K^2 + ... m_0 K^n I.e., a degree n polynomial with coefficients M_j, constant term = 0, evaluated at the point K. To be concrete, consider a 64-bit architecture, and a finite field where elements are represented as two words (for poly1305, we need two words plus a few extra bits, but ignore that now, for simplicity. And for ghash, let's also ignore the complications from bit-reversal). Let B represent the bignum base. I'm going to make this a bit handwavy, but we'll have B = 2^64 or B = x^64 depending on type of field. The finite field is represented by a mod P operation, where the structure of P is nice, with a leading one bit followed by more than 64 zeros, and then a few more non-zero bits at the end. This implies that we can define a multiply operation Y_2 B^2 + Y_1 B + Y_0 = (X_1 B + X_0) (K_1 B + K_0) (mod P) by four independent independent multiplication instructions (widening, 64x64 --> 128) involving X and some precomputed values depending on K, and accumulation only involving shifts/adds that have low latency. The result is not fully reduced mod P; it consists of three words. We can then reduce this to two words by multiplying Y_2 by a suitable single-word constant, with final two-word result R = C Y_2 + Y_1 B + Y_0 Applying this to the original recurrency, R_j = K (R_{j-1} + M_j), the X input corresponds to R_{j-1} + M_j, so the critical dependency path from R_{j-1} to R_j includes *two* multiply latencies. E.g, if multiply latency is 5 cycles, it's not possible to get this evaluation scheme to run faster than 10 cycles per block. (In practice, the accumulation will also contribute one or a few cycles to the critical path, but *much* less than those two multiplies). So question is, how can we do better? ** Postponing reduction ** The approach taken in the new x86_64 poly1305 code I just pushed is to skip the final reduction, and let the state be one word larger (and this is particularly cheap for poly1305, because we don't quite increase state size by a word, but from two words + 3 bits to two words plus ~60 bits). The multiply operation becomes Y_2 B^2 + Y_1 B + Y_0 = (X_2 B^2 + X_1 B + X_0) (K_1 B + K_0) (mod P) This can be arranged with 6 independent multiply instructions + cheap accumulation. (I haven't worked out the details for the ghash case, but I do expect that it's rather practival there too). Then the dependency chain from one block to the next is reduced to one multiply latency, 5 cycles in our example. In case all other needed instructions can be scheduled (manually, or by the processor's out-of-order machinery) to run in 5 cycles in parallel with the multiplies, we would get a running time of 5 cycles per block. ** Interleaving ** The other approach, used in the recent powerpc gcm code, is to interleave multiple blocks. For simplicity, only consider 2-way interleaving here. The key thing is that if we expand te recurrency once, we get R_j = K (M_j + K (R_{j-2} + M_{j-1})) = K M_j + K^2 (R_{j-2} + M_{j-1}) We get two field multiplications, but one of them, K M_j, is completely independent of previous blocks (R_{j-2}), and can be computed in parallel. It may add a cycle or so to accumulation latency, but we can do essentially twice as much work without making the critical path longer. We get 8 independent multiply instructions, and one dependent for the final folding. Can be extended to more than two blocks if needed (depending on number of available registers). Another variant could be to separate even and odd parts of the polynomial being evaluated, and evaluate both parts at K^2. We can then compute the two recurrencies E_j = K^2 (E_{j-1} + M_{2j}) O_j = K^2 (O_{j-1} + M_{2j+1}) in parallel. It's unclear to me what the pros and cons are compared to previous variant. One may get some advantage from both multiplies using the same factor K^2. On the other hand, each recurrency has to be accumulated and folded separately, which costs instructions and registers. Maybe more useful for hardware implementation? This variant is currently not used in Nettle. ** Doing both ** It's possible to combine those two tricks. Processing of two blocks would then be an operation of the form Z_2 B^2 + Z_1 B + Z_0 = (X_2 B^2 + X_1 B + X_0) K^2 + (Y_1 B + Y_0) K Here, the Xs (three words) represent R_{j-2} + M_{j-1}, the Ys repreent M_{j-2}, and the Zs represents R_j, as three words (without final folding). We would need 10 independent multiples, one more than with plain interleaving, but critical path includes only one multiply latency. I think this is a promising alternative, if one would otherwise need to interleaving a large number of blocks to get full utilization of the multipliers. ** How to choose ** When implementing one of those schemes, different processor resources may be the bottleneck. I'd expect it to be one of o Multiply latency, i.e, latency of the dependency chain from one block to the next (including also a few additions, but multiply latency willb e the main part). If this is the bottleneck, it means all other instructions can be scheduled in parallel, and the processor will sit idle for some cycles, waiting for a multiply to complete. Typical latency for multiply is 5 times longer than for an addition (but ratio difers quite a bit between processors, of course) o Multiply throughput, i.e., the maximum number of (independent) multiply instructions that can be run per cycle. Typical number is 0.5 -- 2. If this is the bottleneck, the processor will spend some cycles idle, waiting for a multiplier to be ready to accept a new input. o A superscalar processor can issue several instructinos in the same cycle, but there's a fix small limit. Typical number is 2 -- 6. So, e.g., if the processor can issue maximum 4 instructions per cycle, the evaluation loop consists of 40 instructions, and the loop actually runs in close to 10 cycles per iteration, then instruction issue is the bottleneck. The tricks discussed in this note are useful for finding an evaluation scheme where multiply latency isn't a bottleneck. But once a loop hits the limit on multiply throughput or instructions per cycle, other tricks are needed to optimize further. In particular, the postponed reduction has a cost in multiply throughput, since it needs some additional multiply instruction. I think one should aim to hit the limit on multiply throughput; that one is hard to negotiate (it's possible to reduce the number of multiply instructions somewhat, by the Karatsuba trick, but due to the additional overhead, likely to be useful only on processors with particularly low multiply throughput). Regards, /Niels -- Niels Möller. PGP key CB4962D070D77D7FCB8BA36271D8F1FF368C6677. Internet email is subject to wholesale government surveillance.

2 3

[Arm64, PowerPC64, S390x] Optimize Poly1305
by Maamoun TK 28 Jan '22

28 Jan '22

I created merge requests that have improvements of Poly1305 for arm64, powerpc64, and s390x architectures by following using two-way interleaving. https://git.lysator.liu.se/nettle/nettle/-/merge_requests/38 https://git.lysator.liu.se/nettle/nettle/-/merge_requests/39 https://git.lysator.liu.se/nettle/nettle/-/merge_requests/41 The patches have 41.88% speedup for arm64, 142.95% speedup for powerpc64, and 382.65% speedup for s390x. OpenSSL is still ahead in terms of performance speed since it uses 4-way interleaving or maybe more!! Increasing the interleaving ways more than two has nothing to do with parallelism since the execution units are already saturated by using 2-ways for the three architectures. The reason behind the performance improvement is the number of execution times of reduction procedure is cutted by half for 4-way interleaving since the products of multiplying state parts by key can be combined before the reduction phase. Let me know if you are interested in doing that on nettle! It would be nice if the arm64 patch will be tested on big-endian mode since I don't have access to any big-endian variant for testing. regards, Mamone

3 15

[PATCH v2 0/6] Add powerpc64 assembly for elliptic curves
by Amitay Isaacs 24 Jan '22

24 Jan '22

Hi, This series of patches add the powerpc64 assembly for modp/redc functions for elliptic curves P192, P224, P256, P384, P521, X25519 and X448. It results in 15-30% performance improvements as measured on POWER9 system using hogweed-benchmark. I posted the modified codes in the earlier email thread, but I think posting them as a seperate series will make them easier to cherry pick. V2 changes: - Use actual register names when storing/restoring from stack - Drop m4 definitions which are not in use - Simplify C2 folding for P192 curve Amitay Isaacs (2): ecc: Add powerpc64 assembly for ecc_192_modp ecc: Add powerpc64 assembly for ecc_224_modp Martin Schwenke (4): ecc: Add powerpc64 assembly for ecc_384_modp ecc: Add powerpc64 assembly for ecc_521_modp ecc: Add powerpc64 assembly for ecc_25519_modp ecc: Add powerpc64 assembly for ecc_448_modp powerpc64/ecc-curve25519-modp.asm | 101 +++++++++++++ powerpc64/ecc-curve448-modp.asm | 174 +++++++++++++++++++++++ powerpc64/ecc-secp192r1-modp.asm | 87 ++++++++++++ powerpc64/ecc-secp224r1-modp.asm | 123 ++++++++++++++++ powerpc64/ecc-secp384r1-modp.asm | 227 ++++++++++++++++++++++++++++++ powerpc64/ecc-secp521r1-modp.asm | 166 ++++++++++++++++++++++ 6 files changed, 878 insertions(+) create mode 100644 powerpc64/ecc-curve25519-modp.asm create mode 100644 powerpc64/ecc-curve448-modp.asm create mode 100644 powerpc64/ecc-secp192r1-modp.asm create mode 100644 powerpc64/ecc-secp224r1-modp.asm create mode 100644 powerpc64/ecc-secp384r1-modp.asm create mode 100644 powerpc64/ecc-secp521r1-modp.asm -- 2.34.1

2 8

[PATCH 0/7] Add powerpc64 assembly for elliptic curves
by Amitay Isaacs 20 Jan '22

20 Jan '22

Hi, This series of patches add the powerpc64 assembly for modp/redc functions for elliptic curves P192, P224, P256, P384, P521, X25519 and X448. It results in 15-30% performance improvements as measured on POWER9 system using hogweed-benchmark. master ------ name size sign/ms verify/ms ecdsa 192 13.5465 3.8313 ecdsa 224 8.4079 2.5289 ecdsa 256 8.5772 2.4691 ecdsa 384 3.4361 0.9765 ecdsa 521 2.2918 0.6785 eddsa 255 15.0672 4.1138 eddsa 448 4.7115 1.3067 curve 255 15.5206 6.4745 curve 448 4.7906 2.0458 this series ----------- name size sign/ms verify/ms ecdsa 192 17.5450 5.6564 ecdsa 224 10.8847 3.7482 ecdsa 256 11.0208 3.5215 ecdsa 384 5.1133 1.6133 ecdsa 521 2.8815 0.9348 eddsa 255 17.4936 4.9027 eddsa 448 6.0401 1.7075 curve 255 18.1034 7.6884 curve 448 6.1756 2.7095 Amitay Isaacs (3): ecc: Add powerpc64 assembly for ecc_192_modp ecc: Add powerpc64 assembly for ecc_224_modp ecc: Add powerpc64 assembly for ecc_256_redc Martin Schwenke (4): ecc: Add powerpc64 assembly for ecc_384_modp ecc: Add powerpc64 assembly for ecc_521_modp ecc: Add powerpc64 assembly for ecc_25519_modp ecc: Add powerpc64 assembly for ecc_448_modp powerpc64/ecc-curve25519-modp.asm | 103 ++++++++++++++ powerpc64/ecc-curve448-modp.asm | 174 +++++++++++++++++++++++ powerpc64/ecc-secp192r1-modp.asm | 93 ++++++++++++ powerpc64/ecc-secp224r1-modp.asm | 123 ++++++++++++++++ powerpc64/ecc-secp256r1-redc.asm | 144 +++++++++++++++++++ powerpc64/ecc-secp384r1-modp.asm | 227 ++++++++++++++++++++++++++++++ powerpc64/ecc-secp521r1-modp.asm | 166 ++++++++++++++++++++++ 7 files changed, 1030 insertions(+) create mode 100644 powerpc64/ecc-curve25519-modp.asm create mode 100644 powerpc64/ecc-curve448-modp.asm create mode 100644 powerpc64/ecc-secp192r1-modp.asm create mode 100644 powerpc64/ecc-secp224r1-modp.asm create mode 100644 powerpc64/ecc-secp256r1-redc.asm create mode 100644 powerpc64/ecc-secp384r1-modp.asm create mode 100644 powerpc64/ecc-secp521r1-modp.asm -- 2.33.1

2 26

[Arm64, S390x] Optimize Chacha20
by Maamoun TK 20 Jan '22

20 Jan '22

I created merge requests that have improvements of Chacha20 for arm64 and s390x architectures by following the approach used in powerpc implementation. https://git.lysator.liu.se/nettle/nettle/-/merge_requests/37 https://git.lysator.liu.se/nettle/nettle/-/merge_requests/40 The patches have 80.85% speedup for arm64 arch and 284.79% speedup for s390x arch. It would be nice if the arm64 patch will be tested on big-endian mode since I don't have access to any big-endian variant for testing. regards, Mamone

2 5

[S390x] Optimize various elliptic curve functions
by Maamoun TK 19 Jan '22

19 Jan '22

I created merge requests that have improvements of prime modulo functions of elliptic curves and scalar multiply of curve25519 and curve448 for s390x architecture https://git.lysator.liu.se/nettle/nettle/-/merge_requests/42 https://git.lysator.liu.se/nettle/nettle/-/merge_requests/43 The prime modulo functions are implemented using basic arithmetic instructions (including addition with carry and subtraction with borrow) while scalar multiply of curve25519 and curve448 takes advantage of hardware-accelerated instruction pcc (Perform Cryptographic Computation). Benchmark numbers of the patches are attached to the MR description. regards, Mamone

1 0

Re: Build problem on ppc64be + musl
by Maamoun TK 04 Jan '22

04 Jan '22

On Wed, Aug 18, 2021 at 11:38 PM Stijn Tintel <stijn(a)linux-ipv6.be> wrote: > On 18/08/2021 22:29, Maamoun TK wrote: > > On Tue, Aug 17, 2021 at 9:40 AM Niels Möller <nisse(a)lysator.liu.se > > <mailto:nisse@lysator.liu.se>> wrote: > > > > The configuration where it didn't work was > > powerpc64-openwrt-linux-musl. I'd like Nettle to work on embedded > > systems whenever practical. But support depends on assistance from > > users > > of those systems. > > > > As I understood it, this system needs to use the v2 ABI. I would hope > > it's easy to detect the abi used by the configured C compiler, and > > then > > select the same prologue sequence as is currently used for > > little-endian. I.e., one more configure test, and changing the > > "ifelse(WORDS_BIGENDIAN,no," condition in powerpc64/machine.m4 to > > check > > a different configure variable. > > > > > > I skipped processing the assembly files with a different approach, I > > made the configuration check for musl and endianness variant to > > trigger assembly processing. You can check the fix in this branch > > https://git.lysator.liu.se/mamonet/nettle/-/tree/ppc64_musl_fix > > <https://git.lysator.liu.se/mamonet/nettle/-/tree/ppc64_musl_fix> > > Apparently, the bug reporter uses a cross-compiler for powerpc arch. > > It would be great to run this fix at the same bug environment since I > > tested the patch in different circumstances. > > Your patch has no effect in my environment (OpenWrt build system), as > host_os is linux-gnu, according to config.log, so it doesn't match > *musl. See [1] for config.log and [2] for full compile log. > > The output of powerpc64-openwrt-linux-musl-gcc -E -dM - </dev/null | > sort, which was requested earlier in this thread can be seen at [3]. > > Thanks, > Stijn > > [1] https://gist.github.com/9e0ecb025033dda1d0d58094da84c308 > [2] https://gist.github.com/stintel/0e7046df511cf4d1ca20edb56df50b1b > [3] https://gist.github.com/stintel/b3651a7db87edea9e8bd0aef242bcdae config.guess detects the C standard library based on a result from the compiler defined in "CC_FOR_BUILD" variable, for some reason OpenWrt build system failed to set that variable properly, from your config.log I can see CC_FOR_BUILD='gcc -O -g' but when I use bare musl tools I get CC_FOR_BUILD='musl-gcc' There is nothing specific in the output of powerpc64-openwrt-linux-musl-gcc -E -dM log as I can see. In musl libc FAQ, they stated that there is no __MUSL__ in the preprocessor macros https://wiki.musl-libc.org/faq.html regards, Mamone

2 9

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007

2006

2005

2004

2003

2002

nettle-bugs January 2022