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