xref: /illumos-gate/usr/src/lib/crypt_modules/bsdbf/bcrypt.c (revision 00d0b46c9fa449579f084579de169b055d3ef18c)
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
decode_base64(uint8_t * buffer,uint16_t len,uint8_t * data)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
encode_salt(char * salt,uint8_t * csalt,uint16_t clen,uint8_t logr)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 *
bcrypt_gensalt(uint8_t log_rounds)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   *
bcrypt(key,salt)191 bcrypt(key, salt)
192 	const char   *key;
193 	const char   *salt;
194 {
195 	blf_ctx state;
196 	uint32_t rounds, i, k;
197 	uint16_t j;
198 	size_t key_len;
199 	uint8_t salt_len, logr, minor;
200 	uint8_t ciphertext[4 * BCRYPT_BLOCKS] = "OrpheanBeholderScryDoubt";
201 	uint8_t csalt[BCRYPT_MAXSALT];
202 	uint32_t cdata[BCRYPT_BLOCKS];
203 	char arounds[3];
204 
205 	/* Discard "$" identifier */
206 	salt++;
207 
208 	if (*salt > BCRYPT_VERSION) {
209 		/* How do I handle errors ? Return ':' */
210 		return (error);
211 	}
212 
213 	/* Check for minor versions */
214 	if (salt[1] != '$') {
215 		switch (salt[1]) {
216 		    case 'a': /* 'ab' should not yield the same as 'abab' */
217 		    case 'b': /* cap input length at 72 bytes */
218 			minor = salt[1];
219 			salt++;
220 			break;
221 		    default:
222 			return (error);
223 		}
224 	} else
225 		minor = 0;
226 
227 	/* Discard version + "$" identifier */
228 	salt += 2;
229 
230 	if (salt[2] != '$')
231 		/* Out of sync with passwd entry */
232 		return (error);
233 
234 	(void) memcpy(arounds, salt, sizeof (arounds));
235 	if (arounds[sizeof (arounds) - 1] != '$')
236 		return (error);
237 	if ((logr = atoi(arounds)) < BCRYPT_MINLOGROUNDS ||
238 	    logr > BCRYPT_MAXLOGROUNDS)
239 		return (error);
240 	/* Computer power doesn't increase linear, 2^x should be fine */
241 	rounds = 1U << logr;
242 
243 	/* Discard num rounds + "$" identifier */
244 	salt += 3;
245 
246 	if (strlen(salt) * 3 / 4 < BCRYPT_MAXSALT)
247 		return (error);
248 
249 	/* We dont want the base64 salt but the raw data */
250 	decode_base64(csalt, BCRYPT_MAXSALT, (uint8_t *)salt);
251 	salt_len = BCRYPT_MAXSALT;
252 	if (minor <= 'a')
253 		key_len = (uint8_t)(strlen(key) + (minor >= 'a' ? 1 : 0));
254 	else {
255 		/*
256 		 * strlen() returns a size_t, but the function calls
257 		 * below result in implicit casts to a narrower integer
258 		 * type, so cap key_len at the actual maximum supported
259 		 * length here to avoid integer wraparound
260 		 */
261 		key_len = strlen(key);
262 		if (key_len > 72)
263 			key_len = 72;
264 		key_len++; /* include the NUL */
265 	}
266 
267 	/* Setting up S-Boxes and Subkeys */
268 	Blowfish_initstate(&state);
269 	Blowfish_expandstate(&state, csalt, salt_len,
270 	    (uint8_t *)key, key_len);
271 	for (k = 0; k < rounds; k++) {
272 		Blowfish_expand0state(&state, (uint8_t *)key, key_len);
273 		Blowfish_expand0state(&state, csalt, salt_len);
274 	}
275 
276 	/* This can be precomputed later */
277 	j = 0;
278 	for (i = 0; i < BCRYPT_BLOCKS; i++)
279 		cdata[i] = Blowfish_stream2word(ciphertext,
280 		    4 * BCRYPT_BLOCKS, &j);
281 
282 	/* Now do the encryption */
283 	for (k = 0; k < 64; k++)
284 		blf_enc(&state, cdata, BCRYPT_BLOCKS / 2);
285 
286 	for (i = 0; i < BCRYPT_BLOCKS; i++) {
287 		ciphertext[4 * i + 3] = cdata[i] & 0xff;
288 		cdata[i] = cdata[i] >> 8;
289 		ciphertext[4 * i + 2] = cdata[i] & 0xff;
290 		cdata[i] = cdata[i] >> 8;
291 		ciphertext[4 * i + 1] = cdata[i] & 0xff;
292 		cdata[i] = cdata[i] >> 8;
293 		ciphertext[4 * i + 0] = cdata[i] & 0xff;
294 	}
295 
296 
297 	i = 0;
298 	encrypted[i++] = '$';
299 	encrypted[i++] = BCRYPT_VERSION;
300 	if (minor)
301 		encrypted[i++] = minor;
302 	encrypted[i++] = '$';
303 
304 	(void) snprintf(encrypted + i, 4, "%2.2u$", logr);
305 
306 	encode_base64((uint8_t *)encrypted + i + 3, csalt, BCRYPT_MAXSALT);
307 	encode_base64((uint8_t *)encrypted + strlen(encrypted), ciphertext,
308 	    4 * BCRYPT_BLOCKS - 1);
309 	return (encrypted);
310 }
311 
312 static void
encode_base64(uint8_t * buffer,uint8_t * data,uint16_t len)313 encode_base64(uint8_t *buffer, uint8_t *data, uint16_t len)
314 {
315 	uint8_t *bp = buffer;
316 	uint8_t *p = data;
317 	uint8_t c1, c2;
318 	while (p < data + len) {
319 		c1 = *p++;
320 		*bp++ = Base64Code[(c1 >> 2)];
321 		c1 = (c1 & 0x03) << 4;
322 		if (p >= data + len) {
323 			*bp++ = Base64Code[c1];
324 			break;
325 		}
326 		c2 = *p++;
327 		c1 |= (c2 >> 4) & 0x0f;
328 		*bp++ = Base64Code[c1];
329 		c1 = (c2 & 0x0f) << 2;
330 		if (p >= data + len) {
331 			*bp++ = Base64Code[c1];
332 			break;
333 		}
334 		c2 = *p++;
335 		c1 |= (c2 >> 6) & 0x03;
336 		*bp++ = Base64Code[c1];
337 		*bp++ = Base64Code[c2 & 0x3f];
338 	}
339 	*bp = '\0';
340 }
341 #if 0
342 void
343 main()
344 {
345 	char    blubber[73];
346 	char    salt[100];
347 	char   *p;
348 	salt[0] = '$';
349 	salt[1] = BCRYPT_VERSION;
350 	salt[2] = '$';
351 
352 	snprintf(salt + 3, 4, "%2.2u$", 5);
353 
354 	printf("24 bytes of salt: ");
355 	fgets(salt + 6, 94, stdin);
356 	salt[99] = 0;
357 	printf("72 bytes of password: ");
358 	fpurge(stdin);
359 	fgets(blubber, 73, stdin);
360 	blubber[72] = 0;
361 
362 	p = crypt(blubber, salt);
363 	printf("Passwd entry: %s\n\n", p);
364 
365 	p = bcrypt_gensalt(5);
366 	printf("Generated salt: %s\n", p);
367 	p = crypt(blubber, p);
368 	printf("Passwd entry: %s\n", p);
369 }
370 #endif
371