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