]> git.zerfleddert.de Git - proxmark3-svn/blob - tools/mfkey/crapto1.c
Update README.md
[proxmark3-svn] / tools / mfkey / crapto1.c
1 /* crapto1.c
2
3 This program is free software; you can redistribute it and/or
4 modify it under the terms of the GNU General Public License
5 as published by the Free Software Foundation; either version 2
6 of the License, or (at your option) any later version.
7
8 This program is distributed in the hope that it will be useful,
9 but WITHOUT ANY WARRANTY; without even the implied warranty of
10 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 GNU General Public License for more details.
12
13 You should have received a copy of the GNU General Public License
14 along with this program; if not, write to the Free Software
15 Foundation, Inc., 51 Franklin Street, Fifth Floor,
16 Boston, MA 02110-1301, US$
17
18 Copyright (C) 2008-2014 bla <blapost@gmail.com>
19 */
20 #include "crapto1.h"
21 #include <stdlib.h>
22
23 #if !defined LOWMEM && defined __GNUC__
24 static uint8_t filterlut[1 << 20];
25 static void __attribute__((constructor)) fill_lut()
26 {
27 uint32_t i;
28 for(i = 0; i < 1 << 20; ++i)
29 filterlut[i] = filter(i);
30 }
31 #define filter(x) (filterlut[(x) & 0xfffff])
32 #endif
33
34
35
36 typedef struct bucket {
37 uint32_t *head;
38 uint32_t *bp;
39 } bucket_t;
40
41 typedef bucket_t bucket_array_t[2][0x100];
42
43 typedef struct bucket_info {
44 struct {
45 uint32_t *head, *tail;
46 } bucket_info[2][0x100];
47 uint32_t numbuckets;
48 } bucket_info_t;
49
50
51 static void bucket_sort_intersect(uint32_t* const estart, uint32_t* const estop,
52 uint32_t* const ostart, uint32_t* const ostop,
53 bucket_info_t *bucket_info, bucket_array_t bucket)
54 {
55 uint32_t *p1, *p2;
56 uint32_t *start[2];
57 uint32_t *stop[2];
58
59 start[0] = estart;
60 stop[0] = estop;
61 start[1] = ostart;
62 stop[1] = ostop;
63
64 // init buckets to be empty
65 for (uint32_t i = 0; i < 2; i++) {
66 for (uint32_t j = 0x00; j <= 0xff; j++) {
67 bucket[i][j].bp = bucket[i][j].head;
68 }
69 }
70
71 // sort the lists into the buckets based on the MSB (contribution bits)
72 for (uint32_t i = 0; i < 2; i++) {
73 for (p1 = start[i]; p1 <= stop[i]; p1++) {
74 uint32_t bucket_index = (*p1 & 0xff000000) >> 24;
75 *(bucket[i][bucket_index].bp++) = *p1;
76 }
77 }
78
79
80 // write back intersecting buckets as sorted list.
81 // fill in bucket_info with head and tail of the bucket contents in the list and number of non-empty buckets.
82 uint32_t nonempty_bucket;
83 for (uint32_t i = 0; i < 2; i++) {
84 p1 = start[i];
85 nonempty_bucket = 0;
86 for (uint32_t j = 0x00; j <= 0xff; j++) {
87 if (bucket[0][j].bp != bucket[0][j].head && bucket[1][j].bp != bucket[1][j].head) { // non-empty intersecting buckets only
88 bucket_info->bucket_info[i][nonempty_bucket].head = p1;
89 for (p2 = bucket[i][j].head; p2 < bucket[i][j].bp; *p1++ = *p2++);
90 bucket_info->bucket_info[i][nonempty_bucket].tail = p1 - 1;
91 nonempty_bucket++;
92 }
93 }
94 bucket_info->numbuckets = nonempty_bucket;
95 }
96 }
97
98
99 /** update_contribution
100 * helper, calculates the partial linear feedback contributions and puts in MSB
101 */
102 static inline void update_contribution(uint32_t *item, const uint32_t mask1, const uint32_t mask2)
103 {
104 uint32_t p = *item >> 25;
105
106 p = p << 1 | parity(*item & mask1);
107 p = p << 1 | parity(*item & mask2);
108 *item = p << 24 | (*item & 0xffffff);
109 }
110
111 /** extend_table
112 * using a bit of the keystream extend the table of possible lfsr states
113 */
114 static inline void extend_table(uint32_t *tbl, uint32_t **end, int bit, int m1, int m2, uint32_t in)
115 {
116 in <<= 24;
117 for(*tbl <<= 1; tbl <= *end; *++tbl <<= 1)
118 if(filter(*tbl) ^ filter(*tbl | 1)) {
119 *tbl |= filter(*tbl) ^ bit;
120 update_contribution(tbl, m1, m2);
121 *tbl ^= in;
122 } else if(filter(*tbl) == bit) {
123 *++*end = tbl[1];
124 tbl[1] = tbl[0] | 1;
125 update_contribution(tbl, m1, m2);
126 *tbl++ ^= in;
127 update_contribution(tbl, m1, m2);
128 *tbl ^= in;
129 } else
130 *tbl-- = *(*end)--;
131 }
132 /** extend_table_simple
133 * using a bit of the keystream extend the table of possible lfsr states
134 */
135 static inline void extend_table_simple(uint32_t *tbl, uint32_t **end, int bit)
136 {
137 for(*tbl <<= 1; tbl <= *end; *++tbl <<= 1) {
138 if(filter(*tbl) ^ filter(*tbl | 1)) { // replace
139 *tbl |= filter(*tbl) ^ bit;
140 } else if(filter(*tbl) == bit) { // insert
141 *++*end = *++tbl;
142 *tbl = tbl[-1] | 1;
143 } else { // drop
144 *tbl-- = *(*end)--;
145 }
146 }
147 }
148 /** recover
149 * recursively narrow down the search space, 4 bits of keystream at a time
150 */
151 static struct Crypto1State*
152 recover(uint32_t *o_head, uint32_t *o_tail, uint32_t oks,
153 uint32_t *e_head, uint32_t *e_tail, uint32_t eks, int rem,
154 struct Crypto1State *sl, uint32_t in, bucket_array_t bucket)
155 {
156 uint32_t *o, *e;
157 bucket_info_t bucket_info;
158
159 if(rem == -1) {
160 for(e = e_head; e <= e_tail; ++e) {
161 *e = *e << 1 ^ parity(*e & LF_POLY_EVEN) ^ !!(in & 4);
162 for(o = o_head; o <= o_tail; ++o, ++sl) {
163 sl->even = *o;
164 sl->odd = *e ^ parity(*o & LF_POLY_ODD);
165 sl[1].odd = sl[1].even = 0;
166 }
167 }
168 return sl;
169 }
170
171 for(uint32_t i = 0; i < 4 && rem--; i++) {
172 oks >>= 1;
173 eks >>= 1;
174 in >>= 2;
175 extend_table(o_head, &o_tail, oks & 1, LF_POLY_EVEN << 1 | 1, LF_POLY_ODD << 1, 0);
176 if(o_head > o_tail)
177 return sl;
178
179 extend_table(e_head, &e_tail, eks & 1, LF_POLY_ODD, LF_POLY_EVEN << 1 | 1, in & 3);
180 if(e_head > e_tail)
181 return sl;
182 }
183
184 bucket_sort_intersect(e_head, e_tail, o_head, o_tail, &bucket_info, bucket);
185
186 for (int i = bucket_info.numbuckets - 1; i >= 0; i--) {
187 sl = recover(bucket_info.bucket_info[1][i].head, bucket_info.bucket_info[1][i].tail, oks,
188 bucket_info.bucket_info[0][i].head, bucket_info.bucket_info[0][i].tail, eks,
189 rem, sl, in, bucket);
190 }
191
192 return sl;
193 }
194 /** lfsr_recovery
195 * recover the state of the lfsr given 32 bits of the keystream
196 * additionally you can use the in parameter to specify the value
197 * that was fed into the lfsr at the time the keystream was generated
198 */
199 struct Crypto1State* lfsr_recovery32(uint32_t ks2, uint32_t in)
200 {
201 struct Crypto1State *statelist;
202 uint32_t *odd_head = 0, *odd_tail = 0, oks = 0;
203 uint32_t *even_head = 0, *even_tail = 0, eks = 0;
204 int i;
205
206 // split the keystream into an odd and even part
207 for(i = 31; i >= 0; i -= 2)
208 oks = oks << 1 | BEBIT(ks2, i);
209 for(i = 30; i >= 0; i -= 2)
210 eks = eks << 1 | BEBIT(ks2, i);
211
212 odd_head = odd_tail = malloc(sizeof(uint32_t) << 21);
213 even_head = even_tail = malloc(sizeof(uint32_t) << 21);
214 statelist = malloc(sizeof(struct Crypto1State) << 18);
215 if(!odd_tail-- || !even_tail-- || !statelist) {
216 free(statelist);
217 statelist = 0;
218 goto out;
219 }
220
221 statelist->odd = statelist->even = 0;
222
223 // allocate memory for out of place bucket_sort
224 bucket_array_t bucket;
225
226 for (uint32_t i = 0; i < 2; i++) {
227 for (uint32_t j = 0; j <= 0xff; j++) {
228 bucket[i][j].head = malloc(sizeof(uint32_t)<<14);
229 if (!bucket[i][j].head) {
230 goto out;
231 }
232 }
233 }
234
235 // initialize statelists: add all possible states which would result into the rightmost 2 bits of the keystream
236 for(i = 1 << 20; i >= 0; --i) {
237 if(filter(i) == (oks & 1))
238 *++odd_tail = i;
239 if(filter(i) == (eks & 1))
240 *++even_tail = i;
241 }
242
243 // extend the statelists. Look at the next 8 Bits of the keystream (4 Bit each odd and even):
244 for(i = 0; i < 4; i++) {
245 extend_table_simple(odd_head, &odd_tail, (oks >>= 1) & 1);
246 extend_table_simple(even_head, &even_tail, (eks >>= 1) & 1);
247 }
248
249 // the statelists now contain all states which could have generated the last 10 Bits of the keystream.
250 // 22 bits to go to recover 32 bits in total. From now on, we need to take the "in"
251 // parameter into account.
252 in = (in >> 16 & 0xff) | (in << 16) | (in & 0xff00); // Byte swapping
253 recover(odd_head, odd_tail, oks, even_head, even_tail, eks, 11, statelist, in << 1, bucket);
254
255 out:
256 for (uint32_t i = 0; i < 2; i++)
257 for (uint32_t j = 0; j <= 0xff; j++)
258 free(bucket[i][j].head);
259 free(odd_head);
260 free(even_head);
261 return statelist;
262 }
263
264 static const uint32_t S1[] = { 0x62141, 0x310A0, 0x18850, 0x0C428, 0x06214,
265 0x0310A, 0x85E30, 0xC69AD, 0x634D6, 0xB5CDE, 0xDE8DA, 0x6F46D, 0xB3C83,
266 0x59E41, 0xA8995, 0xD027F, 0x6813F, 0x3409F, 0x9E6FA};
267 static const uint32_t S2[] = { 0x3A557B00, 0x5D2ABD80, 0x2E955EC0, 0x174AAF60,
268 0x0BA557B0, 0x05D2ABD8, 0x0449DE68, 0x048464B0, 0x42423258, 0x278192A8,
269 0x156042D0, 0x0AB02168, 0x43F89B30, 0x61FC4D98, 0x765EAD48, 0x7D8FDD20,
270 0x7EC7EE90, 0x7F63F748, 0x79117020};
271 static const uint32_t T1[] = {
272 0x4F37D, 0x279BE, 0x97A6A, 0x4BD35, 0x25E9A, 0x12F4D, 0x097A6, 0x80D66,
273 0xC4006, 0x62003, 0xB56B4, 0x5AB5A, 0xA9318, 0xD0F39, 0x6879C, 0xB057B,
274 0x582BD, 0x2C15E, 0x160AF, 0x8F6E2, 0xC3DC4, 0xE5857, 0x72C2B, 0x39615,
275 0x98DBF, 0xC806A, 0xE0680, 0x70340, 0x381A0, 0x98665, 0x4C332, 0xA272C};
276 static const uint32_t T2[] = { 0x3C88B810, 0x5E445C08, 0x2982A580, 0x14C152C0,
277 0x4A60A960, 0x253054B0, 0x52982A58, 0x2FEC9EA8, 0x1156C4D0, 0x08AB6268,
278 0x42F53AB0, 0x217A9D58, 0x161DC528, 0x0DAE6910, 0x46D73488, 0x25CB11C0,
279 0x52E588E0, 0x6972C470, 0x34B96238, 0x5CFC3A98, 0x28DE96C8, 0x12CFC0E0,
280 0x4967E070, 0x64B3F038, 0x74F97398, 0x7CDC3248, 0x38CE92A0, 0x1C674950,
281 0x0E33A4A8, 0x01B959D0, 0x40DCACE8, 0x26CEDDF0};
282 static const uint32_t C1[] = { 0x846B5, 0x4235A, 0x211AD};
283 static const uint32_t C2[] = { 0x1A822E0, 0x21A822E0, 0x21A822E0};
284 /** Reverse 64 bits of keystream into possible cipher states
285 * Variation mentioned in the paper. Somewhat optimized version
286 */
287 struct Crypto1State* lfsr_recovery64(uint32_t ks2, uint32_t ks3)
288 {
289 struct Crypto1State *statelist, *sl;
290 uint8_t oks[32], eks[32], hi[32];
291 uint32_t low = 0, win = 0;
292 uint32_t *tail, table[1 << 16];
293 int i, j;
294
295 sl = statelist = malloc(sizeof(struct Crypto1State) << 4);
296 if(!sl)
297 return 0;
298 sl->odd = sl->even = 0;
299
300 for(i = 30; i >= 0; i -= 2) {
301 oks[i >> 1] = BEBIT(ks2, i);
302 oks[16 + (i >> 1)] = BEBIT(ks3, i);
303 }
304 for(i = 31; i >= 0; i -= 2) {
305 eks[i >> 1] = BEBIT(ks2, i);
306 eks[16 + (i >> 1)] = BEBIT(ks3, i);
307 }
308
309 for(i = 0xfffff; i >= 0; --i) {
310 if (filter(i) != oks[0])
311 continue;
312
313 *(tail = table) = i;
314 for(j = 1; tail >= table && j < 29; ++j)
315 extend_table_simple(table, &tail, oks[j]);
316
317 if(tail < table)
318 continue;
319
320 for(j = 0; j < 19; ++j)
321 low = low << 1 | parity(i & S1[j]);
322 for(j = 0; j < 32; ++j)
323 hi[j] = parity(i & T1[j]);
324
325 for(; tail >= table; --tail) {
326 for(j = 0; j < 3; ++j) {
327 *tail = *tail << 1;
328 *tail |= parity((i & C1[j]) ^ (*tail & C2[j]));
329 if(filter(*tail) != oks[29 + j])
330 goto continue2;
331 }
332
333 for(j = 0; j < 19; ++j)
334 win = win << 1 | parity(*tail & S2[j]);
335
336 win ^= low;
337 for(j = 0; j < 32; ++j) {
338 win = win << 1 ^ hi[j] ^ parity(*tail & T2[j]);
339 if(filter(win) != eks[j])
340 goto continue2;
341 }
342
343 *tail = *tail << 1 | parity(LF_POLY_EVEN & *tail);
344 sl->odd = *tail ^ parity(LF_POLY_ODD & win);
345 sl->even = win;
346 ++sl;
347 sl->odd = sl->even = 0;
348 continue2:;
349 }
350 }
351 return statelist;
352 }
353
354 /** lfsr_rollback_bit
355 * Rollback the shift register in order to get previous states
356 */
357 uint8_t lfsr_rollback_bit(struct Crypto1State *s, uint32_t in, int fb)
358 {
359 int out;
360 uint8_t ret;
361 uint32_t t;
362
363 s->odd &= 0xffffff;
364 t = s->odd, s->odd = s->even, s->even = t;
365
366 out = s->even & 1;
367 out ^= LF_POLY_EVEN & (s->even >>= 1);
368 out ^= LF_POLY_ODD & s->odd;
369 out ^= !!in;
370 out ^= (ret = filter(s->odd)) & !!fb;
371
372 s->even |= parity(out) << 23;
373 return ret;
374 }
375 /** lfsr_rollback_byte
376 * Rollback the shift register in order to get previous states
377 */
378 uint8_t lfsr_rollback_byte(struct Crypto1State *s, uint32_t in, int fb)
379 {
380 /*
381 int i, ret = 0;
382 for (i = 7; i >= 0; --i)
383 ret |= lfsr_rollback_bit(s, BIT(in, i), fb) << i;
384 */
385 // unfold loop 20160112
386 uint8_t ret = 0;
387 ret |= lfsr_rollback_bit(s, BIT(in, 7), fb) << 7;
388 ret |= lfsr_rollback_bit(s, BIT(in, 6), fb) << 6;
389 ret |= lfsr_rollback_bit(s, BIT(in, 5), fb) << 5;
390 ret |= lfsr_rollback_bit(s, BIT(in, 4), fb) << 4;
391 ret |= lfsr_rollback_bit(s, BIT(in, 3), fb) << 3;
392 ret |= lfsr_rollback_bit(s, BIT(in, 2), fb) << 2;
393 ret |= lfsr_rollback_bit(s, BIT(in, 1), fb) << 1;
394 ret |= lfsr_rollback_bit(s, BIT(in, 0), fb) << 0;
395 return ret;
396 }
397 /** lfsr_rollback_word
398 * Rollback the shift register in order to get previous states
399 */
400 uint32_t lfsr_rollback_word(struct Crypto1State *s, uint32_t in, int fb)
401 {
402 /*
403 int i;
404 uint32_t ret = 0;
405 for (i = 31; i >= 0; --i)
406 ret |= lfsr_rollback_bit(s, BEBIT(in, i), fb) << (i ^ 24);
407 */
408 // unfold loop 20160112
409 uint32_t ret = 0;
410 ret |= lfsr_rollback_bit(s, BEBIT(in, 31), fb) << (31 ^ 24);
411 ret |= lfsr_rollback_bit(s, BEBIT(in, 30), fb) << (30 ^ 24);
412 ret |= lfsr_rollback_bit(s, BEBIT(in, 29), fb) << (29 ^ 24);
413 ret |= lfsr_rollback_bit(s, BEBIT(in, 28), fb) << (28 ^ 24);
414 ret |= lfsr_rollback_bit(s, BEBIT(in, 27), fb) << (27 ^ 24);
415 ret |= lfsr_rollback_bit(s, BEBIT(in, 26), fb) << (26 ^ 24);
416 ret |= lfsr_rollback_bit(s, BEBIT(in, 25), fb) << (25 ^ 24);
417 ret |= lfsr_rollback_bit(s, BEBIT(in, 24), fb) << (24 ^ 24);
418
419 ret |= lfsr_rollback_bit(s, BEBIT(in, 23), fb) << (23 ^ 24);
420 ret |= lfsr_rollback_bit(s, BEBIT(in, 22), fb) << (22 ^ 24);
421 ret |= lfsr_rollback_bit(s, BEBIT(in, 21), fb) << (21 ^ 24);
422 ret |= lfsr_rollback_bit(s, BEBIT(in, 20), fb) << (20 ^ 24);
423 ret |= lfsr_rollback_bit(s, BEBIT(in, 19), fb) << (19 ^ 24);
424 ret |= lfsr_rollback_bit(s, BEBIT(in, 18), fb) << (18 ^ 24);
425 ret |= lfsr_rollback_bit(s, BEBIT(in, 17), fb) << (17 ^ 24);
426 ret |= lfsr_rollback_bit(s, BEBIT(in, 16), fb) << (16 ^ 24);
427
428 ret |= lfsr_rollback_bit(s, BEBIT(in, 15), fb) << (15 ^ 24);
429 ret |= lfsr_rollback_bit(s, BEBIT(in, 14), fb) << (14 ^ 24);
430 ret |= lfsr_rollback_bit(s, BEBIT(in, 13), fb) << (13 ^ 24);
431 ret |= lfsr_rollback_bit(s, BEBIT(in, 12), fb) << (12 ^ 24);
432 ret |= lfsr_rollback_bit(s, BEBIT(in, 11), fb) << (11 ^ 24);
433 ret |= lfsr_rollback_bit(s, BEBIT(in, 10), fb) << (10 ^ 24);
434 ret |= lfsr_rollback_bit(s, BEBIT(in, 9), fb) << (9 ^ 24);
435 ret |= lfsr_rollback_bit(s, BEBIT(in, 8), fb) << (8 ^ 24);
436
437 ret |= lfsr_rollback_bit(s, BEBIT(in, 7), fb) << (7 ^ 24);
438 ret |= lfsr_rollback_bit(s, BEBIT(in, 6), fb) << (6 ^ 24);
439 ret |= lfsr_rollback_bit(s, BEBIT(in, 5), fb) << (5 ^ 24);
440 ret |= lfsr_rollback_bit(s, BEBIT(in, 4), fb) << (4 ^ 24);
441 ret |= lfsr_rollback_bit(s, BEBIT(in, 3), fb) << (3 ^ 24);
442 ret |= lfsr_rollback_bit(s, BEBIT(in, 2), fb) << (2 ^ 24);
443 ret |= lfsr_rollback_bit(s, BEBIT(in, 1), fb) << (1 ^ 24);
444 ret |= lfsr_rollback_bit(s, BEBIT(in, 0), fb) << (0 ^ 24);
445 return ret;
446 }
447
448 /** nonce_distance
449 * x,y valid tag nonces, then prng_successor(x, nonce_distance(x, y)) = y
450 */
451 static uint16_t *dist = 0;
452 int nonce_distance(uint32_t from, uint32_t to)
453 {
454 uint16_t x, i;
455 if(!dist) {
456 dist = malloc(2 << 16);
457 if(!dist)
458 return -1;
459 for (x = i = 1; i; ++i) {
460 dist[(x & 0xff) << 8 | x >> 8] = i;
461 x = x >> 1 | (x ^ x >> 2 ^ x >> 3 ^ x >> 5) << 15;
462 }
463 }
464 return (65535 + dist[to >> 16] - dist[from >> 16]) % 65535;
465 }
466
467
468 static uint32_t fastfwd[2][8] = {
469 { 0, 0x4BC53, 0xECB1, 0x450E2, 0x25E29, 0x6E27A, 0x2B298, 0x60ECB},
470 { 0, 0x1D962, 0x4BC53, 0x56531, 0xECB1, 0x135D3, 0x450E2, 0x58980}};
471
472
473 /** lfsr_prefix_ks
474 *
475 * Is an exported helper function from the common prefix attack
476 * Described in the "dark side" paper. It returns an -1 terminated array
477 * of possible partial(21 bit) secret state.
478 * The required keystream(ks) needs to contain the keystream that was used to
479 * encrypt the NACK which is observed when varying only the 3 last bits of Nr
480 * only correct iff [NR_3] ^ NR_3 does not depend on Nr_3
481 */
482 uint32_t *lfsr_prefix_ks(uint8_t ks[8], int isodd)
483 {
484 uint32_t *candidates = malloc(4 << 10);
485 if(!candidates) return 0;
486
487 uint32_t c, entry;
488 int size = 0, i, good;
489
490 for(i = 0; i < 1 << 21; ++i) {
491 for(c = 0, good = 1; good && c < 8; ++c) {
492 entry = i ^ fastfwd[isodd][c];
493 good &= (BIT(ks[c], isodd) == filter(entry >> 1));
494 good &= (BIT(ks[c], isodd + 2) == filter(entry));
495 }
496 if(good)
497 candidates[size++] = i;
498 }
499
500 candidates[size] = -1;
501
502 return candidates;
503 }
504
505 /** check_pfx_parity
506 * helper function which eliminates possible secret states using parity bits
507 */
508 static struct Crypto1State* check_pfx_parity(uint32_t prefix, uint32_t rresp, uint8_t parities[8][8], uint32_t odd, uint32_t even, struct Crypto1State* sl)
509 {
510 uint32_t ks1, nr, ks2, rr, ks3, c, good = 1;
511
512 for(c = 0; good && c < 8; ++c) {
513 sl->odd = odd ^ fastfwd[1][c];
514 sl->even = even ^ fastfwd[0][c];
515
516 lfsr_rollback_bit(sl, 0, 0);
517 lfsr_rollback_bit(sl, 0, 0);
518
519 ks3 = lfsr_rollback_bit(sl, 0, 0);
520 ks2 = lfsr_rollback_word(sl, 0, 0);
521 ks1 = lfsr_rollback_word(sl, prefix | c << 5, 1);
522
523 nr = ks1 ^ (prefix | c << 5);
524 rr = ks2 ^ rresp;
525
526 good &= parity(nr & 0x000000ff) ^ parities[c][3] ^ BIT(ks2, 24);
527 good &= parity(rr & 0xff000000) ^ parities[c][4] ^ BIT(ks2, 16);
528 good &= parity(rr & 0x00ff0000) ^ parities[c][5] ^ BIT(ks2, 8);
529 good &= parity(rr & 0x0000ff00) ^ parities[c][6] ^ BIT(ks2, 0);
530 good &= parity(rr & 0x000000ff) ^ parities[c][7] ^ ks3;
531 }
532
533 return sl + good;
534 }
535
536 /** lfsr_common_prefix
537 * Implentation of the common prefix attack.
538 * Requires the 28 bit constant prefix used as reader nonce (pfx)
539 * The reader response used (rr)
540 * The keystream used to encrypt the observed NACK's (ks)
541 * The parity bits (par)
542 * It returns a zero terminated list of possible cipher states after the
543 * tag nonce was fed in
544 */
545
546 struct Crypto1State* lfsr_common_prefix(uint32_t pfx, uint32_t rr, uint8_t ks[8], uint8_t par[8][8])
547 {
548 struct Crypto1State *statelist, *s;
549 uint32_t *odd, *even, *o, *e, top;
550
551 odd = lfsr_prefix_ks(ks, 1);
552 even = lfsr_prefix_ks(ks, 0);
553
554 s = statelist = malloc((sizeof *statelist) << 20);
555 if(!s || !odd || !even) {
556 free(statelist);
557 statelist = 0;
558 goto out;
559 }
560
561 for(o = odd; *o + 1; ++o)
562 for(e = even; *e + 1; ++e)
563 for(top = 0; top < 64; ++top) {
564 *o += 1 << 21;
565 *e += (!(top & 7) + 1) << 21;
566 s = check_pfx_parity(pfx, rr, par, *o, *e, s);
567 }
568
569 s->odd = s->even = 0;
570 out:
571 free(odd);
572 free(even);
573 return statelist;
574 }
Impressum, Datenschutz