[proxmark3-svn] / common / crapto1 / crapto1.c

/*  crapto1.c

	This program is free software; you can redistribute it and/or
	modify it under the terms of the GNU General Public License
	as published by the Free Software Foundation; either version 2
	of the License, or (at your option) any later version.

	This program is distributed in the hope that it will be useful,
	but WITHOUT ANY WARRANTY; without even the implied warranty of
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
	GNU General Public License for more details.

	You should have received a copy of the GNU General Public License
	along with this program; if not, write to the Free Software
	Foundation, Inc., 51 Franklin Street, Fifth Floor,
	Boston, MA  02110-1301, US$

    Copyright (C) 2008-2014 bla <blapost@gmail.com>
*/
#include "crapto1.h"

#include <stdlib.h>
#include "parity.h"

#if !defined LOWMEM && defined __GNUC__
static uint8_t filterlut[1 << 20];
static void __attribute__((constructor)) fill_lut()
{
		uint32_t i;
		for(i = 0; i < 1 << 20; ++i)
				filterlut[i] = filter(i);
}
#define filter(x) (filterlut[(x) & 0xfffff])
#endif


typedef struct bucket {
	uint32_t *head;
	uint32_t *bp;
} bucket_t;

typedef bucket_t bucket_array_t[2][0x100];

typedef struct bucket_info {
	struct {
		uint32_t *head, *tail;
		} bucket_info[2][0x100];
		uint32_t numbuckets;
	} bucket_info_t;


static void bucket_sort_intersect(uint32_t* const estart, uint32_t* const estop,
								  uint32_t* const ostart, uint32_t* const ostop,
								  bucket_info_t *bucket_info, bucket_array_t bucket)
{
	uint32_t *p1, *p2;
	uint32_t *start[2];
	uint32_t *stop[2];

	start[0] = estart;
	stop[0] = estop;
	start[1] = ostart;
	stop[1] = ostop;

	// init buckets to be empty
	for (uint32_t i = 0; i < 2; i++) {
		for (uint32_t j = 0x00; j <= 0xff; j++) {
			bucket[i][j].bp = bucket[i][j].head;
		}
	}

	// sort the lists into the buckets based on the MSB (contribution bits)
	for (uint32_t i = 0; i < 2; i++) {
		for (p1 = start[i]; p1 <= stop[i]; p1++) {
			uint32_t bucket_index = (*p1 & 0xff000000) >> 24;
			*(bucket[i][bucket_index].bp++) = *p1;
		}
	}


	// write back intersecting buckets as sorted list.
	// fill in bucket_info with head and tail of the bucket contents in the list and number of non-empty buckets.
	uint32_t nonempty_bucket;
	for (uint32_t i = 0; i < 2; i++) {
		p1 = start[i];
		nonempty_bucket = 0;
		for (uint32_t j = 0x00; j <= 0xff; j++) {
			if (bucket[0][j].bp != bucket[0][j].head && bucket[1][j].bp != bucket[1][j].head) { // non-empty intersecting buckets only
				bucket_info->bucket_info[i][nonempty_bucket].head = p1;
				for (p2 = bucket[i][j].head; p2 < bucket[i][j].bp; *p1++ = *p2++);
				bucket_info->bucket_info[i][nonempty_bucket].tail = p1 - 1;
				nonempty_bucket++;
			}
		}
		bucket_info->numbuckets = nonempty_bucket;
		}
}
/** binsearch
 * Binary search for the first occurence of *stop's MSB in sorted [start,stop]
 */
static inline uint32_t* binsearch(uint32_t *start, uint32_t *stop)
{
	uint32_t mid, val = *stop & 0xff000000;
	while(start != stop)
		if(start[mid = (stop - start) >> 1] > val)
			stop = &start[mid];
		else
			start += mid + 1;

	return start;
}

/** update_contribution
 * helper, calculates the partial linear feedback contributions and puts in MSB
 */
static inline void
update_contribution(uint32_t *item, const uint32_t mask1, const uint32_t mask2)
{
	uint32_t p = *item >> 25;

	p = p << 1 | evenparity32(*item & mask1);
	p = p << 1 | evenparity32(*item & mask2);
	*item = p << 24 | (*item & 0xffffff);
}

/** extend_table
 * using a bit of the keystream extend the table of possible lfsr states
 */
static inline void
extend_table(uint32_t *tbl, uint32_t **end, int bit, int m1, int m2, uint32_t in)
{
	in <<= 24;
	for(*tbl <<= 1; tbl <= *end; *++tbl <<= 1)
		if(filter(*tbl) ^ filter(*tbl | 1)) {
			*tbl |= filter(*tbl) ^ bit;
			update_contribution(tbl, m1, m2);
			*tbl ^= in;
		} else if(filter(*tbl) == bit) {
			*++*end = tbl[1];
			tbl[1] = tbl[0] | 1;
			update_contribution(tbl, m1, m2);
			*tbl++ ^= in;
			update_contribution(tbl, m1, m2);
			*tbl ^= in;
		} else
			*tbl-- = *(*end)--;
}
/** extend_table_simple
 * using a bit of the keystream extend the table of possible lfsr states
 */
static inline void extend_table_simple(uint32_t *tbl, uint32_t **end, int bit)
{
	for(*tbl <<= 1; tbl <= *end; *++tbl <<= 1)
		if(filter(*tbl) ^ filter(*tbl | 1))
			*tbl |= filter(*tbl) ^ bit;
		else if(filter(*tbl) == bit) {
			*++*end = *++tbl;
			*tbl = tbl[-1] | 1;

		} else
			*tbl-- = *(*end)--;
}


/** recover
 * recursively narrow down the search space, 4 bits of keystream at a time
 */
