[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
	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
	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
	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
	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
	int i, ret = 0;\r
	for (i = 7; i >= 0; --i)\r
		ret |= lfsr_rollback_bit(s, BIT(in, i), fb) << i;\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
	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
	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 c, entry, *candidates = malloc(4 << 10);\r
	int i, size = 0, 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
	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
	187	for(i = 31; i >= 0; i -= 2)\r
	188	oks = oks << 1 \| BEBIT(ks2, i);\r
	189	for(i = 30; i >= 0; i -= 2)\r
	190	eks = eks << 1 \| BEBIT(ks2, i);\r
	191	\r
	192	odd_head = odd_tail = malloc(sizeof(uint32_t) << 21);\r
	193	even_head = even_tail = malloc(sizeof(uint32_t) << 21);\r
	194	statelist = malloc(sizeof(struct Crypto1State) << 18);\r
72109f82	195	if(!odd_tail-- \|\| !even_tail-- \|\| !statelist) {\r
	196	free(statelist);\r
	197	statelist = 0;\r
93f57590	198	goto out;\r
72109f82	199	}\r
93f57590	200	\r
	201	statelist->odd = statelist->even = 0;\r
	202	\r
	203	for(i = 1 << 20; i >= 0; --i) {\r
	204	if(filter(i) == (oks & 1))\r
	205	*++odd_tail = i;\r
	206	if(filter(i) == (eks & 1))\r
	207	*++even_tail = i;\r
	208	}\r
	209	\r
	210	for(i = 0; i < 4; i++) {\r
	211	extend_table_simple(odd_head, &odd_tail, (oks >>= 1) & 1);\r
	212	extend_table_simple(even_head, &even_tail, (eks >>= 1) & 1);\r
	213	}\r
	214	\r
	215	in = (in >> 16 & 0xff) \| (in << 16) \| (in & 0xff00);\r
	216	recover(odd_head, odd_tail, oks,\r
	217	even_head, even_tail, eks, 11, statelist, in << 1);\r
	218	\r
	219	out:\r
	220	free(odd_head);\r
	221	free(even_head);\r
	222	return statelist;\r
	223	}\r
	224	\r
	225	static const uint32_t S1[] = { 0x62141, 0x310A0, 0x18850, 0x0C428, 0x06214,\r
	226	0x0310A, 0x85E30, 0xC69AD, 0x634D6, 0xB5CDE, 0xDE8DA, 0x6F46D, 0xB3C83,\r
	227	0x59E41, 0xA8995, 0xD027F, 0x6813F, 0x3409F, 0x9E6FA};\r
	228	static const uint32_t S2[] = { 0x3A557B00, 0x5D2ABD80, 0x2E955EC0, 0x174AAF60,\r
	229	0x0BA557B0, 0x05D2ABD8, 0x0449DE68, 0x048464B0, 0x42423258, 0x278192A8,\r
	230	0x156042D0, 0x0AB02168, 0x43F89B30, 0x61FC4D98, 0x765EAD48, 0x7D8FDD20,\r
	231	0x7EC7EE90, 0x7F63F748, 0x79117020};\r
	232	static const uint32_t T1[] = {\r
	233	0x4F37D, 0x279BE, 0x97A6A, 0x4BD35, 0x25E9A, 0x12F4D, 0x097A6, 0x80D66,\r
	234	0xC4006, 0x62003, 0xB56B4, 0x5AB5A, 0xA9318, 0xD0F39, 0x6879C, 0xB057B,\r
	235	0x582BD, 0x2C15E, 0x160AF, 0x8F6E2, 0xC3DC4, 0xE5857, 0x72C2B, 0x39615,\r
	236	0x98DBF, 0xC806A, 0xE0680, 0x70340, 0x381A0, 0x98665, 0x4C332, 0xA272C};\r
	237	static const uint32_t T2[] = { 0x3C88B810, 0x5E445C08, 0x2982A580, 0x14C152C0,\r
	238	0x4A60A960, 0x253054B0, 0x52982A58, 0x2FEC9EA8, 0x1156C4D0, 0x08AB6268,\r
	239	0x42F53AB0, 0x217A9D58, 0x161DC528, 0x0DAE6910, 0x46D73488, 0x25CB11C0,\r
	240	0x52E588E0, 0x6972C470, 0x34B96238, 0x5CFC3A98, 0x28DE96C8, 0x12CFC0E0,\r
	241	0x4967E070, 0x64B3F038, 0x74F97398, 0x7CDC3248, 0x38CE92A0, 0x1C674950,\r
	242	0x0E33A4A8, 0x01B959D0, 0x40DCACE8, 0x26CEDDF0};\r
	243	static const uint32_t C1[] = { 0x846B5, 0x4235A, 0x211AD};\r
	244	static const uint32_t C2[] = { 0x1A822E0, 0x21A822E0, 0x21A822E0};\r
	245	/** Reverse 64 bits of keystream into possible cipher states\r
	246	* Variation mentioned in the paper. Somewhat optimized version\r
	247	*/\r
	248	struct Crypto1State* lfsr_recovery64(uint32_t ks2, uint32_t ks3)\r
	249	{\r
	250	struct Crypto1State statelist, sl;\r
	251	uint8_t oks[32], eks[32], hi[32];\r
	252	uint32_t low = 0, win = 0;\r
	253	uint32_t *tail, table[1 << 16];\r
	254	int i, j;\r
	255	\r
	256	sl = statelist = malloc(sizeof(struct Crypto1State) << 4);\r
	257	if(!sl)\r
	258	return 0;\r
	259	sl->odd = sl->even = 0;\r
	260	\r
	261	for(i = 30; i >= 0; i -= 2) {\r
72109f82	262	oks[i >> 1] = BEBIT(ks2, i);\r
72109f82	263	oks[16 + (i >> 1)] = BEBIT(ks3, i);\r
93f57590	264	}\r
93f57590	265	for(i = 31; i >= 0; i -= 2) {\r
72109f82	266	eks[i >> 1] = BEBIT(ks2, i);\r
72109f82	267	eks[16 + (i >> 1)] = BEBIT(ks3, i);\r
93f57590	268	}\r
	269	\r
	270	for(i = 0xfffff; i >= 0; --i) {\r
	271	if (filter(i) != oks[0])\r
	272	continue;\r
	273	\r
	274	*(tail = table) = i;\r
	275	for(j = 1; tail >= table && j < 29; ++j)\r
	276	extend_table_simple(table, &tail, oks[j]);\r
	277	\r
	278	if(tail < table)\r
	279	continue;\r
	280	\r
	281	for(j = 0; j < 19; ++j)\r
	282	low = low << 1 \| parity(i & S1[j]);\r
	283	for(j = 0; j < 32; ++j)\r
	284	hi[j] = parity(i & T1[j]);\r
	285	\r
	286	for(; tail >= table; --tail) {\r
	287	for(j = 0; j < 3; ++j) {\r
	288	tail = tail << 1;\r
	289	tail \|= parity((i & C1[j]) ^ (tail & C2[j]));\r
	290	if(filter(*tail) != oks[29 + j])\r
	291	goto continue2;\r
	292	}\r
	293	\r
	294	for(j = 0; j < 19; ++j)\r
	295	win = win << 1 \| parity(*tail & S2[j]);\r
	296	\r
	297	win ^= low;\r
	298	for(j = 0; j < 32; ++j) {\r
	299	win = win << 1 ^ hi[j] ^ parity(*tail & T2[j]);\r
	300	if(filter(win) != eks[j])\r
	301	goto continue2;\r
	302	}\r
	303	\r
	304	tail = tail << 1 \| parity(LF_POLY_EVEN & *tail);\r
	305	sl->odd = *tail ^ parity(LF_POLY_ODD & win);\r
	306	sl->even = win;\r
	307	++sl;\r
	308	sl->odd = sl->even = 0;\r
	309	continue2:;\r
	310	}\r
	311	}\r
	312	return statelist;\r
	313	}\r
	314	\r
	315	/** lfsr_rollback_bit\r
	316	* Rollback the shift register in order to get previous states\r
	317	*/\r
