[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
	uint32_t tmp;\r
\r
	s->odd &= 0xffffff;\r
	tmp = s->odd;\r
	s->odd = s->even;\r
	s->even = tmp;\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
	{\r
				free(statelist);\r
				free(odd);\r
				free(even);\r
				return 0;\r
	}\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
9cefee6f	49	\r
9492e0b0	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
9cefee6f	58	\r
9492e0b0	59	start[0] = estart;\r
	60	stop[0] = estop;\r
	61	start[1] = ostart;\r
	62	stop[1] = ostop;\r
9cefee6f	63	\r
9492e0b0	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
9cefee6f	70	\r
9492e0b0	71	// sort the lists into the buckets based on the MSB (contribution bits)\r
9cefee6f	72	for (uint32_t i = 0; i < 2; i++) {\r
9492e0b0	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
9cefee6f	79	\r
9492e0b0	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
9492e0b0	150	}\r
9492e0b0	151	}\r
9cefee6f	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
9cefee6f	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
9cefee6f	209	\r
9492e0b0	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
9cefee6f	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
9cefee6f	254	\r
9492e0b0	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
9cefee6f	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
9cefee6f	385	uint32_t tmp;\r
f89c7050 M	386	\r
f89c7050 M	387	s->odd &= 0xffffff;\r
9cefee6f	388	tmp = s->odd;\r
	389	s->odd = s->even;\r
	390	s->even = tmp;\r
f89c7050 M	391	\r
	392	out = s->even & 1;\r
	393	out ^= LF_POLY_EVEN & (s->even >>= 1);\r
	394	out ^= LF_POLY_ODD & s->odd;\r
	395	out ^= !!in;\r
	396	out ^= filter(s->odd) & !!fb;\r
	397	\r
	398	s->even \|= parity(out) << 23;\r
	399	}\r
	400	/** lfsr_rollback_byte\r
	401	* Rollback the shift register in order to get previous states\r
	402	*/\r
	403	void lfsr_rollback_byte(struct Crypto1State *s, uint32_t in, int fb)\r
	404	{\r
	405	int i;\r
	406	for (i = 7; i >= 0; --i)\r
	407	lfsr_rollback_bit(s, BEBIT(in, i), fb);\r
	408	}\r
	409	/** lfsr_rollback_word\r
	410	* Rollback the shift register in order to get previous states\r
	411	*/\r
	412	void lfsr_rollback_word(struct Crypto1State *s, uint32_t in, int fb)\r
	413	{\r
	414	int i;\r
	415	for (i = 31; i >= 0; --i)\r
	416	lfsr_rollback_bit(s, BEBIT(in, i), fb);\r
	417	}\r
	418	\r
	419	/** nonce_distance\r
	420	* x,y valid tag nonces, then prng_successor(x, nonce_distance(x, y)) = y\r
	421	*/\r
	422	static uint16_t *dist = 0;\r
	423	int nonce_distance(uint32_t from, uint32_t to)\r
	424	{\r
	425	uint16_t x, i;\r
	426	if(!dist) {\r
	427	dist = malloc(2 << 16);\r
	428	if(!dist)\r
	429	return -1;\r
	430	for (x = i = 1; i; ++i) {\r
	431	dist[(x & 0xff) << 8 \| x >> 8] = i;\r
	432	x = x >> 1 \| (x ^ x >> 2 ^ x >> 3 ^ x >> 5) << 15;\r
	433	}\r
	434	}\r
	435	return (65535 + dist[to >> 16] - dist[from >> 16]) % 65535;\r
	436	}\r
	437	\r
	438	\r
	439	static uint32_t fastfwd[2][8] = {\r
	440	{ 0, 0x4BC53, 0xECB1, 0x450E2, 0x25E29, 0x6E27A, 0x2B298, 0x60ECB},\r
	441	{ 0, 0x1D962, 0x4BC53, 0x56531, 0xECB1, 0x135D3, 0x450E2, 0x58980}};\r
	442	\r
	443	\r
	444	/** lfsr_prefix_ks\r
	445	*\r
	446	* Is an exported helper function from the common prefix attack\r
	447	* Described in the "dark side" paper. It returns an -1 terminated array\r
	448	* of possible partial(21 bit) secret state.\r
	449	* The required keystream(ks) needs to contain the keystream that was used to\r
	450	* encrypt the NACK which is observed when varying only the 4 last bits of Nr\r
	451	* only correct iff [NR_3] ^ NR_3 does not depend on Nr_3\r
	452	*/\r
	453	uint32_t *lfsr_prefix_ks(uint8_t ks[8], int isodd)\r
	454	{\r
455	uint32_t *candidates = malloc(4 << 21);\r
456	uint32_t c, entry;\r
457	int size, i;\r
458	\r
459	if(!candidates)\r
460	return 0;\r
461	\r
462	size = (1 << 21) - 1;\r
463	for(i = 0; i <= size; ++i)\r
464	candidates[i] = i;\r
465	\r
466	for(c = 0; c < 8; ++c)\r
467	for(i = 0;i <= size; ++i) {\r
468	entry = candidates[i] ^ fastfwd[isodd][c];\r
469	\r
470	if(filter(entry >> 1) == BIT(ks[c], isodd))\r
471	if(filter(entry) == BIT(ks[c], isodd + 2))\r
472	continue;\r
473	\r
474	candidates[i--] = candidates[size--];\r
475	}\r
476	\r
477	candidates[size + 1] = -1;\r
478	\r
479	return candidates;\r
480	}\r
481	\r
482	/** brute_top\r
483	* helper function which eliminates possible secret states using parity bits\r
484	*/\r
485	static struct Crypto1State*\r
486	brute_top(uint32_t prefix, uint32_t rresp, unsigned char parities[8][8],\r
b19bd5d6	487	uint32_t odd, uint32_t even, struct Crypto1State* sl, uint8_t no_chk)\r
f89c7050 M	488	{\r
	489	struct Crypto1State s;\r
	490	uint32_t ks1, nr, ks2, rr, ks3, good, c;\r
	491	\r
	492	for(c = 0; c < 8; ++c) {\r
	493	s.odd = odd ^ fastfwd[1][c];\r
	494	s.even = even ^ fastfwd[0][c];\r
9cefee6f	495	\r
f89c7050 M	496	lfsr_rollback_bit(&s, 0, 0);\r
	497	lfsr_rollback_bit(&s, 0, 0);\r
	498	lfsr_rollback_bit(&s, 0, 0);\r
9cefee6f	499	\r
f89c7050 M	500	lfsr_rollback_word(&s, 0, 0);\r
f89c7050 M	501	lfsr_rollback_word(&s, prefix \| c << 5, 1);\r
9cefee6f	502	\r
f89c7050 M	503	sl->odd = s.odd;\r
f89c7050 M	504	sl->even = s.even;\r
9cefee6f	505	\r
b19bd5d6	506	if (no_chk)\r
b19bd5d6	507	break;\r
9cefee6f	508	\r
f89c7050 M	509	ks1 = crypto1_word(&s, prefix \| c << 5, 1);\r
	510	ks2 = crypto1_word(&s,0,0);\r
	511	ks3 = crypto1_word(&s, 0,0);\r
	512	nr = ks1 ^ (prefix \| c << 5);\r
	513	rr = ks2 ^ rresp;\r
	514	\r
	515	good = 1;\r
	516	good &= parity(nr & 0x000000ff) ^ parities[c][3] ^ BIT(ks2, 24);\r
	517	good &= parity(rr & 0xff000000) ^ parities[c][4] ^ BIT(ks2, 16);\r
	518	good &= parity(rr & 0x00ff0000) ^ parities[c][5] ^ BIT(ks2, 8);\r
	519	good &= parity(rr & 0x0000ff00) ^ parities[c][6] ^ BIT(ks2, 0);\r
	520	good &= parity(rr & 0x000000ff) ^ parities[c][7] ^ BIT(ks3, 24);\r
	521	\r
	522	if(!good)\r
	523	return sl;\r
	524	}\r
	525	\r
	526	return ++sl;\r
9cefee6f	527	}\r
f89c7050 M	528	\r
	529	\r
	530	/** lfsr_common_prefix\r
	531	* Implentation of the common prefix attack.\r
	532	* Requires the 28 bit constant prefix used as reader nonce (pfx)\r
	533	* The reader response used (rr)\r
	534	* The keystream used to encrypt the observed NACK's (ks)\r
	535	* The parity bits (par)\r
	536	* It returns a zero terminated list of possible cipher states after the\r
	537	* tag nonce was fed in\r
	538	*/\r
	539	struct Crypto1State*\r
