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