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