[proxmark3-svn] / tools / nonce2key / crapto1.c

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