Skip to contentSkip to conversation

crypto: poly1305 - add new 32 and 64-bit generic versions

PATCH Superseded Jason A. Donenfeld 6 participants 22 messages Dec 11, 2019 – Dec 15, 2019

Subsystems (6)
Arm (32-bit) x86 MIPS Crypto API +2 more subsystems

v1 of 8 Superseded Latest is v8 →

lore
Share & tools
lore

Jason A. Donenfeld

author maintainer
#0 lore raw

PATCH 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
index d6063feda9da..8f56989ea599 100644
@@ -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
index aded26092268..2a45faf81201 100644
@@ -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
index f6b6a52092b4..8a3006c3b51b 100644
@@ -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
index 21edbd8c99fb..e2c8bc81ab02 100644
@@ -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
index 479b0cab2a1a..6e275d3e5969 100644
@@ -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
index 74c6e1cd73ee..dec2bd6b5aee 100644
@@ -14,11 +14,17 @@
 #define POLY1305_DIGEST_SIZE	16
 
 struct 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
index 0b2c4fce26d9..2d4a8f385e62 100644
@@ -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
index 34a701ab8b92..d19e5195569e 100644
@@ -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
maintainer
#1 lore raw
Quoted 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.

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
index 479b0cab2a1a..6e275d3e5969 100644
@@ -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
index 74c6e1cd73ee..dec2bd6b5aee 100644
@@ -14,11 +14,17 @@
 #define POLY1305_DIGEST_SIZE	16
 
 struct 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
new file mode 100644
index 000000000000..39b3fde68dcf
@@ -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

author maintainer
#2 lore raw

Hey 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_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.

Thanks. Good catch.

Quoted 3 lines

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.

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

author maintainer
#3 lore raw

PATCH v2 1/3 crypto: poly1305 - add new 32 and 64-bit generic versions

In reply to 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.

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
index d6063feda9da..8f56989ea599 100644
@@ -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
index aded26092268..efcbc18a852c 100644
@@ -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
index f6b6a52092b4..d5c06abade0e 100644
@@ -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
index 21edbd8c99fb..e2c8bc81ab02 100644
@@ -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
index 479b0cab2a1a..ad97819711eb 100644
@@ -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
index 53c04423c582..a2f4e37b5107 100644
@@ -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
index 74c6e1cd73ee..57f73285b4a2 100644
@@ -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
index 0b2c4fce26d9..2d4a8f385e62 100644
@@ -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
index 34a701ab8b92..d19e5195569e 100644
@@ -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
author maintainer
#4 lore raw

PATCH 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
index 958440eae27e..1cfd6f0ea679 100644
@@ -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

lib/crypto/Kconfig +1 -1
index 2d4a8f385e62..c2f4a2ea41d7 100644

Lines of this file are not shown. View the 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.

author maintainer
#5 lore raw

Re: [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.

#6 lore raw

Re: [PATCH crypto-next v2 2/3] crypto: x86_64/poly1305 - add faster implementations

In reply to Jason A. Donenfeld
Quoted 9 lines

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.

 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

author maintainer
#7 lore raw

Re: [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

#8 lore raw

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_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.

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.

author maintainer
#9 lore raw

PATCH v2 3/3 crypto: arm/arm64/mips/poly1305 - remove redundant non-reduction from emit

In reply to 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);

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
index abe3f2d587dc..ceec04ec2f40 100644
@@ -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
index 83a2338a8826..e97b092f56b8 100644
@@ -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
index b37d29cf5d0a..fc881b46d911 100644
@@ -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
Tested-by Reviewed-by on v2 3/3
#10 lore raw

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.

---

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
index abe3f2d587dc..ceec04ec2f40 100644
@@ -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
index 83a2338a8826..e97b092f56b8 100644
@@ -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
index b37d29cf5d0a..fc881b46d911 100644
@@ -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

#11 lore raw
In reply to Jason A. Donenfeld

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

author maintainer
#12 lore raw

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.

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

author maintainer
#13 lore raw
Quoted 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.

#14 lore raw
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.

[0] https://git.kernel.org/pub/scm/linux/kernel/git/herbert/cryptodev-2.6.git/commit/?id=11031c0d7d6e9bca0df233a8acfd6708d2b89470

author maintainer
#15 lore raw
Quoted 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.

#16 lore raw
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

author maintainer
#17 lore raw
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.

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.

maintainer
#18 lore raw
Quoted 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.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.

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

maintainer
#19 lore raw
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...

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
author maintainer
#20 lore raw

Hi 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

author maintainer
#21 lore raw
In reply to Eric Biggers

Hi 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