Support cSHAKE and TurboSHAKE. The amount of additional code is tiny and it seems like these will probably be useful at some point. Still no public API. Change-Id: I275124a5936337df9032e9b0b692d1f5739a8f5d Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/100287 Auto-Submit: Adam Langley <agl@google.com> Commit-Queue: Adam Langley <agl@google.com> Reviewed-by: David Benjamin <davidben@google.com>
diff --git a/crypto/fipsmodule/keccak/internal.h b/crypto/fipsmodule/keccak/internal.h index a69081e..e7d79b0 100644 --- a/crypto/fipsmodule/keccak/internal.h +++ b/crypto/fipsmodule/keccak/internal.h
@@ -27,6 +27,10 @@ boringssl_sha3_512, boringssl_shake128, boringssl_shake256, + boringssl_turboshake128, + boringssl_turboshake256, + boringssl_cshake128, + boringssl_cshake256, }; enum boringssl_keccak_phase_t : int32_t { @@ -49,7 +53,8 @@ // BORINGSSL_keccak hashes `in_len` bytes from `in` and writes `out_len` bytes // of output to `out`. If the `config` specifies a fixed-output function, like -// SHA3-256, then `out_len` must be the correct length for that function. +// SHA3-256, then `out_len` must be the correct length for that function. The +// cSHAKE configurations are only valid with the BORINGSSL_cshake functions. OPENSSL_EXPORT void BORINGSSL_keccak(uint8_t *out, size_t out_len, const uint8_t *in, size_t in_len, enum boringssl_keccak_config_t config); @@ -61,6 +66,26 @@ OPENSSL_EXPORT void BORINGSSL_keccak_init( struct BORINGSSL_keccak_st *ctx, enum boringssl_keccak_config_t config); +// BORINGSSL_cshake_init prepares `ctx` for cSHAKE, including absorbing the +// function-name and customization strings. `config` must be +// `boringssl_cshake128` or `boringssl_cshake256`. The message may then be +// absorbed and output squeezed with the usual Keccak functions. +OPENSSL_EXPORT void BORINGSSL_cshake_init(struct BORINGSSL_keccak_st *ctx, + enum boringssl_keccak_config_t config, + const uint8_t *function_name, + size_t function_name_len, + const uint8_t *customization, + size_t customization_len); + +// BORINGSSL_cshake is the one-shot form of BORINGSSL_cshake_init. +OPENSSL_EXPORT void BORINGSSL_cshake(uint8_t *out, size_t out_len, + const uint8_t *in, size_t in_len, + enum boringssl_keccak_config_t config, + const uint8_t *function_name, + size_t function_name_len, + const uint8_t *customization, + size_t customization_len); + // BORINGSSL_keccak_absorb absorbs `in_len` bytes from `in`. OPENSSL_EXPORT void BORINGSSL_keccak_absorb(struct BORINGSSL_keccak_st *ctx, const uint8_t *in, size_t in_len); @@ -94,12 +119,14 @@ // BORINGSSL_keccak_squeeze_x2 performs BORINGSSL_keccak_squeeze in parallel // with two same-length outputs. The contexts must be in equivalent state (i.e. // same config, same amount of bytes absorbed and squeezed). +// This function is not compatible with cSHAKE nor TurboSHAKE. OPENSSL_EXPORT void BORINGSSL_keccak_squeeze_x2( struct BORINGSSL_keccak_st ctx[2], uint8_t *outs[2], size_t out_len); // BORINGSSL_keccak_short_x2 performs BORINGSSL_keccak in parallel on two // same-length strings with same-length outputs. `in_len` must be less than 72 // (or actually `rate_bytes`). +// This function is not compatible with cSHAKE nor TurboSHAKE. OPENSSL_EXPORT void BORINGSSL_keccak_short_x2( uint8_t *outs[2], size_t out_len, const uint8_t *ins[2], size_t in_len, enum boringssl_keccak_config_t config); @@ -108,6 +135,7 @@ #if defined(HAVE_KECCAK_X4) // BORINGSSL_have_keccak_x4 needs to return true before using any of the _x4 // variants here, as they may require additional CPU features. +// This function is not compatible with cSHAKE nor TurboSHAKE. inline bool BORINGSSL_have_keccak_x4() { #if defined(OPENSSL_X86_64) return CRYPTO_is_AVX2_capable(); @@ -119,12 +147,14 @@ // BORINGSSL_keccak_squeeze_x4 performs BORINGSSL_keccak_squeeze in parallel // with four same-length outputs. The contexts must be in equivalent state (i.e. // same config, same amount of bytes absorbed and squeezed). +// This function is not compatible with cSHAKE nor TurboSHAKE. OPENSSL_EXPORT void BORINGSSL_keccak_squeeze_x4( struct BORINGSSL_keccak_st ctx[4], uint8_t *outs[4], size_t out_len); // BORINGSSL_keccak_short_x4 performs BORINGSSL_keccak in parallel on four // same-length strings with same-length outputs. in_len must be less than 72 -// (or actually |rate_bytes|). +// (or actually `rate_bytes`). +// This function is not compatible with cSHAKE nor TurboSHAKE. OPENSSL_EXPORT void BORINGSSL_keccak_short_x4( uint8_t *outs[4], size_t out_len, const uint8_t *ins[4], size_t in_len, enum boringssl_keccak_config_t config);
diff --git a/crypto/fipsmodule/keccak/keccak.cc.inc b/crypto/fipsmodule/keccak/keccak.cc.inc index 83b8647..adb09a2 100644 --- a/crypto/fipsmodule/keccak/keccak.cc.inc +++ b/crypto/fipsmodule/keccak/keccak.cc.inc
@@ -34,7 +34,8 @@ *value = CRYPTO_rotl_u64(*value, shift); } -// keccak_f implements the Keccak-1600 permutation as described at +// keccak_f implements the last `num_rounds` of the Keccak-1600 permutation, +// i.e. Keccak-p[1600, num_rounds], as described at // https://keccak.team/keccak_specs_summary.html. Each lane is represented as a // 64-bit value and the 5×5 lanes are stored as an array in row-major order. // @@ -45,9 +46,10 @@ // are used whenever the calling function is `KECCAK_X4_TARGET`, as target // attributes are inherited into callees when inlining. template <typename U64, void (*rotl)(U64 *value, int shift) = rotl_u64> -static inline OPENSSL_ATTR_ALWAYS_INLINE void keccak_f(U64 state[25]) { +static inline OPENSSL_ATTR_ALWAYS_INLINE void keccak_f(U64 state[25], + int num_rounds = 24) { static const int kNumRounds = 24; - for (int round = 0; round < kNumRounds; round++) { + for (int round = kNumRounds - num_rounds; round < kNumRounds; round++) { // θ step U64 c[5]; for (int x = 0; x < 5; x++) { @@ -208,10 +210,14 @@ required_out_len = 64; break; case boringssl_shake128: + case boringssl_turboshake128: + case boringssl_cshake128: capacity_bytes = 256 / 8; required_out_len = 0; break; case boringssl_shake256: + case boringssl_turboshake256: + case boringssl_cshake256: capacity_bytes = 512 / 8; required_out_len = 0; break; @@ -227,6 +233,23 @@ assert(ctx->rate_bytes % 8 == 0); } +[[maybe_unused]] static bool keccak_can_parallel( + enum boringssl_keccak_config_t config) { + return config == boringssl_sha3_256 || config == boringssl_sha3_512 || + config == boringssl_shake128 || config == boringssl_shake256; +} + +static bool keccak_is_cshake(enum boringssl_keccak_config_t config) { + return config == boringssl_cshake128 || config == boringssl_cshake256; +} + +static int keccak_num_rounds(enum boringssl_keccak_config_t config) { + if (config == boringssl_turboshake128 || config == boringssl_turboshake256) { + return 12; + } + return 24; +} + void bssl::BORINGSSL_keccak(uint8_t *out, size_t out_len, const uint8_t *in, size_t in_len, enum boringssl_keccak_config_t config) { @@ -241,6 +264,8 @@ void bssl::BORINGSSL_keccak_short_x2(uint8_t *outs[2], size_t out_len, const uint8_t *ins[2], size_t in_len, enum boringssl_keccak_config_t config) { + assert(keccak_can_parallel(config)); + struct BORINGSSL_keccak_st ctx[2]; for (size_t i = 0; i < 2; ++i) { BORINGSSL_keccak_init(&ctx[i], config); @@ -263,6 +288,8 @@ KECCAK_X4_TARGET void bssl::BORINGSSL_keccak_short_x4( uint8_t *outs[4], size_t out_len, const uint8_t *ins[4], size_t in_len, enum boringssl_keccak_config_t config) { + assert(keccak_can_parallel(config)); + struct BORINGSSL_keccak_st ctx[4]; for (size_t i = 0; i < 4; ++i) { BORINGSSL_keccak_init(&ctx[i], config); @@ -283,6 +310,7 @@ void bssl::BORINGSSL_keccak_init(struct BORINGSSL_keccak_st *ctx, enum boringssl_keccak_config_t config) { + BSSL_CHECK(!keccak_is_cshake(config)); keccak_init(ctx, config); } @@ -310,7 +338,7 @@ return; } - keccak_f(ctx->state); + keccak_f(ctx->state, keccak_num_rounds(ctx->config)); in += first_block_len; in_len -= first_block_len; } @@ -320,7 +348,7 @@ for (size_t i = 0; i < rate_words; i++) { ctx->state[i] ^= CRYPTO_load_u64_le(in + 8 * i); } - keccak_f(ctx->state); + keccak_f(ctx->state, keccak_num_rounds(ctx->config)); in += ctx->rate_bytes; in_len -= ctx->rate_bytes; } @@ -333,6 +361,72 @@ ctx->absorb_offset = in_len; } +// left_encode implements the integer encoding from NIST SP 800-185, section +// 2.3.1. +static size_t left_encode(uint8_t out[sizeof(size_t) + 1], size_t value) { + size_t num_bytes = 1; + for (size_t v = value; v > 0xff; v >>= 8) { + num_bytes++; + } + out[0] = (uint8_t)num_bytes; + for (size_t i = 0; i < num_bytes; i++) { + out[num_bytes - i] = (uint8_t)(value >> (8 * i)); + } + return num_bytes + 1; +} + +static void cshake_absorb_encode_string(struct BORINGSSL_keccak_st *ctx, + const uint8_t *in, size_t in_len) { + BSSL_CHECK(in_len <= SIZE_MAX / 8); + uint8_t encoded[sizeof(size_t) + 1]; + const size_t encoded_len = left_encode(encoded, in_len * 8); + BORINGSSL_keccak_absorb(ctx, encoded, encoded_len); + BORINGSSL_keccak_absorb(ctx, in, in_len); +} + +void bssl::BORINGSSL_cshake_init(struct BORINGSSL_keccak_st *ctx, + enum boringssl_keccak_config_t config, + const uint8_t *function_name, + size_t function_name_len, + const uint8_t *customization, + size_t customization_len) { + BSSL_CHECK(keccak_is_cshake(config)); + + // SP 800-185 defines cSHAKE with two empty strings to be SHAKE. + if (function_name_len == 0 && customization_len == 0) { + BORINGSSL_keccak_init(ctx, config == boringssl_cshake128 + ? boringssl_shake128 + : boringssl_shake256); + return; + } + + keccak_init(ctx, config); + uint8_t encoded[sizeof(size_t) + 1]; + const size_t encoded_len = left_encode(encoded, ctx->rate_bytes); + BORINGSSL_keccak_absorb(ctx, encoded, encoded_len); + cshake_absorb_encode_string(ctx, function_name, function_name_len); + cshake_absorb_encode_string(ctx, customization, customization_len); + + static const uint8_t kZeros[168] = {0}; + if (ctx->absorb_offset != 0) { + BORINGSSL_keccak_absorb(ctx, kZeros, ctx->rate_bytes - ctx->absorb_offset); + } +} + +void bssl::BORINGSSL_cshake(uint8_t *out, size_t out_len, const uint8_t *in, + size_t in_len, + enum boringssl_keccak_config_t config, + const uint8_t *function_name, + size_t function_name_len, + const uint8_t *customization, + size_t customization_len) { + struct BORINGSSL_keccak_st ctx; + BORINGSSL_cshake_init(&ctx, config, function_name, function_name_len, + customization, customization_len); + BORINGSSL_keccak_absorb(&ctx, in, in_len); + BORINGSSL_keccak_squeeze(&ctx, out, out_len); +} + static uint8_t keccak_terminator(struct BORINGSSL_keccak_st *ctx) { switch (ctx->config) { case boringssl_sha3_256: @@ -340,7 +434,12 @@ return 0x06; case boringssl_shake128: case boringssl_shake256: + case boringssl_turboshake128: + case boringssl_turboshake256: return 0x1f; + case boringssl_cshake128: + case boringssl_cshake256: + return 0x04; default: abort(); } @@ -352,7 +451,7 @@ uint8_t *state_bytes = (uint8_t *)ctx->state; state_bytes[ctx->absorb_offset] ^= keccak_terminator(ctx); state_bytes[ctx->rate_bytes - 1] ^= 0x80; - keccak_f(ctx->state); + keccak_f(ctx->state, keccak_num_rounds(ctx->config)); } #if defined(HAVE_KECCAK_X2) @@ -370,24 +469,13 @@ #if defined(HAVE_KECCAK_X4) static void keccak_finalize_x4(struct BORINGSSL_keccak_st ctx[4]) { + assert(keccak_can_parallel(ctx[0].config)); + for (size_t i = 0; i < 4; ++i) { // XOR the terminator. Accessing `ctx->state` as a `uint8_t*` is allowed // by strict aliasing because we require `uint8_t` to be a character type. - uint8_t terminator; - switch (ctx[i].config) { - case boringssl_sha3_256: - case boringssl_sha3_512: - terminator = 0x06; - break; - case boringssl_shake128: - case boringssl_shake256: - terminator = 0x1f; - break; - default: - abort(); - } uint8_t *state_bytes = (uint8_t *)ctx[i].state; - state_bytes[ctx[i].absorb_offset] ^= terminator; + state_bytes[ctx[i].absorb_offset] ^= keccak_terminator(&ctx[i]); state_bytes[ctx[i].rate_bytes - 1] ^= 0x80; } keccak_f_x4(ctx[0].state, ctx[1].state, ctx[2].state, ctx[3].state); @@ -412,7 +500,7 @@ const uint8_t *state_bytes = (const uint8_t *)ctx->state; while (out_len) { if (ctx->squeeze_offset == ctx->rate_bytes) { - keccak_f(ctx->state); + keccak_f(ctx->state, keccak_num_rounds(ctx->config)); ctx->squeeze_offset = 0; } @@ -431,6 +519,8 @@ #if defined(HAVE_KECCAK_X2) void bssl::BORINGSSL_keccak_squeeze_x2(struct BORINGSSL_keccak_st ctx[2], uint8_t *outs[2], size_t out_len) { + assert(keccak_can_parallel(ctx[0].config)); + for (size_t i = 0; i < 2; ++i) { // The SHA-3 variants must be squeezed in a single call, to confirm that // the output length is correct. @@ -491,6 +581,8 @@ #if defined(HAVE_KECCAK_X4) KECCAK_X4_TARGET void bssl::BORINGSSL_keccak_squeeze_x4( struct BORINGSSL_keccak_st ctx[4], uint8_t *outs[4], size_t out_len) { + assert(keccak_can_parallel(ctx[0].config)); + for (size_t i = 0; i < 4; ++i) { // The SHA-3 variants must be squeezed in a single call, to confirm that // the output length is correct.
diff --git a/crypto/fipsmodule/keccak/keccak_test.cc b/crypto/fipsmodule/keccak/keccak_test.cc index b20d587..603c3fa 100644 --- a/crypto/fipsmodule/keccak/keccak_test.cc +++ b/crypto/fipsmodule/keccak/keccak_test.cc
@@ -19,6 +19,7 @@ #include <gtest/gtest.h> #include <openssl/bytestring.h> +#include <openssl/span.h> #include "../../test/file_test.h" #include "../../test/test_util.h" @@ -212,6 +213,112 @@ FileTestGTest("crypto/fipsmodule/keccak/keccak_tests.txt", KeccakFileTest); } +static void ExpectKeccak(const std::vector<uint8_t> &input, + enum boringssl_keccak_config_t config, + const char *expected_hex) { + std::vector<uint8_t> expected; + ASSERT_TRUE(DecodeHex(&expected, expected_hex)); + std::vector<uint8_t> out(expected.size()); + BORINGSSL_keccak(out.data(), out.size(), input.data(), input.size(), config); + EXPECT_EQ(Bytes(expected), Bytes(out)); + + struct BORINGSSL_keccak_st ctx; + BORINGSSL_keccak_init(&ctx, config); + for (size_t i = 0; i < input.size(); i++) { + BORINGSSL_keccak_absorb(&ctx, &input[i], 1); + } + for (size_t i = 0; i < out.size(); i++) { + BORINGSSL_keccak_squeeze(&ctx, &out[i], 1); + } + EXPECT_EQ(Bytes(expected), Bytes(out)); +} + +TEST(KeccakTest, TurboSHAKE) { + // https://www.rfc-editor.org/rfc/rfc9861.html#section-5 + const std::vector<uint8_t> empty; + ExpectKeccak(empty, boringssl_turboshake128, + "1e415f1c5983aff2169217277d17bb53" + "8cd945a397ddec541f1ce41af2c1b74c"); + ExpectKeccak(empty, boringssl_turboshake256, + "367a329dafea871c7802ec67f905ae13" + "c57695dc2c6663c61035f59a18f8e7db" + "11edc0e12e91ea60eb6b32df06dd7f00" + "2fbafabb6e13ec1cc20d995547600db0"); + + std::vector<uint8_t> input(17 * 17); + for (size_t i = 0; i < input.size(); i++) { + input[i] = static_cast<uint8_t>(i % 251); + } + ExpectKeccak(input, boringssl_turboshake128, + "96c77c279e0126f7fc07c9b07f5cdae1" + "e0be60bdbe10620040e75d7223a624d2"); + ExpectKeccak(input, boringssl_turboshake256, + "66b810db8e90780424c0847372fdc957" + "10882fde31c6df75beb9d4cd9305cfca" + "e35e7b83e8b7e6eb4b78605880116316" + "fe2c078a09b94ad7b8213c0a738b65c0"); +} + +static void ExpectCSHAKE(enum boringssl_keccak_config_t config, + Span<const uint8_t> function_name, + Span<const uint8_t> customization, + const char *expected_hex) { + static const uint8_t kInput[] = {0x00, 0x01, 0x02, 0x03}; + std::vector<uint8_t> expected; + ASSERT_TRUE(DecodeHex(&expected, expected_hex)); + std::vector<uint8_t> out(expected.size()); + BORINGSSL_cshake(out.data(), out.size(), kInput, sizeof(kInput), config, + function_name.data(), function_name.size(), + customization.data(), customization.size()); + EXPECT_EQ(Bytes(expected), Bytes(out)); +} + +TEST(KeccakTest, CSHAKE) { + // These are samples #1 and #3 from NIST's cSHAKE sample vectors for + // SP 800-185. + // https://csrc.nist.gov/CSRC/media/Projects/Cryptographic-Standards-and-Guidelines/documents/examples/cSHAKE_samples.pdf + static const char kCustomization[] = "Email Signature"; + ExpectCSHAKE(boringssl_cshake128, {}, StringAsBytes(kCustomization), + "c1c36925b6409a04f1b504fcbca9d82b" + "4017277cb5ed2b2065fc1d3814d5aaf5"); + ExpectCSHAKE(boringssl_cshake256, {}, StringAsBytes(kCustomization), + "d008828e2b80ac9d2218ffee1d070c48" + "b8e4c87bff32c9699d5b6896eee0edd1" + "64020e2be0560858d9c00c037e34a969" + "37c561a74c412bb4c746469527281c8c"); + + static const char kFunctionName[] = "Function"; + static const char kOtherCustomization[] = "Customization"; + ExpectCSHAKE(boringssl_cshake128, StringAsBytes(kFunctionName), + StringAsBytes(kOtherCustomization), + "494da17e9313dc08cef4eb25f77376f7" + "cae34a0d865d86789d98760f40eade0b"); + + // cSHAKE with empty function-name and customization strings is SHAKE. + static const uint8_t kInput[] = {0x00, 0x01, 0x02, 0x03}; + uint8_t shake[32], cshake[sizeof(shake)]; + BORINGSSL_keccak(shake, sizeof(shake), kInput, sizeof(kInput), + boringssl_shake128); + BORINGSSL_cshake(cshake, sizeof(cshake), kInput, sizeof(kInput), + boringssl_cshake128, nullptr, 0, nullptr, 0); + EXPECT_EQ(Bytes(shake), Bytes(cshake)); + + std::vector<uint8_t> expected; + ASSERT_TRUE(DecodeHex(&expected, + "c1c36925b6409a04f1b504fcbca9d82b" + "4017277cb5ed2b2065fc1d3814d5aaf5")); + std::vector<uint8_t> out(expected.size()); + struct BORINGSSL_keccak_st ctx; + BORINGSSL_cshake_init(&ctx, boringssl_cshake128, nullptr, 0, + reinterpret_cast<const uint8_t *>(kCustomization), + sizeof(kCustomization) - 1); + BORINGSSL_keccak_absorb(&ctx, kInput, 1); + BORINGSSL_keccak_absorb(&ctx, kInput + 1, sizeof(kInput) - 1); + BORINGSSL_keccak_squeeze(&ctx, out.data(), 7); + BORINGSSL_keccak_squeeze(&ctx, out.data() + 7, out.size() - 7); + EXPECT_EQ(Bytes(expected), Bytes(out)); +} + // Unoptimized builds are much slower, and iterative tests run Keccak many // times. Disable them in unoptimized builds for now. // https://crbug.com/479850443