256 lines · c
1// SPDX-License-Identifier: GPL-2.02/*3 * NHPoly1305 - ε-almost-∆-universal hash function for Adiantum4 *5 * Copyright 2018 Google LLC6 */7 8/*9 * "NHPoly1305" is the main component of Adiantum hashing.10 * Specifically, it is the calculation11 *12 * H_L ← Poly1305_{K_L}(NH_{K_N}(pad_{128}(L)))13 *14 * from the procedure in section 6.4 of the Adiantum paper [1]. It is an15 * ε-almost-∆-universal (ε-∆U) hash function for equal-length inputs over16 * Z/(2^{128}Z), where the "∆" operation is addition. It hashes 1024-byte17 * chunks of the input with the NH hash function [2], reducing the input length18 * by 32x. The resulting NH digests are evaluated as a polynomial in19 * GF(2^{130}-5), like in the Poly1305 MAC [3]. Note that the polynomial20 * evaluation by itself would suffice to achieve the ε-∆U property; NH is used21 * for performance since it's over twice as fast as Poly1305.22 *23 * This is *not* a cryptographic hash function; do not use it as such!24 *25 * [1] Adiantum: length-preserving encryption for entry-level processors26 * (https://eprint.iacr.org/2018/720.pdf)27 * [2] UMAC: Fast and Secure Message Authentication28 * (https://fastcrypto.org/umac/umac_proc.pdf)29 * [3] The Poly1305-AES message-authentication code30 * (https://cr.yp.to/mac/poly1305-20050329.pdf)31 */32 33#include <linux/unaligned.h>34#include <crypto/algapi.h>35#include <crypto/internal/hash.h>36#include <crypto/internal/poly1305.h>37#include <crypto/nhpoly1305.h>38#include <linux/crypto.h>39#include <linux/kernel.h>40#include <linux/module.h>41 42static void nh_generic(const u32 *key, const u8 *message, size_t message_len,43 __le64 hash[NH_NUM_PASSES])44{45 u64 sums[4] = { 0, 0, 0, 0 };46 47 BUILD_BUG_ON(NH_PAIR_STRIDE != 2);48 BUILD_BUG_ON(NH_NUM_PASSES != 4);49 50 while (message_len) {51 u32 m0 = get_unaligned_le32(message + 0);52 u32 m1 = get_unaligned_le32(message + 4);53 u32 m2 = get_unaligned_le32(message + 8);54 u32 m3 = get_unaligned_le32(message + 12);55 56 sums[0] += (u64)(u32)(m0 + key[ 0]) * (u32)(m2 + key[ 2]);57 sums[1] += (u64)(u32)(m0 + key[ 4]) * (u32)(m2 + key[ 6]);58 sums[2] += (u64)(u32)(m0 + key[ 8]) * (u32)(m2 + key[10]);59 sums[3] += (u64)(u32)(m0 + key[12]) * (u32)(m2 + key[14]);60 sums[0] += (u64)(u32)(m1 + key[ 1]) * (u32)(m3 + key[ 3]);61 sums[1] += (u64)(u32)(m1 + key[ 5]) * (u32)(m3 + key[ 7]);62 sums[2] += (u64)(u32)(m1 + key[ 9]) * (u32)(m3 + key[11]);63 sums[3] += (u64)(u32)(m1 + key[13]) * (u32)(m3 + key[15]);64 key += NH_MESSAGE_UNIT / sizeof(key[0]);65 message += NH_MESSAGE_UNIT;66 message_len -= NH_MESSAGE_UNIT;67 }68 69 hash[0] = cpu_to_le64(sums[0]);70 hash[1] = cpu_to_le64(sums[1]);71 hash[2] = cpu_to_le64(sums[2]);72 hash[3] = cpu_to_le64(sums[3]);73}74 75/* Pass the next NH hash value through Poly1305 */76static void process_nh_hash_value(struct nhpoly1305_state *state,77 const struct nhpoly1305_key *key)78{79 BUILD_BUG_ON(NH_HASH_BYTES % POLY1305_BLOCK_SIZE != 0);80 81 poly1305_core_blocks(&state->poly_state, &key->poly_key, state->nh_hash,82 NH_HASH_BYTES / POLY1305_BLOCK_SIZE, 1);83}84 85/*86 * Feed the next portion of the source data, as a whole number of 16-byte87 * "NH message units", through NH and Poly1305. Each NH hash is taken over88 * 1024 bytes, except possibly the final one which is taken over a multiple of89 * 16 bytes up to 1024. Also, in the case where data is passed in misaligned90 * chunks, we combine partial hashes; the end result is the same either way.91 */92static void nhpoly1305_units(struct nhpoly1305_state *state,93 const struct nhpoly1305_key *key,94 const u8 *src, unsigned int srclen, nh_t nh_fn)95{96 do {97 unsigned int bytes;98 99 if (state->nh_remaining == 0) {100 /* Starting a new NH message */101 bytes = min_t(unsigned int, srclen, NH_MESSAGE_BYTES);102 nh_fn(key->nh_key, src, bytes, state->nh_hash);103 state->nh_remaining = NH_MESSAGE_BYTES - bytes;104 } else {105 /* Continuing a previous NH message */106 __le64 tmp_hash[NH_NUM_PASSES];107 unsigned int pos;108 int i;109 110 pos = NH_MESSAGE_BYTES - state->nh_remaining;111 bytes = min(srclen, state->nh_remaining);112 nh_fn(&key->nh_key[pos / 4], src, bytes, tmp_hash);113 for (i = 0; i < NH_NUM_PASSES; i++)114 le64_add_cpu(&state->nh_hash[i],115 le64_to_cpu(tmp_hash[i]));116 state->nh_remaining -= bytes;117 }118 if (state->nh_remaining == 0)119 process_nh_hash_value(state, key);120 src += bytes;121 srclen -= bytes;122 } while (srclen);123}124 125int crypto_nhpoly1305_setkey(struct crypto_shash *tfm,126 const u8 *key, unsigned int keylen)127{128 struct nhpoly1305_key *ctx = crypto_shash_ctx(tfm);129 int i;130 131 if (keylen != NHPOLY1305_KEY_SIZE)132 return -EINVAL;133 134 poly1305_core_setkey(&ctx->poly_key, key);135 key += POLY1305_BLOCK_SIZE;136 137 for (i = 0; i < NH_KEY_WORDS; i++)138 ctx->nh_key[i] = get_unaligned_le32(key + i * sizeof(u32));139 140 return 0;141}142EXPORT_SYMBOL(crypto_nhpoly1305_setkey);143 144int crypto_nhpoly1305_init(struct shash_desc *desc)145{146 struct nhpoly1305_state *state = shash_desc_ctx(desc);147 148 poly1305_core_init(&state->poly_state);149 state->buflen = 0;150 state->nh_remaining = 0;151 return 0;152}153EXPORT_SYMBOL(crypto_nhpoly1305_init);154 155int crypto_nhpoly1305_update_helper(struct shash_desc *desc,156 const u8 *src, unsigned int srclen,157 nh_t nh_fn)158{159 struct nhpoly1305_state *state = shash_desc_ctx(desc);160 const struct nhpoly1305_key *key = crypto_shash_ctx(desc->tfm);161 unsigned int bytes;162 163 if (state->buflen) {164 bytes = min(srclen, (int)NH_MESSAGE_UNIT - state->buflen);165 memcpy(&state->buffer[state->buflen], src, bytes);166 state->buflen += bytes;167 if (state->buflen < NH_MESSAGE_UNIT)168 return 0;169 nhpoly1305_units(state, key, state->buffer, NH_MESSAGE_UNIT,170 nh_fn);171 state->buflen = 0;172 src += bytes;173 srclen -= bytes;174 }175 176 if (srclen >= NH_MESSAGE_UNIT) {177 bytes = round_down(srclen, NH_MESSAGE_UNIT);178 nhpoly1305_units(state, key, src, bytes, nh_fn);179 src += bytes;180 srclen -= bytes;181 }182 183 if (srclen) {184 memcpy(state->buffer, src, srclen);185 state->buflen = srclen;186 }187 return 0;188}189EXPORT_SYMBOL(crypto_nhpoly1305_update_helper);190 191int crypto_nhpoly1305_update(struct shash_desc *desc,192 const u8 *src, unsigned int srclen)193{194 return crypto_nhpoly1305_update_helper(desc, src, srclen, nh_generic);195}196EXPORT_SYMBOL(crypto_nhpoly1305_update);197 198int crypto_nhpoly1305_final_helper(struct shash_desc *desc, u8 *dst, nh_t nh_fn)199{200 struct nhpoly1305_state *state = shash_desc_ctx(desc);201 const struct nhpoly1305_key *key = crypto_shash_ctx(desc->tfm);202 203 if (state->buflen) {204 memset(&state->buffer[state->buflen], 0,205 NH_MESSAGE_UNIT - state->buflen);206 nhpoly1305_units(state, key, state->buffer, NH_MESSAGE_UNIT,207 nh_fn);208 }209 210 if (state->nh_remaining)211 process_nh_hash_value(state, key);212 213 poly1305_core_emit(&state->poly_state, NULL, dst);214 return 0;215}216EXPORT_SYMBOL(crypto_nhpoly1305_final_helper);217 218int crypto_nhpoly1305_final(struct shash_desc *desc, u8 *dst)219{220 return crypto_nhpoly1305_final_helper(desc, dst, nh_generic);221}222EXPORT_SYMBOL(crypto_nhpoly1305_final);223 224static struct shash_alg nhpoly1305_alg = {225 .base.cra_name = "nhpoly1305",226 .base.cra_driver_name = "nhpoly1305-generic",227 .base.cra_priority = 100,228 .base.cra_ctxsize = sizeof(struct nhpoly1305_key),229 .base.cra_module = THIS_MODULE,230 .digestsize = POLY1305_DIGEST_SIZE,231 .init = crypto_nhpoly1305_init,232 .update = crypto_nhpoly1305_update,233 .final = crypto_nhpoly1305_final,234 .setkey = crypto_nhpoly1305_setkey,235 .descsize = sizeof(struct nhpoly1305_state),236};237 238static int __init nhpoly1305_mod_init(void)239{240 return crypto_register_shash(&nhpoly1305_alg);241}242 243static void __exit nhpoly1305_mod_exit(void)244{245 crypto_unregister_shash(&nhpoly1305_alg);246}247 248subsys_initcall(nhpoly1305_mod_init);249module_exit(nhpoly1305_mod_exit);250 251MODULE_DESCRIPTION("NHPoly1305 ε-almost-∆-universal hash function");252MODULE_LICENSE("GPL v2");253MODULE_AUTHOR("Eric Biggers <ebiggers@google.com>");254MODULE_ALIAS_CRYPTO("nhpoly1305");255MODULE_ALIAS_CRYPTO("nhpoly1305-generic");256