1 /* $NetBSD: pkcs5_pbkdf2.c,v 1.16 2016/07/01 22:50:09 christos 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.16 2016/07/01 22:50:09 christos 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 "pkcs5_pbkdf2.h" 62 #include "utils.h" 63 64 static void prf_iterate(u_int8_t *, const u_int8_t *, size_t, 65 const u_int8_t *, size_t, size_t, size_t); 66 static int pkcs5_pbkdf2_time(size_t, size_t); 67 68 #define PRF_BLOCKLEN 20 69 70 static void 71 prf_iterate(u_int8_t *r, const u_int8_t *P, size_t Plen, 72 const u_int8_t *S, size_t Slen, size_t c, size_t ind) 73 { 74 int first_time = 1; 75 size_t i; 76 size_t datalen; 77 ssize_t tmplen; 78 u_int8_t *data; 79 u_int8_t tmp[128]; 80 81 data = emalloc(Slen + 4); 82 (void)memcpy(data, S, Slen); 83 be32enc(data + Slen, ind); 84 datalen = Slen + 4; 85 86 for (i=0; i < c; i++) { 87 tmplen = hmac("sha1", P, Plen, data, datalen, tmp, sizeof(tmp)); 88 89 assert(tmplen == PRF_BLOCKLEN); 90 91 if (first_time) { 92 (void)memcpy(r, tmp, PRF_BLOCKLEN); 93 first_time = 0; 94 } else 95 memxor(r, tmp, PRF_BLOCKLEN); 96 (void)memcpy(data, tmp, PRF_BLOCKLEN); 97 datalen = PRF_BLOCKLEN; 98 } 99 free(data); 100 } 101 102 /* 103 * pkcs5_pbkdf2 takes all of its lengths in bytes. 104 */ 105 106 int 107 pkcs5_pbkdf2(u_int8_t **r, size_t dkLen, const u_int8_t *P, size_t Plen, 108 const u_int8_t *S, size_t Slen, size_t c, int compat) 109 { 110 size_t i; 111 size_t l; 112 113 /* sanity */ 114 if (!r) 115 return -1; 116 if (dkLen == 0) 117 return -1; 118 if (c < 1) 119 return -1; 120 121 /* Step 2 */ 122 l = (dkLen + PRF_BLOCKLEN - 1) / PRF_BLOCKLEN; 123 124 /* allocate the output */ 125 *r = emalloc(l * PRF_BLOCKLEN); 126 127 /* Step 3 */ 128 for (i = 0; i < l; i++) 129 prf_iterate(*r + (PRF_BLOCKLEN * i), P, Plen, S, Slen, c, 130 (compat?i:i+1)); 131 132 /* Step 4 and 5 133 * by the structure of the code, we do not need to concatenate 134 * the blocks, they're already concatenated. We do not extract 135 * the first dkLen octets, since we [naturally] assume that the 136 * calling function will use only the octets that it needs and 137 * the free(3) will free all of the allocated memory. 138 */ 139 return 0; 140 } 141 142 /* 143 * We use predefined lengths for the password and salt to ensure that 144 * no analysis can be done on the output of the calibration based on 145 * those parameters. We do not do the same for dkLen because: 146 * 1. dkLen is known to the attacker if they know the iteration 147 * count, and 148 * 2. using the wrong dkLen will skew the calibration by an 149 * integral factor n = (dkLen / 160). 150 */ 151 152 #define CAL_PASSLEN 64 153 #define CAL_SALTLEN 64 154 #define CAL_TIME 30000 /* Minimum number of microseconds that 155 * are considered significant. 156 */ 157 158 /* 159 * We return the user time in microseconds that c iterations 160 * of the algorithm take. 161 */ 162 163 static int 164 pkcs5_pbkdf2_time(size_t dkLen, size_t c) 165 { 166 struct rusage start; 167 struct rusage end; 168 int ret; 169 u_int8_t *r = NULL; 170 u_int8_t P[CAL_PASSLEN]; 171 u_int8_t S[CAL_SALTLEN]; 172 173 (void)getrusage(RUSAGE_SELF, &start); 174 /* XXX compat flag at end to be removed when _OLD keygen method is */ 175 ret = pkcs5_pbkdf2(&r, dkLen, P, sizeof(P), S, sizeof(S), c, 0); 176 if (ret) 177 return ret; 178 (void)getrusage(RUSAGE_SELF, &end); 179 free(r); 180 181 return (end.ru_utime.tv_sec - start.ru_utime.tv_sec) * 1000000 182 + (end.ru_utime.tv_usec - start.ru_utime.tv_usec); 183 } 184 185 int 186 pkcs5_pbkdf2_calibrate(size_t dkLen, int microseconds) 187 { 188 size_t c; 189 int t = 0; 190 size_t ret, i; 191 192 for (i = 0; i < 5; i++) { 193 /* 194 * First we get a meaningfully long time by doubling the 195 * iteration count until it takes longer than CAL_TIME. This 196 * should take approximately 2 * CAL_TIME. 197 */ 198 for (c = 1;; c *= 2) { 199 t = pkcs5_pbkdf2_time(dkLen, c); 200 if (t > CAL_TIME) 201 break; 202 } 203 204 /* Now that we know that, we scale it. */ 205 ret = (size_t) ((u_int64_t) c * microseconds / t); 206 207 /* 208 * Since it is quite important to not get this wrong, 209 * we test the result. 210 */ 211 212 t = pkcs5_pbkdf2_time(dkLen, ret); 213 214 /* if we are over 5% off, return an error */ 215 if (abs(microseconds - t) > (microseconds / 20)) 216 continue; 217 return ret; 218 } 219 return -1; 220 } 221