lib/luks1/pbkdf.c

   1 /*
   2  * Implementation of Password-Based Cryptography as per PKCS#5
   3  * Copyright (C) 2002,2003 Simon Josefsson
   4  * Copyright (C) 2004 Free Software Foundation
   5  *
   6  * LUKS code
   7  * Copyright (C) 2004, Clemens Fruhwirth <clemens@endorphin.org>
   8  * Copyright (C) 2009-2012, Red Hat, Inc. All rights reserved.
   9  *
  10  * This file is free software; you can redistribute it and/or
  11  * modify it under the terms of the GNU Lesser General Public
  12  * License as published by the Free Software Foundation; either
  13  * version 2.1 of the License, or (at your option) any later version.
  14  *
  15  * This file is distributed in the hope that it will be useful,
  16  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  18  * Lesser General Public License for more details.
  19  *
  20  * You should have received a copy of the GNU Lesser General Public
  21  * License along with this file; if not, write to the Free Software
  22  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  23  *
  24  */
  25
  26 #include <netinet/in.h>
  27 #include <errno.h>
  28 #include <signal.h>
  29 #include <alloca.h>
  30 #include <string.h>
  31 #include <sys/time.h>
  32 #include "crypto_backend.h"
  33 #include "pbkdf.h"
  34
  35 static volatile uint64_t __PBKDF2_global_j = 0;
  36 static volatile uint64_t __PBKDF2_performance = 0;
  37
  38 /*
  39  * 5.2 PBKDF2
  40  *
  41  *  PBKDF2 applies a pseudorandom function (see Appendix B.1 for an
  42  *  example) to derive keys. The length of the derived key is essentially
  43  *  unbounded. (However, the maximum effective search space for the
  44  *  derived key may be limited by the structure of the underlying
  45  *  pseudorandom function. See Appendix B.1 for further discussion.)
  46  *  PBKDF2 is recommended for new applications.
  47  *
  48  *  PBKDF2 (P, S, c, dkLen)
  49  *
  50  *  Options:        PRF        underlying pseudorandom function (hLen
  51  *                             denotes the length in octets of the
  52  *                             pseudorandom function output)
  53  *
  54  *  Input:          P          password, an octet string (ASCII or UTF-8)
  55  *                  S          salt, an octet string
  56  *                  c          iteration count, a positive integer
  57  *                  dkLen      intended length in octets of the derived
  58  *                             key, a positive integer, at most
  59  *                             (2^32 - 1) * hLen
  60  *
  61  *  Output:         DK         derived key, a dkLen-octet string
  62  */
  63
  64 #define MAX_PRF_BLOCK_LEN 80
  65
  66 static int pkcs5_pbkdf2(const char *hash,
  67                         const char *P, size_t Plen,
  68                         const char *S, size_t Slen,
  69                         unsigned int c, unsigned int dkLen,
  70                         char *DK, int perfcheck)
  71 {
  72         struct crypt_hmac *hmac;
  73         char U[MAX_PRF_BLOCK_LEN];
  74         char T[MAX_PRF_BLOCK_LEN];
  75         int i, k, rc = -EINVAL;
  76         unsigned int u, hLen, l, r;
  77         size_t tmplen = Slen + 4;
  78         char *tmp;
  79
  80         tmp = alloca(tmplen);
  81         if (tmp == NULL)
  82                 return -ENOMEM;
  83
  84         hLen = crypt_hmac_size(hash);
  85         if (hLen == 0 || hLen > MAX_PRF_BLOCK_LEN)
  86                 return -EINVAL;
  87
  88         if (c == 0)
  89                 return -EINVAL;
  90
  91         if (dkLen == 0)
  92                 return -EINVAL;
  93
  94         /*
  95          *
  96          *  Steps:
  97          *
  98          *     1. If dkLen > (2^32 - 1) * hLen, output "derived key too long" and
  99          *        stop.
 100          */
 101
 102         if (dkLen > 4294967295U)
 103                 return -EINVAL;
 104
 105         /*
 106          *     2. Let l be the number of hLen-octet blocks in the derived key,
 107          *        rounding up, and let r be the number of octets in the last
 108          *        block:
 109          *
 110          *                  l = CEIL (dkLen / hLen) ,
 111          *                  r = dkLen - (l - 1) * hLen .
 112          *
 113          *        Here, CEIL (x) is the "ceiling" function, i.e. the smallest
 114          *        integer greater than, or equal to, x.
 115          */
 116
 117         l = dkLen / hLen;
 118         if (dkLen % hLen)
 119                 l++;
 120         r = dkLen - (l - 1) * hLen;
 121
 122         /*
 123          *     3. For each block of the derived key apply the function F defined
 124          *        below to the password P, the salt S, the iteration count c, and
 125          *        the block index to compute the block:
 126          *
 127          *                  T_1 = F (P, S, c, 1) ,
 128          *                  T_2 = F (P, S, c, 2) ,
 129          *                  ...
 130          *                  T_l = F (P, S, c, l) ,
 131          *
 132          *        where the function F is defined as the exclusive-or sum of the
 133          *        first c iterates of the underlying pseudorandom function PRF
 134          *        applied to the password P and the concatenation of the salt S
 135          *        and the block index i:
 136          *
 137          *                  F (P, S, c, i) = U_1 \xor U_2 \xor ... \xor U_c
 138          *
 139          *        where
 140          *
 141          *                  U_1 = PRF (P, S || INT (i)) ,
 142          *                  U_2 = PRF (P, U_1) ,
 143          *                  ...
 144          *                  U_c = PRF (P, U_{c-1}) .
 145          *
 146          *        Here, INT (i) is a four-octet encoding of the integer i, most
 147          *        significant octet first.
 148          *
 149          *     4. Concatenate the blocks and extract the first dkLen octets to
 150          *        produce a derived key DK:
 151          *
 152          *                  DK = T_1 || T_2 ||  ...  || T_l<0..r-1>
 153          *
 154          *     5. Output the derived key DK.
 155          *
 156          *  Note. The construction of the function F follows a "belt-and-
 157          *  suspenders" approach. The iterates U_i are computed recursively to
 158          *  remove a degree of parallelism from an opponent; they are exclusive-
 159          *  ored together to reduce concerns about the recursion degenerating
 160          *  into a small set of values.
 161          *
 162          */
 163
 164         if (crypt_hmac_init(&hmac, hash, P, Plen))
 165                 return -EINVAL;
 166
 167         for (i = 1; (uint) i <= l; i++) {
 168                 memset(T, 0, hLen);
 169
 170                 for (u = 1; u <= c ; u++) {
 171                         if (u == 1) {
 172                                 memcpy(tmp, S, Slen);
 173                                 tmp[Slen + 0] = (i & 0xff000000) >> 24;
 174                                 tmp[Slen + 1] = (i & 0x00ff0000) >> 16;
 175                                 tmp[Slen + 2] = (i & 0x0000ff00) >> 8;
 176                                 tmp[Slen + 3] = (i & 0x000000ff) >> 0;
 177
 178                                 if (crypt_hmac_write(hmac, tmp, tmplen))
 179                                         goto out;
 180                         } else {
 181                                 if (crypt_hmac_write(hmac, U, hLen))
 182                                         goto out;
 183                         }
 184
 185                         if (crypt_hmac_final(hmac, U, hLen))
 186                                 goto out;
 187
 188                         for (k = 0; (uint) k < hLen; k++)
 189                                 T[k] ^= U[k];
 190
 191                         if (perfcheck && __PBKDF2_performance) {
 192                                 rc = 0;
 193                                 goto out;
 194                         }
 195
 196                         if (perfcheck)
 197                                 __PBKDF2_global_j++;
 198                 }
 199
 200                 memcpy(DK + (i - 1) * hLen, T, (uint) i == l ? r : hLen);
 201         }
 202         rc = 0;
 203 out:
 204         crypt_hmac_destroy(hmac);
 205         return rc;
 206 }
 207
 208 int PBKDF2_HMAC(const char *hash,
 209                 const char *password, size_t passwordLen,
 210                 const char *salt, size_t saltLen, unsigned int iterations,
 211                 char *dKey, size_t dKeyLen)
 212 {
 213         return pkcs5_pbkdf2(hash, password, passwordLen, salt, saltLen,
 214                             iterations, (unsigned int)dKeyLen, dKey, 0);
 215 }
 216
 217 int PBKDF2_HMAC_ready(const char *hash)
 218 {
 219         if (crypt_hmac_size(hash) < 20)
 220                 return -EINVAL;
 221
 222         return 1;
 223 }
 224
 225 static void sigvtalarm(int foo __attribute__((unused)))
 226 {
 227         __PBKDF2_performance = __PBKDF2_global_j;
 228 }
 229
 230 /* This code benchmarks PBKDF2 and returns iterations/second using wth specified hash */
 231 int PBKDF2_performance_check(const char *hash, uint64_t *iter)
 232 {
 233         int timer_type, r;
 234         char buf;
 235         struct itimerval it;
 236
 237         if (__PBKDF2_global_j)
 238                 return -EBUSY;
 239
 240         if (PBKDF2_HMAC_ready(hash) < 0)
 241                 return -EINVAL;
 242
 243         /* If crypto backend is not implemented in userspace,
 244          * but uses some kernel part, we must measure also time
 245          * spent in kernel. */
 246         if (crypt_backend_flags() & CRYPT_BACKEND_KERNEL) {
 247                 timer_type = ITIMER_PROF;
 248                 signal(SIGPROF,sigvtalarm);
 249         } else {
 250                 timer_type = ITIMER_VIRTUAL;
 251                 signal(SIGVTALRM,sigvtalarm);
 252         }
 253
 254         it.it_interval.tv_usec = 0;
 255         it.it_interval.tv_sec = 0;
 256         it.it_value.tv_usec = 0;
 257         it.it_value.tv_sec =  1;
 258         if (setitimer(timer_type, &it, NULL) < 0)
 259                 return -EINVAL;
 260
 261         r = pkcs5_pbkdf2(hash, "foo", 3, "bar", 3, ~(0U), 1, &buf, 1);
 262
 263         *iter = __PBKDF2_performance;
 264         __PBKDF2_global_j = 0;
 265         __PBKDF2_performance = 0;
 266         return r;
 267 }