1 | // SPDX-License-Identifier: GPL-2.0 |
---|---|

2 | /* |

3 | * NHPoly1305 - ε-almost-∆-universal hash function for Adiantum |

4 | * |

5 | * Copyright 2018 Google LLC |

6 | */ |

7 | |

8 | /* |

9 | * "NHPoly1305" is the main component of Adiantum hashing. |

10 | * Specifically, it is the calculation |

11 | * |

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 an |

15 | * ε-almost-∆-universal (ε-∆U) hash function for equal-length inputs over |

16 | * Z/(2^{128}Z), where the "∆" operation is addition. It hashes 1024-byte |

17 | * chunks of the input with the NH hash function [2], reducing the input length |

18 | * by 32x. The resulting NH digests are evaluated as a polynomial in |

19 | * GF(2^{130}-5), like in the Poly1305 MAC [3]. Note that the polynomial |

20 | * evaluation by itself would suffice to achieve the ε-∆U property; NH is used |

21 | * 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 processors |

26 | * (https://eprint.iacr.org/2018/720.pdf) |

27 | * [2] UMAC: Fast and Secure Message Authentication |

28 | * (https://fastcrypto.org/umac/umac_proc.pdf) |

29 | * [3] The Poly1305-AES message-authentication code |

30 | * (https://cr.yp.to/mac/poly1305-20050329.pdf) |

31 | */ |

32 | |

33 | #include <asm/unaligned.h> |

34 | #include <crypto/algapi.h> |

35 | #include <crypto/internal/hash.h> |

36 | #include <crypto/nhpoly1305.h> |

37 | #include <linux/crypto.h> |

38 | #include <linux/kernel.h> |

39 | #include <linux/module.h> |

40 | |

41 | static void nh_generic(const u32 *key, const u8 *message, size_t message_len, |

42 | __le64 hash[NH_NUM_PASSES]) |

43 | { |

44 | u64 sums[4] = { 0, 0, 0, 0 }; |

45 | |

46 | BUILD_BUG_ON(NH_PAIR_STRIDE != 2); |

47 | BUILD_BUG_ON(NH_NUM_PASSES != 4); |

48 | |

49 | while (message_len) { |

50 | u32 m0 = get_unaligned_le32(message + 0); |

51 | u32 m1 = get_unaligned_le32(message + 4); |

52 | u32 m2 = get_unaligned_le32(message + 8); |

53 | u32 m3 = get_unaligned_le32(message + 12); |

54 | |

55 | sums[0] += (u64)(u32)(m0 + key[ 0]) * (u32)(m2 + key[ 2]); |

56 | sums[1] += (u64)(u32)(m0 + key[ 4]) * (u32)(m2 + key[ 6]); |

57 | sums[2] += (u64)(u32)(m0 + key[ 8]) * (u32)(m2 + key[10]); |

58 | sums[3] += (u64)(u32)(m0 + key[12]) * (u32)(m2 + key[14]); |

59 | sums[0] += (u64)(u32)(m1 + key[ 1]) * (u32)(m3 + key[ 3]); |

60 | sums[1] += (u64)(u32)(m1 + key[ 5]) * (u32)(m3 + key[ 7]); |

61 | sums[2] += (u64)(u32)(m1 + key[ 9]) * (u32)(m3 + key[11]); |

62 | sums[3] += (u64)(u32)(m1 + key[13]) * (u32)(m3 + key[15]); |

63 | key += NH_MESSAGE_UNIT / sizeof(key[0]); |

64 | message += NH_MESSAGE_UNIT; |

65 | message_len -= NH_MESSAGE_UNIT; |

66 | } |

67 | |

68 | hash[0] = cpu_to_le64(sums[0]); |

69 | hash[1] = cpu_to_le64(sums[1]); |

70 | hash[2] = cpu_to_le64(sums[2]); |

71 | hash[3] = cpu_to_le64(sums[3]); |

72 | } |

73 | |

74 | /* Pass the next NH hash value through Poly1305 */ |

75 | static void process_nh_hash_value(struct nhpoly1305_state *state, |

76 | const struct nhpoly1305_key *key) |