static struct Crypto1State*
recover(uint32_t *o_head, uint32_t *o_tail, uint32_t oks,
	uint32_t *e_head, uint32_t *e_tail, uint32_t eks, int rem,
	struct Crypto1State *sl, uint32_t in, bucket_array_t bucket)
{
	uint32_t *o, *e, i;
	bucket_info_t bucket_info;

	if(rem == -1) {
		for(e = e_head; e <= e_tail; ++e) {
			*e = *e << 1 ^ evenparity32(*e & LF_POLY_EVEN) ^ !!(in & 4);
			for(o = o_head; o <= o_tail; ++o, ++sl) {
				sl->even = *o;
				sl->odd = *e ^ evenparity32(*o & LF_POLY_ODD);
				sl[1].odd = sl[1].even = 0;
			}
		}
		return sl;
	}

	for(i = 0; i < 4 && rem--; i++) {
		oks >>= 1;
		eks >>= 1;
		in >>= 2;
		extend_table(o_head, &o_tail, oks & 1, LF_POLY_EVEN << 1 | 1,
			     LF_POLY_ODD << 1, 0);
		if(o_head > o_tail)
			return sl;

		extend_table(e_head, &e_tail, eks & 1, LF_POLY_ODD,
			     LF_POLY_EVEN << 1 | 1, in & 3);
		if(e_head > e_tail)
			return sl;
	}
	bucket_sort_intersect(e_head, e_tail, o_head, o_tail, &bucket_info, bucket);

	for (int i = bucket_info.numbuckets - 1; i >= 0; i--) {
		sl = recover(bucket_info.bucket_info[1][i].head, bucket_info.bucket_info[1][i].tail, oks,
					 bucket_info.bucket_info[0][i].head, bucket_info.bucket_info[0][i].tail, eks,
					 rem, sl, in, bucket);
	}

	return sl;
}
/** lfsr_recovery
 * recover the state of the lfsr given 32 bits of the keystream
 * additionally you can use the in parameter to specify the value
 * that was fed into the lfsr at the time the keystream was generated
 */
struct Crypto1State* lfsr_recovery32(uint32_t ks2, uint32_t in)
{
	struct Crypto1State *statelist;
	uint32_t *odd_head = 0, *odd_tail = 0, oks = 0;
	uint32_t *even_head = 0, *even_tail = 0, eks = 0;
	int i;

	for(i = 31; i >= 0; i -= 2)
		oks = oks << 1 | BEBIT(ks2, i);
	for(i = 30; i >= 0; i -= 2)
 		eks = eks << 1 | BEBIT(ks2, i);

	odd_head = odd_tail = malloc(sizeof(uint32_t) << 21);
	even_head = even_tail = malloc(sizeof(uint32_t) << 21);
	statelist =  malloc(sizeof(struct Crypto1State) << 18);
	if(!odd_tail-- || !even_tail-- || !statelist) {
		free(statelist);
		statelist = 0;
		goto out;
	}
	statelist->odd = statelist->even = 0;

	// allocate memory for out of place bucket_sort
	bucket_array_t bucket;
	for (uint32_t i = 0; i < 2; i++)
		for (uint32_t j = 0; j <= 0xff; j++) {
			bucket[i][j].head = malloc(sizeof(uint32_t)<<14);
			if (!bucket[i][j].head) {
				goto out;
			}
		}


	for(i = 1 << 20; i >= 0; --i) {
		if(filter(i) == (oks & 1))
			*++odd_tail = i;
		if(filter(i) == (eks & 1))
			*++even_tail = i;
	}

	for(i = 0; i < 4; i++) {
		extend_table_simple(odd_head,  &odd_tail, (oks >>= 1) & 1);
		extend_table_simple(even_head, &even_tail, (eks >>= 1) & 1);
	}

	in = (in >> 16 & 0xff) | (in << 16) | (in & 0xff00);
	recover(odd_head, odd_tail, oks,
		even_head, even_tail, eks, 11, statelist, in << 1, bucket);

out:
	free(odd_head);
	free(even_head);
	for (uint32_t i = 0; i < 2; i++)
		for (uint32_t j = 0; j <= 0xff; j++)
			free(bucket[i][j].head);

	return statelist;
}

static const uint32_t S1[] = {     0x62141, 0x310A0, 0x18850, 0x0C428, 0x06214,
	0x0310A, 0x85E30, 0xC69AD, 0x634D6, 0xB5CDE, 0xDE8DA, 0x6F46D, 0xB3C83,
	0x59E41, 0xA8995, 0xD027F, 0x6813F, 0x3409F, 0x9E6FA};
static const uint32_t S2[] = {  0x3A557B00, 0x5D2ABD80, 0x2E955EC0, 0x174AAF60,
	0x0BA557B0, 0x05D2ABD8, 0x0449DE68, 0x048464B0, 0x42423258, 0x278192A8,
	0x156042D0, 0x0AB02168, 0x43F89B30, 0x61FC4D98, 0x765EAD48, 0x7D8FDD20,
	0x7EC7EE90, 0x7F63F748, 0x79117020};
static const uint32_t T1[] = {
	0x4F37D, 0x279BE, 0x97A6A, 0x4BD35, 0x25E9A, 0x12F4D, 0x097A6, 0x80D66,
	0xC4006, 0x62003, 0xB56B4, 0x5AB5A, 0xA9318, 0xD0F39, 0x6879C, 0xB057B,
	0x582BD, 0x2C15E, 0x160AF, 0x8F6E2, 0xC3DC4, 0xE5857, 0x72C2B, 0x39615,
	0x98DBF, 0xC806A, 0xE0680, 0x70340, 0x381A0, 0x98665, 0x4C332, 0xA272C};
