the-tree/crypto/nhpoly1305.c

0001 // SPDX-License-Identifier: GPL-2.0
0002 /*
0003  * NHPoly1305 - ε-almost-∆-universal hash function for Adiantum
0004  *
0005  * Copyright 2018 Google LLC
0006  */
0007
0008 /*
0009  * "NHPoly1305" is the main component of Adiantum hashing.
0010  * Specifically, it is the calculation
0011  *
0012  *  H_L ← Poly1305_{K_L}(NH_{K_N}(pad_{128}(L)))
0013  *
0014  * from the procedure in section 6.4 of the Adiantum paper [1].  It is an
0015  * ε-almost-∆-universal (ε-∆U) hash function for equal-length inputs over
0016  * Z/(2^{128}Z), where the "∆" operation is addition.  It hashes 1024-byte
0017  * chunks of the input with the NH hash function [2], reducing the input length
0018  * by 32x.  The resulting NH digests are evaluated as a polynomial in
0019  * GF(2^{130}-5), like in the Poly1305 MAC [3].  Note that the polynomial
0020  * evaluation by itself would suffice to achieve the ε-∆U property; NH is used
0021  * for performance since it's over twice as fast as Poly1305.
0022  *
0023  * This is *not* a cryptographic hash function; do not use it as such!
0024  *
0025  * [1] Adiantum: length-preserving encryption for entry-level processors
0026  *     (https://eprint.iacr.org/2018/720.pdf)
0027  * [2] UMAC: Fast and Secure Message Authentication
0028  *     (https://fastcrypto.org/umac/umac_proc.pdf)
0029  * [3] The Poly1305-AES message-authentication code
0030  *     (https://cr.yp.to/mac/poly1305-20050329.pdf)
0031  */
0032
0033 #include <asm/unaligned.h>
0034 #include <crypto/algapi.h>
0035 #include <crypto/internal/hash.h>
0036 #include <crypto/internal/poly1305.h>
0037 #include <crypto/nhpoly1305.h>
0038 #include <linux/crypto.h>
0039 #include <linux/kernel.h>
0040 #include <linux/module.h>
0041
0042 static void nh_generic(const u32 *key, const u8 *message, size_t message_len,
0043                __le64 hash[NH_NUM_PASSES])
0044 {
0045     u64 sums[4] = { 0, 0, 0, 0 };
0046
0047     BUILD_BUG_ON(NH_PAIR_STRIDE != 2);
0048     BUILD_BUG_ON(NH_NUM_PASSES != 4);
0049
0050     while (message_len) {
0051         u32 m0 = get_unaligned_le32(message + 0);
0052         u32 m1 = get_unaligned_le32(message + 4);
0053         u32 m2 = get_unaligned_le32(message + 8);
0054         u32 m3 = get_unaligned_le32(message + 12);
0055
0056         sums[0] += (u64)(u32)(m0 + key[ 0]) * (u32)(m2 + key[ 2]);
0057         sums[1] += (u64)(u32)(m0 + key[ 4]) * (u32)(m2 + key[ 6]);
0058         sums[2] += (u64)(u32)(m0 + key[ 8]) * (u32)(m2 + key[10]);
0059         sums[3] += (u64)(u32)(m0 + key[12]) * (u32)(m2 + key[14]);
0060         sums[0] += (u64)(u32)(m1 + key[ 1]) * (u32)(m3 + key[ 3]);
0061         sums[1] += (u64)(u32)(m1 + key[ 5]) * (u32)(m3 + key[ 7]);
0062         sums[2] += (u64)(u32)(m1 + key[ 9]) * (u32)(m3 + key[11]);
0063         sums[3] += (u64)(u32)(m1 + key[13]) * (u32)(m3 + key[15]);
0064         key += NH_MESSAGE_UNIT / sizeof(key[0]);
0065         message += NH_MESSAGE_UNIT;
0066         message_len -= NH_MESSAGE_UNIT;
0067     }
0068
0069     hash[0] = cpu_to_le64(sums[0]);
0070     hash[1] = cpu_to_le64(sums[1]);
0071     hash[2] = cpu_to_le64(sums[2]);
0072     hash[3] = cpu_to_le64(sums[3]);
0073 }
0074
0075 /* Pass the next NH hash value through Poly1305 */
0076 static void process_nh_hash_value(struct nhpoly1305_state *state,
0077                   const struct nhpoly1305_key *key)
0078 {
0079     BUILD_BUG_ON(NH_HASH_BYTES % POLY1305_BLOCK_SIZE != 0);
0080
0081     poly1305_core_blocks(&state->poly_state, &key->poly_key, state->nh_hash,
0082                  NH_HASH_BYTES / POLY1305_BLOCK_SIZE, 1);
0083 }
0084
0085 /*
0086  * Feed the next portion of the source data, as a whole number of 16-byte
0087  * "NH message units", through NH and Poly1305.  Each NH hash is taken over
0088  * 1024 bytes, except possibly the final one which is taken over a multiple of
0089  * 16 bytes up to 1024.  Also, in the case where data is passed in misaligned
0090  * chunks, we combine partial hashes; the end result is the same either way.
0091  */
0092 static void nhpoly1305_units(struct nhpoly1305_state *state,
0093                  const struct nhpoly1305_key *key,
0094                  const u8 *src, unsigned int srclen, nh_t nh_fn)
0095 {
0096     do {
0097         unsigned int bytes;
0098
0099         if (state->nh_remaining == 0) {
0100             /* Starting a new NH message */
0101             bytes = min_t(unsigned int, srclen, NH_MESSAGE_BYTES);
0102             nh_fn(key->nh_key, src, bytes, state->nh_hash);
0103             state->nh_remaining = NH_MESSAGE_BYTES - bytes;
0104         } else {
0105             /* Continuing a previous NH message */
0106             __le64 tmp_hash[NH_NUM_PASSES];
0107             unsigned int pos;
0108             int i;
0109
0110             pos = NH_MESSAGE_BYTES - state->nh_remaining;
0111             bytes = min(srclen, state->nh_remaining);
0112             nh_fn(&key->nh_key[pos / 4], src, bytes, tmp_hash);
0113             for (i = 0; i < NH_NUM_PASSES; i++)
0114                 le64_add_cpu(&state->nh_hash[i],
0115                          le64_to_cpu(tmp_hash[i]));
0116             state->nh_remaining -= bytes;
0117         }
0118         if (state->nh_remaining == 0)
0119             process_nh_hash_value(state, key);
0120         src += bytes;
0121         srclen -= bytes;
0122     } while (srclen);
0123 }
0124
0125 int crypto_nhpoly1305_setkey(struct crypto_shash *tfm,
0126                  const u8 *key, unsigned int keylen)
0127 {
0128     struct nhpoly1305_key *ctx = crypto_shash_ctx(tfm);
0129     int i;
0130
0131     if (keylen != NHPOLY1305_KEY_SIZE)
0132         return -EINVAL;
0133
0134     poly1305_core_setkey(&ctx->poly_key, key);
0135     key += POLY1305_BLOCK_SIZE;
0136
0137     for (i = 0; i < NH_KEY_WORDS; i++)
0138         ctx->nh_key[i] = get_unaligned_le32(key + i * sizeof(u32));
0139
0140     return 0;
0141 }
0142 EXPORT_SYMBOL(crypto_nhpoly1305_setkey);
0143
0144 int crypto_nhpoly1305_init(struct shash_desc *desc)
0145 {
0146     struct nhpoly1305_state *state = shash_desc_ctx(desc);
0147
0148     poly1305_core_init(&state->poly_state);
0149     state->buflen = 0;
0150     state->nh_remaining = 0;
0151     return 0;
0152 }
0153 EXPORT_SYMBOL(crypto_nhpoly1305_init);
0154
0155 int crypto_nhpoly1305_update_helper(struct shash_desc *desc,
0156                     const u8 *src, unsigned int srclen,
0157                     nh_t nh_fn)
0158 {
0159     struct nhpoly1305_state *state = shash_desc_ctx(desc);
0160     const struct nhpoly1305_key *key = crypto_shash_ctx(desc->tfm);
0161     unsigned int bytes;
0162
0163     if (state->buflen) {
0164         bytes = min(srclen, (int)NH_MESSAGE_UNIT - state->buflen);
0165         memcpy(&state->buffer[state->buflen], src, bytes);
0166         state->buflen += bytes;
0167         if (state->buflen < NH_MESSAGE_UNIT)
0168             return 0;
0169         nhpoly1305_units(state, key, state->buffer, NH_MESSAGE_UNIT,
0170                  nh_fn);
0171         state->buflen = 0;
0172         src += bytes;
0173         srclen -= bytes;
0174     }
0175
0176     if (srclen >= NH_MESSAGE_UNIT) {
0177         bytes = round_down(srclen, NH_MESSAGE_UNIT);
0178         nhpoly1305_units(state, key, src, bytes, nh_fn);
0179         src += bytes;
0180         srclen -= bytes;
0181     }
0182
0183     if (srclen) {
0184         memcpy(state->buffer, src, srclen);
0185         state->buflen = srclen;
0186     }
0187     return 0;
0188 }
0189 EXPORT_SYMBOL(crypto_nhpoly1305_update_helper);
0190
0191 int crypto_nhpoly1305_update(struct shash_desc *desc,
0192                  const u8 *src, unsigned int srclen)
0193 {
0194     return crypto_nhpoly1305_update_helper(desc, src, srclen, nh_generic);
0195 }
0196 EXPORT_SYMBOL(crypto_nhpoly1305_update);
0197
0198 int crypto_nhpoly1305_final_helper(struct shash_desc *desc, u8 *dst, nh_t nh_fn)
0199 {
0200     struct nhpoly1305_state *state = shash_desc_ctx(desc);
0201     const struct nhpoly1305_key *key = crypto_shash_ctx(desc->tfm);
0202
0203     if (state->buflen) {
0204         memset(&state->buffer[state->buflen], 0,
0205                NH_MESSAGE_UNIT - state->buflen);
0206         nhpoly1305_units(state, key, state->buffer, NH_MESSAGE_UNIT,
0207                  nh_fn);
0208     }
0209
0210     if (state->nh_remaining)
0211         process_nh_hash_value(state, key);
0212
0213     poly1305_core_emit(&state->poly_state, NULL, dst);
0214     return 0;
0215 }
0216 EXPORT_SYMBOL(crypto_nhpoly1305_final_helper);
0217
0218 int crypto_nhpoly1305_final(struct shash_desc *desc, u8 *dst)
0219 {
0220     return crypto_nhpoly1305_final_helper(desc, dst, nh_generic);
0221 }
0222 EXPORT_SYMBOL(crypto_nhpoly1305_final);
0223
0224 static struct shash_alg nhpoly1305_alg = {
0225     .base.cra_name      = "nhpoly1305",
0226     .base.cra_driver_name   = "nhpoly1305-generic",
0227     .base.cra_priority  = 100,
0228     .base.cra_ctxsize   = sizeof(struct nhpoly1305_key),
0229     .base.cra_module    = THIS_MODULE,
0230     .digestsize     = POLY1305_DIGEST_SIZE,
0231     .init           = crypto_nhpoly1305_init,
0232     .update         = crypto_nhpoly1305_update,
0233     .final          = crypto_nhpoly1305_final,
0234     .setkey         = crypto_nhpoly1305_setkey,
0235     .descsize       = sizeof(struct nhpoly1305_state),
0236 };
0237
0238 static int __init nhpoly1305_mod_init(void)
0239 {
0240     return crypto_register_shash(&nhpoly1305_alg);
0241 }
0242
0243 static void __exit nhpoly1305_mod_exit(void)
0244 {
0245     crypto_unregister_shash(&nhpoly1305_alg);
0246 }
0247
0248 subsys_initcall(nhpoly1305_mod_init);
0249 module_exit(nhpoly1305_mod_exit);
0250
0251 MODULE_DESCRIPTION("NHPoly1305 ε-almost-∆-universal hash function");
0252 MODULE_LICENSE("GPL v2");
0253 MODULE_AUTHOR("Eric Biggers <ebiggers@google.com>");
0254 MODULE_ALIAS_CRYPTO("nhpoly1305");
0255 MODULE_ALIAS_CRYPTO("nhpoly1305-generic");