/* 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
+ 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
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
+ 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
} bucket_info[2][0x100];\r
uint32_t numbuckets;\r
} bucket_info_t;\r
- \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
uint32_t *p1, *p2;\r
uint32_t *start[2];\r
uint32_t *stop[2];\r
- \r
+\r
start[0] = estart;\r
stop[0] = estop;\r
start[1] = ostart;\r
stop[1] = ostop;\r
- \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
+\r
// sort the lists into the buckets based on the MSB (contribution bits)\r
- for (uint32_t i = 0; i < 2; i++) { \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
+\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
}\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
*p ^= in;\r
} else { // drop\r
*p-- = *(*end)--;\r
- } \r
+ }\r
}\r
- \r
+\r
}\r
\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
+ 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
}\r
\r
bucket_sort_intersect(e_head, e_tail, o_head, o_tail, &bucket_info, bucket);\r
- \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
+ bucket_info.bucket_info[0][i].head, bucket_info.bucket_info[0][i].tail, eks,\r
rem, sl, in, bucket);\r
}\r
- \r
+\r
return sl;\r
}\r
/** lfsr_recovery\r
}\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
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
+\r
return statelist;\r
}\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
- s->odd ^= (s->odd ^= s->even, s->even ^= s->odd);\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
*/\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)\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
for(c = 0; c < 8; ++c) {\r
s.odd = odd ^ fastfwd[1][c];\r
s.even = even ^ fastfwd[0][c];\r
- \r
+\r
lfsr_rollback_bit(&s, 0, 0);\r
lfsr_rollback_bit(&s, 0, 0);\r
lfsr_rollback_bit(&s, 0, 0);\r
- \r
+\r
lfsr_rollback_word(&s, 0, 0);\r
lfsr_rollback_word(&s, prefix | c << 5, 1);\r
- \r
+\r
sl->odd = s.odd;\r
sl->even = s.even;\r
- \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
}\r
\r
return ++sl;\r
-} \r
+}\r
\r
\r
/** lfsr_common_prefix\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])\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
odd = lfsr_prefix_ks(ks, 1);\r
even = lfsr_prefix_ks(ks, 0);\r
\r
- statelist = malloc((sizeof *statelist) << 20);\r
+ statelist = malloc((sizeof *statelist) << 21); //how large should be?\r
if(!statelist || !odd || !even)\r
- return 0;\r
-\r
+ {\r
+ free(statelist);\r
+ free(odd);\r
+ free(even);\r
+ return 0;\r
+ }\r
\r
s = statelist;\r
- for(o = odd; *o != 0xffffffff; ++o)\r
- for(e = even; *e != 0xffffffff; ++e)\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);\r
+ s = brute_top(pfx, rr, par, *o, *e, s, no_par);\r
}\r
\r
- s->odd = s->even = 0;\r
+ s->odd = s->even = -1;\r
+ //printf("state count = %d\n",s-statelist);\r
\r
free(odd);\r
free(even);\r
projects / proxmark3-svn / blobdiff