static const uint32_t T2[] = {  0x3C88B810, 0x5E445C08, 0x2982A580, 0x14C152C0,
	0x4A60A960, 0x253054B0, 0x52982A58, 0x2FEC9EA8, 0x1156C4D0, 0x08AB6268,
	0x42F53AB0, 0x217A9D58, 0x161DC528, 0x0DAE6910, 0x46D73488, 0x25CB11C0,
	0x52E588E0, 0x6972C470, 0x34B96238, 0x5CFC3A98, 0x28DE96C8, 0x12CFC0E0,
	0x4967E070, 0x64B3F038, 0x74F97398, 0x7CDC3248, 0x38CE92A0, 0x1C674950,
	0x0E33A4A8, 0x01B959D0, 0x40DCACE8, 0x26CEDDF0};
static const uint32_t C1[] = { 0x846B5, 0x4235A, 0x211AD};
static const uint32_t C2[] = { 0x1A822E0, 0x21A822E0, 0x21A822E0};
/** Reverse 64 bits of keystream into possible cipher states
 * Variation mentioned in the paper. Somewhat optimized version
 */
struct Crypto1State* lfsr_recovery64(uint32_t ks2, uint32_t ks3)
{
	struct Crypto1State *statelist, *sl;
	uint8_t oks[32], eks[32], hi[32];
	uint32_t low = 0,  win = 0;
	uint32_t *tail, table[1 << 16];
	int i, j;

	sl = statelist = malloc(sizeof(struct Crypto1State) << 4);
	if(!sl)
		return 0;
	sl->odd = sl->even = 0;

	for(i = 30; i >= 0; i -= 2) {
		oks[i >> 1] = BEBIT(ks2, i);
		oks[16 + (i >> 1)] = BEBIT(ks3, i);
	}
	for(i = 31; i >= 0; i -= 2) {
		eks[i >> 1] = BEBIT(ks2, i);
		eks[16 + (i >> 1)] = BEBIT(ks3, i);
	}

	for(i = 0xfffff; i >= 0; --i) {
		if (filter(i) != oks[0])
			continue;

		*(tail = table) = i;
		for(j = 1; tail >= table && j < 29; ++j)
			extend_table_simple(table, &tail, oks[j]);

		if(tail < table)
			continue;

		for(j = 0; j < 19; ++j)
			low = low << 1 | evenparity32(i & S1[j]);
		for(j = 0; j < 32; ++j)
			hi[j] = evenparity32(i & T1[j]);

		for(; tail >= table; --tail) {
			for(j = 0; j < 3; ++j) {
				*tail = *tail << 1;
				*tail |= evenparity32((i & C1[j]) ^ (*tail & C2[j]));
				if(filter(*tail) != oks[29 + j])
					goto continue2;
			}

			for(j = 0; j < 19; ++j)
				win = win << 1 | evenparity32(*tail & S2[j]);

			win ^= low;
			for(j = 0; j < 32; ++j) {
				win = win << 1 ^ hi[j] ^ evenparity32(*tail & T2[j]);
				if(filter(win) != eks[j])
					goto continue2;
			}

			*tail = *tail << 1 | evenparity32(LF_POLY_EVEN & *tail);
			sl->odd = *tail ^ evenparity32(LF_POLY_ODD & win);
			sl->even = win;
			++sl;
			sl->odd = sl->even = 0;
			continue2:;
		}
	}
	return statelist;
}

/** 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)
{
	int i, ret=0;
	for (i = 7; i >= 0; --i)
		ret |= lfsr_rollback_bit(s, BIT(in, i), fb) << i;
	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)
{
	int i;
	uint32_t ret = 0;
	for (i = 31; i >= 0; --i)
		ret |= lfsr_rollback_bit(s, BEBIT(in, i), fb) << (i ^ 24);
	return ret;
}

/** nonce_distance
 * x,y valid tag nonces, then prng_successor(x, nonce_distance(x, y)) = y
 */
static uint16_t *dist = 0;
int nonce_distance(uint32_t from, uint32_t to)
{
	uint16_t x, i;
	if(!dist) {
		dist = malloc(2 << 16);
		if(!dist)
			return -1;
		for (x = i = 1; i; ++i) {
			dist[(x & 0xff) << 8 | x >> 8] = i;
			x = x >> 1 | (x ^ x >> 2 ^ x >> 3 ^ x >> 5) << 15;
		}
	}
	return (65535 + dist[to >> 16] - dist[from >> 16]) % 65535;
}


static uint32_t fastfwd[2][8] = {
	{ 0, 0x4BC53, 0xECB1, 0x450E2, 0x25E29, 0x6E27A, 0x2B298, 0x60ECB},
	{ 0, 0x1D962, 0x4BC53, 0x56531, 0xECB1, 0x135D3, 0x450E2, 0x58980}};
/** lfsr_prefix_ks
 *
 * Is an exported helper function from the common prefix attack
 * Described in the "dark side" paper. It returns an -1 terminated array
 * of possible partial(21 bit) secret state.
 * The required keystream(ks) needs to contain the keystream that was used to
 * encrypt the NACK which is observed when varying only the 3 last bits of Nr
 * only correct iff [NR_3] ^ NR_3 does not depend on Nr_3
 */
uint32_t *lfsr_prefix_ks(uint8_t ks[8], int isodd)
{
	uint32_t c, entry, *candidates = malloc(4 << 10);
	int i, size = 0, good;
	
	if(!candidates)
		return 0;

	for(i = 0; i < 1 << 21; ++i) {
		for(c = 0, good = 1; good && c < 8; ++c) {
			entry = i ^ fastfwd[isodd][c];
			good &= (BIT(ks[c], isodd) == filter(entry >> 1));
			good &= (BIT(ks[c], isodd + 2) == filter(entry));
		}
		if(good)
			candidates[size++] = i;
	}
	
	candidates[size] = -1;

	return candidates;
}

/** check_pfx_parity
 * helper function which eliminates possible secret states using parity bits
 */
