From 08ab32228ad20fd730979d700bf46b18e469703c Mon Sep 17 00:00:00 2001 From: NIIBE Yutaka Date: Mon, 7 Feb 2022 14:06:33 +0900 Subject: kdf: Add experimental Balloon KDF. * cipher/kdf.c (prng_aes_ctr_init, prng_aes_ctr_get_rand64): New. (prng_aes_ctr_fini, ballon_context_size): New. (balloon_open): Implement with SHA-256. (balloon_xor_block, balloon_compress, balloon_expand): New. (balloon_compute_fill, balloon_compute_mix, balloon_compute): New. (balloon_compute_all, balloon_final, balloon_close): New. (_gcry_kdf_open): Check argument for GCRY_KDF_BALLOON. (_gcry_kdf_compute): Dispatch for GCRY_KDF_BALLOON. (_gcry_kdf_final, _gcry_kdf_close): Likewise. * tests/t-kdf.c (check_balloon): New. (main): Add check_balloon. -- GnuPG-bug-id: 5817 Signed-off-by: NIIBE Yutaka --- cipher/kdf.c | 451 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++-- tests/t-kdf.c | 122 +++++++++++++++- 2 files changed, 557 insertions(+), 16 deletions(-) diff --git a/cipher/kdf.c b/cipher/kdf.c index edff5597..04a8421a 100644 --- a/cipher/kdf.c +++ b/cipher/kdf.c @@ -877,29 +877,446 @@ argon2_open (gcry_kdf_hd_t *hd, int subalgo, *hd = (void *)a; return 0; } + +typedef struct balloon_context *balloon_ctx_t; + +/* Per thread data for Balloon. */ +struct balloon_thread_data { + balloon_ctx_t b; + gpg_err_code_t ec; + unsigned int idx; + unsigned char *block; +}; + +/* Balloon context */ +struct balloon_context { + int algo; + int hash_type; + int prng_type; + + unsigned int blklen; + gcry_md_spec_t md_spec; + + const unsigned char *password; + size_t passwordlen; + + const unsigned char *salt; + /* Length of salt is fixed. */ + + unsigned int s_cost; + unsigned int t_cost; + unsigned int parallelism; + + u64 n_blocks; + + unsigned char *block; + + /* In future, we may use flexible array member. */ + struct balloon_thread_data thread_data[1]; +}; + +/* Maximum size of underlining sigest size. */ +#define BALLOON_SALT_LEN_MAX 64 + +static gpg_err_code_t +prng_aes_ctr_init (gcry_cipher_hd_t *hd_p, balloon_ctx_t b, + gcry_buffer_t *iov, unsigned int iov_count) +{ + gpg_err_code_t ec; + gcry_cipher_hd_t hd; + unsigned char key[BALLOON_SALT_LEN_MAX]; + b->md_spec.hash_buffers (key, b->blklen, iov, iov_count); + ec = _gcry_cipher_open (&hd, GCRY_CIPHER_AES, GCRY_CIPHER_MODE_CTR, 0); + if (ec) + return ec; + + ec = _gcry_cipher_setkey (hd, key, 16); + if (ec) + { + _gcry_cipher_close (hd); + return ec; + } + + wipememory (key, 32); + *hd_p = hd; + return ec; +} + +static u64 +prng_aes_ctr_get_rand64 (gcry_cipher_hd_t hd) +{ + static const unsigned char zero64[8]; + unsigned char rand64[8]; + + _gcry_cipher_encrypt (hd, rand64, sizeof (rand64), zero64, sizeof (zero64)); + return buf_get_le64 (rand64); +} + +static void +prng_aes_ctr_fini (gcry_cipher_hd_t hd) +{ + _gcry_cipher_close (hd); +} + +static size_t +ballon_context_size (unsigned int parallelism) +{ + size_t n; + + n = offsetof (struct balloon_context, thread_data) + + parallelism * sizeof (struct balloon_thread_data); + return n; +} static gpg_err_code_t balloon_open (gcry_kdf_hd_t *hd, int subalgo, const unsigned long *param, unsigned int paramlen, - const void *passphrase, size_t passphraselen, + const void *password, size_t passwordlen, const void *salt, size_t saltlen) { + unsigned int blklen; + int hash_type; + unsigned int s_cost; + unsigned int t_cost; + unsigned int parallelism = 1; + balloon_ctx_t b; + gpg_err_code_t ec; + size_t n; + unsigned char *block; + unsigned int i; + gcry_md_spec_t md_spec; + + /* For now, only SHA256 is supported. */ + if (subalgo != GCRY_MD_SHA256) + return GPG_ERR_NOT_SUPPORTED; + else + { + hash_type = subalgo; + md_spec = _gcry_digest_spec_sha256; + } + + blklen = _gcry_md_get_algo_dlen (hash_type); + if (!blklen || blklen > BALLOON_SALT_LEN_MAX) + return GPG_ERR_NOT_SUPPORTED; + + if (saltlen != blklen) + return GPG_ERR_NOT_SUPPORTED; + /* * It should have space_cost and time_cost. * Optionally, for parallelised version, it has parallelism. + * Possibly (in future), it may have options for PRNG. */ if (paramlen != 2 && paramlen != 3) return GPG_ERR_INV_VALUE; + else + { + s_cost = (unsigned int)param[0]; + t_cost = (unsigned int)param[1]; + if (paramlen >= 3) + parallelism = (unsigned int)param[2]; + } + + if (s_cost < 1) + return GPG_ERR_INV_VALUE; + + n = ballon_context_size (parallelism); + b = xtrymalloc (n); + if (!b) + return gpg_err_code_from_errno (errno); + + b->algo = GCRY_KDF_BALLOON; + b->hash_type = hash_type; + b->md_spec = md_spec; + b->blklen = blklen; + + b->password = password; + b->passwordlen = passwordlen; + b->salt = salt; + + b->s_cost = s_cost; + b->t_cost = t_cost; + b->parallelism = parallelism; + + b->n_blocks = (s_cost * 1024) / b->blklen; - (void)param; - (void)subalgo; - (void)passphrase; - (void)passphraselen; - (void)salt; - (void)saltlen; - *hd = NULL; - return GPG_ERR_NOT_IMPLEMENTED; + block = xtrycalloc (parallelism * b->n_blocks, b->blklen); + if (!block) + { + ec = gpg_err_code_from_errno (errno); + xfree (b); + return ec; + } + b->block = block; + + for (i = 0; i < parallelism; i++) + { + struct balloon_thread_data *t = &b->thread_data[i]; + + t->b = b; + t->ec = 0; + t->idx = i; + t->block = block; + block += b->blklen * b->n_blocks; + } + + *hd = (void *)b; + return 0; +} + + +static void +balloon_xor_block (balloon_ctx_t b, u64 *dst, const u64 *src) +{ + int i; + + for (i = 0; i < b->blklen/8; i++) + dst[i] ^= src[i]; +} + +#define BALLOON_COMPRESS_BLOCKS 5 + +static void +balloon_compress (balloon_ctx_t b, u64 *counter_p, unsigned char *out, + const unsigned char *blocks[BALLOON_COMPRESS_BLOCKS]) +{ + gcry_buffer_t iov[1+BALLOON_COMPRESS_BLOCKS]; + unsigned char octet_counter[sizeof (u64)]; + unsigned int i; + + buf_put_le64 (octet_counter, *counter_p); + iov[0].data = octet_counter; + iov[0].len = sizeof (octet_counter); + iov[0].off = 0; + + for (i = 1; i < 1+BALLOON_COMPRESS_BLOCKS; i++) + { + iov[i].data = (void *)blocks[i-1]; + iov[i].len = b->blklen; + iov[i].off = 0; + } + + b->md_spec.hash_buffers (out, b->blklen, iov, 1+BALLOON_COMPRESS_BLOCKS); + *counter_p += 1; +} + +static void +balloon_expand (balloon_ctx_t b, u64 *counter_p, unsigned char *block, + u64 n_blocks) +{ + gcry_buffer_t iov[2]; + unsigned char octet_counter[sizeof (u64)]; + u64 i; + + iov[0].data = octet_counter; + iov[0].len = sizeof (octet_counter); + iov[0].off = 0; + iov[1].len = b->blklen; + iov[1].off = 0; + + for (i = 1; i < n_blocks; i++) + { + buf_put_le64 (octet_counter, *counter_p); + iov[1].data = block; + block += b->blklen; + b->md_spec.hash_buffers (block, b->blklen, iov, 2); + *counter_p += 1; + } +} + +static void +balloon_compute_fill (balloon_ctx_t b, + struct balloon_thread_data *t, + const unsigned char *salt, + u64 *counter_p) +{ + gcry_buffer_t iov[6]; + unsigned char octet_counter[sizeof (u64)]; + unsigned char octet_s_cost[4]; + unsigned char octet_t_cost[4]; + unsigned char octet_parallelism[4]; + + buf_put_le64 (octet_counter, *counter_p); + buf_put_le32 (octet_s_cost, b->s_cost); + buf_put_le32 (octet_t_cost, b->t_cost); + buf_put_le32 (octet_parallelism, b->parallelism); + + iov[0].data = octet_counter; + iov[0].len = sizeof (octet_counter); + iov[0].off = 0; + iov[1].data = (void *)salt; + iov[1].len = b->blklen; + iov[1].off = 0; + iov[2].data = (void *)b->password; + iov[2].len = b->passwordlen; + iov[2].off = 0; + iov[3].data = octet_s_cost; + iov[3].len = 4; + iov[3].off = 0; + iov[4].data = octet_t_cost; + iov[4].len = 4; + iov[4].off = 0; + iov[5].data = octet_parallelism; + iov[5].len = 4; + iov[5].off = 0; + b->md_spec.hash_buffers (t->block, b->blklen, iov, 6); + *counter_p += 1; + balloon_expand (b, counter_p, t->block, b->n_blocks); +} + +static void +balloon_compute_mix (gcry_cipher_hd_t prng, + balloon_ctx_t b, struct balloon_thread_data *t, + u64 *counter_p) +{ + u64 i; + + for (i = 0; i < b->n_blocks; i++) + { + unsigned char *cur_block = t->block + (b->blklen * i); + const unsigned char *blocks[BALLOON_COMPRESS_BLOCKS]; + const unsigned char *prev_block; + unsigned int n; + + prev_block = i + ? cur_block - b->blklen + : t->block + (b->blklen * (t->b->n_blocks - 1)); + + n = 0; + blocks[n++] = prev_block; + blocks[n++] = cur_block; + + for (; n < BALLOON_COMPRESS_BLOCKS; n++) + { + u64 rand64 = prng_aes_ctr_get_rand64 (prng); + blocks[n] = t->block + (b->blklen * (rand64 % b->n_blocks)); + } + + balloon_compress (b, counter_p, cur_block, blocks); + } +} + + +static void +balloon_compute (void *priv) +{ + struct balloon_thread_data *t = (struct balloon_thread_data *)priv; + balloon_ctx_t b = t->b; + gcry_cipher_hd_t prng; + gcry_buffer_t iov[4]; + unsigned char salt[BALLOON_SALT_LEN_MAX]; + unsigned char octet_s_cost[4]; + unsigned char octet_t_cost[4]; + unsigned char octet_parallelism[4]; + u32 u; + u64 counter; + unsigned int i; + + counter = 0; + + memcpy (salt, b->salt, b->blklen); + u = buf_get_le32 (b->salt) + t->idx; + buf_put_le32 (salt, u); + + buf_put_le32 (octet_s_cost, b->s_cost); + buf_put_le32 (octet_t_cost, b->t_cost); + buf_put_le32 (octet_parallelism, b->parallelism); + + iov[0].data = salt; + iov[0].len = b->blklen; + iov[0].off = 0; + iov[1].data = octet_s_cost; + iov[1].len = 4; + iov[1].off = 0; + iov[2].data = octet_t_cost; + iov[2].len = 4; + iov[2].off = 0; + iov[3].data = octet_parallelism; + iov[3].len = 4; + iov[3].off = 0; + + t->ec = prng_aes_ctr_init (&prng, b, iov, 4); + if (t->ec) + return; + + balloon_compute_fill (b, t, salt, &counter); + + for (i = 0; i < b->t_cost; i++) + balloon_compute_mix (prng, b, t, &counter); + + /* The result is now at the last block. */ + + prng_aes_ctr_fini (prng); +} + +static gpg_err_code_t +balloon_compute_all (balloon_ctx_t b, const struct gcry_kdf_thread_ops *ops) +{ + unsigned int parallelism = b->parallelism; + unsigned int i; + int ret; + + for (i = 0; i < parallelism; i++) + { + struct balloon_thread_data *t = &b->thread_data[i]; + + if (ops) + { + ret = ops->dispatch_job (ops->jobs_context, balloon_compute, t); + if (ret < 0) + return GPG_ERR_CANCELED; + } + else + balloon_compute (t); + } + + if (ops) + { + ret = ops->wait_all_jobs (ops->jobs_context); + if (ret < 0) + return GPG_ERR_CANCELED; + } + + return 0; +} + +static gpg_err_code_t +balloon_final (balloon_ctx_t b, size_t resultlen, void *result) +{ + unsigned int parallelism = b->parallelism; + unsigned int i; + + if (resultlen != b->blklen) + return GPG_ERR_INV_VALUE; + + memset (result, 0, b->blklen); + for (i = 0; i < parallelism; i++) + { + struct balloon_thread_data *t = &b->thread_data[i]; + const unsigned char *last_block; + + last_block = t->block + (b->blklen * (t->b->n_blocks - 1)); + balloon_xor_block (b, result, (u64 *)last_block); + } + + return 0; +} + +static void +balloon_close (balloon_ctx_t b) +{ + unsigned int parallelism = b->parallelism; + size_t n = ballon_context_size (parallelism); + + if (b->block) + { + wipememory (b->block, parallelism * b->n_blocks); + xfree (b->block); + } + + wipememory (b, n); + xfree (b); } @@ -930,14 +1347,12 @@ _gcry_kdf_open (gcry_kdf_hd_t *hd, int algo, int subalgo, break; case GCRY_KDF_BALLOON: - if (!passphraselen || !saltlen) + if (!passphraselen || !saltlen || keylen || adlen) ec = GPG_ERR_INV_VALUE; else { (void)key; - (void)keylen; (void)ad; - (void)adlen; ec = balloon_open (hd, subalgo, param, paramlen, passphrase, passphraselen, salt, saltlen); } @@ -962,6 +1377,10 @@ _gcry_kdf_compute (gcry_kdf_hd_t h, const struct gcry_kdf_thread_ops *ops) ec = argon2_compute ((argon2_ctx_t)h, ops); break; + case GCRY_KDF_BALLOON: + ec = balloon_compute_all ((balloon_ctx_t)h, ops); + break; + default: ec = GPG_ERR_UNKNOWN_ALGORITHM; break; @@ -982,6 +1401,10 @@ _gcry_kdf_final (gcry_kdf_hd_t h, size_t resultlen, void *result) ec = argon2_final ((argon2_ctx_t)h, resultlen, result); break; + case GCRY_KDF_BALLOON: + ec = balloon_final ((balloon_ctx_t)h, resultlen, result); + break; + default: ec = GPG_ERR_UNKNOWN_ALGORITHM; break; @@ -999,6 +1422,10 @@ _gcry_kdf_close (gcry_kdf_hd_t h) argon2_close ((argon2_ctx_t)h); break; + case GCRY_KDF_BALLOON: + balloon_close ((balloon_ctx_t)h); + break; + default: break; } diff --git a/tests/t-kdf.c b/tests/t-kdf.c index 4c82fed8..234bbac6 100644 --- a/tests/t-kdf.c +++ b/tests/t-kdf.c @@ -1451,10 +1451,10 @@ check_argon2 (void) pass, 32, salt, 16, key, 8, ad, 12, 32, out); if (err) - fail ("argon2 test %d failed: %s\n", 0, gpg_strerror (err)); + fail ("argon2 test %d failed: %s\n", count*2+0, gpg_strerror (err)); else if (memcmp (out, expected[count], 32)) { - fail ("argon2 test %d failed: mismatch\n", 0); + fail ("argon2 test %d failed: mismatch\n", count*2+0); fputs ("got:", stderr); for (i=0; i < 32; i++) fprintf (stderr, " %02x", out[i]); @@ -1467,10 +1467,10 @@ check_argon2 (void) pass, 32, salt, 16, key, 8, ad, 12, 32, out); if (err) - fail ("argon2 test %d failed: %s\n", 1, gpg_strerror (err)); + fail ("argon2 test %d failed: %s\n", count*2+1, gpg_strerror (err)); else if (memcmp (out, expected[count], 32)) { - fail ("argon2 test %d failed: mismatch\n", 1); + fail ("argon2 test %d failed: mismatch\n", count*2+1); fputs ("got:", stderr); for (i=0; i < 32; i++) fprintf (stderr, " %02x", out[i]); @@ -1490,6 +1490,119 @@ check_argon2 (void) } +static void +check_balloon (void) +{ + /* Two test vectors generated by the research prototype implementation. + $ balloon abcdefghijklmno + t_cost = 1 + s_cost = 1024 + p_cost = 1 + passwd = abcdefghijklmno + Time total : 0.0527251 + Hashes per sec : 18.9663 + Output : $balloon$v=1$s=1024,t=1,p=1 + $FRzqOiIuPvuoy55vGfKzyse+2f28F7m9iFHCctnEBwg= + $NxOGNPyTPZzKiJjgj7H6pJDLIgR05HI7VaxJpxEao5Q= + $ balloon -t 12 -s 4096 -p 4 Long_sentence_used_as_passphrase + t_cost = 12 + s_cost = 4096 + p_cost = 4 + passwd = Long_sentence_used_as_passphrase + Time total : 3.70399 + Hashes per sec : 0.269979 + Output : $balloon$v=1$s=4096,t=12,p=4 + $8Yor74EqTwBrrdaeYeSVx0VXVAgDrsILAnJWdVUy93s= + $FaNb9ofeWEggzhW9BUSODgZH5/awzNz5Adoub48+BgQ= + */ + gcry_error_t err; + const unsigned long param[2][4] = { + { 1024, 1, 1 }, + { 4096, 12, 4 } + }; + const unsigned char *pass[2] = { + (const unsigned char *)"abcdefghijklmno", + (const unsigned char *)"Long_sentence_used_as_passphrase" + }; + const unsigned char salt[2][32] = { + { + 0x15, 0x1c, 0xea, 0x3a, 0x22, 0x2e, 0x3e, 0xfb, + 0xa8, 0xcb, 0x9e, 0x6f, 0x19, 0xf2, 0xb3, 0xca, + 0xc7, 0xbe, 0xd9, 0xfd, 0xbc, 0x17, 0xb9, 0xbd, + 0x88, 0x51, 0xc2, 0x72, 0xd9, 0xc4, 0x07, 0x08 + }, + { + 0xf1, 0x8a, 0x2b, 0xef, 0x81, 0x2a, 0x4f, 0x00, + 0x6b, 0xad, 0xd6, 0x9e, 0x61, 0xe4, 0x95, 0xc7, + 0x45, 0x57, 0x54, 0x08, 0x03, 0xae, 0xc2, 0x0b, + 0x02, 0x72, 0x56, 0x75, 0x55, 0x32, 0xf7, 0x7b + } + }; + const unsigned char expected[2][32] = { + { + 0x37, 0x13, 0x86, 0x34, 0xfc, 0x93, 0x3d, 0x9c, + 0xca, 0x88, 0x98, 0xe0, 0x8f, 0xb1, 0xfa, 0xa4, + 0x90, 0xcb, 0x22, 0x04, 0x74, 0xe4, 0x72, 0x3b, + 0x55, 0xac, 0x49, 0xa7, 0x11, 0x1a, 0xa3, 0x94 + }, + { + 0x15, 0xa3, 0x5b, 0xf6, 0x87, 0xde, 0x58, 0x48, + 0x20, 0xce, 0x15, 0xbd, 0x05, 0x44, 0x8e, 0x0e, + 0x06, 0x47, 0xe7, 0xf6, 0xb0, 0xcc, 0xdc, 0xf9, + 0x01, 0xda, 0x2e, 0x6f, 0x8f, 0x3e, 0x06, 0x04 + } + }; + unsigned char out[32]; + int i; + int subalgo = GCRY_MD_SHA256; + int count = 0; + + again: + + if (verbose) + fprintf (stderr, "checking Balloon test vector %d\n", count); + + err = my_kdf_derive (0, + GCRY_KDF_BALLOON, subalgo, param[count], 3, + pass[count], strlen ((char *)pass[count]), + salt[count], 32, NULL, 0, NULL, 0, + 32, out); + if (err) + fail ("balloon test %d failed: %s\n", count*2+0, gpg_strerror (err)); + else if (memcmp (out, expected[count], 32)) + { + fail ("balloon test %d failed: mismatch\n", count*2+0); + fputs ("got:", stderr); + for (i=0; i < 32; i++) + fprintf (stderr, " %02x", out[i]); + putc ('\n', stderr); + } + +#ifdef HAVE_PTHREAD + err = my_kdf_derive (1, + GCRY_KDF_BALLOON, subalgo, param[count], 3, + pass[count], strlen ((char *)pass[count]), + salt[count], 32, NULL, 0, NULL, 0, + 32, out); + if (err) + fail ("balloon test %d failed: %s\n", count*2+1, gpg_strerror (err)); + else if (memcmp (out, expected[count], 32)) + { + fail ("balloon test %d failed: mismatch\n", count*2+1); + fputs ("got:", stderr); + for (i=0; i < 32; i++) + fprintf (stderr, " %02x", out[i]); + putc ('\n', stderr); + } +#endif + + /* Next test vector */ + count++; + if (count < 2) + goto again; +} + + int main (int argc, char **argv) { @@ -1567,6 +1680,7 @@ main (int argc, char **argv) check_pbkdf2 (); check_scrypt (); check_argon2 (); + check_balloon (); } return error_count ? 1 : 0; -- cgit v1.2.1