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