Hello Niels, I am sending you an updated patch. I have resolved all of the issues except for the modulo. Can you please take a look again?
Kind regards, Zoltan On Thu, Sep 1, 2022 at 12:56 PM Niels Möller <[email protected]> wrote: > Zoltan Fridrich <[email protected]> writes: > > >> + r %= mod; > > > >>Division is a pretty expensive operation. If this loop is in any way > >>performance critical, there are ways to speed up this arithmetic. > > > > How would you recommend speeding it up? > > E.g, if m is small enough, you can precompute 0x10000 % m outside of > the loop, something like (totally untested) > > uint32_t two16_mod_m = 0x10000 % mod; > uint32_t r = 0; > unsigned i; > for (i = length; i-- > 0; ) > { > r = (r << 8) + block[i]; > r = (r & 0xffff) + (r >> 16) * two16_mod_m; > } > return r % mod; > > (one needs some analys to ensure that r stays in range and never > overflows; the above is probably not quite right). > > I think one can gain speed by only keeping r partially reduced in the > loop. It's also possible to reduce it completely, but replace division > by multiplication (see https://gmplib.org/~tege/divcnst-pldi94.pdf, > https://gmplib.org/~tege/division-paper.pdf). If the compiler is clever > enough, it could realize that mod is a loop invariant and do that for > you, but I wouldn't count on that. > > The point is that on typical processors, a division instruction can take > 50-100 cycles or more, while a multiplication is typicalle done in 5 > cycles or less. > > >>For consistency, can you see if you can make the interface/function > >>signature closer to the pbkdf2 function (see pbkdf2.h)? It takes a > >>pointer to a mac context, already initialized by the caller (in this > >>case, it would instead be a hash context), function pointers for update > >>and digest, and the digest size. > > > > The closest function signature I can think of would look like this: > > > > void > > balloon(void *hash_ctx, > > nettle_hash_update_func *update, > > nettle_hash_digest_func *digest, > > size_t digest_size, uint *buf, > > size_t s_cost, size_t t_cost, > > size_t passwd_length, const uint8_t *passwd, > > size_t salt_length, const uint8_t *salt, > > size_t length, uint8_t *dst) > > > > But isn't 13 argument function an overkill? > > Would this function signature be ok or would you recommend something > else? > > I agree it's a bit unwieldy, but ok for a low-level primitive. But I > think you can reduce it to 12, since length and digest_size are always > the same, right? > > One can then add wrappers for hash functions of interest, e.g., > balloon_sha256, which would be a bit simper. > > > Good point. I think it might be reasonable for someone to want a buffer > > size of a few GB in extreme cases. > > I can put s_cost and t_cost as size_t. I think there is no harm in doing > > that. Is that ok if I put them as size_t? > > I think that is ok. size_t for cost_s makes sense. I don't know what's > the reasonable value is for cost_t? But makes some sense to stick to the > same type for both cost parameters. > > Regards, > /Niels > > -- > Niels Möller. PGP key CB4962D070D77D7FCB8BA36271D8F1FF368C6677. > Internet email is subject to wholesale government surveillance. > >
diff --color -ruNp a/balloon.c b/balloon.c --- a/balloon.c 1970-01-01 01:00:00.000000000 +0100 +++ b/balloon.c 2022-09-01 16:36:32.301075387 +0200 @@ -0,0 +1,204 @@ +/* balloon.c + + Balloon password-hashing algorithm. + + Copyright (C) 2022 Zoltan Fridrich + + 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/. +*/ + +/* For a description of the algorithm, see: + * Boneh, D., Corrigan-Gibbs, H., Schechter, S. (2017, May 12). Balloon Hashing: + * A Memory-Hard Function Providing Provable Protection Against Sequential Attacks. + * Retrieved Sep 1, 2022, from https://eprint.iacr.org/2016/027.pdf + */ + +#if HAVE_CONFIG_H +# include "config.h" +#endif + +#include <string.h> + +#include "balloon.h" +#include "macros.h" +#include "nettle-internal.h" +#include "sha1.h" +#include "sha2.h" + +#define DELTA 3 + +static void +hash(void *ctx, + nettle_hash_update_func *update, + nettle_hash_digest_func *digest, + size_t digest_size, + uint64_t cnt, + size_t a_len, const uint8_t *a, + size_t b_len, const uint8_t *b, + uint8_t *dst) +{ + uint8_t tmp[8]; + LE_WRITE_UINT64(tmp, cnt); + update(ctx, sizeof(tmp), tmp); + update(ctx, a_len, a); + update(ctx, b_len, b); + digest(ctx, digest_size, dst); +} + +static void +hash_ints(void *ctx, + nettle_hash_update_func *update, + nettle_hash_digest_func *digest, + size_t digest_size, + uint64_t i, uint64_t j, uint64_t k, + uint8_t *dst) +{ + uint8_t tmp[24]; + LE_WRITE_UINT64(tmp, i); + LE_WRITE_UINT64(tmp + 8, j); + LE_WRITE_UINT64(tmp + 16, k); + update(ctx, sizeof(tmp), tmp); + digest(ctx, digest_size, dst); +} + +/* Takes length bytes long big number stored + * in little endian format and computes modulus + */ +static size_t +block_to_int(size_t length, const uint8_t *block, size_t mod) +{ + size_t i = length, r = 0; + while (i--) { + r = (r << 8) + block[i]; + r %= mod; + } + return r; +} + +void +balloon(void *hash_ctx, + nettle_hash_update_func *update, + nettle_hash_digest_func *digest, + size_t digest_size, size_t s_cost, size_t t_cost, + size_t passwd_length, const uint8_t *passwd, + size_t salt_length, const uint8_t *salt, + uint8_t *buf, uint8_t *dst) +{ + uint8_t block[NETTLE_MAX_HASH_DIGEST_SIZE]; + const size_t BS = digest_size; + size_t i, j, k, cnt = 0; + + hash(hash_ctx, update, digest, digest_size, + cnt++, passwd_length, passwd, salt_length, salt, buf); + for (i = 1; i < s_cost; ++i) + hash(hash_ctx, update, digest, digest_size, + cnt++, BS, buf + (i - 1) * BS, 0, NULL, buf + i * BS); + + for (i = 0; i < t_cost; ++i) { + for (j = 0; j < s_cost; ++j) { + hash(hash_ctx, update, digest, digest_size, + cnt++, BS, buf + (j ? j - 1 : s_cost - 1) * BS, + BS, buf + j * BS, buf + j * BS); + for (k = 0; k < DELTA; ++k) { + hash_ints(hash_ctx, update, digest, digest_size, i, j, k, block); + hash(hash_ctx, update, digest, digest_size, + cnt++, salt_length, salt, BS, block, block); + hash(hash_ctx, update, digest, digest_size, + cnt++, BS, buf + j * BS, + BS, buf + block_to_int(BS, block, s_cost) * BS, + buf + j * BS); + } + } + } + memcpy(dst, buf + (s_cost - 1) * BS, BS); +} + +void +balloon_sha1(size_t s_cost, size_t t_cost, + size_t passwd_length, const uint8_t *passwd, + size_t salt_length, const uint8_t *salt, + uint8_t *buf, uint8_t *dst) +{ + struct sha1_ctx ctx; + sha1_init(&ctx); + balloon(&ctx, + (nettle_hash_update_func*)sha1_update, + (nettle_hash_digest_func*)sha1_digest, + SHA1_DIGEST_SIZE, s_cost, t_cost, + passwd_length, passwd, salt_length, salt, buf, dst); +} + +void +balloon_sha256(size_t s_cost, size_t t_cost, + size_t passwd_length, const uint8_t *passwd, + size_t salt_length, const uint8_t *salt, + uint8_t *buf, uint8_t *dst) +{ + struct sha256_ctx ctx; + sha256_init(&ctx); + balloon(&ctx, + (nettle_hash_update_func*)sha256_update, + (nettle_hash_digest_func*)sha256_digest, + SHA256_DIGEST_SIZE, s_cost, t_cost, + passwd_length, passwd, salt_length, salt, buf, dst); +} + +void +balloon_sha384(size_t s_cost, size_t t_cost, + size_t passwd_length, const uint8_t *passwd, + size_t salt_length, const uint8_t *salt, + uint8_t *buf, uint8_t *dst) +{ + struct sha384_ctx ctx; + sha384_init(&ctx); + balloon(&ctx, + (nettle_hash_update_func*)sha384_update, + (nettle_hash_digest_func*)sha384_digest, + SHA384_DIGEST_SIZE, s_cost, t_cost, + passwd_length, passwd, salt_length, salt, buf, dst); +} + +void +balloon_sha512(size_t s_cost, size_t t_cost, + size_t passwd_length, const uint8_t *passwd, + size_t salt_length, const uint8_t *salt, + uint8_t *buf, uint8_t *dst) +{ + struct sha512_ctx ctx; + sha512_init(&ctx); + balloon(&ctx, + (nettle_hash_update_func*)sha512_update, + (nettle_hash_digest_func*)sha512_digest, + SHA512_DIGEST_SIZE, s_cost, t_cost, + passwd_length, passwd, salt_length, salt, buf, dst); +} + +size_t +balloon_itch(size_t digest_size, size_t s_cost) +{ + return s_cost * digest_size; +} diff --color -ruNp a/balloon.h b/balloon.h --- a/balloon.h 1970-01-01 01:00:00.000000000 +0100 +++ b/balloon.h 2022-09-01 15:35:11.786615951 +0200 @@ -0,0 +1,97 @@ +/* balloon.h + + Balloon password-hashing algorithm. + + Copyright (C) 2022 Zoltan Fridrich + + 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/. +*/ + +/* For a description of the algorithm, see: + * Boneh, D., Corrigan-Gibbs, H., Schechter, S. (2017, May 12). Balloon Hashing: + * A Memory-Hard Function Providing Provable Protection Against Sequential Attacks. + * Retrieved Sep 1, 2022, from https://eprint.iacr.org/2016/027.pdf + */ + +#ifndef NETTLE_BALLOON_H_INCLUDED +#define NETTLE_BALLOON_H_INCLUDED + +#include "nettle-types.h" + +#ifdef __cplusplus +extern "C" { +#endif + +/* Name mangling */ +#define balloon nettle_balloon +#define balloon_sha1 nettle_balloon_sha1 +#define balloon_sha256 nettle_balloon_sha256 +#define balloon_sha384 nettle_balloon_sha384 +#define balloon_sha512 nettle_balloon_sha512 +#define balloon_itch nettle_balloon_itch + +void +balloon(void *hash_ctx, + nettle_hash_update_func *update, + nettle_hash_digest_func *digest, + size_t digest_size, size_t s_cost, size_t t_cost, + size_t passwd_length, const uint8_t *passwd, + size_t salt_length, const uint8_t *salt, + uint8_t *buf, uint8_t *dst); + +void +balloon_sha1(size_t s_cost, size_t t_cost, + size_t passwd_length, const uint8_t *passwd, + size_t salt_length, const uint8_t *salt, + uint8_t *buf, uint8_t *dst); + +void +balloon_sha256(size_t s_cost, size_t t_cost, + size_t passwd_length, const uint8_t *passwd, + size_t salt_length, const uint8_t *salt, + uint8_t *buf, uint8_t *dst); + +void +balloon_sha384(size_t s_cost, size_t t_cost, + size_t passwd_length, const uint8_t *passwd, + size_t salt_length, const uint8_t *salt, + uint8_t *buf, uint8_t *dst); + +void +balloon_sha512(size_t s_cost, size_t t_cost, + size_t passwd_length, const uint8_t *passwd, + size_t salt_length, const uint8_t *salt, + uint8_t *buf, uint8_t *dst); + +size_t +balloon_itch(size_t digest_size, size_t s_cost); + +#ifdef __cplusplus +} +#endif + +#endif /* NETTLE_BALLOON_H_INCLUDED */ diff --color -ruNp a/Makefile.in b/Makefile.in --- a/Makefile.in 2022-08-03 15:22:54.207789385 +0200 +++ b/Makefile.in 2022-08-18 16:18:39.330463813 +0200 @@ -82,7 +82,7 @@ nettle_SOURCES = aes-decrypt-internal.c aes256-meta.c \ nist-keywrap.c \ arcfour.c arcfour-crypt.c \ - arctwo.c arctwo-meta.c blowfish.c blowfish-bcrypt.c \ + arctwo.c arctwo-meta.c balloon.c blowfish.c blowfish-bcrypt.c \ base16-encode.c base16-decode.c base16-meta.c \ base64-encode.c base64-decode.c base64-meta.c \ base64url-encode.c base64url-decode.c base64url-meta.c \ @@ -218,7 +218,7 @@ hogweed_SOURCES = sexp.c sexp-format.c \ OPT_SOURCES = fat-arm.c fat-arm64.c fat-ppc.c fat-s390x.c fat-x86_64.c mini-gmp.c -HEADERS = aes.h arcfour.h arctwo.h asn1.h blowfish.h \ +HEADERS = aes.h arcfour.h arctwo.h asn1.h balloon.h blowfish.h \ base16.h base64.h bignum.h buffer.h camellia.h cast128.h \ cbc.h ccm.h cfb.h chacha.h chacha-poly1305.h ctr.h \ curve25519.h curve448.h des.h dsa.h dsa-compat.h eax.h \ diff --color -ruNp a/testsuite/balloon-test.c b/testsuite/balloon-test.c --- a/testsuite/balloon-test.c 1970-01-01 01:00:00.000000000 +0100 +++ b/testsuite/balloon-test.c 2022-09-01 15:32:14.918074418 +0200 @@ -0,0 +1,88 @@ +/* balloon-test.c + + Copyright (C) 2022 Zoltan Fridrich + + 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/. +*/ + +#include "testutils.h" +#include "balloon.h" +#include "nettle-internal.h" + +static void +test_balloon(const struct nettle_hash *alg, + size_t password_len, const char *password, + size_t salt_len, const char *salt, + unsigned s_cost, unsigned t_cost, + const struct tstring *expected) +{ + int fail = 0; + void *ctx = xalloc(alg->context_size); + uint8_t *buf = xalloc(balloon_itch(alg->digest_size, s_cost)); + uint8_t hash[NETTLE_MAX_HASH_DIGEST_SIZE]; + + alg->init(ctx); + balloon(ctx, alg->update, alg->digest, alg->digest_size, + s_cost, t_cost, password_len, (const uint8_t *)password, + salt_len, (const uint8_t *)salt, buf, hash); + + if (!MEMEQ(alg->digest_size, hash, expected->data)) { + fprintf(stderr, "test_balloon: result doesn't match the expectation:"); + fprintf(stderr, "\nOutput: "); + print_hex(alg->digest_size, hash); + fprintf(stderr, "\nExpected:"); + tstring_print_hex(expected); + fprintf(stderr, "\n"); + fail = 1; + } + + free(ctx); + free(buf); + + if (fail) + FAIL(); +} + +/* + * Test vectors are taken from: + * <https://github.com/nachonavarro/balloon-hashing> + * <https://github.com/RustCrypto/password-hashes/tree/master/balloon-hash> + */ +void +test_main(void) +{ + test_balloon(&nettle_sha256, 8, "hunter42", 11, "examplesalt", 1024, 3, + SHEX("716043dff777b44aa7b88dcbab12c078abecfac9d289c5b5195967aa63440dfb")); + test_balloon(&nettle_sha256, 0, "", 4, "salt", 3, 3, + SHEX("5f02f8206f9cd212485c6bdf85527b698956701ad0852106f94b94ee94577378")); + test_balloon(&nettle_sha256, 8, "password", 0, "", 3, 3, + SHEX("20aa99d7fe3f4df4bd98c655c5480ec98b143107a331fd491deda885c4d6a6cc")); + test_balloon(&nettle_sha256, 1, "", 1, "", 3, 3, + SHEX("4fc7e302ffa29ae0eac31166cee7a552d1d71135f4e0da66486fb68a749b73a4")); + test_balloon(&nettle_sha256, 8, "password", 4, "salt", 1, 1, + SHEX("eefda4a8a75b461fa389c1dcfaf3e9dfacbc26f81f22e6f280d15cc18c417545")); +} diff --color -ruNp a/testsuite/.gitignore b/testsuite/.gitignore --- a/testsuite/.gitignore 2022-08-03 15:22:54.246790154 +0200 +++ b/testsuite/.gitignore 2022-08-03 16:37:44.331951753 +0200 @@ -4,6 +4,7 @@ /aes-keywrap-test /arcfour-test /arctwo-test +/balloon-test /base16-test /base64-test /bignum-test diff --color -ruNp a/testsuite/Makefile.in b/testsuite/Makefile.in --- a/testsuite/Makefile.in 2022-08-03 15:22:54.246790154 +0200 +++ b/testsuite/Makefile.in 2022-08-03 16:39:17.725784157 +0200 @@ -11,7 +11,7 @@ PRE_CPPFLAGS = -I.. -I$(top_srcdir) PRE_LDFLAGS = -L.. TS_NETTLE_SOURCES = aes-test.c aes-keywrap-test.c arcfour-test.c arctwo-test.c \ - blowfish-test.c bcrypt-test.c cast128-test.c \ + balloon-test.c blowfish-test.c bcrypt-test.c cast128-test.c \ base16-test.c base64-test.c \ camellia-test.c chacha-test.c \ cnd-memcpy-test.c \
_______________________________________________ nettle-bugs mailing list -- [email protected] To unsubscribe send an email to [email protected]
