src/crypto.c

#include "crypto.h"
#include "util.h"

#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/random.h>
#include <unistd.h>

/* ---------------- SHA-256 (FIPS 180-4) ---------------- */

struct s256 { uint32_t h[8]; uint64_t len; uint8_t b[64]; size_t bl; };

static const uint32_t K[64] = {
    0x428a2f98,0x71374491,0xb5c0fbcf,0xe9b5dba5,0x3956c25b,0x59f111f1,
    0x923f82a4,0xab1c5ed5,0xd807aa98,0x12835b01,0x243185be,0x550c7dc3,
    0x72be5d74,0x80deb1fe,0x9bdc06a7,0xc19bf174,0xe49b69c1,0xefbe4786,
    0x0fc19dc6,0x240ca1cc,0x2de92c6f,0x4a7484aa,0x5cb0a9dc,0x76f988da,
    0x983e5152,0xa831c66d,0xb00327c8,0xbf597fc7,0xc6e00bf3,0xd5a79147,
    0x06ca6351,0x14292967,0x27b70a85,0x2e1b2138,0x4d2c6dfc,0x53380d13,
    0x650a7354,0x766a0abb,0x81c2c92e,0x92722c85,0xa2bfe8a1,0xa81a664b,
    0xc24b8b70,0xc76c51a3,0xd192e819,0xd6990624,0xf40e3585,0x106aa070,
    0x19a4c116,0x1e376c08,0x2748774c,0x34b0bcb5,0x391c0cb3,0x4ed8aa4a,
    0x5b9cca4f,0x682e6ff3,0x748f82ee,0x78a5636f,0x84c87814,0x8cc70208,
    0x90befffa,0xa4506ceb,0xbef9a3f7,0xc67178f2
};

#define RR(x,n) (((x) >> (n)) | ((x) << (32 - (n))))

static void s256_block(struct s256 *s, const uint8_t *p)
{
    uint32_t w[64];
    for (int i = 0; i < 16; i++)
        w[i] = (uint32_t)p[i*4] << 24 | (uint32_t)p[i*4+1] << 16 |
               (uint32_t)p[i*4+2] << 8 | (uint32_t)p[i*4+3];
    for (int i = 16; i < 64; i++) {
        uint32_t s0 = RR(w[i-15],7) ^ RR(w[i-15],18) ^ (w[i-15] >> 3);
        uint32_t s1 = RR(w[i-2],17) ^ RR(w[i-2],19) ^ (w[i-2] >> 10);
        w[i] = w[i-16] + s0 + w[i-7] + s1;
    }
    uint32_t a=s->h[0],b=s->h[1],c=s->h[2],d=s->h[3],
             e=s->h[4],f=s->h[5],g=s->h[6],h=s->h[7];
    for (int i = 0; i < 64; i++) {
        uint32_t S1 = RR(e,6) ^ RR(e,11) ^ RR(e,25);
        uint32_t ch = (e & f) ^ (~e & g);
        uint32_t t1 = h + S1 + ch + K[i] + w[i];
        uint32_t S0 = RR(a,2) ^ RR(a,13) ^ RR(a,22);
        uint32_t mj = (a & b) ^ (a & c) ^ (b & c);
        uint32_t t2 = S0 + mj;
        h=g; g=f; f=e; e=d+t1; d=c; c=b; b=a; a=t1+t2;
    }
    s->h[0]+=a; s->h[1]+=b; s->h[2]+=c; s->h[3]+=d;
    s->h[4]+=e; s->h[5]+=f; s->h[6]+=g; s->h[7]+=h;
}

static void s256_init(struct s256 *s)
{
    static const uint32_t iv[8] = {
        0x6a09e667,0xbb67ae85,0x3c6ef372,0xa54ff53a,
        0x510e527f,0x9b05688c,0x1f83d9ab,0x5be0cd19
    };
    memcpy(s->h, iv, sizeof iv);
    s->len = 0;
    s->bl = 0;
}

