Received-SPF: pass (google.com: best guess record for domain of linux-crypto-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67;
Date:   Wed, 11 Dec 2019 11:06:16 -0800
From:   Eric Biggers <ebiggers@kernel.org>
To:     "Jason A. Donenfeld" <Jason@zx2c4.com>
Cc:     linux-crypto@vger.kernel.org
Subject: Re: [PATCH crypto-next v1] crypto: poly1305 - add new 32 and 64-bit
 generic versions
Message-ID: <20191211190615.GC82952@gmail.com>
References: <20191211170936.385572-1-Jason@zx2c4.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Disposition: inline
Content-Transfer-Encoding: 8bit
In-Reply-To: <20191211170936.385572-1-Jason@zx2c4.com>
User-Agent: Mutt/1.10.1 (2018-07-13)
Sender: linux-crypto-owner@vger.kernel.org
Precedence: bulk

On Wed, Dec 11, 2019 at 06:09:36PM +0100, Jason A. Donenfeld wrote:
> 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?

> 
> 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.
> 
> Signed-off-by: Jason A. Donenfeld <Jason@zx2c4.com>
> Cc: Eric Biggers <ebiggers@kernel.org>

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"

> diff --git a/include/crypto/internal/poly1305.h b/include/crypto/internal/poly1305.h
> index 479b0cab2a1a..6e275d3e5969 100644
> --- a/include/crypto/internal/poly1305.h
> +++ b/include/crypto/internal/poly1305.h
> @@ -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);

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.
	 */

> diff --git a/include/crypto/poly1305.h b/include/crypto/poly1305.h
> index 74c6e1cd73ee..dec2bd6b5aee 100644
> --- a/include/crypto/poly1305.h
> +++ b/include/crypto/poly1305.h
> @@ -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];
> +	};
>  };

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?

> diff --git a/lib/crypto/poly1305-donna32.c b/lib/crypto/poly1305-donna32.c
> new file mode 100644
> index 000000000000..39b3fde68dcf
> --- /dev/null
> +++ b/lib/crypto/poly1305-donna32.c
> @@ -0,0 +1,204 @@
> +// SPDX-License-Identifier: GPL-2.0 OR MIT
> +/*
> + * Copyright (C) 2015-2019 Jason A. Donenfeld <Jason@zx2c4.com>. 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;
> +	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