pbkdf2.c

/** \file pbkdf2.c
  *
  * \brief Implements the PBKDF2 algorithm.
  *
  * PBKDF2 can be used to derive encryption keys from a password. The
  * number of iterations is controlled by the platform-dependent
  * getPBKDF2Iterations() function. Using PBKDF2 provides more resistance
  * against online and offline brute-force attacks, as compared to using
  * a hash function once.
  *
  * Since embedded devices are typically less powerful than desktop personal
  * computers, the benefit of using PBKDF2 on such a device is not as great as
  * using PBKDF2 on a desktop personal computer. However, it is still better
  * than nothing.
  *
  * This file is licensed as described by the file LICENCE.
  */

#ifdef TEST_PBKDF2
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "test_helpers.h"
#endif // #ifdef TEST_PBKDF2

#include "common.h"
#include "hmac_sha512.h"
#include "endian.h"
#include "hwinterface.h"
#include "pbkdf2.h"

/** Derive a key using the specified password and salt, using HMAC-SHA512 as
  * the underlying pseudo-random function. The derived key length is fixed
  * at #SHA512_HASH_LENGTH bytes.
  *
  * This code here is based on section 5.3 ("PBKDF Specification") of
  * NIST SP 800-132 (obtained from
  * http://csrc.nist.gov/publications/nistpubs/800-132/nist-sp800-132.pdf on
  * 30 March 2013).
  * \param out A byte array where the resulting derived key will be written.
  *            This must have space for #SHA512_HASH_LENGTH bytes.
  * \param password Byte array specifying the password to use in PBKDF2.
  * \param password_length The length (in bytes) of the password.
  * \param salt Byte array specifying the salt to use in PBKDF2.
  * \param salt_length The length (in bytes) of the salt.
  * \warning salt cannot be too long; salt_length must be less than or equal
  *          to #SHA512_HASH_LENGTH - 4.
  */
void pbkdf2(uint8_t *out, const uint8_t *password, const unsigned int password_length, const uint8_t *salt, const unsigned int salt_length)
{
	uint8_t u[SHA512_HASH_LENGTH];
	uint8_t hmac_result[SHA512_HASH_LENGTH];
	unsigned int u_length;
	uint32_t num_iterations;
	uint32_t i;
	unsigned int j;

	memset(out, 0, SHA512_HASH_LENGTH);
	memset(u, 0, sizeof(u));
	if (salt_length > (SHA512_HASH_LENGTH - 4))
	{
		// Salt too long.
		fatalError();
		return;
	}
	else
	{
		u_length = salt_length;
	}
	memcpy(u, salt, u_length);
	writeU32BigEndian(&(u[u_length]), 1);
	u_length += 4;

	num_iterations = getPBKDF2Iterations();
	for (i = 0; i < num_iterations; i++)
	{
		hmacSha512(hmac_result, password, password_length, u, u_length);
		memcpy(u, hmac_result, sizeof(u));
		u_length = SHA512_HASH_LENGTH;
		for (j = 0; j < SHA512_HASH_LENGTH; j++)
		{
			out[j] ^= u[j];
		}
	}
}

#ifdef TEST

/** PBKDF2 is used to derive encryption keys. In order to make brute-force
  * attacks more expensive, this should return a number which is as large
  * as possible, without being so large that key derivation requires an
  * excessive amount of time (> 1 s). This is a platform-dependent function
  * because key derivation speed is platform-dependent.
  *
  * In order to permit key recovery when the number of iterations is unknown,
  * this should be a power of 2. That way, an implementation can use
  * successively greater powers of 2 until the correct number of iterations is
  * found.
  * \return Number of iterations to use in PBKDF2 algorithm.
  */
uint32_t getPBKDF2Iterations(void)
{
	return 1024;
}

#endif // #ifdef TEST

#ifdef TEST_PBKDF2

/** Stores one test vector for pbkdf2(). */
struct PBKDF2TestVector
{
	const char *password;
	unsigned long password_length;
	const char *salt;
	unsigned long salt_length;
	const uint8_t expected_result[SHA512_HASH_LENGTH];
};

