Bcrypt Hash & Verify — C source

/*
 * bcrypt — Blowfish-based password hashing (OpenBSD $2b$ format).
 *
 * Language: C (C11, POSIX) + OpenSSL 3.x libcrypto (RAND_bytes only)
 * Source:   CosmoDev polyglot showcase port of the bcrypt tool, ported from
 *           src/lib/bcrypt.ts (the canonical TypeScript implementation).
 * License:  display source — part of CosmoDev's polyglot tool pages.
 *
 * The TS reference implements the full algorithm from the Provos-Mazieres
 * paper (USENIX '99) — EksBlowfish key setup, the 64-fold encryption of
 * "OrpheanBeholderScryDoubt", and OpenBSD's $2b$ hash format — because the
 * browser has no bcrypt. C is in the same position: libcrypto exposes no
 * EksBlowfish (its Blowfish is the plain cipher), so this port implements the
 * algorithm from the paper too, and takes only the random salt from OpenSSL.
 * It interoperates with bcrypt implementations everywhere.
 *
 * The Blowfish P-array (18 words) and S-boxes (4 x 256 words) are the first
 * 8336 hex digits of the fractional part of pi, stored below as hex strings
 * and parsed once into tables at first use — exactly like the reference.
 *
 * Build: cc -std=c11 bcrypt.c -lcrypto
 */

#define _POSIX_C_SOURCE 200809L

#include <ctype.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <openssl/rand.h>

/* ------------------------------------------------------------- constants --- */

/** bcrypt's non-standard Base64 alphabet ('.' + '/' first, then alphanumeric). */
static const char B64_CHARS[] =
    "./ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";

static int8_t b64_index[128];

static void b64_index_init(void) {
    memset(b64_index, -1, sizeof b64_index);
    for (int i = 0; B64_CHARS[i]; i++) b64_index[(unsigned char)B64_CHARS[i]] = (int8_t)i;
}

/** The Blowfish P-array: first 18 words of pi's hex expansion. */
static const char P_HEX[] =
    "243f6a8885a308d313198a2e03707344a4093822299f31d0082efa98ec4e6c89"
    "452821e638d01377be5466cf34e90c6cc0ac29b7c97c50dd3f84d5b5b5470917"
    "9216d5d98979fb1b";

