]> git.zerfleddert.de Git - proxmark3-svn/blame - client/nonce2key/crapto1.c
Added a utility script to convert a 'dumpdata.bin'-file into the 'eml'-format that...
[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
49 \r
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
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
99static 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
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
127static inline uint32_t*\r
128binsearch(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
143static inline void\r
144update_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
156static inline void\r
157extend_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
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
185static inline void\r
186extend_table_simple(uint32_t *tbl, uint32_t **end, int bit)\r
187{\r
9492e0b0 188 for(*tbl <<= 1; tbl <= *end; *++tbl <<= 1) \r
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
193 *tbl = tbl[-1] | 1;\r
9492e0b0 194 } else // drop\r
f89c7050
M
195 *tbl-- = *(*end)--;\r
196}\r
9492e0b0 197\r
198\r
f89c7050
M
199/** recover\r
200 * recursively narrow down the search space, 4 bits of keystream at a time\r
201 */\r
202static struct Crypto1State*\r
203recover(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
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
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
249struct 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
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
303\r
f89c7050
M
304\r
305out:\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
315static 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
318static 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
322static 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
327static 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
333static const uint32_t C1[] = { 0x846B5, 0x4235A, 0x211AD};\r
334static 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
338struct 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
408void 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
426void 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
435void 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
445static uint16_t *dist = 0;\r
446int 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
462static 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
476uint32_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
508static struct Crypto1State*\r
509brute_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
562struct Crypto1State*\r
b19bd5d6 563lfsr_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
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
583\r
b19bd5d6 584 s->odd = s->even = -1; \r
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
Impressum, Datenschutz