crypto/polyval-generic.c

   1 // SPDX-License-Identifier: GPL-2.0-only
   2 /*
   3  * POLYVAL: hash function for HCTR2.
   4  *
   5  * Copyright (c) 2007 Nokia Siemens Networks - Mikko Herranen <mh1@iki.fi>
   6  * Copyright (c) 2009 Intel Corp.
   7  *   Author: Huang Ying <ying.huang@intel.com>
   8  * Copyright 2021 Google LLC
   9  */
  10
  11 /*
  12  * Code based on crypto/ghash-generic.c
  13  *
  14  * POLYVAL is a keyed hash function similar to GHASH. POLYVAL uses a different
  15  * modulus for finite field multiplication which makes hardware accelerated
  16  * implementations on little-endian machines faster. POLYVAL is used in the
  17  * kernel to implement HCTR2, but was originally specified for AES-GCM-SIV
  18  * (RFC 8452).
  19  *
  20  * For more information see:
  21  * Length-preserving encryption with HCTR2:
  22  *   https://eprint.iacr.org/2021/1441.pdf
  23  * AES-GCM-SIV: Nonce Misuse-Resistant Authenticated Encryption:
  24  *   https://datatracker.ietf.org/doc/html/rfc8452
  25  *
  26  * Like GHASH, POLYVAL is not a cryptographic hash function and should
  27  * not be used outside of crypto modes explicitly designed to use POLYVAL.
  28  *
  29  * This implementation uses a convenient trick involving the GHASH and POLYVAL
  30  * fields. This trick allows multiplication in the POLYVAL field to be
  31  * implemented by using multiplication in the GHASH field as a subroutine. An
  32  * element of the POLYVAL field can be converted to an element of the GHASH
  33  * field by computing x*REVERSE(a), where REVERSE reverses the byte-ordering of
  34  * a. Similarly, an element of the GHASH field can be converted back to the
  35  * POLYVAL field by computing REVERSE(x^{-1}*a). For more information, see:
  36  * https://datatracker.ietf.org/doc/html/rfc8452#appendix-A
  37  *
  38  * By using this trick, we do not need to implement the POLYVAL field for the
  39  * generic implementation.
  40  *
  41  * Warning: this generic implementation is not intended to be used in practice
  42  * and is not constant time. For practical use, a hardware accelerated
  43  * implementation of POLYVAL should be used instead.
  44  *
  45  */
  46
  47 #include <linux/unaligned.h>
  48 #include <crypto/algapi.h>
  49 #include <crypto/gf128mul.h>
  50 #include <crypto/polyval.h>
  51 #include <crypto/internal/hash.h>
  52 #include <linux/crypto.h>
  53 #include <linux/init.h>
  54 #include <linux/kernel.h>
  55 #include <linux/module.h>
  56
  57 struct polyval_tfm_ctx {
  58         struct gf128mul_4k *gf128;
  59 };
  60
  61 struct polyval_desc_ctx {
  62         union {
  63                 u8 buffer[POLYVAL_BLOCK_SIZE];
  64                 be128 buffer128;
  65         };
  66         u32 bytes;
  67 };
  68
  69 static void copy_and_reverse(u8 dst[POLYVAL_BLOCK_SIZE],
  70                              const u8 src[POLYVAL_BLOCK_SIZE])
  71 {
  72         u64 a = get_unaligned((const u64 *)&src[0]);
  73         u64 b = get_unaligned((const u64 *)&src[8]);
  74
  75         put_unaligned(swab64(a), (u64 *)&dst[8]);
  76         put_unaligned(swab64(b), (u64 *)&dst[0]);
  77 }
  78
  79 /*
  80  * Performs multiplication in the POLYVAL field using the GHASH field as a
  81  * subroutine.  This function is used as a fallback for hardware accelerated
  82  * implementations when simd registers are unavailable.
  83  *
  84  * Note: This function is not used for polyval-generic, instead we use the 4k
  85  * lookup table implementation for finite field multiplication.
  86  */
  87 void polyval_mul_non4k(u8 *op1, const u8 *op2)
  88 {
  89         be128 a, b;
  90
  91         // Assume one argument is in Montgomery form and one is not.
  92         copy_and_reverse((u8 *)&a, op1);
  93         copy_and_reverse((u8 *)&b, op2);
  94         gf128mul_x_lle(&a, &a);
  95         gf128mul_lle(&a, &b);
  96         copy_and_reverse(op1, (u8 *)&a);
  97 }
  98 EXPORT_SYMBOL_GPL(polyval_mul_non4k);
  99
 100 /*
 101  * Perform a POLYVAL update using non4k multiplication.  This function is used
 102  * as a fallback for hardware accelerated implementations when simd registers
 103  * are unavailable.
 104  *
 105  * Note: This function is not used for polyval-generic, instead we use the 4k
 106  * lookup table implementation of finite field multiplication.
 107  */
 108 void polyval_update_non4k(const u8 *key, const u8 *in,
 109                           size_t nblocks, u8 *accumulator)
 110 {
 111         while (nblocks--) {
 112                 crypto_xor(accumulator, in, POLYVAL_BLOCK_SIZE);
 113                 polyval_mul_non4k(accumulator, key);
 114                 in += POLYVAL_BLOCK_SIZE;
 115         }
 116 }
 117 EXPORT_SYMBOL_GPL(polyval_update_non4k);
 118
 119 static int polyval_setkey(struct crypto_shash *tfm,
 120                           const u8 *key, unsigned int keylen)
 121 {
 122         struct polyval_tfm_ctx *ctx = crypto_shash_ctx(tfm);
 123         be128 k;
 124
 125         if (keylen != POLYVAL_BLOCK_SIZE)
 126                 return -EINVAL;
 127
 128         gf128mul_free_4k(ctx->gf128);
 129
 130         BUILD_BUG_ON(sizeof(k) != POLYVAL_BLOCK_SIZE);
 131         copy_and_reverse((u8 *)&k, key);
 132         gf128mul_x_lle(&k, &k);
 133
 134         ctx->gf128 = gf128mul_init_4k_lle(&k);
 135         memzero_explicit(&k, POLYVAL_BLOCK_SIZE);
 136
 137         if (!ctx->gf128)
 138                 return -ENOMEM;
 139
 140         return 0;
 141 }
 142
 143 static int polyval_init(struct shash_desc *desc)
 144 {
 145         struct polyval_desc_ctx *dctx = shash_desc_ctx(desc);
 146
 147         memset(dctx, 0, sizeof(*dctx));
 148
 149         return 0;
 150 }
 151
 152 static int polyval_update(struct shash_desc *desc,
 153                          const u8 *src, unsigned int srclen)
 154 {
 155         struct polyval_desc_ctx *dctx = shash_desc_ctx(desc);
 156         const struct polyval_tfm_ctx *ctx = crypto_shash_ctx(desc->tfm);
 157         u8 *pos;
 158         u8 tmp[POLYVAL_BLOCK_SIZE];
 159         int n;
 160
 161         if (dctx->bytes) {
 162                 n = min(srclen, dctx->bytes);
 163                 pos = dctx->buffer + dctx->bytes - 1;
 164
 165                 dctx->bytes -= n;
 166                 srclen -= n;
 167
 168                 while (n--)
 169                         *pos-- ^= *src++;
 170
 171                 if (!dctx->bytes)
 172                         gf128mul_4k_lle(&dctx->buffer128, ctx->gf128);
 173         }
 174
 175         while (srclen >= POLYVAL_BLOCK_SIZE) {
 176                 copy_and_reverse(tmp, src);
 177                 crypto_xor(dctx->buffer, tmp, POLYVAL_BLOCK_SIZE);
 178                 gf128mul_4k_lle(&dctx->buffer128, ctx->gf128);
 179                 src += POLYVAL_BLOCK_SIZE;
 180                 srclen -= POLYVAL_BLOCK_SIZE;
 181         }
 182
 183         if (srclen) {
 184                 dctx->bytes = POLYVAL_BLOCK_SIZE - srclen;
 185                 pos = dctx->buffer + POLYVAL_BLOCK_SIZE - 1;
 186                 while (srclen--)
 187                         *pos-- ^= *src++;
 188         }
 189
 190         return 0;
 191 }
 192
 193 static int polyval_final(struct shash_desc *desc, u8 *dst)
 194 {
 195         struct polyval_desc_ctx *dctx = shash_desc_ctx(desc);
 196         const struct polyval_tfm_ctx *ctx = crypto_shash_ctx(desc->tfm);
 197
 198         if (dctx->bytes)
 199                 gf128mul_4k_lle(&dctx->buffer128, ctx->gf128);
 200         copy_and_reverse(dst, dctx->buffer);
 201         return 0;
 202 }
 203
 204 static void polyval_exit_tfm(struct crypto_tfm *tfm)
 205 {
 206         struct polyval_tfm_ctx *ctx = crypto_tfm_ctx(tfm);
 207
 208         gf128mul_free_4k(ctx->gf128);
 209 }
 210
 211 static struct shash_alg polyval_alg = {
 212         .digestsize     = POLYVAL_DIGEST_SIZE,
 213         .init           = polyval_init,
 214         .update         = polyval_update,
 215         .final          = polyval_final,
 216         .setkey         = polyval_setkey,
 217         .descsize       = sizeof(struct polyval_desc_ctx),
 218         .base           = {
 219                 .cra_name               = "polyval",
 220                 .cra_driver_name        = "polyval-generic",
 221                 .cra_priority           = 100,
 222                 .cra_blocksize          = POLYVAL_BLOCK_SIZE,
 223                 .cra_ctxsize            = sizeof(struct polyval_tfm_ctx),
 224                 .cra_module             = THIS_MODULE,
 225                 .cra_exit               = polyval_exit_tfm,
 226         },
 227 };
 228
 229 static int __init polyval_mod_init(void)
 230 {
 231         return crypto_register_shash(&polyval_alg);
 232 }
 233
 234 static void __exit polyval_mod_exit(void)
 235 {
 236         crypto_unregister_shash(&polyval_alg);
 237 }
 238
 239 subsys_initcall(polyval_mod_init);
 240 module_exit(polyval_mod_exit);
 241
 242 MODULE_LICENSE("GPL");
 243 MODULE_DESCRIPTION("POLYVAL hash function");
 244 MODULE_ALIAS_CRYPTO("polyval");
 245 MODULE_ALIAS_CRYPTO("polyval-generic");