nt_se_suc.c

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

// Crypto1 state structure
struct Crypto1State {
    uint32_t odd, even;
};

// Function prototypes
void crypto1_init(struct Crypto1State *state, uint64_t key);
void crypto1_deinit(struct Crypto1State *state);
struct Crypto1State *crypto1_create(uint64_t key);
void crypto1_destroy(struct Crypto1State *state);
uint32_t crypto1_word(struct Crypto1State *s, uint32_t in, int is_encrypted);
uint32_t prng_successor(uint32_t x, uint32_t n);
static inline int filter(uint32_t const x);

// Parity table
const uint8_t OddByteParity[256] = {
    1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1,
    0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0,
    0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0,
    1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1,
    0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0,
    1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1,
    1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1,
    0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0,
    0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0,
    1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1,
    1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1,
    0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0,
    1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1,
    0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0,
    0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0,
    1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1
};

// Macro definitions
#define LF_POLY_ODD (0x29CE5C)
#define LF_POLY_EVEN (0x870804)
#define BIT(x, n) ((x) >> (n) & 1)
#define BEBIT(x, n) BIT(x, (n) ^ 24)
#define SWAPENDIAN(x) (x = (x >> 8 & 0xff00ff) | (x & 0xff00ff) << 8, x = x >> 16 | x << 16)

// Parity functions
static inline bool evenparity8(const uint8_t x) {
    return !OddByteParity[x];
}

static inline bool evenparity32(uint32_t x) {
    x ^= x >> 16;
    x ^= x >> 8;
    return evenparity8(x);
}

// Crypto1 functions
void crypto1_init(struct Crypto1State *state, uint64_t key) {
    if (state == NULL)
        return;
    state->odd = 0;
    state->even = 0;
    for (int i = 47; i > 0; i -= 2) {
        state->odd  = state->odd  << 1 | BIT(key, (i - 1) ^ 7);
        state->even = state->even << 1 | BIT(key, i ^ 7);
    }
}

void crypto1_deinit(struct Crypto1State *state) {
    state->odd = 0;
    state->even = 0;
}

struct Crypto1State *crypto1_create(uint64_t key) {
    struct Crypto1State *state = calloc(sizeof(*state), sizeof(uint8_t));
    if (!state) return NULL;
    crypto1_init(state, key);
    return state;
}

void crypto1_destroy(struct Crypto1State *state) {
    free(state);
}

static inline int filter(uint32_t const x) {
    uint32_t f;

    f  = 0xf22c0 >> (x       & 0xf) & 16;
    f |= 0x6c9c0 >> (x >>  4 & 0xf) &  8;
    f |= 0x3c8b0 >> (x >>  8 & 0xf) &  4;
    f |= 0x1e458 >> (x >> 12 & 0xf) &  2;
    f |= 0x0d938 >> (x >> 16 & 0xf) &  1;
    return BIT(0xEC57E80A, f);
}

uint8_t crypto1_bit(struct Crypto1State *s, uint8_t in, int is_encrypted) {
    uint32_t feedin, t;
    uint8_t ret = filter(s->odd);

    feedin  = ret & (!!is_encrypted);
    feedin ^= !!in;
    feedin ^= LF_POLY_ODD & s->odd;
    feedin ^= LF_POLY_EVEN & s->even;
    s->even = s->even << 1 | evenparity32(feedin);

    t = s->odd;
    s->odd = s->even;
    s->even = t;

    return ret;
}