/** Test vectors for pbkdf2().
  * It's hard to find publicly available test vectors for PBKDF2-HMAC-SHA512
  * (though there are lots for PBKDF2-HMAC-SHA1), so these were generated
  * using Python 2.5.2 with pycrypto v2.6. Here's the source:
\code

from Crypto.Hash import SHA512, HMAC
from Crypto.Protocol.KDF import PBKDF2
import sys

p = "1" # Set to password
s = "2" # Set to salt

f = lambda key, msg: HMAC.new(key, msg, SHA512).digest()
out = PBKDF2(password=p, salt=s, dkLen=64, count=1024, prf=f)
str = out.encode("hex")

first = True
while len(str) > 0:
	if not first:
		sys.stdout.write(", ")
	first = False
	if len(str) % 16 == 0:
		sys.stdout.write("\n")
	sys.stdout.write("0x" + str[0:2])
	str = str[2:]

\endcode
  * \showinitializer
  */
struct PBKDF2TestVector pbkdf2_test_vectors[] =
{

{"1", 1,
"2", 1,
{0xa1, 0x80, 0x45, 0x1f, 0x46, 0x18, 0xdf, 0x95,
0x15, 0xab, 0x0b, 0xe2, 0xc5, 0x6a, 0xc3, 0x42,
0x02, 0x87, 0xcb, 0x8f, 0xc0, 0x15, 0xf7, 0x84,
0x94, 0xc9, 0x39, 0x4a, 0x62, 0xef, 0x6e, 0x66,
0x57, 0xfd, 0xd1, 0x81, 0x1f, 0xfb, 0x8c, 0x54,
0xeb, 0x89, 0x2e, 0xa5, 0x94, 0xa7, 0xe1, 0xf6,
0xed, 0x81, 0xf2, 0x72, 0x64, 0xa8, 0xe9, 0xb1,
0xc6, 0xed, 0x63, 0x9f, 0x35, 0xbb, 0x12, 0xe8}},

{"", 0,
"", 0,
{0xfb, 0xaa, 0x2a, 0xcb, 0x43, 0xd1, 0xe1, 0xaf,
0xff, 0x85, 0x83, 0x58, 0xaf, 0x28, 0x43, 0xcc,
0x57, 0x8d, 0xb4, 0xe2, 0x2b, 0x94, 0x21, 0x18,
0x09, 0xc0, 0xbf, 0x47, 0x29, 0xd2, 0x6c, 0x2f,
0x65, 0x4a, 0x2d, 0x6c, 0xe6, 0xd5, 0x2b, 0xea,
0x06, 0x20, 0xa7, 0xdb, 0x62, 0x32, 0x1c, 0x96,
0x38, 0xae, 0xb2, 0xd1, 0x16, 0x61, 0x46, 0x7f,
0xee, 0x96, 0x81, 0x04, 0xcc, 0x1b, 0x51, 0xa4}},

{"Bitcoin uses peer to peer technology to operate with no central authority", 73,
"Common salt has the chemical formula NaCl", 41,
{0x34, 0x5c, 0x92, 0xb1, 0xaa, 0xf0, 0xc1, 0x9e,
0xfd, 0x22, 0xfd, 0x80, 0x6d, 0x27, 0x35, 0x87,
0xdc, 0xe8, 0x9c, 0xfa, 0xe6, 0xdc, 0x02, 0x50,
0x9e, 0x5a, 0x40, 0xbe, 0xd8, 0x4d, 0x6f, 0x66,
0xed, 0x24, 0x26, 0x9f, 0xd5, 0xcc, 0xe0, 0x6e,
0x1f, 0xf4, 0xf5, 0x89, 0x83, 0xc5, 0x6e, 0x60,
0xda, 0xb2, 0x9c, 0xd8, 0xb5, 0x7e, 0xe3, 0x24,
0xf5, 0x37, 0xe7, 0xe6, 0x39, 0x83, 0x80, 0x37}},

{"Bitcoin uses peer to peer technology to operate with no central authority", 73,
"", 0,
{0x5d, 0x8f, 0x77, 0x0f, 0xc9, 0xa7, 0x8c, 0x9f,
0x7d, 0x3d, 0xde, 0x84, 0x49, 0xe0, 0x66, 0xca,
0x3d, 0x62, 0x27, 0x97, 0x9f, 0x21, 0x8e, 0x18,
0x93, 0x16, 0x87, 0xda, 0x0c, 0xfc, 0x8f, 0xd5,
0x13, 0xdd, 0x1d, 0xb4, 0xcb, 0x29, 0x8b, 0x2c,
0xa2, 0xe7, 0x34, 0x3d, 0xfd, 0xf3, 0x69, 0x4f,
0x02, 0x69, 0x24, 0xea, 0xdd, 0x02, 0x5b, 0x0b,
0x47, 0xcd, 0x39, 0xd3, 0x1b, 0x67, 0x42, 0x1d}},

{"", 0,
"Common salt has the chemical formula NaCl", 41,
{0x12, 0x77, 0x94, 0xe0, 0x0d, 0xd3, 0x10, 0xcc,
0xdb, 0x58, 0xc3, 0xc0, 0x35, 0x92, 0xe4, 0x0d,
0x54, 0xc4, 0x10, 0xaf, 0x49, 0x98, 0x39, 0xee,
0x91, 0xc4, 0x0f, 0xe6, 0x2f, 0xea, 0xe3, 0xc4,
0x9f, 0xa0, 0x6a, 0x79, 0x9a, 0x2d, 0xe8, 0x29,
0x48, 0xeb, 0x5f, 0x43, 0x40, 0xe9, 0x93, 0x64,
0x99, 0xfb, 0x63, 0x38, 0x19, 0x07, 0x1b, 0xa2,
0x7a, 0x72, 0x74, 0x7c, 0xb0, 0x43, 0xd5, 0x7a}},

{"Pass\0word", 9,
"Sa\0lt", 5,
{0xaa, 0x55, 0xb0, 0x5f, 0x2c, 0x77, 0x11, 0xbb,
0x83, 0xea, 0x01, 0xe5, 0x62, 0xc2, 0x5c, 0x8d,
0x9f, 0xc1, 0xdc, 0xb2, 0xc5, 0xac, 0x7a, 0x36,
0x20, 0x70, 0x86, 0x81, 0xb5, 0x15, 0x11, 0x29,
0xf1, 0x31, 0x1b, 0xa0, 0xed, 0x88, 0xf7, 0x1a,
0xa9, 0x01, 0x88, 0xf3, 0x22, 0x13, 0x0f, 0xf1,
0x6a, 0x68, 0x3d, 0x47, 0x42, 0x7c, 0x2f, 0x31,
0x75, 0xfc, 0xe4, 0x7a, 0x8b, 0xc2, 0xa0, 0xf5}},

{"\x00\x01\xff\xfe", 4,
"\x00\x01\xff\xfe", 4,
{0x58, 0xee, 0x8a, 0xe3, 0x70, 0xc4, 0xed, 0x62,
0x88, 0xf0, 0x48, 0x50, 0xf7, 0x22, 0x6e, 0xe1,
0x82, 0xf3, 0x69, 0xaa, 0xdc, 0xf1, 0x1e, 0x6b,
0xfc, 0xf5, 0x27, 0x0c, 0xec, 0x90, 0x9c, 0x90,
0xd5, 0xee, 0x78, 0x26, 0x15, 0xd1, 0xc3, 0x45,
0x61, 0x89, 0xba, 0x59, 0xd1, 0xde, 0xe4, 0xf0,
0xaa, 0x28, 0x45, 0x38, 0xf1, 0x15, 0x15, 0x9c,
0xad, 0x6a, 0x15, 0xe6, 0xff, 0x56, 0xe7, 0xdf}},

{"Test vector", 11,
"This is a maximum length salt ..ABCDEFGH[][][][][][][]\\\\!!!!", 60,
{0xe0, 0xc1, 0x06, 0x48, 0xfc, 0x64, 0xa9, 0x3a,
0xd1, 0xc8, 0x35, 0x1a, 0x2c, 0x03, 0x6b, 0xc6,
0x16, 0xf5, 0x75, 0x96, 0xc1, 0x34, 0x5d, 0x73,
0x63, 0xe7, 0x6a, 0x3f, 0x47, 0xd0, 0x97, 0x72,
0x81, 0xf7, 0x78, 0x65, 0x01, 0x4e, 0x43, 0x11,
0xa5, 0x9d, 0x3a, 0xb6, 0xe8, 0xbc, 0xe0, 0x2c,
0x97, 0x37, 0x5c, 0xe8, 0x99, 0xf7, 0x4f, 0x81,
0xd6, 0xbb, 0xdb, 0x1c, 0x03, 0x52, 0x0c, 0x43}},

{"LongCatIsLongLongCatIsLongLongCatIsLongLongCatIsLongLongCatIsLong\
LongCatIsLongLongCatIsLongLongCatIsLongLongCatIsLongLongCatIsLong\
LongCatIsLongLongCatIsLongLongCatIsLongLongCatIsLongLongCatIsLong\
LongCatIsLongLongCatIsLongLongCatIsLongLongCatIsLongLongCatIsLong\
LongCatIsLongLongCatIsLongLongCatIsLongLongCatIsLongLongCatIsLong\
LongCatIsLongLongCatIsLongLongCatIsLongLongCatIsLongLongCatIsLong\
LongCatIsLongLongCatIsLongLongCatIsLongLongCatIsLongLongCatIsLong\
LongCatIsLongLongCatIsLongLongCatIsLongLongCatIsLongLongCatIsLong\
LongCatIsLongLongCatIsLong", 546,
"salt", 4,
{0x46, 0xdd, 0x09, 0xe7, 0x17, 0x2a, 0xf3, 0x93,
0x6f, 0x36, 0xb5, 0x5a, 0xcc, 0x51, 0xc8, 0x09,
0xf6, 0xcc, 0xd3, 0x1e, 0x8e, 0x53, 0x17, 0xea,
0xa7, 0x9c, 0xab, 0xab, 0x28, 0xc7, 0xe6, 0x16,
0x9f, 0xa9, 0x56, 0x0a, 0xc9, 0x4b, 0x53, 0x20,
0x1f, 0xbc, 0x06, 0x04, 0xd6, 0xa5, 0xf0, 0xc2,
0x39, 0x4f, 0xee, 0xa9, 0x91, 0x73, 0x61, 0xd7,
0xf5, 0xb6, 0x3a, 0xdb, 0x30, 0x0f, 0xdc, 0x85}}
};

int main(void)
{
	unsigned int num_test_vectors;
	unsigned int i;
	uint8_t out[SHA512_HASH_LENGTH];

	initTests(__FILE__);

	num_test_vectors = sizeof(pbkdf2_test_vectors) / sizeof(struct PBKDF2TestVector);
	for (i = 0; i < num_test_vectors; i++)
	{
		pbkdf2(
			out,
			(const uint8_t *)pbkdf2_test_vectors[i].password,
			pbkdf2_test_vectors[i].password_length,
			(const uint8_t *)pbkdf2_test_vectors[i].salt,
			pbkdf2_test_vectors[i].salt_length);
		if (memcmp(out, pbkdf2_test_vectors[i].expected_result, SHA512_HASH_LENGTH))
		{
			printf("Test %u mismatch, got:\n", i);
			bigPrintVariableSize(out, SHA512_HASH_LENGTH, true);
			printf("\nExpected:\n");
			bigPrintVariableSize(pbkdf2_test_vectors[i].expected_result, SHA512_HASH_LENGTH, true);
			printf("\n");
			reportFailure();
		}
		else
		{
			reportSuccess();
		}
	}

	finishTests();
	exit(0);
}

#endif // #ifdef TEST_PBKDF2