1 // SPDX-License-Identifier: GPL-2.0-or-later 2 /* 3 * SHA-3, as specified in 4 * https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.202.pdf 5 * 6 * SHA-3 code by Jeff Garzik <jeff@garzik.org> 7 * Ard Biesheuvel <ard.biesheuvel@linaro.org> 8 * David Howells <dhowells@redhat.com> 9 * 10 * See also Documentation/crypto/sha3.rst 11 */ 12 13 #define pr_fmt(fmt) KBUILD_MODNAME ": " fmt 14 #include <crypto/sha3.h> 15 #include <crypto/utils.h> 16 #include <linux/export.h> 17 #include <linux/kernel.h> 18 #include <linux/module.h> 19 #include <linux/unaligned.h> 20 #include "fips.h" 21 22 /* 23 * On some 32-bit architectures, such as h8300, GCC ends up using over 1 KB of 24 * stack if the round calculation gets inlined into the loop in 25 * sha3_keccakf_generic(). On the other hand, on 64-bit architectures with 26 * plenty of [64-bit wide] general purpose registers, not inlining it severely 27 * hurts performance. So let's use 64-bitness as a heuristic to decide whether 28 * to inline or not. 29 */ 30 #ifdef CONFIG_64BIT 31 #define SHA3_INLINE inline 32 #else 33 #define SHA3_INLINE noinline 34 #endif 35 36 #define SHA3_KECCAK_ROUNDS 24 37 38 static const u64 sha3_keccakf_rndc[SHA3_KECCAK_ROUNDS] = { 39 0x0000000000000001ULL, 0x0000000000008082ULL, 0x800000000000808aULL, 40 0x8000000080008000ULL, 0x000000000000808bULL, 0x0000000080000001ULL, 41 0x8000000080008081ULL, 0x8000000000008009ULL, 0x000000000000008aULL, 42 0x0000000000000088ULL, 0x0000000080008009ULL, 0x000000008000000aULL, 43 0x000000008000808bULL, 0x800000000000008bULL, 0x8000000000008089ULL, 44 0x8000000000008003ULL, 0x8000000000008002ULL, 0x8000000000000080ULL, 45 0x000000000000800aULL, 0x800000008000000aULL, 0x8000000080008081ULL, 46 0x8000000000008080ULL, 0x0000000080000001ULL, 0x8000000080008008ULL 47 }; 48 49 /* 50 * Perform a single round of Keccak mixing. 51 */ 52 static SHA3_INLINE void sha3_keccakf_one_round_generic(u64 st[25], int round) 53 { 54 u64 t[5], tt, bc[5]; 55 56 /* Theta */ 57 bc[0] = st[0] ^ st[5] ^ st[10] ^ st[15] ^ st[20]; 58 bc[1] = st[1] ^ st[6] ^ st[11] ^ st[16] ^ st[21]; 59 bc[2] = st[2] ^ st[7] ^ st[12] ^ st[17] ^ st[22]; 60 bc[3] = st[3] ^ st[8] ^ st[13] ^ st[18] ^ st[23]; 61 bc[4] = st[4] ^ st[9] ^ st[14] ^ st[19] ^ st[24]; 62 63 t[0] = bc[4] ^ rol64(bc[1], 1); 64 t[1] = bc[0] ^ rol64(bc[2], 1); 65 t[2] = bc[1] ^ rol64(bc[3], 1); 66 t[3] = bc[2] ^ rol64(bc[4], 1); 67 t[4] = bc[3] ^ rol64(bc[0], 1); 68 69 st[0] ^= t[0]; 70 71 /* Rho Pi */ 72 tt = st[1]; 73 st[ 1] = rol64(st[ 6] ^ t[1], 44); 74 st[ 6] = rol64(st[ 9] ^ t[4], 20); 75 st[ 9] = rol64(st[22] ^ t[2], 61); 76 st[22] = rol64(st[14] ^ t[4], 39); 77 st[14] = rol64(st[20] ^ t[0], 18); 78 st[20] = rol64(st[ 2] ^ t[2], 62); 79 st[ 2] = rol64(st[12] ^ t[2], 43); 80 st[12] = rol64(st[13] ^ t[3], 25); 81 st[13] = rol64(st[19] ^ t[4], 8); 82 st[19] = rol64(st[23] ^ t[3], 56); 83 st[23] = rol64(st[15] ^ t[0], 41); 84 st[15] = rol64(st[ 4] ^ t[4], 27); 85 st[ 4] = rol64(st[24] ^ t[4], 14); 86 st[24] = rol64(st[21] ^ t[1], 2); 87 st[21] = rol64(st[ 8] ^ t[3], 55); 88 st[ 8] = rol64(st[16] ^ t[1], 45); 89 st[16] = rol64(st[ 5] ^ t[0], 36); 90 st[ 5] = rol64(st[ 3] ^ t[3], 28); 91 st[ 3] = rol64(st[18] ^ t[3], 21); 92 st[18] = rol64(st[17] ^ t[2], 15); 93 st[17] = rol64(st[11] ^ t[1], 10); 94 st[11] = rol64(st[ 7] ^ t[2], 6); 95 st[ 7] = rol64(st[10] ^ t[0], 3); 96 st[10] = rol64( tt ^ t[1], 1); 97 98 /* Chi */ 99 bc[ 0] = ~st[ 1] & st[ 2]; 100 bc[ 1] = ~st[ 2] & st[ 3]; 101 bc[ 2] = ~st[ 3] & st[ 4]; 102 bc[ 3] = ~st[ 4] & st[ 0]; 103 bc[ 4] = ~st[ 0] & st[ 1]; 104 st[ 0] ^= bc[ 0]; 105 st[ 1] ^= bc[ 1]; 106 st[ 2] ^= bc[ 2]; 107 st[ 3] ^= bc[ 3]; 108 st[ 4] ^= bc[ 4]; 109 110 bc[ 0] = ~st[ 6] & st[ 7]; 111 bc[ 1] = ~st[ 7] & st[ 8]; 112 bc[ 2] = ~st[ 8] & st[ 9]; 113 bc[ 3] = ~st[ 9] & st[ 5]; 114 bc[ 4] = ~st[ 5] & st[ 6]; 115 st[ 5] ^= bc[ 0]; 116 st[ 6] ^= bc[ 1]; 117 st[ 7] ^= bc[ 2]; 118 st[ 8] ^= bc[ 3]; 119 st[ 9] ^= bc[ 4]; 120 121 bc[ 0] = ~st[11] & st[12]; 122 bc[ 1] = ~st[12] & st[13]; 123 bc[ 2] = ~st[13] & st[14]; 124 bc[ 3] = ~st[14] & st[10]; 125 bc[ 4] = ~st[10] & st[11]; 126 st[10] ^= bc[ 0]; 127 st[11] ^= bc[ 1]; 128 st[12] ^= bc[ 2]; 129 st[13] ^= bc[ 3]; 130 st[14] ^= bc[ 4]; 131 132 bc[ 0] = ~st[16] & st[17]; 133 bc[ 1] = ~st[17] & st[18]; 134 bc[ 2] = ~st[18] & st[19]; 135 bc[ 3] = ~st[19] & st[15]; 136 bc[ 4] = ~st[15] & st[16]; 137 st[15] ^= bc[ 0]; 138 st[16] ^= bc[ 1]; 139 st[17] ^= bc[ 2]; 140 st[18] ^= bc[ 3]; 141 st[19] ^= bc[ 4]; 142 143 bc[ 0] = ~st[21] & st[22]; 144 bc[ 1] = ~st[22] & st[23]; 145 bc[ 2] = ~st[23] & st[24]; 146 bc[ 3] = ~st[24] & st[20]; 147 bc[ 4] = ~st[20] & st[21]; 148 st[20] ^= bc[ 0]; 149 st[21] ^= bc[ 1]; 150 st[22] ^= bc[ 2]; 151 st[23] ^= bc[ 3]; 152 st[24] ^= bc[ 4]; 153 154 /* Iota */ 155 st[0] ^= sha3_keccakf_rndc[round]; 156 } 157 158 /* Generic implementation of the Keccak-f[1600] permutation */ 159 static void sha3_keccakf_generic(struct sha3_state *state) 160 { 161 /* 162 * Temporarily convert the state words from little-endian to native- 163 * endian so that they can be operated on. Note that on little-endian 164 * machines this conversion is a no-op and is optimized out. 165 */ 166 167 for (int i = 0; i < ARRAY_SIZE(state->words); i++) 168 state->native_words[i] = le64_to_cpu(state->words[i]); 169 170 for (int round = 0; round < SHA3_KECCAK_ROUNDS; round++) 171 sha3_keccakf_one_round_generic(state->native_words, round); 172 173 for (int i = 0; i < ARRAY_SIZE(state->words); i++) 174 state->words[i] = cpu_to_le64(state->native_words[i]); 175 } 176 177 /* 178 * Generic implementation of absorbing the given nonzero number of full blocks 179 * into the sponge function Keccak[r=8*block_size, c=1600-8*block_size]. 180 */ 181 static void __maybe_unused 182 sha3_absorb_blocks_generic(struct sha3_state *state, const u8 *data, 183 size_t nblocks, size_t block_size) 184 { 185 do { 186 for (size_t i = 0; i < block_size; i += 8) 187 state->words[i / 8] ^= get_unaligned((__le64 *)&data[i]); 188 sha3_keccakf_generic(state); 189 data += block_size; 190 } while (--nblocks); 191 } 192 193 #ifdef CONFIG_CRYPTO_LIB_SHA3_ARCH 194 #include "sha3.h" /* $(SRCARCH)/sha3.h */ 195 #else 196 #define sha3_keccakf sha3_keccakf_generic 197 #define sha3_absorb_blocks sha3_absorb_blocks_generic 198 #endif 199 200 void __sha3_update(struct __sha3_ctx *ctx, const u8 *in, size_t in_len) 201 { 202 const size_t block_size = ctx->block_size; 203 size_t absorb_offset = ctx->absorb_offset; 204 205 /* Warn if squeezing has already begun. */ 206 WARN_ON_ONCE(absorb_offset >= block_size); 207 208 if (absorb_offset && absorb_offset + in_len >= block_size) { 209 crypto_xor(&ctx->state.bytes[absorb_offset], in, 210 block_size - absorb_offset); 211 in += block_size - absorb_offset; 212 in_len -= block_size - absorb_offset; 213 sha3_keccakf(&ctx->state); 214 absorb_offset = 0; 215 } 216 217 if (in_len >= block_size) { 218 size_t nblocks = in_len / block_size; 219 220 sha3_absorb_blocks(&ctx->state, in, nblocks, block_size); 221 in += nblocks * block_size; 222 in_len -= nblocks * block_size; 223 } 224 225 if (in_len) { 226 crypto_xor(&ctx->state.bytes[absorb_offset], in, in_len); 227 absorb_offset += in_len; 228 } 229 ctx->absorb_offset = absorb_offset; 230 } 231 EXPORT_SYMBOL_GPL(__sha3_update); 232 233 void sha3_final(struct sha3_ctx *sha3_ctx, u8 *out) 234 { 235 struct __sha3_ctx *ctx = &sha3_ctx->ctx; 236 237 ctx->state.bytes[ctx->absorb_offset] ^= 0x06; 238 ctx->state.bytes[ctx->block_size - 1] ^= 0x80; 239 sha3_keccakf(&ctx->state); 240 memcpy(out, ctx->state.bytes, ctx->digest_size); 241 sha3_zeroize_ctx(sha3_ctx); 242 } 243 EXPORT_SYMBOL_GPL(sha3_final); 244 245 void shake_squeeze(struct shake_ctx *shake_ctx, u8 *out, size_t out_len) 246 { 247 struct __sha3_ctx *ctx = &shake_ctx->ctx; 248 const size_t block_size = ctx->block_size; 249 size_t squeeze_offset = ctx->squeeze_offset; 250 251 if (ctx->absorb_offset < block_size) { 252 /* First squeeze: */ 253 254 /* Add the domain separation suffix and padding. */ 255 ctx->state.bytes[ctx->absorb_offset] ^= 0x1f; 256 ctx->state.bytes[block_size - 1] ^= 0x80; 257 258 /* Indicate that squeezing has begun. */ 259 ctx->absorb_offset = block_size; 260 261 /* 262 * Indicate that no output is pending yet, i.e. sha3_keccakf() 263 * will need to be called before the first copy. 264 */ 265 squeeze_offset = block_size; 266 } 267 while (out_len) { 268 if (squeeze_offset == block_size) { 269 sha3_keccakf(&ctx->state); 270 squeeze_offset = 0; 271 } 272 size_t copy = min(out_len, block_size - squeeze_offset); 273 274 memcpy(out, &ctx->state.bytes[squeeze_offset], copy); 275 out += copy; 276 out_len -= copy; 277 squeeze_offset += copy; 278 } 279 ctx->squeeze_offset = squeeze_offset; 280 } 281 EXPORT_SYMBOL_GPL(shake_squeeze); 282 283 void sha3_224(const u8 *in, size_t in_len, u8 out[SHA3_224_DIGEST_SIZE]) 284 { 285 struct sha3_ctx ctx; 286 287 sha3_224_init(&ctx); 288 sha3_update(&ctx, in, in_len); 289 sha3_final(&ctx, out); 290 } 291 EXPORT_SYMBOL_GPL(sha3_224); 292 293 void sha3_256(const u8 *in, size_t in_len, u8 out[SHA3_256_DIGEST_SIZE]) 294 { 295 struct sha3_ctx ctx; 296 297 sha3_256_init(&ctx); 298 sha3_update(&ctx, in, in_len); 299 sha3_final(&ctx, out); 300 } 301 EXPORT_SYMBOL_GPL(sha3_256); 302 303 void sha3_384(const u8 *in, size_t in_len, u8 out[SHA3_384_DIGEST_SIZE]) 304 { 305 struct sha3_ctx ctx; 306 307 sha3_384_init(&ctx); 308 sha3_update(&ctx, in, in_len); 309 sha3_final(&ctx, out); 310 } 311 EXPORT_SYMBOL_GPL(sha3_384); 312 313 void sha3_512(const u8 *in, size_t in_len, u8 out[SHA3_512_DIGEST_SIZE]) 314 { 315 struct sha3_ctx ctx; 316 317 sha3_512_init(&ctx); 318 sha3_update(&ctx, in, in_len); 319 sha3_final(&ctx, out); 320 } 321 EXPORT_SYMBOL_GPL(sha3_512); 322 323 void shake128(const u8 *in, size_t in_len, u8 *out, size_t out_len) 324 { 325 struct shake_ctx ctx; 326 327 shake128_init(&ctx); 328 shake_update(&ctx, in, in_len); 329 shake_squeeze(&ctx, out, out_len); 330 shake_zeroize_ctx(&ctx); 331 } 332 EXPORT_SYMBOL_GPL(shake128); 333 334 void shake256(const u8 *in, size_t in_len, u8 *out, size_t out_len) 335 { 336 struct shake_ctx ctx; 337 338 shake256_init(&ctx); 339 shake_update(&ctx, in, in_len); 340 shake_squeeze(&ctx, out, out_len); 341 shake_zeroize_ctx(&ctx); 342 } 343 EXPORT_SYMBOL_GPL(shake256); 344 345 #if defined(sha3_mod_init_arch) || defined(CONFIG_CRYPTO_FIPS) 346 static int __init sha3_mod_init(void) 347 { 348 #ifdef sha3_mod_init_arch 349 sha3_mod_init_arch(); 350 #endif 351 if (fips_enabled) { 352 /* 353 * FIPS cryptographic algorithm self-test. As per the FIPS 354 * Implementation Guidance, testing any SHA-3 algorithm 355 * satisfies the test requirement for all of them. 356 */ 357 u8 hash[SHA3_256_DIGEST_SIZE]; 358 359 sha3_256(fips_test_data, sizeof(fips_test_data), hash); 360 if (memcmp(fips_test_sha3_256_value, hash, sizeof(hash)) != 0) 361 panic("sha3: FIPS self-test failed\n"); 362 } 363 return 0; 364 } 365 subsys_initcall(sha3_mod_init); 366 367 static void __exit sha3_mod_exit(void) 368 { 369 } 370 module_exit(sha3_mod_exit); 371 #endif 372 373 MODULE_DESCRIPTION("SHA-3 library functions"); 374 MODULE_LICENSE("GPL"); 375