1 /* $OpenBSD: bcrypt.c,v 1.47 2014/12/30 10:27:24 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 <pwd.h> 38 #include <stdio.h> 39 #include <stdlib.h> 40 #include <string.h> 41 42 /* This implementation is adaptable to current computing power. 43 * You can have up to 2^31 rounds which should be enough for some 44 * time to come. 45 */ 46 47 #define BCRYPT_VERSION '2' 48 #define BCRYPT_MAXSALT 16 /* Precomputation is just so nice */ 49 #define BCRYPT_BLOCKS 6 /* Ciphertext blocks */ 50 #define BCRYPT_MINLOGROUNDS 4 /* we have log2(rounds) in salt */ 51 52 #define BCRYPT_SALTSPACE (7 + (BCRYPT_MAXSALT * 4 + 2) / 3 + 1) 53 #define BCRYPT_HASHSPACE 61 54 55 char *bcrypt_gensalt(u_int8_t); 56 57 static int encode_base64(char *, const u_int8_t *, size_t); 58 static int decode_base64(u_int8_t *, size_t, const char *); 59 60 /* 61 * Generates a salt for this version of crypt. 62 */ 63 static int 64 bcrypt_initsalt(int log_rounds, uint8_t *salt, size_t saltbuflen) 65 { 66 uint8_t csalt[BCRYPT_MAXSALT]; 67 68 if (saltbuflen < BCRYPT_SALTSPACE) 69 return -1; 70 71 arc4random_buf(csalt, sizeof(csalt)); 72 73 if (log_rounds < 4) 74 log_rounds = 4; 75 else if (log_rounds > 31) 76 log_rounds = 31; 77 78 snprintf(salt, saltbuflen, "$2b$%2.2u$", log_rounds); 79 encode_base64(salt + 7, csalt, sizeof(csalt)); 80 81 return 0; 82 } 83 84 /* 85 * the core bcrypt function 86 */ 87 static int 88 bcrypt_hashpass(const char *key, const char *salt, char *encrypted, 89 size_t encryptedlen) 90 { 91 blf_ctx state; 92 u_int32_t rounds, i, k; 93 u_int16_t j; 94 size_t key_len; 95 u_int8_t salt_len, logr, minor; 96 u_int8_t ciphertext[4 * BCRYPT_BLOCKS] = "OrpheanBeholderScryDoubt"; 97 u_int8_t csalt[BCRYPT_MAXSALT]; 98 u_int32_t cdata[BCRYPT_BLOCKS]; 99 100 if (encryptedlen < BCRYPT_HASHSPACE) 101 return -1; 102 103 /* Check and discard "$" identifier */ 104 if (salt[0] != '$') 105 return -1; 106 salt += 1; 107 108 if (salt[0] != BCRYPT_VERSION) 109 return -1; 110 111 /* Check for minor versions */ 112 switch ((minor = salt[1])) { 113 case 'a': 114 key_len = (u_int8_t)(strlen(key) + 1); 115 break; 116 case 'b': 117 /* strlen() returns a size_t, but the function calls 118 * below result in implicit casts to a narrower integer 119 * type, so cap key_len at the actual maximum supported 120 * length here to avoid integer wraparound */ 121 key_len = strlen(key); 122 if (key_len > 72) 123 key_len = 72; 124 key_len++; /* include the NUL */ 125 break; 126 default: 127 return -1; 128 } 129 if (salt[2] != '$') 130 return -1; 131 /* Discard version + "$" identifier */ 132 salt += 3; 133 134 /* Check and parse num rounds */ 135 if (!isdigit((unsigned char)salt[0]) || 136 !isdigit((unsigned char)salt[1]) || salt[2] != '$') 137 return -1; 138 logr = atoi(salt); 139 if (logr < BCRYPT_MINLOGROUNDS || logr > 31) 140 return -1; 141 /* Computer power doesn't increase linearly, 2^x should be fine */ 142 rounds = 1U << logr; 143 144 /* Discard num rounds + "$" identifier */ 145 salt += 3; 146 147 if (strlen(salt) * 3 / 4 < BCRYPT_MAXSALT) 148 return -1; 149 150 /* We dont want the base64 salt but the raw data */ 151 if (decode_base64(csalt, BCRYPT_MAXSALT, salt)) 152 return -1; 153 salt_len = BCRYPT_MAXSALT; 154 155 /* Setting up S-Boxes and Subkeys */ 156 Blowfish_initstate(&state); 157 Blowfish_expandstate(&state, csalt, salt_len, 158 (u_int8_t *) key, key_len); 159 for (k = 0; k < rounds; k++) { 160 Blowfish_expand0state(&state, (u_int8_t *) key, key_len); 161 Blowfish_expand0state(&state, csalt, salt_len); 162 } 163 164 /* This can be precomputed later */ 165 j = 0; 166 for (i = 0; i < BCRYPT_BLOCKS; i++) 167 cdata[i] = Blowfish_stream2word(ciphertext, 4 * BCRYPT_BLOCKS, &j); 168 169 /* Now do the encryption */ 170 for (k = 0; k < 64; k++) 171 blf_enc(&state, cdata, BCRYPT_BLOCKS / 2); 172 173 for (i = 0; i < BCRYPT_BLOCKS; i++) { 174 ciphertext[4 * i + 3] = cdata[i] & 0xff; 175 cdata[i] = cdata[i] >> 8; 176 ciphertext[4 * i + 2] = cdata[i] & 0xff; 177 cdata[i] = cdata[i] >> 8; 178 ciphertext[4 * i + 1] = cdata[i] & 0xff; 179 cdata[i] = cdata[i] >> 8; 180 ciphertext[4 * i + 0] = cdata[i] & 0xff; 181 } 182 183 184 snprintf(encrypted, 8, "$2%c$%2.2u$", minor, logr); 185 encode_base64(encrypted + 7, csalt, BCRYPT_MAXSALT); 186 encode_base64(encrypted + 7 + 22, ciphertext, 4 * BCRYPT_BLOCKS - 1); 187 explicit_bzero(&state, sizeof(state)); 188 explicit_bzero(ciphertext, sizeof(ciphertext)); 189 explicit_bzero(csalt, sizeof(csalt)); 190 explicit_bzero(cdata, sizeof(cdata)); 191 return 0; 192 } 193 194 /* 195 * user friendly functions 196 */ 197 int 198 bcrypt_newhash(const char *pass, int log_rounds, char *hash, size_t hashlen) 199 { 200 char salt[BCRYPT_SALTSPACE]; 201 202 if (bcrypt_initsalt(log_rounds, salt, sizeof(salt)) != 0) 203 return -1; 204 205 if (bcrypt_hashpass(pass, salt, hash, hashlen) != 0) 206 return -1; 207 208 explicit_bzero(salt, sizeof(salt)); 209 return 0; 210 } 211 212 int 213 bcrypt_checkpass(const char *pass, const char *goodhash) 214 { 215 char hash[BCRYPT_HASHSPACE]; 216 217 if (bcrypt_hashpass(pass, goodhash, hash, sizeof(hash)) != 0) 218 return -1; 219 if (strlen(hash) != strlen(goodhash) || 220 timingsafe_bcmp(hash, goodhash, strlen(goodhash)) != 0) 221 return -1; 222 223 explicit_bzero(hash, sizeof(hash)); 224 return 0; 225 } 226 227 /* 228 * Measure this system's performance by measuring the time for 8 rounds. 229 * We are aiming for something that takes between 0.25 and 0.5 seconds. 230 */ 231 int 232 bcrypt_autorounds(void) 233 { 234 clock_t before, after; 235 int r = 8; 236 char buf[_PASSWORD_LEN]; 237 int duration; 238 239 before = clock(); 240 bcrypt_newhash("testpassword", r, buf, sizeof(buf)); 241 after = clock(); 242 243 duration = after - before; 244 245 /* too quick? slow it down. */ 246 while (r < 16 && duration <= CLOCKS_PER_SEC / 4) { 247 r += 1; 248 duration *= 2; 249 } 250 /* too slow? speed it up. */ 251 while (r > 4 && duration > CLOCKS_PER_SEC / 2) { 252 r -= 1; 253 duration /= 2; 254 } 255 256 return r; 257 } 258 259 /* 260 * internal utilities 261 */ 262 static const u_int8_t Base64Code[] = 263 "./ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"; 264 265 static const u_int8_t index_64[128] = { 266 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 267 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 268 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 269 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 270 255, 255, 255, 255, 255, 255, 0, 1, 54, 55, 271 56, 57, 58, 59, 60, 61, 62, 63, 255, 255, 272 255, 255, 255, 255, 255, 2, 3, 4, 5, 6, 273 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 274 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 275 255, 255, 255, 255, 255, 255, 28, 29, 30, 276 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 277 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 278 51, 52, 53, 255, 255, 255, 255, 255 279 }; 280 #define CHAR64(c) ( (c) > 127 ? 255 : index_64[(c)]) 281 282 /* 283 * read buflen (after decoding) bytes of data from b64data 284 */ 285 static int 286 decode_base64(u_int8_t *buffer, size_t len, const char *b64data) 287 { 288 u_int8_t *bp = buffer; 289 const u_int8_t *p = b64data; 290 u_int8_t c1, c2, c3, c4; 291 292 while (bp < buffer + len) { 293 c1 = CHAR64(*p); 294 /* Invalid data */ 295 if (c1 == 255) 296 return -1; 297 298 c2 = CHAR64(*(p + 1)); 299 if (c2 == 255) 300 return -1; 301 302 *bp++ = (c1 << 2) | ((c2 & 0x30) >> 4); 303 if (bp >= buffer + len) 304 break; 305 306 c3 = CHAR64(*(p + 2)); 307 if (c3 == 255) 308 return -1; 309 310 *bp++ = ((c2 & 0x0f) << 4) | ((c3 & 0x3c) >> 2); 311 if (bp >= buffer + len) 312 break; 313 314 c4 = CHAR64(*(p + 3)); 315 if (c4 == 255) 316 return -1; 317 *bp++ = ((c3 & 0x03) << 6) | c4; 318 319 p += 4; 320 } 321 return 0; 322 } 323 324 /* 325 * Turn len bytes of data into base64 encoded data. 326 * This works without = padding. 327 */ 328 static int 329 encode_base64(char *b64buffer, const u_int8_t *data, size_t len) 330 { 331 u_int8_t *bp = b64buffer; 332 const u_int8_t *p = data; 333 u_int8_t c1, c2; 334 335 while (p < data + len) { 336 c1 = *p++; 337 *bp++ = Base64Code[(c1 >> 2)]; 338 c1 = (c1 & 0x03) << 4; 339 if (p >= data + len) { 340 *bp++ = Base64Code[c1]; 341 break; 342 } 343 c2 = *p++; 344 c1 |= (c2 >> 4) & 0x0f; 345 *bp++ = Base64Code[c1]; 346 c1 = (c2 & 0x0f) << 2; 347 if (p >= data + len) { 348 *bp++ = Base64Code[c1]; 349 break; 350 } 351 c2 = *p++; 352 c1 |= (c2 >> 6) & 0x03; 353 *bp++ = Base64Code[c1]; 354 *bp++ = Base64Code[c2 & 0x3f]; 355 } 356 *bp = '\0'; 357 return 0; 358 } 359 360 /* 361 * classic interface 362 */ 363 char * 364 bcrypt_gensalt(u_int8_t log_rounds) 365 { 366 static char gsalt[BCRYPT_SALTSPACE]; 367 368 bcrypt_initsalt(log_rounds, gsalt, sizeof(gsalt)); 369 370 return gsalt; 371 } 372 373 char * 374 bcrypt(const char *pass, const char *salt) 375 { 376 static char gencrypted[BCRYPT_HASHSPACE]; 377 static char gerror[2]; 378 379 /* How do I handle errors ? Return ':' */ 380 strlcpy(gerror, ":", sizeof(gerror)); 381 if (bcrypt_hashpass(pass, salt, gencrypted, sizeof(gencrypted)) != 0) 382 return gerror; 383 384 return gencrypted; 385 } 386