uint32_t crypto1_word(struct Crypto1State *s, uint32_t in, int is_encrypted) {
    uint32_t ret = 0;
    ret |= crypto1_bit(s, BEBIT(in, 0), is_encrypted) << (24 ^ 0);
    ret |= crypto1_bit(s, BEBIT(in, 1), is_encrypted) << (24 ^ 1);
    ret |= crypto1_bit(s, BEBIT(in, 2), is_encrypted) << (24 ^ 2);
    ret |= crypto1_bit(s, BEBIT(in, 3), is_encrypted) << (24 ^ 3);
    ret |= crypto1_bit(s, BEBIT(in, 4), is_encrypted) << (24 ^ 4);
    ret |= crypto1_bit(s, BEBIT(in, 5), is_encrypted) << (24 ^ 5);
    ret |= crypto1_bit(s, BEBIT(in, 6), is_encrypted) << (24 ^ 6);
    ret |= crypto1_bit(s, BEBIT(in, 7), is_encrypted) << (24 ^ 7);
    ret |= crypto1_bit(s, BEBIT(in, 8), is_encrypted) << (24 ^ 8);
    ret |= crypto1_bit(s, BEBIT(in, 9), is_encrypted) << (24 ^ 9);
    ret |= crypto1_bit(s, BEBIT(in, 10), is_encrypted) << (24 ^ 10);
    ret |= crypto1_bit(s, BEBIT(in, 11), is_encrypted) << (24 ^ 11);
    ret |= crypto1_bit(s, BEBIT(in, 12), is_encrypted) << (24 ^ 12);
    ret |= crypto1_bit(s, BEBIT(in, 13), is_encrypted) << (24 ^ 13);
    ret |= crypto1_bit(s, BEBIT(in, 14), is_encrypted) << (24 ^ 14);
    ret |= crypto1_bit(s, BEBIT(in, 15), is_encrypted) << (24 ^ 15);
    ret |= crypto1_bit(s, BEBIT(in, 16), is_encrypted) << (24 ^ 16);
    ret |= crypto1_bit(s, BEBIT(in, 17), is_encrypted) << (24 ^ 17);
    ret |= crypto1_bit(s, BEBIT(in, 18), is_encrypted) << (24 ^ 18);
    ret |= crypto1_bit(s, BEBIT(in, 19), is_encrypted) << (24 ^ 19);
    ret |= crypto1_bit(s, BEBIT(in, 20), is_encrypted) << (24 ^ 20);
    ret |= crypto1_bit(s, BEBIT(in, 21), is_encrypted) << (24 ^ 21);
    ret |= crypto1_bit(s, BEBIT(in, 22), is_encrypted) << (24 ^ 22);
    ret |= crypto1_bit(s, BEBIT(in, 23), is_encrypted) << (24 ^ 23);
    ret |= crypto1_bit(s, BEBIT(in, 24), is_encrypted) << (24 ^ 24);
    ret |= crypto1_bit(s, BEBIT(in, 25), is_encrypted) << (24 ^ 25);
    ret |= crypto1_bit(s, BEBIT(in, 26), is_encrypted) << (24 ^ 26);
    ret |= crypto1_bit(s, BEBIT(in, 27), is_encrypted) << (24 ^ 27);
    ret |= crypto1_bit(s, BEBIT(in, 28), is_encrypted) << (24 ^ 28);
    ret |= crypto1_bit(s, BEBIT(in, 29), is_encrypted) << (24 ^ 29);
    ret |= crypto1_bit(s, BEBIT(in, 30), is_encrypted) << (24 ^ 30);
    ret |= crypto1_bit(s, BEBIT(in, 31), is_encrypted) << (24 ^ 31);
    return ret;
}

uint32_t prng_successor(uint32_t x, uint32_t n) {
    SWAPENDIAN(x);
    while (n--)
        x = x >> 1 | (x >> 16 ^ x >> 18 ^ x >> 19 ^ x >> 21) << 31;

    return SWAPENDIAN(x);
}


/** lfsr_rollback_bit
 * Rollback the shift register in order to get previous states
 */
uint8_t lfsr_rollback_bit(struct Crypto1State *s, uint32_t in, int fb) {
    int out;
    uint8_t ret;
    uint32_t t;

    s->odd &= 0xffffff;
    t = s->odd, s->odd = s->even, s->even = t;

    out = s->even & 1;
    out ^= LF_POLY_EVEN & (s->even >>= 1);
    out ^= LF_POLY_ODD & s->odd;
    out ^= !!in;
    out ^= (ret = filter(s->odd)) & (!!fb);

    s->even |= (evenparity32(out)) << 23;
    return ret;
}
/** lfsr_rollback_byte
 * Rollback the shift register in order to get previous states
 */
uint8_t lfsr_rollback_byte(struct Crypto1State *s, uint32_t in, int fb) {
    uint8_t ret = 0;
    ret |= lfsr_rollback_bit(s, BIT(in, 7), fb) << 7;
    ret |= lfsr_rollback_bit(s, BIT(in, 6), fb) << 6;
    ret |= lfsr_rollback_bit(s, BIT(in, 5), fb) << 5;
    ret |= lfsr_rollback_bit(s, BIT(in, 4), fb) << 4;
    ret |= lfsr_rollback_bit(s, BIT(in, 3), fb) << 3;
    ret |= lfsr_rollback_bit(s, BIT(in, 2), fb) << 2;
    ret |= lfsr_rollback_bit(s, BIT(in, 1), fb) << 1;
    ret |= lfsr_rollback_bit(s, BIT(in, 0), fb) << 0;
    return ret;
}
/** lfsr_rollback_word
 * Rollback the shift register in order to get previous states
 */