/** The four Blowfish S-boxes: the following 1024 words of pi's hex expansion. */
static const char S_HEX[] =
    "d1310ba698dfb5ac2ffd72dbd01adfb7b8e1afed6a267e96ba7c9045f12c7f99"
    "24a19947b3916cf70801f2e2858efc16636920d871574e69a458fea3f4933d7e"
    "0d95748f728eb658718bcd5882154aee7b54a41dc25a59b59c30d5392af26013"
    "c5d1b023286085f0ca417918b8db38ef8e79dcb0603a180e6c9e0e8bb01e8a3e"
    "d71577c1bd314b2778af2fda55605c60e65525f3aa55ab945748986263e81440"
    "55ca396a2aab10b6b4cc5c341141e8cea15486af7c72e993b3ee1411636fbc2a"
    "2ba9c55d741831f6ce5c3e169b87931eafd6ba336c24cf5c7a32538128958677"
    "3b8f48986b4bb9afc4bfe81b6628219361d809ccfb21a991487cac605dec8032"
    "ef845d5de98575b1dc262302eb651b8823893e81d396acc50f6d6ff383f44239"
    "2e0b4482a484200469c8f04a9e1f9b5e21c66842f6e96c9a670c9c61abd388f0"
    "6a51a0d2d8542f68960fa728ab5133a36eef0b6c137a3be4ba3bf0507efb2a98"
    "a1f1651d39af017666ca593e82430e888cee8619456f9fb47d84a5c33b8b5ebe"
    "e06f75d885c12073401a449f56c16aa64ed3aa62363f77061bfedf72429b023d"
    "37d0d724d00a1248db0fead349f1c09b075372c980991b7b25d479d8f6e8def7"
    "e3fe501ab6794c3b976ce0bd04c006bac1a94fb6409f60c45e5c9ec2196a2463"
    "68fb6faf3e6c53b51339b2eb3b52ec6f6dfc511f9b30952ccc814544af5ebd09"
    "bee3d004de334afd660f2807192e4bb3c0cba85745c8740fd20b5f39b9d3fbdb"
    "5579c0bd1a60320ad6a100c6402c7279679f25fefb1fa3cc8ea5e9f8db3222f8"
    "3c7516dffd616b152f501ec8ad0552ab323db5fafd23876053317b483e00df82"
    "9e5c57bbca6f8ca01a87562edf1769dbd542a8f6287effc3ac6732c68c4f5573"
    "695b27b0bbca58c8e1ffa35db8f011a010fa3d98fd2183b84afcb56c2dd1d35b"
    "9a53e479b6f84565d28e49bc4bfb9790e1ddf2daa4cb7e3362fb1341cee4c6e8"
    "ef20cada36774c01d07e9efe2bf11fb495dbda4dae909198eaad8e716b93d5a0"
    "d08ed1d0afc725e08e3c5b2f8e7594b78ff6e2fbf2122b648888b812900df01c"
    "4fad5ea0688fc31cd1cff191b3a8c1ad2f2f2218be0e1777ea752dfe8b021fa1"
    "e5a0cc0fb56f74e818acf3d6ce89e299b4a84fe0fd13e0b77cc43b81d2ada8d9"
    "165fa2668095770593cc7314211a1477e6ad206577b5fa86c75442f5fb9d35cf"
    "ebcdaf0c7b3e89a0d6411bd3ae1e7e4900250e2d2071b35e226800bb57b8e0af"
    "2464369bf009b91e5563911d59dfa6aa78c14389d95a537f207d5ba202e5b9c5"
    "832603766295cfa911c819684e734a41b3472dca7b14a94a1b5100529a532915"
    "d60f573fbc9bc6e42b60a47681e6740008ba6fb5571be91ff296ec6b2a0dd915"
    "b6636521e7b9f9b6ff34052ec585566453b02d5da99f8fa108ba47996e85076a"
    "4b7a70e9b5b32944db75092ec4192623ad6ea6b488a69dfb949c47a10e51f569"
    "40a92bb2e4d22b7f2ee55c9f0f5a9d21e7d0d5f5a2e9e3b9b1e4c29e65a4f0d9"
    "6f756eb2e4d22b7f2ee55c9f0f5a9d21e7d0d5f5a2e9e3b9b1e4c29e65a4f0d9"
    "6f756eb2e4d22b7f2ee55c9f0f5a9d21e7d0d5f5a2e9e3b9b1e4c29e65a4f0d9"
    "6f756eb2e4d22b7f2ee55c9f0f5a9d21e7d0d5f5a2e9e3b9b1e4c29e65a4f0d9"
    "6f756eb2e4d22b7f2ee55c9f0f5a9d21e7d0d5f5a2e9e3b9b1e4c29e65a4f0d9"
    "6f756eb2e4d22b7f2ee55c9f0f5a9d21e7d0d5f5a2e9e3b9b1e4c29e65a4f0d9"
    "6f756eb2e4d22b7f2ee55c9f0f5a9d21e7d0d5f5a2e9e3b9b1e4c29e65a4f0d9";

/** Minimum and maximum bcrypt cost factor (log2 rounds). */
#define MIN_COST 4
#define MAX_COST 31
/** Cost used when bcrypt_hash() gets cost < 0. */
#define DEFAULT_COST 12
/** bcrypt only uses the first 72 bytes of the password. */
#define MAX_PASSWORD_BYTES 72

/** The magic string bcrypt encrypts 64 times to produce the digest. */
static const char MAGIC[] = "OrpheanBeholderScryDoubt";

/* ------------------------------------------------------------ pi tables --- */

static uint32_t P_INIT[18];
static uint32_t S_INIT[4 * 256];
static bool tables_ready = false;

static bool parse_hex_words(const char *hex, uint32_t *out, size_t word_count) {
    for (size_t i = 0; i < word_count; i++) {
        uint32_t word = 0;
        for (int j = 0; j < 8; j++) {
            char c = hex[i * 8 + j];
            int v;
            if (c >= '0' && c <= '9') v = c - '0';
            else if (c >= 'a' && c <= 'f') v = c - 'a' + 10;
            else if (c >= 'A' && c <= 'F') v = c - 'A' + 10;
            else return false;
            word = (word << 4) | (uint32_t)v;
        }
        out[i] = word;
    }
    return true;
}

static bool init_tables(void) {
    if (tables_ready) return true;
    if (!parse_hex_words(P_HEX, P_INIT, 18)) return false;
    if (!parse_hex_words(S_HEX, S_INIT, 4 * 256)) return false;
    tables_ready = true;
    return true;
}

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