77 | { |

78 | BUILD_BUG_ON(NH_HASH_BYTES % POLY1305_BLOCK_SIZE != 0); |

79 | |

80 | poly1305_core_blocks(&state->poly_state, &key->poly_key, state->nh_hash, |

81 | NH_HASH_BYTES / POLY1305_BLOCK_SIZE); |

82 | } |

83 | |

84 | /* |

85 | * Feed the next portion of the source data, as a whole number of 16-byte |

86 | * "NH message units", through NH and Poly1305. Each NH hash is taken over |

87 | * 1024 bytes, except possibly the final one which is taken over a multiple of |

88 | * 16 bytes up to 1024. Also, in the case where data is passed in misaligned |

89 | * chunks, we combine partial hashes; the end result is the same either way. |

90 | */ |

91 | static void nhpoly1305_units(struct nhpoly1305_state *state, |

92 | const struct nhpoly1305_key *key, |

93 | const u8 *src, unsigned int srclen, nh_t nh_fn) |

94 | { |

95 | do { |

96 | unsigned int bytes; |

97 | |

98 | if (state->nh_remaining == 0) { |

99 | /* Starting a new NH message */ |

100 | bytes = min_t(unsigned int, srclen, NH_MESSAGE_BYTES); |

101 | nh_fn(key->nh_key, src, bytes, state->nh_hash); |

102 | state->nh_remaining = NH_MESSAGE_BYTES - bytes; |

103 | } else { |

104 | /* Continuing a previous NH message */ |

105 | __le64 tmp_hash[NH_NUM_PASSES]; |

106 | unsigned int pos; |

107 | int i; |

108 | |

109 | pos = NH_MESSAGE_BYTES - state->nh_remaining; |

110 | bytes = min(srclen, state->nh_remaining); |

111 | nh_fn(&key->nh_key[pos / 4], src, bytes, tmp_hash); |

112 | for (i = 0; i < NH_NUM_PASSES; i++) |

113 | le64_add_cpu(&state->nh_hash[i], |

114 | le64_to_cpu(tmp_hash[i])); |

115 | state->nh_remaining -= bytes; |

116 | } |

117 | if (state->nh_remaining == 0) |

118 | process_nh_hash_value(state, key); |

119 | src += bytes; |

120 | srclen -= bytes; |

121 | } while (srclen); |

122 | } |

123 | |

124 | int crypto_nhpoly1305_setkey(struct crypto_shash *tfm, |

125 | const u8 *key, unsigned int keylen) |

126 | { |

127 | struct nhpoly1305_key *ctx = crypto_shash_ctx(tfm); |

128 | int i; |

129 | |

130 | if (keylen != NHPOLY1305_KEY_SIZE) |

131 | return -EINVAL; |

132 | |

133 | poly1305_core_setkey(&ctx->poly_key, key); |

134 | key += POLY1305_BLOCK_SIZE; |

135 | |

136 | for (i = 0; i < NH_KEY_WORDS; i++) |

137 | ctx->nh_key[i] = get_unaligned_le32(key + i * sizeof(u32)); |

138 | |

139 | return 0; |

140 | } |

141 | EXPORT_SYMBOL(crypto_nhpoly1305_setkey); |

142 | |

143 | int crypto_nhpoly1305_init(struct shash_desc *desc) |

144 | { |

145 | struct nhpoly1305_state *state = shash_desc_ctx(desc); |

146 | |

147 | poly1305_core_init(&state->poly_state); |

148 | state->buflen = 0; |

149 | state->nh_remaining = 0; |

150 | return 0; |

151 | } |

152 | EXPORT_SYMBOL(crypto_nhpoly1305_init); |

153 | |

154 | int crypto_nhpoly1305_update_helper(struct shash_desc *desc, |

155 | const u8 *src, unsigned int srclen, |

156 | nh_t nh_fn) |

