crypto: poly1305 - add new 32 and 64-bit generic versions
Subsystems (6)
Jason A. Donenfeld
maintainerPATCH 1/1 crypto: poly1305 - add new 32 and 64-bit generic versions
These two C implementations from Zinc -- a 32x32 one and a 64x64 one, depending on the platform -- come from Andrew Moon's public domain poly1305-donna portable code, modified for usage in the kernel. The precomputation in the 32-bit version and the use of 64x64 multiplies in the 64-bit version make these perform better than the code it replaces. Moon's code is also very widespread and has received many eyeballs of scrutiny.
There's a bit of interference between the x86 implementation, which relies on internal details of the old scalar implementation. Soon the x86 implementation will be replaced with a faster one that doesn't rely on this, but for now, we inline the bits of the old implementation that the x86 implementation relied on. Also, since we now support a slightly larger key space, via the union, some offsets had to be fixed up.
Nonce calculation was folded in with the emit function, to take advantage of 64x64 arithmetic. However, Adiantum appeared to rely on no nonce handling in emit, so this path was conditionalized. I don't have an Adiantum rig handy, so I'd appreciate a review from somebody who does and can make sure this doesn't break it.
--- arch/x86/crypto/poly1305-avx2-x86_64.S | 20 +-- arch/x86/crypto/poly1305_glue.c | 215 +++++++++++++++++++++++-- crypto/adiantum.c | 2 +- crypto/nhpoly1305.c | 2 +- crypto/poly1305_generic.c | 23 +++ include/crypto/internal/poly1305.h | 32 +--- include/crypto/poly1305.h | 10 +- lib/crypto/Kconfig | 2 +- lib/crypto/Makefile | 4 +- lib/crypto/poly1305-donna32.c | 204 +++++++++++++++++++++++ lib/crypto/poly1305-donna64.c | 185 +++++++++++++++++++++ lib/crypto/poly1305.c | 160 +----------------- 12 files changed, 644 insertions(+), 215 deletions(-) create mode 100644 lib/crypto/poly1305-donna32.c create mode 100644 lib/crypto/poly1305-donna64.c
arch/x86/crypto/poly1305-avx2-x86_64.S +10 -10
@@ -34,16 +34,16 @@ ORMASK: .octa 0x00000000010000000000000001000000 #define u2 0x08(%r8) #define u3 0x0c(%r8) #define u4 0x10(%r8) -#define w0 0x14(%r8) -#define w1 0x18(%r8) -#define w2 0x1c(%r8) -#define w3 0x20(%r8) -#define w4 0x24(%r8) -#define y0 0x28(%r8) -#define y1 0x2c(%r8) -#define y2 0x30(%r8) -#define y3 0x34(%r8) -#define y4 0x38(%r8) +#define w0 0x18(%r8) +#define w1 0x1c(%r8) +#define w2 0x20(%r8) +#define w3 0x24(%r8) +#define w4 0x28(%r8) +#define y0 0x30(%r8) +#define y1 0x34(%r8) +#define y2 0x38(%r8) +#define y3 0x3c(%r8) +#define y4 0x40(%r8) #define m %rsi #define hc0 %ymm0 #define hc1 %ymm1
arch/x86/crypto/poly1305_glue.c +204 -11
252 lines not on this page · raw message
crypto/adiantum.c +1 -1
@@ -249,7 +249,7 @@ static void adiantum_hash_header(struct skcipher_request *req)poly1305_core_blocks (&state, &tctx->header_hash_key, req->iv,TWEAK_SIZE /POLY1305_BLOCK_SIZE ,1 ); -poly1305_core_emit (&state, &rctx->header_hash); +poly1305_core_emit (&state,NULL , &rctx->header_hash); }/* Hash the left-hand part (the "bulk") of the message using NHPoly1305 */
crypto/nhpoly1305.c +1 -1
@@ -210,7 +210,7 @@ int crypto_nhpoly1305_final_helper(struct shash_desc *desc, u8 *dst, nh_t nh_fn)if (state->nh_remaining)process_nh_hash_value (state, key); -poly1305_core_emit (&state->poly_state, dst); +poly1305_core_emit (&state->poly_state,NULL , dst);return 0 ; }EXPORT_SYMBOL (crypto_nhpoly1305_final_helper);
crypto/poly1305_generic.c +23 -0
@@ -31,6 +31,29 @@ static int crypto_poly1305_init(struct shash_desc *desc)return 0 ; } +static unsigned int crypto_poly1305_setdesckey (struct poly1305_desc_ctx *dctx, +const u8 *src,unsigned int srclen) +{ +if (!dctx->sset) { +if (!dctx->rset && srclen >=POLY1305_BLOCK_SIZE ) { +poly1305_core_setkey (dctx->r, src); + src +=POLY1305_BLOCK_SIZE ; + srclen -=POLY1305_BLOCK_SIZE ; + dctx->rset =2 ; + } +if (srclen >=POLY1305_BLOCK_SIZE ) { + dctx->s[0 ] =get_unaligned_le32 (src +0 ); + dctx->s[1 ] =get_unaligned_le32 (src +4 ); + dctx->s[2 ] =get_unaligned_le32 (src +8 ); + dctx->s[3 ] =get_unaligned_le32 (src +12 ); + src +=POLY1305_BLOCK_SIZE ; + srclen -=POLY1305_BLOCK_SIZE ; + dctx->sset = true; + } + } +return srclen; +} +static void poly1305_blocks (struct poly1305_desc_ctx *dctx,const u8 *src,unsigned int srclen) {
include/crypto/internal/poly1305.h +2 -30
@@ -24,35 +24,7 @@ static inline void poly1305_core_init(struct poly1305_state *state)void poly1305_core_blocks (struct poly1305_state *state,const struct poly1305_key *key,const void *src,unsigned int nblocks,u32 hibit); -void poly1305_core_emit (const struct poly1305_state *state,void *dst); - -/* -* Poly1305 requires a unique key for each tag, which implies that we can't set -* it on the tfm that gets accessed by multiple users simultaneously. Instead we -* expect the key as the first 32 bytes in the update() call. -*/ -static inline -unsigned int crypto_poly1305_setdesckey (struct poly1305_desc_ctx *dctx, -const u8 *src,unsigned int srclen) -{ -if (!dctx->sset) { -if (!dctx->rset && srclen >=POLY1305_BLOCK_SIZE ) { -poly1305_core_setkey (dctx->r, src); - src +=POLY1305_BLOCK_SIZE ; - srclen -=POLY1305_BLOCK_SIZE ; - dctx->rset =1 ; - } -if (srclen >=POLY1305_BLOCK_SIZE ) { - dctx->s[0 ] =get_unaligned_le32 (src +0 ); - dctx->s[1 ] =get_unaligned_le32 (src +4 ); - dctx->s[2 ] =get_unaligned_le32 (src +8 ); - dctx->s[3 ] =get_unaligned_le32 (src +12 ); - src +=POLY1305_BLOCK_SIZE ; - srclen -=POLY1305_BLOCK_SIZE ; - dctx->sset = true; - } - } -return srclen; -} +void poly1305_core_emit (const struct poly1305_state *state,const u32 nonce[4 ], +void *dst);#endif
include/crypto/poly1305.h +8 -2
@@ -14,11 +14,17 @@#define POLY1305_DIGEST_SIZE 16struct poly1305_key { -u32 r[5 ];/* key, base 2^26 */ +union { +u32 r[5 ];/* key, base 2^26 */ +u64 r64[3 ]; + }; };struct poly1305_state { -u32 h[5 ];/* accumulator, base 2^26 */ +union { +u32 h[5 ];/* accumulator, base 2^26 */ +u64 h64[3 ]; + }; };struct poly1305_desc_ctx {
lib/crypto/Kconfig +1 -1
@@ -92,7 +92,7 @@ config CRYPTO_LIB_POLY1305_RSIZE default 2 if MIPS default 4 if X86_64 default 9 if ARM || ARM64 - default 1 + default 2 config CRYPTO_ARCH_HAVE_LIB_POLY1305 tristate
lib/crypto/Makefile +3 -1
@@ -28,7 +28,9 @@ obj-$(CONFIG_CRYPTO_LIB_DES) += libdes.o libdes-y := des.o obj-$(CONFIG_CRYPTO_LIB_POLY1305_GENERIC) += libpoly1305.o -libpoly1305-y := poly1305.o +libpoly1305-y := poly1305-donna32.o +libpoly1305-$(CONFIG_ARCH_SUPPORTS_INT128) := poly1305-donna64.o +libpoly1305-y += poly1305.o obj-$(CONFIG_CRYPTO_LIB_SHA256) += libsha256.o libsha256-y := sha256.o
lib/crypto/poly1305-donna32.c new file +204 -0
204 lines not on this page · raw message
lib/crypto/poly1305-donna64.c new file +185 -0
185 lines not on this page · raw message
lib/crypto/poly1305.c +2 -158
184 lines not on this page · raw message
Signature · 1 line
2.24.0
Eric Biggers
maintainerQuoted 7 lines · Jason A. Donenfeld
These two C implementations from Zinc -- a 32x32 one and a 64x64 one, depending on the platform -- come from Andrew Moon's public domain poly1305-donna portable code, modified for usage in the kernel. The precomputation in the 32-bit version and the use of 64x64 multiplies in the 64-bit version make these perform better than the code it replaces. Moon's code is also very widespread and has received many eyeballs of scrutiny.
Isn't the existing implementation in the kernel already based on the 32x32 code from Andrew Moon? Can you elaborate on how the new code is different?
Quoted 8 lines
There's a bit of interference between the x86 implementation, which relies on internal details of the old scalar implementation. Soon the x86 implementation will be replaced with a faster one that doesn't rely on this, but for now, we inline the bits of the old implementation that the x86 implementation relied on. Also, since we now support a slightly larger key space, via the union, some offsets had to be fixed up.
Quoted 8 lines
Nonce calculation was folded in with the emit function, to take advantage of 64x64 arithmetic. However, Adiantum appeared to rely on no nonce handling in emit, so this path was conditionalized. I don't have an Adiantum rig handy, so I'd appreciate a review from somebody who does and can make sure this doesn't break it.
Signed-off-by Jason A. Donenfeld <[email protected]>Cc Eric Biggers <[email protected]>
You can run the self-tests. But I tried and it doesn't get past nhpoly1305:
[ 0.856458] alg: shash: nhpoly1305-generic test failed (wrong result) on test vector 1, cfg="init+update+final aligned buffer"
Quoted 30 lines
include/crypto/internal/poly1305.h +0
-22@@ -24,35 +24,7 @@ static inline void poly1305_core_init(struct poly1305_state *state)void poly1305_core_blocks (struct poly1305_state *state,const struct poly1305_key *key,const void *src,unsigned int nblocks,u32 hibit); -void poly1305_core_emit (const struct poly1305_state *state,void *dst); - -/* -* Poly1305 requires a unique key for each tag, which implies that we can't set -* it on the tfm that gets accessed by multiple users simultaneously. Instead we -* expect the key as the first 32 bytes in the update() call. -*/ -static inline -unsigned int crypto_poly1305_setdesckey (struct poly1305_desc_ctx *dctx, -const u8 *src,unsigned int srclen) -{ -if (!dctx->sset) { -if (!dctx->rset && srclen >=POLY1305_BLOCK_SIZE ) { -poly1305_core_setkey (dctx->r, src); - src +=POLY1305_BLOCK_SIZE ; - srclen -=POLY1305_BLOCK_SIZE ; - dctx->rset =1 ; - } -if (srclen >=POLY1305_BLOCK_SIZE ) { - dctx->s[0 ] =get_unaligned_le32 (src +0 ); - dctx->s[1 ] =get_unaligned_le32 (src +4 ); - dctx->s[2 ] =get_unaligned_le32 (src +8 );
include/crypto/internal/poly1305.h static inline void poly1305_core_init(struct poly1305_state *state) · line 28
Quoted 10 lines
include/crypto/internal/poly1305.h +2
-8- dctx->s[3 ] =get_unaligned_le32 (src +12 ); - src +=POLY1305_BLOCK_SIZE ; - srclen -=POLY1305_BLOCK_SIZE ; - dctx->sset = true; - } - } -return srclen; -} +void poly1305_core_emit (const struct poly1305_state *state,const u32 nonce[4 ], +void *dst);
Adding nonce support here makes the comment above this code outdated.
/*
* Poly1305 core functions. These implement the ε-almost-∆-universal hash
* function underlying the Poly1305 MAC, i.e. they don't add an encrypted nonce
* ("s key") at the end. They also only support block-aligned inputs. */
Quoted 12 lines
include/crypto/poly1305.h +3
-1@@ -14,11 +14,17 @@#define POLY1305_DIGEST_SIZE 16struct poly1305_key { -u32 r[5 ];/* key, base 2^26 */ +union { +u32 r[5 ];/* key, base 2^26 */ +u64 r64[3 ];
include/crypto/poly1305.h line 28
Quoted 10 lines
include/crypto/poly1305.h +5
-1+ }; };struct poly1305_state { -u32 h[5 ];/* accumulator, base 2^26 */ +union { +u32 h[5 ];/* accumulator, base 2^26 */ +u64 h64[3 ]; + }; };
It would be helpful to include comments for the r64 and h64 fields, like there are for the r and h fields. What base is being used?
Quoted 24 lines
lib/crypto/poly1305-donna32.c new file +18
-0@@ -0,0 +1,204 @@ +// SPDX-License-Identifier: GPL-2.0 OR MIT +/* +* Copyright (C) 2015-2019 Jason A. Donenfeld <[email protected]>. All Rights Reserved. +* +* This is based in part on Andrew Moon's poly1305-donna, which is in the +* public domain. +*/ + +#include <linux/kernel.h> +#include <asm/unaligned.h> +#include <crypto/internal/poly1305.h> + +void poly1305_core_setkey (struct poly1305_key *key,const u8 raw_key[16 ]) +{ +/* r &= 0xffffffc0ffffffc0ffffffc0fffffff */ + key[0 ].r[0 ] = (get_unaligned_le32 (&raw_key[0 ])) &0x3ffffff ; + key[0 ].r[1 ] = (get_unaligned_le32 (&raw_key[3 ]) >>2 ) &0x3ffff03 ; + key[0 ].r[2 ] = (get_unaligned_le32 (&raw_key[6 ]) >>4 ) &0x3ffc0ff ;
lib/crypto/poly1305-donna32.c line 28
Quoted 10 lines
lib/crypto/poly1305-donna32.c new file +10
-0+ key[0 ].r[3 ] = (get_unaligned_le32 (&raw_key[9 ]) >>6 ) &0x3f03fff ; + key[0 ].r[4 ] = (get_unaligned_le32 (&raw_key[12 ]) >>8 ) &0x00fffff ; + +/* s = 5*r */ + key[1 ].r[0 ] = key[0 ].r[1 ] *5 ; + key[1 ].r[1 ] = key[0 ].r[2 ] *5 ; + key[1 ].r[2 ] = key[0 ].r[3 ] *5 ; + key[1 ].r[3 ] = key[0 ].r[4 ] *5 ; +} +EXPORT_SYMBOL (poly1305_core_setkey);
This assumes the struct poly1305_key is actually part of an array. This is probably what's causing the self-tests to fail, since some callers provide only a single struct poly1305_key.
Shouldn't this detail be hidden in struct poly1305_key? Or at least the functions should take 'struct poly1305_key key[2]' to make this assumption explicit.
- Eric
Jason A. Donenfeld
maintainerHey Eric,
Thanks for the review. I just finished porting the x86_64 code, which
I'll submit alongside v2 tomorrow, pending a night of sleep and some
rereading: https://git.kernel.org/pub/scm/linux/kernel/git/zx2c4/linux.git/commit/?h=jd/crypto-5.5&id=7380dd3ac2b8ea4a2b1b111139426c7d25374bba
Quoted 2 lines · Eric Biggers
Isn't the existing implementation in the kernel already based on the 32x32 code from Andrew Moon? Can you elaborate on how the new code is different?
It matches the style of the 64x64 one, so that it's easy to compare them. And, as mentioned in the commit message, it precomputes s1,s2,s3,s4, speeding up updates.
Quoted 3 lines
You can run the self-tests. But I tried and it doesn't get past nhpoly1305:
[ 0.856458] alg: shash: nhpoly1305-generic test failed (wrong result) on test vector 1, cfg="init+update+final aligned buffer"
Oh, right, duh. Okay, I'll submit v2 once I get those tests passing. Thanks.
Quoted 10 lines
include/crypto/internal/poly1305.h static inline void poly1305_core_init(struct poly1305_state *state) · line 28
Quoted 2 lines
include/crypto/internal/poly1305.h +2
-0+void poly1305_core_emit (const struct poly1305_state *state,const u32 nonce[4 ], +void *dst);Adding nonce support here makes the comment above this code outdated.
/*
* Poly1305 core functions. These implement the ε-almost-∆-universal hash
* function underlying the Poly1305 MAC, i.e. they don't add an encrypted nonce
* ("s key") at the end. They also only support block-aligned inputs. */
Ack.
Quoted 2 lines
It would be helpful to include comments for the r64 and h64 fields, like there are for the r and h fields. What base is being used?
Sure, I'll add comments.
Quoted 3 lines
This assumes the struct
poly1305_keyis actually part of an array. This is probably what's causing the self-tests to fail, since some callers provide only a single structpoly1305_key.
Thanks. Good catch.
Quoted 3 lines
Shouldn't this detail be hidden in struct
poly1305_key? Or at least the functions should take 'structpoly1305_keykey[2]' to make this assumption explicit.
I'll make it explicit. The way things work right now, the desc_ctx is an array of a .config-number of keys. In some future cleanup, I think that should basically be opaque instead, but I'll leave this out of this now, and instead fix up the signatures to make clear what's going on, and audit all callers.
Jason
Jason A. Donenfeld
maintainerPATCH v2 1/3 crypto: poly1305 - add new 32 and 64-bit generic versions
In reply to Jason A. DonenfeldThese two C implementations from Zinc -- a 32x32 one and a 64x64 one, depending on the platform -- come from Andrew Moon's public domain poly1305-donna portable code, modified for usage in the kernel. The precomputation in the 32-bit version and the use of 64x64 multiplies in the 64-bit version make these perform better than the code it replaces. Moon's code is also very widespread and has received many eyeballs of scrutiny.
There's a bit of interference between the x86 implementation, which relies on internal details of the old scalar implementation. In the next commit, the x86 implementation will be replaced with a faster one that doesn't rely on this, so none of this matters much. But for now, to keep this passing the tests, we inline the bits of the old implementation that the x86 implementation relied on. Also, since we now support a slightly larger key space, via the union, some offsets had to be fixed up.
Nonce calculation was folded in with the emit function, to take advantage of 64x64 arithmetic. However, Adiantum appeared to rely on no nonce handling in emit, so this path was conditionalized. It also assumed only one key's worth of storage, rather than the now two, so this has been updated.
--- arch/x86/crypto/poly1305-avx2-x86_64.S | 20 +-- arch/x86/crypto/poly1305_glue.c | 215 +++++++++++++++++++++++-- crypto/adiantum.c | 10 +- crypto/nhpoly1305.c | 6 +- crypto/poly1305_generic.c | 23 +++ include/crypto/internal/poly1305.h | 39 +---- include/crypto/nhpoly1305.h | 2 +- include/crypto/poly1305.h | 16 +- lib/crypto/Kconfig | 2 +- lib/crypto/Makefile | 4 +- lib/crypto/poly1305-donna32.c | 204 +++++++++++++++++++++++ lib/crypto/poly1305-donna64.c | 185 +++++++++++++++++++++ lib/crypto/poly1305.c | 160 +----------------- 13 files changed, 661 insertions(+), 225 deletions(-) create mode 100644 lib/crypto/poly1305-donna32.c create mode 100644 lib/crypto/poly1305-donna64.c
arch/x86/crypto/poly1305-avx2-x86_64.S +10 -10
@@ -34,16 +34,16 @@ ORMASK: .octa 0x00000000010000000000000001000000 #define u2 0x08(%r8) #define u3 0x0c(%r8) #define u4 0x10(%r8) -#define w0 0x14(%r8) -#define w1 0x18(%r8) -#define w2 0x1c(%r8) -#define w3 0x20(%r8) -#define w4 0x24(%r8) -#define y0 0x28(%r8) -#define y1 0x2c(%r8) -#define y2 0x30(%r8) -#define y3 0x34(%r8) -#define y4 0x38(%r8) +#define w0 0x18(%r8) +#define w1 0x1c(%r8) +#define w2 0x20(%r8) +#define w3 0x24(%r8) +#define w4 0x28(%r8) +#define y0 0x30(%r8) +#define y1 0x34(%r8) +#define y2 0x38(%r8) +#define y3 0x3c(%r8) +#define y4 0x40(%r8) #define m %rsi #define hc0 %ymm0 #define hc1 %ymm1
arch/x86/crypto/poly1305_glue.c +204 -11
252 lines not on this page · raw message
crypto/adiantum.c +5 -5
@@ -72,7 +72,7 @@ struct adiantum_tfm_ctx {struct crypto_skcipher *streamcipher;struct crypto_cipher *blockcipher;struct crypto_shash *hash; -struct poly1305_key header_hash_key; +struct poly1305_key header_hash_key[2 ]; };struct adiantum_request_ctx {
@@ -175,7 +175,7 @@ static int adiantum_setkey(struct crypto_skcipher *tfm, const u8 *key, keyp +=BLOCKCIPHER_KEY_SIZE ;/* Set the hash key (K_H) */ -poly1305_core_setkey (&tctx->header_hash_key, keyp); +poly1305_core_setkey (tctx->header_hash_key, keyp); keyp +=POLY1305_BLOCK_SIZE ;crypto_shash_clear_flags (tctx->hash,CRYPTO_TFM_REQ_MASK );
@@ -242,14 +242,14 @@ static void adiantum_hash_header(struct skcipher_request *req)poly1305_core_init (&state);BUILD_BUG_ON (sizeof (header) %POLY1305_BLOCK_SIZE !=0 ); -poly1305_core_blocks (&state, &tctx->header_hash_key, +poly1305_core_blocks (&state, tctx->header_hash_key, &header,sizeof (header) /POLY1305_BLOCK_SIZE ,1 );BUILD_BUG_ON (TWEAK_SIZE %POLY1305_BLOCK_SIZE !=0 ); -poly1305_core_blocks (&state, &tctx->header_hash_key, req->iv, +poly1305_core_blocks (&state, tctx->header_hash_key, req->iv,TWEAK_SIZE /POLY1305_BLOCK_SIZE ,1 ); -poly1305_core_emit (&state, &rctx->header_hash); +poly1305_core_emit (&state,NULL , &rctx->header_hash); }/* Hash the left-hand part (the "bulk") of the message using NHPoly1305 */
crypto/nhpoly1305.c +3 -3
@@ -78,7 +78,7 @@ static void process_nh_hash_value(struct nhpoly1305_state *state, {BUILD_BUG_ON (NH_HASH_BYTES %POLY1305_BLOCK_SIZE !=0 ); -poly1305_core_blocks (&state->poly_state, &key->poly_key, state->nh_hash, +poly1305_core_blocks (&state->poly_state, key->poly_key, state->nh_hash,NH_HASH_BYTES /POLY1305_BLOCK_SIZE ,1 ); }
@@ -131,7 +131,7 @@ int crypto_nhpoly1305_setkey(struct crypto_shash *tfm,if (keylen !=NHPOLY1305_KEY_SIZE )return -EINVAL ; -poly1305_core_setkey (&ctx->poly_key, key); +poly1305_core_setkey (ctx->poly_key, key); key +=POLY1305_BLOCK_SIZE ;for (i =0 ; i <NH_KEY_WORDS ; i++)
@@ -210,7 +210,7 @@ int crypto_nhpoly1305_final_helper(struct shash_desc *desc, u8 *dst, nh_t nh_fn)if (state->nh_remaining)process_nh_hash_value (state, key); -poly1305_core_emit (&state->poly_state, dst); +poly1305_core_emit (&state->poly_state,NULL , dst);return 0 ; }EXPORT_SYMBOL (crypto_nhpoly1305_final_helper);
crypto/poly1305_generic.c +23 -0
@@ -31,6 +31,29 @@ static int crypto_poly1305_init(struct shash_desc *desc)return 0 ; } +static unsigned int crypto_poly1305_setdesckey (struct poly1305_desc_ctx *dctx, +const u8 *src,unsigned int srclen) +{ +if (!dctx->sset) { +if (!dctx->rset && srclen >=POLY1305_BLOCK_SIZE ) { +poly1305_core_setkey (dctx->r, src); + src +=POLY1305_BLOCK_SIZE ; + srclen -=POLY1305_BLOCK_SIZE ; + dctx->rset =2 ; + } +if (srclen >=POLY1305_BLOCK_SIZE ) { + dctx->s[0 ] =get_unaligned_le32 (src +0 ); + dctx->s[1 ] =get_unaligned_le32 (src +4 ); + dctx->s[2 ] =get_unaligned_le32 (src +8 ); + dctx->s[3 ] =get_unaligned_le32 (src +12 ); + src +=POLY1305_BLOCK_SIZE ; + srclen -=POLY1305_BLOCK_SIZE ; + dctx->sset = true; + } + } +return srclen; +} +static void poly1305_blocks (struct poly1305_desc_ctx *dctx,const u8 *src,unsigned int srclen) {
include/crypto/internal/poly1305.h +6 -33
@@ -11,11 +11,12 @@#include <crypto/poly1305.h> /* -* Poly1305 core functions. These implement the ε-almost-∆-universal hash +* Poly1305 core functions. These can implement the ε-almost-∆-universal hash * function underlying the Poly1305 MAC, i.e. they don't add an encrypted nonce -* ("s key") at the end. They also only support block-aligned inputs. +* ("s key") at the end, by passing NULL to nonce. They also only support +* block-aligned inputs. */ -void poly1305_core_setkey (struct poly1305_key *key,const u8 *raw_key); +void poly1305_core_setkey (struct poly1305_key key[2 ],const u8 *raw_key);static inline void poly1305_core_init (struct poly1305_state *state) { *state = (struct poly1305_state ){};
@@ -24,35 +25,7 @@ static inline void poly1305_core_init(struct poly1305_state *state)void poly1305_core_blocks (struct poly1305_state *state,const struct poly1305_key *key,const void *src,unsigned int nblocks,u32 hibit); -void poly1305_core_emit (const struct poly1305_state *state,void *dst); - -/* -* Poly1305 requires a unique key for each tag, which implies that we can't set -* it on the tfm that gets accessed by multiple users simultaneously. Instead we -* expect the key as the first 32 bytes in the update() call. -*/ -static inline -unsigned int crypto_poly1305_setdesckey (struct poly1305_desc_ctx *dctx, -const u8 *src,unsigned int srclen) -{ -if (!dctx->sset) { -if (!dctx->rset && srclen >=POLY1305_BLOCK_SIZE ) { -poly1305_core_setkey (dctx->r, src); - src +=POLY1305_BLOCK_SIZE ; - srclen -=POLY1305_BLOCK_SIZE ; - dctx->rset =1 ; - } -if (srclen >=POLY1305_BLOCK_SIZE ) { - dctx->s[0 ] =get_unaligned_le32 (src +0 ); - dctx->s[1 ] =get_unaligned_le32 (src +4 ); - dctx->s[2 ] =get_unaligned_le32 (src +8 ); - dctx->s[3 ] =get_unaligned_le32 (src +12 ); - src +=POLY1305_BLOCK_SIZE ; - srclen -=POLY1305_BLOCK_SIZE ; - dctx->sset = true; - } - } -return srclen; -} +void poly1305_core_emit (const struct poly1305_state *state,const u32 nonce[4 ], +void *dst);#endif
include/crypto/nhpoly1305.h +1 -1
@@ -33,7 +33,7 @@#define NHPOLY1305_KEY_SIZE (POLY1305_BLOCK_SIZE + NH_KEY_BYTES)struct nhpoly1305_key { -struct poly1305_key poly_key; +struct poly1305_key poly_key[2 ];u32 nh_key[NH_KEY_WORDS ]; };
include/crypto/poly1305.h +14 -2
@@ -13,12 +13,24 @@#define POLY1305_KEY_SIZE 32#define POLY1305_DIGEST_SIZE 16 +/* The poly1305_key and poly1305_state types are mostly opaque and +* implementation-defined. Limbs might be in base 2^64 or base 2^26, or +* different yet. The union type provided keeps these 64-bit aligned for the +* case in which this is implemented using 64x64 multiplies. +*/ +struct poly1305_key { -u32 r[5 ];/* key, base 2^26 */ +union { +u32 r[5 ]; +u64 r64[3 ]; + }; };struct poly1305_state { -u32 h[5 ];/* accumulator, base 2^26 */ +union { +u32 h[5 ]; +u64 h64[3 ]; + }; };struct poly1305_desc_ctx {
lib/crypto/Kconfig +1 -1
@@ -92,7 +92,7 @@ config CRYPTO_LIB_POLY1305_RSIZE default 2 if MIPS default 4 if X86_64 default 9 if ARM || ARM64 - default 1 + default 2 config CRYPTO_ARCH_HAVE_LIB_POLY1305 tristate
lib/crypto/Makefile +3 -1
@@ -28,7 +28,9 @@ obj-$(CONFIG_CRYPTO_LIB_DES) += libdes.o libdes-y := des.o obj-$(CONFIG_CRYPTO_LIB_POLY1305_GENERIC) += libpoly1305.o -libpoly1305-y := poly1305.o +libpoly1305-y := poly1305-donna32.o +libpoly1305-$(CONFIG_ARCH_SUPPORTS_INT128) := poly1305-donna64.o +libpoly1305-y += poly1305.o obj-$(CONFIG_CRYPTO_LIB_SHA256) += libsha256.o libsha256-y := sha256.o
lib/crypto/poly1305-donna32.c new file +204 -0
204 lines not on this page · raw message
lib/crypto/poly1305-donna64.c new file +185 -0
185 lines not on this page · raw message
lib/crypto/poly1305.c +2 -158
184 lines not on this page · raw message
Signature · 1 line
2.24.0
Jason A. Donenfeld
maintainerPATCH v2 2/3 crypto: x86_64/poly1305 - add faster implementations
These x86_64 vectorized implementations are based on Andy Polyakov's implementation, and support AVX, AVX-2, and AVX512F. The AVX-512F implementation is disabled on Skylake, due to throttling, but it is quite fast on >= Cannonlake.
On the left is cycle counts on a Core i7 6700HQ using the AVX-2 codepath, comparing this implementation ("new") to the implementation in the current crypto api ("old"). On the right are benchmarks on a Xeon Gold 5120 using the AVX-512 codepath. The new implementation is faster on all benchmarks.
AVX-2 AVX-512
--------- -----------
size old new size old new ---- ---- ---- ---- ---- ---- 0 70 68 0 74 70 16 92 90 16 96 92 32 134 104 32 136 106 48 172 120 48 184 124 64 218 136 64 218 138 80 254 158 80 260 160 96 298 174 96 300 176 112 342 192 112 342 194 128 388 212 128 384 212 144 428 228 144 420 226 160 466 246 160 464 248 176 510 264 176 504 264 192 550 282 192 544 282 208 594 302 208 582 300 224 628 316 224 624 318 240 676 334 240 662 338 256 716 354 256 708 358 272 764 374 272 748 372 288 802 352 288 788 358 304 420 366 304 422 370 320 428 360 320 432 364 336 484 378 336 486 380 352 426 384 352 434 390 368 478 400 368 480 408 384 488 394 384 490 398 400 542 408 400 542 412 416 486 416 416 492 426 432 534 430 432 538 436 448 544 422 448 546 432 464 600 438 464 600 448 480 540 448 480 548 456 496 594 464 496 594 476 512 602 456 512 606 470 528 656 476 528 656 480 544 600 480 544 606 498 560 650 494 560 652 512 576 664 490 576 662 508 592 714 508 592 716 522 608 656 514 608 664 538 624 708 532 624 710 552 640 716 524 640 720 516 656 770 536 656 772 526 672 716 548 672 722 544 688 770 562 688 768 556 704 774 552 704 778 556 720 826 568 720 832 568 736 768 574 736 780 584 752 822 592 752 826 600 768 830 584 768 836 560 784 884 602 784 888 572 800 828 610 800 838 588 816 884 628 816 884 604 832 888 618 832 894 598 848 942 632 848 946 612 864 884 644 864 896 628 880 936 660 880 942 644 896 948 652 896 952 608 912 1000 664 912 1004 616 928 942 676 928 954 634 944 994 690 944 1000 646 960 1002 680 960 1008 646 976 1054 694 976 1062 658 992 1002 706 992 1012 674 1008 1052 720 1008 1058 690
--- arch/x86/crypto/Makefile | 12 +- arch/x86/crypto/poly1305-avx2-x86_64.S | 390 --- arch/x86/crypto/poly1305-sse2-x86_64.S | 590 ---- arch/x86/crypto/poly1305-x86_64.pl | 4266 ++++++++++++++++++++++++ arch/x86/crypto/poly1305_glue.c | 473 +-- lib/crypto/Kconfig | 2 +- 6 files changed, 4441 insertions(+), 1292 deletions(-) delete mode 100644 arch/x86/crypto/poly1305-avx2-x86_64.S delete mode 100644 arch/x86/crypto/poly1305-sse2-x86_64.S create mode 100644 arch/x86/crypto/poly1305-x86_64.pl
arch/x86/crypto/Makefile +7 -5
@@ -101,11 +101,8 @@ aesni-intel-y := aesni-intel_asm.o aesni-intel_glue.o aesni-intel-$(CONFIG_64BIT) += aesni-intel_avx-x86_64.o aes_ctrby8_avx-x86_64.o ghash-clmulni-intel-y := ghash-clmulni-intel_asm.o ghash-clmulni-intel_glue.o sha1-ssse3-y := sha1_ssse3_asm.o sha1_ssse3_glue.o -poly1305-x86_64-y := poly1305-sse2-x86_64.o poly1305_glue.o -ifeq ($(avx2_supported),yes) -sha1-ssse3-y += sha1_avx2_x86_64_asm.o -poly1305-x86_64-y += poly1305-avx2-x86_64.o -endif +poly1305-x86_64-y := poly1305-x86_64.o poly1305_glue.o +targets += poly1305-x86_64.S ifeq ($(sha1_ni_supported),yes) sha1-ssse3-y += sha1_ni_asm.o endif
@@ -118,3 +115,8 @@ sha256-ssse3-y += sha256_ni_asm.o endif sha512-ssse3-y := sha512-ssse3-asm.o sha512-avx-asm.o sha512-avx2-asm.o sha512_ssse3_glue.o crct10dif-pclmul-y := crct10dif-pcl-asm_64.o crct10dif-pclmul_glue.o + +quiet_cmd_perlasm = PERLASM $@ + cmd_perlasm = $(PERL) $< > $@ +$(obj)/%.S: $(src)/%.pl FORCE + $(call if_changed,perlasm)
arch/x86/crypto/poly1305-avx2-x86_64.S deleted +0 -390
390 lines not on this page · raw message
arch/x86/crypto/poly1305-sse2-x86_64.S deleted +0 -590
590 lines not on this page · raw message
arch/x86/crypto/poly1305-x86_64.pl new file +4266 -0
1,999 lines not on this page · raw message
arch/x86/crypto/poly1305_glue.c +167 -306
473 lines not on this page · raw message
The rest of this diff is not shown. View the raw message.
Signature · 1 line
2.24.0
Part of the diff is not shown here. View the raw message.
Jason A. Donenfeld
maintainerRe: [PATCH crypto-next v2 2/3] crypto: x86_64/poly1305 - add faster implementations
Looks like I accidentally removed sha1-ssse3-y from the Makefile in this one. I'll have this fixed for a v3, but please let me know if there are any other nits before I submit that.
Re: [PATCH crypto-next v2 2/3] crypto: x86_64/poly1305 - add faster implementations
In reply to Jason A. DonenfeldQuoted 9 lines
These
x86_64vectorized implementations are based on Andy Polyakov's implementation, and support AVX, AVX-2, and AVX512F. The AVX-512F implementation is disabled on Skylake, due to throttling, but it is quite fast on >= Cannonlake.arch/x86/crypto/poly1305-avx2-x86_64.S | 390 --- arch/x86/crypto/poly1305-sse2-x86_64.S | 590 ---- arch/x86/crypto/poly1305-x86_64.pl | 4266 ++++++++++++++++++++++++
As the author of the removed code, I'm certainly biased, so I won't hinder the adaption of the new code. Nonetheless some final remarks from my side:
* It removes the existing SSE2 code path. Most likely not that much of an issue due to the new AVX variant.
* I certainly would favor gradual improvement, and I think the code would allow it. But as said, not my pick.
* Those 4000+ lines perl/asm are a lot and a hard review; I won't find time and motivation to do it. ;-)
Thanks!
Martin
Jason A. Donenfeld
maintainerRe: [PATCH crypto-next v2 2/3] crypto: x86_64/poly1305 - add faster implementations
Hi Martin,
Quoted 2 lines · Martin Willi
As the author of the removed code, I'm certainly biased, so I won't hinder the adaption of the new code.
Thanks.
Quoted 2 lines
* It removes the existing SSE2 code path. Most likely not that much of an issue due to the new AVX variant.
It's not clear that that sse2 code is even faster than the x86_64 scalar code in the new implementation, actually. Either way, regardless of that, in spite of the previous sentence, I don't think it really matters, based on the chips we care about targeting.
Quoted 2 lines
* I certainly would favor gradual improvement, and I think the code would allow it. But as said, not my pick.
You saw this code well over a year ago and seemed okay with it at the time. Meanwhile you were inspired to fix your ChaCha implementation to narrow the gap, but no progress with your Poly1305 one. And I'd like to avoid adding a NEW implementation to audit for bugs and vulnerabilities and stuff. On the contrary, this code here is in widespread use and has been highly scrutinized. So please, don't waste time doing such a thing. I'd nack it on the grounds of it being an unnecessary risk.
Quoted 1 line
* Those 4000+ lines perl/asm are a lot
Ard just added the same for the new Poly1305 implementations on ARM, ARM64, MIPS, and MIPS64. This is code that's seen the most possible eyeballs of code in this category. And now we're finally converging on a complete set for that, with x86_64 being the last holdout. Please don't hinder its adoption. Your old code is slow and hasn't received much scrutiny. This new code is fast and has received a lot of scrutiny.
Jason
Re: [PATCH crypto-next v2 2/3] crypto: x86_64/poly1305 - add faster implementations
Quoted 7 lines
Quoted 2 lines
* It removes the existing SSE2 code path. Most likely not that much of an issue due to the new AVX variant.
It's not clear that that sse2 code is even faster than the
x86_64scalar code in the new implementation, actually. Either way, regardless of that, in spite of the previous sentence, I don't think it really matters, based on the chips we care about targeting.
There is remark in commentary section. SSE2 was faster on P4 and and early Core processors, but for non-Intel and contemporary non-AVX-capable processors, most notably from Atom family, scalar x86_64 *is* fastest option. As for scalar performance on legacy Intel processors, for me omitting SSE2 meant ~33% loss for oldest P4 and less for not as old ones. [Just in case, situation is naturally different on 32-bit systems. From coverage vs. performance viewpoint SSE2+AVX2 is arguably more suitable mix in 32-bit case, AVX makes lesser sense, because gain is not impressive enough in comparison to SSE2.]
Cheers.
Jason A. Donenfeld
maintainerPATCH v2 3/3 crypto: arm/arm64/mips/poly1305 - remove redundant non-reduction from emit
In reply to Jason A. DonenfeldThis appears to be some kind of copy and paste error, and is actually dead code.
Pre: f = 0 ⇒ (f >> 32) = 0
f = (f >> 32) + le32_to_cpu(digest[0]);
Post: 0 ≤ f < 2³²
put_unaligned_le32(f, dst);Pre: 0 ≤ f < 2³² ⇒ (f >> 32) = 0
f = (f >> 32) + le32_to_cpu(digest[1]);
Post: 0 ≤ f < 2³²
put_unaligned_le32(f, dst + 4);Pre: 0 ≤ f < 2³² ⇒ (f >> 32) = 0
f = (f >> 32) + le32_to_cpu(digest[2]);
Post: 0 ≤ f < 2³²
put_unaligned_le32(f, dst + 8);Pre: 0 ≤ f < 2³² ⇒ (f >> 32) = 0
f = (f >> 32) + le32_to_cpu(digest[3]);
Post: 0 ≤ f < 2³²
put_unaligned_le32(f, dst + 12);Therefore this sequence is redundant. And Andy's code appears to handle misalignment acceptably.
--- arch/arm/crypto/poly1305-glue.c | 18 ++---------------- arch/arm64/crypto/poly1305-glue.c | 18 ++---------------- arch/mips/crypto/poly1305-glue.c | 18 ++---------------- 3 files changed, 6 insertions(+), 48 deletions(-)
arch/arm/crypto/poly1305-glue.c +2 -16
@@ -20,7 +20,7 @@void poly1305_init_arm (void *state,const u8 *key);void poly1305_blocks_arm (void *state,const u8 *src,u32 len,u32 hibit); -void poly1305_emit_arm (void *state,__le32 *digest,const u32 *nonce); +void poly1305_emit_arm (void *state,u8 *digest,const u32 *nonce);void __weak poly1305_blocks_neon (void *state,const u8 *src,u32 len,u32 hibit) {
@@ -179,9 +179,6 @@ EXPORT_SYMBOL(poly1305_update_arch);void poly1305_final_arch (struct poly1305_desc_ctx *dctx,u8 *dst) { -__le32 digest[4 ]; -u64 f =0 ; -if (unlikely (dctx->buflen)) { dctx->buf[dctx->buflen++] =1 ; memset(dctx->buf + dctx->buflen, 0,
@@ -189,18 +186,7 @@ void poly1305_final_arch(struct poly1305_desc_ctx *dctx, u8 *dst)poly1305_blocks_arm (&dctx->h, dctx->buf,POLY1305_BLOCK_SIZE ,0 ); } -poly1305_emit_arm (&dctx->h, digest, dctx->s); - -/* mac = (h + s) % (2^128) */ - f = (f >>32 ) +le32_to_cpu (digest[0 ]); -put_unaligned_le32 (f, dst); - f = (f >>32 ) +le32_to_cpu (digest[1 ]); -put_unaligned_le32 (f, dst +4 ); - f = (f >>32 ) +le32_to_cpu (digest[2 ]); -put_unaligned_le32 (f, dst +8 ); - f = (f >>32 ) +le32_to_cpu (digest[3 ]); -put_unaligned_le32 (f, dst +12 ); - +poly1305_emit_arm (&dctx->h, dst, dctx->s); *dctx = (struct poly1305_desc_ctx ){}; }EXPORT_SYMBOL (poly1305_final_arch);
arch/arm64/crypto/poly1305-glue.c +2 -16
@@ -21,7 +21,7 @@ asmlinkage void poly1305_init_arm64(void *state, const u8 *key); asmlinkage void poly1305_blocks(void *state, const u8 *src, u32 len, u32 hibit); asmlinkage void poly1305_blocks_neon(void *state, const u8 *src, u32 len, u32 hibit); -asmlinkage void poly1305_emit(void *state, __le32 *digest, const u32 *nonce); +asmlinkage void poly1305_emit(void *state, u8 *digest, const u32 *nonce);static __ro_after_init DEFINE_STATIC_KEY_FALSE (have_neon);
@@ -162,9 +162,6 @@ EXPORT_SYMBOL(poly1305_update_arch);void poly1305_final_arch (struct poly1305_desc_ctx *dctx,u8 *dst) { -__le32 digest[4 ]; -u64 f =0 ; -if (unlikely (dctx->buflen)) { dctx->buf[dctx->buflen++] =1 ; memset(dctx->buf + dctx->buflen, 0,
@@ -172,18 +169,7 @@ void poly1305_final_arch(struct poly1305_desc_ctx *dctx, u8 *dst)poly1305_blocks (&dctx->h, dctx->buf,POLY1305_BLOCK_SIZE ,0 ); } -poly1305_emit (&dctx->h, digest, dctx->s); - -/* mac = (h + s) % (2^128) */ - f = (f >>32 ) +le32_to_cpu (digest[0 ]); -put_unaligned_le32 (f, dst); - f = (f >>32 ) +le32_to_cpu (digest[1 ]); -put_unaligned_le32 (f, dst +4 ); - f = (f >>32 ) +le32_to_cpu (digest[2 ]); -put_unaligned_le32 (f, dst +8 ); - f = (f >>32 ) +le32_to_cpu (digest[3 ]); -put_unaligned_le32 (f, dst +12 ); - +poly1305_emit (&dctx->h, dst, dctx->s); *dctx = (struct poly1305_desc_ctx ){}; }EXPORT_SYMBOL (poly1305_final_arch);
arch/mips/crypto/poly1305-glue.c +2 -16
@@ -15,7 +15,7 @@ asmlinkage void poly1305_init_mips(void *state, const u8 *key); asmlinkage void poly1305_blocks_mips(void *state, const u8 *src, u32 len, u32 hibit); -asmlinkage void poly1305_emit_mips(void *state, __le32 *digest, const u32 *nonce); +asmlinkage void poly1305_emit_mips(void *state, u8 *digest, const u32 *nonce);void poly1305_init_arch (struct poly1305_desc_ctx *dctx,const u8 *key) {
@@ -134,9 +134,6 @@ EXPORT_SYMBOL(poly1305_update_arch);void poly1305_final_arch (struct poly1305_desc_ctx *dctx,u8 *dst) { -__le32 digest[4 ]; -u64 f =0 ; -if (unlikely (dctx->buflen)) { dctx->buf[dctx->buflen++] =1 ; memset(dctx->buf + dctx->buflen, 0,
@@ -144,18 +141,7 @@ void poly1305_final_arch(struct poly1305_desc_ctx *dctx, u8 *dst)poly1305_blocks_mips (&dctx->h, dctx->buf,POLY1305_BLOCK_SIZE ,0 ); } -poly1305_emit_mips (&dctx->h, digest, dctx->s); - -/* mac = (h + s) % (2^128) */ - f = (f >>32 ) +le32_to_cpu (digest[0 ]); -put_unaligned_le32 (f, dst); - f = (f >>32 ) +le32_to_cpu (digest[1 ]); -put_unaligned_le32 (f, dst +4 ); - f = (f >>32 ) +le32_to_cpu (digest[2 ]); -put_unaligned_le32 (f, dst +8 ); - f = (f >>32 ) +le32_to_cpu (digest[3 ]); -put_unaligned_le32 (f, dst +12 ); - +poly1305_emit_mips (&dctx->h, dst, dctx->s); *dctx = (struct poly1305_desc_ctx ){}; }EXPORT_SYMBOL (poly1305_final_arch);
Signature · 1 line
2.24.0
Re: [PATCH crypto-next v2 3/3] crypto: arm/arm64/mips/poly1305 - remove redundant non-reduction from emit
Quoted 24 lines · Jason A. Donenfeld
This appears to be some kind of copy and paste error, and is actually dead code.
Pre: f = 0 ⇒ (f >> 32) = 0
f = (f >> 32) + le32_to_cpu(digest[0]); Post: 0 ≤ f < 2³² put_unaligned_le32(f, dst);Pre: 0 ≤ f < 2³² ⇒ (f >> 32) = 0
f = (f >> 32) + le32_to_cpu(digest[1]); Post: 0 ≤ f < 2³² put_unaligned_le32(f, dst + 4);Pre: 0 ≤ f < 2³² ⇒ (f >> 32) = 0
f = (f >> 32) + le32_to_cpu(digest[2]); Post: 0 ≤ f < 2³² put_unaligned_le32(f, dst + 8);Pre: 0 ≤ f < 2³² ⇒ (f >> 32) = 0
f = (f >> 32) + le32_to_cpu(digest[3]); Post: 0 ≤ f < 2³² put_unaligned_le32(f, dst + 12);
Quoted 6 lines
Therefore this sequence is redundant. And Andy's code appears to handle misalignment acceptably.
Signed-off-by Jason A. Donenfeld <[email protected]>Cc Ard Biesheuvel <[email protected]>---
The change is obviously correct, but I ran it on a big-endian system just to be sure.
Quoted 137 lines
arch/arm/crypto/poly1305-glue.c | 18 ++---------------- arch/arm64/crypto/poly1305-glue.c | 18 ++---------------- arch/mips/crypto/poly1305-glue.c | 18 ++---------------- 3 files changed, 6 insertions(+), 48 deletions(-)arch/arm/crypto/poly1305-glue.c +2
-16@@ -20,7 +20,7 @@void poly1305_init_arm (void *state,const u8 *key);void poly1305_blocks_arm (void *state,const u8 *src,u32 len,u32 hibit); -void poly1305_emit_arm (void *state,__le32 *digest,const u32 *nonce); +void poly1305_emit_arm (void *state,u8 *digest,const u32 *nonce);void __weak poly1305_blocks_neon (void *state,const u8 *src,u32 len,u32 hibit) {@@ -179,9 +179,6 @@ EXPORT_SYMBOL(poly1305_update_arch);void poly1305_final_arch (struct poly1305_desc_ctx *dctx,u8 *dst) { -__le32 digest[4 ]; -u64 f =0 ; -if (unlikely (dctx->buflen)) { dctx->buf[dctx->buflen++] =1 ; memset(dctx->buf + dctx->buflen, 0,@@ -189,18 +186,7 @@ void poly1305_final_arch(struct poly1305_desc_ctx *dctx, u8 *dst)poly1305_blocks_arm (&dctx->h, dctx->buf,POLY1305_BLOCK_SIZE ,0 ); } -poly1305_emit_arm (&dctx->h, digest, dctx->s); - -/* mac = (h + s) % (2^128) */ - f = (f >>32 ) +le32_to_cpu (digest[0 ]); -put_unaligned_le32 (f, dst); - f = (f >>32 ) +le32_to_cpu (digest[1 ]); -put_unaligned_le32 (f, dst +4 ); - f = (f >>32 ) +le32_to_cpu (digest[2 ]); -put_unaligned_le32 (f, dst +8 ); - f = (f >>32 ) +le32_to_cpu (digest[3 ]); -put_unaligned_le32 (f, dst +12 ); - +poly1305_emit_arm (&dctx->h, dst, dctx->s); *dctx = (struct poly1305_desc_ctx ){}; }EXPORT_SYMBOL (poly1305_final_arch);arch/arm64/crypto/poly1305-glue.c +2
-16@@ -21,7 +21,7 @@ asmlinkage void poly1305_init_arm64(void *state, const u8 *key); asmlinkage void poly1305_blocks(void *state, const u8 *src, u32 len, u32 hibit); asmlinkage void poly1305_blocks_neon(void *state, const u8 *src, u32 len, u32 hibit); -asmlinkage void poly1305_emit(void *state, __le32 *digest, const u32 *nonce); +asmlinkage void poly1305_emit(void *state, u8 *digest, const u32 *nonce);static __ro_after_init DEFINE_STATIC_KEY_FALSE (have_neon);@@ -162,9 +162,6 @@ EXPORT_SYMBOL(poly1305_update_arch);void poly1305_final_arch (struct poly1305_desc_ctx *dctx,u8 *dst) { -__le32 digest[4 ]; -u64 f =0 ; -if (unlikely (dctx->buflen)) { dctx->buf[dctx->buflen++] =1 ; memset(dctx->buf + dctx->buflen, 0,@@ -172,18 +169,7 @@ void poly1305_final_arch(struct poly1305_desc_ctx *dctx, u8 *dst)poly1305_blocks (&dctx->h, dctx->buf,POLY1305_BLOCK_SIZE ,0 ); } -poly1305_emit (&dctx->h, digest, dctx->s); - -/* mac = (h + s) % (2^128) */ - f = (f >>32 ) +le32_to_cpu (digest[0 ]); -put_unaligned_le32 (f, dst); - f = (f >>32 ) +le32_to_cpu (digest[1 ]); -put_unaligned_le32 (f, dst +4 ); - f = (f >>32 ) +le32_to_cpu (digest[2 ]); -put_unaligned_le32 (f, dst +8 ); - f = (f >>32 ) +le32_to_cpu (digest[3 ]); -put_unaligned_le32 (f, dst +12 ); - +poly1305_emit (&dctx->h, dst, dctx->s); *dctx = (struct poly1305_desc_ctx ){}; }EXPORT_SYMBOL (poly1305_final_arch);arch/mips/crypto/poly1305-glue.c +2
-17@@ -15,7 +15,7 @@ asmlinkage void poly1305_init_mips(void *state, const u8 *key); asmlinkage void poly1305_blocks_mips(void *state, const u8 *src, u32 len, u32 hibit); -asmlinkage void poly1305_emit_mips(void *state, __le32 *digest, const u32 *nonce); +asmlinkage void poly1305_emit_mips(void *state, u8 *digest, const u32 *nonce);void poly1305_init_arch (struct poly1305_desc_ctx *dctx,const u8 *key) {@@ -134,9 +134,6 @@ EXPORT_SYMBOL(poly1305_update_arch);void poly1305_final_arch (struct poly1305_desc_ctx *dctx,u8 *dst) { -__le32 digest[4 ]; -u64 f =0 ; -if (unlikely (dctx->buflen)) { dctx->buf[dctx->buflen++] =1 ; memset(dctx->buf + dctx->buflen, 0,@@ -144,18 +141,7 @@ void poly1305_final_arch(struct poly1305_desc_ctx *dctx, u8 *dst)poly1305_blocks_mips (&dctx->h, dctx->buf,POLY1305_BLOCK_SIZE ,0 ); } -poly1305_emit_mips (&dctx->h, digest, dctx->s); - -/* mac = (h + s) % (2^128) */ - f = (f >>32 ) +le32_to_cpu (digest[0 ]); -put_unaligned_le32 (f, dst); - f = (f >>32 ) +le32_to_cpu (digest[1 ]); -put_unaligned_le32 (f, dst +4 ); - f = (f >>32 ) +le32_to_cpu (digest[2 ]); -put_unaligned_le32 (f, dst +8 ); - f = (f >>32 ) +le32_to_cpu (digest[3 ]); -put_unaligned_le32 (f, dst +12 ); - +poly1305_emit_mips (&dctx->h, dst, dctx->s); *dctx = (struct poly1305_desc_ctx ){}; }EXPORT_SYMBOL (poly1305_final_arch); --2.24.0
Hi Jason,
Quoted 6 lines
These two C implementations from Zinc -- a 32x32 one and a 64x64 one, depending on the platform -- come from Andrew Moon's public domain poly1305-donna portable code, modified for usage in the kernel. The precomputation in the 32-bit version and the use of 64x64 multiplies in the 64-bit version make these perform better than the code it replaces.
Can you provide some numbers to testify that? In my tests, the 32-bit version gives me exact the same results.
The 64-bit version is roughly 10% faster. However, what are the platforms where the 64-bit version matters? Won't any SIMD version outperform the 64-bit version anyway?
Martin
Jason A. Donenfeld
maintainerHi Martin,
Quoted 2 lines · Martin Willi
Can you provide some numbers to testify that? In my tests, the 32-bit version gives me exact the same results.
On 32-bit, if you only call update() once, then the results are the same. However, as soon as you call it more than once, this new version has increasing gains. Other than that, they should behave pretty much identically.
Quoted 3 lines
The 64-bit version is roughly 10% faster. However, what are the platforms where the 64-bit version matters? Won't any SIMD version outperform the 64-bit version anyway?
Depending on the platform, it's sometimes more than 10% faster. Not all 64-bit platforms have the luxury of a SIMD version. And not all code paths wind up hitting the SIMD version, either. The code is very short and simple -- and compiles shorter than the 32-bit one actually -- and placed side by side with the new 32-bit one, you can pretty easily compare them as clean standalone things. I think there's no good reason for being attached to your old code here; it's all mostly Andrew's stuff anyway.
Jason
Jason A. Donenfeld
maintainerQuoted 11 lines · Jason A. Donenfeld
Hi Martin,
Quoted 2 lines · Martin Willi
Can you provide some numbers to testify that? In my tests, the 32-bit version gives me exact the same results.
On 32-bit, if you only call
update()once, then the results are the same. However, as soon as you call it more than once, this new version has increasing gains. Other than that, they should behave pretty much identically.
Oh, you asked for numbers. I just fired up an Armada 370/XP and am seeing a 8% increase in performance on calls to the update function.
Quoted 9 lines · Jason A. Donenfeld
Quoted 7 lines · Jason A. Donenfeld
Hi Martin,
Quoted 2 lines · Martin Willi
Can you provide some numbers to testify that? In my tests, the 32-bit version gives me exact the same results.
Quoted 7 lines
Quoted 4 lines
On 32-bit, if you only call
update()once, then the results are the same. However, as soon as you call it more than once, this new version has increasing gains. Other than that, they should behave pretty much identically.Oh, you asked for numbers. I just fired up an Armada 370/XP and am seeing a 8% increase in performance on calls to the update function.
It would help if we could get some actual numbers. I usually try to capture the performance delta for a small set of block sizes that are significant for the use case at hand, e.g., like so [0], and also include blocksizes that are not 2^n. If the change improves the general case without causing any significant regressions elsewhere, I don't think we need to continue this debate.
Jason A. Donenfeld
maintainerQuoted 19 lines · Ard Biesheuvel
Quoted 9 lines · Jason A. Donenfeld
Quoted 7 lines · Jason A. Donenfeld
Hi Martin,
Quoted 2 lines · Martin Willi
Can you provide some numbers to testify that? In my tests, the 32-bit version gives me exact the same results.
Quoted 7 lines
Quoted 4 lines
On 32-bit, if you only call
update()once, then the results are the same. However, as soon as you call it more than once, this new version has increasing gains. Other than that, they should behave pretty much identically.Oh, you asked for numbers. I just fired up an Armada 370/XP and am seeing a 8% increase in performance on calls to the update function.
Quoted 6 lines
It would help if we could get some actual numbers. I usually try to capture the performance delta for a small set of block sizes that are significant for the use case at hand, e.g., like so [0], and also include blocksizes that are not 2^n. If the change improves the general case without causing any significant regressions elsewhere, I don't think we need to continue this debate.
I'm not sure I understand why the 32x32 performance discussion is even happening in the first place. The new 32x32 code most certainly doesn't make anything worse. It most likely makes some things better in some places -- 8% on that machine I fired up, maybe more and maybe less other places. But who even cares? The principle advantage of this patchset is the 64x64 code, and I think we gain something else, immeasurable, by having parallel and comparable implementations. Please, let's not turn this into another pointless debate.
Quoted 2 lines
The principle advantage of this patchset is the 64x64 code
If there are platforms / code paths where this code matters, all fine.
But the 64-bit version adds a lot of complexity because of the different state representation and the conversion between these states. I just don't think the gain (?) justifies that added complexity.
Martin
Jason A. Donenfeld
maintainerQuoted 3 lines · Martin Willi
Quoted 1 line
The principle advantage of this patchset is the 64x64 code
If there are platforms / code paths where this code matters, all fine.
It does matter.
Quoted 4 lines
But the 64-bit version adds a lot of complexity because of the different state representation and the conversion between these states. I just don't think the gain (?) justifies that added complexity.
No, there's no conversion between the state representation, or any complexity like that added.
I think if anything, the way this patch works, we wind up with something easier to audit and look at. You can examine poly1305-donna32.c and poly1305-donna64.c side-by-side and compare line-by-line, as clean and isolate implementations. And this is very well-known code too.
Eric Biggers
maintainerQuoted 12 lines · Jason A. Donenfeld
Quoted 3 lines · Martin Willi
Quoted 1 line
The principle advantage of this patchset is the 64x64 code
If there are platforms / code paths where this code matters, all fine.
It does matter.
Quoted 4 lines
But the 64-bit version adds a lot of complexity because of the different state representation and the conversion between these states. I just don't think the gain (?) justifies that added complexity.
Quoted 8 lines
No, there's no conversion between the state representation, or any complexity like that added.
I think if anything, the way this patch works, we wind up with something easier to audit and look at. You can examine
poly1305-donna32.candpoly1305-donna64.cside-by-side and compare line-by-line, as clean and isolate implementations. And this is very well-known code too.
It's inherently more complex to have multiple alternate implementations, and it reduces testability because there's no obvious way to even test your 32-bit version on x86_64 (which most developers use), as it seems your 64-bit version always gets built instead.
Now, it's possible that the performance gain outweighs this, and I too would like to have the C implementation of Poly1305 be faster. So if you'd like to argue for the performance gain, fine, and if there's a significant performance gain I don't have an objection. But I'm not sure why you're at the same time trying to argue that *adding* an extra implementation somehow makes the code easier to audit and doesn't add complexity...
- Eric
Herbert Xu
maintainerQuoted 7 lines · Eric Biggers
Now, it's possible that the performance gain outweighs this, and I too would like to have the C implementation of Poly1305 be faster. So if you'd like to argue for the performance gain, fine, and if there's a significant performance gain I don't have an objection. But I'm not sure why you're at the same time trying to argue that *adding* an extra implementation somehow makes the code easier to audit and doesn't add complexity...
Right. We need the numbers not because we're somehow attached to the existing code, but we need them to show that we should carry the burden of having two C implementations, 32-bit vs 64-bit.
Thanks,
Signature · 3 lines
Email: Herbert Xu <[email protected]> Home Page: http://gondor.apana.org.au/~herbert/ PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
Jason A. Donenfeld
maintainerHi Herbert,
Quoted 10 lines · Herbert Xu
Quoted 7 lines · Eric Biggers
Now, it's possible that the performance gain outweighs this, and I too would like to have the C implementation of Poly1305 be faster. So if you'd like to argue for the performance gain, fine, and if there's a significant performance gain I don't have an objection. But I'm not sure why you're at the same time trying to argue that *adding* an extra implementation somehow makes the code easier to audit and doesn't add complexity...
Quoted 3 lines
Right. We need the numbers not because we're somehow attached to the existing code, but we need them to show that we should carry the burden of having two C implementations, 32-bit vs 64-bit.
This info is now in the commit message of the version in my tree, rather than sprinkled around casually in these threads. I also did a bit more benchmarking this morning.
From <https://git.zx2c4.com/linux-dev/commit/?h=jd/crypto-5.5&id=900b79e1ff48f1f294ef3e9fb2520699c8895860>:
Quoted 5 lines
Testing with kbench9000, depending on the CPU, the update function for the 32x32 version has been improved by 4%-7%, and for the 64x64 by 19%-30%. The 32x32 gains are small, but I think there's great value in having a parallel implementation to the 64x64 one so that the two can be compared side-by-side as nice stand-alone units.
I'll resubmit this on Monday.
Regards,
Jason
Jason A. Donenfeld
maintainerHi Eric,
Quoted 6 lines · Eric Biggers
Now, it's possible that the performance gain outweighs this, and I too would like to have the C implementation of Poly1305 be faster. So if you'd like to argue for the performance gain, fine, and if there's a significant performance gain I don't have an objection. But I'm not sure why you're at the same time trying to argue that *adding* an extra implementation somehow makes the code easier to audit and doesn't add complexity...
Sorry, I don't mean to be confusing, but I clearly haven't written very well. There are two things being discussed here, 32-bit and 64-bit, rather than just one. Let me clarify:
- The motivation for the 64-bit version is primarily performance. Its performance isn't really in dispute. It's significant and good. I'll put this in the commit message of the next series I send out.
- The motivation for the 32-bit version is primarily to have code that can be compared line by line to the 64-bit version, in order to make auditing easier given the situation with two implementations and also for general cleanliness. I think there's enormous value in having the other implementation be "parallel". Rather than two totally different and foreign implementations, we have two related and comparable ones. That's a good thing. As a *side note*, it might also be slightly faster than the one it replaces, which is great and all I guess, but not the primary motivation of the 32-bit version.
Does that make sense? That's why I appear to simultaneously be arguing that performance matters and doesn't matter. The motivation for the 64-bit version is performance. The motivation for the 32-bit version is cleanliness. Two things, which are related.
I'll make this clear in the commit message of the next series I send. Sorry again for being confusing.
Jason