]> git.zerfleddert.de Git - proxmark3-svn/blob - client/reveng/reveng.c
Speedup Mifare Plus Attack v1
[proxmark3-svn] / client / reveng / reveng.c
1 /* reveng.c
2 * Greg Cook, 27/Jun/2016
3 */
4
5 /* CRC RevEng: arbitrary-precision CRC calculator and algorithm finder
6 * Copyright (C) 2010, 2011, 2012, 2013, 2014, 2015, 2016 Gregory Cook
7 *
8 * This file is part of CRC RevEng.
9 *
10 * CRC RevEng is free software: you can redistribute it and/or modify
11 * it under the terms of the GNU General Public License as published by
12 * the Free Software Foundation, either version 3 of the License, or
13 * (at your option) any later version.
14 *
15 * CRC RevEng is distributed in the hope that it will be useful,
16 * but WITHOUT ANY WARRANTY; without even the implied warranty of
17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 * GNU General Public License for more details.
19 *
20 * You should have received a copy of the GNU General Public License
21 * along with CRC RevEng. If not, see <https://www.gnu.org/licenses/>.
22 */
23
24 /* 2013-09-16: calini(), calout() work on shortest argument
25 * 2013-06-11: added sequence number to uprog() calls
26 * 2013-02-08: added polynomial range search
27 * 2013-01-18: refactored model checking to pshres(); renamed chkres()
28 * 2012-05-24: efficiently build Init contribution string
29 * 2012-05-24: removed broken search for crossed-endian algorithms
30 * 2012-05-23: rewrote engini() after Ewing; removed modini()
31 * 2011-01-17: fixed ANSI C warnings
32 * 2011-01-08: fixed calini(), modini() caters for crossed-endian algos
33 * 2011-01-04: renamed functions, added calini(), factored pshres();
34 * rewrote engini() and implemented quick Init search
35 * 2011-01-01: reveng() initialises terminating entry, addparms()
36 * initialises all fields
37 * 2010-12-26: renamed CRC RevEng. right results, rejects polys faster
38 * 2010-12-24: completed, first tests (unsuccessful)
39 * 2010-12-21: completed modulate(), partial sketch of reveng()
40 * 2010-12-19: started reveng
41 */
42
43 /* reveng() can in theory be modified to search for polynomials shorter
44 * than the full width as well, but this imposes a heavy time burden on
45 * the full width search, which is the primary use case, as well as
46 * complicating the search range function introduced in version 1.1.0.
47 * It is more effective to search for each shorter width directly.
48 */
49
50 #include <stdlib.h>
51
52 #define FILE void
53 #include "reveng.h"
54
55 static poly_t *modpol(const poly_t init, int rflags, int args, const poly_t *argpolys);
56 static void engini(int *resc, model_t **result, const poly_t divisor, int flags, int args, const poly_t *argpolys);
57 static void calout(int *resc, model_t **result, const poly_t divisor, const poly_t init, int flags, int args, const poly_t *argpolys);
58 static void calini(int *resc, model_t **result, const poly_t divisor, int flags, const poly_t xorout, int args, const poly_t *argpolys);
59 static void chkres(int *resc, model_t **result, const poly_t divisor, const poly_t init, int flags, const poly_t xorout, int args, const poly_t *argpolys);
60
61 static const poly_t pzero = PZERO;
62
63 model_t *
64 reveng(const model_t *guess, const poly_t qpoly, int rflags, int args, const poly_t *argpolys) {
65 /* Complete the parameters of a model by calculation or brute search. */
66 poly_t *pworks, *wptr, rem, gpoly;
67 model_t *result = NULL, *rptr;
68 int resc = 0;
69 unsigned long spin = 0, seq = 0;
70
71 if(~rflags & R_HAVEP) {
72 /* The poly is not known.
73 * Produce a list of differences between the arguments.
74 */
75 pworks = modpol(guess->init, rflags, args, argpolys);
76 if(!pworks || !plen(*pworks)) {
77 free(pworks);
78 goto requit;
79 }
80 /* Initialise the guessed poly to the starting value. */
81 gpoly = pclone(guess->spoly);
82 /* Clear the least significant term, to be set in the
83 * loop. qpoly does not need fixing as it is only
84 * compared with odd polys.
85 */
86 if(plen(gpoly))
87 pshift(&gpoly, gpoly, 0UL, 0UL, plen(gpoly) - 1UL, 1UL);
88
89 while(piter(&gpoly) && (~rflags & R_HAVEQ || pcmp(&gpoly, &qpoly) < 0)) {
90 /* For each possible poly of this size, try
91 * dividing all the differences in the list.
92 */
93 if(!(spin++ & R_SPMASK)) {
94 uprog(gpoly, guess->flags, seq++);
95 }
96 for(wptr = pworks; plen(*wptr); ++wptr) {
97 /* straight divide message by poly, don't multiply by x^n */
98 rem = pcrc(*wptr, gpoly, pzero, pzero, 0);
99 if(ptst(rem)) {
100 pfree(&rem);
101 break;
102 } else
103 pfree(&rem);
104 }
105 /* If gpoly divides all the differences, it is a
106 * candidate. Search for an Init value for this
107 * poly or if Init is known, log the result.
108 */
109 if(!plen(*wptr)) {
110 /* gpoly is a candidate poly */
111 if(rflags & R_HAVEI && rflags & R_HAVEX)
112 chkres(&resc, &result, gpoly, guess->init, guess->flags, guess->xorout, args, argpolys);
113 else if(rflags & R_HAVEI)
114 calout(&resc, &result, gpoly, guess->init, guess->flags, args, argpolys);
115 else if(rflags & R_HAVEX)
116 calini(&resc, &result, gpoly, guess->flags, guess->xorout, args, argpolys);
117 else
118 engini(&resc, &result, gpoly, guess->flags, args, argpolys);
119 }
120 if(!piter(&gpoly))
121 break;
122 }
123 /* Finished with gpoly and the differences list, free them.
124 */
125 pfree(&gpoly);
126 for(wptr = pworks; plen(*wptr); ++wptr)
127 pfree(wptr);
128 free(pworks);
129 }
130 else if(rflags & R_HAVEI && rflags & R_HAVEX)
131 /* All parameters are known! Submit the result if we get here */
132 chkres(&resc, &result, guess->spoly, guess->init, guess->flags, guess->xorout, args, argpolys);
133 else if(rflags & R_HAVEI)
134 /* Poly and Init are known, calculate XorOut */
135 calout(&resc, &result, guess->spoly, guess->init, guess->flags, args, argpolys);
136 else if(rflags & R_HAVEX)
137 /* Poly and XorOut are known, calculate Init */
138 calini(&resc, &result, guess->spoly, guess->flags, guess->xorout, args, argpolys);
139 else
140 /* Poly is known but not Init; search for Init. */
141 engini(&resc, &result, guess->spoly, guess->flags, args, argpolys);
142
143 requit:
144 if(!(result = realloc(result, ++resc * sizeof(model_t)))) {
145 uerror("cannot reallocate result array");
146 return NULL;
147 }
148 rptr = result + resc - 1;
149 rptr->spoly = pzero;
150 rptr->init = pzero;
151 rptr->flags = 0;
152 rptr->xorout = pzero;
153 rptr->check = pzero;
154 rptr->name = NULL;
155
156 return(result);
157 }
158
159 static poly_t *
160 modpol(const poly_t init, int rflags, int args, const poly_t *argpolys) {
161 /* Produce, in ascending length order, a list of differences
162 * between the arguments in the list by summing pairs of arguments.
163 * If R_HAVEI is not set in rflags, only pairs of equal length are
164 * summed.
165 * Otherwise, sums of right-aligned pairs are also returned, with
166 * the supplied init poly added to the leftmost terms of each
167 * poly of the pair.
168 */
169 poly_t work, swap, *result, *rptr, *iptr;
170 const poly_t *aptr, *bptr, *eptr = argpolys + args;
171 unsigned long alen, blen;
172
173 if(args < 2) return(NULL);
174
175 if(!(result = malloc(((((args - 1) * args) >> 1) + 1) * sizeof(poly_t))))
176 uerror("cannot allocate memory for codeword table");
177
178 rptr = result;
179
180 for(aptr = argpolys; aptr < eptr; ++aptr) {
181 alen = plen(*aptr);
182 for(bptr = aptr + 1; bptr < eptr; ++bptr) {
183 blen = plen(*bptr);
184 if(alen == blen) {
185 work = pclone(*aptr);
186 psum(&work, *bptr, 0UL);
187 } else if(rflags & R_HAVEI && alen < blen) {
188 work = pclone(*bptr);
189 psum(&work, *aptr, blen - alen);
190 psum(&work, init, 0UL);
191 psum(&work, init, blen - alen);
192 } else if(rflags & R_HAVEI /* && alen > blen */) {
193 work = pclone(*aptr);
194 psum(&work, *bptr, alen - blen);
195 psum(&work, init, 0UL);
196 psum(&work, init, alen - blen);
197 } else
198 work = pzero;
199
200 if(plen(work))
201 pnorm(&work);
202 if((blen = plen(work))) {
203 /* insert work into result[] in ascending order of length */
204 for(iptr = result; iptr < rptr; ++iptr) {
205 if(plen(work) < plen(*iptr)) {
206 swap = *iptr;
207 *iptr = work;
208 work = swap;
209 }
210 else if(plen(*iptr) == blen && !pcmp(&work, iptr)) {
211 pfree(&work);
212 work = *--rptr;
213 break;
214 }
215 }
216 *rptr++ = work;
217 }
218 }
219 }
220 *rptr = pzero;
221 return(result);
222 }
223
224 static void
225 engini(int *resc, model_t **result, const poly_t divisor, int flags, int args, const poly_t *argpolys) {
226 /* Search for init values implied by the arguments.
227 * Method from: Ewing, Gregory C. (March 2010).
228 * "Reverse-Engineering a CRC Algorithm". Christchurch:
229 * University of Canterbury.
230 * <http://www.cosc.canterbury.ac.nz/greg.ewing/essays/
231 * CRC-Reverse-Engineering.html>
232 */
233 poly_t apoly = PZERO, bpoly, pone = PZERO, *mat, *jptr;
234 const poly_t *aptr, *bptr, *iptr;
235 unsigned long alen, blen, dlen, ilen, i, j;
236 int cy;
237
238 dlen = plen(divisor);
239
240 /* Allocate the CRC matrix */
241 if(!(mat = (poly_t *) malloc((dlen << 1) * sizeof(poly_t))))
242 uerror("cannot allocate memory for CRC matrix");
243
244 /* Find arguments of the two shortest lengths */
245 alen = blen = plen(*(aptr = bptr = iptr = argpolys));
246 for(++iptr; iptr < argpolys + args; ++iptr) {
247 ilen = plen(*iptr);
248 if(ilen < alen) {
249 bptr = aptr; blen = alen;
250 aptr = iptr; alen = ilen;
251 } else if(ilen > alen && (aptr == bptr || ilen < blen)) {
252 bptr = iptr; blen = ilen;
253 }
254 }
255 if(aptr == bptr) {
256 /* if no arguments are suitable, calculate Init with an
257 * assumed XorOut of 0. Create a padded XorOut
258 */
259 palloc(&apoly, dlen);
260 calini(resc, result, divisor, flags, apoly, args, argpolys);
261 pfree(&apoly);
262 free(mat);
263 return;
264 }
265
266 /* Find the potential contribution of the bottom bit of Init */
267 palloc(&pone, 1UL);
268 piter(&pone);
269 if(blen < (dlen << 1)) {
270 palloc(&apoly, dlen); /* >= 1 */
271 psum(&apoly, pone, (dlen << 1) - 1UL - blen); /* >= 0 */
272 psum(&apoly, pone, (dlen << 1) - 1UL - alen); /* >= 1 */
273 } else {
274 palloc(&apoly, blen - dlen + 1UL); /* > dlen */
275 psum(&apoly, pone, 0UL);
276 psum(&apoly, pone, blen - alen); /* >= 1 */
277 }
278 if(plen(apoly) > dlen) {
279 mat[dlen] = pcrc(apoly, divisor, pzero, pzero, 0);
280 pfree(&apoly);
281 } else {
282 mat[dlen] = apoly;
283 }
284
285 /* Find the actual contribution of Init */
286 apoly = pcrc(*aptr, divisor, pzero, pzero, 0);
287 bpoly = pcrc(*bptr, divisor, pzero, apoly, 0);
288
289 /* Populate the matrix */
290 palloc(&apoly, 1UL);
291 for(jptr=mat; jptr<mat+dlen; ++jptr)
292 *jptr = pzero;
293 for(iptr = jptr++; jptr < mat + (dlen << 1); iptr = jptr++)
294 *jptr = pcrc(apoly, divisor, *iptr, pzero, P_MULXN);
295 pfree(&apoly);
296
297 /* Transpose the matrix, augment with the Init contribution
298 * and convert to row echelon form
299 */
300 for(i=0UL; i<dlen; ++i) {
301 apoly = pzero;
302 iptr = mat + (dlen << 1);
303 for(j=0UL; j<dlen; ++j)
304 ppaste(&apoly, *--iptr, i, j, j + 1UL, dlen + 1UL);
305 if(ptst(apoly))
306 ppaste(&apoly, bpoly, i, dlen, dlen + 1UL, dlen + 1UL);
307 j = pfirst(apoly);
308 while(j < dlen && !pident(mat[j], pzero)) {
309 psum(&apoly, mat[j], 0UL); /* pfirst(apoly) > j */
310 j = pfirst(apoly);
311 }
312 if(j < dlen)
313 mat[j] = apoly; /* pident(mat[j], pzero) || pfirst(mat[j]) == j */
314 else
315 pfree(&apoly);
316 }
317 palloc(&bpoly, dlen + 1UL);
318 psum(&bpoly, pone, dlen);
319
320 /* Iterate through all solutions */
321 do {
322 /* Solve the matrix by Gaussian elimination.
323 * The parity of the result, masked by each row, should be even.
324 */
325 cy = 1;
326 apoly = pclone(bpoly);
327 jptr = mat + dlen;
328 for(i=0UL; i<dlen; ++i) {
329 /* Compute next bit of Init */
330 if(pmpar(apoly, *--jptr))
331 psum(&apoly, pone, dlen - 1UL - i);
332 /* Toggle each zero row with carry, for next iteration */
333 if(cy) {
334 if(pident(*jptr, pzero)) {
335 /* 0 to 1, no carry */
336 *jptr = bpoly;
337 cy = 0;
338 } else if(pident(*jptr, bpoly)) {
339 /* 1 to 0, carry forward */
340 *jptr = pzero;
341 }
342 }
343 }
344
345 /* Trim the augment mask bit */
346 praloc(&apoly, dlen);
347
348 /* Test the Init value and add to results if correct */
349 calout(resc, result, divisor, apoly, flags, args, argpolys);
350 pfree(&apoly);
351 } while(!cy);
352 pfree(&pone);
353 pfree(&bpoly);
354
355 /* Free the matrix. */
356 for(jptr=mat; jptr < mat + (dlen << 1); ++jptr)
357 pfree(jptr);
358 free(mat);
359 }
360
361 static void
362 calout(int *resc, model_t **result, const poly_t divisor, const poly_t init, int flags, int args, const poly_t *argpolys) {
363 /* Calculate Xorout, check it against all the arguments and
364 * add to results if consistent.
365 */
366 poly_t xorout;
367 const poly_t *aptr, *iptr;
368 unsigned long alen, ilen;
369
370 if(args < 1) return;
371
372 /* find argument of the shortest length */
373 alen = plen(*(aptr = iptr = argpolys));
374 for(++iptr; iptr < argpolys + args; ++iptr) {
375 ilen = plen(*iptr);
376 if(ilen < alen) {
377 aptr = iptr; alen = ilen;
378 }
379 }
380
381 xorout = pcrc(*aptr, divisor, init, pzero, 0);
382 /* On little-endian algorithms, the calculations yield
383 * the reverse of the actual xorout: in the Williams
384 * model, the refout stage intervenes between init and
385 * xorout.
386 */
387 if(flags & P_REFOUT)
388 prev(&xorout);
389
390 /* Submit the model to the results table.
391 * Could skip the shortest argument but we wish to check our
392 * calculation.
393 */
394 chkres(resc, result, divisor, init, flags, xorout, args, argpolys);
395 pfree(&xorout);
396 }
397
398 static void
399 calini(int *resc, model_t **result, const poly_t divisor, int flags, const poly_t xorout, int args, const poly_t *argpolys) {
400 /* Calculate Init, check it against all the arguments and add to
401 * results if consistent.
402 */
403 poly_t rcpdiv, rxor, arg, init;
404 const poly_t *aptr, *iptr;
405 unsigned long alen, ilen;
406
407 if(args < 1) return;
408
409 /* find argument of the shortest length */
410 alen = plen(*(aptr = iptr = argpolys));
411 for(++iptr; iptr < argpolys + args; ++iptr) {
412 ilen = plen(*iptr);
413 if(ilen < alen) {
414 aptr = iptr; alen = ilen;
415 }
416 }
417
418 rcpdiv = pclone(divisor);
419 prcp(&rcpdiv);
420 /* If the algorithm is reflected, an ordinary CRC requires the
421 * model's XorOut to be reversed, as XorOut follows the RefOut
422 * stage. To reverse the CRC calculation we need rxor to be the
423 * mirror image of the forward XorOut.
424 */
425 rxor = pclone(xorout);
426 if(~flags & P_REFOUT)
427 prev(&rxor);
428 arg = pclone(*aptr);
429 prev(&arg);
430
431 init = pcrc(arg, rcpdiv, rxor, pzero, 0);
432 pfree(&arg);
433 pfree(&rxor);
434 pfree(&rcpdiv);
435 prev(&init);
436
437 /* Submit the model to the results table.
438 * Could skip the shortest argument but we wish to check our
439 * calculation.
440 */
441 chkres(resc, result, divisor, init, flags, xorout, args, argpolys);
442 pfree(&init);
443 }
444
445 static void
446 chkres(int *resc, model_t **result, const poly_t divisor, const poly_t init, int flags, const poly_t xorout, int args, const poly_t *argpolys) {
447 /* Checks a model against the argument list, and adds to the
448 * external results table if consistent.
449 * Extends the result array and update the external pointer if
450 * necessary.
451 */
452 model_t *rptr;
453 poly_t xor, crc;
454 const poly_t *aptr = argpolys, *const eptr = argpolys + args;
455
456 /* If the algorithm is reflected, an ordinary CRC requires the
457 * model's XorOut to be reversed, as XorOut follows the RefOut
458 * stage.
459 */
460 xor = pclone(xorout);
461 if(flags & P_REFOUT)
462 prev(&xor);
463
464 for(; aptr < eptr; ++aptr) {
465 crc = pcrc(*aptr, divisor, init, xor, 0);
466 if(ptst(crc)) {
467 pfree(&crc);
468 break;
469 } else {
470 pfree(&crc);
471 }
472 }
473 pfree(&xor);
474 if(aptr != eptr) return;
475
476 *result = realloc(*result, ++*resc * sizeof(model_t));
477 if (!*result) {
478 uerror("cannot reallocate result array");
479 return;
480 }
481
482 rptr = *result + *resc - 1;
483 rptr->spoly = pclone(divisor);
484 rptr->init = pclone(init);
485 rptr->flags = flags;
486 rptr->xorout = pclone(xorout);
487 rptr->name = NULL;
488
489 /* compute check value for this model */
490 mcheck(rptr);
491
492 /* callback to notify new model */
493 ufound(rptr);
494 }
Impressum, Datenschutz