1 /* $OpenBSD: bcrypt.c,v 1.52 2015/01/28 23:33:52 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 = atoi(salt); 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 219 int 220 bcrypt_checkpass(const char *pass, const char *goodhash) 221 { 222 char hash[BCRYPT_HASHSPACE]; 223 224 if (bcrypt_hashpass(pass, goodhash, hash, sizeof(hash)) != 0) 225 return -1; 226 if (strlen(hash) != strlen(goodhash) || 227 timingsafe_bcmp(hash, goodhash, strlen(goodhash)) != 0) { 228 errno = EACCES; 229 return -1; 230 } 231 232 explicit_bzero(hash, sizeof(hash)); 233 return 0; 234 } 235 236 /* 237 * Measure this system's performance by measuring the time for 8 rounds. 238 * We are aiming for something that takes around 0.1s, but not too much over. 239 */ 240 int 241 bcrypt_autorounds(void) 242 { 243 struct timespec before, after; 244 int r = 8; 245 char buf[_PASSWORD_LEN]; 246 int duration; 247 248 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &before); 249 bcrypt_newhash("testpassword", r, buf, sizeof(buf)); 250 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &after); 251 252 duration = after.tv_sec - before.tv_sec; 253 duration *= 1000000; 254 duration += (after.tv_nsec - before.tv_nsec) / 1000; 255 256 /* too quick? slow it down. */ 257 while (r < 16 && duration <= 60000) { 258 r += 1; 259 duration *= 2; 260 } 261 /* too slow? speed it up. */ 262 while (r > 4 && duration > 120000) { 263 r -= 1; 264 duration /= 2; 265 } 266 267 return r; 268 } 269 270 /* 271 * internal utilities 272 */ 273 static const u_int8_t Base64Code[] = 274 "./ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"; 275 276 static const u_int8_t index_64[128] = { 277 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 278 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 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, 0, 1, 54, 55, 282 56, 57, 58, 59, 60, 61, 62, 63, 255, 255, 283 255, 255, 255, 255, 255, 2, 3, 4, 5, 6, 284 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 285 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 286 255, 255, 255, 255, 255, 255, 28, 29, 30, 287 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 288 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 289 51, 52, 53, 255, 255, 255, 255, 255 290 }; 291 #define CHAR64(c) ( (c) > 127 ? 255 : index_64[(c)]) 292 293 /* 294 * read buflen (after decoding) bytes of data from b64data 295 */ 296 static int 297 decode_base64(u_int8_t *buffer, size_t len, const char *b64data) 298 { 299 u_int8_t *bp = buffer; 300 const u_int8_t *p = b64data; 301 u_int8_t c1, c2, c3, c4; 302 303 while (bp < buffer + len) { 304 c1 = CHAR64(*p); 305 /* Invalid data */ 306 if (c1 == 255) 307 return -1; 308 309 c2 = CHAR64(*(p + 1)); 310 if (c2 == 255) 311 return -1; 312 313 *bp++ = (c1 << 2) | ((c2 & 0x30) >> 4); 314 if (bp >= buffer + len) 315 break; 316 317 c3 = CHAR64(*(p + 2)); 318 if (c3 == 255) 319 return -1; 320 321 *bp++ = ((c2 & 0x0f) << 4) | ((c3 & 0x3c) >> 2); 322 if (bp >= buffer + len) 323 break; 324 325 c4 = CHAR64(*(p + 3)); 326 if (c4 == 255) 327 return -1; 328 *bp++ = ((c3 & 0x03) << 6) | c4; 329 330 p += 4; 331 } 332 return 0; 333 } 334 335 /* 336 * Turn len bytes of data into base64 encoded data. 337 * This works without = padding. 338 */ 339 static int 340 encode_base64(char *b64buffer, const u_int8_t *data, size_t len) 341 { 342 u_int8_t *bp = b64buffer; 343 const u_int8_t *p = data; 344 u_int8_t c1, c2; 345 346 while (p < data + len) { 347 c1 = *p++; 348 *bp++ = Base64Code[(c1 >> 2)]; 349 c1 = (c1 & 0x03) << 4; 350 if (p >= data + len) { 351 *bp++ = Base64Code[c1]; 352 break; 353 } 354 c2 = *p++; 355 c1 |= (c2 >> 4) & 0x0f; 356 *bp++ = Base64Code[c1]; 357 c1 = (c2 & 0x0f) << 2; 358 if (p >= data + len) { 359 *bp++ = Base64Code[c1]; 360 break; 361 } 362 c2 = *p++; 363 c1 |= (c2 >> 6) & 0x03; 364 *bp++ = Base64Code[c1]; 365 *bp++ = Base64Code[c2 & 0x3f]; 366 } 367 *bp = '\0'; 368 return 0; 369 } 370 371 /* 372 * classic interface 373 */ 374 char * 375 bcrypt_gensalt(u_int8_t log_rounds) 376 { 377 static char gsalt[BCRYPT_SALTSPACE]; 378 379 bcrypt_initsalt(log_rounds, gsalt, sizeof(gsalt)); 380 381 return gsalt; 382 } 383 384 char * 385 bcrypt(const char *pass, const char *salt) 386 { 387 static char gencrypted[BCRYPT_HASHSPACE]; 388 static char gerror[2]; 389 390 /* How do I handle errors ? Return ':' */ 391 strlcpy(gerror, ":", sizeof(gerror)); 392 if (bcrypt_hashpass(pass, salt, gencrypted, sizeof(gencrypted)) != 0) 393 return gerror; 394 395 return gencrypted; 396 } 397