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