b19bd5d6	540	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	541	{\r
	542	struct Crypto1State statelist, s;\r
	543	uint32_t odd, even, o, e, top;\r
	544	\r
	545	odd = lfsr_prefix_ks(ks, 1);\r
	546	even = lfsr_prefix_ks(ks, 0);\r
	547	\r
9cefee6f	548	statelist = malloc((sizeof *statelist) << 21); //how large should be?\r
f89c7050	549	if(!statelist \|\| !odd \|\| !even)\r
a61b4976	550	{\r
90e278d3 MHS	551	free(statelist);\r
	552	free(odd);\r
	553	free(even);\r
9cefee6f	554	return 0;\r
a61b4976	555	}\r
f89c7050	556	\r
f89c7050	557	s = statelist;\r
b19bd5d6	558	for(o = odd; *o != -1; ++o)\r
b19bd5d6	559	for(e = even; *e != -1; ++e)\r
f89c7050 M	560	for(top = 0; top < 64; ++top) {\r
	561	o = (o & 0x1fffff) \| (top << 21);\r
	562	e = (e & 0x1fffff) \| (top >> 3) << 21;\r
b19bd5d6	563	s = brute_top(pfx, rr, par, o, e, s, no_par);\r
f89c7050 M	564	}\r
f89c7050 M	565	\r
9cefee6f	566	s->odd = s->even = -1;\r
b19bd5d6	567	//printf("state count = %d\n",s-statelist);\r
f89c7050 M	568	\r
	569	free(odd);\r
	570	free(even);\r
	571	\r
	572	return statelist;\r
	573	}\r