Hello, It is based on this paper https://eprint.iacr.org/2016/027.pdf Thank you for your review. I have updated the patch.
1. balloon_set_hash_alg() function is gone. Now the user provides a hash algorithm via argument. 2. I have changed the helper functions a bit and I used stack allocation for all local variables, no more heap allocation. 3. Now the user has to provide a working buffer via argument. I have added the function balloon_buf_size() that returns the necessary size of the buffer. Attaching updated patch. Kind regards, Zoltan On Fri, Aug 19, 2022 at 10:06 AM Niels Möller <ni...@lysator.liu.se> wrote: > Zoltan Fridrich <zfrid...@redhat.com> writes: > > > I would like to contribute an implementation of the balloon hashing > > algorithm to Nettle. > > Please provide some information about use cases and which specification > it is based on. (I only had a quick look at wikipedia and the > https://eprint.iacr.org/2016/027 paper, to get some context). > > > I am aware that the code does not have proper Nettle formatting, I will > > change that after the patch will be in an acceptable state. Could you > > please provide feedback on the patch? Thank you. > > A few initial comments: > > 1. The balloon_set_hash_alg implies global state, which isn't good in a > library. It's better to pass the const struct nettle_hash *hash_alg > as an argument to the balloon function. > > 2. For allocating smallish items like the hashing context, use stack > allocation. Using the TMP_DECL, TMP_ALLOC macros (when size is > bounded but determined at runtime), of if constant, a plain > > uint8_t data[3*sizeof(i)]; > > instead of > > uint8_t *data = xalloc(3 * sizeof(i)); > > For the hashing context, if only one is needed, it would be better to > allocate in the top-level baloon function, instead of allocating and > freeing in the hash utility function. > > Or in this particular case, one could also consider using > > uint64_t data[3]; > > plus endian-dependent byteswapping when writing the values. As I > understand it, if this part isn't performance critical, style should > be chosen based on what makes the code clearest. > > 3. For allocating the working storage, which as I understand it can be > intentionally pretty large, using xalloc isn't so nice. It would be > more inline with nettle design to leave to the application to > allocate the storage and pass in. You can then provide a function or > macro the application can use to determine needed size. > > 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-08-19 11:11:11.591188729 +0200 @@ -0,0 +1,127 @@ +/* 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/. +*/ + +#if HAVE_CONFIG_H +# include "config.h" +#endif + +#include <string.h> + +#include "balloon.h" +#include "macros.h" +#include "nettle-internal.h" + +#define DELTA 3 + +static inline void +hash(const struct nettle_hash *alg, + uint64_t cnt, + size_t a_len, const uint8_t *a, + size_t b_len, const uint8_t *b, + uint8_t *result) +{ + uint8_t ctx[NETTLE_MAX_HASH_CONTEXT_SIZE]; + uint8_t tmp[sizeof(uint64_t)]; + + alg->init(ctx); + LE_WRITE_UINT64(tmp, cnt); + alg->update(ctx, sizeof(tmp), tmp); + alg->update(ctx, a_len, a); + alg->update(ctx, b_len, b); + alg->digest(ctx, alg->digest_size, result); +} + +static inline void +hash_ints(const struct nettle_hash *alg, + uint64_t i, uint64_t j, uint64_t k, uint8_t *result) +{ + uint8_t ctx[NETTLE_MAX_HASH_CONTEXT_SIZE]; + uint8_t tmp[sizeof(uint64_t)]; + + alg->init(ctx); + LE_WRITE_UINT64(tmp, i); + alg->update(ctx, sizeof(tmp), tmp); + LE_WRITE_UINT64(tmp, j); + alg->update(ctx, sizeof(tmp), tmp); + LE_WRITE_UINT64(tmp, k); + alg->update(ctx, sizeof(tmp), tmp); + alg->digest(ctx, alg->digest_size, result); +} + +static inline unsigned +block_to_int(size_t length, const uint8_t *block, unsigned mod) +{ + unsigned r = 0; + + for (int i = length - 1; i >= 0; --i) { + r <<= 8; + r += (block[i] & 0xFF); + r %= mod; + } + return r; +} + +void +balloon(size_t passwd_len, const uint8_t *passwd, + size_t salt_len, const uint8_t *salt, + unsigned s_cost, unsigned t_cost, + const struct nettle_hash *alg, + uint8_t *buf, uint8_t *result) +{ + uint8_t block[NETTLE_MAX_HASH_DIGEST_SIZE]; + const unsigned BS = alg->digest_size; + unsigned i, j, k, cnt = 0; + + hash(alg, cnt++, passwd_len, passwd, salt_len, salt, buf); + for (i = 1; i < s_cost; ++i) + hash(alg, 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(alg, 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(alg, i, j, k, block); + hash(alg, cnt++, salt_len, salt, BS, block, block); + hash(alg, cnt++, BS, buf + j * BS, + BS, buf + block_to_int(BS, block, s_cost) * BS, + buf + j * BS); + } + } + } + memcpy(result, buf + (s_cost - 1) * BS, BS); +} + +size_t +balloon_buf_size(const struct nettle_hash *alg, unsigned s_cost) +{ + return s_cost * alg->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-08-19 11:00:04.057815450 +0200 @@ -0,0 +1,59 @@ +/* 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/. +*/ + +#ifndef NETTLE_BALLOON_H_INCLUDED +#define NETTLE_BALLOON_H_INCLUDED + +#include "nettle-meta.h" + +#ifdef __cplusplus +extern "C" { +#endif + +/* Name mangling */ +#define balloon nettle_balloon +#define balloon_buf_size nettle_balloon_buf_size + +void +balloon(size_t passwd_len, const uint8_t *passwd, + size_t salt_len, const uint8_t *salt, + unsigned s_cost, unsigned t_cost, + const struct nettle_hash *alg, + uint8_t *buf, uint8_t *result); + +size_t +balloon_buf_size(const struct nettle_hash *alg, unsigned 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-08-19 10:57:18.966504697 +0200 @@ -0,0 +1,75 @@ +/* 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 inline void +test_balloon(size_t password_len, const char *password, + size_t salt_len, const char *salt, + unsigned s_cost, unsigned t_cost, + const struct nettle_hash *alg, const struct tstring *expected) +{ + uint8_t hash[NETTLE_MAX_HASH_DIGEST_SIZE]; + uint8_t *buf = xalloc(balloon_buf_size(alg, s_cost)); + + balloon(password_len, (const uint8_t *)password, + salt_len, (const uint8_t *)salt, + s_cost, t_cost, alg, 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"); + free(buf); + FAIL(); + } + free(buf); +} + +void +test_main(void) +{ + test_balloon(8, "hunter42", 11, "examplesalt", 1024, 3, &nettle_sha256, + SHEX("716043dff777b44aa7b88dcbab12c078abecfac9d289c5b5195967aa63440dfb")); + test_balloon(0, "", 4, "salt", 3, 3, &nettle_sha256, + SHEX("5f02f8206f9cd212485c6bdf85527b698956701ad0852106f94b94ee94577378")); + test_balloon(8, "password", 0, "", 3, 3, &nettle_sha256, + SHEX("20aa99d7fe3f4df4bd98c655c5480ec98b143107a331fd491deda885c4d6a6cc")); + test_balloon(1, "", 1, "", 3, 3, &nettle_sha256, + SHEX("4fc7e302ffa29ae0eac31166cee7a552d1d71135f4e0da66486fb68a749b73a4")); + test_balloon(8, "password", 4, "salt", 1, 1, &nettle_sha256, + 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 -- nettle-bugs@lists.lysator.liu.se To unsubscribe send an email to nettle-bugs-le...@lists.lysator.liu.se
