Hello Niels,
Niels Möller <ni...@lysator.liu.se> writes:
> Daiki Ueno <u...@gnu.org> writes:
>
>>> * One could perhaps use index == 0 instead of index == block_size for
>>> the case that there is no buffered data. But the current convention
>>> does make your "if (length <= left)" nice and simple.
>>
>> I agree that the current convention is a bit awkward, so in the attached
>> patch I changed to use index == 0 as the indicator where buffering is
>> needed. That actually makes the code simpler as we can defer buffering
>> until when the data is read. One drawback though is that it causes
>> additional memcpy in a corner case where the _shake_output is used to
>> retrieve data smaller than the block size.
>
> I wonder if that will still be simpler if one also moves the
> sha3_permute calls?
>
> I have merged your previous version to a branch
> add-sha3_256_shake_output, and ci looks green. So perhaps best to merge
> that to master, and iterate from there?
Sorry for the delay, and thank you for merging it to master. I've come
up with the attached 3 patches on top of it, which basically do:
- Apply my changes in the previous post to count index from zero, not
the end of the block
- Rename sha3_256_shake_output to sha3_shake256_output and add
sha3_shake256_init/update as well, as you suggested in the previous
conversation. That would help us implement SHAKE128 without exposing
SHA3-128 digest functions and I find it easier to read when used in
the ML-KEM implementation.
- Generalize _shake_output function independent of the underlying SHA-3
algorithm.
>>> * It looks a bit backwards to me that each iteration *first* copies data
>>> to the digest, and *then* calls sha3_permute. In case no more data is
>>> to be output, that sha3_permute call is wasted. It would be more
>>> natural to me to not call sha3_permute until we know the output is
>>> needed. But to fix that and still keep things nice for the first
>>> output block, I think one would need to reorganize _nettle_sha3_pad to
>>> not imply a call to sha3_permute (via sha3_absorb). So that's better
>>> done in a separate change.
>>
>> Right, I can do that after the current patch is settled.
>
> I've done a bit of hacking locally. What I did was to take out the
> xoring parts of sha3_absorb into it's own function sha3_xor_block, and
> let sha3_pad_shake use that, without any call to sha3_permute. And then
> call sha3_permute as output is needed.
Cool!
>>> * I'm still tempted to use ctx->index = ~index rather than ctx->index =
>>> index | INDEX_HIGH_BIT. But maybe that would just be too obfuscated.
>>
>> I'm actually not sure how this works. For example, if unsigned int is
>> 32-bit and index is 3, wouldn't ~index turn to 0xfffffffc, while index |
>> INDEX_HIGH_BIT is 0x80000003?
>
> It would be a different representation, with the very minor advantage
> that the INDEX_HIGH_BIT value isn't needed (in source code, or handled
> at runtime). Like
>
> index = ctx->index;
>
> if (index < sizeof(ctx->block))
> { ... first call to shake_output, pad and initialize... }
> else
> index = ~index;
>
> assert (index <= sizeof(ctx->block));
>
> ... output processing ...
>
> ctx->index = ~index;
I see. I rewote it using this pattern.
>>> In next step, to also support shake128, we should generalize your code
>>> using an internal function _sha3_shake_output taking block and block
>>> size as arguments.
>>
>> Yes.
>
> I've tried that in my local hack, I think it's rather straight-forward.
> (I might be able to post corresponding patch later). What's unclear is
> how much to share between _shake and shake_output. One could define
> _shake as _shake_output + _init. The drawback I see is that (i) we would
> allow _shake_output followed by _shake, which isn't proper api usage,
> and (ii) _shake needs a lot less logic since it should always start by
> padding, and it doesn't need to buffer any data, so it seems a bit wrong
> to have it call shake_output that does this unneeded extra work.
In the attached patch, _shake is now re-implemented using _shake_output
+ _init, and also marked as deprecated in favor of the new incremental
interface.
Regards,
--
Daiki Ueno
>From aab41e6fe2dd4461c59af63a84b45e19ec0eb9e7 Mon Sep 17 00:00:00 2001
From: Daiki Ueno <du...@redhat.com>
Date: Sat, 23 Mar 2024 17:44:33 +0900
Subject: [PATCH 1/3] shake256: Simplify the implementation
Signed-off-by: Daiki Ueno <du...@redhat.com>
---
shake256.c | 25 +++++++++++++++----------
1 file changed, 15 insertions(+), 10 deletions(-)
diff --git a/shake256.c b/shake256.c
index 9c418395..11d34d5e 100644
--- a/shake256.c
+++ b/shake256.c
@@ -75,23 +75,30 @@ sha3_256_shake_output (struct sha3_256_ctx *ctx,
/* We use the leftmost bit as a flag to indicate SHAKE is initialized. */
if (ctx->index & INDEX_HIGH_BIT)
- index = ctx->index & ~INDEX_HIGH_BIT;
+ index = ~ctx->index;
else
{
/* This is the first call of _shake_output. */
_sha3_pad_shake (&ctx->state, sizeof (ctx->block), ctx->block, ctx->index);
/* Point at the end of block to trigger fill in of the buffer. */
- index = sizeof (ctx->block);
+ index = 0;
}
- assert (index <= sizeof (ctx->block));
+ assert (index < sizeof (ctx->block));
+
+ if (index == 0)
+ {
+ /* Fill in the buffer. */
+ _nettle_write_le64 (sizeof (ctx->block), ctx->block, ctx->state.a);
+ sha3_permute (&ctx->state);
+ }
/* Write remaining data from the buffer. */
left = sizeof (ctx->block) - index;
if (length <= left)
{
memcpy (digest, ctx->block + index, length);
- ctx->index = (index + length) | INDEX_HIGH_BIT;
+ ctx->index = ~((index + length) % sizeof (ctx->block));
return;
}
else
@@ -102,22 +109,20 @@ sha3_256_shake_output (struct sha3_256_ctx *ctx,
}
/* Write full blocks. */
- while (length > sizeof (ctx->block))
+ while (length >= sizeof (ctx->block))
{
_nettle_write_le64 (sizeof (ctx->block), digest, ctx->state.a);
+ sha3_permute (&ctx->state);
length -= sizeof (ctx->block);
digest += sizeof (ctx->block);
- sha3_permute (&ctx->state);
}
if (length > 0)
{
- /* Fill in the buffer for next call. */
+ /* Fill in the buffer. */
_nettle_write_le64 (sizeof (ctx->block), ctx->block, ctx->state.a);
sha3_permute (&ctx->state);
memcpy (digest, ctx->block, length);
- ctx->index = length | INDEX_HIGH_BIT;
}
- else
- ctx->index = sizeof (ctx->block) | INDEX_HIGH_BIT;
+ ctx->index = ~length;
}
--
2.44.0
>From 1dc19a0714d3e58b9fbbe1838137002254ba87c1 Mon Sep 17 00:00:00 2001
From: Daiki Ueno <du...@redhat.com>
Date: Sat, 23 Mar 2024 17:58:21 +0900
Subject: [PATCH 2/3] shake256: Rename sha3_256_shake_output to
sha3_shake256_output
This adds a new family of functions to deal with SHAKE256. The
original sha3_256_shake is deprecated in favor of this, and
re-implemented using the new functions.
Signed-off-by: Daiki Ueno <du...@redhat.com>
---
sha3.h | 36 ++++++++++++++++++++++++++---------
shake256.c | 40 +++++++++++++++++++++++----------------
testsuite/shake256-test.c | 10 +++++-----
3 files changed, 56 insertions(+), 30 deletions(-)
diff --git a/sha3.h b/sha3.h
index 4b7e186c..87cbb879 100644
--- a/sha3.h
+++ b/sha3.h
@@ -49,7 +49,9 @@ 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_shake256_init nettle_sha3_shake256_init
+#define sha3_shake256_update nettle_sha3_shake256_update
+#define sha3_shake256_output nettle_sha3_shake256_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
@@ -91,6 +93,8 @@ sha3_permute (struct sha3_state *state);
#define SHA3_512_DIGEST_SIZE 64
#define SHA3_512_BLOCK_SIZE 72
+#define SHA3_SHAKE256_BLOCK_SIZE SHA3_256_BLOCK_SIZE
+
/* For backwards compatibility */
#define SHA3_224_DATA_SIZE SHA3_224_BLOCK_SIZE
#define SHA3_256_DATA_SIZE SHA3_256_BLOCK_SIZE
@@ -137,17 +141,31 @@ sha3_256_digest(struct sha3_256_ctx *ctx,
size_t length,
uint8_t *digest);
-/* Alternative digest function implementing shake256, with arbitrary
- digest size */
+/* This function is deprecated; consider migrating to sha3_shake256_*
+ interface. */
void
-sha3_256_shake(struct sha3_256_ctx *ctx,
- size_t length,
- uint8_t *digest);
+sha3_256_shake (struct sha3_256_ctx *ctx,
+ size_t length,
+ uint8_t *digest);
+
+/* Alternative interface implementing SHAKE256, with arbitrary digest size. */
+struct sha3_shake256_ctx
+{
+ struct sha3_state state;
+ unsigned index;
+ uint8_t block[SHA3_SHAKE256_BLOCK_SIZE];
+};
+
+void
+sha3_shake256_init (struct sha3_shake256_ctx *ctx);
+
+void
+sha3_shake256_update (struct sha3_shake256_ctx *ctx,
+ size_t length,
+ const uint8_t *data);
-/* 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,
+sha3_shake256_output (struct sha3_shake256_ctx *ctx,
size_t length,
uint8_t *digest);
diff --git a/shake256.c b/shake256.c
index 11d34d5e..879c0935 100644
--- a/shake256.c
+++ b/shake256.c
@@ -49,27 +49,25 @@
#define INDEX_HIGH_BIT (~((UINT_MAX) >> 1))
void
-sha3_256_shake (struct sha3_256_ctx *ctx,
- size_t length,
- uint8_t *dst)
+sha3_shake256_init (struct sha3_shake256_ctx *ctx)
{
- _sha3_pad_shake (&ctx->state, SHA3_256_BLOCK_SIZE, ctx->block, ctx->index);
- while (length > SHA3_256_BLOCK_SIZE)
- {
- _nettle_write_le64 (SHA3_256_BLOCK_SIZE, dst, ctx->state.a);
- length -= SHA3_256_BLOCK_SIZE;
- dst += SHA3_256_BLOCK_SIZE;
- sha3_permute (&ctx->state);
- }
- _nettle_write_le64 (length, dst, ctx->state.a);
+ memset (ctx, 0, offsetof (struct sha3_shake256_ctx, block));
+}
- sha3_256_init (ctx);
+void
+sha3_shake256_update (struct sha3_shake256_ctx *ctx,
+ size_t length,
+ const uint8_t *data)
+{
+ ctx->index = _nettle_sha3_update (&ctx->state,
+ SHA3_256_BLOCK_SIZE, ctx->block,
+ ctx->index, length, data);
}
void
-sha3_256_shake_output (struct sha3_256_ctx *ctx,
- size_t length,
- uint8_t *digest)
+sha3_shake256_output (struct sha3_shake256_ctx *ctx,
+ size_t length,
+ uint8_t *digest)
{
unsigned index, left;
@@ -126,3 +124,13 @@ sha3_256_shake_output (struct sha3_256_ctx *ctx,
}
ctx->index = ~length;
}
+
+void
+sha3_256_shake (struct sha3_256_ctx *ctx,
+ size_t length,
+ uint8_t *dst)
+{
+ struct sha3_shake256_ctx *shake = (struct sha3_shake256_ctx *) ctx;
+ sha3_shake256_output (shake, length, dst);
+ sha3_shake256_init (shake);
+}
diff --git a/testsuite/shake256-test.c b/testsuite/shake256-test.c
index 016060e8..38326466 100644
--- a/testsuite/shake256-test.c
+++ b/testsuite/shake256-test.c
@@ -39,7 +39,7 @@
const struct nettle_hash nettle_shake256 =
{
"shake256",
- sizeof(struct sha3_256_ctx),
+ sizeof(struct sha3_shake256_ctx),
0,
SHA3_256_BLOCK_SIZE,
(nettle_hash_init_func *) sha3_256_init,
@@ -52,18 +52,18 @@ test_incremental (const struct tstring *msg,
const struct tstring *digest,
size_t interval)
{
- struct sha3_256_ctx ctx;
+ struct sha3_shake256_ctx ctx;
size_t offset = 0;
uint8_t *buffer = xalloc (digest->length);
- sha3_256_init (&ctx);
- sha3_256_update (&ctx, msg->length, msg->data);
+ sha3_shake256_init (&ctx);
+ sha3_shake256_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);
+ sha3_shake256_output (&ctx, to_read, buffer + offset);
offset += to_read;
}
--
2.44.0
>From d33ed2d88d41aae20ad2733e19f8bf41a06693a1 Mon Sep 17 00:00:00 2001
From: Daiki Ueno <du...@redhat.com>
Date: Sun, 24 Mar 2024 09:14:40 +0900
Subject: [PATCH 3/3] sha3-shake: Generalize sha3_shake*_output
Signed-off-by: Daiki Ueno <du...@redhat.com>
---
Makefile.in | 2 +-
sha3-internal.h | 7 +++
sha3-shake.c | 111 ++++++++++++++++++++++++++++++++++++++++++++++++
shake256.c | 63 ++-------------------------
4 files changed, 122 insertions(+), 61 deletions(-)
create mode 100644 sha3-shake.c
diff --git a/Makefile.in b/Makefile.in
index f027e762..6953a528 100644
--- a/Makefile.in
+++ b/Makefile.in
@@ -151,7 +151,7 @@ nettle_SOURCES = aes-decrypt-internal.c aes-decrypt.c aes-decrypt-table.c \
sha3.c sha3-permute.c \
sha3-224.c sha3-224-meta.c sha3-256.c sha3-256-meta.c \
sha3-384.c sha3-384-meta.c sha3-512.c sha3-512-meta.c \
- shake256.c \
+ sha3-shake.c shake256.c \
sm3.c sm3-meta.c \
serpent-set-key.c serpent-encrypt.c serpent-decrypt.c \
serpent-meta.c \
diff --git a/sha3-internal.h b/sha3-internal.h
index 9b01231a..f1e5c55b 100644
--- a/sha3-internal.h
+++ b/sha3-internal.h
@@ -56,5 +56,12 @@ _nettle_sha3_pad (struct sha3_state *state,
#define _sha3_pad_shake(state, block_size, block, pos) \
_nettle_sha3_pad (state, block_size, block, pos, SHA3_SHAKE_MAGIC)
+unsigned
+_nettle_sha3_shake_output (struct sha3_state *state,
+ size_t block_size,
+ uint8_t *block,
+ unsigned index,
+ size_t length,
+ uint8_t *digest);
#endif
diff --git a/sha3-shake.c b/sha3-shake.c
new file mode 100644
index 00000000..eb6df3bb
--- /dev/null
+++ b/sha3-shake.c
@@ -0,0 +1,111 @@
+/* sha3-shake.c
+
+ Support function for SHA3 SHAKE XOF.
+
+ Copyright (C) 2024 Red Hat, Inc.
+
+ This file is part of GNU Nettle.
+
+ GNU Nettle is free software: you can redistribute it and/or
+ modify it under the terms of either:
+
+ * the GNU Lesser General Public License as published by the Free
+ Software Foundation; either version 3 of the License, or (at your
+ option) any later version.
+
+ or
+
+ * the GNU General Public License as published by the Free
+ Software Foundation; either version 2 of the License, or (at your
+ option) any later version.
+
+ or both in parallel, as here.
+
+ GNU Nettle is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ General Public License for more details.
+
+ You should have received copies of the GNU General Public License and
+ the GNU Lesser General Public License along with this program. If
+ not, see http://www.gnu.org/licenses/.
+*/
+
+#if HAVE_CONFIG_H
+# include "config.h"
+#endif
+
+#include <assert.h>
+#include <limits.h>
+#include <stddef.h>
+#include <string.h>
+
+#include "sha3.h"
+#include "sha3-internal.h"
+
+#include "nettle-write.h"
+
+#define INDEX_HIGH_BIT (~((UINT_MAX) >> 1))
+
+unsigned
+_nettle_sha3_shake_output (struct sha3_state *state,
+ size_t block_size,
+ uint8_t *block,
+ unsigned index,
+ size_t length,
+ uint8_t *digest)
+{
+ unsigned left;
+
+ /* We use the leftmost bit as a flag to indicate SHAKE is initialized. */
+ if (index & INDEX_HIGH_BIT)
+ index = ~index;
+ else
+ {
+ /* This is the first call of _shake_output. */
+ _sha3_pad_shake (state, block_size, block, index);
+ /* Point at the end of block to trigger fill in of the buffer. */
+ index = 0;
+ }
+
+ assert (index < block_size);
+
+ if (index == 0)
+ {
+ /* Fill in the buffer. */
+ _nettle_write_le64 (block_size, block, state->a);
+ sha3_permute (state);
+ }
+
+ /* Write remaining data from the buffer. */
+ left = block_size - index;
+ if (length <= left)
+ {
+ memcpy (digest, block + index, length);
+ return ~((index + length) % block_size);
+ }
+ else
+ {
+ memcpy (digest, block + index, left);
+ length -= left;
+ digest += left;
+ }
+
+ /* Write full blocks. */
+ while (length >= block_size)
+ {
+ _nettle_write_le64 (block_size, digest, state->a);
+ sha3_permute (state);
+ length -= block_size;
+ digest += block_size;
+ }
+
+ if (length > 0)
+ {
+ /* Fill in the buffer. */
+ _nettle_write_le64 (block_size, block, state->a);
+ sha3_permute (state);
+ memcpy (digest, block, length);
+ }
+ return ~length;
+}
diff --git a/shake256.c b/shake256.c
index 879c0935..9656b4ce 100644
--- a/shake256.c
+++ b/shake256.c
@@ -36,18 +36,12 @@
# include "config.h"
#endif
-#include <assert.h>
-#include <limits.h>
#include <stddef.h>
#include <string.h>
#include "sha3.h"
#include "sha3-internal.h"
-#include "nettle-write.h"
-
-#define INDEX_HIGH_BIT (~((UINT_MAX) >> 1))
-
void
sha3_shake256_init (struct sha3_shake256_ctx *ctx)
{
@@ -69,60 +63,9 @@ sha3_shake256_output (struct sha3_shake256_ctx *ctx,
size_t length,
uint8_t *digest)
{
- unsigned index, left;
-
- /* We use the leftmost bit as a flag to indicate SHAKE is initialized. */
- if (ctx->index & INDEX_HIGH_BIT)
- index = ~ctx->index;
- else
- {
- /* This is the first call of _shake_output. */
- _sha3_pad_shake (&ctx->state, sizeof (ctx->block), ctx->block, ctx->index);
- /* Point at the end of block to trigger fill in of the buffer. */
- index = 0;
- }
-
- assert (index < sizeof (ctx->block));
-
- if (index == 0)
- {
- /* Fill in the buffer. */
- _nettle_write_le64 (sizeof (ctx->block), ctx->block, ctx->state.a);
- sha3_permute (&ctx->state);
- }
-
- /* Write remaining data from the buffer. */
- left = sizeof (ctx->block) - index;
- if (length <= left)
- {
- memcpy (digest, ctx->block + index, length);
- ctx->index = ~((index + length) % sizeof (ctx->block));
- return;
- }
- else
- {
- memcpy (digest, ctx->block + index, left);
- length -= left;
- digest += left;
- }
-
- /* Write full blocks. */
- while (length >= sizeof (ctx->block))
- {
- _nettle_write_le64 (sizeof (ctx->block), digest, ctx->state.a);
- sha3_permute (&ctx->state);
- length -= sizeof (ctx->block);
- digest += sizeof (ctx->block);
- }
-
- if (length > 0)
- {
- /* Fill in the buffer. */
- _nettle_write_le64 (sizeof (ctx->block), ctx->block, ctx->state.a);
- sha3_permute (&ctx->state);
- memcpy (digest, ctx->block, length);
- }
- ctx->index = ~length;
+ ctx->index = _nettle_sha3_shake_output (&ctx->state,
+ SHA3_256_BLOCK_SIZE, ctx->block,
+ ctx->index, length, digest);
}
void
--
2.44.0
_______________________________________________
nettle-bugs mailing list -- nettle-bugs@lists.lysator.liu.se
To unsubscribe send an email to nettle-bugs-le...@lists.lysator.liu.se
