1 /* $OpenBSD: bcrypt.c,v 1.58 2020/07/06 13:33:05 pirofti Exp $ */
2
3 /*
4 * Copyright (c) 2014 Ted Unangst <tedu@openbsd.org>
5 * Copyright (c) 1997 Niels Provos <provos@umich.edu>
6 *
7 * Permission to use, copy, modify, and distribute this software for any
8 * purpose with or without fee is hereby granted, provided that the above
9 * copyright notice and this permission notice appear in all copies.
10 *
11 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
12 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
13 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
14 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
15 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
16 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
17 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
18 */
19 /* This password hashing algorithm was designed by David Mazieres
20 * <dm@lcs.mit.edu> and works as follows:
21 *
22 * 1. state := InitState ()
23 * 2. state := ExpandKey (state, salt, password)
24 * 3. REPEAT rounds:
25 * state := ExpandKey (state, 0, password)
26 * state := ExpandKey (state, 0, salt)
27 * 4. ctext := "OrpheanBeholderScryDoubt"
28 * 5. REPEAT 64:
29 * ctext := Encrypt_ECB (state, ctext);
30 * 6. RETURN Concatenate (salt, ctext);
31 *
32 */
33
34 #include <sys/types.h>
35 #include <blf.h>
36 #include <ctype.h>
37 #include <errno.h>
38 #include <pwd.h>
39 #include <stdio.h>
40 #include <stdlib.h>
41 #include <string.h>
42 #include <time.h>
43
44 /* This implementation is adaptable to current computing power.
45 * You can have up to 2^31 rounds which should be enough for some
46 * time to come.
47 */
48
49 #define BCRYPT_VERSION '2'
50 #define BCRYPT_MAXSALT 16 /* Precomputation is just so nice */
51 #define BCRYPT_WORDS 6 /* Ciphertext words */
52 #define BCRYPT_MINLOGROUNDS 4 /* we have log2(rounds) in salt */
53
54 #define BCRYPT_SALTSPACE (7 + (BCRYPT_MAXSALT * 4 + 2) / 3 + 1)
55 #define BCRYPT_HASHSPACE 61
56
57 char *bcrypt_gensalt(u_int8_t);
58
59 static int encode_base64(char *, const u_int8_t *, size_t);
60 static int decode_base64(u_int8_t *, size_t, const char *);
61
62 /*
63 * Generates a salt for this version of crypt.
64 */
65 static int
bcrypt_initsalt(int log_rounds,uint8_t * salt,size_t saltbuflen)66 bcrypt_initsalt(int log_rounds, uint8_t *salt, size_t saltbuflen)
67 {
68 uint8_t csalt[BCRYPT_MAXSALT];
69
70 if (saltbuflen < BCRYPT_SALTSPACE) {
71 errno = EINVAL;
72 return -1;
73 }
74
75 arc4random_buf(csalt, sizeof(csalt));
76
77 if (log_rounds < 4)
78 log_rounds = 4;
79 else if (log_rounds > 31)
80 log_rounds = 31;
81
82 snprintf(salt, saltbuflen, "$2b$%2.2u$", log_rounds);
83 encode_base64(salt + 7, csalt, sizeof(csalt));
84
85 return 0;
86 }
87
88 /*
89 * the core bcrypt function
90 */
91 static int
bcrypt_hashpass(const char * key,const char * salt,char * encrypted,size_t encryptedlen)92 bcrypt_hashpass(const char *key, const char *salt, char *encrypted,
93 size_t encryptedlen)
94 {
95 blf_ctx state;
96 u_int32_t rounds, i, k;
97 u_int16_t j;
98 size_t key_len;
99 u_int8_t salt_len, logr, minor;
100 u_int8_t ciphertext[4 * BCRYPT_WORDS] = "OrpheanBeholderScryDoubt";
101 u_int8_t csalt[BCRYPT_MAXSALT];
102 u_int32_t cdata[BCRYPT_WORDS];
103
104 if (encryptedlen < BCRYPT_HASHSPACE)
105 goto inval;
106
107 /* Check and discard "$" identifier */
108 if (salt[0] != '$')
109 goto inval;
110 salt += 1;
111
112 if (salt[0] != BCRYPT_VERSION)
113 goto inval;
114
115 /* Check for minor versions */
116 switch ((minor = salt[1])) {
117 case 'a':
118 key_len = (u_int8_t)(strlen(key) + 1);
119 break;
120 case 'b':
121 /* strlen() returns a size_t, but the function calls
122 * below result in implicit casts to a narrower integer
123 * type, so cap key_len at the actual maximum supported
124 * length here to avoid integer wraparound */
125 key_len = strlen(key);
126 if (key_len > 72)
127 key_len = 72;
128 key_len++; /* include the NUL */
129 break;
130 default:
131 goto inval;
132 }
133 if (salt[2] != '$')
134 goto inval;
135 /* Discard version + "$" identifier */
136 salt += 3;
137
138 /* Check and parse num rounds */
139 if (!isdigit((unsigned char)salt[0]) ||
140 !isdigit((unsigned char)salt[1]) || salt[2] != '$')
141 goto inval;
142 logr = (salt[1] - '0') + ((salt[0] - '0') * 10);
143 if (logr < BCRYPT_MINLOGROUNDS || logr > 31)
144 goto inval;
145 /* Computer power doesn't increase linearly, 2^x should be fine */
146 rounds = 1U << logr;
147
148 /* Discard num rounds + "$" identifier */
149 salt += 3;
150
151 if (strlen(salt) * 3 / 4 < BCRYPT_MAXSALT)
152 goto inval;
153
154 /* We dont want the base64 salt but the raw data */
155 if (decode_base64(csalt, BCRYPT_MAXSALT, salt))
156 goto inval;
157 salt_len = BCRYPT_MAXSALT;
158
159 /* Setting up S-Boxes and Subkeys */
160 Blowfish_initstate(&state);
161 Blowfish_expandstate(&state, csalt, salt_len,
162 (u_int8_t *) key, key_len);
163 for (k = 0; k < rounds; k++) {
164 Blowfish_expand0state(&state, (u_int8_t *) key, key_len);
165 Blowfish_expand0state(&state, csalt, salt_len);
166 }
167
168 /* This can be precomputed later */
169 j = 0;
170 for (i = 0; i < BCRYPT_WORDS; i++)
171 cdata[i] = Blowfish_stream2word(ciphertext, 4 * BCRYPT_WORDS, &j);
172
173 /* Now do the encryption */
174 for (k = 0; k < 64; k++)
175 blf_enc(&state, cdata, BCRYPT_WORDS / 2);
176
177 for (i = 0; i < BCRYPT_WORDS; i++) {
178 ciphertext[4 * i + 3] = cdata[i] & 0xff;
179 cdata[i] = cdata[i] >> 8;
180 ciphertext[4 * i + 2] = cdata[i] & 0xff;
181 cdata[i] = cdata[i] >> 8;
182 ciphertext[4 * i + 1] = cdata[i] & 0xff;
183 cdata[i] = cdata[i] >> 8;
184 ciphertext[4 * i + 0] = cdata[i] & 0xff;
185 }
186
187
188 snprintf(encrypted, 8, "$2%c$%2.2u$", minor, logr);
189 encode_base64(encrypted + 7, csalt, BCRYPT_MAXSALT);
190 encode_base64(encrypted + 7 + 22, ciphertext, 4 * BCRYPT_WORDS - 1);
191 explicit_bzero(&state, sizeof(state));
192 explicit_bzero(ciphertext, sizeof(ciphertext));
193 explicit_bzero(csalt, sizeof(csalt));
194 explicit_bzero(cdata, sizeof(cdata));
195 return 0;
196
197 inval:
198 errno = EINVAL;
199 return -1;
200 }
201
202 /*
203 * user friendly functions
204 */
205 int
bcrypt_newhash(const char * pass,int log_rounds,char * hash,size_t hashlen)206 bcrypt_newhash(const char *pass, int log_rounds, char *hash, size_t hashlen)
207 {
208 char salt[BCRYPT_SALTSPACE];
209
210 if (bcrypt_initsalt(log_rounds, salt, sizeof(salt)) != 0)
211 return -1;
212
213 if (bcrypt_hashpass(pass, salt, hash, hashlen) != 0)
214 return -1;
215
216 explicit_bzero(salt, sizeof(salt));
217 return 0;
218 }
219 DEF_WEAK(bcrypt_newhash);
220
221 int
bcrypt_checkpass(const char * pass,const char * goodhash)222 bcrypt_checkpass(const char *pass, const char *goodhash)
223 {
224 char hash[BCRYPT_HASHSPACE];
225
226 if (bcrypt_hashpass(pass, goodhash, hash, sizeof(hash)) != 0)
227 return -1;
228 if (strlen(hash) != strlen(goodhash) ||
229 timingsafe_bcmp(hash, goodhash, strlen(goodhash)) != 0) {
230 errno = EACCES;
231 return -1;
232 }
233
234 explicit_bzero(hash, sizeof(hash));
235 return 0;
236 }
237 DEF_WEAK(bcrypt_checkpass);
238
239 /*
240 * Measure this system's performance by measuring the time for 8 rounds.
241 * We are aiming for something that takes around 0.1s, but not too much over.
242 */
243 int
_bcrypt_autorounds(void)244 _bcrypt_autorounds(void)
245 {
246 struct timespec before, after;
247 int r = 8;
248 char buf[_PASSWORD_LEN];
249 int duration;
250
251 WRAP(clock_gettime)(CLOCK_THREAD_CPUTIME_ID, &before);
252 bcrypt_newhash("testpassword", r, buf, sizeof(buf));
253 WRAP(clock_gettime)(CLOCK_THREAD_CPUTIME_ID, &after);
254
255 duration = after.tv_sec - before.tv_sec;
256 duration *= 1000000;
257 duration += (after.tv_nsec - before.tv_nsec) / 1000;
258
259 /* too quick? slow it down. */
260 while (r < 16 && duration <= 60000) {
261 r += 1;
262 duration *= 2;
263 }
264 /* too slow? speed it up. */
265 while (r > 6 && duration > 120000) {
266 r -= 1;
267 duration /= 2;
268 }
269
270 return r;
271 }
272
273 /*
274 * internal utilities
275 */
276 static const u_int8_t Base64Code[] =
277 "./ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
278
279 static const u_int8_t index_64[128] = {
280 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
281 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
282 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
283 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
284 255, 255, 255, 255, 255, 255, 0, 1, 54, 55,
285 56, 57, 58, 59, 60, 61, 62, 63, 255, 255,
286 255, 255, 255, 255, 255, 2, 3, 4, 5, 6,
287 7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
288 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27,
289 255, 255, 255, 255, 255, 255, 28, 29, 30,
290 31, 32, 33, 34, 35, 36, 37, 38, 39, 40,
291 41, 42, 43, 44, 45, 46, 47, 48, 49, 50,
292 51, 52, 53, 255, 255, 255, 255, 255
293 };
294 #define CHAR64(c) ( (c) > 127 ? 255 : index_64[(c)])
295
296 /*
297 * read buflen (after decoding) bytes of data from b64data
298 */
299 static int
decode_base64(u_int8_t * buffer,size_t len,const char * b64data)300 decode_base64(u_int8_t *buffer, size_t len, const char *b64data)
301 {
302 u_int8_t *bp = buffer;
303 const u_int8_t *p = b64data;
304 u_int8_t c1, c2, c3, c4;
305
306 while (bp < buffer + len) {
307 c1 = CHAR64(*p);
308 /* Invalid data */
309 if (c1 == 255)
310 return -1;
311
312 c2 = CHAR64(*(p + 1));
313 if (c2 == 255)
314 return -1;
315
316 *bp++ = (c1 << 2) | ((c2 & 0x30) >> 4);
317 if (bp >= buffer + len)
318 break;
319
320 c3 = CHAR64(*(p + 2));
321 if (c3 == 255)
322 return -1;
323
324 *bp++ = ((c2 & 0x0f) << 4) | ((c3 & 0x3c) >> 2);
325 if (bp >= buffer + len)
326 break;
327
328 c4 = CHAR64(*(p + 3));
329 if (c4 == 255)
330 return -1;
331 *bp++ = ((c3 & 0x03) << 6) | c4;
332
333 p += 4;
334 }
335 return 0;
336 }
337
338 /*
339 * Turn len bytes of data into base64 encoded data.
340 * This works without = padding.
341 */
342 static int
encode_base64(char * b64buffer,const u_int8_t * data,size_t len)343 encode_base64(char *b64buffer, const u_int8_t *data, size_t len)
344 {
345 u_int8_t *bp = b64buffer;
346 const u_int8_t *p = data;
347 u_int8_t c1, c2;
348
349 while (p < data + len) {
350 c1 = *p++;
351 *bp++ = Base64Code[(c1 >> 2)];
352 c1 = (c1 & 0x03) << 4;
353 if (p >= data + len) {
354 *bp++ = Base64Code[c1];
355 break;
356 }
357 c2 = *p++;
358 c1 |= (c2 >> 4) & 0x0f;
359 *bp++ = Base64Code[c1];
360 c1 = (c2 & 0x0f) << 2;
361 if (p >= data + len) {
362 *bp++ = Base64Code[c1];
363 break;
364 }
365 c2 = *p++;
366 c1 |= (c2 >> 6) & 0x03;
367 *bp++ = Base64Code[c1];
368 *bp++ = Base64Code[c2 & 0x3f];
369 }
370 *bp = '\0';
371 return 0;
372 }
373
374 /*
375 * classic interface
376 */
377 char *
bcrypt_gensalt(u_int8_t log_rounds)378 bcrypt_gensalt(u_int8_t log_rounds)
379 {
380 static char gsalt[BCRYPT_SALTSPACE];
381
382 bcrypt_initsalt(log_rounds, gsalt, sizeof(gsalt));
383
384 return gsalt;
385 }
386
387 char *
bcrypt(const char * pass,const char * salt)388 bcrypt(const char *pass, const char *salt)
389 {
390 static char gencrypted[BCRYPT_HASHSPACE];
391
392 if (bcrypt_hashpass(pass, salt, gencrypted, sizeof(gencrypted)) != 0)
393 return NULL;
394
395 return gencrypted;
396 }
397 DEF_WEAK(bcrypt);
398