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