1bf114f1dSAlex Hornung /* Implementation of Password-Based Cryptography as per PKCS#5
2bf114f1dSAlex Hornung * Copyright (C) 2002,2003 Simon Josefsson
3bf114f1dSAlex Hornung * Copyright (C) 2004 Free Software Foundation
4bf114f1dSAlex Hornung *
5bf114f1dSAlex Hornung * LUKS code
6bf114f1dSAlex Hornung * Copyright (C) 2004 Clemens Fruhwirth <clemens@endorphin.org>
7bf114f1dSAlex Hornung * Copyright (C) 2009 Red Hat, Inc. All rights reserved.
8bf114f1dSAlex Hornung *
9bf114f1dSAlex Hornung * This file is free software; you can redistribute it and/or
10bf114f1dSAlex Hornung * modify it under the terms of the GNU Lesser General Public
11bf114f1dSAlex Hornung * License as published by the Free Software Foundation; either
12bf114f1dSAlex Hornung * version 2.1 of the License, or (at your option) any later version.
13bf114f1dSAlex Hornung *
14bf114f1dSAlex Hornung * This file is distributed in the hope that it will be useful,
15bf114f1dSAlex Hornung * but WITHOUT ANY WARRANTY; without even the implied warranty of
16bf114f1dSAlex Hornung * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17bf114f1dSAlex Hornung * Lesser General Public License for more details.
18bf114f1dSAlex Hornung *
19bf114f1dSAlex Hornung * You should have received a copy of the GNU Lesser General Public
20bf114f1dSAlex Hornung * License along with this file; if not, write to the Free Software
21bf114f1dSAlex Hornung * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
22bf114f1dSAlex Hornung *
23bf114f1dSAlex Hornung */
24bf114f1dSAlex Hornung
25bf114f1dSAlex Hornung #include <netinet/in.h>
26bf114f1dSAlex Hornung #include <errno.h>
27bf114f1dSAlex Hornung #include <signal.h>
28bf114f1dSAlex Hornung #include <sys/time.h>
2913af8cbeSAlex Hornung #include <string.h>
3013af8cbeSAlex Hornung #include <strings.h>
3113af8cbeSAlex Hornung #include <stdlib.h>
3213af8cbeSAlex Hornung #include <openssl/evp.h>
3313af8cbeSAlex Hornung #include <openssl/hmac.h>
34bf114f1dSAlex Hornung
35bf114f1dSAlex Hornung static volatile uint64_t __PBKDF2_global_j = 0;
36bf114f1dSAlex Hornung static volatile uint64_t __PBKDF2_performance = 0;
37bf114f1dSAlex Hornung
38bf114f1dSAlex Hornung /*
39bf114f1dSAlex Hornung * 5.2 PBKDF2
40bf114f1dSAlex Hornung *
41bf114f1dSAlex Hornung * PBKDF2 applies a pseudorandom function (see Appendix B.1 for an
42bf114f1dSAlex Hornung * example) to derive keys. The length of the derived key is essentially
43bf114f1dSAlex Hornung * unbounded. (However, the maximum effective search space for the
44bf114f1dSAlex Hornung * derived key may be limited by the structure of the underlying
45bf114f1dSAlex Hornung * pseudorandom function. See Appendix B.1 for further discussion.)
46bf114f1dSAlex Hornung * PBKDF2 is recommended for new applications.
47bf114f1dSAlex Hornung *
48bf114f1dSAlex Hornung * PBKDF2 (P, S, c, dkLen)
49bf114f1dSAlex Hornung *
50bf114f1dSAlex Hornung * Options: PRF underlying pseudorandom function (hLen
51bf114f1dSAlex Hornung * denotes the length in octets of the
52bf114f1dSAlex Hornung * pseudorandom function output)
53bf114f1dSAlex Hornung *
54bf114f1dSAlex Hornung * Input: P password, an octet string (ASCII or UTF-8)
55bf114f1dSAlex Hornung * S salt, an octet string
56bf114f1dSAlex Hornung * c iteration count, a positive integer
57bf114f1dSAlex Hornung * dkLen intended length in octets of the derived
58bf114f1dSAlex Hornung * key, a positive integer, at most
59bf114f1dSAlex Hornung * (2^32 - 1) * hLen
60bf114f1dSAlex Hornung *
61bf114f1dSAlex Hornung * Output: DK derived key, a dkLen-octet string
62bf114f1dSAlex Hornung */
63bf114f1dSAlex Hornung
64bf114f1dSAlex Hornung #define MAX_PRF_BLOCK_LEN 80
65bf114f1dSAlex Hornung
pkcs5_pbkdf2(const char * hash,const char * P,size_t Plen,const char * S,size_t Slen,unsigned int c,unsigned int dkLen,char * DK,int perfcheck)66bf114f1dSAlex Hornung static int pkcs5_pbkdf2(const char *hash,
67bf114f1dSAlex Hornung const char *P, size_t Plen,
68bf114f1dSAlex Hornung const char *S, size_t Slen,
69bf114f1dSAlex Hornung unsigned int c, unsigned int dkLen,
70bf114f1dSAlex Hornung char *DK, int perfcheck)
71bf114f1dSAlex Hornung {
72bf114f1dSAlex Hornung char U[MAX_PRF_BLOCK_LEN];
73bf114f1dSAlex Hornung char T[MAX_PRF_BLOCK_LEN];
7413af8cbeSAlex Hornung const EVP_MD *PRF;
75*6f5ec8b5SAntonio Huete Jimenez HMAC_CTX *ctx;
7613af8cbeSAlex Hornung int i, k, rc = -EINVAL;
77bf114f1dSAlex Hornung unsigned int u, hLen, l, r;
78bf114f1dSAlex Hornung unsigned char *p;
79bf114f1dSAlex Hornung size_t tmplen = Slen + 4;
80bf114f1dSAlex Hornung char *tmp;
81bf114f1dSAlex Hornung
82bf114f1dSAlex Hornung tmp = alloca(tmplen);
83bf114f1dSAlex Hornung if (tmp == NULL)
84bf114f1dSAlex Hornung return -ENOMEM;
85bf114f1dSAlex Hornung
8613af8cbeSAlex Hornung OpenSSL_add_all_digests();
8713af8cbeSAlex Hornung PRF = EVP_get_digestbyname(hash);
8813af8cbeSAlex Hornung if (PRF == NULL) {
8913af8cbeSAlex Hornung printf("pkcs5_pbkdf2: invalid hash %s\n", hash);
90bf114f1dSAlex Hornung return -EINVAL;
9113af8cbeSAlex Hornung }
92bf114f1dSAlex Hornung
9313af8cbeSAlex Hornung hLen = EVP_MD_size(PRF);
94bf114f1dSAlex Hornung if (hLen == 0 || hLen > MAX_PRF_BLOCK_LEN)
95bf114f1dSAlex Hornung return -EINVAL;
96bf114f1dSAlex Hornung
97bf114f1dSAlex Hornung if (c == 0)
98bf114f1dSAlex Hornung return -EINVAL;
99bf114f1dSAlex Hornung
100bf114f1dSAlex Hornung if (dkLen == 0)
101bf114f1dSAlex Hornung return -EINVAL;
102bf114f1dSAlex Hornung
103bf114f1dSAlex Hornung /*
104bf114f1dSAlex Hornung *
105bf114f1dSAlex Hornung * Steps:
106bf114f1dSAlex Hornung *
107bf114f1dSAlex Hornung * 1. If dkLen > (2^32 - 1) * hLen, output "derived key too long" and
108bf114f1dSAlex Hornung * stop.
109bf114f1dSAlex Hornung */
110bf114f1dSAlex Hornung
111bf114f1dSAlex Hornung if (dkLen > 4294967295U)
112bf114f1dSAlex Hornung return -EINVAL;
113bf114f1dSAlex Hornung
114bf114f1dSAlex Hornung /*
115bf114f1dSAlex Hornung * 2. Let l be the number of hLen-octet blocks in the derived key,
116bf114f1dSAlex Hornung * rounding up, and let r be the number of octets in the last
117bf114f1dSAlex Hornung * block:
118bf114f1dSAlex Hornung *
119bf114f1dSAlex Hornung * l = CEIL (dkLen / hLen) ,
120bf114f1dSAlex Hornung * r = dkLen - (l - 1) * hLen .
121bf114f1dSAlex Hornung *
122bf114f1dSAlex Hornung * Here, CEIL (x) is the "ceiling" function, i.e. the smallest
123bf114f1dSAlex Hornung * integer greater than, or equal to, x.
124bf114f1dSAlex Hornung */
125bf114f1dSAlex Hornung
126bf114f1dSAlex Hornung l = dkLen / hLen;
127bf114f1dSAlex Hornung if (dkLen % hLen)
128bf114f1dSAlex Hornung l++;
129bf114f1dSAlex Hornung r = dkLen - (l - 1) * hLen;
130bf114f1dSAlex Hornung
131bf114f1dSAlex Hornung /*
132bf114f1dSAlex Hornung * 3. For each block of the derived key apply the function F defined
133bf114f1dSAlex Hornung * below to the password P, the salt S, the iteration count c, and
134bf114f1dSAlex Hornung * the block index to compute the block:
135bf114f1dSAlex Hornung *
136bf114f1dSAlex Hornung * T_1 = F (P, S, c, 1) ,
137bf114f1dSAlex Hornung * T_2 = F (P, S, c, 2) ,
138bf114f1dSAlex Hornung * ...
139bf114f1dSAlex Hornung * T_l = F (P, S, c, l) ,
140bf114f1dSAlex Hornung *
141bf114f1dSAlex Hornung * where the function F is defined as the exclusive-or sum of the
142bf114f1dSAlex Hornung * first c iterates of the underlying pseudorandom function PRF
143bf114f1dSAlex Hornung * applied to the password P and the concatenation of the salt S
144bf114f1dSAlex Hornung * and the block index i:
145bf114f1dSAlex Hornung *
146bf114f1dSAlex Hornung * F (P, S, c, i) = U_1 \xor U_2 \xor ... \xor U_c
147bf114f1dSAlex Hornung *
148bf114f1dSAlex Hornung * where
149bf114f1dSAlex Hornung *
150bf114f1dSAlex Hornung * U_1 = PRF (P, S || INT (i)) ,
151bf114f1dSAlex Hornung * U_2 = PRF (P, U_1) ,
152bf114f1dSAlex Hornung * ...
153bf114f1dSAlex Hornung * U_c = PRF (P, U_{c-1}) .
154bf114f1dSAlex Hornung *
155bf114f1dSAlex Hornung * Here, INT (i) is a four-octet encoding of the integer i, most
156bf114f1dSAlex Hornung * significant octet first.
157bf114f1dSAlex Hornung *
158bf114f1dSAlex Hornung * 4. Concatenate the blocks and extract the first dkLen octets to
159bf114f1dSAlex Hornung * produce a derived key DK:
160bf114f1dSAlex Hornung *
161bf114f1dSAlex Hornung * DK = T_1 || T_2 || ... || T_l<0..r-1>
162bf114f1dSAlex Hornung *
163bf114f1dSAlex Hornung * 5. Output the derived key DK.
164bf114f1dSAlex Hornung *
165bf114f1dSAlex Hornung * Note. The construction of the function F follows a "belt-and-
166bf114f1dSAlex Hornung * suspenders" approach. The iterates U_i are computed recursively to
167bf114f1dSAlex Hornung * remove a degree of parallelism from an opponent; they are exclusive-
168bf114f1dSAlex Hornung * ored together to reduce concerns about the recursion degenerating
169bf114f1dSAlex Hornung * into a small set of values.
170bf114f1dSAlex Hornung *
171bf114f1dSAlex Hornung */
172*6f5ec8b5SAntonio Huete Jimenez ctx = HMAC_CTX_new();
173bf114f1dSAlex Hornung for (i = 1; (uint) i <= l; i++) {
174bf114f1dSAlex Hornung memset(T, 0, hLen);
175bf114f1dSAlex Hornung
176bf114f1dSAlex Hornung for (u = 1; u <= c ; u++) {
177bf114f1dSAlex Hornung if (u == 1) {
178bf114f1dSAlex Hornung memcpy(tmp, S, Slen);
179bf114f1dSAlex Hornung tmp[Slen + 0] = (i & 0xff000000) >> 24;
180bf114f1dSAlex Hornung tmp[Slen + 1] = (i & 0x00ff0000) >> 16;
181bf114f1dSAlex Hornung tmp[Slen + 2] = (i & 0x0000ff00) >> 8;
182bf114f1dSAlex Hornung tmp[Slen + 3] = (i & 0x000000ff) >> 0;
183*6f5ec8b5SAntonio Huete Jimenez HMAC_Init_ex(ctx, P, Plen, PRF, NULL);
184*6f5ec8b5SAntonio Huete Jimenez HMAC_Update(ctx, tmp, tmplen);
185*6f5ec8b5SAntonio Huete Jimenez HMAC_Final(ctx, U, NULL);
186bf114f1dSAlex Hornung } else {
18713af8cbeSAlex Hornung HMAC(PRF, P, Plen, U, hLen, U, NULL);
188bf114f1dSAlex Hornung }
189bf114f1dSAlex Hornung
190bf114f1dSAlex Hornung for (k = 0; (uint) k < hLen; k++)
191bf114f1dSAlex Hornung T[k] ^= U[k];
192bf114f1dSAlex Hornung
193bf114f1dSAlex Hornung if (perfcheck && __PBKDF2_performance) {
194bf114f1dSAlex Hornung rc = 0;
195bf114f1dSAlex Hornung goto out;
196bf114f1dSAlex Hornung }
197bf114f1dSAlex Hornung
198bf114f1dSAlex Hornung if (perfcheck)
199bf114f1dSAlex Hornung __PBKDF2_global_j++;
200bf114f1dSAlex Hornung }
201bf114f1dSAlex Hornung
202bf114f1dSAlex Hornung memcpy(DK + (i - 1) * hLen, T, (uint) i == l ? r : hLen);
203bf114f1dSAlex Hornung }
204bf114f1dSAlex Hornung rc = 0;
205bf114f1dSAlex Hornung out:
206*6f5ec8b5SAntonio Huete Jimenez HMAC_CTX_free(ctx);
207bf114f1dSAlex Hornung return rc;
208bf114f1dSAlex Hornung }
209bf114f1dSAlex Hornung
PBKDF2_HMAC(const char * hash,const char * password,size_t passwordLen,const char * salt,size_t saltLen,unsigned int iterations,char * dKey,size_t dKeyLen)210bf114f1dSAlex Hornung int PBKDF2_HMAC(const char *hash,
211bf114f1dSAlex Hornung const char *password, size_t passwordLen,
212bf114f1dSAlex Hornung const char *salt, size_t saltLen, unsigned int iterations,
213bf114f1dSAlex Hornung char *dKey, size_t dKeyLen)
214bf114f1dSAlex Hornung {
215bf114f1dSAlex Hornung return pkcs5_pbkdf2(hash, password, passwordLen, salt, saltLen,
216bf114f1dSAlex Hornung iterations, (unsigned int)dKeyLen, dKey, 0);
217bf114f1dSAlex Hornung }
218bf114f1dSAlex Hornung
PBKDF2_HMAC_ready(const char * hash)219bf114f1dSAlex Hornung int PBKDF2_HMAC_ready(const char *hash)
220bf114f1dSAlex Hornung {
22113af8cbeSAlex Hornung const EVP_MD *md;
222bf114f1dSAlex Hornung
22313af8cbeSAlex Hornung OpenSSL_add_all_digests();
22413af8cbeSAlex Hornung md = EVP_get_digestbyname(hash);
22513af8cbeSAlex Hornung if (md == NULL)
226bf114f1dSAlex Hornung return -EINVAL;
227bf114f1dSAlex Hornung
228bf114f1dSAlex Hornung /* Used hash must have at least 160 bits */
22913af8cbeSAlex Hornung if (EVP_MD_size(md) < 20)
230bf114f1dSAlex Hornung return -EINVAL;
231bf114f1dSAlex Hornung
232bf114f1dSAlex Hornung return 1;
233bf114f1dSAlex Hornung }
234bf114f1dSAlex Hornung
sigvtalarm(int foo)235bf114f1dSAlex Hornung static void sigvtalarm(int foo)
236bf114f1dSAlex Hornung {
237bf114f1dSAlex Hornung __PBKDF2_performance = __PBKDF2_global_j;
238bf114f1dSAlex Hornung }
239bf114f1dSAlex Hornung
240bf114f1dSAlex Hornung /* This code benchmarks PBKDF2 and returns iterations/second using wth specified hash */
PBKDF2_performance_check(const char * hash,uint64_t * iter)241bf114f1dSAlex Hornung int PBKDF2_performance_check(const char *hash, uint64_t *iter)
242bf114f1dSAlex Hornung {
243bf114f1dSAlex Hornung int r;
244bf114f1dSAlex Hornung char buf;
245bf114f1dSAlex Hornung struct itimerval it;
246bf114f1dSAlex Hornung
24713af8cbeSAlex Hornung if (__PBKDF2_global_j) {
24813af8cbeSAlex Hornung printf("foo1\n");
249bf114f1dSAlex Hornung return -EBUSY;
25013af8cbeSAlex Hornung }
251bf114f1dSAlex Hornung
25213af8cbeSAlex Hornung if (!PBKDF2_HMAC_ready(hash)) {
25313af8cbeSAlex Hornung printf("foo2\n");
254bf114f1dSAlex Hornung return -EINVAL;
25513af8cbeSAlex Hornung }
256bf114f1dSAlex Hornung
257bf114f1dSAlex Hornung signal(SIGVTALRM,sigvtalarm);
258bf114f1dSAlex Hornung it.it_interval.tv_usec = 0;
259bf114f1dSAlex Hornung it.it_interval.tv_sec = 0;
260bf114f1dSAlex Hornung it.it_value.tv_usec = 0;
261bf114f1dSAlex Hornung it.it_value.tv_sec = 1;
26213af8cbeSAlex Hornung if (setitimer (ITIMER_VIRTUAL, &it, NULL) < 0) {
26313af8cbeSAlex Hornung printf("foo3\n");
264bf114f1dSAlex Hornung return -EINVAL;
26513af8cbeSAlex Hornung }
266bf114f1dSAlex Hornung
267bf114f1dSAlex Hornung r = pkcs5_pbkdf2(hash, "foo", 3, "bar", 3, ~(0U), 1, &buf, 1);
268bf114f1dSAlex Hornung *iter = __PBKDF2_performance;
269bf114f1dSAlex Hornung __PBKDF2_global_j = 0;
270bf114f1dSAlex Hornung __PBKDF2_performance = 0;
271bf114f1dSAlex Hornung return r;
272bf114f1dSAlex Hornung }
273