Re: [PATCH] PKCS #5 PBKDF2

Simon Josefsson simon@josefsson.org writes:

How about adding KDFs? Here is a starting pointer for the most common function, PKCS #5 PBKDF2. Review appreciated.

I don't have time to review it at the moment, but I hope to be able to do that within a few days. You may also want to have a look at

http://git.lysator.liu.se/lsh/lsh/blobs/master/src/pkcs5.c

which I wrote a long time ago. Probably not very useful for Nettle as is, but I'll happily relicense it as LGPL if anything is derived from it.

One immediate comment: "PBKDF2" is an awful name :-/

Are there any other key derivation methods which are important?

Regards, /Niels

/Simon

From 2fe9180d4b0afb7acb77622d541d5be21830fc7b Mon Sep 17 00:00:00 2001 From: Simon Josefsson simon@josefsson.org Date: Wed, 12 Sep 2012 22:05:30 +0200 Subject: [PATCH] New PKCS #5 PBKDF2 function.

---

ChangeLog | 14 ++++++ Makefile.in | 2 + NEWS | 6 +++ nettle-internal.h | 1 + nettle.texinfo | 38 +++++++++++++++- pbkdf2.c | 103 ++++++++++++++++++++++++++++++++++++++++++++ pbkdf2.h | 49 +++++++++++++++++++++ testsuite/.gitignore | 1 + testsuite/.test-rules.make | 3 ++ testsuite/Makefile.in | 2 +- testsuite/meta-hash-test.c | 3 ++ testsuite/pbkdf2-test.c | 51 ++++++++++++++++++++++ 12 files changed, 270 insertions(+), 3 deletions(-) create mode 100644 pbkdf2.c create mode 100644 pbkdf2.h create mode 100644 testsuite/pbkdf2-test.c

diff --git a/ChangeLog b/ChangeLog index fe61ad9..a35f747 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,17 @@ +2012-09-12 Simon Josefsson simon@josefsson.org

• • NEWS: Mention addition of PBKDF2.
• • pbkdf2.c (pbkdf2_hmac): New file and function.
• • pbkdf2.h: Declare it.
• • Makefile.in (nettle_SOURCES): Add pbkdf2.c.
• (HEADERS): Add pbkdf2.h.
• • testsuite/pbkdf2-test.c: New test case.
• • nettle-internal.h (NETTLE_MAX_HASH_CONTEXT_SIZE): New constant.
• • testsuite/meta-hash-test.c (test_main): Validate NETTLE_MAX_HASH_CONTEXT_SIZE.
• • nettle.texinfo (Key derivation functions): New section.
• • testsuite/Makefile.in (TS_NETTLE_SOURCES): Add pbkdf2-test.c.
• • testsuite/.test-rules.make (pbkdf2-test): New target.

2012-09-10 Niels Möller nisse@lysator.liu.se

• examples/eratosthenes.c (main): Explicitly deallocate storage

diff --git a/Makefile.in b/Makefile.in index cf93593..7c6cf33 100644 --- a/Makefile.in +++ b/Makefile.in @@ -77,6 +77,7 @@ nettle_SOURCES = aes-decrypt-internal.c aes-decrypt.c \ des3.c des-compat.c \ hmac.c hmac-md5.c hmac-ripemd160.c hmac-sha1.c \ hmac-sha224.c hmac-sha256.c hmac-sha384.c hmac-sha512.c \

•  pbkdf2.c \
  

  knuth-lfib.c \ md2.c md2-meta.c md4.c md4-meta.c \ md5.c md5-compress.c md5-compat.c md5-meta.c \

@@ -123,6 +124,7 @@ HEADERS = aes.h arcfour.h arctwo.h asn1.h bignum.h blowfish.h \ cbc.h ctr.h gcm.h \ des.h des-compat.h dsa.h \ hmac.h \

•  pbkdf2.h \
  

  knuth-lfib.h \ macros.h \ md2.h md4.h \

diff --git a/NEWS b/NEWS index 4957f80..ea846a7 100644 --- a/NEWS +++ b/NEWS @@ -1,3 +1,9 @@

• New features:
• • Support for PKCS #5 PBKDF2. Contributed by Simon Josefsson.

•      Specification in RFC 2898 and test vectors in RFC 6070.
  

NEWS for the 2.5 release

This release includes important portability fixes for Windows diff --git a/nettle-internal.h b/nettle-internal.h index e85e3c5..a7a37f8 100644 --- a/nettle-internal.h +++ b/nettle-internal.h @@ -48,6 +48,7 @@ do { if (size > (sizeof(name) / sizeof(name[0]))) abort(); } while (0) #define NETTLE_MAX_BIGNUM_SIZE ((NETTLE_MAX_BIGNUM_BITS + 7)/8) #define NETTLE_MAX_HASH_BLOCK_SIZE 128 #define NETTLE_MAX_HASH_DIGEST_SIZE 64 +#define NETTLE_MAX_HASH_CONTEXT_SIZE 2 #define NETTLE_MAX_SEXP_ASSOC 17 #define NETTLE_MAX_CIPHER_BLOCK_SIZE 32

