1 /*-
2 * Copyright 2013-2018 Alexander Peslyak
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted.
7 *
8 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
9 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
10 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
11 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
12 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
13 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
14 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
15 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
16 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
17 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
18 * SUCH DAMAGE.
19 */
20
21 #include "crypt-port.h"
22
23 #if INCLUDE_yescrypt || INCLUDE_scrypt || INCLUDE_gost_yescrypt
24
25 #include <stdint.h>
26 #include <string.h>
27
28 #include "alg-sha256.h"
29
30 #define YESCRYPT_INTERNAL
31 #include "alg-yescrypt.h"
32
33 #pragma GCC diagnostic ignored "-Wconversion"
34 #pragma GCC diagnostic ignored "-Wsign-conversion"
35 #pragma GCC diagnostic ignored "-Wsign-compare"
36 #pragma GCC diagnostic ignored "-Wcast-qual"
37
38 #define BYTES2CHARS(bytes) ((((bytes) * 8) + 5) / 6)
39
40 #define HASH_SIZE sizeof(yescrypt_binary_t) /* bytes */
41 #define HASH_LEN BYTES2CHARS(HASH_SIZE) /* base-64 chars */
42
43 /*
44 * "$y$", up to 8 params of up to 6 chars each, '$', salt
45 * Alternatively, but that's smaller:
46 * "$7$", 3 params encoded as 1+5+5 chars, salt
47 */
48 #define PREFIX_LEN (3 + 8 * 6 + 1 + BYTES2CHARS(32))
49
50 static const uint8_t atoi64_partial[77] = {
51 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,
52 64, 64, 64, 64, 64, 64, 64,
53 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
54 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37,
55 64, 64, 64, 64, 64, 64,
56 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50,
57 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63
58 };
59
60 static uint8_t *encode64_uint32(uint8_t *dst, size_t dstlen,
61 uint32_t src, uint32_t min)
62 {
63 uint32_t start = 0, end = 47, chars = 1, bits = 0;
64
65 if (src < min)
66 return NULL;
67 src -= min;
68
69 do {
70 uint32_t count = (end + 1 - start) << bits;
71 if (src < count)
72 break;
73 if (start >= 63)
74 return NULL;
75 start = end + 1;
76 end = start + (62 - end) / 2;
77 src -= count;
78 chars++;
79 bits += 6;
80 } while (1);
81
82 if (dstlen <= chars) /* require room for a NUL terminator */
83 return NULL;
84
85 *dst++ = itoa64[start + (src >> bits)];
86
87 while (--chars) {
88 bits -= 6;
89 *dst++ = itoa64[(src >> bits) & 0x3f];
90 }
91
92 *dst = 0; /* NUL terminate just in case */
93
94 return dst;
95 }
96
97 static inline uint32_t atoi64(uint8_t src)
98 {
99 if (src >= '.' && src <= 'z')
100 return atoi64_partial[src - '.'];
101
102 return 64;
103 }
104
105 static const uint8_t *decode64_uint32(uint32_t *dst,
106 const uint8_t *src, uint32_t min)
107 {
108 uint32_t start = 0, end = 47, chars = 1, bits = 0;
109 uint32_t c;
110
111 c = atoi64(*src++);
112 if (c > 63)
113 goto fail;
114
115 *dst = min;
116 while (c > end) {
117 *dst += (end + 1 - start) << bits;
118 start = end + 1;
119 end = start + (62 - end) / 2;
120 chars++;
121 bits += 6;
122 }
123
124 *dst += (c - start) << bits;
125
126 while (--chars) {
127 c = atoi64(*src++);
128 if (c > 63)
129 goto fail;
130 bits -= 6;
131 *dst += c << bits;
132 }
133
134 return src;
135
136 fail:
137 *dst = 0;
138 return NULL;
139 }
140
141 static uint8_t *encode64_uint32_fixed(uint8_t *dst, size_t dstlen,
142 uint32_t src, uint32_t srcbits)
143 {
144 uint32_t bits;
145
146 for (bits = 0; bits < srcbits; bits += 6) {
147 if (dstlen < 2)
148 return NULL;
149 *dst++ = itoa64[src & 0x3f];
150 dstlen--;
151 src >>= 6;
152 }
153
154 if (src || dstlen < 1)
155 return NULL;
156
157 *dst = 0; /* NUL terminate just in case */
158
159 return dst;
160 }
161
162 uint8_t *encode64(uint8_t *dst, size_t dstlen,
163 const uint8_t *src, size_t srclen)
164 {
165 size_t i;
166
167 for (i = 0; i < srclen; ) {
168 uint8_t *dnext;
169 uint32_t value = 0, bits = 0;
170 do {
171 value |= (uint32_t)src[i++] << bits;
172 bits += 8;
173 } while (bits < 24 && i < srclen);
174 dnext = encode64_uint32_fixed(dst, dstlen, value, bits);
175 if (!dnext)
176 return NULL;
177 dstlen -= dnext - dst;
178 dst = dnext;
179 }
180
181 if (dstlen < 1)
182 return NULL;
183
184 *dst = 0; /* NUL terminate just in case */
185
186 return dst;
187 }
188
189 static const uint8_t *decode64_uint32_fixed(uint32_t *dst, uint32_t dstbits,
190 const uint8_t *src)
191 {
192 uint32_t bits;
193
194 *dst = 0;
195 for (bits = 0; bits < dstbits; bits += 6) {
196 uint32_t c = atoi64(*src++);
197 if (c > 63) {
198 *dst = 0;
199 return NULL;
200 }
201 *dst |= c << bits;
202 }
203
204 return src;
205 }
206
207 const uint8_t *decode64(uint8_t *dst, size_t *dstlen,
208 const uint8_t *src, size_t srclen)
209 {
210 size_t dstpos = 0;
211
212 while (dstpos <= *dstlen && srclen) {
213 uint32_t value = 0, bits = 0;
214 while (srclen--) {
215 uint32_t c = atoi64(*src);
216 if (c > 63) {
217 srclen = 0;
218 break;
219 }
220 src++;
221 value |= c << bits;
222 bits += 6;
223 if (bits >= 24)
224 break;
225 }
226 if (!bits)
227 break;
228 if (bits < 12) /* must have at least one full byte */
229 goto fail;
230 while (dstpos++ < *dstlen) {
231 *dst++ = value;
232 value >>= 8;
233 bits -= 8;
234 if (bits < 8) { /* 2 or 4 */
235 if (value) /* must be 0 */
236 goto fail;
237 bits = 0;
238 break;
239 }
240 }
241 if (bits)
242 goto fail;
243 }
244
245 if (!srclen && dstpos <= *dstlen) {
246 *dstlen = dstpos;
247 return src;
248 }
249
250 fail:
251 *dstlen = 0;
252 return NULL;
253 }
254
255 typedef enum { ENC = 1, DEC = -1 } encrypt_dir_t;
256
257 static void memxor(unsigned char *dst, unsigned char *src, size_t size)
258 {
259 while (size--)
260 *dst++ ^= *src++;
261 }
262
263 static void yescrypt_sha256_cipher(unsigned char *data, size_t datalen,
264 const yescrypt_binary_t *key, encrypt_dir_t dir)
265 {
266 SHA256_CTX ctx;
267 unsigned char f[32 + 4];
268 size_t halflen, which;
269 unsigned char mask, round, target;
270
271 if (!datalen)
272 return;
273 if (datalen > 64)
274 datalen = 64;
275
276 halflen = datalen >> 1;
277
278 which = 0; /* offset to half we are working on (0 or halflen) */
279 mask = 0x0f; /* current half's extra nibble mask if datalen is odd */
280
281 round = 0;
282 target = 5; /* 6 rounds due to Jacques Patarin's CRYPTO 2004 paper */
283
284 if (dir == DEC) {
285 which = halflen; /* even round count, so swap the halves */
286 mask ^= 0xff;
287
288 round = target;
289 target = 0;
290 }
291
292 f[32] = 0;
293 f[33] = sizeof(*key);
294 f[34] = datalen;
295
296 do {
297 SHA256_Init(&ctx);
298 f[35] = round;
299 SHA256_Update(&ctx, &f[32], 4);
300 SHA256_Update(&ctx, key, sizeof(*key));
301 SHA256_Update(&ctx, &data[which], halflen);
302 if (datalen & 1) {
303 f[0] = data[datalen - 1] & mask;
304 SHA256_Update(&ctx, f, 1);
305 }
306 SHA256_Final(f, &ctx);
307 which ^= halflen;
308 memxor(&data[which], f, halflen);
309 if (datalen & 1) {
310 mask ^= 0xff;
311 data[datalen - 1] ^= f[halflen] & mask;
312 }
313 if (round == target)
314 break;
315 round += dir;
316 } while (1);
317
318 /* ctx is presumably zeroized by SHA256_Final() */
319 explicit_bzero(f, sizeof(f));
320 }
321
322 uint8_t *yescrypt_r(const yescrypt_shared_t *shared, yescrypt_local_t *local,
323 const uint8_t *passwd, size_t passwdlen,
324 const uint8_t *setting,
325 const yescrypt_binary_t *key,
326 uint8_t *buf, size_t buflen)
327 {
328 unsigned char saltbin[64], hashbin[32];
329 const uint8_t *src, *saltstr, *salt;
330 uint8_t *dst;
331 size_t need, prefixlen, saltstrlen, saltlen;
332 yescrypt_params_t params = { .p = 1 };
333
334 if (setting[0] != '$' ||
335 (setting[1] != '7' && setting[1] != 'y') ||
336 setting[2] != '$')
337 return NULL;
338 src = setting + 3;
339
340 if (setting[1] == '7') {
341 uint32_t N_log2 = atoi64(*src++);
342 if (N_log2 < 1 || N_log2 > 63)
343 return NULL;
344 params.N = (uint64_t)1 << N_log2;
345
346 src = decode64_uint32_fixed(¶ms.r, 30, src);
347 if (!src)
348 return NULL;
349
350 src = decode64_uint32_fixed(¶ms.p, 30, src);
351 if (!src)
352 return NULL;
353
354 if (key)
355 return NULL;
356 } else {
357 uint32_t flavor, N_log2;
358
359 src = decode64_uint32(&flavor, src, 0);
360 if (!src)
361 return NULL;
362
363 if (flavor < YESCRYPT_RW) {
364 params.flags = flavor;
365 } else if (flavor <= YESCRYPT_RW + (YESCRYPT_RW_FLAVOR_MASK >> 2)) {
366 params.flags = YESCRYPT_RW + ((flavor - YESCRYPT_RW) << 2);
367 } else {
368 return NULL;
369 }
370
371 src = decode64_uint32(&N_log2, src, 1);
372 if (!src || N_log2 > 63)
373 return NULL;
374 params.N = (uint64_t)1 << N_log2;
375
376 src = decode64_uint32(¶ms.r, src, 1);
377 if (!src)
378 return NULL;
379
380 if (*src != '$') {
381 uint32_t have;
382
383 src = decode64_uint32(&have, src, 1);
384 if (!src)
385 return NULL;
386
387 if (have & 1) {
388 src = decode64_uint32(¶ms.p, src, 2);
389 if (!src)
390 return NULL;
391 }
392
393 if (have & 2) {
394 src = decode64_uint32(¶ms.t, src, 1);
395 if (!src)
396 return NULL;
397 }
398
399 if (have & 4) {
400 src = decode64_uint32(¶ms.g, src, 1);
401 if (!src)
402 return NULL;
403 }
404
405 if (have & 8) {
406 uint32_t NROM_log2;
407 src = decode64_uint32(&NROM_log2, src, 1);
408 if (!src || NROM_log2 > 63)
409 return NULL;
410 params.NROM = (uint64_t)1 << NROM_log2;
411 }
412 }
413
414 if (*src++ != '$')
415 return NULL;
416 }
417
418 prefixlen = src - setting;
419
420 saltstr = src;
421 src = (uint8_t *)strrchr((char *)saltstr, '$');
422 if (src)
423 saltstrlen = src - saltstr;
424 else
425 saltstrlen = strlen((char *)saltstr);
426
427 if (setting[1] == '7') {
428 salt = saltstr;
429 saltlen = saltstrlen;
430 } else {
431 const uint8_t *saltend;
432
433 saltlen = sizeof(saltbin);
434 saltend = decode64(saltbin, &saltlen, saltstr, saltstrlen);
435
436 if (!saltend || (size_t)(saltend - saltstr) != saltstrlen)
437 goto fail;
438
439 salt = saltbin;
440
441 if (key)
442 yescrypt_sha256_cipher(saltbin, saltlen, key, ENC);
443 }
444
445 need = prefixlen + saltstrlen + 1 + HASH_LEN + 1;
446 if (need > buflen || need < saltstrlen)
447 goto fail;
448
449 if (yescrypt_kdf(shared, local, passwd, passwdlen, salt, saltlen,
450 ¶ms, hashbin, sizeof(hashbin)))
451 goto fail;
452
453 if (key) {
454 explicit_bzero(saltbin, sizeof(saltbin));
455 yescrypt_sha256_cipher(hashbin, sizeof(hashbin), key, ENC);
456 }
457
458 dst = buf;
459 memcpy(dst, setting, prefixlen + saltstrlen);
460 dst += prefixlen + saltstrlen;
461 *dst++ = '$';
462
463 dst = encode64(dst, buflen - (dst - buf), hashbin, sizeof(hashbin));
464 explicit_bzero(hashbin, sizeof(hashbin));
465 if (!dst || dst >= buf + buflen)
466 return NULL;
467
468 *dst = 0; /* NUL termination */
469
470 return buf;
471
472 fail:
473 explicit_bzero(saltbin, sizeof(saltbin));
474 explicit_bzero(hashbin, sizeof(hashbin));
475 return NULL;
476 }
477
478 uint8_t *yescrypt(const uint8_t *passwd, const uint8_t *setting)
479 {
480 /* prefix, '$', hash, NUL */
481 static uint8_t buf[PREFIX_LEN + 1 + HASH_LEN + 1];
482 yescrypt_local_t local;
483 uint8_t *retval;
484
485 if (yescrypt_init_local(&local))
486 return NULL;
487 retval = yescrypt_r(NULL, &local,
488 passwd, strlen((char *)passwd), setting, NULL, buf, sizeof(buf));
489 if (yescrypt_free_local(&local))
490 return NULL;
491 return retval;
492 }
493
494 uint8_t *yescrypt_reencrypt(uint8_t *hash,
495 const yescrypt_binary_t *from_key,
496 const yescrypt_binary_t *to_key)
497 {
498 uint8_t *retval = NULL, *saltstart, *hashstart;
499 const uint8_t *hashend;
500 unsigned char saltbin[64], hashbin[32];
501 size_t saltstrlen, saltlen = 0, hashlen;
502
503 if (strncmp((char *)hash, "$y$", 3))
504 return NULL;
505
506 saltstart = NULL;
507 hashstart = (uint8_t *)strrchr((char *)hash, '$');
508 if (hashstart) {
509 if (hashstart > (uint8_t *)hash) {
510 saltstart = hashstart - 1;
511 while (*saltstart != '$' && saltstart > hash)
512 saltstart--;
513 if (*saltstart == '$')
514 saltstart++;
515 }
516 hashstart++;
517 } else {
518 hashstart = hash;
519 }
520 saltstrlen = saltstart ? (hashstart - 1 - saltstart) : 0;
521 if (saltstrlen > BYTES2CHARS(64) ||
522 strlen((char *)hashstart) != HASH_LEN)
523 return NULL;
524
525 if (saltstrlen) {
526 const uint8_t *saltend;
527 saltlen = sizeof(saltbin);
528 saltend = decode64(saltbin, &saltlen, saltstart, saltstrlen);
529 if (!saltend || *saltend != '$' || saltlen < 1 || saltlen > 64)
530 goto out;
531
532 if (from_key)
533 yescrypt_sha256_cipher(saltbin, saltlen, from_key, ENC);
534 if (to_key)
535 yescrypt_sha256_cipher(saltbin, saltlen, to_key, DEC);
536 }
537
538 hashlen = sizeof(hashbin);
539 hashend = decode64(hashbin, &hashlen, hashstart, HASH_LEN);
540 if (!hashend || *hashend || hashlen != sizeof(hashbin))
541 goto out;
542
543 if (from_key)
544 yescrypt_sha256_cipher(hashbin, hashlen, from_key, DEC);
545 if (to_key)
546 yescrypt_sha256_cipher(hashbin, hashlen, to_key, ENC);
547
548 if (saltstrlen) {
549 if (!encode64(saltstart, saltstrlen + 1, saltbin, saltlen))
550 goto out; /* can't happen */
551 *(saltstart + saltstrlen) = '$';
552 }
553
554 if (!encode64(hashstart, HASH_LEN + 1, hashbin, hashlen))
555 goto out; /* can't happen */
556
557 retval = hash;
558
559 out:
560 explicit_bzero(saltbin, sizeof(saltbin));
561 explicit_bzero(hashbin, sizeof(hashbin));
562
563 return retval;
564 }
565
566 static uint32_t N2log2(uint64_t N)
567 {
568 uint32_t N_log2;
569
570 if (N < 2)
571 return 0;
572
573 N_log2 = 2;
574 while (N >> N_log2 != 0)
575 N_log2++;
576 N_log2--;
577
578 if (N >> N_log2 != 1)
579 return 0;
580
581 return N_log2;
582 }
583
584 uint8_t *yescrypt_encode_params_r(const yescrypt_params_t *params,
585 const uint8_t *src, size_t srclen,
586 uint8_t *buf, size_t buflen)
587 {
588 uint32_t flavor, N_log2, NROM_log2, have;
589 uint8_t *dst;
590
591 if (srclen > SIZE_MAX / 16)
592 return NULL;
593
594 if (params->flags < YESCRYPT_RW) {
595 flavor = params->flags;
596 } else if ((params->flags & YESCRYPT_MODE_MASK) == YESCRYPT_RW &&
597 params->flags <= (YESCRYPT_RW | YESCRYPT_RW_FLAVOR_MASK)) {
598 flavor = YESCRYPT_RW + (params->flags >> 2);
599 } else {
600 return NULL;
601 }
602
603 N_log2 = N2log2(params->N);
604 if (!N_log2)
605 return NULL;
606
607 NROM_log2 = N2log2(params->NROM);
608 if (params->NROM && !NROM_log2)
609 return NULL;
610
611 if ((uint64_t)params->r * (uint64_t)params->p >= (1U << 30))
612 return NULL;
613
614 dst = buf;
615 *dst++ = '$';
616 *dst++ = 'y';
617 *dst++ = '$';
618
619 dst = encode64_uint32(dst, buflen - (dst - buf), flavor, 0);
620 if (!dst)
621 return NULL;
622
623 dst = encode64_uint32(dst, buflen - (dst - buf), N_log2, 1);
624 if (!dst)
625 return NULL;
626
627 dst = encode64_uint32(dst, buflen - (dst - buf), params->r, 1);
628 if (!dst)
629 return NULL;
630
631 have = 0;
632 if (params->p != 1)
633 have |= 1;
634 if (params->t)
635 have |= 2;
636 if (params->g)
637 have |= 4;
638 if (NROM_log2)
639 have |= 8;
640
641 if (have) {
642 dst = encode64_uint32(dst, buflen - (dst - buf), have, 1);
643 if (!dst)
644 return NULL;
645 }
646
647 if (params->p != 1) {
648 dst = encode64_uint32(dst, buflen - (dst - buf), params->p, 2);
649 if (!dst)
650 return NULL;
651 }
652
653 if (params->t) {
654 dst = encode64_uint32(dst, buflen - (dst - buf), params->t, 1);
655 if (!dst)
656 return NULL;
657 }
658
659 if (params->g) {
660 dst = encode64_uint32(dst, buflen - (dst - buf), params->g, 1);
661 if (!dst)
662 return NULL;
663 }
664
665 if (NROM_log2) {
666 dst = encode64_uint32(dst, buflen - (dst - buf), NROM_log2, 1);
667 if (!dst)
668 return NULL;
669 }
670
671 if (dst >= buf + buflen)
672 return NULL;
673
674 *dst++ = '$';
675
676 dst = encode64(dst, buflen - (dst - buf), src, srclen);
677 if (!dst || dst >= buf + buflen)
678 return NULL;
679
680 *dst = 0; /* NUL termination */
681
682 return buf;
683 }
684
685 uint8_t *yescrypt_encode_params(const yescrypt_params_t *params,
686 const uint8_t *src, size_t srclen)
687 {
688 /* prefix, NUL */
689 static uint8_t buf[PREFIX_LEN + 1];
690 return yescrypt_encode_params_r(params, src, srclen, buf, sizeof(buf));
691 }
692
693 int crypto_scrypt(const uint8_t *passwd, size_t passwdlen,
694 const uint8_t *salt, size_t saltlen, uint64_t N, uint32_t r, uint32_t p,
695 uint8_t *buf, size_t buflen)
696 {
697 yescrypt_local_t local;
698 yescrypt_params_t params = { .flags = 0, .N = N, .r = r, .p = p };
699 int retval;
700
701 if (yescrypt_init_local(&local))
702 return -1;
703 retval = yescrypt_kdf(NULL, &local,
704 passwd, passwdlen, salt, saltlen, ¶ms, buf, buflen);
705 if (yescrypt_free_local(&local))
706 return -1;
707 return retval;
708 }
709
710 #endif /* INCLUDE_yescrypt || INCLUDE_scrypt || INCLUDE_gost_yescrypt */