static struct Crypto1State*
check_pfx_parity(uint32_t prefix, uint32_t rresp, uint8_t parities[8][8],
          	uint32_t odd, uint32_t even, struct Crypto1State* sl, uint32_t no_par)
{
	uint32_t ks1, nr, ks2, rr, ks3, c, good = 1;

	for(c = 0; good && c < 8; ++c) {
		sl->odd = odd ^ fastfwd[1][c];
		sl->even = even ^ fastfwd[0][c];

		lfsr_rollback_bit(sl, 0, 0);
		lfsr_rollback_bit(sl, 0, 0);

		ks3 = lfsr_rollback_bit(sl, 0, 0);
		ks2 = lfsr_rollback_word(sl, 0, 0);
		ks1 = lfsr_rollback_word(sl, prefix | c << 5, 1);

		if (no_par)
			break;

		nr = ks1 ^ (prefix | c << 5);
		rr = ks2 ^ rresp;

		good &= evenparity32(nr & 0x000000ff) ^ parities[c][3] ^ BIT(ks2, 24);
		good &= evenparity32(rr & 0xff000000) ^ parities[c][4] ^ BIT(ks2, 16);
		good &= evenparity32(rr & 0x00ff0000) ^ parities[c][5] ^ BIT(ks2,  8);
		good &= evenparity32(rr & 0x0000ff00) ^ parities[c][6] ^ BIT(ks2,  0);
		good &= evenparity32(rr & 0x000000ff) ^ parities[c][7] ^ ks3;
	}

	return sl + good;
}


/** lfsr_common_prefix
 * Implentation of the common prefix attack.
 */
struct Crypto1State*
lfsr_common_prefix(uint32_t pfx, uint32_t rr, uint8_t ks[8], uint8_t par[8][8], uint32_t no_par)
{
	struct Crypto1State *statelist, *s;
	uint32_t *odd, *even, *o, *e, top;

	odd = lfsr_prefix_ks(ks, 1);
	even = lfsr_prefix_ks(ks, 0);

	s = statelist = malloc((sizeof *statelist) << 22); // was << 20. Need more for no_par special attack. Enough???
	if(!s || !odd || !even) {
		free(statelist);
		statelist = 0;
                goto out;
	}

	for(o = odd; *o + 1; ++o)
		for(e = even; *e + 1; ++e)
			for(top = 0; top < 64; ++top) {
				*o += 1 << 21;
				*e += (!(top & 7) + 1) << 21;
				s = check_pfx_parity(pfx, rr, par, *o, *e, s, no_par);
			}

	s->odd = s->even = 0;
out:
	free(odd);
	free(even);
	return statelist;
}
Commit	Line	Data
33443e7c	1	/* crapto1.c
	2
	3	This program is free software; you can redistribute it and/or
	4	modify it under the terms of the GNU General Public License
	5	as published by the Free Software Foundation; either version 2
	6	of the License, or (at your option) any later version.
	7
	8	This program is distributed in the hope that it will be useful,
	9	but WITHOUT ANY WARRANTY; without even the implied warranty of
	10	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	11	GNU General Public License for more details.
	12
	13	You should have received a copy of the GNU General Public License
	14	along with this program; if not, write to the Free Software
	15	Foundation, Inc., 51 Franklin Street, Fifth Floor,
	16	Boston, MA 02110-1301, US$
	17
0ca9bc0e	18	Copyright (C) 2008-2014 bla <blapost@gmail.com>
33443e7c	19	*/
33443e7c	20	#include "crapto1.h"
1f065e1d	21
33443e7c	22	#include <stdlib.h>
1f065e1d	23	#include "parity.h"
33443e7c	24
	25	#if !defined LOWMEM && defined __GNUC__
	26	static uint8_t filterlut[1 << 20];
	27	static void __attribute__((constructor)) fill_lut()
	28	{
	29	uint32_t i;
	30	for(i = 0; i < 1 << 20; ++i)
	31	filterlut[i] = filter(i);
	32	}
	33	#define filter(x) (filterlut[(x) & 0xfffff])
	34	#endif
	35
	36
	37
	38	typedef struct bucket {
	39	uint32_t *head;
	40	uint32_t *bp;
	41	} bucket_t;
	42
	43	typedef bucket_t bucket_array_t[2][0x100];
	44
	45	typedef struct bucket_info {
	46	struct {
	47	uint32_t head, tail;
	48	} bucket_info[2][0x100];
	49	uint32_t numbuckets;
	50	} bucket_info_t;
	51
	52
	53	static void bucket_sort_intersect(uint32_t* const estart, uint32_t* const estop,
	54	uint32_t* const ostart, uint32_t* const ostop,
	55	bucket_info_t *bucket_info, bucket_array_t bucket)
	56	{
	57	uint32_t p1, p2;
	58	uint32_t *start[2];
	59	uint32_t *stop[2];
	60
	61	start[0] = estart;
	62	stop[0] = estop;
	63	start[1] = ostart;
	64	stop[1] = ostop;
	65
	66	// init buckets to be empty
	67	for (uint32_t i = 0; i < 2; i++) {
	68	for (uint32_t j = 0x00; j <= 0xff; j++) {
	69	bucket[i][j].bp = bucket[i][j].head;
	70	}
	71	}
	72
	73	// sort the lists into the buckets based on the MSB (contribution bits)
	74	for (uint32_t i = 0; i < 2; i++) {
	75	for (p1 = start[i]; p1 <= stop[i]; p1++) {
	76	uint32_t bucket_index = (*p1 & 0xff000000) >> 24;
	77	(bucket[i][bucket_index].bp++) = p1;
	78	}
	79	}
	80
	81
	82	// write back intersecting buckets as sorted list.
	83	// fill in bucket_info with head and tail of the bucket contents in the list and number of non-empty buckets.
	84	uint32_t nonempty_bucket;
	85	for (uint32_t i = 0; i < 2; i++) {
	86	p1 = start[i];
	87	nonempty_bucket = 0;
88	for (uint32_t j = 0x00; j <= 0xff; j++) {
89	if (bucket[0][j].bp != bucket[0][j].head && bucket[1][j].bp != bucket[1][j].head) { // non-empty intersecting buckets only
90	bucket_info->bucket_info[i][nonempty_bucket].head = p1;
91	for (p2 = bucket[i][j].head; p2 < bucket[i][j].bp; p1++ = p2++);
92	bucket_info->bucket_info[i][nonempty_bucket].tail = p1 - 1;
93	nonempty_bucket++;
94	}
95	}
96	bucket_info->numbuckets = nonempty_bucket;
97	}
98	}
33443e7c	99	/** binsearch
	100	* Binary search for the first occurence of *stop's MSB in sorted [start,stop]
	101	*/
