Hello Niels, Niels Möller <[email protected]> writes:
> Daiki Ueno <[email protected]> writes: > >> When I'm trying to implement ML-KEM (Kyber), I realized that the current >> API for SHAKE (sha3_256_shake) is a bit too limited: while ML-KEM uses >> SHAKE128 as a source of pseudorandom samples[1], the the current API >> requires the total number of bytes are determined prior to the call, and >> after the call the hash context is reset. > > I vaguely recall discussing that when shake256 was added, and we > concluded it was good enough as a start, and could be extended later. > > I think it would be nice if one could support the streaming case with > the existing struct sha3_256_ctx, and little extra wrapping. Question is > what the interface should be. I see a few variants: > > 1. > void /* Essentially the same as _sha3_pad_shake */ > sha3_256_shake_start (struct sha3_256_ctx *ctx); > > void /* Unbuffered, length must be a multiple of SHA3_256_BLOCK_SIZE */ > sha3_256_shake_output (struct sha3_256_ctx *ctx > size_t length, uint8_t *dst); > > void /* Last call, length can be arbitrary, context reinitialized */ > sha3_256_shake_end (struct sha3_256_ctx *ctx > size_t length, uint8_t *dst); > > Requiring all calls but the last to be full blocks is consistent with > nettle's funtions for block ciphers. But since we anyway have a buffer > available (to support arbitrary sizes for streaming the input), we could > perhaps just as well reuse that buffer. > > 2. > void /* Essentially the same as _sha3_pad_shake */ > sha3_256_shake_start (struct sha3_256_ctx *ctx); > > void /* Arbitrary length, no need to signal end of data */ > sha3_256_shake_output (struct sha3_256_ctx *ctx > size_t length, uint8_t *dst); > > void /* Explicit init call needed to start a new input message */ > sha3_256_init (struct sha3_256_ctx *ctx); > > In this case, sha3_256_shake_output would use ctx->index and ctx->buffer > for partial blocks. > > With some hacking (say, using the unused high bit of ctx->index to > signal that shake is in output mode), then we could have just > > 3. > void /* Arbitrary length, no need to signal start or end of output */ > sha3_256_shake_output (struct sha3_256_ctx *ctx > size_t length, uint8_t *dst); > > void /* Explicit init call needed to start a new input message */ > sha3_256_init (struct sha3_256_ctx *ctx); > > As always, naming is also a crucial question. Is _shake_output a good > name? Or _shake_read, or _shake_generate? From the terminology in the > spec (https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.202.pdf), I think > "_shake_output" is reasonable. > > When deciding on naming and conventions, we should strive to define > somthing that can be reused for later hash functions with variable > output size (called extendable-output functions, "XOF", in the spec). > > So what do you think makes most sense? Thank you. The option (3) sounds like a great idea as it only need one more function to be added for streaming. I tried to implement it as the attached patch. Regards, -- Daiki Ueno
>From fa02672ce0ee7956a444381c88693c9b03c2bd15 Mon Sep 17 00:00:00 2001 From: Daiki Ueno <[email protected]> Date: Sun, 10 Mar 2024 09:43:04 +0900 Subject: [PATCH] sha3: Extend SHAKE256 API with incremental output This adds an alternative function sha3_256_shake_output in the SHAKE256 support, which enables to read output multiple times in an incremental manner. Signed-off-by: Daiki Ueno <[email protected]> --- sha3.h | 8 ++++++ shake256.c | 52 +++++++++++++++++++++++++++++++++++ testsuite/shake256-test.c | 58 +++++++++++++++++++++++++++++++++++++++ 3 files changed, 118 insertions(+) diff --git a/sha3.h b/sha3.h index 9220829d..4b7e186c 100644 --- a/sha3.h +++ b/sha3.h @@ -49,6 +49,7 @@ extern "C" { #define sha3_256_update nettle_sha3_256_update #define sha3_256_digest nettle_sha3_256_digest #define sha3_256_shake nettle_sha3_256_shake +#define sha3_256_shake_output nettle_sha3_256_shake_output #define sha3_384_init nettle_sha3_384_init #define sha3_384_update nettle_sha3_384_update #define sha3_384_digest nettle_sha3_384_digest @@ -143,6 +144,13 @@ sha3_256_shake(struct sha3_256_ctx *ctx, size_t length, uint8_t *digest); +/* Unlike sha3_256_shake, this function can be called multiple times + to retrieve output from shake256 in an incremental manner */ +void +sha3_256_shake_output(struct sha3_256_ctx *ctx, + size_t length, + uint8_t *digest); + struct sha3_384_ctx { struct sha3_state state; diff --git a/shake256.c b/shake256.c index f5c77a43..1356218b 100644 --- a/shake256.c +++ b/shake256.c @@ -36,6 +36,7 @@ # include "config.h" #endif +#include <limits.h> #include <stddef.h> #include <string.h> @@ -44,6 +45,8 @@ #include "nettle-write.h" +#define MIN(x,y) ((x)<(y)?(x):(y)) + void sha3_256_shake (struct sha3_256_ctx *ctx, size_t length, @@ -61,3 +64,52 @@ sha3_256_shake (struct sha3_256_ctx *ctx, sha3_256_init (ctx); } + +void +sha3_256_shake_output(struct sha3_256_ctx *ctx, + size_t length, + uint8_t *digest) +{ + unsigned offset; + unsigned mask = UINT_MAX >> 1; + + /* We use the leftmost bit as a flag to indicate SHAKE is initialized. */ + if (ctx->index & ~mask) + offset = ctx->index & mask; + else + { + _sha3_pad_shake (&ctx->state, SHA3_256_BLOCK_SIZE, ctx->block, ctx->index); + /* Point at the end of block to trigger fill in of the buffer. */ + offset = sizeof (ctx->block); + } + + for (;;) + { + /* Write remaining data from the buffer. */ + if (offset < sizeof (ctx->block)) + { + unsigned remaining; + + remaining = MIN(length, sizeof (ctx->block) - offset); + memcpy (digest, &ctx->block[offset], remaining); + digest += remaining; + offset += remaining; + + length -= remaining; + if (!length) + { + /* Write back offset with a mask. */ + ctx->index = offset | ~mask; + return; + } + } + + /* Fill in the buffer. */ + if (offset == sizeof (ctx->block)) + { + _nettle_write_le64 (sizeof (ctx->block), ctx->block, ctx->state.a); + sha3_permute (&ctx->state); + offset = 0; + } + } +} diff --git a/testsuite/shake256-test.c b/testsuite/shake256-test.c index b91417cb..016060e8 100644 --- a/testsuite/shake256-test.c +++ b/testsuite/shake256-test.c @@ -34,6 +34,8 @@ #include "sha3.h" +#define MIN(a,b) (((a) < (b)) ? (a) : (b)) + const struct nettle_hash nettle_shake256 = { "shake256", @@ -45,9 +47,36 @@ const struct nettle_hash nettle_shake256 = (nettle_hash_digest_func *) sha3_256_shake, }; +static void +test_incremental (const struct tstring *msg, + const struct tstring *digest, + size_t interval) +{ + struct sha3_256_ctx ctx; + size_t offset = 0; + uint8_t *buffer = xalloc (digest->length); + + sha3_256_init (&ctx); + sha3_256_update (&ctx, msg->length, msg->data); + + while (offset < digest->length) + { + size_t to_read = MIN(digest->length - offset, interval); + + sha3_256_shake_output (&ctx, to_read, buffer + offset); + + offset += to_read; + } + + ASSERT (MEMEQ (digest->length, digest->data, buffer)); + free (buffer); +} + void test_main(void) { + const struct tstring *msg, *digest; + /* Extracted from ShortMsgKAT_SHAKE256.txt. */ test_hash (&nettle_shake256, /* 0 octets */ SHEX(""), @@ -5937,4 +5966,33 @@ test_main(void) "805C7B7E2CFD54E0FAD62F0D8CA67A775DC4546AF9096F2EDB2" "21DB42843D65327861282DC946A0BA01A11863AB2D1DFD16E39" "73D4")); + + /* Test incremental API */ + msg = SHEX("3A3A819C48EFDE2AD914FBF00E18AB6BC4F14513AB27D0C178A188B61431E7F5623CB66B23346775D386B50E982C493ADBBFC54B9A3CD383382336A1A0B2150A15358F336D03AE18F666C7573D55C4FD181C29E6CCFDE63EA35F0ADF5885CFC0A3D84A2B2E4DD24496DB789E663170CEF74798AA1BBCD4574EA0BBA40489D764B2F83AADC66B148B4A0CD95246C127D5871C4F11418690A5DDF01246A0C80A43C70088B6183639DCFDA4125BD113A8F49EE23ED306FAAC576C3FB0C1E256671D817FC2534A52F5B439F72E424DE376F4C565CCA82307DD9EF76DA5B7C4EB7E085172E328807C02D011FFBF33785378D79DC266F6A5BE6BB0E4A92ECEEBAEB1"); + digest = SHEX("8A5199B4A7E133E264A86202720655894D48CFF344A928CF834" + "7F48379CEF347DFC5BCFFAB99B27B1F89AA2735E23D30088FFA" + "03B9EDB02B9635470AB9F1038985D55F9CA774572DD006470EA" + "65145469609F9FA0831BF1FFD842DC24ACADE27BD9816E3B5BF" + "2876CB112232A0EB4475F1DFF9F5C713D9FFD4CCB89AE5607FE" + "35731DF06317949EEF646E9591CF3BE53ADD6B7DD2B6096E2B3" + "FB06E662EC8B2D77422DAAD9463CD155204ACDBD38E319613F3" + "9F99B6DFB35CA9365160066DB19835888C2241FF9A731A4ACBB" + "5663727AAC34A401247FBAA7499E7D5EE5B69D31025E63D04C3" + "5C798BCA1262D5673A9CF0930B5AD89BD485599DC184528DA47" + "90F088EBD170B635D9581632D2FF90DB79665CED430089AF13C" + "9F21F6D443A818064F17AEC9E9C5457001FA8DC6AFBADBE3138" + "F388D89D0E6F22F66671255B210754ED63D81DCE75CE8F189B5" + "34E6D6B3539AA51E837C42DF9DF59C71E6171CD4902FE1BDC73" + "FB1775B5C754A1ED4EA7F3105FC543EE0418DAD256F3F6118EA" + "77114A16C15355B42877A1DB2A7DF0E155AE1D8670ABCEC3450" + "F4E2EEC9838F895423EF63D261138BAAF5D9F104CB5A957AEA0" + "6C0B9B8C78B0D441796DC0350DDEABB78A33B6F1F9E68EDE3D1" + "805C7B7E2CFD54E0FAD62F0D8CA67A775DC4546AF9096F2EDB2" + "21DB42843D65327861282DC946A0BA01A11863AB2D1DFD16E39" + "73D4"); + + test_incremental (msg, digest, 16); + test_incremental (msg, digest, SHA3_256_BLOCK_SIZE - 1); + test_incremental (msg, digest, SHA3_256_BLOCK_SIZE); + test_incremental (msg, digest, SHA3_256_BLOCK_SIZE + 1); } -- 2.43.2
_______________________________________________ nettle-bugs mailing list -- [email protected] To unsubscribe send an email to [email protected]
