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