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