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