"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 }