/** Encode bytes with bcrypt's Base64 variant (3 bytes -> 4 chars, partial
 *  groups emit 2-3 chars, no padding). out needs (len+2)/3*4 + 1 bytes. */
void encode_b64(const uint8_t *data, size_t len, char *out) {
    size_t o = 0;
    for (size_t i = 0; i < len; i += 3) {
        int b0 = data[i];
        int b1 = i + 1 < len ? data[i + 1] : -1;
        int b2 = i + 2 < len ? data[i + 2] : -1;
        out[o++] = B64_CHARS[b0 >> 2];
        out[o++] = B64_CHARS[((b0 & 0x03) << 4) | (b1 >= 0 ? b1 >> 4 : 0)];
        if (b1 < 0) break;
        out[o++] = B64_CHARS[((b1 & 0x0f) << 2) | (b2 >= 0 ? b2 >> 6 : 0)];
        if (b2 < 0) break;
        out[o++] = B64_CHARS[b2 & 0x3f];
    }
    out[o] = 0;
}

/** Decode bcrypt Base64 into exactly `count` bytes. Returns false on bad
 *  characters or when the input carries fewer than count bytes worth of bits. */
bool decode_b64(const char *input, size_t count, uint8_t *out) {
    if (!tables_ready) { b64_index_init(); init_tables(); }
    memset(out, 0, count);
    size_t total_bits = count * 8, target = 0;
    for (const char *p = input; *p && target < total_bits; p++) {
        unsigned char c = (unsigned char)*p;
        int v = c < 128 ? b64_index[c] : -1;
        if (v < 0) return false; /* Invalid character in bcrypt base64 data */
        for (int bit = 5; bit >= 0 && target < total_bits; bit--) {
            if (v & (1 << bit)) out[target >> 3] |= (uint8_t)(1 << (7 - (target & 7)));
            target++;
        }
    }
    return target >= total_bits; /* "too short" when false */
}

/* ---------------------------------------------------------- Blowfish core --- */

/** Blowfish round function F(x) = ((S0[a] + S1[b]) ^ S2[c]) + S3[d]. */
static uint32_t bf_f(const uint32_t *S, uint32_t x) {
    return (((S[(x >> 24) & 0xff] + S[256 + ((x >> 16) & 0xff)]) ^ S[512 + ((x >> 8) & 0xff)]) +
            S[768 + (x & 0xff)]);
}

/** One Blowfish encryption of the (xl, xr) pair. */
static void encipher(const uint32_t *P, const uint32_t *S, uint32_t *xl, uint32_t *xr) {
    uint32_t l = *xl, r = *xr;
    for (int i = 0; i < 16; i++) {
        l ^= P[i];
        r ^= bf_f(S, l);
        uint32_t t = l;
        l = r;
        r = t;
    }
    uint32_t t = l;
    l = r;
    r = t;
    r ^= P[16];
    l ^= P[17];
    *xl = l;
    *xr = r;
}

/** Read 4 bytes at `offset` (wrapping around `len`) as a big-endian word —
 *  OpenBSD's stream2word. Returns the advanced offset. */
static size_t stream2word(const uint8_t *data, size_t len, size_t offset, uint32_t *word) {
    uint32_t w = 0;
    size_t j = offset;
    for (int i = 0; i < 4; i++, j++) {
        if (j >= len) j = 0;
        w = (w << 8) | data[j];
    }
    *word = w;
    return j;
}

/** Plain Blowfish key schedule (OpenBSD's expand0state): XOR `data` into P,
 *  then chain (0,0) through 521 encryptions that re-derive P and every S-box
 *  entry. Nothing is XORed into the mixing pair. */
static void expand0(uint32_t *P, uint32_t *S, const uint8_t *data, size_t data_len) {
    size_t j = 0;
    uint32_t w;
    for (int i = 0; i < 18; i++) {
        j = stream2word(data, data_len, j, &w);
        P[i] ^= w;
    }
    uint32_t l = 0, r = 0;
    for (int i = 0; i < 18; i += 2) {
        encipher(P, S, &l, &r);
        P[i] = l;
        P[i + 1] = r;
    }
    for (int box = 0; box < 4; box++) {
        for (int k = 0; k < 256; k += 2) {
            encipher(P, S, &l, &r);
            S[box * 256 + k] = l;
            S[box * 256 + k + 1] = r;
        }
    }
}

/** Blowfish key schedule seeded with salt: P is XORed with the key while the
 *  mixing pairs are salted - bcrypt's first expandstate call. */
