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