[PATCH] PKCS#5 PBKDF2
Simon Josefsson
jas@extundo.com
Tue, 03 Dec 2002 02:53:07 +0100
Not sure if this is suitable for libgcrypt, but it seems that even a
complete PKCS#5 implementation would be so small it doesn't make sense
to create a libpkcs5. Only tested on alphaev68-dec-osf5.1 and
i686-pc-linux-gnu.
On a similar topic, what do you think about adding a CRC32 "message
digest"? It might be useful to have, even though it is not the most
secure message digest, and the libgcrypt framework fits rather nicely.
2002-12-03 Simon Josefsson <jas@extundo.com>
* Makefile.am (libcipher_la_SOURCES): Add pkcs5.c
* pkcs5.c: New file.
2002-12-03 Simon Josefsson <jas@extundo.com>
* gcrypt.h (gcry_pbkdf2): Add.
2002-12-03 Simon Josefsson <jas@extundo.com>
* Makefile.am (TESTS): Add pkcs5.c.
* pkcs5.c: Add.
Index: cipher/Makefile.am
===================================================================
RCS file: /cvs/gnupg/libgcrypt/cipher/Makefile.am,v
retrieving revision 1.67
diff -u -p -r1.67 Makefile.am
--- cipher/Makefile.am 10 Nov 2002 18:03:28 -0000 1.67
+++ cipher/Makefile.am 3 Dec 2002 01:47:48 -0000
@@ -45,6 +45,7 @@ libcipher_la_LDFLAGS =
libcipher_la_SOURCES = cipher.c \
pubkey.c \
md.c \
+ pkcs5.c \
dynload.c \
dynload.h \
bithelp.h \
Index: cipher/pkcs5.c
===================================================================
RCS file: cipher/pkcs5.c
diff -N cipher/pkcs5.c
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ cipher/pkcs5.c 3 Dec 2002 01:47:48 -0000
@@ -0,0 +1,201 @@
+/* pkcs5.c Partial Password-Based Cryptography (PKCS#5) implementation
+ * Copyright (C) 2002 Free Software Foundation, Inc.
+ *
+ * This file 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.
+ *
+ * This file 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 this file; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ */
+
+#include <config.h>
+#include "g10lib.h"
+
+/*
+ * 5.2 PBKDF2
+ *
+ * PBKDF2 applies a pseudorandom function (see Appendix B.1 for an
+ * example) to derive keys. The length of the derived key is essentially
+ * unbounded. (However, the maximum effective search space for the
+ * derived key may be limited by the structure of the underlying
+ * pseudorandom function. See Appendix B.1 for further discussion.)
+ * PBKDF2 is recommended for new applications.
+ *
+ * PBKDF2 (P, S, c, dkLen)
+ *
+ * Options: PRF underlying pseudorandom function (hLen
+ * denotes the length in octets of the
+ * pseudorandom function output)
+ *
+ * Input: P password, an octet string
+ * S salt, an octet string
+ * c iteration count, a positive integer
+ * dkLen intended length in octets of the derived
+ * key, a positive integer, at most
+ * (2^32 - 1) * hLen
+ *
+ * Output: DK derived key, a dkLen-octet string
+ */
+
+int
+gcry_pbkdf2 (int PRF, const char *P, size_t Plen, const char *S,
+ size_t Slen, unsigned int c, unsigned int dkLen, char *DK)
+{
+ GCRY_MD_HD prf;
+ char *U;
+ unsigned int u;
+ unsigned int hLen;
+ unsigned int l;
+ unsigned int r;
+ unsigned int t;
+ int rc;
+ unsigned char *p;
+ int i;
+ int k;
+
+ hLen = gcry_md_get_algo_dlen (PRF);
+ if (hLen == 0)
+ return GCRYERR_INV_MD_ALGO;
+
+ if (c == 0)
+ return GCRYERR_INV_ARG;
+
+ if (dkLen == 0)
+ return GCRYERR_INV_ARG;
+
+ /*
+ *
+ * Steps:
+ *
+ * 1. If dkLen > (2^32 - 1) * hLen, output "derived key too long" and
+ * stop.
+ */
+
+ if (dkLen > 4294967295U)
+ return GCRYERR_INV_ARG;
+
+ /*
+ * 2. Let l be the number of hLen-octet blocks in the derived key,
+ * rounding up, and let r be the number of octets in the last
+ * block:
+ *
+ * l = CEIL (dkLen / hLen) ,
+ * r = dkLen - (l - 1) * hLen .
+ *
+ * Here, CEIL (x) is the "ceiling" function, i.e. the smallest
+ * integer greater than, or equal to, x.
+ */
+
+ l = dkLen / hLen;
+ if (dkLen % hLen)
+ l++;
+ r = dkLen - (l - 1) * hLen;
+
+ /*
+ * 3. For each block of the derived key apply the function F defined
+ * below to the password P, the salt S, the iteration count c, and
+ * the block index to compute the block:
+ *
+ * T_1 = F (P, S, c, 1) ,
+ * T_2 = F (P, S, c, 2) ,
+ * ...
+ * T_l = F (P, S, c, l) ,
+ *
+ * where the function F is defined as the exclusive-or sum of the
+ * first c iterates of the underlying pseudorandom function PRF
+ * applied to the password P and the concatenation of the salt S
+ * and the block index i:
+ *
+ * F (P, S, c, i) = U_1 \xor U_2 \xor ... \xor U_c
+ *
+ * where
+ *
+ * U_1 = PRF (P, S || INT (i)) ,
+ * U_2 = PRF (P, U_1) ,
+ * ...
+ * U_c = PRF (P, U_{c-1}) .
+ *
+ * Here, INT (i) is a four-octet encoding of the integer i, most
+ * significant octet first.
+ *
+ * 4. Concatenate the blocks and extract the first dkLen octets to
+ * produce a derived key DK:
+ *
+ * DK = T_1 || T_2 || ... || T_l<0..r-1>
+ *
+ * 5. Output the derived key DK.
+ *
+ * Note. The construction of the function F follows a "belt-and-
+ * suspenders" approach. The iterates U_i are computed recursively to
+ * remove a degree of parallelism from an opponent; they are exclusive-
+ * ored together to reduce concerns about the recursion degenerating
+ * into a small set of values.
+ *
+ */
+
+ prf = gcry_md_open (PRF, GCRY_MD_FLAG_HMAC);
+ if (prf == NULL)
+ return gcry_errno();
+
+ U = gcry_malloc(hLen);
+ if (!U)
+ {
+ rc = GCRYERR_NO_MEM;
+ goto done;
+ }
+
+ for (i = 1; i <= l; i++)
+ {
+ memset(DK + (i - 1) * hLen, 0, i == l ? r : hLen);
+
+ for (u = 1; u <= c; u++)
+ {
+ gcry_md_reset (prf);
+
+ rc = gcry_md_setkey (prf, P, Plen);
+ if (rc != GCRYERR_SUCCESS)
+ goto done;
+
+ if (u == 1)
+ {
+ char tmp[4];
+ gcry_md_write (prf, S, Slen);
+ tmp[0] = (i & 0xff000000) >> 24;
+ tmp[1] = (i & 0x00ff0000) >> 16;
+ tmp[2] = (i & 0x0000ff00) >> 8;
+ tmp[3] = (i & 0x000000ff) >> 0;
+ gcry_md_write (prf, tmp, 4);
+ }
+ else
+ gcry_md_write (prf, U, hLen);
+
+ p = gcry_md_read (prf, PRF);
+ if (p == NULL)
+ {
+ rc = gcry_errno();
+ goto done;
+ }
+
+ memcpy (U, p, hLen);
+
+ for (k = 0; k < (i == l ? r : hLen); k++)
+ DK[(i - 1) * hLen + k] ^= U[k];
+ }
+ }
+
+ rc = GCRYERR_SUCCESS;
+
+ done:
+ gcry_md_close (prf);
+ gcry_free(U);
+ return rc;
+}
Index: src/gcrypt.h
===================================================================
RCS file: /cvs/gnupg/libgcrypt/src/gcrypt.h,v
retrieving revision 1.64
diff -u -p -r1.64 gcrypt.h
--- src/gcrypt.h 10 Nov 2002 18:02:34 -0000 1.64
+++ src/gcrypt.h 3 Dec 2002 01:47:48 -0000
@@ -916,6 +916,9 @@ void gcry_free (void *a);
/* Return true if A is allocated in "secure" memory. */
int gcry_is_secure (const void *a);
+/* PKCS#5 Key derivation function */
+int gcry_pbkdf2 (int PRF, const char *P, size_t Plen, const char *S,
+ size_t Slen, unsigned int c, unsigned int dkLen, char *DK);
#ifndef GCRYPT_NO_MPI_MACROS
# ifndef DID_MPI_TYPEDEF
Index: tests/Makefile.am
===================================================================
RCS file: /cvs/gnupg/libgcrypt/tests/Makefile.am,v
retrieving revision 1.4
diff -u -p -r1.4 Makefile.am
--- tests/Makefile.am 14 May 2002 13:11:08 -0000 1.4
+++ tests/Makefile.am 3 Dec 2002 01:47:48 -0000
@@ -21,7 +21,7 @@
# TESTS_ENVIRONMENT =
-TESTS = basic tsexp
+TESTS = basic tsexp pkcs5
EXTRA_DIST =
Index: tests/pkcs5.c
===================================================================
RCS file: tests/pkcs5.c
diff -N tests/pkcs5.c
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ tests/pkcs5.c 3 Dec 2002 01:47:48 -0000
@@ -0,0 +1,179 @@
+/* pkcs5.c - pkcs5 regression tests
+ * Copyright (C) 2002 Free Software Foundation, Inc.
+ *
+ * This file is part of Libgcrypt.
+ *
+ * Libgcrypt 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.
+ *
+ * Libgcrypt 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 this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <stdarg.h>
+#include "../src/gcrypt.h"
+
+static int verbose;
+static int error_count;
+
+static void
+fail ( const char *format, ... )
+{
+ va_list arg_ptr ;
+
+ va_start( arg_ptr, format ) ;
+ vfprintf (stderr, format, arg_ptr );
+ va_end(arg_ptr);
+ error_count++;
+}
+
+static void
+die ( const char *format, ... )
+{
+ va_list arg_ptr ;
+
+ va_start( arg_ptr, format ) ;
+ vfprintf (stderr, format, arg_ptr );
+ va_end(arg_ptr);
+ exit (1);
+}
+
+#define ESZETT "\xC3\x9F"
+#define S_CARON "\xC5\xA1"
+#define C_ACUTE "\xC4\x87"
+#define G_CLEF "\xF0\x9D\x84\x9E"
+
+struct pkcs5
+{
+ int iterations;
+ char *password;
+ char *salt;
+ int algo;
+ int dklen;
+ char *expected;
+}
+ pkcs5[] = {
+ {
+ 1, "password", "ATHENA.MIT.EDUraeburn", GCRY_MD_SHA1, 16,
+ "\xCD\xED\xB5\x28\x1B\xB2\xF8\x01\x56\x5A\x11\x22\xB2\x56\x35\x15"}
+ ,
+ {
+ 2, "password", "ATHENA.MIT.EDUraeburn", GCRY_MD_SHA1, 16,
+ "\x01\xdb\xee\x7f\x4a\x9e\x24\x3e\x98\x8b\x62\xc7\x3c\xda\x93\x5d"}
+ ,
+ {
+ 2, "password", "ATHENA.MIT.EDUraeburn", GCRY_MD_SHA1, 32,
+ "\x01\xdb\xee\x7f\x4a\x9e\x24\x3e\x98\x8b\x62\xc7\x3c\xda\x93\x5d"
+ "\xa0\x53\x78\xb9\x32\x44\xec\x8f\x48\xa9\x9e\x61\xad\x79\x9d\x86"}
+ ,
+ {
+ 1200, "password", "ATHENA.MIT.EDUraeburn", GCRY_MD_SHA1, 16,
+ "\x5c\x08\xeb\x61\xfd\xf7\x1e\x4e\x4e\xc3\xcf\x6b\xa1\xf5\x51\x2b"}
+ ,
+ {
+ 1200, "password", "ATHENA.MIT.EDUraeburn", GCRY_MD_SHA1, 32,
+ "\x5c\x08\xeb\x61\xfd\xf7\x1e\x4e\x4e\xc3\xcf\x6b\xa1\xf5\x51\x2b"
+ "\xa7\xe5\x2d\xdb\xc5\xe5\x14\x2f\x70\x8a\x31\xe2\xe6\x2b\x1e\x13"}
+ ,
+ {
+ 5, "password", "\x12\x34\x56\x78\x78\x56\x34\x12\x00", GCRY_MD_SHA1, 16,
+ "\xd1\xda\xa7\x86\x15\xf2\x87\xe6\xa1\xc8\xb1\x20\xd7\x06\x2a\x49"}
+ ,
+ {
+ 5, "password", "\x12\x34\x56\x78\x78\x56\x34\x12\x00", GCRY_MD_SHA1, 32,
+ "\xd1\xda\xa7\x86\x15\xf2\x87\xe6\xa1\xc8\xb1\x20\xd7\x06\x2a\x49"
+ "\x3f\x98\xd2\x03\xe6\xbe\x49\xa6\xad\xf4\xfa\x57\x4b\x6e\x64\xee"}
+ ,
+ {
+ 1200, "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
+ "pass phrase equals block size", GCRY_MD_SHA1, 16,
+ "\x13\x9c\x30\xc0\x96\x6b\xc3\x2b\xa5\x5f\xdb\xf2\x12\x53\x0a\xc9"}
+ ,
+ {
+ 1200, "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
+ "pass phrase equals block size", GCRY_MD_SHA1, 32,
+ "\x13\x9c\x30\xc0\x96\x6b\xc3\x2b\xa5\x5f\xdb\xf2\x12\x53\x0a\xc9"
+ "\xc5\xec\x59\xf1\xa4\x52\xf5\xcc\x9a\xd9\x40\xfe\xa0\x59\x8e\xd1"}
+ ,
+ {
+ 1200, "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
+ "pass phrase exceeds block size", GCRY_MD_SHA1, 16,
+ "\x9c\xca\xd6\xd4\x68\x77\x0c\xd5\x1b\x10\xe6\xa6\x87\x21\xbe\x61"}
+ ,
+ {
+ 1200, "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
+ "pass phrase exceeds block size", GCRY_MD_SHA1, 32,
+ "\x9c\xca\xd6\xd4\x68\x77\x0c\xd5\x1b\x10\xe6\xa6\x87\x21\xbe\x61"
+ "\x1a\x8b\x4d\x28\x26\x01\xdb\x3b\x36\xbe\x92\x46\x91\x5e\xc8\x2a"}
+ ,
+ {
+ 50, G_CLEF "\x00", "EXAMPLE.COMpianist", GCRY_MD_SHA1, 16,
+ "\x6b\x9c\xf2\x6d\x45\x45\x5a\x43\xa5\xb8\xbb\x27\x6a\x40\x3b\x39"}
+ ,
+ {
+ 50, G_CLEF "\x00", "EXAMPLE.COMpianist", GCRY_MD_SHA1, 32,
+ "\x6b\x9c\xf2\x6d\x45\x45\x5a\x43\xa5\xb8\xbb\x27\x6a\x40\x3b\x39"
+ "\xe7\xfe\x37\xa0\xc4\x1e\x02\xc2\x81\xff\x30\x69\xe1\xe9\x4f\x52"}
+ ,
+ {
+ 500, "All n-entities must communicate with other n-entities via n-1 "
+ "entiteeheehees", "\x12\x34\x56\x78\x78\x56\x34\x12\x00",
+ GCRY_MD_SHA1, 16,
+ "\x6A\x89\x70\xBF\x68\xC9\x2C\xAE\xA8\x4A\x8D\xF2\x85\x10\x85\x86"}
+ };
+
+int
+main (int argc, char **argv)
+{
+ unsigned char out[BUFSIZ];
+ int res;
+ int i;
+
+ if (argc > 1 && !strcmp (argv[1], "--verbose"))
+ verbose = 1;
+
+ gcry_control (GCRYCTL_DISABLE_SECMEM, NULL, 0);
+ if (!gcry_check_version (GCRYPT_VERSION))
+ die ("version mismatch\n");
+
+ for (i = 0; i < sizeof (pkcs5) / sizeof (pkcs5[0]); i++)
+ {
+ if (verbose)
+ printf ("PKCS5 entry %d\n", i);
+
+ res = gcry_pbkdf2 (pkcs5[i].algo,
+ pkcs5[i].password,strlen (pkcs5[i].password),
+ pkcs5[i].salt, strlen (pkcs5[i].salt),
+ pkcs5[i].iterations, pkcs5[i].dklen, out);
+ if (res)
+ {
+ fail ("PKCS5 entry %d failed fatally: %d\n", i, res);
+ continue;
+ }
+
+ if (memcmp (pkcs5[i].expected, out, pkcs5[i].dklen) != 0)
+ {
+ fail ("PKCS5 entry %d failed\n", i);
+
+ if (verbose)
+ printf ("ERROR\n");
+ }
+ else if (verbose)
+ printf ("OK\n");
+ }
+
+ return error_count? 1:0;
+}
+
+