diff --git a/nettle.texinfo b/nettle.texinfo index 4904d91..d887ed9 100644 --- a/nettle.texinfo +++ b/nettle.texinfo @@ -70,6 +70,7 @@ Reference

• Cipher functions::
• Cipher modes::
• Keyed hash functions::

+* Key derivation functions::

• Public-key algorithms::
• Randomness::
• Ascii encoding::

@@ -316,6 +317,7 @@ This chapter describes all the Nettle functions, grouped by family.

• Cipher functions::
• Cipher modes::
• Keyed hash functions::

+* Key derivation functions::

• Public-key algorithms::
• Randomness::
• Ascii encoding::

@@ -1852,7 +1854,7 @@ only the first @var{length} octets of the digest are written.

-@node Keyed hash functions, Public-key algorithms, Cipher modes, Reference +@node Keyed hash functions, Key derivation functions, Cipher modes, Reference @comment node-name, next, previous, up @section Keyed Hash Functions

@@ -2102,7 +2104,39 @@ This function also resets the context for processing new messages, with the same key. @end deftypefun

-@node Public-key algorithms, Randomness, Keyed hash functions, Reference +@node Key derivation functions, Public-key algorithms, Keyed hash functions, Reference +@comment node-name, next, previous, up +@section Key derivation Functions

+@cindex Key Derivation Function +@cindex Password Based Key Derivation Function +@cindex PKCS #5 +@cindex KDF +@cindex PBKDF

