[proxmark3-svn] / armsrc / crapto1.c

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