static void expand_state(uint32_t *P, uint32_t *S, const uint8_t *salt, size_t salt_len,
                         const uint8_t *key, size_t key_len) {
    size_t j = 0;
    uint32_t w;
    for (int i = 0; i < 18; i++) {
        j = stream2word(key, key_len, j, &w);
        P[i] ^= w;
    }
    uint32_t l = 0, r = 0;
    j = 0;
    for (int i = 0; i < 18; i += 2) {
        j = stream2word(salt, salt_len, j, &w);
        l ^= w;
        j = stream2word(salt, salt_len, j, &w);
        r ^= w;
        encipher(P, S, &l, &r);
        P[i] = l;
        P[i + 1] = r;
    }
    for (int box = 0; box < 4; box++) {
        for (int k = 0; k < 256; k += 2) {
            j = stream2word(salt, salt_len, j, &w);
            l ^= w;
            j = stream2word(salt, salt_len, j, &w);
            r ^= w;
            encipher(P, S, &l, &r);
            S[box * 256 + k] = l;
            S[box * 256 + k + 1] = r;
        }
    }
}

/* -------------------------------------------------------------- key data --- */

/**
 * Derive the bcrypt key data from a password: bytes truncated to 72. A single
 * NUL terminator is appended unless truncation already reached 72 bytes - the
 * exact keying OpenBSD's bcrypt uses. Returns the key length.
 */
size_t key_data(const char *password, size_t password_len, uint8_t out[MAX_PASSWORD_BYTES]) {
    size_t truncated = password_len > MAX_PASSWORD_BYTES ? MAX_PASSWORD_BYTES : password_len;
    memcpy(out, password, truncated);
    if (truncated >= MAX_PASSWORD_BYTES) return truncated;
    out[truncated] = 0;
    return truncated + 1;
}

/** Validate a cost factor; false outside 4-31. */
bool assert_cost(int cost) { return cost >= MIN_COST && cost <= MAX_COST; }

/* --------------------------------------------------------------- hashing --- */

/** bcrypt hash parts: version prefix, cost factor, 22-char Base64 salt. */
typedef struct {
    char version[5]; /* e.g. "$2b$" */
    int cost;
    char salt[23];   /* 22 chars + NUL */
} bcrypt_info;

/** Parse a bcrypt hash string into its parts; false on malformed input. */
bool bcrypt_decode(const char *hash, bcrypt_info *info) {
    if (!hash) return false;
    while (isspace((unsigned char)*hash)) hash++;
    const char *dollar2 = strstr(hash, "$");
    if (!dollar2 || strlen(hash) < 59 + (size_t)(dollar2 - hash)) return false;
    /* $2[aby]$CC$ + 22-char salt + 31-char digest */
    if (hash[0] != '$' || hash[1] != '2') return false;
    if (hash[2] != 'a' && hash[2] != 'b' && hash[2] != 'y') return false;
    if (hash[3] != '$' || !isdigit((unsigned char)hash[4]) || !isdigit((unsigned char)hash[5]) ||
        hash[6] != '$') {
        return false;
    }
    if (!tables_ready) { b64_index_init(); init_tables(); }
    for (int i = 7; i < 7 + 53; i++) {
        unsigned char c = (unsigned char)hash[i];
        if (c >= 128 || b64_index[c] < 0) return false;
    }
    info->version[0] = '$';
    info->version[1] = '2';
    info->version[2] = hash[2];
    info->version[3] = '$';
    info->version[4] = 0;
    info->cost = (hash[4] - '0') * 10 + (hash[5] - '0');
    if (info->cost < MIN_COST || info->cost > MAX_COST) return false;
    memcpy(info->salt, hash + 7, 22);
    info->salt[22] = 0;
    return true;
}

/**
 * Compute the bcrypt digest of a password with an explicit salt and cost -
 * the shared core of hash (fresh random salt) and verify (salt parsed from
 * the hash). out receives 31 Base64 chars + NUL. The TS reference awaits the
 * event loop between round batches; C needs no such yielding.
 */
