Debian Codegraph @

lib/alg-yescrypt-common.c

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