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