0ca9bc0e	102	static inline uint32_t* binsearch(uint32_t start, uint32_t stop)
33443e7c	103	{
	104	uint32_t mid, val = *stop & 0xff000000;
	105	while(start != stop)
	106	if(start[mid = (stop - start) >> 1] > val)
	107	stop = &start[mid];
	108	else
	109	start += mid + 1;
	110
	111	return start;
	112	}
	113
	114	/** update_contribution
	115	* helper, calculates the partial linear feedback contributions and puts in MSB
	116	*/
	117	static inline void
	118	update_contribution(uint32_t *item, const uint32_t mask1, const uint32_t mask2)
	119	{
	120	uint32_t p = *item >> 25;
	121
1f065e1d	122	p = p << 1 \| evenparity32(*item & mask1);
1f065e1d	123	p = p << 1 \| evenparity32(*item & mask2);
33443e7c	124	item = p << 24 \| (item & 0xffffff);
	125	}
	126
	127	/** extend_table
	128	* using a bit of the keystream extend the table of possible lfsr states
	129	*/
	130	static inline void
	131	extend_table(uint32_t tbl, uint32_t *end, int bit, int m1, int m2, uint32_t in)
	132	{
	133	in <<= 24;
0ca9bc0e	134	for(tbl <<= 1; tbl <= end; *++tbl <<= 1)
	135	if(filter(tbl) ^ filter(tbl \| 1)) {
	136	tbl \|= filter(tbl) ^ bit;
	137	update_contribution(tbl, m1, m2);
	138	*tbl ^= in;
	139	} else if(filter(*tbl) == bit) {
	140	++end = tbl[1];
	141	tbl[1] = tbl[0] \| 1;
	142	update_contribution(tbl, m1, m2);
	143	*tbl++ ^= in;
	144	update_contribution(tbl, m1, m2);
	145	*tbl ^= in;
	146	} else
	147	tbl-- = (*end)--;
33443e7c	148	}
33443e7c	149	/** extend_table_simple
	150	* using a bit of the keystream extend the table of possible lfsr states
	151	*/
