]> cvs.zerfleddert.de Git - proxmark3-svn/blame - client/nonce2key/crapto1.c
projects / proxmark3-svn / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
Merge branch 'master' of https://github.com/Proxmark/proxmark3
[proxmark3-svn] / client / nonce2key / crapto1.c
CommitLineData
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
24static uint8_t filterlut[1 << 20];\r
25static 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
36typedef struct bucket {\r
37 uint32_t *head;\r
38 uint32_t *bp;\r
39} bucket_t;\r
40\r
41typedef bucket_t bucket_array_t[2][0x100];\r
42\r
43typedef 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
51static 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
101static inline uint32_t*\r
102binsearch(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
117static inline void\r
118update_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
130static inline void\r
131extend_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
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
159static inline void\r
160extend_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
167 *tbl = tbl[-1] | 1;\r
9492e0b0 168 } else // drop\r
f89c7050
M		 169 *tbl-- = *(*end)--;\r
170}\r
9492e0b0 171\r
172\r
f89c7050
M		 173/** recover\r
174 * recursively narrow down the search space, 4 bits of keystream at a time\r
175 */\r
176static struct Crypto1State*\r
177recover(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
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
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
223struct 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
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
9492e0b0 254 // initialize statelists: add all possible states which would result into the rightmost 2 bits of the keystream\r
f89c7050
M		 255 for(i = 1 << 20; i >= 0; --i) {\r
256 if(filter(i) == (oks & 1))\r
257 *++odd_tail = i;\r
258 if(filter(i) == (eks & 1))\r
259 *++even_tail = i;\r
260 }\r
261\r
9492e0b0 262 // extend the statelists. Look at the next 8 Bits of the keystream (4 Bit each odd and even):\r
f89c7050
M		 263 for(i = 0; i < 4; i++) {\r
264 extend_table_simple(odd_head, &odd_tail, (oks >>= 1) & 1);\r
265 extend_table_simple(even_head, &even_tail, (eks >>= 1) & 1);\r
266 }\r
267\r
9492e0b0 268 // the statelists now contain all states which could have generated the last 10 Bits of the keystream.\r
269 // 22 bits to go to recover 32 bits in total. From now on, we need to take the "in"\r
270 // parameter into account.\r
271\r
272 in = (in >> 16 & 0xff) | (in << 16) | (in & 0xff00); // Byte swapping\r
273\r
bcf61bd3 274 recover(odd_head, odd_tail, oks, even_head, even_tail, eks, 11, statelist, in << 1, bucket);\r
f89c7050
M		 275\r
276out:\r
277 free(odd_head);\r
278 free(even_head);\r
9492e0b0 279 for (uint32_t i = 0; i < 2; i++)\r
280 for (uint32_t j = 0; j <= 0xff; j++)\r
281 free(bucket[i][j].head);\r
9cefee6f 282\r
f89c7050
M		 283 return statelist;\r
284}\r
285\r
286static const uint32_t S1[] = { 0x62141, 0x310A0, 0x18850, 0x0C428, 0x06214,\r
287 0x0310A, 0x85E30, 0xC69AD, 0x634D6, 0xB5CDE, 0xDE8DA, 0x6F46D, 0xB3C83,\r
288 0x59E41, 0xA8995, 0xD027F, 0x6813F, 0x3409F, 0x9E6FA};\r
289static const uint32_t S2[] = { 0x3A557B00, 0x5D2ABD80, 0x2E955EC0, 0x174AAF60,\r
290 0x0BA557B0, 0x05D2ABD8, 0x0449DE68, 0x048464B0, 0x42423258, 0x278192A8,\r
291 0x156042D0, 0x0AB02168, 0x43F89B30, 0x61FC4D98, 0x765EAD48, 0x7D8FDD20,\r
292 0x7EC7EE90, 0x7F63F748, 0x79117020};\r
293static const uint32_t T1[] = {\r
294 0x4F37D, 0x279BE, 0x97A6A, 0x4BD35, 0x25E9A, 0x12F4D, 0x097A6, 0x80D66,\r
295 0xC4006, 0x62003, 0xB56B4, 0x5AB5A, 0xA9318, 0xD0F39, 0x6879C, 0xB057B,\r
296 0x582BD, 0x2C15E, 0x160AF, 0x8F6E2, 0xC3DC4, 0xE5857, 0x72C2B, 0x39615,\r
297 0x98DBF, 0xC806A, 0xE0680, 0x70340, 0x381A0, 0x98665, 0x4C332, 0xA272C};\r
298static const uint32_t T2[] = { 0x3C88B810, 0x5E445C08, 0x2982A580, 0x14C152C0,\r
299 0x4A60A960, 0x253054B0, 0x52982A58, 0x2FEC9EA8, 0x1156C4D0, 0x08AB6268,\r
300 0x42F53AB0, 0x217A9D58, 0x161DC528, 0x0DAE6910, 0x46D73488, 0x25CB11C0,\r
301 0x52E588E0, 0x6972C470, 0x34B96238, 0x5CFC3A98, 0x28DE96C8, 0x12CFC0E0,\r
302 0x4967E070, 0x64B3F038, 0x74F97398, 0x7CDC3248, 0x38CE92A0, 0x1C674950,\r
303 0x0E33A4A8, 0x01B959D0, 0x40DCACE8, 0x26CEDDF0};\r
304static const uint32_t C1[] = { 0x846B5, 0x4235A, 0x211AD};\r
305static const uint32_t C2[] = { 0x1A822E0, 0x21A822E0, 0x21A822E0};\r
306/** Reverse 64 bits of keystream into possible cipher states\r
307 * Variation mentioned in the paper. Somewhat optimized version\r
308 */\r
309struct Crypto1State* lfsr_recovery64(uint32_t ks2, uint32_t ks3)\r
310{\r
311 struct Crypto1State *statelist, *sl;\r
312 uint8_t oks[32], eks[32], hi[32];\r
313 uint32_t low = 0, win = 0;\r
314 uint32_t *tail, table[1 << 16];\r
315 int i, j;\r
316\r
317 sl = statelist = malloc(sizeof(struct Crypto1State) << 4);\r
318 if(!sl)\r
319 return 0;\r
320 sl->odd = sl->even = 0;\r
321\r
322 for(i = 30; i >= 0; i -= 2) {\r
323 oks[i >> 1] = BIT(ks2, i ^ 24);\r
324 oks[16 + (i >> 1)] = BIT(ks3, i ^ 24);\r
325 }\r
326 for(i = 31; i >= 0; i -= 2) {\r
327 eks[i >> 1] = BIT(ks2, i ^ 24);\r
328 eks[16 + (i >> 1)] = BIT(ks3, i ^ 24);\r
329 }\r
330\r
331 for(i = 0xfffff; i >= 0; --i) {\r
332 if (filter(i) != oks[0])\r
333 continue;\r
334\r
335 *(tail = table) = i;\r
336 for(j = 1; tail >= table && j < 29; ++j)\r
337 extend_table_simple(table, &tail, oks[j]);\r
338\r
339 if(tail < table)\r
340 continue;\r
341\r
342 for(j = 0; j < 19; ++j)\r
343 low = low << 1 | parity(i & S1[j]);\r
344 for(j = 0; j < 32; ++j)\r
345 hi[j] = parity(i & T1[j]);\r
346\r
347 for(; tail >= table; --tail) {\r
348 for(j = 0; j < 3; ++j) {\r
349 *tail = *tail << 1;\r
350 *tail |= parity((i & C1[j]) ^ (*tail & C2[j]));\r
351 if(filter(*tail) != oks[29 + j])\r
352 goto continue2;\r
353 }\r
354\r
355 for(j = 0; j < 19; ++j)\r
356 win = win << 1 | parity(*tail & S2[j]);\r
357\r
358 win ^= low;\r
359 for(j = 0; j < 32; ++j) {\r
360 win = win << 1 ^ hi[j] ^ parity(*tail & T2[j]);\r
361 if(filter(win) != eks[j])\r
362 goto continue2;\r
363 }\r
364\r
365 *tail = *tail << 1 | parity(LF_POLY_EVEN & *tail);\r
366 sl->odd = *tail ^ parity(LF_POLY_ODD & win);\r
367 sl->even = win;\r
368 ++sl;\r
369 sl->odd = sl->even = 0;\r
370 continue2:;\r
371 }\r
372 }\r
373 return statelist;\r
374}\r
375\r
376/** lfsr_rollback_bit\r
377 * Rollback the shift register in order to get previous states\r
378 */\r
379void lfsr_rollback_bit(struct Crypto1State *s, uint32_t in, int fb)\r
380{\r
381 int out;\r
9cefee6f 382 uint32_t tmp;\r
f89c7050
M		 383\r
384 s->odd &= 0xffffff;\r
9cefee6f 385 tmp = s->odd;\r
386 s->odd = s->even;\r
387 s->even = tmp;\r
f89c7050
M		 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
400void 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
409void 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
419static uint16_t *dist = 0;\r
420int 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
436static 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
450uint32_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
482static struct Crypto1State*\r
483brute_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
9cefee6f 492\r
f89c7050
M		 493 lfsr_rollback_bit(&s, 0, 0);\r
494 lfsr_rollback_bit(&s, 0, 0);\r
495 lfsr_rollback_bit(&s, 0, 0);\r
9cefee6f 496\r
f89c7050
M		 497 lfsr_rollback_word(&s, 0, 0);\r
498 lfsr_rollback_word(&s, prefix | c << 5, 1);\r
9cefee6f 499\r
f89c7050
M		 500 sl->odd = s.odd;\r
501 sl->even = s.even;\r
9cefee6f 502\r
b19bd5d6 503 if (no_chk)\r
504 break;\r
9cefee6f 505\r
f89c7050
M		 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
9cefee6f 524}\r
f89c7050
M		 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
bcf61bd3 536struct Crypto1State* 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		 537{\r
538 struct Crypto1State *statelist, *s;\r
539 uint32_t *odd, *even, *o, *e, top;\r
540\r
541 odd = lfsr_prefix_ks(ks, 1);\r
542 even = lfsr_prefix_ks(ks, 0);\r
543\r
9cefee6f 544 statelist = malloc((sizeof *statelist) << 21); //how large should be?\r
f89c7050 545 if(!statelist || !odd || !even)\r
a61b4976 546 {\r
bcf61bd3 547 free(statelist);\r
548 free(odd);\r
549 free(even);\r
550 return 0;\r
a61b4976 551 }\r
f89c7050 552\r
f89c7050 553 s = statelist;\r
b19bd5d6 554 for(o = odd; *o != -1; ++o)\r
555 for(e = even; *e != -1; ++e)\r
f89c7050
M		 556 for(top = 0; top < 64; ++top) {\r
557 *o = (*o & 0x1fffff) | (top << 21);\r
558 *e = (*e & 0x1fffff) | (top >> 3) << 21;\r
b19bd5d6 559 s = brute_top(pfx, rr, par, *o, *e, s, no_par);\r
f89c7050
M		 560 }\r
561\r
9cefee6f 562 s->odd = s->even = -1;\r
b19bd5d6 563 //printf("state count = %d\n",s-statelist);\r
f89c7050
M		 564\r
565 free(odd);\r
566 free(even);\r
567\r
568 return statelist;\r
569}\r
bcf61bd3 570\r
571/*\r
572struct Crypto1State* lfsr_common_prefix(uint32_t pfx, uint32_t rr, uint8_t ks[8], uint8_t par[8][8], uint8_t no_par, uint32_t nt, uint32_t uid)\r
573{\r
574 long long int amount = 0;\r
575 struct Crypto1State *statelist, *s;\r
576 uint32_t *odd, *even, *o, *e, top;\r
577\r
578 odd = lfsr_prefix_ks(ks, 1);\r
579 even = lfsr_prefix_ks(ks, 0);\r
580\r
581 s = statelist = malloc((sizeof *statelist) << 20);\r
582 if(!s || !odd || !even) {\r
583 free(odd);\r
584 free(even);\r
585 free(statelist);\r
586 return 0;\r
587 }\r
588\r
589 char filename[50] = "archivo.txt";\r
590 sprintf(filename, "logs/%x.txt", nt);\r
591 PrintAndLog("Name: %s\n", filename);\r
592 FILE *file = fopen(filename,"w+");\r
593 if ( !file ) {\r
594 s->odd = s->even = 0;\r
595 free(odd);\r
596 free(even);\r
597 PrintAndLog("Failed to create file");\r
598 return 0;\r
599 }\r
600 PrintAndLog("Creating file... ");\r
601 uint32_t xored = uid^nt;\r
602 \r
603 int lastOdd = 0;\r
604 for(o = odd; *o + 1; ++o)\r
605 for(e = even; *e + 1; ++e)\r
606 for(top = 0; top < 64; ++top) {\r
607 *o += 1 << 21;\r
608 *e += (!(top & 7) + 1) << 21;\r
609\r
610 //added by MG\r
611 if(lastOdd != statelist->odd){\r
612 // Here I create a temporal crypto1 state, \r
613 // where I load the odd and even state and work with it,\r
614 // in order not to interfere with regular mechanism, This is what I save to file\r
615 struct Crypto1State *state;\r
616 lastOdd = state->odd = statelist->odd; state->even = statelist->even;\r
617 lfsr_rollback_word(state,xored,0);\r
618 fprintf(file,"%x %x \n",state->odd,state->even);\r
619 amount++;\r
620 }\r
621 //s = check_pfx_parity(pfx, rr, par, *o, *e, s); //This is not useful at all when attacking chineese cards\r
622 s = brute_top(pfx, rr, par, *o, *e, s, no_par); \r
623 }\r
624\r
625 PrintAndLog("File created, amount %u\n",amount);\r
626 fclose(file);\r
627 s->odd = s->even = 0;\r
628 free(odd);\r
629 free(even);\r
630 return statelist;\r
631}\r
632 */\r
Proxmark3 GIT tracking
Impressum, Datenschutz