static void s256_update(struct s256 *s, const void *data, size_t len)
{
    const uint8_t *p = data;
    s->len += len;
    while (len) {
        size_t take = 64 - s->bl;
        if (take > len)
            take = len;
        memcpy(s->b + s->bl, p, take);
        s->bl += take;
        p += take;
        len -= take;
        if (s->bl == 64) {
            s256_block(s, s->b);
            s->bl = 0;
        }
    }
}

static void s256_final(struct s256 *s, uint8_t out[32])
{
    uint64_t bits = s->len * 8;
    uint8_t pad = 0x80;
    s256_update(s, &pad, 1);
    uint8_t z = 0;
    while (s->bl != 56)
        s256_update(s, &z, 1);
    uint8_t lb[8];
    for (int i = 0; i < 8; i++)
        lb[i] = (uint8_t)(bits >> (56 - i * 8));
    s256_update(s, lb, 8);
    for (int i = 0; i < 8; i++) {
        out[i*4]   = (uint8_t)(s->h[i] >> 24);
        out[i*4+1] = (uint8_t)(s->h[i] >> 16);
        out[i*4+2] = (uint8_t)(s->h[i] >> 8);
        out[i*4+3] = (uint8_t)s->h[i];
    }
}

void sha256(const void *data, size_t len, uint8_t out[32])
{
    struct s256 s;
    s256_init(&s);
    s256_update(&s, data, len);
    s256_final(&s, out);
}

static void hmac_sha256(const uint8_t *key, size_t klen,
                        const uint8_t *msg, size_t mlen, uint8_t out[32])
{
    uint8_t k[64];
    memset(k, 0, 64);
    if (klen > 64) {
        sha256(key, klen, k);
    } else {
        memcpy(k, key, klen);
    }
    uint8_t ipad[64], opad[64];
    for (int i = 0; i < 64; i++) {
        ipad[i] = k[i] ^ 0x36;
        opad[i] = k[i] ^ 0x5c;
    }
    struct s256 s;
    s256_init(&s);
    s256_update(&s, ipad, 64);
    s256_update(&s, msg, mlen);
    uint8_t inner[32];
    s256_final(&s, inner);
    s256_init(&s);
    s256_update(&s, opad, 64);
    s256_update(&s, inner, 32);
    s256_final(&s, out);
}

void gt_hmac_sha256(const uint8_t *key, size_t klen,
                    const uint8_t *msg, size_t mlen, uint8_t out[32])
{
    hmac_sha256(key, klen, msg, mlen, out);
}

/* ---------------- PBKDF2 ---------------- */

void pbkdf2_sha256(const char *password, const uint8_t *salt, size_t saltlen,
                   unsigned iters, uint8_t out[32])
{
    /* single block (dkLen == hLen) */
    struct buf m;
    buf_init(&m);
    buf_put(&m, salt, saltlen);
    uint8_t ctr[4] = { 0, 0, 0, 1 };
    buf_put(&m, ctr, 4);
    uint8_t u[32];
    hmac_sha256((const uint8_t *)password, strlen(password),
                (const uint8_t *)m.data, m.len, u);
    memcpy(out, u, 32);
    for (unsigned i = 1; i < iters; i++) {
        hmac_sha256((const uint8_t *)password, strlen(password), u, 32, u);
        for (int j = 0; j < 32; j++)
            out[j] ^= u[j];
    }
    buf_free(&m);
}

/* HMAC-SHA256 over two message parts (scrypt needs salt || counter) */
static void hmac_sha256_2(const uint8_t *key, size_t klen,
                          const uint8_t *m1, size_t m1len,
                          const uint8_t *m2, size_t m2len, uint8_t out[32])
{
    uint8_t k[64];
    memset(k, 0, 64);
    if (klen > 64) {
        sha256(key, klen, k);
    } else {
        memcpy(k, key, klen);
    }
    uint8_t ipad[64], opad[64];
    for (int i = 0; i < 64; i++) {
        ipad[i] = k[i] ^ 0x36;
        opad[i] = k[i] ^ 0x5c;
    }
    struct s256 s;
    s256_init(&s);
    s256_update(&s, ipad, 64);
    s256_update(&s, m1, m1len);
    s256_update(&s, m2, m2len);
    uint8_t inner[32];
    s256_final(&s, inner);
    s256_init(&s);
    s256_update(&s, opad, 64);
    s256_update(&s, inner, 32);
    s256_final(&s, out);
}

