lib/luks1/pbkdf.c

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