1 /* $NetBSD: pkcs5_pbkdf2.c,v 1.15 2010/11/27 17:08:37 elric Exp $ */ 2 3 /*- 4 * Copyright (c) 2002, 2003 The NetBSD Foundation, Inc. 5 * All rights reserved. 6 * 7 * This code is derived from software contributed to The NetBSD Foundation 8 * by Roland C. Dowdeswell. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 13 * 1. Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution. 18 * 19 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS 20 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 21 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 22 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS 23 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 24 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 25 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 26 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 27 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 28 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 29 * POSSIBILITY OF SUCH DAMAGE. 30 */ 31 32 /* 33 * This code is an implementation of PKCS #5 PBKDF2 which is described 34 * in: 35 * 36 * ``PKCS #5 v2.0: Password-Based Cryptography Standard'', RSA Laboratories, 37 * March 25, 1999. 38 * 39 * and can be found at the following URL: 40 * 41 * http://www.rsasecurity.com/rsalabs/pkcs/pkcs-5/ 42 * 43 * It was also republished as RFC 2898. 44 */ 45 46 47 #include <sys/cdefs.h> 48 #ifndef lint 49 __RCSID("$NetBSD: pkcs5_pbkdf2.c,v 1.15 2010/11/27 17:08:37 elric Exp $"); 50 #endif 51 52 #include <sys/resource.h> 53 #include <sys/endian.h> 54 55 #include <assert.h> 56 #include <stdlib.h> 57 #include <string.h> 58 #include <err.h> 59 #include <util.h> 60 61 #include <openssl/hmac.h> 62 63 #include "pkcs5_pbkdf2.h" 64 #include "utils.h" 65 66 static void prf_iterate(u_int8_t *, const u_int8_t *, size_t, 67 const u_int8_t *, size_t, size_t, size_t); 68 static int pkcs5_pbkdf2_time(size_t, size_t); 69 70 #define PRF_BLOCKLEN 20 71 72 static void 73 prf_iterate(u_int8_t *r, const u_int8_t *P, size_t Plen, 74 const u_int8_t *S, size_t Slen, size_t c, size_t ind) 75 { 76 int first_time = 1; 77 size_t i; 78 size_t datalen; 79 unsigned int tmplen; 80 u_int8_t *data; 81 u_int8_t tmp[EVP_MAX_MD_SIZE]; 82 83 data = emalloc(Slen + 4); 84 (void)memcpy(data, S, Slen); 85 be32enc(data + Slen, ind); 86 datalen = Slen + 4; 87 88 for (i=0; i < c; i++) { 89 (void)HMAC(EVP_sha1(), P, Plen, data, datalen, tmp, &tmplen); 90 91 assert(tmplen == PRF_BLOCKLEN); 92 93 if (first_time) { 94 (void)memcpy(r, tmp, PRF_BLOCKLEN); 95 first_time = 0; 96 } else 97 memxor(r, tmp, PRF_BLOCKLEN); 98 (void)memcpy(data, tmp, PRF_BLOCKLEN); 99 datalen = PRF_BLOCKLEN; 100 } 101 free(data); 102 } 103 104 /* 105 * pkcs5_pbkdf2 takes all of its lengths in bytes. 106 */ 107 108 int 109 pkcs5_pbkdf2(u_int8_t **r, size_t dkLen, const u_int8_t *P, size_t Plen, 110 const u_int8_t *S, size_t Slen, size_t c, int compat) 111 { 112 size_t i; 113 size_t l; 114 115 /* sanity */ 116 if (!r) 117 return -1; 118 if (dkLen == 0) 119 return -1; 120 if (c < 1) 121 return -1; 122 123 /* Step 2 */ 124 l = (dkLen + PRF_BLOCKLEN - 1) / PRF_BLOCKLEN; 125 126 /* allocate the output */ 127 *r = emalloc(l * PRF_BLOCKLEN); 128 129 /* Step 3 */ 130 for (i = 0; i < l; i++) 131 prf_iterate(*r + (PRF_BLOCKLEN * i), P, Plen, S, Slen, c, 132 (compat?i:i+1)); 133 134 /* Step 4 and 5 135 * by the structure of the code, we do not need to concatenate 136 * the blocks, they're already concatenated. We do not extract 137 * the first dkLen octets, since we [naturally] assume that the 138 * calling function will use only the octets that it needs and 139 * the free(3) will free all of the allocated memory. 140 */ 141 return 0; 142 } 143 144 /* 145 * We use predefined lengths for the password and salt to ensure that 146 * no analysis can be done on the output of the calibration based on 147 * those parameters. We do not do the same for dkLen because: 148 * 1. dkLen is known to the attacker if they know the iteration 149 * count, and 150 * 2. using the wrong dkLen will skew the calibration by an 151 * integral factor n = (dkLen / 160). 152 */ 153 154 #define CAL_PASSLEN 64 155 #define CAL_SALTLEN 64 156 #define CAL_TIME 30000 /* Minimum number of microseconds that 157 * are considered significant. 158 */ 159 160 /* 161 * We return the user time in microseconds that c iterations 162 * of the algorithm take. 163 */ 164 165 static int 166 pkcs5_pbkdf2_time(size_t dkLen, size_t c) 167 { 168 struct rusage start; 169 struct rusage end; 170 int ret; 171 u_int8_t *r = NULL; 172 u_int8_t P[CAL_PASSLEN]; 173 u_int8_t S[CAL_SALTLEN]; 174 175 (void)getrusage(RUSAGE_SELF, &start); 176 /* XXX compat flag at end to be removed when _OLD keygen method is */ 177 ret = pkcs5_pbkdf2(&r, dkLen, P, sizeof(P), S, sizeof(S), c, 0); 178 if (ret) 179 return ret; 180 (void)getrusage(RUSAGE_SELF, &end); 181 free(r); 182 183 return (end.ru_utime.tv_sec - start.ru_utime.tv_sec) * 1000000 184 + (end.ru_utime.tv_usec - start.ru_utime.tv_usec); 185 } 186 187 int 188 pkcs5_pbkdf2_calibrate(size_t dkLen, int microseconds) 189 { 190 size_t c; 191 int t = 0; 192 size_t ret, i; 193 194 for (i = 0; i < 5; i++) { 195 /* 196 * First we get a meaningfully long time by doubling the 197 * iteration count until it takes longer than CAL_TIME. This 198 * should take approximately 2 * CAL_TIME. 199 */ 200 for (c = 1;; c *= 2) { 201 t = pkcs5_pbkdf2_time(dkLen, c); 202 if (t > CAL_TIME) 203 break; 204 } 205 206 /* Now that we know that, we scale it. */ 207 ret = (size_t) ((u_int64_t) c * microseconds / t); 208 209 /* 210 * Since it is quite important to not get this wrong, 211 * we test the result. 212 */ 213 214 t = pkcs5_pbkdf2_time(dkLen, ret); 215 216 /* if we are over 5% off, return an error */ 217 if (abs(microseconds - t) > (microseconds / 20)) 218 continue; 219 return ret; 220 } 221 return -1; 222 } 223