/* multi-block PBKDF2-HMAC-SHA256 (scrypt's outer KDF) */
static void pbkdf2_any(const uint8_t *pw, size_t plen,
                       const uint8_t *salt, size_t saltlen,
                       unsigned iters, uint8_t *out, size_t olen)
{
    uint8_t u[32];
    uint32_t blk = 1;
    while (olen) {
        uint8_t ctr[4] = { (uint8_t)(blk >> 24), (uint8_t)(blk >> 16),
                           (uint8_t)(blk >> 8), (uint8_t)blk };
        hmac_sha256_2(pw, plen, salt, saltlen, ctr, 4, u);
        uint8_t t[32];
        memcpy(t, u, 32);
        for (unsigned i = 1; i < iters; i++) {
            hmac_sha256(pw, plen, u, 32, u);
            for (int j = 0; j < 32; j++)
                t[j] ^= u[j];
        }
        size_t n = olen < 32 ? olen : 32;
        memcpy(out, t, n);
        out += n;
        olen -= n;
        blk++;
    }
}

/* ---------------- scrypt (RFC 7914) ---------------- */

#define R32(a, b) (((a) << (b)) | ((a) >> (32 - (b))))

static uint32_t le32d(const uint8_t *p)
{
    return (uint32_t)p[0] | (uint32_t)p[1] << 8 | (uint32_t)p[2] << 16 |
           (uint32_t)p[3] << 24;
}

static void le32e(uint8_t *p, uint32_t v)
{
    p[0] = (uint8_t)v;
    p[1] = (uint8_t)(v >> 8);
    p[2] = (uint8_t)(v >> 16);
    p[3] = (uint8_t)(v >> 24);
}

static void salsa20_8(uint32_t B[16])
{
    uint32_t x[16];
    memcpy(x, B, 64);
    for (int i = 0; i < 8; i += 2) {
        x[ 4] ^= R32(x[ 0] + x[12],  7);
        x[ 8] ^= R32(x[ 4] + x[ 0],  9);
        x[12] ^= R32(x[ 8] + x[ 4], 13);
        x[ 0] ^= R32(x[12] + x[ 8], 18);
        x[ 9] ^= R32(x[ 5] + x[ 1],  7);
        x[13] ^= R32(x[ 9] + x[ 5],  9);
        x[ 1] ^= R32(x[13] + x[ 9], 13);
        x[ 5] ^= R32(x[ 1] + x[13], 18);
        x[14] ^= R32(x[10] + x[ 6],  7);
        x[ 2] ^= R32(x[14] + x[10],  9);
        x[ 6] ^= R32(x[ 2] + x[14], 13);
        x[10] ^= R32(x[ 6] + x[ 2], 18);
        x[ 3] ^= R32(x[15] + x[11],  7);
        x[ 7] ^= R32(x[ 3] + x[15],  9);
        x[11] ^= R32(x[ 7] + x[ 3], 13);
        x[15] ^= R32(x[11] + x[ 7], 18);
        x[ 1] ^= R32(x[ 0] + x[ 3],  7);
        x[ 2] ^= R32(x[ 1] + x[ 0],  9);
        x[ 3] ^= R32(x[ 2] + x[ 1], 13);
        x[ 0] ^= R32(x[ 3] + x[ 2], 18);
        x[ 6] ^= R32(x[ 5] + x[ 4],  7);
        x[ 7] ^= R32(x[ 6] + x[ 5],  9);
        x[ 4] ^= R32(x[ 7] + x[ 6], 13);
        x[ 5] ^= R32(x[ 4] + x[ 7], 18);
        x[11] ^= R32(x[10] + x[ 9],  7);
        x[ 8] ^= R32(x[11] + x[10],  9);
        x[ 9] ^= R32(x[ 8] + x[11], 13);
        x[10] ^= R32(x[ 9] + x[ 8], 18);
        x[12] ^= R32(x[15] + x[14],  7);
        x[13] ^= R32(x[12] + x[15],  9);
        x[14] ^= R32(x[13] + x[12], 13);
        x[15] ^= R32(x[14] + x[13], 18);
    }
    for (int i = 0; i < 16; i++)
        B[i] += x[i];
}