72109f82	318	uint8_t lfsr_rollback_bit(struct Crypto1State *s, uint32_t in, int fb)\r
93f57590	319	{\r
93f57590	320	int out;\r
72109f82	321	uint8_t ret;\r
72109f82	322	uint32_t t;\r
93f57590	323	\r
93f57590	324	s->odd &= 0xffffff;\r
72109f82	325	t = s->odd, s->odd = s->even, s->even = t;\r
93f57590	326	\r
	327	out = s->even & 1;\r
	328	out ^= LF_POLY_EVEN & (s->even >>= 1);\r
	329	out ^= LF_POLY_ODD & s->odd;\r
	330	out ^= !!in;\r
72109f82	331	out ^= (ret = filter(s->odd)) & !!fb;\r
93f57590	332	\r
93f57590	333	s->even \|= parity(out) << 23;\r
72109f82	334	return ret;\r
93f57590	335	}\r
	336	/** lfsr_rollback_byte\r
	337	* Rollback the shift register in order to get previous states\r
	338	*/\r
72109f82	339	uint8_t lfsr_rollback_byte(struct Crypto1State *s, uint32_t in, int fb)\r
93f57590	340	{\r
72109f82	341	int i, ret = 0;\r
93f57590	342	for (i = 7; i >= 0; --i)\r
72109f82	343	ret \|= lfsr_rollback_bit(s, BIT(in, i), fb) << i;\r
72109f82	344	return ret;\r
93f57590	345	}\r
	346	/** lfsr_rollback_word\r
	347	* Rollback the shift register in order to get previous states\r
	348	*/\r
