1 /* 2 * Copyright 2003 Sun Microsystems, Inc. All rights reserved. 3 * Use is subject to license terms. 4 */ 5 6 /* $OpenBSD: bcrypt.c,v 1.16 2002/02/19 19:39:36 millert Exp $ */ 7 8 /* 9 * Copyright 1997 Niels Provos <provos@physnet.uni-hamburg.de> 10 * All rights reserved. 11 * 12 * Redistribution and use in source and binary forms, with or without 13 * modification, are permitted provided that the following conditions 14 * are met: 15 * 1. Redistributions of source code must retain the above copyright 16 * notice, this list of conditions and the following disclaimer. 17 * 2. Redistributions in binary form must reproduce the above copyright 18 * notice, this list of conditions and the following disclaimer in the 19 * documentation and/or other materials provided with the distribution. 20 * 3. All advertising materials mentioning features or use of this software 21 * must display the following acknowledgement: 22 * This product includes software developed by Niels Provos. 23 * 4. The name of the author may not be used to endorse or promote products 24 * derived from this software without specific prior written permission. 25 * 26 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 27 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 28 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 29 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 30 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 31 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 32 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 33 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 34 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 35 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 36 */ 37 38 /* 39 * This password hashing algorithm was designed by David Mazieres 40 * <dm@lcs.mit.edu> and works as follows: 41 * 42 * 1. state := InitState () 43 * 2. state := ExpandKey (state, salt, password) 3. 44 * REPEAT rounds: 45 * state := ExpandKey (state, 0, salt) 46 * state := ExpandKey(state, 0, password) 47 * 4. ctext := "OrpheanBeholderScryDoubt" 48 * 5. REPEAT 64: 49 * ctext := Encrypt_ECB (state, ctext); 50 * 6. RETURN Concatenate (salt, ctext); 51 * 52 */ 53 54 #if 0 55 #include <stdio.h> 56 #endif 57 58 #include <stdio.h> 59 #include <stdlib.h> 60 #include <sys/types.h> 61 #include <string.h> 62 #include <pwd.h> 63 #include <blf.h> 64 65 extern uint32_t arc4random(); 66 67 /* 68 * This implementation is adaptable to current computing power. 69 * You can have up to 2^31 rounds which should be enough for some 70 * time to come. 71 */ 72 73 #define BCRYPT_VERSION '2' 74 #define BCRYPT_MAXSALT 16 /* Precomputation is just so nice */ 75 #define BCRYPT_BLOCKS 6 /* Ciphertext blocks */ 76 #define BCRYPT_MINLOGROUNDS 4 /* we have log2(rounds) in salt */ 77 #define BCRYPT_MAXLOGROUNDS 31 78 79 char *bcrypt_gensalt(uint8_t); 80 81 static void encode_salt(char *, uint8_t *, uint16_t, uint8_t); 82 static void encode_base64(uint8_t *, uint8_t *, uint16_t); 83 static void decode_base64(uint8_t *, uint16_t, uint8_t *); 84 85 static char encrypted[128]; /* _PASSWORD_LEN in <pwd.h> on OpenBSD */ 86 static char gsalt[BCRYPT_MAXSALT * 4 / 3 + 1]; 87 static char error[] = ":"; 88 89 static uint8_t Base64Code[] = 90 "./ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"; 91 92 static uint8_t index_64[128] = 93 { 94 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 95 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 96 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 97 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 98 255, 255, 255, 255, 255, 255, 0, 1, 54, 55, 99 56, 57, 58, 59, 60, 61, 62, 63, 255, 255, 100 255, 255, 255, 255, 255, 2, 3, 4, 5, 6, 101 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 102 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 103 255, 255, 255, 255, 255, 255, 28, 29, 30, 104 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 105 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 106 51, 52, 53, 255, 255, 255, 255, 255 107 }; 108 #define CHAR64(c) ((c) > 127 ? 255 : index_64[(c)]) 109 110 static void 111 decode_base64(uint8_t *buffer, uint16_t len, uint8_t *data) 112 { 113 uint8_t *bp = buffer; 114 uint8_t *p = data; 115 uint8_t c1, c2, c3, c4; 116 while (bp < buffer + len) { 117 c1 = CHAR64(*p); 118 c2 = CHAR64(*(p + 1)); 119 120 /* Invalid data */ 121 if (c1 == 255 || c2 == 255) 122 break; 123 124 *bp++ = (c1 << 2) | ((c2 & 0x30) >> 4); 125 if (bp >= buffer + len) 126 break; 127 128 c3 = CHAR64(*(p + 2)); 129 if (c3 == 255) 130 break; 131 132 *bp++ = ((c2 & 0x0f) << 4) | ((c3 & 0x3c) >> 2); 133 if (bp >= buffer + len) 134 break; 135 136 c4 = CHAR64(*(p + 3)); 137 if (c4 == 255) 138 break; 139 *bp++ = ((c3 & 0x03) << 6) | c4; 140 141 p += 4; 142 } 143 } 144 145 static void 146 encode_salt(char *salt, uint8_t *csalt, uint16_t clen, uint8_t logr) 147 { 148 salt[0] = '$'; 149 salt[1] = BCRYPT_VERSION; 150 salt[2] = 'a'; 151 salt[3] = '$'; 152 153 (void) snprintf(salt + 4, 4, "%2.2u$", logr); 154 155 encode_base64((uint8_t *)salt + 7, csalt, clen); 156 } 157 /* 158 * Generates a salt for this version of crypt. 159 * Since versions may change. Keeping this here 160 * seems sensible. 161 */ 162 163 char * 164 bcrypt_gensalt(uint8_t log_rounds) 165 { 166 uint8_t csalt[BCRYPT_MAXSALT]; 167 uint16_t i; 168 uint32_t seed = 0; 169 170 for (i = 0; i < BCRYPT_MAXSALT; i++) { 171 if (i % 4 == 0) 172 seed = arc4random(); 173 csalt[i] = seed & 0xff; 174 seed = seed >> 8; 175 } 176 177 if (log_rounds < BCRYPT_MINLOGROUNDS) 178 log_rounds = BCRYPT_MINLOGROUNDS; 179 else if (log_rounds > BCRYPT_MAXLOGROUNDS) 180 log_rounds = BCRYPT_MAXLOGROUNDS; 181 182 encode_salt(gsalt, csalt, BCRYPT_MAXSALT, log_rounds); 183 return (gsalt); 184 } 185 /* 186 * We handle $Vers$log2(NumRounds)$salt+passwd$ 187 * i.e. $2$04$iwouldntknowwhattosayetKdJ6iFtacBqJdKe6aW7ou 188 */ 189 190 char * 191 bcrypt(const char *key, const char *salt) 192 { 193 blf_ctx state; 194 uint32_t rounds, i, k; 195 uint16_t j; 196 size_t key_len; 197 uint8_t salt_len, logr, minor; 198 uint8_t ciphertext[4 * BCRYPT_BLOCKS] __nonstring = 199 "OrpheanBeholderScryDoubt"; 200 uint8_t csalt[BCRYPT_MAXSALT]; 201 uint32_t cdata[BCRYPT_BLOCKS]; 202 char arounds[3]; 203 204 /* Discard "$" identifier */ 205 salt++; 206 207 if (*salt > BCRYPT_VERSION) { 208 /* How do I handle errors ? Return ':' */ 209 return (error); 210 } 211 212 /* Check for minor versions */ 213 if (salt[1] != '$') { 214 switch (salt[1]) { 215 case 'a': /* 'ab' should not yield the same as 'abab' */ 216 case 'b': /* cap input length at 72 bytes */ 217 minor = salt[1]; 218 salt++; 219 break; 220 default: 221 return (error); 222 } 223 } else 224 minor = 0; 225 226 /* Discard version + "$" identifier */ 227 salt += 2; 228 229 if (salt[2] != '$') 230 /* Out of sync with passwd entry */ 231 return (error); 232 233 (void) memcpy(arounds, salt, sizeof (arounds)); 234 if (arounds[sizeof (arounds) - 1] != '$') 235 return (error); 236 if ((logr = atoi(arounds)) < BCRYPT_MINLOGROUNDS || 237 logr > BCRYPT_MAXLOGROUNDS) 238 return (error); 239 /* Computer power doesn't increase linear, 2^x should be fine */ 240 rounds = 1U << logr; 241 242 /* Discard num rounds + "$" identifier */ 243 salt += 3; 244 245 if (strlen(salt) * 3 / 4 < BCRYPT_MAXSALT) 246 return (error); 247 248 /* We dont want the base64 salt but the raw data */ 249 decode_base64(csalt, BCRYPT_MAXSALT, (uint8_t *)salt); 250 salt_len = BCRYPT_MAXSALT; 251 if (minor <= 'a') 252 key_len = (uint8_t)(strlen(key) + (minor >= 'a' ? 1 : 0)); 253 else { 254 /* 255 * strlen() returns a size_t, but the function calls 256 * below result in implicit casts to a narrower integer 257 * type, so cap key_len at the actual maximum supported 258 * length here to avoid integer wraparound 259 */ 260 key_len = strlen(key); 261 if (key_len > 72) 262 key_len = 72; 263 key_len++; /* include the NUL */ 264 } 265 266 /* Setting up S-Boxes and Subkeys */ 267 Blowfish_initstate(&state); 268 Blowfish_expandstate(&state, csalt, salt_len, 269 (uint8_t *)key, key_len); 270 for (k = 0; k < rounds; k++) { 271 Blowfish_expand0state(&state, (uint8_t *)key, key_len); 272 Blowfish_expand0state(&state, csalt, salt_len); 273 } 274 275 /* This can be precomputed later */ 276 j = 0; 277 for (i = 0; i < BCRYPT_BLOCKS; i++) 278 cdata[i] = Blowfish_stream2word(ciphertext, 279 4 * BCRYPT_BLOCKS, &j); 280 281 /* Now do the encryption */ 282 for (k = 0; k < 64; k++) 283 blf_enc(&state, cdata, BCRYPT_BLOCKS / 2); 284 285 for (i = 0; i < BCRYPT_BLOCKS; i++) { 286 ciphertext[4 * i + 3] = cdata[i] & 0xff; 287 cdata[i] = cdata[i] >> 8; 288 ciphertext[4 * i + 2] = cdata[i] & 0xff; 289 cdata[i] = cdata[i] >> 8; 290 ciphertext[4 * i + 1] = cdata[i] & 0xff; 291 cdata[i] = cdata[i] >> 8; 292 ciphertext[4 * i + 0] = cdata[i] & 0xff; 293 } 294 295 296 i = 0; 297 encrypted[i++] = '$'; 298 encrypted[i++] = BCRYPT_VERSION; 299 if (minor) 300 encrypted[i++] = minor; 301 encrypted[i++] = '$'; 302 303 (void) snprintf(encrypted + i, 4, "%2.2u$", logr); 304 305 encode_base64((uint8_t *)encrypted + i + 3, csalt, BCRYPT_MAXSALT); 306 encode_base64((uint8_t *)encrypted + strlen(encrypted), ciphertext, 307 4 * BCRYPT_BLOCKS - 1); 308 return (encrypted); 309 } 310 311 static void 312 encode_base64(uint8_t *buffer, uint8_t *data, uint16_t len) 313 { 314 uint8_t *bp = buffer; 315 uint8_t *p = data; 316 uint8_t c1, c2; 317 while (p < data + len) { 318 c1 = *p++; 319 *bp++ = Base64Code[(c1 >> 2)]; 320 c1 = (c1 & 0x03) << 4; 321 if (p >= data + len) { 322 *bp++ = Base64Code[c1]; 323 break; 324 } 325 c2 = *p++; 326 c1 |= (c2 >> 4) & 0x0f; 327 *bp++ = Base64Code[c1]; 328 c1 = (c2 & 0x0f) << 2; 329 if (p >= data + len) { 330 *bp++ = Base64Code[c1]; 331 break; 332 } 333 c2 = *p++; 334 c1 |= (c2 >> 6) & 0x03; 335 *bp++ = Base64Code[c1]; 336 *bp++ = Base64Code[c2 & 0x3f]; 337 } 338 *bp = '\0'; 339 } 340 #if 0 341 void 342 main() 343 { 344 char blubber[73]; 345 char salt[100]; 346 char *p; 347 salt[0] = '$'; 348 salt[1] = BCRYPT_VERSION; 349 salt[2] = '$'; 350 351 snprintf(salt + 3, 4, "%2.2u$", 5); 352 353 printf("24 bytes of salt: "); 354 fgets(salt + 6, 94, stdin); 355 salt[99] = 0; 356 printf("72 bytes of password: "); 357 fpurge(stdin); 358 fgets(blubber, 73, stdin); 359 blubber[72] = 0; 360 361 p = crypt(blubber, salt); 362 printf("Passwd entry: %s\n\n", p); 363 364 p = bcrypt_gensalt(5); 365 printf("Generated salt: %s\n", p); 366 p = crypt(blubber, p); 367 printf("Passwd entry: %s\n", p); 368 } 369 #endif 370