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
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.
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.
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.
27 #include <sys/resource.h>
28 #include "crypto_backend.h"
30 #ifndef CLOCK_MONOTONIC_RAW
31 #define CLOCK_MONOTONIC_RAW CLOCK_MONOTONIC
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
41 /* These PBKDF2 limits must be never violated */
42 int crypt_pbkdf_get_limits(const char *kdf, struct crypt_pbkdf_limits *limits)
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->max_memory = 0; /* N/A */
52 limits->min_parallel = 0; /* N/A */
53 limits->max_parallel = 0; /* N/A */
55 } else if (!strcmp(kdf, "argon2i") || !strcmp(kdf, "argon2id")) {
56 limits->min_iterations = 4;
57 limits->max_iterations = UINT32_MAX;
58 limits->min_memory = 32;
59 limits->max_memory = 4*1024*1024; /* 4GiB */
60 limits->min_parallel = 1;
61 limits->max_parallel = 4;
68 static long time_ms(struct rusage *start, struct rusage *end)
70 int count_kernel_time = 0;
73 if (crypt_backend_flags() & CRYPT_BACKEND_KERNEL)
74 count_kernel_time = 1;
77 * FIXME: if there is no self usage info, count system time.
78 * This seem like getrusage() bug in some hypervisors...
80 if (!end->ru_utime.tv_sec && !start->ru_utime.tv_sec &&
81 !end->ru_utime.tv_usec && !start->ru_utime.tv_usec)
82 count_kernel_time = 1;
84 ms = (end->ru_utime.tv_sec - start->ru_utime.tv_sec) * 1000;
85 ms += (end->ru_utime.tv_usec - start->ru_utime.tv_usec) / 1000;
87 if (count_kernel_time) {
88 ms += (end->ru_stime.tv_sec - start->ru_stime.tv_sec) * 1000;
89 ms += (end->ru_stime.tv_usec - start->ru_stime.tv_usec) / 1000;
95 static long timespec_ms(struct timespec *start, struct timespec *end)
97 return (end->tv_sec - start->tv_sec) * 1000 +
98 (end->tv_nsec - start->tv_nsec) / (1000 * 1000);
101 static int measure_argon2(const char *kdf, const char *password, size_t password_length,
102 const char *salt, size_t salt_length,
103 char *key, size_t key_length,
104 uint32_t t_cost, uint32_t m_cost, uint32_t parallel,
105 size_t samples, long ms_atleast, long *out_ms)
107 long ms, ms_min = LONG_MAX;
111 for (i = 0; i < samples; i++) {
112 struct timespec tstart, tend;
115 * NOTE: We must use clock_gettime here, because Argon2 can run over
116 * multiple threads, and thus we care about real time, not CPU time!
118 if (clock_gettime(CLOCK_MONOTONIC_RAW, &tstart) < 0)
121 r = crypt_pbkdf(kdf, NULL, password, password_length, salt,
122 salt_length, key, key_length, t_cost, m_cost, parallel);
126 if (clock_gettime(CLOCK_MONOTONIC_RAW, &tend) < 0)
129 ms = timespec_ms(&tstart, &tend);
133 if (ms < ms_atleast) {
148 static int next_argon2_params(uint32_t *t_cost, uint32_t *m_cost,
149 uint32_t min_t_cost, uint32_t min_m_cost,
150 uint32_t max_m_cost, long ms, uint32_t target_ms)
152 uint32_t old_t_cost, old_m_cost, new_t_cost, new_m_cost;
155 old_t_cost = *t_cost;
156 old_m_cost = *m_cost;
158 if ((uint32_t)ms > target_ms) {
159 /* decreasing, first try to lower t_cost, then m_cost */
160 num = (uint64_t)*t_cost * (uint64_t)target_ms;
161 denom = (uint64_t)ms;
162 new_t_cost = (uint32_t)(num / denom);
163 if (new_t_cost < min_t_cost) {
164 num = (uint64_t)*t_cost * (uint64_t)*m_cost *
166 denom = (uint64_t)min_t_cost * (uint64_t)ms;
167 *t_cost = min_t_cost;
168 *m_cost = (uint32_t)(num / denom);
169 if (*m_cost < min_m_cost) {
170 *m_cost = min_m_cost;
174 *t_cost = new_t_cost;
177 /* increasing, first try to increase m_cost, then t_cost */
178 num = (uint64_t)*m_cost * (uint64_t)target_ms;
179 denom = (uint64_t)ms;
180 new_m_cost = (uint32_t)(num / denom);
181 if (new_m_cost > max_m_cost) {
182 num = (uint64_t)*t_cost * (uint64_t)*m_cost *
184 denom = (uint64_t)max_m_cost * (uint64_t)ms;
185 *t_cost = (uint32_t)(num / denom);
186 *m_cost = max_m_cost;
187 if (*t_cost <= min_t_cost) {
188 *t_cost = min_t_cost;
191 } else if (new_m_cost < min_m_cost) {
192 *m_cost = min_m_cost;
195 *m_cost = new_m_cost;
199 /* do not continue if it is the same as in the previous run */
200 if (old_t_cost == *t_cost && old_m_cost == *m_cost)
206 static int crypt_argon2_check(const char *kdf, const char *password,
207 size_t password_length, const char *salt,
208 size_t salt_length, size_t key_length,
209 uint32_t min_t_cost, uint32_t min_m_cost, uint32_t max_m_cost,
210 uint32_t parallel, uint32_t target_ms,
211 uint32_t *out_t_cost, uint32_t *out_m_cost,
212 int (*progress)(uint32_t time_ms, void *usrptr),
217 uint32_t t_cost, m_cost;
219 long ms_atleast = (long)target_ms * BENCH_PERCENT_ATLEAST / 100;
220 long ms_atmost = (long)target_ms * BENCH_PERCENT_ATMOST / 100;
222 if (key_length <= 0 || target_ms <= 0)
225 if (min_m_cost < (parallel * 8))
226 min_m_cost = parallel * 8;
228 if (max_m_cost < min_m_cost)
231 key = malloc(key_length);
238 /* 1. Find some small parameters, s. t. ms >= BENCH_MIN_MS: */
240 r = measure_argon2(kdf, password, password_length, salt, salt_length,
241 key, key_length, t_cost, m_cost, parallel,
242 BENCH_SAMPLES_FAST, BENCH_MIN_MS, &ms);
244 /* Update parameters to actual measurement */
245 *out_t_cost = t_cost;
246 *out_m_cost = m_cost;
247 if (progress && progress((uint32_t)ms, usrptr))
254 if (ms >= BENCH_MIN_MS)
257 if (m_cost == max_m_cost) {
258 if (ms < BENCH_MIN_MS_FAST)
261 uint32_t new = (t_cost * BENCH_MIN_MS) / (uint32_t)ms;
268 if (ms < BENCH_MIN_MS_FAST)
271 uint32_t new = (m_cost * BENCH_MIN_MS) / (uint32_t)ms;
277 if (m_cost > max_m_cost) {
283 * 2. Use the params obtained in (1.) to estimate the target params.
284 * 3. Then repeatedly measure the candidate params and if they fall out of
285 * the acceptance range (+-5 %), try to improve the estimate:
288 if (next_argon2_params(&t_cost, &m_cost, min_t_cost, min_m_cost,
289 max_m_cost, ms, target_ms)) {
290 /* Update parameters to final computation */
291 *out_t_cost = t_cost;
292 *out_m_cost = m_cost;
296 r = measure_argon2(kdf, password, password_length, salt, salt_length,
297 key, key_length, t_cost, m_cost, parallel,
298 BENCH_SAMPLES_SLOW, ms_atleast, &ms);
301 /* Update parameters to actual measurement */
302 *out_t_cost = t_cost;
303 *out_m_cost = m_cost;
304 if (progress && progress((uint32_t)ms, usrptr))
311 } while (ms < ms_atleast || ms > ms_atmost);
314 crypt_backend_memzero(key, key_length);
320 /* This code benchmarks PBKDF and returns iterations/second using specified hash */
321 static int crypt_pbkdf_check(const char *kdf, const char *hash,
322 const char *password, size_t password_length,
323 const char *salt, size_t salt_length,
324 size_t key_length, uint32_t *iter_secs, uint32_t target_ms,
325 int (*progress)(uint32_t time_ms, void *usrptr), void *usrptr)
328 struct rusage rstart, rend;
335 if (!kdf || !hash || key_length <= 0)
338 key = malloc(key_length);
343 iterations = 1 << 15;
345 if (getrusage(RUSAGE_SELF, &rstart) < 0) {
350 r = crypt_pbkdf(kdf, hash, password, password_length, salt,
351 salt_length, key, key_length, iterations, 0, 0);
356 if (getrusage(RUSAGE_SELF, &rend) < 0) {
361 ms = time_ms(&rstart, &rend);
363 PBKDF2_temp = (double)iterations * target_ms / ms;
364 if (PBKDF2_temp > UINT32_MAX) {
368 *iter_secs = (uint32_t)PBKDF2_temp;
371 if (progress && progress((uint32_t)ms, usrptr)) {
388 if (++step > 10 || !iterations) {
395 crypt_backend_memzero(key, key_length);
401 int crypt_pbkdf_perf(const char *kdf, const char *hash,
402 const char *password, size_t password_size,
403 const char *salt, size_t salt_size,
404 size_t volume_key_size, uint32_t time_ms,
405 uint32_t max_memory_kb, uint32_t parallel_threads,
406 uint32_t *iterations_out, uint32_t *memory_out,
407 int (*progress)(uint32_t time_ms, void *usrptr), void *usrptr)
409 struct crypt_pbkdf_limits pbkdf_limits;
412 if (!kdf || !iterations_out || !memory_out)
415 /* FIXME: whole limits propagation should be more clear here */
416 r = crypt_pbkdf_get_limits(kdf, &pbkdf_limits);
423 if (!strcmp(kdf, "pbkdf2"))
424 r = crypt_pbkdf_check(kdf, hash, password, password_size,
425 salt, salt_size, volume_key_size,
426 iterations_out, time_ms, progress, usrptr);
428 else if (!strncmp(kdf, "argon2", 6))
429 r = crypt_argon2_check(kdf, password, password_size,
430 salt, salt_size, volume_key_size,
431 pbkdf_limits.min_iterations,
432 pbkdf_limits.min_memory,
434 parallel_threads, time_ms, iterations_out,
435 memory_out, progress, usrptr);