"Fossies" - the Fresh Open Source Software Archive 
Member "cryptsetup-2.4.3/lib/crypto_backend/pbkdf_check.c" (13 Jan 2022, 11658 Bytes) of package /linux/misc/cryptsetup-2.4.3.tar.xz:
As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style:
standard) with prefixed line numbers and
code folding option.
Alternatively you can here
view or
download the uninterpreted source code file.
For more information about "pbkdf_check.c" see the
Fossies "Dox" file reference documentation and the last
Fossies "Diffs" side-by-side code changes report:
2.3.6_vs_2.4.0.
1 /*
2 * PBKDF performance check
3 * Copyright (C) 2012-2021 Red Hat, Inc. All rights reserved.
4 * Copyright (C) 2012-2021 Milan Broz
5 * Copyright (C) 2016-2020 Ondrej Mosnacek
6 *
7 * This file is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU Lesser General Public
9 * License as published by the Free Software Foundation; either
10 * version 2.1 of the License, or (at your option) any later version.
11 *
12 * This file is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 * Lesser General Public License for more details.
16 *
17 * You should have received a copy of the GNU Lesser General Public
18 * License along with this file; if not, write to the Free Software
19 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
20 */
21
22 #include <stdlib.h>
23 #include <errno.h>
24 #include <limits.h>
25 #include <time.h>
26 #include <sys/time.h>
27 #include <sys/resource.h>
28 #include "crypto_backend.h"
29
30 #ifndef CLOCK_MONOTONIC_RAW
31 #define CLOCK_MONOTONIC_RAW CLOCK_MONOTONIC
32 #endif
33
34 #define BENCH_MIN_MS 250
35 #define BENCH_MIN_MS_FAST 10
36 #define BENCH_PERCENT_ATLEAST 95
37 #define BENCH_PERCENT_ATMOST 110
38 #define BENCH_SAMPLES_FAST 3
39 #define BENCH_SAMPLES_SLOW 1
40
41 /* These PBKDF2 limits must be never violated */
42 int crypt_pbkdf_get_limits(const char *kdf, struct crypt_pbkdf_limits *limits)
43 {
44 if (!kdf || !limits)
45 return -EINVAL;
46
47 if (!strcmp(kdf, "pbkdf2")) {
48 limits->min_iterations = 1000; /* recommendation in NIST SP 800-132 */
49 limits->max_iterations = UINT32_MAX;
50 limits->min_memory = 0; /* N/A */
51 limits->min_bench_memory=0; /* N/A */
52 limits->max_memory = 0; /* N/A */
53 limits->min_parallel = 0; /* N/A */
54 limits->max_parallel = 0; /* N/A */
55 return 0;
56 } else if (!strcmp(kdf, "argon2i") || !strcmp(kdf, "argon2id")) {
57 limits->min_iterations = 4;
58 limits->max_iterations = UINT32_MAX;
59 limits->min_memory = 32; /* hard limit */
60 limits->min_bench_memory=64*1024; /* 64 MiB minimum for benchmark */
61 limits->max_memory = 4*1024*1024; /* 4GiB */
62 limits->min_parallel = 1;
63 limits->max_parallel = 4;
64 return 0;
65 }
66
67 return -EINVAL;
68 }
69
70 static long time_ms(struct rusage *start, struct rusage *end)
71 {
72 int count_kernel_time = 0;
73 long ms;
74
75 if (crypt_backend_flags() & CRYPT_BACKEND_KERNEL)
76 count_kernel_time = 1;
77
78 /*
79 * If there is no self usage info, count system time.
80 * This seem like getrusage() bug in some hypervisors...
81 */
82 if (!end->ru_utime.tv_sec && !start->ru_utime.tv_sec &&
83 !end->ru_utime.tv_usec && !start->ru_utime.tv_usec)
84 count_kernel_time = 1;
85
86 ms = (end->ru_utime.tv_sec - start->ru_utime.tv_sec) * 1000;
87 ms += (end->ru_utime.tv_usec - start->ru_utime.tv_usec) / 1000;
88
89 if (count_kernel_time) {
90 ms += (end->ru_stime.tv_sec - start->ru_stime.tv_sec) * 1000;
91 ms += (end->ru_stime.tv_usec - start->ru_stime.tv_usec) / 1000;
92 }
93
94 return ms;
95 }
96
97 static long timespec_ms(struct timespec *start, struct timespec *end)
98 {
99 return (end->tv_sec - start->tv_sec) * 1000 +
100 (end->tv_nsec - start->tv_nsec) / (1000 * 1000);
101 }
102
103 static int measure_argon2(const char *kdf, const char *password, size_t password_length,
104 const char *salt, size_t salt_length,
105 char *key, size_t key_length,
106 uint32_t t_cost, uint32_t m_cost, uint32_t parallel,
107 size_t samples, long ms_atleast, long *out_ms)
108 {
109 long ms, ms_min = LONG_MAX;
110 int r;
111 size_t i;
112
113 for (i = 0; i < samples; i++) {
114 struct timespec tstart, tend;
115
116 /*
117 * NOTE: We must use clock_gettime here, because Argon2 can run over
118 * multiple threads, and thus we care about real time, not CPU time!
119 */
120 if (clock_gettime(CLOCK_MONOTONIC_RAW, &tstart) < 0)
121 return -EINVAL;
122
123 r = crypt_pbkdf(kdf, NULL, password, password_length, salt,
124 salt_length, key, key_length, t_cost, m_cost, parallel);
125 if (r < 0)
126 return r;
127
128 if (clock_gettime(CLOCK_MONOTONIC_RAW, &tend) < 0)
129 return -EINVAL;
130
131 ms = timespec_ms(&tstart, &tend);
132 if (ms < 0)
133 return -EINVAL;
134
135 if (ms < ms_atleast) {
136 /* early exit */
137 ms_min = ms;
138 break;
139 }
140 if (ms < ms_min) {
141 ms_min = ms;
142 }
143 }
144 *out_ms = ms_min;
145 return 0;
146 }
147
148 #define CONTINUE 0
149 #define FINAL 1
150 static int next_argon2_params(uint32_t *t_cost, uint32_t *m_cost,
151 uint32_t min_t_cost, uint32_t min_m_cost,
152 uint32_t max_m_cost, long ms, uint32_t target_ms)
153 {
154 uint32_t old_t_cost, old_m_cost, new_t_cost, new_m_cost;
155 uint64_t num, denom;
156
157 old_t_cost = *t_cost;
158 old_m_cost = *m_cost;
159
160 if ((uint32_t)ms > target_ms) {
161 /* decreasing, first try to lower t_cost, then m_cost */
162 num = (uint64_t)*t_cost * (uint64_t)target_ms;
163 denom = (uint64_t)ms;
164 new_t_cost = (uint32_t)(num / denom);
165 if (new_t_cost < min_t_cost) {
166 num = (uint64_t)*t_cost * (uint64_t)*m_cost *
167 (uint64_t)target_ms;
168 denom = (uint64_t)min_t_cost * (uint64_t)ms;
169 *t_cost = min_t_cost;
170 *m_cost = (uint32_t)(num / denom);
171 if (*m_cost < min_m_cost) {
172 *m_cost = min_m_cost;
173 return FINAL;
174 }
175 } else {
176 *t_cost = new_t_cost;
177 }
178 } else {
179 /* increasing, first try to increase m_cost, then t_cost */
180 num = (uint64_t)*m_cost * (uint64_t)target_ms;
181 denom = (uint64_t)ms;
182 new_m_cost = (uint32_t)(num / denom);
183 if (new_m_cost > max_m_cost) {
184 num = (uint64_t)*t_cost * (uint64_t)*m_cost *
185 (uint64_t)target_ms;
186 denom = (uint64_t)max_m_cost * (uint64_t)ms;
187 *t_cost = (uint32_t)(num / denom);
188 *m_cost = max_m_cost;
189 if (*t_cost <= min_t_cost) {
190 *t_cost = min_t_cost;
191 return FINAL;
192 }
193 } else if (new_m_cost < min_m_cost) {
194 *m_cost = min_m_cost;
195 return FINAL;
196 } else {
197 *m_cost = new_m_cost;
198 }
199 }
200
201 /* do not continue if it is the same as in the previous run */
202 if (old_t_cost == *t_cost && old_m_cost == *m_cost)
203 return FINAL;
204
205 return CONTINUE;
206 }
207
208 static int crypt_argon2_check(const char *kdf, const char *password,
209 size_t password_length, const char *salt,
210 size_t salt_length, size_t key_length,
211 uint32_t min_t_cost, uint32_t min_m_cost, uint32_t max_m_cost,
212 uint32_t parallel, uint32_t target_ms,
213 uint32_t *out_t_cost, uint32_t *out_m_cost,
214 int (*progress)(uint32_t time_ms, void *usrptr),
215 void *usrptr)
216 {
217 int r = 0;
218 char *key = NULL;
219 uint32_t t_cost, m_cost;
220 long ms;
221 long ms_atleast = (long)target_ms * BENCH_PERCENT_ATLEAST / 100;
222 long ms_atmost = (long)target_ms * BENCH_PERCENT_ATMOST / 100;
223
224 if (key_length <= 0 || target_ms <= 0)
225 return -EINVAL;
226
227 if (min_m_cost < (parallel * 8))
228 min_m_cost = parallel * 8;
229
230 if (max_m_cost < min_m_cost)
231 return -EINVAL;
232
233 key = malloc(key_length);
234 if (!key)
235 return -ENOMEM;
236
237 t_cost = min_t_cost;
238 m_cost = min_m_cost;
239
240 /* 1. Find some small parameters, s. t. ms >= BENCH_MIN_MS: */
241 while (1) {
242 r = measure_argon2(kdf, password, password_length, salt, salt_length,
243 key, key_length, t_cost, m_cost, parallel,
244 BENCH_SAMPLES_FAST, BENCH_MIN_MS, &ms);
245 if (!r) {
246 /* Update parameters to actual measurement */
247 *out_t_cost = t_cost;
248 *out_m_cost = m_cost;
249 if (progress && progress((uint32_t)ms, usrptr))
250 r = -EINTR;
251 }
252
253 if (r < 0)
254 goto out;
255
256 if (ms >= BENCH_MIN_MS)
257 break;
258
259 if (m_cost == max_m_cost) {
260 if (ms < BENCH_MIN_MS_FAST)
261 t_cost *= 16;
262 else {
263 uint32_t new = (t_cost * BENCH_MIN_MS) / (uint32_t)ms;
264 if (new == t_cost)
265 break;
266
267 t_cost = new;
268 }
269 } else {
270 if (ms < BENCH_MIN_MS_FAST)
271 m_cost *= 16;
272 else {
273 uint32_t new = (m_cost * BENCH_MIN_MS) / (uint32_t)ms;
274 if (new == m_cost)
275 break;
276
277 m_cost = new;
278 }
279 if (m_cost > max_m_cost) {
280 m_cost = max_m_cost;
281 }
282 }
283 }
284 /*
285 * 2. Use the params obtained in (1.) to estimate the target params.
286 * 3. Then repeatedly measure the candidate params and if they fall out of
287 * the acceptance range (+-5 %), try to improve the estimate:
288 */
289 do {
290 if (next_argon2_params(&t_cost, &m_cost, min_t_cost, min_m_cost,
291 max_m_cost, ms, target_ms)) {
292 /* Update parameters to final computation */
293 *out_t_cost = t_cost;
294 *out_m_cost = m_cost;
295 break;
296 }
297
298 r = measure_argon2(kdf, password, password_length, salt, salt_length,
299 key, key_length, t_cost, m_cost, parallel,
300 BENCH_SAMPLES_SLOW, ms_atleast, &ms);
301
302 if (!r) {
303 /* Update parameters to actual measurement */
304 *out_t_cost = t_cost;
305 *out_m_cost = m_cost;
306 if (progress && progress((uint32_t)ms, usrptr))
307 r = -EINTR;
308 }
309
310 if (r < 0)
311 break;
312
313 } while (ms < ms_atleast || ms > ms_atmost);
314 out:
315 if (key) {
316 crypt_backend_memzero(key, key_length);
317 free(key);
318 }
319 return r;
320 }
321
322 /* This code benchmarks PBKDF and returns iterations/second using specified hash */
323 static int crypt_pbkdf_check(const char *kdf, const char *hash,
324 const char *password, size_t password_length,
325 const char *salt, size_t salt_length,
326 size_t key_length, uint32_t *iter_secs, uint32_t target_ms,
327 int (*progress)(uint32_t time_ms, void *usrptr), void *usrptr)
328
329 {
330 struct rusage rstart, rend;
331 int r = 0, step = 0;
332 long ms = 0;
333 char *key = NULL;
334 uint32_t iterations;
335 double PBKDF2_temp;
336
337 if (!kdf || !hash || key_length <= 0)
338 return -EINVAL;
339
340 key = malloc(key_length);
341 if (!key)
342 return -ENOMEM;
343
344 *iter_secs = 0;
345 iterations = 1 << 15;
346 while (1) {
347 if (getrusage(RUSAGE_SELF, &rstart) < 0) {
348 r = -EINVAL;
349 goto out;
350 }
351
352 r = crypt_pbkdf(kdf, hash, password, password_length, salt,
353 salt_length, key, key_length, iterations, 0, 0);
354
355 if (r < 0)
356 goto out;
357
358 if (getrusage(RUSAGE_SELF, &rend) < 0) {
359 r = -EINVAL;
360 goto out;
361 }
362
363 ms = time_ms(&rstart, &rend);
364 if (ms) {
365 PBKDF2_temp = (double)iterations * target_ms / ms;
366 if (PBKDF2_temp > UINT32_MAX) {
367 r = -EINVAL;
368 goto out;
369 }
370 *iter_secs = (uint32_t)PBKDF2_temp;
371 }
372
373 if (progress && progress((uint32_t)ms, usrptr)) {
374 r = -EINTR;
375 goto out;
376 }
377
378 if (ms > 500)
379 break;
380
381 if (ms <= 62)
382 iterations <<= 4;
383 else if (ms <= 125)
384 iterations <<= 3;
385 else if (ms <= 250)
386 iterations <<= 2;
387 else
388 iterations <<= 1;
389
390 if (++step > 10 || !iterations) {
391 r = -EINVAL;
392 goto out;
393 }
394 }
395 out:
396 if (key) {
397 crypt_backend_memzero(key, key_length);
398 free(key);
399 }
400 return r;
401 }
402
403 int crypt_pbkdf_perf(const char *kdf, const char *hash,
404 const char *password, size_t password_size,
405 const char *salt, size_t salt_size,
406 size_t volume_key_size, uint32_t time_ms,
407 uint32_t max_memory_kb, uint32_t parallel_threads,
408 uint32_t *iterations_out, uint32_t *memory_out,
409 int (*progress)(uint32_t time_ms, void *usrptr), void *usrptr)
410 {
411 struct crypt_pbkdf_limits pbkdf_limits;
412 int r = -EINVAL;
413 uint32_t min_memory;
414
415 if (!kdf || !iterations_out || !memory_out)
416 return -EINVAL;
417
418 r = crypt_pbkdf_get_limits(kdf, &pbkdf_limits);
419 if (r < 0)
420 return r;
421
422 min_memory = pbkdf_limits.min_bench_memory;
423 if (min_memory > max_memory_kb)
424 min_memory = max_memory_kb;
425
426 *memory_out = 0;
427 *iterations_out = 0;
428
429 if (!strcmp(kdf, "pbkdf2"))
430 r = crypt_pbkdf_check(kdf, hash, password, password_size,
431 salt, salt_size, volume_key_size,
432 iterations_out, time_ms, progress, usrptr);
433
434 else if (!strncmp(kdf, "argon2", 6))
435 r = crypt_argon2_check(kdf, password, password_size,
436 salt, salt_size, volume_key_size,
437 pbkdf_limits.min_iterations,
438 min_memory,
439 max_memory_kb,
440 parallel_threads, time_ms, iterations_out,
441 memory_out, progress, usrptr);
442 return r;
443 }