contrib/cryptsetup/luks/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 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 <sys/time.h>
  29 #include <string.h>
  30 #include <strings.h>
  31 #include <stdlib.h>
  32 #include <openssl/evp.h>
  33 #include <openssl/hmac.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         char U[MAX_PRF_BLOCK_LEN];
  73         char T[MAX_PRF_BLOCK_LEN];
  74         const EVP_MD *PRF;
  75         HMAC_CTX ctx;
  76         int i, k, rc = -EINVAL;
  77         unsigned int u, hLen, l, r;
  78         unsigned char *p;
  79         size_t tmplen = Slen + 4;
  80         char *tmp;
  81
  82         tmp = alloca(tmplen);
  83         if (tmp == NULL)
  84                 return -ENOMEM;
  85
  86         OpenSSL_add_all_digests();
  87         PRF = EVP_get_digestbyname(hash);
  88         if (PRF == NULL) {
  89                 printf("pkcs5_pbkdf2: invalid hash %s\n", hash);
  90                 return -EINVAL;
  91         }
  92
  93         hLen = EVP_MD_size(PRF);
  94         if (hLen == 0 || hLen > MAX_PRF_BLOCK_LEN)
  95                 return -EINVAL;
  96
  97         if (c == 0)
  98                 return -EINVAL;
  99
 100         if (dkLen == 0)
 101                 return -EINVAL;
 102
 103         /*
 104          *
 105          *  Steps:
 106          *
 107          *     1. If dkLen > (2^32 - 1) * hLen, output "derived key too long" and
 108          *        stop.
 109          */
 110
 111         if (dkLen > 4294967295U)
 112                 return -EINVAL;
 113
 114         /*
 115          *     2. Let l be the number of hLen-octet blocks in the derived key,
 116          *        rounding up, and let r be the number of octets in the last
 117          *        block:
 118          *
 119          *                  l = CEIL (dkLen / hLen) ,
 120          *                  r = dkLen - (l - 1) * hLen .
 121          *
 122          *        Here, CEIL (x) is the "ceiling" function, i.e. the smallest
 123          *        integer greater than, or equal to, x.
 124          */
 125
 126         l = dkLen / hLen;
 127         if (dkLen % hLen)
 128                 l++;
 129         r = dkLen - (l - 1) * hLen;
 130
 131         /*
 132          *     3. For each block of the derived key apply the function F defined
 133          *        below to the password P, the salt S, the iteration count c, and
 134          *        the block index to compute the block:
 135          *
 136          *                  T_1 = F (P, S, c, 1) ,
 137          *                  T_2 = F (P, S, c, 2) ,
 138          *                  ...
 139          *                  T_l = F (P, S, c, l) ,
 140          *
 141          *        where the function F is defined as the exclusive-or sum of the
 142          *        first c iterates of the underlying pseudorandom function PRF
 143          *        applied to the password P and the concatenation of the salt S
 144          *        and the block index i:
 145          *
 146          *                  F (P, S, c, i) = U_1 \xor U_2 \xor ... \xor U_c
 147          *
 148          *        where
 149          *
 150          *                  U_1 = PRF (P, S || INT (i)) ,
 151          *                  U_2 = PRF (P, U_1) ,
 152          *                  ...
 153          *                  U_c = PRF (P, U_{c-1}) .
 154          *
 155          *        Here, INT (i) is a four-octet encoding of the integer i, most
 156          *        significant octet first.
 157          *
 158          *     4. Concatenate the blocks and extract the first dkLen octets to
 159          *        produce a derived key DK:
 160          *
 161          *                  DK = T_1 || T_2 ||  ...  || T_l<0..r-1>
 162          *
 163          *     5. Output the derived key DK.
 164          *
 165          *  Note. The construction of the function F follows a "belt-and-
 166          *  suspenders" approach. The iterates U_i are computed recursively to
 167          *  remove a degree of parallelism from an opponent; they are exclusive-
 168          *  ored together to reduce concerns about the recursion degenerating
 169          *  into a small set of values.
 170          *
 171          */
 172         HMAC_CTX_init(&ctx);
 173
 174         for (i = 1; (uint) i <= l; i++) {
 175                 memset(T, 0, hLen);
 176
 177                 for (u = 1; u <= c ; u++) {
 178                         if (u == 1) {
 179                                 memcpy(tmp, S, Slen);
 180                                 tmp[Slen + 0] = (i & 0xff000000) >> 24;
 181                                 tmp[Slen + 1] = (i & 0x00ff0000) >> 16;
 182                                 tmp[Slen + 2] = (i & 0x0000ff00) >> 8;
 183                                 tmp[Slen + 3] = (i & 0x000000ff) >> 0;
 184                                 HMAC_Init_ex(&ctx, P, Plen, PRF, NULL);
 185                                 HMAC_Update(&ctx, tmp, tmplen);
 186                                 HMAC_Final(&ctx, U, NULL);
 187                         } else {
 188                                 HMAC(PRF, P, Plen, U, hLen, U, NULL);
 189                         }
 190
 191                         for (k = 0; (uint) k < hLen; k++)
 192                                 T[k] ^= U[k];
 193
 194                         if (perfcheck && __PBKDF2_performance) {
 195                                 rc = 0;
 196                                 goto out;
 197                         }
 198
 199                         if (perfcheck)
 200                                 __PBKDF2_global_j++;
 201                 }
 202
 203                 memcpy(DK + (i - 1) * hLen, T, (uint) i == l ? r : hLen);
 204         }
 205         rc = 0;
 206 out:
 207         HMAC_CTX_cleanup(&ctx);
 208         return rc;
 209 }
 210
 211 int PBKDF2_HMAC(const char *hash,
 212                 const char *password, size_t passwordLen,
 213                 const char *salt, size_t saltLen, unsigned int iterations,
 214                 char *dKey, size_t dKeyLen)
 215 {
 216         return pkcs5_pbkdf2(hash, password, passwordLen, salt, saltLen,
 217                             iterations, (unsigned int)dKeyLen, dKey, 0);
 218 }
 219
 220 int PBKDF2_HMAC_ready(const char *hash)
 221 {
 222         const EVP_MD *md;
 223
 224         OpenSSL_add_all_digests();
 225         md = EVP_get_digestbyname(hash);
 226         if (md == NULL)
 227                 return -EINVAL;
 228
 229         /* Used hash must have at least 160 bits */
 230         if (EVP_MD_size(md) < 20)
 231                 return -EINVAL;
 232
 233         return 1;
 234 }
 235
 236 static void sigvtalarm(int foo)
 237 {
 238         __PBKDF2_performance = __PBKDF2_global_j;
 239 }
 240
 241 /* This code benchmarks PBKDF2 and returns iterations/second using wth specified hash */
 242 int PBKDF2_performance_check(const char *hash, uint64_t *iter)
 243 {
 244         int r;
 245         char buf;
 246         struct itimerval it;
 247
 248         if (__PBKDF2_global_j) {
 249                 printf("foo1\n");
 250                 return -EBUSY;
 251         }
 252
 253         if (!PBKDF2_HMAC_ready(hash)) {
 254                 printf("foo2\n");
 255                 return -EINVAL;
 256         }
 257
 258         signal(SIGVTALRM,sigvtalarm);
 259         it.it_interval.tv_usec = 0;
 260         it.it_interval.tv_sec = 0;
 261         it.it_value.tv_usec = 0;
 262         it.it_value.tv_sec =  1;
 263         if (setitimer (ITIMER_VIRTUAL, &it, NULL) < 0) {
 264                 printf("foo3\n");
 265                 return -EINVAL;
 266         }
 267
 268         r = pkcs5_pbkdf2(hash, "foo", 3, "bar", 3, ~(0U), 1, &buf, 1);
 269         *iter = __PBKDF2_performance;
 270         __PBKDF2_global_j = 0;
 271         __PBKDF2_performance = 0;
 272         return r;
 273 }