bcrypt.c (8391B)
1 /* $OpenBSD: bcrypt.c,v 1.45 2014/07/20 04:22:34 guenther 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 case 'y': 118 /* strlen() returns a size_t, but the function calls 119 * below result in implicit casts to a narrower integer 120 * type, so cap key_len at the actual maximum supported 121 * length here to avoid integer wraparound */ 122 key_len = strlen(key); 123 if (key_len > 72) 124 key_len = 72; 125 key_len++; /* include the NUL */ 126 break; 127 default: 128 return -1; 129 } 130 if (salt[2] != '$') 131 return -1; 132 /* Discard version + "$" identifier */ 133 salt += 3; 134 135 /* Check and parse num rounds */ 136 if (!isdigit((unsigned char)salt[0]) || 137 !isdigit((unsigned char)salt[1]) || salt[2] != '$') 138 return -1; 139 logr = atoi(salt); 140 if (logr < BCRYPT_MINLOGROUNDS || logr > 31) 141 return -1; 142 /* Computer power doesn't increase linearly, 2^x should be fine */ 143 rounds = 1U << logr; 144 145 /* Discard num rounds + "$" identifier */ 146 salt += 3; 147 148 if (strlen(salt) * 3 / 4 < BCRYPT_MAXSALT) 149 return -1; 150 151 /* We dont want the base64 salt but the raw data */ 152 if (decode_base64(csalt, BCRYPT_MAXSALT, salt)) 153 return -1; 154 salt_len = BCRYPT_MAXSALT; 155 156 /* Setting up S-Boxes and Subkeys */ 157 Blowfish_initstate(&state); 158 Blowfish_expandstate(&state, csalt, salt_len, 159 (u_int8_t *) key, key_len); 160 for (k = 0; k < rounds; k++) { 161 Blowfish_expand0state(&state, (u_int8_t *) key, key_len); 162 Blowfish_expand0state(&state, csalt, salt_len); 163 } 164 165 /* This can be precomputed later */ 166 j = 0; 167 for (i = 0; i < BCRYPT_BLOCKS; i++) 168 cdata[i] = Blowfish_stream2word(ciphertext, 4 * BCRYPT_BLOCKS, &j); 169 170 /* Now do the encryption */ 171 for (k = 0; k < 64; k++) 172 blf_enc(&state, cdata, BCRYPT_BLOCKS / 2); 173 174 for (i = 0; i < BCRYPT_BLOCKS; i++) { 175 ciphertext[4 * i + 3] = cdata[i] & 0xff; 176 cdata[i] = cdata[i] >> 8; 177 ciphertext[4 * i + 2] = cdata[i] & 0xff; 178 cdata[i] = cdata[i] >> 8; 179 ciphertext[4 * i + 1] = cdata[i] & 0xff; 180 cdata[i] = cdata[i] >> 8; 181 ciphertext[4 * i + 0] = cdata[i] & 0xff; 182 } 183 184 185 snprintf(encrypted, 8, "$2%c$%2.2u$", minor, logr); 186 encode_base64(encrypted + 7, csalt, BCRYPT_MAXSALT); 187 encode_base64(encrypted + 7 + 22, ciphertext, 4 * BCRYPT_BLOCKS - 1); 188 explicit_bzero(&state, sizeof(state)); 189 explicit_bzero(ciphertext, sizeof(ciphertext)); 190 explicit_bzero(csalt, sizeof(csalt)); 191 explicit_bzero(cdata, sizeof(cdata)); 192 return 0; 193 } 194 195 /* 196 * user friendly functions 197 */ 198 int 199 bcrypt_newhash(const char *pass, int log_rounds, char *hash, size_t hashlen) 200 { 201 char salt[BCRYPT_SALTSPACE]; 202 203 if (bcrypt_initsalt(log_rounds, salt, sizeof(salt)) != 0) 204 return -1; 205 206 if (bcrypt_hashpass(pass, salt, hash, hashlen) != 0) 207 return -1; 208 209 explicit_bzero(salt, sizeof(salt)); 210 return 0; 211 } 212 213 int 214 bcrypt_checkpass(const char *pass, const char *goodhash) 215 { 216 char hash[BCRYPT_HASHSPACE]; 217 218 if (bcrypt_hashpass(pass, goodhash, hash, sizeof(hash)) != 0) 219 return -1; 220 if (strlen(hash) != strlen(goodhash) || 221 timingsafe_bcmp(hash, goodhash, strlen(goodhash)) != 0) 222 return -1; 223 224 explicit_bzero(hash, sizeof(hash)); 225 return 0; 226 } 227 228 /* 229 * internal utilities 230 */ 231 static const u_int8_t Base64Code[] = 232 "./ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"; 233 234 static const u_int8_t index_64[128] = { 235 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 236 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 237 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 238 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 239 255, 255, 255, 255, 255, 255, 0, 1, 54, 55, 240 56, 57, 58, 59, 60, 61, 62, 63, 255, 255, 241 255, 255, 255, 255, 255, 2, 3, 4, 5, 6, 242 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 243 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 244 255, 255, 255, 255, 255, 255, 28, 29, 30, 245 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 246 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 247 51, 52, 53, 255, 255, 255, 255, 255 248 }; 249 #define CHAR64(c) ( (c) > 127 ? 255 : index_64[(c)]) 250 251 /* 252 * read buflen (after decoding) bytes of data from b64data 253 */ 254 static int 255 decode_base64(u_int8_t *buffer, size_t len, const char *b64data) 256 { 257 u_int8_t *bp = buffer; 258 const u_int8_t *p = b64data; 259 u_int8_t c1, c2, c3, c4; 260 261 while (bp < buffer + len) { 262 c1 = CHAR64(*p); 263 /* Invalid data */ 264 if (c1 == 255) 265 return -1; 266 267 c2 = CHAR64(*(p + 1)); 268 if (c2 == 255) 269 return -1; 270 271 *bp++ = (c1 << 2) | ((c2 & 0x30) >> 4); 272 if (bp >= buffer + len) 273 break; 274 275 c3 = CHAR64(*(p + 2)); 276 if (c3 == 255) 277 return -1; 278 279 *bp++ = ((c2 & 0x0f) << 4) | ((c3 & 0x3c) >> 2); 280 if (bp >= buffer + len) 281 break; 282 283 c4 = CHAR64(*(p + 3)); 284 if (c4 == 255) 285 return -1; 286 *bp++ = ((c3 & 0x03) << 6) | c4; 287 288 p += 4; 289 } 290 return 0; 291 } 292 293 /* 294 * Turn len bytes of data into base64 encoded data. 295 * This works without = padding. 296 */ 297 static int 298 encode_base64(char *b64buffer, const u_int8_t *data, size_t len) 299 { 300 u_int8_t *bp = b64buffer; 301 const u_int8_t *p = data; 302 u_int8_t c1, c2; 303 304 while (p < data + len) { 305 c1 = *p++; 306 *bp++ = Base64Code[(c1 >> 2)]; 307 c1 = (c1 & 0x03) << 4; 308 if (p >= data + len) { 309 *bp++ = Base64Code[c1]; 310 break; 311 } 312 c2 = *p++; 313 c1 |= (c2 >> 4) & 0x0f; 314 *bp++ = Base64Code[c1]; 315 c1 = (c2 & 0x0f) << 2; 316 if (p >= data + len) { 317 *bp++ = Base64Code[c1]; 318 break; 319 } 320 c2 = *p++; 321 c1 |= (c2 >> 6) & 0x03; 322 *bp++ = Base64Code[c1]; 323 *bp++ = Base64Code[c2 & 0x3f]; 324 } 325 *bp = '\0'; 326 return 0; 327 }