/* BlockMix_salsa8: B is 2r 64-byte blocks (32r words), Y same size */
static void blockmix(uint32_t *B, uint32_t *Y, unsigned r)
{
    uint32_t X[16];
    memcpy(X, B + (size_t)(2 * r - 1) * 16, 64);
    for (unsigned i = 0; i < 2 * r; i++) {
        for (int j = 0; j < 16; j++)
            X[j] ^= B[i * 16 + j];
        salsa20_8(X);
        memcpy(Y + i * 16, X, 64);
    }
    for (unsigned i = 0; i < r; i++) {
        memcpy(B + i * 16, Y + (i * 2) * 16, 64);
        memcpy(B + (i + r) * 16, Y + (i * 2 + 1) * 16, 64);
    }
}

/* ROMix: B is 32r words, V is N * 32r words of memory-hard scratch */
static void romix(uint32_t *B, uint32_t *V, uint32_t *Y,
                  uint64_t N, unsigned r)
{
    size_t bw = (size_t)32 * r;
    uint32_t *X = B;
    for (uint64_t i = 0; i < N; i++) {
        memcpy(V + i * bw, X, bw * 4);
        blockmix(X, Y, r);
    }
    for (uint64_t i = 0; i < N; i++) {
        /* Integerify(B): last 64-byte block as a little-endian int */
        uint64_t j = (uint64_t)X[(size_t)(2 * r - 1) * 16] |
                     (uint64_t)X[(size_t)(2 * r - 1) * 16 + 1] << 32;
        j &= N - 1;                     /* N is a power of two */
        for (size_t k = 0; k < bw; k++)
            X[k] ^= V[j * bw + k];
        blockmix(X, Y, r);
    }
}

int scrypt_kdf(const uint8_t *pw, size_t pwlen,
               const uint8_t *salt, size_t saltlen,
               uint64_t N, unsigned r, unsigned p,
               uint8_t *out, size_t outlen)
{
    if (N < 2 || (N & (N - 1)) != 0 || r < 1 || p < 1 || r > 64 ||
        p > 64 || outlen == 0)
        return -1;
    size_t bw = (size_t)32 * r;
    size_t blen = bw * 4 * p;           /* 128 * r * p bytes */
    uint8_t  *B = malloc(blen);
    uint32_t *W = malloc(blen);
    uint32_t *V = malloc(bw * 4 * (size_t)N);
    uint32_t *Y = malloc(bw * 4);
    if (!B || !W || !V || !Y) {
        free(B); free(W); free(V); free(Y);
        return -1;
    }
    pbkdf2_any(pw, pwlen, salt, saltlen, 1, B, blen);
    for (size_t i = 0; i < bw * p; i++)
        W[i] = le32d(B + i * 4);
    for (unsigned i = 0; i < p; i++)
        romix(W + i * bw, V, Y, N, r);
    for (size_t i = 0; i < bw * p; i++)
        le32e(B + i * 4, W[i]);
    pbkdf2_any(pw, pwlen, B, blen, 1, out, outlen);
    gt_bzero(B, blen);
    gt_bzero(W, blen);
    gt_bzero(V, bw * 4 * (size_t)N);
    gt_bzero(Y, bw * 4);
    free(B); free(W); free(V); free(Y);
    return 0;
}

/* ---------------- hex / random / compare ---------------- */

void to_hex(const uint8_t *in, size_t n, char *out)
{
    static const char H[] = "0123456789abcdef";
    for (size_t i = 0; i < n; i++) {
        out[i*2]   = H[in[i] >> 4];
        out[i*2+1] = H[in[i] & 15];
    }
    out[n*2] = '\0';
}

static int hexv(int c)
{
    if (c >= '0' && c <= '9') return c - '0';
    if (c >= 'a' && c <= 'f') return c - 'a' + 10;
    if (c >= 'A' && c <= 'F') return c - 'A' + 10;
    return -1;
}

