1 files changed, 408 insertions, 0 deletions

diff --git a/libbb/yescrypt/alg-yescrypt-common.c b/libbb/yescrypt/alg-yescrypt-common.c
new file mode 100644
index 000000000..c51823787
--- /dev/null
+++ b/libbb/yescrypt/alg-yescrypt-common.c
@@ -0,0 +1,408 @@
+/*-
+ * Copyright 2013-2018 Alexander Peslyak
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#if RESTRICTED_PARAMS
+
+#define decode64_uint32(dst, src, min) \
+({ \
+        uint32_t d32 = a2i64(*(src)); \
+        if (d32 > 47) \
+                goto fail; \
+        *(dst) = d32 + (min); \
+        ++src; \
+})
+#define test_decode64_uint32() ((void)0)
+#define FULL_PARAMS(...)
+
+#else
+
+#define FULL_PARAMS(...) __VA_ARGS__
+
+/* Not inlining:
+ * de/encode64 functions are only used to read
+ * yescrypt_params_t field, and convert salt to binary -
+ * both of these are negligible compared to main hashing operation
+ */
+static NOINLINE const uint8_t *decode64_uint32(
+                uint32_t *dst,
+                const uint8_t *src, uint32_t val)
+{
+        uint32_t start = 0, end = 47, bits = 0;
+        uint32_t c;
+
+        if (!src) /* previous decode failed already? */
+                goto fail;
+
+        c = a2i64(*src++);
+        if (c > 63)
+                goto fail;
+
+// The encoding of number N:
+// start = 0 end = 47
+// If N < 48, it is encoded verbatim, else
+// N -= 48
+// start = end+1 = 48
+// end += (64-end)/2 = 55
+// If N < (end+1-start)<<6 = 8<<6, it is encoded as 48+(N>>6)|low6bits (that is, 48...55|<6bit>), else
+// N -= 8<<6
+// start = end+1 = 56
+// end += (64-end)/2 = 59
+// If N < (end+1-start)<<2*6 = 4<<12, it is encoded as 56+(N>>2*6)|low12bits (that is, 56...59|<6bit>|<6bit>), else
+// ...same for 60..61|<6bit>|<6bit>|<6bit>
+// .......same for 62|<6bit>|<6bit>|<6bit>|<6bit>
+// .......same for 63|<6bit>|<6bit>|<6bit>|<6bit>|<6bit>
+        dbg_dec64("c:%d val:0x%08x", (int)c, (unsigned)val);
+        while (c > end) {
+                dbg_dec64("c:%d > end:%d", (int)c, (int)end);
+                val += (end + 1 - start) << bits;
+                dbg_dec64("val+=0x%08x", (int)((end + 1 - start) << bits));
+                dbg_dec64(" val:0x%08x", (unsigned)val);
+                start = end + 1;
+                end += (64 - end) / 2;
+                bits += 6;
+                dbg_dec64("start=%d", (int)start);
+                dbg_dec64("end=%d", (int)end);
+                dbg_dec64("bits=%d", (int)bits);
+        }
+
+        val += (c - start) << bits;
+        dbg_dec64("final val+=0x%08x", (int)((c - start) << bits));
+        dbg_dec64("       val:0x%08x", (unsigned)val);
+
+        while (bits != 0) {
+                c = a2i64(*src++);
+                if (c > 63)
+                        goto fail;
+                bits -= 6;
+                val += c << bits;
+                dbg_dec64("low bits val+=0x%08x", (int)(c << bits));
+                dbg_dec64("          val:0x%08x", (unsigned)val);
+        }
+ ret:
+        *dst = val;
+        return src;
+ fail:
+        val = 0;
+        src = NULL;
+        goto ret;
+}
+
+#if TEST_DECODE64
+static void test_decode64_uint32(void)
+{
+        const uint8_t *src, *end;
+        uint32_t u32;
+        int a = 48;
+        int b = 8<<6;  // 0x0200
+        int c = 4<<12; // 0x04000
+        int d = 2<<18; // 0x080000
+        int e = 1<<24; // 0x1000000
+
+        src = (void*)"wzzz";
+        end = decode64_uint32(&u32, src, 0);
+        if (u32 != 0x0003ffff+c+b+a) bb_error_msg_and_die("Incorrect decode '%s':0x%08x", src, (unsigned)u32);
+        if (end != src + 4) bb_error_msg_and_die("Incorrect decode '%s': %p end:%p", src, src, end);
+        src = (void*)"xzzz";
+        end = decode64_uint32(&u32, src, 0);
+        if (u32 != 0x0007ffff+c+b+a) bb_error_msg_and_die("Incorrect decode '%s':0x%08x", src, (unsigned)u32);
+        if (end != src + 4) bb_error_msg_and_die("Incorrect decode '%s': %p end:%p", src, src, end);
+        // Note how the last representable "x---" encoding, 0x7ffff, is exactly d-1!
+        // And if we now increment it, we get:
+        src = (void*)"y....";
+        end = decode64_uint32(&u32, src, 0);
+        if (u32 != 0x00000000+d+c+b+a) bb_error_msg_and_die("Incorrect decode '%s':0x%08x", src, (unsigned)u32);
+        if (end != src + 5) bb_error_msg_and_die("Incorrect decode '%s': %p end:%p", src, src, end);
+        src = (void*)"yzzzz";
+        end = decode64_uint32(&u32, src, 0);
+        if (u32 != 0x00ffffff+d+c+b+a) bb_error_msg_and_die("Incorrect decode '%s':0x%08x", src, (unsigned)u32);
+        if (end != src + 5) bb_error_msg_and_die("Incorrect decode '%s': %p end:%p", src, src, end);
+
+        src = (void*)"zzzzzz";
+        end = decode64_uint32(&u32, src, 0);
+        if (u32 != 0x3fffffff+e+d+c+b+a) bb_error_msg_and_die("Incorrect decode '%s':0x%08x", src, (unsigned)u32);
+        if (end != src + 6) bb_error_msg_and_die("Incorrect decode '%s': %p end:%p", src, src, end);
+
+        bb_error_msg("test_decode64_uint32() OK");
+}
+#else
+# define test_decode64_uint32() ((void)0)
+#endif
+
+#endif /* !RESTRICTED_PARAMS */
+
+#if 1
+static const uint8_t *decode64(
+                uint8_t *dst, size_t *dstlen,
+                const uint8_t *src)
+{
+        unsigned dstpos = 0;
+
+        dbg_dec64("src:'%s'", src);
+        for (;;) {
+                uint32_t c, value = 0;
+                int bits = 0;
+                while (*src != '\0' && *src != '$') {
+                        c = a2i64(*src);
+                        if (c > 63) { /* bad ascii64 char, stop decoding at it */
+                                break;
+                        }
+                        src++;
+                        value |= c << bits;
+                        bits += 6;
+                        if (bits == 24) /* got 4 chars */
+                                goto store;
+                }
+                /* we read entire src, or met a non-ascii64 char (such as "$") */
+                if (bits == 0)
+                        break;
+                /* else: we got last, partial bit block - store it */
+ store:
+                dbg_dec64(" storing bits:%d dstpos:%u v:%08x", bits, dstpos, (int)SWAP_BE32(value)); //BE to see lsb first
+                for (;;) {
+                        if ((*src == '\0' || *src == '$')
+                         && value == 0 && bits < 8
+                        ) {
+                                /* Example: mkpasswd PWD '$y$j9T$123':
+                                 * the "123" is bits:18 value:03,51,00
+                                 * is considered to be 2 bytes, not 3!
+                                 *
+                                 * '$y$j9T$zzz' in upstream fails outright (3rd byte isn't zero).
+                                 * IOW: for upstream, validity of salt depends on VALUE,
+                                 * not just size of salt. Which is a bug.
+                                 * The '$y$j9T$zzz.' salt is the same
+                                 * (it adds 6 zero msbits) but upstream works with it,
+                                 * thus '$y$j9T$zzz' should work too and give the same result.
+                                 */
+                                goto end;
+                        }
+                        if (dstpos >= *dstlen) {
+                                dbg_dec64(" ERR: bits:%d dstpos:%u dst[] is too small", bits, dstpos);
+                                goto fail;
+                        }
+                        *dst++ = value;
+                        dstpos++;
+                        value >>= 8;
+                        bits -= 8;
+                        if (bits <= 0) /* can get negative, if we e.g. had 6 bits */
+                                break;
+                }
+                if (*src == '\0' || *src == '$')
+                        break;
+        }
+ end:
+        *dstlen = dstpos;
+        dbg_dec64("dec64: OK, dst[%d]", (int)dstpos);
+        return src;
+ fail:
+        /* *dstlen = 0; - not needed, caller detects error by seeing NULL */
+        return NULL;
+}
+#else
+/* Buggy (and larger) original code */
+static const uint8_t *decode64(
+                uint8_t *dst, size_t *dstlen,
+                const uint8_t *src, size_t srclen)
+{
+        size_t dstpos = 0;
+
+        while (dstpos <= *dstlen && srclen) {
+                uint32_t value = 0, bits = 0;
+                while (srclen--) {
+                        uint32_t c = a2i64(*src);
+                        if (c > 63) {
+                                srclen = 0;
+                                break;
+                        }
+                        src++;
+                        value |= c << bits;
+                        bits += 6;
+                        if (bits >= 24)
+                                break;
+                }
+                if (!bits)
+                        break;
+                if (bits < 12) /* must have at least one full byte */
+                        goto fail;
+                dbg_dec64(" storing bits:%d v:%08x", (int)bits, (int)SWAP_BE32(value)); //BE to see lsb first
+                while (dstpos++ < *dstlen) {
+                        *dst++ = value;
+                        value >>= 8;
+                        bits -= 8;
+                        if (bits < 8) { /* 2 or 4 */
+                                if (value) /* must be 0 */
+                                        goto fail;
+                                bits = 0;
+                                break;
+                        }
+                }
+                if (bits)
+                        goto fail;
+        }
+
+        if (!srclen && dstpos <= *dstlen) {
+                *dstlen = dstpos;
+                dbg_dec64("dec64: OK, dst[%d]", (int)dstpos);
+                return src;
+        }
+ fail:
+        /* *dstlen = 0; - not needed, caller detects error by seeing NULL */
+        return NULL;
+}
+#endif
+
+static char *encode64(
+                char *dst, size_t dstlen,
+                const uint8_t *src, size_t srclen)
+{
+        while (srclen) {
+                uint32_t value = 0, b = 0;
+                do {
+                        value |= (uint32_t)(*src++ << b);
+                        b += 8;
+                        srclen--;
+                } while (srclen && b < 24);
+
+                b >>= 3; /* number of bits to number of bytes */
+                b++; /* 1, 2 or 3 bytes will become 2, 3 or 4 ascii64 chars */
+                dstlen -= b;
+                if ((ssize_t)dstlen <= 0)
+                        return NULL;
+                dst = num2str64_lsb_first(dst, value, b);
+        }
+        *dst = '\0';
+        return dst;
+}
+
+char *yescrypt_r(
+                const uint8_t *passwd, size_t passwdlen,
+                const uint8_t *setting,
+                char *buf, size_t buflen)
+{
+        struct {
+                yescrypt_ctx_t yctx[1];
+                unsigned char hashbin32[32];
+        } u;
+#define yctx      u.yctx
+#define hashbin32 u.hashbin32
+        char *dst;
+        const uint8_t *src, *saltend;
+        size_t need, prefixlen;
+        uint32_t u32;
+
+        test_decode64_uint32();
+
+        memset(yctx, 0, sizeof(yctx));
+        FULL_PARAMS(yctx->param.p = 1;)
+
+        /* we assume setting starts with "$y$" (caller must ensure this) */
+        src = setting + 3;
+
+        src = decode64_uint32(&yctx->param.flags, src, 0);
+        /* "j9T" returns: 0x2f */
+        //if (!src)
+        //      goto fail;
+
+        if (yctx->param.flags < YESCRYPT_RW) {
+                dbg("yctx->param.flags=0x%x", (unsigned)yctx->param.flags);
+                goto fail; // bbox: we don't support scrypt - only yescrypt
+        } else if (yctx->param.flags <= YESCRYPT_RW + (YESCRYPT_RW_FLAVOR_MASK >> 2)) {
+                /* "j9T" sets flags to 0xb6 */
+                yctx->param.flags = YESCRYPT_RW + ((yctx->param.flags - YESCRYPT_RW) << 2);
+                dbg("yctx->param.flags=0x%x", (unsigned)yctx->param.flags);
+                dbg(" YESCRYPT_RW:%u", !!(yctx->param.flags & YESCRYPT_RW));
+                dbg((yctx->param.flags & YESCRYPT_RW_FLAVOR_MASK) ==
+                       (YESCRYPT_ROUNDS_6 | YESCRYPT_GATHER_4 | YESCRYPT_SIMPLE_2 | YESCRYPT_SBOX_12K)
+                    ? " YESCRYPT_ROUNDS_6 | YESCRYPT_GATHER_4 | YESCRYPT_SIMPLE_2 | YESCRYPT_SBOX_12K"
+                    : " flags are not standard"
+                );
+        } else {
+                goto fail;
+        }
+
+        src = decode64_uint32(&u32, src, 1);
+        if (/*!src ||*/ u32 > 63)
+                goto fail;
+        yctx->param.N = (uint64_t)1 << u32;
+        /* "j9T" sets to 4096 (1<<12) */
+        dbg("yctx->param.N=%llu (1<<%u)", (unsigned long long)yctx->param.N, (unsigned)u32);
+
+        src = decode64_uint32(&yctx->param.r, src, 1);
+        /* "j9T" sets to 32 */
+        dbg("yctx->param.r=%u", yctx->param.r);
+
+        if (!src)
+                goto fail;
+        if (*src != '$') {
+#if RESTRICTED_PARAMS
+                goto fail;
+#else
+                src = decode64_uint32(&u32, src, 1);
+                dbg("yescrypt has extended params:0x%x", (unsigned)u32);
+                if (u32 & 1)
+                        src = decode64_uint32(&yctx->param.p, src, 2);
+                if (u32 & 2)
+                        src = decode64_uint32(&yctx->param.t, src, 1);
+                if (u32 & 4)
+                        src = decode64_uint32(&yctx->param.g, src, 1);
+                if (u32 & 8) {
+                        src = decode64_uint32(&u32, src, 1);
+                        if (/*!src ||*/ u32 > 63)
+                                goto fail;
+                        yctx->param.NROM = (uint64_t)1 << u32;
+                }
+                if (!src)
+                        goto fail;
+                if (*src != '$')
+                        goto fail;
+#endif
+        }
+
+        yctx->saltlen = sizeof(yctx->salt);
+        src++; /* now points to salt */
+        saltend = decode64(yctx->salt, &yctx->saltlen, src);
+        if (!saltend || (*saltend != '\0' && *saltend != '$'))
+                goto fail; /* salt[] is too small, or bad char during decode */
+        dbg_dec64("salt is %d ascii64 chars -> %d bytes (in binary)", (int)(saltend - src), (int)yctx->saltlen);
+
+        prefixlen = saltend - setting;
+        need = prefixlen + 1 + YESCRYPT_HASH_LEN + 1;
+        if (need > buflen /*overflow is quite unlikely: || need < prefixlen*/)
+                goto fail;
+
+        if (yescrypt_kdf32(yctx, passwd, passwdlen, hashbin32)) {
+                dbg("error in yescrypt_kdf32");
+                goto fail;
+        }
+
+        dst = mempcpy(buf, setting, prefixlen);
+        *dst++ = '$';
+        dst = encode64(dst, buflen - (dst - buf), hashbin32, sizeof(hashbin32));
+        if (!dst)
+                goto fail;
+ ret:
+        free_region(yctx->local);
+        explicit_bzero(&u, sizeof(u));
+        return buf;
+ fail:
+        buf = NULL;
+        goto ret;
+#undef yctx
+#undef hashbin32
+}