0ca9bc0e	152	static inline void extend_table_simple(uint32_t tbl, uint32_t *end, int bit)
33443e7c	153	{
33443e7c	154	for(tbl <<= 1; tbl <= end; *++tbl <<= 1)
0ca9bc0e	155	if(filter(tbl) ^ filter(tbl \| 1))
33443e7c	156	tbl \|= filter(tbl) ^ bit;
0ca9bc0e	157	else if(filter(*tbl) == bit) {
33443e7c	158	++end = *++tbl;
33443e7c	159	*tbl = tbl[-1] \| 1;
0ca9bc0e	160
0ca9bc0e	161	} else
33443e7c	162	tbl-- = (*end)--;
	163	}
	164
	165
	166	/** recover
	167	* recursively narrow down the search space, 4 bits of keystream at a time
	168	*/
	169	static struct Crypto1State*
	170	recover(uint32_t o_head, uint32_t o_tail, uint32_t oks,
	171	uint32_t e_head, uint32_t e_tail, uint32_t eks, int rem,
	172	struct Crypto1State *sl, uint32_t in, bucket_array_t bucket)
	173	{
0ca9bc0e	174	uint32_t o, e, i;
33443e7c	175	bucket_info_t bucket_info;
	176
	177	if(rem == -1) {
	178	for(e = e_head; e <= e_tail; ++e) {
1f065e1d	179	e = e << 1 ^ evenparity32(*e & LF_POLY_EVEN) ^ !!(in & 4);
33443e7c	180	for(o = o_head; o <= o_tail; ++o, ++sl) {
33443e7c	181	sl->even = *o;
1f065e1d	182	sl->odd = e ^ evenparity32(o & LF_POLY_ODD);
0ca9bc0e	183	sl[1].odd = sl[1].even = 0;
33443e7c	184	}
33443e7c	185	}
33443e7c	186	return sl;
	187	}
	188
0ca9bc0e	189	for(i = 0; i < 4 && rem--; i++) {
	190	oks >>= 1;
	191	eks >>= 1;
	192	in >>= 2;
	193	extend_table(o_head, &o_tail, oks & 1, LF_POLY_EVEN << 1 \| 1,
	194	LF_POLY_ODD << 1, 0);
33443e7c	195	if(o_head > o_tail)
	196	return sl;
	197
0ca9bc0e	198	extend_table(e_head, &e_tail, eks & 1, LF_POLY_ODD,
0ca9bc0e	199	LF_POLY_EVEN << 1 \| 1, in & 3);
33443e7c	200	if(e_head > e_tail)
	201	return sl;
	202	}
33443e7c	203	bucket_sort_intersect(e_head, e_tail, o_head, o_tail, &bucket_info, bucket);
	204
	205	for (int i = bucket_info.numbuckets - 1; i >= 0; i--) {
	206	sl = recover(bucket_info.bucket_info[1][i].head, bucket_info.bucket_info[1][i].tail, oks,
	207	bucket_info.bucket_info[0][i].head, bucket_info.bucket_info[0][i].tail, eks,
	208	rem, sl, in, bucket);
	209	}
	210
	211	return sl;
	212	}
	213	/** lfsr_recovery
	214	* recover the state of the lfsr given 32 bits of the keystream
	215	* additionally you can use the in parameter to specify the value
	216	* that was fed into the lfsr at the time the keystream was generated
	217	*/
	218	struct Crypto1State* lfsr_recovery32(uint32_t ks2, uint32_t in)
	219	{
	220	struct Crypto1State *statelist;
	221	uint32_t odd_head = 0, odd_tail = 0, oks = 0;
	222	uint32_t even_head = 0, even_tail = 0, eks = 0;
	223	int i;
	224
33443e7c	225	for(i = 31; i >= 0; i -= 2)
	226	oks = oks << 1 \| BEBIT(ks2, i);
	227	for(i = 30; i >= 0; i -= 2)
	228	eks = eks << 1 \| BEBIT(ks2, i);
	229
	230	odd_head = odd_tail = malloc(sizeof(uint32_t) << 21);
	231	even_head = even_tail = malloc(sizeof(uint32_t) << 21);
	232	statelist = malloc(sizeof(struct Crypto1State) << 18);
	233	if(!odd_tail-- \|\| !even_tail-- \|\| !statelist) {
0ca9bc0e	234	free(statelist);
0ca9bc0e	235	statelist = 0;
33443e7c	236	goto out;
	237	}
	238	statelist->odd = statelist->even = 0;
	239
	240	// allocate memory for out of place bucket_sort
	241	bucket_array_t bucket;
	242	for (uint32_t i = 0; i < 2; i++)
	243	for (uint32_t j = 0; j <= 0xff; j++) {
	244	bucket[i][j].head = malloc(sizeof(uint32_t)<<14);
	245	if (!bucket[i][j].head) {
	246	goto out;
	247	}
	248	}
	249
	250
33443e7c	251	for(i = 1 << 20; i >= 0; --i) {
	252	if(filter(i) == (oks & 1))
	253	*++odd_tail = i;
	254	if(filter(i) == (eks & 1))
	255	*++even_tail = i;
	256	}
	257
33443e7c	258	for(i = 0; i < 4; i++) {
	259	extend_table_simple(odd_head, &odd_tail, (oks >>= 1) & 1);
	260	extend_table_simple(even_head, &even_tail, (eks >>= 1) & 1);
	261	}
	262
0ca9bc0e	263	in = (in >> 16 & 0xff) \| (in << 16) \| (in & 0xff00);
33443e7c	264	recover(odd_head, odd_tail, oks,
	265	even_head, even_tail, eks, 11, statelist, in << 1, bucket);
	266
33443e7c	267	out:
	268	free(odd_head);
	269	free(even_head);
	270	for (uint32_t i = 0; i < 2; i++)
	271	for (uint32_t j = 0; j <= 0xff; j++)
	272	free(bucket[i][j].head);
	273
	274	return statelist;
	275	}
	276
	277	static const uint32_t S1[] = { 0x62141, 0x310A0, 0x18850, 0x0C428, 0x06214,
	278	0x0310A, 0x85E30, 0xC69AD, 0x634D6, 0xB5CDE, 0xDE8DA, 0x6F46D, 0xB3C83,
	279	0x59E41, 0xA8995, 0xD027F, 0x6813F, 0x3409F, 0x9E6FA};
	280	static const uint32_t S2[] = { 0x3A557B00, 0x5D2ABD80, 0x2E955EC0, 0x174AAF60,
	281	0x0BA557B0, 0x05D2ABD8, 0x0449DE68, 0x048464B0, 0x42423258, 0x278192A8,
	282	0x156042D0, 0x0AB02168, 0x43F89B30, 0x61FC4D98, 0x765EAD48, 0x7D8FDD20,
	283	0x7EC7EE90, 0x7F63F748, 0x79117020};
	284	static const uint32_t T1[] = {
	285	0x4F37D, 0x279BE, 0x97A6A, 0x4BD35, 0x25E9A, 0x12F4D, 0x097A6, 0x80D66,
	286	0xC4006, 0x62003, 0xB56B4, 0x5AB5A, 0xA9318, 0xD0F39, 0x6879C, 0xB057B,
	287	0x582BD, 0x2C15E, 0x160AF, 0x8F6E2, 0xC3DC4, 0xE5857, 0x72C2B, 0x39615,
	288	0x98DBF, 0xC806A, 0xE0680, 0x70340, 0x381A0, 0x98665, 0x4C332, 0xA272C};
	289	static const uint32_t T2[] = { 0x3C88B810, 0x5E445C08, 0x2982A580, 0x14C152C0,
	290	0x4A60A960, 0x253054B0, 0x52982A58, 0x2FEC9EA8, 0x1156C4D0, 0x08AB6268,
	291	0x42F53AB0, 0x217A9D58, 0x161DC528, 0x0DAE6910, 0x46D73488, 0x25CB11C0,
	292	0x52E588E0, 0x6972C470, 0x34B96238, 0x5CFC3A98, 0x28DE96C8, 0x12CFC0E0,
	293	0x4967E070, 0x64B3F038, 0x74F97398, 0x7CDC3248, 0x38CE92A0, 0x1C674950,
	294	0x0E33A4A8, 0x01B959D0, 0x40DCACE8, 0x26CEDDF0};
	295	static const uint32_t C1[] = { 0x846B5, 0x4235A, 0x211AD};
	296	static const uint32_t C2[] = { 0x1A822E0, 0x21A822E0, 0x21A822E0};
	297	/** Reverse 64 bits of keystream into possible cipher states
	298	* Variation mentioned in the paper. Somewhat optimized version
	299	*/
	300	struct Crypto1State* lfsr_recovery64(uint32_t ks2, uint32_t ks3)
	301	{
	302	struct Crypto1State statelist, sl;
	303	uint8_t oks[32], eks[32], hi[32];
	304	uint32_t low = 0, win = 0;
	305	uint32_t *tail, table[1 << 16];
	306	int i, j;
	307
	308	sl = statelist = malloc(sizeof(struct Crypto1State) << 4);
	309	if(!sl)
	310	return 0;
	311	sl->odd = sl->even = 0;
	312
	313	for(i = 30; i >= 0; i -= 2) {
0ca9bc0e	314	oks[i >> 1] = BEBIT(ks2, i);
0ca9bc0e	315	oks[16 + (i >> 1)] = BEBIT(ks3, i);
33443e7c	316	}
33443e7c	317	for(i = 31; i >= 0; i -= 2) {
0ca9bc0e	318	eks[i >> 1] = BEBIT(ks2, i);
0ca9bc0e	319	eks[16 + (i >> 1)] = BEBIT(ks3, i);
33443e7c	320	}
	321
	322	for(i = 0xfffff; i >= 0; --i) {
	323	if (filter(i) != oks[0])
	324	continue;
	325
	326	*(tail = table) = i;
	327	for(j = 1; tail >= table && j < 29; ++j)
	328	extend_table_simple(table, &tail, oks[j]);
	329
	330	if(tail < table)
	331	continue;
	332
	333	for(j = 0; j < 19; ++j)
1f065e1d	334	low = low << 1 \| evenparity32(i & S1[j]);
33443e7c	335	for(j = 0; j < 32; ++j)
1f065e1d	336	hi[j] = evenparity32(i & T1[j]);
33443e7c	337
	338	for(; tail >= table; --tail) {
	339	for(j = 0; j < 3; ++j) {
	340	tail = tail << 1;
1f065e1d	341	tail \|= evenparity32((i & C1[j]) ^ (tail & C2[j]));
33443e7c	342	if(filter(*tail) != oks[29 + j])
	343	goto continue2;
	344	}
	345
	346	for(j = 0; j < 19; ++j)
1f065e1d	347	win = win << 1 \| evenparity32(*tail & S2[j]);
33443e7c	348
	349	win ^= low;
	350	for(j = 0; j < 32; ++j) {
1f065e1d	351	win = win << 1 ^ hi[j] ^ evenparity32(*tail & T2[j]);
33443e7c	352	if(filter(win) != eks[j])
	353	goto continue2;
	354	}
	355
1f065e1d	356	tail = tail << 1 \| evenparity32(LF_POLY_EVEN & *tail);
1f065e1d	357	sl->odd = *tail ^ evenparity32(LF_POLY_ODD & win);
33443e7c	358	sl->even = win;
	359	++sl;
	360	sl->odd = sl->even = 0;
	361	continue2:;
	362	}
	363	}
	364	return statelist;
	365	}
	366
	367	/** lfsr_rollback_bit
	368	* Rollback the shift register in order to get previous states
	369	*/