int from_hex(const char *hex, uint8_t *out, size_t outlen)
{
    for (size_t i = 0; i < outlen; i++) {
        int hi = hexv(hex[i*2]), lo = hexv(hex[i*2+1]);
        if (hi < 0 || lo < 0)
            return -1;
        out[i] = (uint8_t)(hi * 16 + lo);
    }
    return 0;
}

void rand_bytes(void *buf, size_t n)
{
    uint8_t *p = buf;
    while (n) {
        ssize_t r = getrandom(p, n, 0);
        if (r > 0) {
            p += r;
            n -= (size_t)r;
            continue;
        }
        /* fallback: /dev/urandom */
        int fd = open("/dev/urandom", O_RDONLY);
        if (fd < 0)
            die("getrandom");
        ssize_t q = read(fd, p, n);
        close(fd);
        if (q <= 0)
            die("urandom");
        p += q;
        n -= (size_t)q;
    }
}

void rand_hex(char *out, size_t n)
{
    uint8_t *tmp = xmalloc(n);
    rand_bytes(tmp, n);
    to_hex(tmp, n, out);
    memset(tmp, 0, n);
    free(tmp);
}

int consteq(const void *a, const void *b, size_t n)
{
    const uint8_t *x = a, *y = b;
    uint8_t d = 0;
    for (size_t i = 0; i < n; i++)
        d |= (uint8_t)(x[i] ^ y[i]);
    return d == 0;
}

/* memory wipe the compiler cannot elide */
void gt_bzero(void *p, size_t n)
{
#if defined(__GLIBC__) || defined(__MUSL__) || defined(__OpenBSD__) || \
    defined(__FreeBSD__)
    explicit_bzero(p, n);
#else
    volatile uint8_t *v = p;
    while (n--)
        *v++ = 0;
#endif
}

/* ---------------- password storage ----------------
 * Versioned formats, dispatched by prefix:
 *   scrypt$<N>$<r>$<p>$<32-hex salt>$<64-hex hash>   (current)
 *   pbkdf2$<iters>$<64-hex salt>$<64-hex hash>       (legacy)
 * Verify accepts both; hash always emits scrypt unless
 * GIT_TRACE_KDF=pbkdf2 forces the legacy writer (migration tests).
 * pw_needs_rehash() flags rows still on a legacy scheme. */

#define PW_ITERS 100000
#define SC_N     32768          /* ~32 MiB of ROMix scratch */
#define SC_R     8
#define SC_P     1
/* verify-side caps: a tampered DB row may not memory-bomb us */
#define SC_N_MAX (1u << 18)

int pw_hash(const char *password, char *out, size_t outlen)
{
    uint8_t salt[16], dk[32];
    rand_bytes(salt, sizeof salt);
    const char *kdf = getenv("GIT_TRACE_KDF");
    if (kdf && strcmp(kdf, "pbkdf2") == 0) {
        pbkdf2_sha256(password, salt, sizeof salt, PW_ITERS, dk);
        char sh[33], dh[65];
        to_hex(salt, 16, sh);
        to_hex(dk, 32, dh);
        int rc = snprintf(out, outlen, "pbkdf2$%u$%s$%s",
                          PW_ITERS, sh, dh) < (int)outlen ? 0 : -1;
        gt_bzero(dk, sizeof dk);
        return rc;
    }
    if (scrypt_kdf((const uint8_t *)password, strlen(password),
                   salt, sizeof salt, SC_N, SC_R, SC_P, dk, 32) != 0)
        return -1;
    char sh[33], dh[65];
    to_hex(salt, 16, sh);
    to_hex(dk, 32, dh);
    int rc = snprintf(out, outlen, "scrypt$%u$%u$%u$%s$%s",
                      (unsigned)SC_N, SC_R, SC_P, sh, dh)
             < (int)outlen ? 0 : -1;
    gt_bzero(dk, sizeof dk);
    return rc;
}

