2 * Implementation of Password-Based Cryptography as per PKCS#5
3 * Copyright (C) 2002,2003 Simon Josefsson
4 * Copyright (C) 2004 Free Software Foundation
6 * cryptsetup related changes
7 * Copyright (C) 2012, Red Hat, Inc. All rights reserved.
8 * Copyright (C) 2012-2014, Milan Broz
10 * This file is free software; you can redistribute it and/or
11 * modify it under the terms of the GNU Lesser General Public
12 * License as published by the Free Software Foundation; either
13 * version 2.1 of the License, or (at your option) any later version.
15 * This file is distributed in the hope that it will be useful,
16 * but WITHOUT ANY WARRANTY; without even the implied warranty of
17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
18 * Lesser General Public License for more details.
20 * You should have received a copy of the GNU Lesser General Public
21 * License along with this file; if not, write to the Free Software
22 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
28 #include "crypto_backend.h"
30 static int hash_buf(const char *src, size_t src_len,
31 char *dst, size_t dst_len,
32 const char *hash_name)
34 struct crypt_hash *hd = NULL;
37 if (crypt_hash_init(&hd, hash_name))
40 r = crypt_hash_write(hd, src, src_len);
43 r = crypt_hash_final(hd, dst, dst_len);
45 crypt_hash_destroy(hd);
52 * PBKDF2 applies a pseudorandom function (see Appendix B.1 for an
53 * example) to derive keys. The length of the derived key is essentially
54 * unbounded. (However, the maximum effective search space for the
55 * derived key may be limited by the structure of the underlying
56 * pseudorandom function. See Appendix B.1 for further discussion.)
57 * PBKDF2 is recommended for new applications.
59 * PBKDF2 (P, S, c, dkLen)
61 * Options: PRF underlying pseudorandom function (hLen
62 * denotes the length in octets of the
63 * pseudorandom function output)
65 * Input: P password, an octet string (ASCII or UTF-8)
66 * S salt, an octet string
67 * c iteration count, a positive integer
68 * dkLen intended length in octets of the derived
69 * key, a positive integer, at most
72 * Output: DK derived key, a dkLen-octet string
76 * if hash_block_size is not zero, the HMAC key is pre-hashed
77 * inside this function.
78 * This prevents situation when crypto backend doesn't support
79 * long HMAC keys or it tries hash long key in every iteration
80 * (because of crypt_final() cannot do simple key reset.
83 #define MAX_PRF_BLOCK_LEN 80
85 int pkcs5_pbkdf2(const char *hash,
86 const char *P, size_t Plen,
87 const char *S, size_t Slen,
88 unsigned int c, unsigned int dkLen,
89 char *DK, unsigned int hash_block_size)
91 struct crypt_hmac *hmac;
92 char U[MAX_PRF_BLOCK_LEN];
93 char T[MAX_PRF_BLOCK_LEN];
94 char P_hash[MAX_PRF_BLOCK_LEN];
95 int i, k, rc = -EINVAL;
96 unsigned int u, hLen, l, r;
97 size_t tmplen = Slen + 4;
100 tmp = alloca(tmplen);
104 hLen = crypt_hmac_size(hash);
105 if (hLen == 0 || hLen > MAX_PRF_BLOCK_LEN)
118 * 1. If dkLen > (2^32 - 1) * hLen, output "derived key too long" and
122 if (dkLen > 4294967295U)
126 * 2. Let l be the number of hLen-octet blocks in the derived key,
127 * rounding up, and let r be the number of octets in the last
130 * l = CEIL (dkLen / hLen) ,
131 * r = dkLen - (l - 1) * hLen .
133 * Here, CEIL (x) is the "ceiling" function, i.e. the smallest
134 * integer greater than, or equal to, x.
140 r = dkLen - (l - 1) * hLen;
143 * 3. For each block of the derived key apply the function F defined
144 * below to the password P, the salt S, the iteration count c, and
145 * the block index to compute the block:
147 * T_1 = F (P, S, c, 1) ,
148 * T_2 = F (P, S, c, 2) ,
150 * T_l = F (P, S, c, l) ,
152 * where the function F is defined as the exclusive-or sum of the
153 * first c iterates of the underlying pseudorandom function PRF
154 * applied to the password P and the concatenation of the salt S
155 * and the block index i:
157 * F (P, S, c, i) = U_1 \xor U_2 \xor ... \xor U_c
161 * U_1 = PRF (P, S || INT (i)) ,
162 * U_2 = PRF (P, U_1) ,
164 * U_c = PRF (P, U_{c-1}) .
166 * Here, INT (i) is a four-octet encoding of the integer i, most
167 * significant octet first.
169 * 4. Concatenate the blocks and extract the first dkLen octets to
170 * produce a derived key DK:
172 * DK = T_1 || T_2 || ... || T_l<0..r-1>
174 * 5. Output the derived key DK.
176 * Note. The construction of the function F follows a "belt-and-
177 * suspenders" approach. The iterates U_i are computed recursively to
178 * remove a degree of parallelism from an opponent; they are exclusive-
179 * ored together to reduce concerns about the recursion degenerating
180 * into a small set of values.
184 /* If hash_block_size is provided, hash password in advance. */
185 if (hash_block_size > 0 && Plen > hash_block_size) {
186 if (hash_buf(P, Plen, P_hash, hLen, hash))
189 if (crypt_hmac_init(&hmac, hash, P_hash, hLen))
191 crypt_backend_memzero(P_hash, sizeof(P_hash));
193 if (crypt_hmac_init(&hmac, hash, P, Plen))
197 for (i = 1; (unsigned int) i <= l; i++) {
200 for (u = 1; u <= c ; u++) {
202 memcpy(tmp, S, Slen);
203 tmp[Slen + 0] = (i & 0xff000000) >> 24;
204 tmp[Slen + 1] = (i & 0x00ff0000) >> 16;
205 tmp[Slen + 2] = (i & 0x0000ff00) >> 8;
206 tmp[Slen + 3] = (i & 0x000000ff) >> 0;
208 if (crypt_hmac_write(hmac, tmp, tmplen))
211 if (crypt_hmac_write(hmac, U, hLen))
215 if (crypt_hmac_final(hmac, U, hLen))
218 for (k = 0; (unsigned int) k < hLen; k++)
222 memcpy(DK + (i - 1) * hLen, T, (unsigned int) i == l ? r : hLen);
226 crypt_hmac_destroy(hmac);
227 crypt_backend_memzero(U, sizeof(U));
228 crypt_backend_memzero(T, sizeof(T));
229 crypt_backend_memzero(tmp, tmplen);
239 unsigned int hash_block_length;
240 unsigned int iterations;
241 const char *password;
242 unsigned int password_length;
244 unsigned int salt_length;
246 unsigned int output_length;
249 struct test_vector test_vectors[] = {
254 "ATHENA.MIT.EDUraeburn", 21,
255 "\xcd\xed\xb5\x28\x1b\xb2\xf8\x01"
256 "\x56\x5a\x11\x22\xb2\x56\x35\x15"
257 "\x0a\xd1\xf7\xa0\x4b\xb9\xf3\xa3"
258 "\x33\xec\xc0\xe2\xe1\xf7\x08\x37", 32
262 "ATHENA.MIT.EDUraeburn", 21,
263 "\x01\xdb\xee\x7f\x4a\x9e\x24\x3e"
264 "\x98\x8b\x62\xc7\x3c\xda\x93\x5d"
265 "\xa0\x53\x78\xb9\x32\x44\xec\x8f"
266 "\x48\xa9\x9e\x61\xad\x79\x9d\x86", 32
270 "ATHENA.MIT.EDUraeburn", 21,
271 "\x5c\x08\xeb\x61\xfd\xf7\x1e\x4e"
272 "\x4e\xc3\xcf\x6b\xa1\xf5\x51\x2b"
273 "\xa7\xe5\x2d\xdb\xc5\xe5\x14\x2f"
274 "\x70\x8a\x31\xe2\xe6\x2b\x1e\x13", 32
278 "\0224VxxV4\022", 8, // "\x1234567878563412
279 "\xd1\xda\xa7\x86\x15\xf2\x87\xe6"
280 "\xa1\xc8\xb1\x20\xd7\x06\x2a\x49"
281 "\x3f\x98\xd2\x03\xe6\xbe\x49\xa6"
282 "\xad\xf4\xfa\x57\x4b\x6e\x64\xee", 32
285 "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"
286 "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", 64,
287 "pass phrase equals block size", 29,
288 "\x13\x9c\x30\xc0\x96\x6b\xc3\x2b"
289 "\xa5\x5f\xdb\xf2\x12\x53\x0a\xc9"
290 "\xc5\xec\x59\xf1\xa4\x52\xf5\xcc"
291 "\x9a\xd9\x40\xfe\xa0\x59\x8e\xd1", 32
294 "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"
295 "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", 65,
296 "pass phrase exceeds block size", 30,
297 "\x9c\xca\xd6\xd4\x68\x77\x0c\xd5"
298 "\x1b\x10\xe6\xa6\x87\x21\xbe\x61"
299 "\x1a\x8b\x4d\x28\x26\x01\xdb\x3b"
300 "\x36\xbe\x92\x46\x91\x5e\xc8\x2a", 32
303 "\360\235\204\236", 4, // g-clef ("\xf09d849e)
304 "EXAMPLE.COMpianist", 18,
305 "\x6b\x9c\xf2\x6d\x45\x45\x5a\x43"
306 "\xa5\xb8\xbb\x27\x6a\x40\x3b\x39"
307 "\xe7\xfe\x37\xa0\xc4\x1e\x02\xc2"
308 "\x81\xff\x30\x69\xe1\xe9\x4f\x52", 32
314 "\x0c\x60\xc8\x0f\x96\x1f\x0e\x71\xf3\xa9"
315 "\xb5\x24\xaf\x60\x12\x06\x2f\xe0\x37\xa6", 20
320 "\xea\x6c\x01\x4d\xc7\x2d\x6f\x8c\xcd\x1e"
321 "\xd9\x2a\xce\x1d\x41\xf0\xd8\xde\x89\x57", 20
326 "\x4b\x00\x79\x01\xb7\x65\x48\x9a\xbe\xad"
327 "\x49\xd9\x26\xf7\x21\xd0\x65\xa4\x29\xc1", 20
329 "sha1", 64, 16777216,
332 "\xee\xfe\x3d\x61\xcd\x4d\xa4\xe4\xe9\x94"
333 "\x5b\x3d\x6b\xa2\x15\x8c\x26\x34\xe9\x84", 20
336 "passwordPASSWORDpassword", 24,
337 "saltSALTsaltSALTsaltSALTsaltSALTsalt", 36,
338 "\x3d\x2e\xec\x4f\xe4\x1c\x84\x9b\x80\xc8"
339 "\xd8\x36\x62\xc0\xe4\x4a\x8b\x29\x1a\x96"
340 "\x4c\xf2\xf0\x70\x38", 25
345 "\x56\xfa\x6a\xa7\x55\x48\x09\x9d\xcc\x37"
346 "\xd7\xf0\x34\x25\xe0\xc3", 16
348 /* empty password test */
352 "\x13\x3a\x4c\xe8\x37\xb4\xd2\x52\x1e\xe2"
353 "\xbf\x03\xe1\x1c\x71\xca\x79\x4e\x07\x97", 20
355 /* Password exceeds block size test */
357 "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"
358 "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", 65,
359 "pass phrase exceeds block size", 30,
360 "\x22\x34\x4b\xc4\xb6\xe3\x26\x75"
361 "\xa8\x09\x0f\x3e\xa8\x0b\xe0\x1d"
362 "\x5f\x95\x12\x6a\x2c\xdd\xc3\xfa"
363 "\xcc\x4a\x5e\x6d\xca\x04\xec\x58", 32
366 "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"
367 "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"
368 "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"
369 "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", 129,
370 "pass phrase exceeds block size", 30,
371 "\x0f\xb2\xed\x2c\x0e\x6e\xfb\x7d"
372 "\x7d\x8e\xdd\x58\x01\xb4\x59\x72"
373 "\x99\x92\x16\x30\x5e\xa4\x36\x8d"
374 "\x76\x14\x80\xf3\xe3\x7a\x22\xb9", 32
376 "whirlpool", 64, 1200,
377 "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"
378 "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", 65,
379 "pass phrase exceeds block size", 30,
380 "\x9c\x1c\x74\xf5\x88\x26\xe7\x6a"
381 "\x53\x58\xf4\x0c\x39\xe7\x80\x89"
382 "\x07\xc0\x31\x19\x9a\x50\xa2\x48"
383 "\xf1\xd9\xfe\x78\x64\xe5\x84\x50", 32
387 static void printhex(const char *s, const char *buf, size_t len)
392 for (i = 0; i < len; i++)
393 printf("\\x%02x", (unsigned char)buf[i]);
398 static int pkcs5_pbkdf2_test_vectors(void)
402 struct test_vector *vec;
404 for (i = 0; i < (sizeof(test_vectors) / sizeof(*test_vectors)); i++) {
405 vec = &test_vectors[i];
406 for (j = 1; j <= vec->output_length; j++) {
407 if (pkcs5_pbkdf2(vec->hash,
408 vec->password, vec->password_length,
409 vec->salt, vec->salt_length,
411 j, result, vec->hash_block_length)) {
412 printf("pbkdf2 failed, vector %d\n", i);
415 if (memcmp(result, vec->output, j) != 0) {
416 printf("vector %u\n", i);
417 printhex(" got", result, j);
418 printhex("want", vec->output, j);
421 memset(result, 0, sizeof(result));