0ca9bc0e	370	uint8_t lfsr_rollback_bit(struct Crypto1State *s, uint32_t in, int fb)
33443e7c	371	{
33443e7c	372	int out;
0ca9bc0e	373	uint8_t ret;
	374	uint32_t t;
	375
33443e7c	376	s->odd &= 0xffffff;
0ca9bc0e	377	t = s->odd, s->odd = s->even, s->even = t;
33443e7c	378
	379	out = s->even & 1;
	380	out ^= LF_POLY_EVEN & (s->even >>= 1);
	381	out ^= LF_POLY_ODD & s->odd;
	382	out ^= !!in;
0ca9bc0e	383	out ^= (ret = filter(s->odd)) & !!fb;
33443e7c	384
1f065e1d	385	s->even \|= evenparity32(out) << 23;
0ca9bc0e	386	return ret;
33443e7c	387	}
	388	/** lfsr_rollback_byte
	389	* Rollback the shift register in order to get previous states
	390	*/
0ca9bc0e	391	uint8_t lfsr_rollback_byte(struct Crypto1State *s, uint32_t in, int fb)
33443e7c	392	{
0ca9bc0e	393	int i, ret=0;
33443e7c	394	for (i = 7; i >= 0; --i)
0ca9bc0e	395	ret \|= lfsr_rollback_bit(s, BIT(in, i), fb) << i;
0ca9bc0e	396	return ret;
33443e7c	397	}
	398	/** lfsr_rollback_word
	399	* Rollback the shift register in order to get previous states
	400	*/
0ca9bc0e	401	uint32_t lfsr_rollback_word(struct Crypto1State *s, uint32_t in, int fb)
33443e7c	402	{
33443e7c	403	int i;
0ca9bc0e	404	uint32_t ret = 0;
33443e7c	405	for (i = 31; i >= 0; --i)
0ca9bc0e	406	ret \|= lfsr_rollback_bit(s, BEBIT(in, i), fb) << (i ^ 24);
0ca9bc0e	407	return ret;
33443e7c	408	}
	409
	410	/** nonce_distance
	411	* x,y valid tag nonces, then prng_successor(x, nonce_distance(x, y)) = y
	412	*/
	413	static uint16_t *dist = 0;
	414	int nonce_distance(uint32_t from, uint32_t to)
	415	{
	416	uint16_t x, i;
	417	if(!dist) {
	418	dist = malloc(2 << 16);
	419	if(!dist)
	420	return -1;
	421	for (x = i = 1; i; ++i) {
	422	dist[(x & 0xff) << 8 \| x >> 8] = i;
	423	x = x >> 1 \| (x ^ x >> 2 ^ x >> 3 ^ x >> 5) << 15;
	424	}
	425	}
	426	return (65535 + dist[to >> 16] - dist[from >> 16]) % 65535;
	427	}
	428
	429
	430	static uint32_t fastfwd[2][8] = {
	431	{ 0, 0x4BC53, 0xECB1, 0x450E2, 0x25E29, 0x6E27A, 0x2B298, 0x60ECB},
	432	{ 0, 0x1D962, 0x4BC53, 0x56531, 0xECB1, 0x135D3, 0x450E2, 0x58980}};
