lib/crypto_backend/pbkdf_check.c

   1 /*
   2  * PBKDF performance check
   3  * Copyright (C) 2012-2023 Red Hat, Inc. All rights reserved.
   4  * Copyright (C) 2012-2023 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 }