1 /* $OpenBSD: bcrypt.c,v 1.56 2016/06/26 21:04:08 tedu Exp $ */ 2 3 /* 4 * Copyright (c) 2014 Ted Unangst <tedu@openbsd.org> 5 * Copyright (c) 1997 Niels Provos <provos@umich.edu> 6 * 7 * Permission to use, copy, modify, and distribute this software for any 8 * purpose with or without fee is hereby granted, provided that the above 9 * copyright notice and this permission notice appear in all copies. 10 * 11 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 12 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 13 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 14 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 15 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 16 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 17 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 18 */ 19 /* This password hashing algorithm was designed by David Mazieres 20 * <dm@lcs.mit.edu> and works as follows: 21 * 22 * 1. state := InitState () 23 * 2. state := ExpandKey (state, salt, password) 24 * 3. REPEAT rounds: 25 * state := ExpandKey (state, 0, password) 26 * state := ExpandKey (state, 0, salt) 27 * 4. ctext := "OrpheanBeholderScryDoubt" 28 * 5. REPEAT 64: 29 * ctext := Encrypt_ECB (state, ctext); 30 * 6. RETURN Concatenate (salt, ctext); 31 * 32 */ 33 34 #include <sys/types.h> 35 #include <blf.h> 36 #include <ctype.h> 37 #include <errno.h> 38 #include <pwd.h> 39 #include <stdio.h> 40 #include <stdlib.h> 41 #include <string.h> 42 43 /* This implementation is adaptable to current computing power. 44 * You can have up to 2^31 rounds which should be enough for some 45 * time to come. 46 */ 47 48 #define BCRYPT_VERSION '2' 49 #define BCRYPT_MAXSALT 16 /* Precomputation is just so nice */ 50 #define BCRYPT_WORDS 6 /* Ciphertext words */ 51 #define BCRYPT_MINLOGROUNDS 4 /* we have log2(rounds) in salt */ 52 53 #define BCRYPT_SALTSPACE (7 + (BCRYPT_MAXSALT * 4 + 2) / 3 + 1) 54 #define BCRYPT_HASHSPACE 61 55 56 char *bcrypt_gensalt(u_int8_t); 57 58 static int encode_base64(char *, const u_int8_t *, size_t); 59 static int decode_base64(u_int8_t *, size_t, const char *); 60 61 /* 62 * Generates a salt for this version of crypt. 63 */ 64 static int 65 bcrypt_initsalt(int log_rounds, uint8_t *salt, size_t saltbuflen) 66 { 67 uint8_t csalt[BCRYPT_MAXSALT]; 68 69 if (saltbuflen < BCRYPT_SALTSPACE) { 70 errno = EINVAL; 71 return -1; 72 } 73 74 arc4random_buf(csalt, sizeof(csalt)); 75 76 if (log_rounds < 4) 77 log_rounds = 4; 78 else if (log_rounds > 31) 79 log_rounds = 31; 80 81 snprintf(salt, saltbuflen, "$2b$%2.2u$", log_rounds); 82 encode_base64(salt + 7, csalt, sizeof(csalt)); 83 84 return 0; 85 } 86 87 /* 88 * the core bcrypt function 89 */ 90 static int 91 bcrypt_hashpass(const char *key, const char *salt, char *encrypted, 92 size_t encryptedlen) 93 { 94 blf_ctx state; 95 u_int32_t rounds, i, k; 96 u_int16_t j; 97 size_t key_len; 98 u_int8_t salt_len, logr, minor; 99 u_int8_t ciphertext[4 * BCRYPT_WORDS] = "OrpheanBeholderScryDoubt"; 100 u_int8_t csalt[BCRYPT_MAXSALT]; 101 u_int32_t cdata[BCRYPT_WORDS]; 102 103 if (encryptedlen < BCRYPT_HASHSPACE) 104 goto inval; 105 106 /* Check and discard "$" identifier */ 107 if (salt[0] != '$') 108 goto inval; 109 salt += 1; 110 111 if (salt[0] != BCRYPT_VERSION) 112 goto inval; 113 114 /* Check for minor versions */ 115 switch ((minor = salt[1])) { 116 case 'a': 117 key_len = (u_int8_t)(strlen(key) + 1); 118 break; 119 case 'b': 120 /* strlen() returns a size_t, but the function calls 121 * below result in implicit casts to a narrower integer 122 * type, so cap key_len at the actual maximum supported 123 * length here to avoid integer wraparound */ 124 key_len = strlen(key); 125 if (key_len > 72) 126 key_len = 72; 127 key_len++; /* include the NUL */ 128 break; 129 default: 130 goto inval; 131 } 132 if (salt[2] != '$') 133 goto inval; 134 /* Discard version + "$" identifier */ 135 salt += 3; 136 137 /* Check and parse num rounds */ 138 if (!isdigit((unsigned char)salt[0]) || 139 !isdigit((unsigned char)salt[1]) || salt[2] != '$') 140 goto inval; 141 logr = (salt[1] - '0') + ((salt[0] - '0') * 10); 142 if (logr < BCRYPT_MINLOGROUNDS || logr > 31) 143 goto inval; 144 /* Computer power doesn't increase linearly, 2^x should be fine */ 145 rounds = 1U << logr; 146 147 /* Discard num rounds + "$" identifier */ 148 salt += 3; 149 150 if (strlen(salt) * 3 / 4 < BCRYPT_MAXSALT) 151 goto inval; 152 153 /* We dont want the base64 salt but the raw data */ 154 if (decode_base64(csalt, BCRYPT_MAXSALT, salt)) 155 goto inval; 156 salt_len = BCRYPT_MAXSALT; 157 158 /* Setting up S-Boxes and Subkeys */ 159 Blowfish_initstate(&state); 160 Blowfish_expandstate(&state, csalt, salt_len, 161 (u_int8_t *) key, key_len); 162 for (k = 0; k < rounds; k++) { 163 Blowfish_expand0state(&state, (u_int8_t *) key, key_len); 164 Blowfish_expand0state(&state, csalt, salt_len); 165 } 166 167 /* This can be precomputed later */ 168 j = 0; 169 for (i = 0; i < BCRYPT_WORDS; i++) 170 cdata[i] = Blowfish_stream2word(ciphertext, 4 * BCRYPT_WORDS, &j); 171 172 /* Now do the encryption */ 173 for (k = 0; k < 64; k++) 174 blf_enc(&state, cdata, BCRYPT_WORDS / 2); 175 176 for (i = 0; i < BCRYPT_WORDS; i++) { 177 ciphertext[4 * i + 3] = cdata[i] & 0xff; 178 cdata[i] = cdata[i] >> 8; 179 ciphertext[4 * i + 2] = cdata[i] & 0xff; 180 cdata[i] = cdata[i] >> 8; 181 ciphertext[4 * i + 1] = cdata[i] & 0xff; 182 cdata[i] = cdata[i] >> 8; 183 ciphertext[4 * i + 0] = cdata[i] & 0xff; 184 } 185 186 187 snprintf(encrypted, 8, "$2%c$%2.2u$", minor, logr); 188 encode_base64(encrypted + 7, csalt, BCRYPT_MAXSALT); 189 encode_base64(encrypted + 7 + 22, ciphertext, 4 * BCRYPT_WORDS - 1); 190 explicit_bzero(&state, sizeof(state)); 191 explicit_bzero(ciphertext, sizeof(ciphertext)); 192 explicit_bzero(csalt, sizeof(csalt)); 193 explicit_bzero(cdata, sizeof(cdata)); 194 return 0; 195 196 inval: 197 errno = EINVAL; 198 return -1; 199 } 200 201 /* 202 * user friendly functions 203 */ 204 int 205 bcrypt_newhash(const char *pass, int log_rounds, char *hash, size_t hashlen) 206 { 207 char salt[BCRYPT_SALTSPACE]; 208 209 if (bcrypt_initsalt(log_rounds, salt, sizeof(salt)) != 0) 210 return -1; 211 212 if (bcrypt_hashpass(pass, salt, hash, hashlen) != 0) 213 return -1; 214 215 explicit_bzero(salt, sizeof(salt)); 216 return 0; 217 } 218 DEF_WEAK(bcrypt_newhash); 219 220 int 221 bcrypt_checkpass(const char *pass, const char *goodhash) 222 { 223 char hash[BCRYPT_HASHSPACE]; 224 225 if (bcrypt_hashpass(pass, goodhash, hash, sizeof(hash)) != 0) 226 return -1; 227 if (strlen(hash) != strlen(goodhash) || 228 timingsafe_bcmp(hash, goodhash, strlen(goodhash)) != 0) { 229 errno = EACCES; 230 return -1; 231 } 232 233 explicit_bzero(hash, sizeof(hash)); 234 return 0; 235 } 236 DEF_WEAK(bcrypt_checkpass); 237 238 /* 239 * Measure this system's performance by measuring the time for 8 rounds. 240 * We are aiming for something that takes around 0.1s, but not too much over. 241 */ 242 int 243 _bcrypt_autorounds(void) 244 { 245 struct timespec before, after; 246 int r = 8; 247 char buf[_PASSWORD_LEN]; 248 int duration; 249 250 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &before); 251 bcrypt_newhash("testpassword", r, buf, sizeof(buf)); 252 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &after); 253 254 duration = after.tv_sec - before.tv_sec; 255 duration *= 1000000; 256 duration += (after.tv_nsec - before.tv_nsec) / 1000; 257 258 /* too quick? slow it down. */ 259 while (r < 16 && duration <= 60000) { 260 r += 1; 261 duration *= 2; 262 } 263 /* too slow? speed it up. */ 264 while (r > 6 && duration > 120000) { 265 r -= 1; 266 duration /= 2; 267 } 268 269 return r; 270 } 271 272 /* 273 * internal utilities 274 */ 275 static const u_int8_t Base64Code[] = 276 "./ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"; 277 278 static const u_int8_t index_64[128] = { 279 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 280 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 281 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 282 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 283 255, 255, 255, 255, 255, 255, 0, 1, 54, 55, 284 56, 57, 58, 59, 60, 61, 62, 63, 255, 255, 285 255, 255, 255, 255, 255, 2, 3, 4, 5, 6, 286 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 287 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 288 255, 255, 255, 255, 255, 255, 28, 29, 30, 289 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 290 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 291 51, 52, 53, 255, 255, 255, 255, 255 292 }; 293 #define CHAR64(c) ( (c) > 127 ? 255 : index_64[(c)]) 294 295 /* 296 * read buflen (after decoding) bytes of data from b64data 297 */ 298 static int 299 decode_base64(u_int8_t *buffer, size_t len, const char *b64data) 300 { 301 u_int8_t *bp = buffer; 302 const u_int8_t *p = b64data; 303 u_int8_t c1, c2, c3, c4; 304 305 while (bp < buffer + len) { 306 c1 = CHAR64(*p); 307 /* Invalid data */ 308 if (c1 == 255) 309 return -1; 310 311 c2 = CHAR64(*(p + 1)); 312 if (c2 == 255) 313 return -1; 314 315 *bp++ = (c1 << 2) | ((c2 & 0x30) >> 4); 316 if (bp >= buffer + len) 317 break; 318 319 c3 = CHAR64(*(p + 2)); 320 if (c3 == 255) 321 return -1; 322 323 *bp++ = ((c2 & 0x0f) << 4) | ((c3 & 0x3c) >> 2); 324 if (bp >= buffer + len) 325 break; 326 327 c4 = CHAR64(*(p + 3)); 328 if (c4 == 255) 329 return -1; 330 *bp++ = ((c3 & 0x03) << 6) | c4; 331 332 p += 4; 333 } 334 return 0; 335 } 336 337 /* 338 * Turn len bytes of data into base64 encoded data. 339 * This works without = padding. 340 */ 341 static int 342 encode_base64(char *b64buffer, const u_int8_t *data, size_t len) 343 { 344 u_int8_t *bp = b64buffer; 345 const u_int8_t *p = data; 346 u_int8_t c1, c2; 347 348 while (p < data + len) { 349 c1 = *p++; 350 *bp++ = Base64Code[(c1 >> 2)]; 351 c1 = (c1 & 0x03) << 4; 352 if (p >= data + len) { 353 *bp++ = Base64Code[c1]; 354 break; 355 } 356 c2 = *p++; 357 c1 |= (c2 >> 4) & 0x0f; 358 *bp++ = Base64Code[c1]; 359 c1 = (c2 & 0x0f) << 2; 360 if (p >= data + len) { 361 *bp++ = Base64Code[c1]; 362 break; 363 } 364 c2 = *p++; 365 c1 |= (c2 >> 6) & 0x03; 366 *bp++ = Base64Code[c1]; 367 *bp++ = Base64Code[c2 & 0x3f]; 368 } 369 *bp = '\0'; 370 return 0; 371 } 372 373 /* 374 * classic interface 375 */ 376 char * 377 bcrypt_gensalt(u_int8_t log_rounds) 378 { 379 static char gsalt[BCRYPT_SALTSPACE]; 380 381 bcrypt_initsalt(log_rounds, gsalt, sizeof(gsalt)); 382 383 return gsalt; 384 } 385 386 char * 387 bcrypt(const char *pass, const char *salt) 388 { 389 static char gencrypted[BCRYPT_HASHSPACE]; 390 391 if (bcrypt_hashpass(pass, salt, gencrypted, sizeof(gencrypted)) != 0) 392 return NULL; 393 394 return gencrypted; 395 } 396 DEF_WEAK(bcrypt); 397