72109f82	349	uint32_t lfsr_rollback_word(struct Crypto1State *s, uint32_t in, int fb)\r
93f57590	350	{\r
93f57590	351	int i;\r
72109f82	352	uint32_t ret = 0;\r
93f57590	353	for (i = 31; i >= 0; --i)\r
72109f82	354	ret \|= lfsr_rollback_bit(s, BEBIT(in, i), fb) << (i ^ 24);\r
72109f82	355	return ret;\r
93f57590	356	}\r
	357	\r
	358	/** nonce_distance\r
	359	* x,y valid tag nonces, then prng_successor(x, nonce_distance(x, y)) = y\r
	360	*/\r
	361	static uint16_t *dist = 0;\r
	362	int nonce_distance(uint32_t from, uint32_t to)\r
	363	{\r
	364	uint16_t x, i;\r
	365	if(!dist) {\r
	366	dist = malloc(2 << 16);\r
	367	if(!dist)\r
	368	return -1;\r
	369	for (x = i = 1; i; ++i) {\r
	370	dist[(x & 0xff) << 8 \| x >> 8] = i;\r
	371	x = x >> 1 \| (x ^ x >> 2 ^ x >> 3 ^ x >> 5) << 15;\r
	372	}\r
	373	}\r
	374	return (65535 + dist[to >> 16] - dist[from >> 16]) % 65535;\r
	375	}\r
	376	\r
	377	\r
	378	static uint32_t fastfwd[2][8] = {\r
	379	{ 0, 0x4BC53, 0xECB1, 0x450E2, 0x25E29, 0x6E27A, 0x2B298, 0x60ECB},\r
	380	{ 0, 0x1D962, 0x4BC53, 0x56531, 0xECB1, 0x135D3, 0x450E2, 0x58980}};\r
	381	\r
	382	\r
	383	/** lfsr_prefix_ks\r
	384	*\r
	385	* Is an exported helper function from the common prefix attack\r
	386	* Described in the "dark side" paper. It returns an -1 terminated array\r
	387	* of possible partial(21 bit) secret state.\r
	388	* The required keystream(ks) needs to contain the keystream that was used to\r
72109f82	389	* encrypt the NACK which is observed when varying only the 3 last bits of Nr\r
93f57590	390	* only correct iff [NR_3] ^ NR_3 does not depend on Nr_3\r
	391	*/\r
	392	uint32_t *lfsr_prefix_ks(uint8_t ks[8], int isodd)\r
	393	{\r
72109f82	394	uint32_t c, entry, *candidates = malloc(4 << 10);\r
72109f82	395	int i, size = 0, good;\r
93f57590	396	\r
	397	if(!candidates)\r
	398	return 0;\r
	399	\r
72109f82	400	for(i = 0; i < 1 << 21; ++i) {\r
	401	for(c = 0, good = 1; good && c < 8; ++c) {\r
	402	entry = i ^ fastfwd[isodd][c];\r
	403	good &= (BIT(ks[c], isodd) == filter(entry >> 1));\r
	404	good &= (BIT(ks[c], isodd + 2) == filter(entry));\r
93f57590	405	}\r
72109f82	406	if(good)\r
	407	candidates[size++] = i;\r
	408	}\r
93f57590	409	\r
72109f82	410	candidates[size] = -1;\r
93f57590	411	\r
	412	return candidates;\r
	413	}\r
	414	\r