int pw_verify(const char *password, const char *stored)
{
    if (strncmp(stored, "scrypt$", 7) == 0) {
        unsigned long long N;
        unsigned r, p;
        char sh[65], dh[65];
        if (sscanf(stored, "scrypt$%llu$%u$%u$%64[0-9a-f]$%64[0-9a-f]",
                   &N, &r, &p, sh, dh) != 5)
            return 0;
        if (N < 2 || N > SC_N_MAX || (N & (N - 1)) != 0 ||
            r < 1 || r > 16 || p < 1 || p > 16)
            return 0;
        size_t sl = strlen(sh) / 2;
        if (sl == 0 || sl > 32 || strlen(dh) != 64)
            return 0;
        uint8_t salt[32], want[32], dk[32];
        if (from_hex(sh, salt, sl) != 0 || from_hex(dh, want, 32) != 0)
            return 0;
        if (scrypt_kdf((const uint8_t *)password, strlen(password),
                       salt, sl, N, r, p, dk, 32) != 0)
            return 0;
        int ok = consteq(dk, want, 32);
        gt_bzero(dk, sizeof dk);
        return ok;
    }
    unsigned iters;
    char sh[65], dh[65];
    if (sscanf(stored, "pbkdf2$%u$%64[0-9a-f]$%64[0-9a-f]",
               &iters, sh, dh) != 3)
        return 0;
    if (iters < 1 || iters > 10000000)
        return 0;
    size_t sl = strlen(sh) / 2;
    if (sl == 0 || sl > 32 || strlen(dh) != 64)
        return 0;
    uint8_t salt[32], want[32], dk[32];
    if (from_hex(sh, salt, sl) != 0 || from_hex(dh, want, 32) != 0)
        return 0;
    pbkdf2_sha256(password, salt, sl, iters, dk);
    int ok = consteq(dk, want, 32);
    gt_bzero(dk, sizeof dk);
    return ok;
}

int pw_needs_rehash(const char *stored)
{
    return strncmp(stored, "scrypt$", 7) != 0;
}

const char *pw_scheme(const char *stored)
{
    if (strncmp(stored, "scrypt$", 7) == 0)
        return "scrypt";
    if (strncmp(stored, "pbkdf2$", 7) == 0)
        return "pbkdf2";
    return "unknown";
}

/* ---------------- base64 ---------------- */

long b64_decode(const char *in, size_t inlen, void *outp, size_t outcap)
{
    uint8_t *out = outp;
    size_t w = 0;
    uint32_t acc = 0;
    int bits = 0;
    for (size_t i = 0; i < inlen; i++) {
        int c = (unsigned char)in[i];
        int v;
        if (c >= 'A' && c <= 'Z')      v = c - 'A';
        else if (c >= 'a' && c <= 'z') v = c - 'a' + 26;
        else if (c >= '0' && c <= '9') v = c - '0' + 52;
        else if (c == '+')             v = 62;
        else if (c == '/')             v = 63;
        else if (c == '=')             break;
        else                           return -1;
        acc = (acc << 6) | (uint32_t)v;
        bits += 6;
        if (bits >= 8) {
            bits -= 8;
            if (w >= outcap)
                return -1;
            out[w++] = (uint8_t)(acc >> bits);
        }
    }
    return (long)w;
}

void b64_encode(const void *inp, size_t inlen, char *out, size_t outcap,
                int strip_padding)
{
    static const char T[] =
        "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
    const uint8_t *in = inp;
    size_t w = 0;
    for (size_t i = 0; i + 3 <= inlen; i += 3) {
        uint32_t v = (uint32_t)in[i] << 16 | (uint32_t)in[i+1] << 8 | in[i+2];
        if (w + 4 >= outcap) { out[0] = 0; return; }
        out[w++] = T[v >> 18];
        out[w++] = T[(v >> 12) & 63];
        out[w++] = T[(v >> 6) & 63];
        out[w++] = T[v & 63];
    }
    size_t rem = inlen % 3;
    if (rem) {
        uint32_t v = (uint32_t)in[inlen - rem] << 16;
        if (rem == 2)
            v |= (uint32_t)in[inlen - 1] << 8;
        if (w + 4 >= outcap) { out[0] = 0; return; }
        out[w++] = T[v >> 18];
        out[w++] = T[(v >> 12) & 63];
        if (rem == 2)
            out[w++] = T[(v >> 6) & 63];
        if (!strip_padding)
            for (size_t k = rem; k < 3; k++)
                out[w++] = '=';
    }
    out[w] = '\0';
}