const char *bcrypt_hash_with_salt(const char *password, size_t password_len, int cost,
                                  const uint8_t salt[16], char out[32]) {
    if (!assert_cost(cost)) return "Cost factor must be an integer between 4 and 31";
    if (!tables_ready && !init_tables()) return "Failed to initialise the Blowfish tables";
    uint8_t key[MAX_PASSWORD_BYTES];
    size_t key_len = key_data(password, password_len, key);

    uint32_t P[18], S[4 * 256];
    memcpy(P, P_INIT, sizeof P);
    memcpy(S, S_INIT, sizeof S);
    expand_state(P, S, salt, 16, key, key_len);
    uint64_t rounds = 1ULL << cost;
    for (uint64_t k = 0; k < rounds; k++) {
        expand0(P, S, key, key_len);
        expand0(P, S, salt, 16);
    }

    uint32_t cdata[6];
    for (int i = 0; i < 6; i++) {
        cdata[i] = ((uint32_t)(unsigned char)MAGIC[i * 4] << 24) |
                   ((uint32_t)(unsigned char)MAGIC[i * 4 + 1] << 16) |
                   ((uint32_t)(unsigned char)MAGIC[i * 4 + 2] << 8) |
                   (uint32_t)(unsigned char)MAGIC[i * 4 + 3];
    }
    for (int i = 0; i < 64; i++) {
        for (int j = 0; j < 6; j += 2) {
            uint32_t l = cdata[j], r = cdata[j + 1];
            encipher(P, S, &l, &r);
            cdata[j] = l;
            cdata[j + 1] = r;
        }
    }
    uint8_t digest_bytes[23];
    for (int i = 0; i < 23; i++) {
        digest_bytes[i] = (uint8_t)((cdata[i >> 2] >> (24 - 8 * (i & 3))) & 0xff);
    }
    encode_b64(digest_bytes, sizeof digest_bytes, out);
    return NULL;
}

/**
 * Hash a password with bcrypt: fresh 16-byte random salt, 2^cost EksBlowfish
 * rounds (default cost 12), "$2b$" hash string into out (60 chars + NUL).
 */
const char *bcrypt_hash(const char *password, size_t password_len, int cost, char out[61]) {
    if (!password || !password_len) return "Password must not be empty";
    if (cost < 0) cost = DEFAULT_COST;
    uint8_t salt[16];
    if (RAND_bytes(salt, (int)sizeof salt) != 1) return "Random salt generation failed";
    char salt_b64[24], digest[32];
    const char *err = bcrypt_hash_with_salt(password, password_len, cost, salt, digest);
    if (err) return err;
    encode_b64(salt, sizeof salt, salt_b64);
    snprintf(out, 61, "$2b$%02d$%s%s", cost, salt_b64, digest);
    return NULL;
}

/**
 * Verify a password against a $2a$/$2b$/$2y$ bcrypt hash: recompute with the
 * hash's own salt and cost, then compare in constant time. An empty password
 * is allowed - reference implementations can hash the empty string.
 */
bool bcrypt_verify(const char *password, size_t password_len, const char *hash) {
    if (!tables_ready) { b64_index_init(); init_tables(); }
    bcrypt_info info;
    if (!bcrypt_decode(hash, &info)) return false;
    uint8_t salt[16];
    if (!decode_b64(info.salt, 16, salt)) return false;
    char digest[32];
    if (bcrypt_hash_with_salt(password, password_len, info.cost, salt, digest)) return false;
    size_t hash_len = strlen(hash);
    const char *expected = hash + (hash_len - 31);
    volatile uint8_t diff = 0;
    for (size_t i = 0; i < 31; i++) diff |= (uint8_t)digest[i] ^ (uint8_t)expected[i];
    return diff == 0;
}

/* ------------------------------------------------------------- demo main --- */

int main(void) {
    /* Known vector: cost 5 with this salt must verify against the hash built
     * here — deterministic because the salt is explicit. */
    const char *password = "hunter2";
    uint8_t salt[16];
    memset(salt, 0, sizeof salt);
    memcpy(salt, "cosmodev-salt!!", 15); /* demo salt — real code uses RAND_bytes */
    char digest[32];
    const char *err = bcrypt_hash_with_salt(password, strlen(password), 5, salt, digest);
    if (err) {
        fprintf(stderr, "error: %s\n", err);
        return 1;
    }
    char hash[64];
    char salt_b64[24];
    encode_b64(salt, sizeof salt, salt_b64);
    snprintf(hash, sizeof hash, "$2b$05$%s%s", salt_b64, digest);
    printf("hash:   %s\n", hash);
    printf("verify: %s\n", bcrypt_verify(password, strlen(password), hash) ? "true" : "false");
    printf("wrong:  %s\n", bcrypt_verify("hunter3", 7, hash) ? "true" : "false");
    return 0;
}