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