[proxmark3-svn] / tools / mfkey / 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
/** 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
 */\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
7847961b	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
72109f82	18	Copyright (C) 2008-2014 bla <blapost@gmail.com>\r
7847961b	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
7847961b	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
7847961b	48	\r
	49	if(rit >= start)\r
	50	--rit;\r
	51	if(rit != start)\r
72109f82	52	t = rit, rit = start, start = t;\r
7847961b	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
	60	static inline uint32_t* binsearch(uint32_t start, uint32_t stop)\r
	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 extend_table_simple(uint32_t tbl, uint32_t *end, int bit)\r
	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
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
149	if(o_head > o_tail)\r
150	return sl;\r
151	\r
152	extend_table(e_head, &e_tail, eks & 1, LF_POLY_ODD,\r
153	LF_POLY_EVEN << 1 \| 1, in & 3);\r
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
195	if(!odd_tail-- \|\| !even_tail-- \|\| !statelist) {\r
196	free(statelist);\r
197	statelist = 0;\r
198	goto out;\r
199	}\r
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
262	oks[i >> 1] = BEBIT(ks2, i);\r
263	oks[16 + (i >> 1)] = BEBIT(ks3, i);\r
264	}\r
265	for(i = 31; i >= 0; i -= 2) {\r
266	eks[i >> 1] = BEBIT(ks2, i);\r
267	eks[16 + (i >> 1)] = BEBIT(ks3, i);\r
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
318	uint8_t lfsr_rollback_bit(struct Crypto1State *s, uint32_t in, int fb)\r
319	{\r
320	int out;\r
321	uint8_t ret;\r
72109f82	322	uint32_t t;\r
7847961b	323	\r
7847961b	324	s->odd &= 0xffffff;\r
72109f82	325	t = s->odd, s->odd = s->even, s->even = t;\r
7847961b	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
	331	out ^= (ret = filter(s->odd)) & !!fb;\r
	332	\r
	333	s->even \|= parity(out) << 23;\r
	334	return ret;\r
	335	}\r
	336	/** lfsr_rollback_byte\r
	337	* Rollback the shift register in order to get previous states\r
	338	*/\r
	339	uint8_t lfsr_rollback_byte(struct Crypto1State *s, uint32_t in, int fb)\r
	340	{\r
	341	int i, ret = 0;\r
	342	for (i = 7; i >= 0; --i)\r
	343	ret \|= lfsr_rollback_bit(s, BIT(in, i), fb) << i;\r
	344	return ret;\r
	345	}\r
	346	/** lfsr_rollback_word\r
	347	* Rollback the shift register in order to get previous states\r
	348	*/\r
	349	uint32_t lfsr_rollback_word(struct Crypto1State *s, uint32_t in, int fb)\r
	350	{\r
	351	int i;\r
	352	uint32_t ret = 0;\r
	353	for (i = 31; i >= 0; --i)\r
	354	ret \|= lfsr_rollback_bit(s, BEBIT(in, i), fb) << (i ^ 24);\r
	355	return ret;\r
	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	/** lfsr_prefix_ks\r
	382	*\r
	383	* Is an exported helper function from the common prefix attack\r
	384	* Described in the "dark side" paper. It returns an -1 terminated array\r
	385	* of possible partial(21 bit) secret state.\r
	386	* The required keystream(ks) needs to contain the keystream that was used to\r
	387	* encrypt the NACK which is observed when varying only the 3 last bits of Nr\r
	388	* only correct iff [NR_3] ^ NR_3 does not depend on Nr_3\r
	389	*/\r
390	uint32_t *lfsr_prefix_ks(uint8_t ks[8], int isodd)\r
391	{\r
392	uint32_t c, entry, *candidates = malloc(4 << 10);\r
393	int i, size = 0, good;\r
394	\r
395	if(!candidates)\r
396	return 0;\r
397	\r
398	for(i = 0; i < 1 << 21; ++i) {\r
399	for(c = 0, good = 1; good && c < 8; ++c) {\r
400	entry = i ^ fastfwd[isodd][c];\r
401	good &= (BIT(ks[c], isodd) == filter(entry >> 1));\r
402	good &= (BIT(ks[c], isodd + 2) == filter(entry));\r
403	}\r
404	if(good)\r
405	candidates[size++] = i;\r
406	}\r
407	\r
408	candidates[size] = -1;\r
409	\r
410	return candidates;\r
411	}\r
412	\r
413	/** check_pfx_parity\r
414	* helper function which eliminates possible secret states using parity bits\r
415	*/\r
416	static struct Crypto1State*\r
417	check_pfx_parity(uint32_t prefix, uint32_t rresp, uint8_t parities[8][8],\r
418	uint32_t odd, uint32_t even, struct Crypto1State* sl)\r
419	{\r
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
433	nr = ks1 ^ (prefix \| c << 5);\r
434	rr = ks2 ^ rresp;\r
435	\r
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
440	good &= parity(rr & 0x000000ff) ^ parities[c][7] ^ ks3;\r
441	}\r
442	\r
443	return sl + good;\r
444	} \r
445	\r
446	\r
447	/** lfsr_common_prefix\r
448	* Implentation of the common prefix attack.\r
449	*/\r
450	struct Crypto1State*\r
451	lfsr_common_prefix(uint32_t pfx, uint32_t rr, uint8_t ks[8], uint8_t par[8][8])\r
452	{\r
453	struct Crypto1State statelist, s;\r
454	uint32_t odd, even, o, e, top;\r
455	\r
456	odd = lfsr_prefix_ks(ks, 1);\r
457	even = lfsr_prefix_ks(ks, 0);\r
458	\r
459	s = statelist = malloc((sizeof *statelist) << 20);\r
460	if(!s \|\| !odd \|\| !even) {\r
461	free(statelist);\r
462	statelist = 0;\r
463	goto out;\r
464	}\r
465	\r
466	for(o = odd; *o + 1; ++o)\r
467	for(e = even; *e + 1; ++e)\r
468	for(top = 0; top < 64; ++top) {\r
469	*o += 1 << 21;\r
470	*e += (!(top & 7) + 1) << 21;\r
471	s = check_pfx_parity(pfx, rr, par, o, e, s);\r
472	}\r
473	\r
474	s->odd = s->even = 0;\r
475	out:\r
476	free(odd);\r
477	free(even);\r
478	return statelist;\r
479	}\r