+A @dfn{key derivation function} (@acronym{KDF}) is a function that from +a given symmetric key derives other symmetric keys. A sub-class of KDFs +is the @dfn{password-based key derivation functions} (@acronym{PBKDFs}), +which take as input a password or passphrase, and its purpose is +typically to strengthen it and protect against certain pre-computation +attacks by using salting and expensive computation. The most well known +PBKDF is the @code{PKCS #5 PBKDF2} described in @cite{RFC 2898} which +uses a pseudorandom function such as @acronym{HMAC-SHA1}.

+Nettle's @acronym{PBKDF2} function is defined in @file{<nettle/pbkdf2.h>}. +It contains a function:

+@deftypefun void pbkdf2_hmac (unsigned @var{Plen}, const uint8_t *@var{P}, unsigned @var{Slen}, const uint8_t *@var{S}, const struct nettle_hash *@var{hash}, unsigned int @var{c}, unsigned @var{dkLen}, uint8_t *@var{DK})

+Derive symmetric key from a password according to PKCS #5 PBKDF2. The +PRF is the HMAC familly with @var{hash} indicating the underlying hash +function. Inputs are the password @var{P} of length @var{Plen}, the +salt @var{S} of length @var{Slen}, the iteration counter @var{C} (> 0), +and the desired derived output length @var{dkLen}. The output buffer is +@var{DK} which must have room for at least @var{dkLen} octets. +@end deftypefun

+@node Public-key algorithms, Randomness, Key derivation functions, Reference @comment node-name, next, previous, up @section Public-key algorithms

diff --git a/pbkdf2.c b/pbkdf2.c new file mode 100644 index 0000000..eab8f0a --- /dev/null +++ b/pbkdf2.c @@ -0,0 +1,103 @@ +/* pbkdf2.c

• • PKCS #5 password-based key derivation function PBKDF2, see RFC 2898.
• */

+/* nettle, low-level cryptographics library

• • Copyright (C) 2012 Simon Josefsson
• • The nettle library is free software; you can redistribute it and/or modify
• • it under the terms of the GNU Lesser General Public License as published by
• • the Free Software Foundation; either version 2.1 of the License, or (at your
• • option) any later version.
• • The nettle library 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 Lesser General Public
• • License for more details.
• • You should have received a copy of the GNU Lesser General Public License
• • along with the nettle library; see the file COPYING.LIB. If not, write to
• • the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
• • MA 02111-1301, USA.
• */

+#if HAVE_CONFIG_H +# include "config.h" +#endif

+#include <assert.h> +#include <stdlib.h> +#include <string.h>

+#include "pbkdf2.h"

+#include "hmac.h" +#include "nettle-internal.h"

+void +pbkdf2_hmac (unsigned Plen, const uint8_t * P,

•     unsigned Slen, const uint8_t * S,
  

•     const struct nettle_hash *hash,
  

•     unsigned int c, unsigned dkLen, uint8_t * DK)
  

+{

• unsigned int hLen = hash->digest_size;
• char U[NETTLE_MAX_HASH_DIGEST_SIZE];
• char T[NETTLE_MAX_HASH_DIGEST_SIZE];
• unsigned int u;
• unsigned int l;
• unsigned int r;
• unsigned int i;
• unsigned int k;
• char tmp[4];
• TMP_DECL (inner, uint8_t, NETTLE_MAX_HASH_CONTEXT_SIZE);
• TMP_DECL (outer, uint8_t, NETTLE_MAX_HASH_CONTEXT_SIZE);
• TMP_DECL (state, uint8_t, NETTLE_MAX_HASH_CONTEXT_SIZE);
• if (c == 0)
• return;
• if (dkLen == 0)
• return;
• l = ((dkLen - 1) / hLen) + 1;
• r = dkLen - (l - 1) * hLen;
• TMP_ALLOC (inner, hash->context_size);
• TMP_ALLOC (outer, hash->context_size);
• TMP_ALLOC (state, hash->context_size);
• for (i = 1; i <= l; i++)
• {

•  memset (T, 0, hLen);
  

•  for (u = 1; u <= c; u++)
  

• {

•  hmac_set_key (outer, inner, state, hash, Plen, P);
  

•  if (u == 1)
  

•    {
  

•      tmp[0] = (i & 0xff000000) >> 24;
  

•      tmp[1] = (i & 0x00ff0000) >> 16;
  

•      tmp[2] = (i & 0x0000ff00) >> 8;
  

•      tmp[3] = (i & 0x000000ff) >> 0;
  

•      hmac_update (state, hash, Slen, S);
  

•      hmac_update (state, hash, 4, tmp);
  

•    }
  

•  else
  

•    {
  

•      hmac_set_key (outer, inner, state, hash, Plen, P);
  

•      hmac_update (state, hash, hLen, U);
  

•    }
  

•  hmac_digest (outer, inner, state, hash, hLen, U);
  

•  for (k = 0; k < hLen; k++)
  

•    T[k] ^= U[k];
  

• }

•  memcpy (DK + (i - 1) * hLen, T, i == l ? r : hLen);
  

• }

+} diff --git a/pbkdf2.h b/pbkdf2.h new file mode 100644 index 0000000..f2f42c5 --- /dev/null +++ b/pbkdf2.h @@ -0,0 +1,49 @@ +/* pbkdf2.c

• • PKCS #5 password-based key derivation function PBKDF2, see RFC 2898.
• */

+/* nettle, low-level cryptographics library

• • Copyright (C) 2012 Simon Josefsson
• • The nettle library is free software; you can redistribute it and/or modify
• • it under the terms of the GNU Lesser General Public License as published by
• • the Free Software Foundation; either version 2.1 of the License, or (at your
• • option) any later version.
• • The nettle library 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 Lesser General Public
• • License for more details.
• • You should have received a copy of the GNU Lesser General Public License
• • along with the nettle library; see the file COPYING.LIB. If not, write to
• • the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
• • MA 02111-1301, USA.
• */

+#ifndef NETTLE_PBKDF2_H_INCLUDED +#define NETTLE_PBKDF2_H_INCLUDED

+#include "nettle-meta.h"

+#ifdef __cplusplus +extern "C" +{ +#endif

+/* Namespace mangling */ +#define pbkdf2_hmac nettle_pbkdf2_hmac

+void +pbkdf2_hmac (unsigned Plen, const uint8_t * P,

•     unsigned Slen, const uint8_t * S,
  

•     const struct nettle_hash *hash,
  

•     unsigned int c, unsigned dkLen, uint8_t * DK);
  

+#ifdef __cplusplus +} +#endif

+#endif /* NETTLE_PBKDF2_H_INCLUDED */ diff --git a/testsuite/.gitignore b/testsuite/.gitignore index c9f4698..b7ddd79 100644 --- a/testsuite/.gitignore +++ b/testsuite/.gitignore @@ -20,6 +20,7 @@ /dsa-test /gcm-test /hmac-test +/pbkdf2-test /knuth-lfib-test /md2-test /md4-test diff --git a/testsuite/.test-rules.make b/testsuite/.test-rules.make index 10c993f..d8f8f23 100644 --- a/testsuite/.test-rules.make +++ b/testsuite/.test-rules.make @@ -88,6 +88,9 @@ gcm-test$(EXEEXT): gcm-test.$(OBJEXT) hmac-test$(EXEEXT): hmac-test.$(OBJEXT) $(LINK) hmac-test.$(OBJEXT) $(TEST_OBJS) -o hmac-test$(EXEEXT)

+pbkdf2-test$(EXEEXT): pbkdf2-test.$(OBJEXT)

• $(LINK) pbkdf2-test.$(OBJEXT) $(TEST_OBJS) -o pbkdf2-test$(EXEEXT)

meta-hash-test$(EXEEXT): meta-hash-test.$(OBJEXT) $(LINK) meta-hash-test.$(OBJEXT) $(TEST_OBJS) -o meta-hash-test$(EXEEXT)

diff --git a/testsuite/Makefile.in b/testsuite/Makefile.in index 206a76e..86f365a 100644 --- a/testsuite/Makefile.in +++ b/testsuite/Makefile.in @@ -25,7 +25,7 @@ TS_NETTLE_SOURCES = aes-test.c arcfour-test.c arctwo-test.c \ knuth-lfib-test.c \ cbc-test.c ctr-test.c gcm-test.c hmac-test.c \ meta-hash-test.c meta-cipher-test.c meta-armor-test.c \

•     buffer-test.c yarrow-test.c
  

•     buffer-test.c yarrow-test.c pbkdf2-test.c
  
  

TS_HOGWEED_SOURCES = sexp-test.c sexp-format-test.c \ rsa2sexp-test.c sexp2rsa-test.c \ diff --git a/testsuite/meta-hash-test.c b/testsuite/meta-hash-test.c index 6db279b..0a8c61c 100644 --- a/testsuite/meta-hash-test.c +++ b/testsuite/meta-hash-test.c @@ -1,4 +1,5 @@ #include "testutils.h" +#include "nettle-internal.h" #include "nettle-meta.h"

const char* hashes[] = { @@ -29,6 +30,8 @@ test_main(void) while (NULL != nettle_hashes[j]) j++; ASSERT(j == count); /* we are not missing testing any hashes */

• for (j = 0; NULL != nettle_hashes[j]; j++)
• ASSERT(nettle_hashes[j]->context_size <= NETTLE_MAX_HASH_CONTEXT_SIZE); SUCCESS();

}

diff --git a/testsuite/pbkdf2-test.c b/testsuite/pbkdf2-test.c new file mode 100644 index 0000000..45d11a7 --- /dev/null +++ b/testsuite/pbkdf2-test.c @@ -0,0 +1,51 @@ +#include "testutils.h" +#include "pbkdf2.h"

+#define PBKDF2_HMAC_TEST(alg, plen, p, slen, s, c, dklen, expect) do { \

• dk[dklen] = 17; \
• pbkdf2_hmac (plen, p, slen, s, alg, c, dklen, dk); \
• ASSERT(MEMEQ (dklen, dk, expect)); \
• ASSERT(dk[dklen] == 17); \
• } while (0)

