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