1 /* $NetBSD: pkcs5_pbkdf2.c,v 1.17 2021/11/22 16:04:03 nia Exp $ */
2
3 /*-
4 * Copyright (c) 2002, 2003 The NetBSD Foundation, Inc.
5 * All rights reserved.
6 *
7 * This code is derived from software contributed to The NetBSD Foundation
8 * by Roland C. Dowdeswell.
9 *
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
12 * are met:
13 * 1. Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 * notice, this list of conditions and the following disclaimer in the
17 * documentation and/or other materials provided with the distribution.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
20 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
21 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
23 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
24 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
25 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
26 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
27 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
28 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
29 * POSSIBILITY OF SUCH DAMAGE.
30 */
31
32 /*
33 * This code is an implementation of PKCS #5 PBKDF2 which is described
34 * in:
35 *
36 * ``PKCS #5 v2.0: Password-Based Cryptography Standard'', RSA Laboratories,
37 * March 25, 1999.
38 *
39 * and can be found at the following URL:
40 *
41 * http://www.rsasecurity.com/rsalabs/pkcs/pkcs-5/
42 *
43 * It was also republished as RFC 2898.
44 */
45
46
47 #include <sys/cdefs.h>
48 #ifndef lint
49 __RCSID("$NetBSD: pkcs5_pbkdf2.c,v 1.17 2021/11/22 16:04:03 nia Exp $");
50 #endif
51
52 #include <sys/resource.h>
53 #include <sys/endian.h>
54
55 #include <assert.h>
56 #include <stdio.h>
57 #include <stdlib.h>
58 #include <string.h>
59 #include <err.h>
60 #include <util.h>
61
62 #include "pkcs5_pbkdf2.h"
63 #include "utils.h"
64
65 static void prf_iterate(u_int8_t *, const u_int8_t *, size_t,
66 const u_int8_t *, size_t, size_t, size_t);
67 static int pkcs5_pbkdf2_time(size_t, size_t);
68
69 #define PRF_BLOCKLEN 20
70
71 static void
prf_iterate(u_int8_t * r,const u_int8_t * P,size_t Plen,const u_int8_t * S,size_t Slen,size_t c,size_t ind)72 prf_iterate(u_int8_t *r, const u_int8_t *P, size_t Plen,
73 const u_int8_t *S, size_t Slen, size_t c, size_t ind)
74 {
75 int first_time = 1;
76 size_t i;
77 size_t datalen;
78 ssize_t tmplen;
79 u_int8_t *data;
80 u_int8_t tmp[128];
81
82 data = emalloc(Slen + 4);
83 (void)memcpy(data, S, Slen);
84 be32enc(data + Slen, ind);
85 datalen = Slen + 4;
86
87 for (i=0; i < c; i++) {
88 tmplen = hmac("sha1", P, Plen, data, datalen, tmp, sizeof(tmp));
89
90 assert(tmplen == PRF_BLOCKLEN);
91
92 if (first_time) {
93 (void)memcpy(r, tmp, PRF_BLOCKLEN);
94 first_time = 0;
95 } else
96 memxor(r, tmp, PRF_BLOCKLEN);
97 (void)memcpy(data, tmp, PRF_BLOCKLEN);
98 datalen = PRF_BLOCKLEN;
99 }
100 free(data);
101 }
102
103 /*
104 * pkcs5_pbkdf2 takes all of its lengths in bytes.
105 */
106
107 int
pkcs5_pbkdf2(u_int8_t ** r,size_t dkLen,const u_int8_t * P,size_t Plen,const u_int8_t * S,size_t Slen,size_t c,int compat)108 pkcs5_pbkdf2(u_int8_t **r, size_t dkLen, const u_int8_t *P, size_t Plen,
109 const u_int8_t *S, size_t Slen, size_t c, int compat)
110 {
111 size_t i;
112 size_t l;
113
114 /* sanity */
115 if (!r)
116 return -1;
117 if (dkLen == 0)
118 return -1;
119 if (c < 1)
120 return -1;
121
122 /* Step 2 */
123 l = (dkLen + PRF_BLOCKLEN - 1) / PRF_BLOCKLEN;
124
125 /* allocate the output */
126 *r = emalloc(l * PRF_BLOCKLEN);
127
128 /* Step 3 */
129 for (i = 0; i < l; i++)
130 prf_iterate(*r + (PRF_BLOCKLEN * i), P, Plen, S, Slen, c,
131 (compat?i:i+1));
132
133 /* Step 4 and 5
134 * by the structure of the code, we do not need to concatenate
135 * the blocks, they're already concatenated. We do not extract
136 * the first dkLen octets, since we [naturally] assume that the
137 * calling function will use only the octets that it needs and
138 * the free(3) will free all of the allocated memory.
139 */
140 return 0;
141 }
142
143 /*
144 * We use predefined lengths for the password and salt to ensure that
145 * no analysis can be done on the output of the calibration based on
146 * those parameters. We do not do the same for dkLen because:
147 * 1. dkLen is known to the attacker if they know the iteration
148 * count, and
149 * 2. using the wrong dkLen will skew the calibration by an
150 * integral factor n = (dkLen / 160).
151 */
152
153 #define CAL_PASSLEN 64
154 #define CAL_SALTLEN 64
155 #define CAL_TIME 30000 /* Minimum number of microseconds that
156 * are considered significant.
157 */
158
159 /*
160 * We return the user time in microseconds that c iterations
161 * of the algorithm take.
162 */
163
164 static int
pkcs5_pbkdf2_time(size_t dkLen,size_t c)165 pkcs5_pbkdf2_time(size_t dkLen, size_t c)
166 {
167 struct rusage start;
168 struct rusage end;
169 int ret;
170 u_int8_t *r = NULL;
171 u_int8_t P[CAL_PASSLEN];
172 u_int8_t S[CAL_SALTLEN];
173
174 (void)getrusage(RUSAGE_SELF, &start);
175 /* XXX compat flag at end to be removed when _OLD keygen method is */
176 ret = pkcs5_pbkdf2(&r, dkLen, P, sizeof(P), S, sizeof(S), c, 0);
177 if (ret)
178 return ret;
179 (void)getrusage(RUSAGE_SELF, &end);
180 free(r);
181
182 return (end.ru_utime.tv_sec - start.ru_utime.tv_sec) * 1000000
183 + (end.ru_utime.tv_usec - start.ru_utime.tv_usec);
184 }
185
186 int
pkcs5_pbkdf2_calibrate(size_t dkLen,int microseconds)187 pkcs5_pbkdf2_calibrate(size_t dkLen, int microseconds)
188 {
189 size_t c;
190 int t = 0;
191 size_t ret, i;
192
193 fprintf(stderr, "pkcs5_pbkdf2: calibrating iterations...");
194
195 for (i = 0; i < 5; i++) {
196 /*
197 * First we get a meaningfully long time by doubling the
198 * iteration count until it takes longer than CAL_TIME. This
199 * should take approximately 2 * CAL_TIME.
200 */
201 for (c = 1;; c *= 2) {
202 t = pkcs5_pbkdf2_time(dkLen, c);
203 fprintf(stderr, ".");
204 if (t > CAL_TIME)
205 break;
206 }
207
208 /* Now that we know that, we scale it. */
209 ret = (size_t) ((u_int64_t) c * microseconds / t);
210
211 /*
212 * Since it is quite important to not get this wrong,
213 * we test the result.
214 */
215
216 t = pkcs5_pbkdf2_time(dkLen, ret);
217
218 /* if we are over 5% off, return an error */
219 if (abs(microseconds - t) > (microseconds / 20))
220 continue;
221 fprintf(stderr, " done\n");
222 return ret;
223 }
224 fprintf(stderr, " failed\n");
225 return -1;
226 }
227