1 /* $OpenBSD: bcrypt.c,v 1.31 2014/03/22 23:02:03 tedu Exp $ */ 2 3 /* 4 * Copyright (c) 1997 Niels Provos <provos@umich.edu> 5 * 6 * Permission to use, copy, modify, and distribute this software for any 7 * purpose with or without fee is hereby granted, provided that the above 8 * copyright notice and this permission notice appear in all copies. 9 * 10 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 11 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 12 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 13 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 14 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 15 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 16 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 17 */ 18 /* This password hashing algorithm was designed by David Mazieres 19 * <dm@lcs.mit.edu> and works as follows: 20 * 21 * 1. state := InitState () 22 * 2. state := ExpandKey (state, salt, password) 23 * 3. REPEAT rounds: 24 * state := ExpandKey (state, 0, password) 25 * state := ExpandKey (state, 0, salt) 26 * 4. ctext := "OrpheanBeholderScryDoubt" 27 * 5. REPEAT 64: 28 * ctext := Encrypt_ECB (state, ctext); 29 * 6. RETURN Concatenate (salt, ctext); 30 * 31 */ 32 33 #include <stdio.h> 34 #include <stdlib.h> 35 #include <sys/types.h> 36 #include <string.h> 37 #include <pwd.h> 38 #include <blf.h> 39 40 /* This implementation is adaptable to current computing power. 41 * You can have up to 2^31 rounds which should be enough for some 42 * time to come. 43 */ 44 45 #define BCRYPT_VERSION '2' 46 #define BCRYPT_MAXSALT 16 /* Precomputation is just so nice */ 47 #define BCRYPT_BLOCKS 6 /* Ciphertext blocks */ 48 #define BCRYPT_MINLOGROUNDS 4 /* we have log2(rounds) in salt */ 49 50 char *bcrypt_gensalt(u_int8_t); 51 52 static void encode_salt(char *, u_int8_t *, u_int16_t, u_int8_t); 53 static void encode_base64(u_int8_t *, u_int8_t *, u_int16_t); 54 static void decode_base64(u_int8_t *, u_int16_t, u_int8_t *); 55 56 static char encrypted[_PASSWORD_LEN]; 57 static char gsalt[7 + (BCRYPT_MAXSALT * 4 + 2) / 3 + 1]; 58 static char error[] = ":"; 59 60 static void 61 encode_salt(char *salt, u_int8_t *csalt, u_int16_t clen, u_int8_t logr) 62 { 63 salt[0] = '$'; 64 salt[1] = BCRYPT_VERSION; 65 salt[2] = 'a'; 66 salt[3] = '$'; 67 68 snprintf(salt + 4, 4, "%2.2u$", logr); 69 70 encode_base64((u_int8_t *) salt + 7, csalt, clen); 71 } 72 /* Generates a salt for this version of crypt. 73 Since versions may change. Keeping this here 74 seems sensible. 75 */ 76 77 char * 78 bcrypt_gensalt(u_int8_t log_rounds) 79 { 80 u_int8_t csalt[BCRYPT_MAXSALT]; 81 82 arc4random_buf(csalt, sizeof(csalt)); 83 84 if (log_rounds < 4) 85 log_rounds = 4; 86 else if (log_rounds > 31) 87 log_rounds = 31; 88 89 encode_salt(gsalt, csalt, BCRYPT_MAXSALT, log_rounds); 90 return gsalt; 91 } 92 /* We handle $Vers$log2(NumRounds)$salt+passwd$ 93 i.e. $2$04$iwouldntknowwhattosayetKdJ6iFtacBqJdKe6aW7ou */ 94 95 char * 96 bcrypt(const char *key, const char *salt) 97 { 98 blf_ctx state; 99 u_int32_t rounds, i, k; 100 u_int16_t j; 101 size_t key_len; 102 u_int8_t salt_len, logr, minor; 103 u_int8_t ciphertext[4 * BCRYPT_BLOCKS] = "OrpheanBeholderScryDoubt"; 104 u_int8_t csalt[BCRYPT_MAXSALT]; 105 u_int32_t cdata[BCRYPT_BLOCKS]; 106 char arounds[3]; 107 108 /* Discard "$" identifier */ 109 salt++; 110 111 if (*salt > BCRYPT_VERSION) { 112 /* How do I handle errors ? Return ':' */ 113 return error; 114 } 115 116 /* Check for minor versions */ 117 if (salt[1] != '$') { 118 switch (salt[1]) { 119 case 'a': /* 'ab' should not yield the same as 'abab' */ 120 case 'b': /* cap input length at 72 bytes */ 121 minor = salt[1]; 122 salt++; 123 break; 124 default: 125 return error; 126 } 127 } else 128 minor = 0; 129 130 /* Discard version + "$" identifier */ 131 salt += 2; 132 133 if (salt[2] != '$') 134 /* Out of sync with passwd entry */ 135 return error; 136 137 memcpy(arounds, salt, sizeof(arounds)); 138 if (arounds[sizeof(arounds) - 1] != '$') 139 return error; 140 arounds[sizeof(arounds) - 1] = 0; 141 logr = strtonum(arounds, BCRYPT_MINLOGROUNDS, 31, NULL); 142 if (logr == 0) 143 return error; 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 return error; 152 153 /* We dont want the base64 salt but the raw data */ 154 decode_base64(csalt, BCRYPT_MAXSALT, (u_int8_t *) salt); 155 salt_len = BCRYPT_MAXSALT; 156 if (minor <= 'a') 157 key_len = (u_int8_t)(strlen(key) + (minor >= 'a' ? 1 : 0)); 158 else { 159 /* strlen() returns a size_t, but the function calls 160 * below result in implicit casts to a narrower integer 161 * type, so cap key_len at the actual maximum supported 162 * length here to avoid integer wraparound */ 163 key_len = strlen(key); 164 if (key_len > 72) 165 key_len = 72; 166 key_len++; /* include the NUL */ 167 } 168 169 /* Setting up S-Boxes and Subkeys */ 170 Blowfish_initstate(&state); 171 Blowfish_expandstate(&state, csalt, salt_len, 172 (u_int8_t *) key, key_len); 173 for (k = 0; k < rounds; k++) { 174 Blowfish_expand0state(&state, (u_int8_t *) key, key_len); 175 Blowfish_expand0state(&state, csalt, salt_len); 176 } 177 178 /* This can be precomputed later */ 179 j = 0; 180 for (i = 0; i < BCRYPT_BLOCKS; i++) 181 cdata[i] = Blowfish_stream2word(ciphertext, 4 * BCRYPT_BLOCKS, &j); 182 183 /* Now do the encryption */ 184 for (k = 0; k < 64; k++) 185 blf_enc(&state, cdata, BCRYPT_BLOCKS / 2); 186 187 for (i = 0; i < BCRYPT_BLOCKS; i++) { 188 ciphertext[4 * i + 3] = cdata[i] & 0xff; 189 cdata[i] = cdata[i] >> 8; 190 ciphertext[4 * i + 2] = cdata[i] & 0xff; 191 cdata[i] = cdata[i] >> 8; 192 ciphertext[4 * i + 1] = cdata[i] & 0xff; 193 cdata[i] = cdata[i] >> 8; 194 ciphertext[4 * i + 0] = cdata[i] & 0xff; 195 } 196 197 198 i = 0; 199 encrypted[i++] = '$'; 200 encrypted[i++] = BCRYPT_VERSION; 201 if (minor) 202 encrypted[i++] = minor; 203 encrypted[i++] = '$'; 204 205 snprintf(encrypted + i, 4, "%2.2u$", logr); 206 207 encode_base64((u_int8_t *) encrypted + i + 3, csalt, BCRYPT_MAXSALT); 208 encode_base64((u_int8_t *) encrypted + strlen(encrypted), ciphertext, 209 4 * BCRYPT_BLOCKS - 1); 210 memset(&state, 0, sizeof(state)); 211 memset(ciphertext, 0, sizeof(ciphertext)); 212 memset(csalt, 0, sizeof(csalt)); 213 memset(cdata, 0, sizeof(cdata)); 214 return encrypted; 215 } 216 217 const static u_int8_t Base64Code[] = 218 "./ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"; 219 220 const static u_int8_t index_64[128] = { 221 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 222 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 223 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 224 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 225 255, 255, 255, 255, 255, 255, 0, 1, 54, 55, 226 56, 57, 58, 59, 60, 61, 62, 63, 255, 255, 227 255, 255, 255, 255, 255, 2, 3, 4, 5, 6, 228 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 229 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 230 255, 255, 255, 255, 255, 255, 28, 29, 30, 231 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 232 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 233 51, 52, 53, 255, 255, 255, 255, 255 234 }; 235 #define CHAR64(c) ( (c) > 127 ? 255 : index_64[(c)]) 236 237 static void 238 decode_base64(u_int8_t *buffer, u_int16_t len, u_int8_t *data) 239 { 240 u_int8_t *bp = buffer; 241 u_int8_t *p = data; 242 u_int8_t c1, c2, c3, c4; 243 while (bp < buffer + len) { 244 c1 = CHAR64(*p); 245 c2 = CHAR64(*(p + 1)); 246 247 /* Invalid data */ 248 if (c1 == 255 || c2 == 255) 249 break; 250 251 *bp++ = (c1 << 2) | ((c2 & 0x30) >> 4); 252 if (bp >= buffer + len) 253 break; 254 255 c3 = CHAR64(*(p + 2)); 256 if (c3 == 255) 257 break; 258 259 *bp++ = ((c2 & 0x0f) << 4) | ((c3 & 0x3c) >> 2); 260 if (bp >= buffer + len) 261 break; 262 263 c4 = CHAR64(*(p + 3)); 264 if (c4 == 255) 265 break; 266 *bp++ = ((c3 & 0x03) << 6) | c4; 267 268 p += 4; 269 } 270 } 271 272 static void 273 encode_base64(u_int8_t *buffer, u_int8_t *data, u_int16_t len) 274 { 275 u_int8_t *bp = buffer; 276 u_int8_t *p = data; 277 u_int8_t c1, c2; 278 while (p < data + len) { 279 c1 = *p++; 280 *bp++ = Base64Code[(c1 >> 2)]; 281 c1 = (c1 & 0x03) << 4; 282 if (p >= data + len) { 283 *bp++ = Base64Code[c1]; 284 break; 285 } 286 c2 = *p++; 287 c1 |= (c2 >> 4) & 0x0f; 288 *bp++ = Base64Code[c1]; 289 c1 = (c2 & 0x0f) << 2; 290 if (p >= data + len) { 291 *bp++ = Base64Code[c1]; 292 break; 293 } 294 c2 = *p++; 295 c1 |= (c2 >> 6) & 0x03; 296 *bp++ = Base64Code[c1]; 297 *bp++ = Base64Code[c2 & 0x3f]; 298 } 299 *bp = '\0'; 300 } 301