157 | { |

158 | struct nhpoly1305_state *state = shash_desc_ctx(desc); |

159 | const struct nhpoly1305_key *key = crypto_shash_ctx(desc->tfm); |

160 | unsigned int bytes; |

161 | |

162 | if (state->buflen) { |

163 | bytes = min(srclen, (int)NH_MESSAGE_UNIT - state->buflen); |

164 | memcpy(&state->buffer[state->buflen], src, bytes); |

165 | state->buflen += bytes; |

166 | if (state->buflen < NH_MESSAGE_UNIT) |

167 | return 0; |

168 | nhpoly1305_units(state, key, state->buffer, NH_MESSAGE_UNIT, |

169 | nh_fn); |

170 | state->buflen = 0; |

171 | src += bytes; |

172 | srclen -= bytes; |

173 | } |

174 | |

175 | if (srclen >= NH_MESSAGE_UNIT) { |

176 | bytes = round_down(srclen, NH_MESSAGE_UNIT); |

177 | nhpoly1305_units(state, key, src, bytes, nh_fn); |

178 | src += bytes; |

179 | srclen -= bytes; |

180 | } |

181 | |

182 | if (srclen) { |

183 | memcpy(state->buffer, src, srclen); |

184 | state->buflen = srclen; |

185 | } |

186 | return 0; |

187 | } |

188 | EXPORT_SYMBOL(crypto_nhpoly1305_update_helper); |

189 | |

190 | int crypto_nhpoly1305_update(struct shash_desc *desc, |

191 | const u8 *src, unsigned int srclen) |

192 | { |

193 | return crypto_nhpoly1305_update_helper(desc, src, srclen, nh_generic); |

194 | } |

195 | EXPORT_SYMBOL(crypto_nhpoly1305_update); |

196 | |

197 | int crypto_nhpoly1305_final_helper(struct shash_desc *desc, u8 *dst, nh_t nh_fn) |

198 | { |

199 | struct nhpoly1305_state *state = shash_desc_ctx(desc); |

200 | const struct nhpoly1305_key *key = crypto_shash_ctx(desc->tfm); |

201 | |

202 | if (state->buflen) { |

203 | memset(&state->buffer[state->buflen], 0, |

204 | NH_MESSAGE_UNIT - state->buflen); |

205 | nhpoly1305_units(state, key, state->buffer, NH_MESSAGE_UNIT, |

206 | nh_fn); |

207 | } |

208 | |

209 | if (state->nh_remaining) |

210 | process_nh_hash_value(state, key); |

211 | |

212 | poly1305_core_emit(&state->poly_state, dst); |

213 | return 0; |

214 | } |

215 | EXPORT_SYMBOL(crypto_nhpoly1305_final_helper); |

216 | |

217 | int crypto_nhpoly1305_final(struct shash_desc *desc, u8 *dst) |

218 | { |

219 | return crypto_nhpoly1305_final_helper(desc, dst, nh_generic); |

220 | } |

221 | EXPORT_SYMBOL(crypto_nhpoly1305_final); |

222 | |

223 | static struct shash_alg nhpoly1305_alg = { |

224 | .base.cra_name = "nhpoly1305", |

225 | .base.cra_driver_name = "nhpoly1305-generic", |

226 | .base.cra_priority = 100, |

227 | .base.cra_ctxsize = sizeof(struct nhpoly1305_key), |

228 | .base.cra_module = THIS_MODULE, |

229 | .digestsize = POLY1305_DIGEST_SIZE, |

230 | .init = crypto_nhpoly1305_init, |

231 | .update = crypto_nhpoly1305_update, |

232 | .final = crypto_nhpoly1305_final, |

233 | .setkey = crypto_nhpoly1305_setkey, |

234 | .descsize = sizeof(struct nhpoly1305_state), |

235 | }; |

236 | |

237 | static int __init nhpoly1305_mod_init(void) |

238 | { |

239 | return crypto_register_shash(&nhpoly1305_alg); |

240 | } |

241 | |

242 | static void __exit nhpoly1305_mod_exit(void) |

243 | { |

244 | crypto_unregister_shash(&nhpoly1305_alg); |

245 | } |

246 | |

247 | module_init(nhpoly1305_mod_init); |

248 | module_exit(nhpoly1305_mod_exit); |

249 | |

250 | MODULE_DESCRIPTION("NHPoly1305 ε-almost-∆-universal hash function"); |

251 | MODULE_LICENSE("GPL v2"); |

252 | MODULE_AUTHOR("Eric Biggers <ebiggers@google.com>"); |

253 | MODULE_ALIAS_CRYPTO("nhpoly1305"); |

254 | MODULE_ALIAS_CRYPTO("nhpoly1305-generic"); |

255 |