33443e7c	433	/** lfsr_prefix_ks
	434	*
	435	* Is an exported helper function from the common prefix attack
	436	* Described in the "dark side" paper. It returns an -1 terminated array
	437	* of possible partial(21 bit) secret state.
	438	* The required keystream(ks) needs to contain the keystream that was used to
0ca9bc0e	439	* encrypt the NACK which is observed when varying only the 3 last bits of Nr
33443e7c	440	* only correct iff [NR_3] ^ NR_3 does not depend on Nr_3
	441	*/
	442	uint32_t *lfsr_prefix_ks(uint8_t ks[8], int isodd)
	443	{
0ca9bc0e	444	uint32_t c, entry, *candidates = malloc(4 << 10);
	445	int i, size = 0, good;
	446
33443e7c	447	if(!candidates)
	448	return 0;
	449
0ca9bc0e	450	for(i = 0; i < 1 << 21; ++i) {
	451	for(c = 0, good = 1; good && c < 8; ++c) {
	452	entry = i ^ fastfwd[isodd][c];
	453	good &= (BIT(ks[c], isodd) == filter(entry >> 1));
	454	good &= (BIT(ks[c], isodd + 2) == filter(entry));
33443e7c	455	}
0ca9bc0e	456	if(good)
	457	candidates[size++] = i;
	458	}
	459
	460	candidates[size] = -1;
33443e7c	461
	462	return candidates;
	463	}
	464
0ca9bc0e	465	/** check_pfx_parity
33443e7c	466	* helper function which eliminates possible secret states using parity bits
	467	*/
	468	static struct Crypto1State*
0ca9bc0e	469	check_pfx_parity(uint32_t prefix, uint32_t rresp, uint8_t parities[8][8],
de867f50	470	uint32_t odd, uint32_t even, struct Crypto1State* sl, uint32_t no_par)
33443e7c	471	{
de867f50	472	uint32_t ks1, nr, ks2, rr, ks3, c, good = 1;
33443e7c	473
0ca9bc0e	474	for(c = 0; good && c < 8; ++c) {
	475	sl->odd = odd ^ fastfwd[1][c];
	476	sl->even = even ^ fastfwd[0][c];
33443e7c	477
0ca9bc0e	478	lfsr_rollback_bit(sl, 0, 0);
0ca9bc0e	479	lfsr_rollback_bit(sl, 0, 0);
33443e7c	480
0ca9bc0e	481	ks3 = lfsr_rollback_bit(sl, 0, 0);
	482	ks2 = lfsr_rollback_word(sl, 0, 0);
	483	ks1 = lfsr_rollback_word(sl, prefix \| c << 5, 1);
33443e7c	484
	485	if (no_par)
	486	break;
	487
33443e7c	488	nr = ks1 ^ (prefix \| c << 5);
	489	rr = ks2 ^ rresp;
	490
1f065e1d	491	good &= evenparity32(nr & 0x000000ff) ^ parities[c][3] ^ BIT(ks2, 24);
	492	good &= evenparity32(rr & 0xff000000) ^ parities[c][4] ^ BIT(ks2, 16);
	493	good &= evenparity32(rr & 0x00ff0000) ^ parities[c][5] ^ BIT(ks2, 8);
	494	good &= evenparity32(rr & 0x0000ff00) ^ parities[c][6] ^ BIT(ks2, 0);
	495	good &= evenparity32(rr & 0x000000ff) ^ parities[c][7] ^ ks3;
33443e7c	496	}
33443e7c	497
0ca9bc0e	498	return sl + good;
33443e7c	499	}
	500
	501
	502	/** lfsr_common_prefix
	503	* Implentation of the common prefix attack.
33443e7c	504	*/
33443e7c	505	struct Crypto1State*
de867f50	506	lfsr_common_prefix(uint32_t pfx, uint32_t rr, uint8_t ks[8], uint8_t par[8][8], uint32_t no_par)
33443e7c	507	{
	508	struct Crypto1State statelist, s;
	509	uint32_t odd, even, o, e, top;
	510
	511	odd = lfsr_prefix_ks(ks, 1);
	512	even = lfsr_prefix_ks(ks, 0);
	513
7779d73c	514	s = statelist = malloc((sizeof *statelist) << 22); // was << 20. Need more for no_par special attack. Enough???
0ca9bc0e	515	if(!s \|\| !odd \|\| !even) {
	516	free(statelist);
	517	statelist = 0;
	518	goto out;
33443e7c	519	}
33443e7c	520
0ca9bc0e	521	for(o = odd; *o + 1; ++o)
0ca9bc0e	522	for(e = even; *e + 1; ++e)
33443e7c	523	for(top = 0; top < 64; ++top) {
0ca9bc0e	524	*o += 1 << 21;
0ca9bc0e	525	*e += (!(top & 7) + 1) << 21;
de867f50	526	s = check_pfx_parity(pfx, rr, par, o, e, s, no_par);
33443e7c	527	}
33443e7c	528
0ca9bc0e	529	s->odd = s->even = 0;
0ca9bc0e	530	out:
33443e7c	531	free(odd);
33443e7c	532	free(even);
33443e7c	533	return statelist;
33443e7c	534	}