[PATCH 2/9] lib/crypto: polyval: Add POLYVAL library

[Ard Biesheuvel]

Hi,

On Mon, 10 Nov 2025 at 00:49, Eric Biggers <ebiggers at kernel.org> wrote:
>
> Add support for POLYVAL to lib/crypto/.
>
> This will replace the polyval crypto_shash algorithm and its use in the
> hctr2 template, simplifying the code and reducing overhead.
>
> Specifically, this commit introduces the POLYVAL library API and a
> generic implementation of it.  Later commits will migrate the existing
> architecture-optimized implementations of POLYVAL into lib/crypto/ and
> add a KUnit test suite.
>
> I've also rewritten the generic implementation completely, using a more
> modern approach instead of the traditional table-based approach.  It's
> now constant-time, requires no precomputation or dynamic memory
> allocations, decreases the per-key memory usage from 4096 bytes to 16
> bytes, and is faster than the old polyval-generic even on bulk data
> reusing the same key (at least on x86_64, where I measured 15% faster).
> We should do this for GHASH too, but for now just do it for POLYVAL.
>

Very nice.

GHASH might suffer on 32-bit, I suppose, but taking this approach at
least on 64-bit also for GHASH would be a huge improvement.

I had a stab at replacing the int128 arithmetic with
__builtin_bitreverse64(), but it seems to make little difference (and
GCC does not support it [yet]). I've tried both arm64 and x86, and the
perf delta (using your kunit benchmark) is negligible in either case.
(FYI)



> Signed-off-by: Eric Biggers <ebiggers at kernel.org>
> ---
>  include/crypto/polyval.h | 171 +++++++++++++++++++++-
>  lib/crypto/Kconfig       |  10 ++
>  lib/crypto/Makefile      |   8 +
>  lib/crypto/polyval.c     | 307 +++++++++++++++++++++++++++++++++++++++
>  4 files changed, 493 insertions(+), 3 deletions(-)
>  create mode 100644 lib/crypto/polyval.c
>

Reviewed-by: Ard Biesheuvel <ardb at kernel.org>
Tested-by: Ard Biesheuvel <ardb at kernel.org>