+#define MAX_DKLEN 25

+int +test_main (void) +{

• uint8_t dk[MAX_DKLEN + 1];
• /* Test vectors for PBKDF2 from RFC 6070. */
• PBKDF2_HMAC_TEST (&nettle_sha1, 8, "password", 4, "salt", 1, 20,

•     H("0c60c80f961f0e71f3a9b524af6012062fe037a6"));
  

• PBKDF2_HMAC_TEST (&nettle_sha1, 8, "password", 4, "salt", 2, 20,

•     H("ea6c014dc72d6f8ccd1ed92ace1d41f0d8de8957"));
  

• PBKDF2_HMAC_TEST (&nettle_sha1, 8, "password", 4, "salt", 4096, 20,

•     H("4b007901b765489abead49d926f721d065a429c1"));
  

+#if 0 /* too slow */

• PBKDF2_HMAC_TEST (&nettle_sha1, 8, "password", 4, "salt", 16777216, 20,

•     H("eefe3d61cd4da4e4e9945b3d6ba2158c2634e984"));
  

+#endif

• PBKDF2_HMAC_TEST (&nettle_sha1, 24, "passwordPASSWORDpassword",

•     36, "saltSALTsaltSALTsaltSALTsaltSALTsalt", 4096, 25,
  

•     H("3d2eec4fe41c849b80c8d83662c0e44a8b291a964cf2f07038"));
  

• PBKDF2_HMAC_TEST (&nettle_sha1, 9, "pass\0word", 5, "sa\0lt", 4096, 16,

•     H("56fa6aa75548099dcc37d7f03425e0c3"));
  

• /* PBKDF2-HMAC-SHA-256 test vectors confirmed with another

• implementation.  */
  

• PBKDF2_HMAC_TEST (&nettle_sha256, 6, "passwd", 4, "salt", 1, 16,

•     H("55ac046e56e3089fec1691c22544b605"));
  

• PBKDF2_HMAC_TEST (&nettle_sha256, 8, "Password", 4, "NaCl", 80000, 16,

•     H("4ddcd8f60b98be21830cee5ef22701f9"));
  

• SUCCESS ();

+}