uint32_t lfsr_rollback_word(struct Crypto1State *s, uint32_t in, int fb) {

    uint32_t ret = 0;
    // note: xor args have been swapped because some compilers emit a warning
    // for 10^x and 2^x as possible misuses for exponentiation. No comment.
    ret |= lfsr_rollback_bit(s, BEBIT(in, 31), fb) << (24 ^ 31);
    ret |= lfsr_rollback_bit(s, BEBIT(in, 30), fb) << (24 ^ 30);
    ret |= lfsr_rollback_bit(s, BEBIT(in, 29), fb) << (24 ^ 29);
    ret |= lfsr_rollback_bit(s, BEBIT(in, 28), fb) << (24 ^ 28);
    ret |= lfsr_rollback_bit(s, BEBIT(in, 27), fb) << (24 ^ 27);
    ret |= lfsr_rollback_bit(s, BEBIT(in, 26), fb) << (24 ^ 26);
    ret |= lfsr_rollback_bit(s, BEBIT(in, 25), fb) << (24 ^ 25);
    ret |= lfsr_rollback_bit(s, BEBIT(in, 24), fb) << (24 ^ 24);

    ret |= lfsr_rollback_bit(s, BEBIT(in, 23), fb) << (24 ^ 23);
    ret |= lfsr_rollback_bit(s, BEBIT(in, 22), fb) << (24 ^ 22);
    ret |= lfsr_rollback_bit(s, BEBIT(in, 21), fb) << (24 ^ 21);
    ret |= lfsr_rollback_bit(s, BEBIT(in, 20), fb) << (24 ^ 20);
    ret |= lfsr_rollback_bit(s, BEBIT(in, 19), fb) << (24 ^ 19);
    ret |= lfsr_rollback_bit(s, BEBIT(in, 18), fb) << (24 ^ 18);
    ret |= lfsr_rollback_bit(s, BEBIT(in, 17), fb) << (24 ^ 17);
    ret |= lfsr_rollback_bit(s, BEBIT(in, 16), fb) << (24 ^ 16);

    ret |= lfsr_rollback_bit(s, BEBIT(in, 15), fb) << (24 ^ 15);
    ret |= lfsr_rollback_bit(s, BEBIT(in, 14), fb) << (24 ^ 14);
    ret |= lfsr_rollback_bit(s, BEBIT(in, 13), fb) << (24 ^ 13);
    ret |= lfsr_rollback_bit(s, BEBIT(in, 12), fb) << (24 ^ 12);
    ret |= lfsr_rollback_bit(s, BEBIT(in, 11), fb) << (24 ^ 11);
    ret |= lfsr_rollback_bit(s, BEBIT(in, 10), fb) << (24 ^ 10);
    ret |= lfsr_rollback_bit(s, BEBIT(in, 9), fb) << (24 ^ 9);
    ret |= lfsr_rollback_bit(s, BEBIT(in, 8), fb) << (24 ^ 8);

    ret |= lfsr_rollback_bit(s, BEBIT(in, 7), fb) << (24 ^ 7);
    ret |= lfsr_rollback_bit(s, BEBIT(in, 6), fb) << (24 ^ 6);
    ret |= lfsr_rollback_bit(s, BEBIT(in, 5), fb) << (24 ^ 5);
    ret |= lfsr_rollback_bit(s, BEBIT(in, 4), fb) << (24 ^ 4);
    ret |= lfsr_rollback_bit(s, BEBIT(in, 3), fb) << (24 ^ 3);
    ret |= lfsr_rollback_bit(s, BEBIT(in, 2), fb) << (24 ^ 2);
    ret |= lfsr_rollback_bit(s, BEBIT(in, 1), fb) << (24 ^ 1);
    ret |= lfsr_rollback_bit(s, BEBIT(in, 0), fb) << (24 ^ 0);
    return ret;
}

void print_crypto1_state(struct Crypto1State *state) {
    printf("LFSR state: odd = %08x, even = %08x\n", state->odd, state->even);
}


uint32_t hex_to_uint32(const char *hex) {
    uint32_t val;
    sscanf(hex, "%x", &val);
    return val;
}

uint64_t hex_to_uint64(const char *hex) {
    uint64_t val;
    sscanf(hex, "%lx", &val);
    return val;
}

int main(int argc, char *argv[]) {
    if (argc != 5) {
        fprintf(stderr, "Usage: %s <key> <uid> <nt> <nt_enc>\n", argv[0]);
        return 1;
    }

    uint64_t key = hex_to_uint64(argv[1]);
    uint32_t uid = hex_to_uint32(argv[2]);
    uint32_t nt = hex_to_uint32(argv[3]);
    uint32_t nt_enc = hex_to_uint32(argv[4]);

    printf("Inputs:\n");
    printf("Key: %012lx\n", key);
    printf("nt: %08x\n", nt);
    printf("uid: %08x\n", uid);
    printf("nt_enc: %08x\n", nt_enc);
    int found_dist = 0;
    int dist_a = 0;
    int dist_b = 0;

    for (int i = 0; i < 65535; i++) {
        struct Crypto1State *state_tmp = crypto1_create(key);
        uint32_t nth_successor = prng_successor(nt, i);
        if ((nth_successor ^ crypto1_word(state_tmp, uid ^ nth_successor, 0)) == nt_enc) {
            printf("nt_enc (plain): %08x\n", nth_successor);
            printf("dist from nt: %i\n", i);
            dist_a = i;
            found_dist++;
            printf("ks: %08x\n", nth_successor ^ nt_enc);
            break;
        }
        crypto1_destroy(state_tmp);
    }
    for (int i = 0; i < 65535; i++) {
        struct Crypto1State *state_tmp = crypto1_create(key);
        uint32_t nth_successor = prng_successor(0x0000aaaa, i);
        if ((nth_successor ^ crypto1_word(state_tmp, uid ^ nth_successor, 0)) == nt_enc) {
            printf("dist from 0: %i\n", i);
            dist_b = i;
            found_dist++;
            break;
        }
        crypto1_destroy(state_tmp);
    }
    if (found_dist == 2) {
        printf("offset: %i\n", dist_a-dist_b);
    } else {
        printf("error: could not find dist\n");
        return 1;
    }

    return 0;
}