72109f82	415	/** check_pfx_parity\r
93f57590	416	* helper function which eliminates possible secret states using parity bits\r
93f57590	417	*/\r
9d1eaa28	418	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	419	{\r
72109f82	420	uint32_t ks1, nr, ks2, rr, ks3, c, good = 1;\r
	421	\r
	422	for(c = 0; good && c < 8; ++c) {\r
	423	sl->odd = odd ^ fastfwd[1][c];\r
	424	sl->even = even ^ fastfwd[0][c];\r
	425	\r
	426	lfsr_rollback_bit(sl, 0, 0);\r
	427	lfsr_rollback_bit(sl, 0, 0);\r
	428	\r
	429	ks3 = lfsr_rollback_bit(sl, 0, 0);\r
	430	ks2 = lfsr_rollback_word(sl, 0, 0);\r
	431	ks1 = lfsr_rollback_word(sl, prefix \| c << 5, 1);\r
	432	\r
93f57590	433	nr = ks1 ^ (prefix \| c << 5);\r
	434	rr = ks2 ^ rresp;\r
	435	\r
93f57590	436	good &= parity(nr & 0x000000ff) ^ parities[c][3] ^ BIT(ks2, 24);\r
	437	good &= parity(rr & 0xff000000) ^ parities[c][4] ^ BIT(ks2, 16);\r
	438	good &= parity(rr & 0x00ff0000) ^ parities[c][5] ^ BIT(ks2, 8);\r
	439	good &= parity(rr & 0x0000ff00) ^ parities[c][6] ^ BIT(ks2, 0);\r
72109f82	440	good &= parity(rr & 0x000000ff) ^ parities[c][7] ^ ks3;\r
93f57590	441	}\r
93f57590	442	\r
72109f82	443	return sl + good;\r
93f57590	444	} \r
	445	\r
	446	\r
	447	/** lfsr_common_prefix\r
	448	* Implentation of the common prefix attack.\r
	449	* Requires the 28 bit constant prefix used as reader nonce (pfx)\r
	450	* The reader response used (rr)\r
	451	* The keystream used to encrypt the observed NACK's (ks)\r
	452	* The parity bits (par)\r
	453	* It returns a zero terminated list of possible cipher states after the\r
	454	* tag nonce was fed in\r
	455	*/\r
9d1eaa28	456	struct Crypto1State* lfsr_common_prefix(uint32_t pfx, uint32_t rr, uint8_t ks[8], uint8_t par[8][8])\r
93f57590	457	{\r
	458	struct Crypto1State statelist, s;\r
	459	uint32_t odd, even, o, e, top;\r
	460	\r
	461	odd = lfsr_prefix_ks(ks, 1);\r
	462	even = lfsr_prefix_ks(ks, 0);\r
	463	\r
72109f82	464	s = statelist = malloc((sizeof *statelist) << 20);\r
	465	if(!s \|\| !odd \|\| !even) {\r
	466	free(statelist);\r
9d1eaa28	467	free(odd);\r
	468	free(even);\r
	469	return 0;\r
72109f82	470	}\r
93f57590	471	\r
72109f82	472	for(o = odd; *o + 1; ++o)\r
72109f82	473	for(e = even; *e + 1; ++e)\r
93f57590	474	for(top = 0; top < 64; ++top) {\r
72109f82	475	*o += 1 << 21;\r
	476	*e += (!(top & 7) + 1) << 21;\r
	477	s = check_pfx_parity(pfx, rr, par, o, e, s);\r
93f57590	478	}\r
	479	\r
	480	s->odd = s->even = 0;\r
9d1eaa28	481	\r
93f57590	482	return statelist;\r
93f57590	483	}\r