/*
 * seedsearch — find a seed whose first P-256 candidate is out of range.
 *
 * PROTOCOL.md requires rejection sampling mod n when deriving a P-256 scalar
 * from a seed, and discussion #6 requires a vector that actually exercises
 * the rejection branch: "pin a seed that requires a rejection, or the branch
 * goes untested". A rejection happens with probability about 2^-32, so no
 * seed anybody picks by hand will ever hit it. This searches for one.
 *
 * The search space is deliberately reproducible rather than random:
 *
 *     seed_k = "contra/v1/vector-search!" || u64be(k)      (32 bytes)
 *
 * so the witness is a single number: the vector file pins k, and anyone can
 * rebuild the seed from it without trusting this program. It also makes the
 * seed visibly generated rather than plausibly a real key. (Threads race, so
 * the k reported is a witness, not necessarily the smallest one.)
 *
 * A hit is a k where OS2IP(candidate_0) is 0 or >= n, with
 *
 *     candidate_0 = HKDF-SHA-256(IKM = seed_k, salt = "",
 *                                info = "contra/v1/ec-p256" || 0x00)
 *
 * This tool is a helper, not an authority. Whatever it finds is re-derived
 * and re-checked by gen.c against OpenSSL before it reaches the vector file.
 *
 * Build: make seedsearch      Run: ./seedsearch [threads]
 */
#define OPENSSL_SUPPRESS_DEPRECATED 1

#include <inttypes.h>
#include <pthread.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <openssl/sha.h>

#define SEED_PREFIX "contra/v1/vector-search!" /* 24 bytes, no NUL */
#define SEED_PREFIX_LEN 24
#define EC_LABEL "contra/v1/ec-p256"
#define EC_LABEL_LEN 17

/* P-256 group order n, big-endian. */
static const unsigned char P256_N[32] = {
    0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00, 0xff, 0xff, 0xff,
    0xff, 0xff, 0xff, 0xff, 0xff, 0xbc, 0xe6, 0xfa, 0xad, 0xa7, 0x17,
    0x9e, 0x84, 0xf3, 0xb9, 0xca, 0xc2, 0xfc, 0x63, 0x25, 0x51};

/* HMAC-SHA-256 over a key of at most 64 bytes. Enough for this search. */
static void hmac_sha256(const unsigned char *key, size_t keylen,
                        const unsigned char *msg, size_t msglen,
                        unsigned char out[32]) {
    unsigned char ipad[64], opad[64], inner[32];
    SHA256_CTX c;
    size_t i;

    memset(ipad, 0x36, sizeof ipad);
    memset(opad, 0x5c, sizeof opad);
    for (i = 0; i < keylen; i++) {
        ipad[i] ^= key[i];
        opad[i] ^= key[i];
    }

    SHA256_Init(&c);
    SHA256_Update(&c, ipad, sizeof ipad);
    SHA256_Update(&c, msg, msglen);
    SHA256_Final(inner, &c);

    SHA256_Init(&c);
    SHA256_Update(&c, opad, sizeof opad);
    SHA256_Update(&c, inner, sizeof inner);
    SHA256_Final(out, &c);
}

/* True when the candidate is not a usable P-256 scalar: zero, or >= n. */
static int out_of_range(const unsigned char c[32]) {
    int i, nonzero = 0;

    for (i = 0; i < 32; i++)
        if (c[i]) {
            nonzero = 1;
            break;
        }
    if (!nonzero) return 1;

    for (i = 0; i < 32; i++) {
        if (c[i] < P256_N[i]) return 0;
        if (c[i] > P256_N[i]) return 1;
    }
    return 1; /* exactly n */
}

static volatile int g_found = 0;
static uint64_t g_found_k = 0;
static pthread_mutex_t g_mu = PTHREAD_MUTEX_INITIALIZER;

struct span {
    uint64_t start, stride, limit;
};

static void *worker(void *arg) {
    struct span *s = arg;
    unsigned char seed[32], prk[32], info[EC_LABEL_LEN + 2], cand[32];
    unsigned char zero_salt[32];
    uint64_t k;

    memset(zero_salt, 0, sizeof zero_salt);
    memcpy(seed, SEED_PREFIX, SEED_PREFIX_LEN);
    memcpy(info, EC_LABEL, EC_LABEL_LEN);
    info[EC_LABEL_LEN] = 0x00;     /* counter i = 0 */
    info[EC_LABEL_LEN + 1] = 0x01; /* HKDF-Expand block counter T(1) */

    for (k = s->start; k < s->limit && !g_found; k += s->stride) {
        int i;
        for (i = 0; i < 8; i++) seed[24 + i] = (unsigned char)(k >> (56 - 8 * i));

        /* HKDF-Extract with a zero-length salt: RFC 5869 substitutes
         * HashLen zero bytes as the HMAC key. */
        hmac_sha256(zero_salt, sizeof zero_salt, seed, sizeof seed, prk);
        /* HKDF-Expand, first and only 32-byte block. */
        hmac_sha256(prk, sizeof prk, info, sizeof info, cand);

        /* Cheap filter first: a candidate >= n must open 0xFFFFFFFF. */
        if (cand[0] != 0xff || cand[1] != 0xff || cand[2] != 0xff ||
            cand[3] != 0xff)
            continue;

        if (out_of_range(cand)) {
            pthread_mutex_lock(&g_mu);
            if (!g_found || k < g_found_k) g_found_k = k;
            g_found = 1;
            pthread_mutex_unlock(&g_mu);
            return NULL;
        }
    }
    return NULL;
}

int main(int argc, char **argv) {
    long nthreads = (argc > 1) ? strtol(argv[1], NULL, 10) : 8;
    pthread_t *th;
    struct span *spans;
    long i;

    if (nthreads < 1) nthreads = 1;
    th = calloc((size_t)nthreads, sizeof *th);
    spans = calloc((size_t)nthreads, sizeof *spans);
    if (!th || !spans) return 1;

    for (i = 0; i < nthreads; i++) {
        spans[i].start = (uint64_t)i;
        spans[i].stride = (uint64_t)nthreads;
        spans[i].limit = UINT64_C(1) << 40;
        pthread_create(&th[i], NULL, worker, &spans[i]);
    }
    for (i = 0; i < nthreads; i++) pthread_join(th[i], NULL);

    if (!g_found) {
        fprintf(stderr, "seedsearch: no rejecting seed found\n");
        return 1;
    }
    printf("%" PRIu64 "\n", g_found_k);
    return 0;
}