git.zerfleddert.de Git - proxmark3-svn/blob - client/reveng/reveng.c

   1 /* reveng.c
   2  * Greg Cook, 9/Apr/2015
   3  */
   4
   5 /* CRC RevEng, an arbitrary-precision CRC calculator and algorithm finder
   6  * Copyright (C) 2010, 2011, 2012, 2013, 2014, 2015  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 <http://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         rptr = result + resc - 1;
 147         rptr->spoly  = pzero;
 148         rptr->init   = pzero;
 149         rptr->flags  = 0;
 150         rptr->xorout = pzero;
 151         rptr->check  = pzero;
 152         rptr->name   = NULL;
 153
 154         return(result);
 155 }
 156
 157 static poly_t *
 158 modpol(const poly_t init, int rflags, int args, const poly_t *argpolys) {
 159         /* Produce, in ascending length order, a list of differences
 160          * between the arguments in the list by summing pairs of arguments.
 161          * If R_HAVEI is not set in rflags, only pairs of equal length are
 162          * summed.
 163          * Otherwise, sums of right-aligned pairs are also returned, with
 164          * the supplied init poly added to the leftmost terms of each
 165          * poly of the pair.
 166          */
 167         poly_t work, swap, *result, *rptr, *iptr;
 168         const poly_t *aptr, *bptr, *eptr = argpolys + args;
 169         unsigned long alen, blen;
 170
 171         if(args < 2) return(NULL);
 172
 173         if(!(result = malloc(((((args - 1) * args) >> 1) + 1) * sizeof(poly_t))))
 174                 uerror("cannot allocate memory for codeword table");
 175
 176         rptr = result;
 177
 178         for(aptr = argpolys; aptr < eptr; ++aptr) {
 179                 alen = plen(*aptr);
 180                 for(bptr = aptr + 1; bptr < eptr; ++bptr) {
 181                         blen = plen(*bptr);
 182                         if(alen == blen) {
 183                                 work = pclone(*aptr);
 184                                 psum(&work, *bptr, 0UL);
 185                         } else if(rflags & R_HAVEI && alen < blen) {
 186                                 work = pclone(*bptr);
 187                                 psum(&work, *aptr, blen - alen);
 188                                 psum(&work, init, 0UL);
 189                                 psum(&work, init, blen - alen);
 190                         } else if(rflags & R_HAVEI /* && alen > blen */) {
 191                                 work = pclone(*aptr);
 192                                 psum(&work, *bptr, alen - blen);
 193                                 psum(&work, init, 0UL);
 194                                 psum(&work, init, alen - blen);
 195                         } else
 196                                 work = pzero;
 197
 198                         if(plen(work))
 199                                 pnorm(&work);
 200                         if((blen = plen(work))) {
 201                                 /* insert work into result[] in ascending order of length */
 202                                 for(iptr = result; iptr < rptr; ++iptr) {
 203                                         if(plen(work) < plen(*iptr)) {
 204                                                 swap = *iptr;
 205                                                 *iptr = work;
 206                                                 work = swap;
 207                                         }
 208                                         else if(plen(*iptr) == blen && !pcmp(&work, iptr)) {
 209                                                 pfree(&work);
 210                                                 work = *--rptr;
 211                                                 break;
 212                                         }
 213                                 }
 214                                 *rptr++ = work;
 215                         }
 216                 }
 217         }
 218         *rptr = pzero;
 219         return(result);
 220 }
 221
 222 static void
 223 engini(int *resc, model_t **result, const poly_t divisor, int flags, int args, const poly_t *argpolys) {
 224         /* Search for init values implied by the arguments.
 225          * Method from: Ewing, Gregory C. (March 2010).
 226          * "Reverse-Engineering a CRC Algorithm". Christchurch:
 227          * University of Canterbury.
 228          * <http://www.cosc.canterbury.ac.nz/greg.ewing/essays/
 229          * CRC-Reverse-Engineering.html>
 230          */
 231         poly_t apoly = PZERO, bpoly, pone = PZERO, *mat, *jptr;
 232         const poly_t *aptr, *bptr, *iptr;
 233         unsigned long alen, blen, dlen, ilen, i, j;
 234         int cy;
 235
 236         dlen = plen(divisor);
 237
 238         /* Allocate the CRC matrix */
 239         if(!(mat = (poly_t *) malloc((dlen << 1) * sizeof(poly_t))))
 240                 uerror("cannot allocate memory for CRC matrix");
 241
 242         /* Find arguments of the two shortest lengths */
 243         alen = blen = plen(*(aptr = bptr = iptr = argpolys));
 244         for(++iptr; iptr < argpolys + args; ++iptr) {
 245                 ilen = plen(*iptr);
 246                 if(ilen < alen) {
 247                         bptr = aptr; blen = alen;
 248                         aptr = iptr; alen = ilen;
 249                 } else if(ilen > alen && (aptr == bptr || ilen < blen)) {
 250                         bptr = iptr; blen = ilen;
 251                 }
 252         }
 253         if(aptr == bptr) {
 254                 /* if no arguments are suitable, calculate Init with an
 255                  * assumed XorOut of 0.  Create a padded XorOut
 256                  */
 257                 palloc(&apoly, dlen);
 258                 calini(resc, result, divisor, flags, apoly, args, argpolys);
 259                 pfree(&apoly);
 260                 free(mat);
 261                 return;
 262         }
 263
 264         /* Find the potential contribution of the bottom bit of Init */
 265         palloc(&pone, 1UL);
 266         piter(&pone);
 267         if(blen < (dlen << 1)) {
 268                 palloc(&apoly, dlen); /* >= 1 */
 269                 psum(&apoly, pone, (dlen << 1) - 1UL - blen); /* >= 0 */
 270                 psum(&apoly, pone, (dlen << 1) - 1UL - alen); /* >= 1 */
 271         } else {
 272                 palloc(&apoly, blen - dlen + 1UL); /* > dlen */
 273                 psum(&apoly, pone, 0UL);
 274                 psum(&apoly, pone, blen - alen); /* >= 1 */
 275         }
 276         if(plen(apoly) > dlen) {
 277                 mat[dlen] = pcrc(apoly, divisor, pzero, pzero, 0);
 278                 pfree(&apoly);
 279         } else {
 280                 mat[dlen] = apoly;
 281         }
 282
 283         /* Find the actual contribution of Init */
 284         apoly = pcrc(*aptr, divisor, pzero, pzero, 0);
 285         bpoly = pcrc(*bptr, divisor, pzero, apoly, 0);
 286
 287         /* Populate the matrix */
 288         palloc(&apoly, 1UL);
 289         for(jptr=mat; jptr<mat+dlen; ++jptr)
 290                 *jptr = pzero;
 291         for(iptr = jptr++; jptr < mat + (dlen << 1); iptr = jptr++)
 292                 *jptr = pcrc(apoly, divisor, *iptr, pzero, P_MULXN);
 293         pfree(&apoly);
 294
 295         /* Transpose the matrix, augment with the Init contribution
 296          * and convert to row echelon form
 297          */
 298         for(i=0UL; i<dlen; ++i) {
 299                 apoly = pzero;
 300                 iptr = mat + (dlen << 1);
 301                 for(j=0UL; j<dlen; ++j)
 302                         ppaste(&apoly, *--iptr, i, j, j + 1UL, dlen + 1UL);
 303                 if(ptst(apoly))
 304                         ppaste(&apoly, bpoly, i, dlen, dlen + 1UL, dlen + 1UL);
 305                 j = pfirst(apoly);
 306                 while(j < dlen && !pident(mat[j], pzero)) {
 307                         psum(&apoly, mat[j], 0UL); /* pfirst(apoly) > j */
 308                         j = pfirst(apoly);
 309                 }
 310                 if(j < dlen)
 311                         mat[j] = apoly; /* pident(mat[j], pzero) || pfirst(mat[j]) == j */
 312                 else
 313                         pfree(&apoly);
 314         }
 315         palloc(&bpoly, dlen + 1UL);
 316         psum(&bpoly, pone, dlen);
 317
 318         /* Iterate through all solutions */
 319         do {
 320                 /* Solve the matrix by Gaussian elimination.
 321                  * The parity of the result, masked by each row, should be even.
 322                  */
 323                 cy = 1;
 324                 apoly = pclone(bpoly);
 325                 jptr = mat + dlen;
 326                 for(i=0UL; i<dlen; ++i) {
 327                         /* Compute next bit of Init */
 328                         if(pmpar(apoly, *--jptr))
 329                                 psum(&apoly, pone, dlen - 1UL - i);
 330                         /* Toggle each zero row with carry, for next iteration */
 331                         if(cy) {
 332                                if(pident(*jptr, pzero)) {
 333                                        /* 0 to 1, no carry */
 334                                        *jptr = bpoly;
 335                                        cy = 0;
 336                                } else if(pident(*jptr, bpoly)) {
 337                                        /* 1 to 0, carry forward */
 338                                        *jptr = pzero;
 339                                }
 340                         }
 341                 }
 342
 343                 /* Trim the augment mask bit */
 344                 praloc(&apoly, dlen);
 345
 346                 /* Test the Init value and add to results if correct */
 347                 calout(resc, result, divisor, apoly, flags, args, argpolys);
 348                 pfree(&apoly);
 349         } while(!cy);
 350         pfree(&pone);
 351         pfree(&bpoly);
 352
 353         /* Free the matrix. */
 354         for(jptr=mat; jptr < mat + (dlen << 1); ++jptr)
 355                 pfree(jptr);
 356         free(mat);
 357 }
 358
 359 static void
 360 calout(int *resc, model_t **result, const poly_t divisor, const poly_t init, int flags, int args, const poly_t *argpolys) {
 361         /* Calculate Xorout, check it against all the arguments and
 362          * add to results if consistent.
 363          */
 364         poly_t xorout;
 365         const poly_t *aptr, *iptr;
 366         unsigned long alen, ilen;
 367
 368         if(args < 1) return;
 369
 370         /* find argument of the shortest length */
 371         alen = plen(*(aptr = iptr = argpolys));
 372         for(++iptr; iptr < argpolys + args; ++iptr) {
 373                 ilen = plen(*iptr);
 374                 if(ilen < alen) {
 375                         aptr = iptr; alen = ilen;
 376                 }
 377         }
 378
 379         xorout = pcrc(*aptr, divisor, init, pzero, 0);
 380         /* On little-endian algorithms, the calculations yield
 381          * the reverse of the actual xorout: in the Williams
 382          * model, the refout stage intervenes between init and
 383          * xorout.
 384          */
 385         if(flags & P_REFOUT)
 386                 prev(&xorout);
 387
 388         /* Submit the model to the results table.
 389          * Could skip the shortest argument but we wish to check our
 390          * calculation.
 391          */
 392         chkres(resc, result, divisor, init, flags, xorout, args, argpolys);
 393         pfree(&xorout);
 394 }
 395
 396 static void
 397 calini(int *resc, model_t **result, const poly_t divisor, int flags, const poly_t xorout, int args, const poly_t *argpolys) {
 398         /* Calculate Init, check it against all the arguments and add to
 399          * results if consistent.
 400          */
 401         poly_t rcpdiv, rxor, arg, init;
 402         const poly_t *aptr, *iptr;
 403         unsigned long alen, ilen;
 404
 405         if(args < 1) return;
 406
 407         /* find argument of the shortest length */
 408         alen = plen(*(aptr = iptr = argpolys));
 409         for(++iptr; iptr < argpolys + args; ++iptr) {
 410                 ilen = plen(*iptr);
 411                 if(ilen < alen) {
 412                         aptr = iptr; alen = ilen;
 413                 }
 414         }
 415
 416         rcpdiv = pclone(divisor);
 417         prcp(&rcpdiv);
 418         /* If the algorithm is reflected, an ordinary CRC requires the
 419          * model's XorOut to be reversed, as XorOut follows the RefOut
 420          * stage.  To reverse the CRC calculation we need rxor to be the
 421          * mirror image of the forward XorOut.
 422          */
 423         rxor = pclone(xorout);
 424         if(~flags & P_REFOUT)
 425                 prev(&rxor);
 426         arg = pclone(*aptr);
 427         prev(&arg);
 428
 429         init = pcrc(arg, rcpdiv, rxor, pzero, 0);
 430         pfree(&arg);
 431         pfree(&rxor);
 432         pfree(&rcpdiv);
 433         prev(&init);
 434
 435         /* Submit the model to the results table.
 436          * Could skip the shortest argument but we wish to check our
 437          * calculation.
 438          */
 439         chkres(resc, result, divisor, init, flags, xorout, args, argpolys);
 440         pfree(&init);
 441 }
 442
 443 static void
 444 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) {
 445         /* Checks a model against the argument list, and adds to the
 446          * external results table if consistent.
 447          * Extends the result array and update the external pointer if
 448          * necessary.
 449          */
 450         model_t *rptr;
 451         poly_t xor, crc;
 452         const poly_t *aptr = argpolys, *const eptr = argpolys + args;
 453
 454         /* If the algorithm is reflected, an ordinary CRC requires the
 455          * model's XorOut to be reversed, as XorOut follows the RefOut
 456          * stage.
 457          */
 458         xor = pclone(xorout);
 459         if(flags & P_REFOUT)
 460                 prev(&xor);
 461
 462         for(; aptr < eptr; ++aptr) {
 463                 crc = pcrc(*aptr, divisor, init, xor, 0);
 464                 if(ptst(crc)) {
 465                         pfree(&crc);
 466                         break;
 467                 } else {
 468                         pfree(&crc);
 469                 }
 470         }
 471         pfree(&xor);
 472         if(aptr != eptr) return;
 473
 474         if(!(*result = realloc(*result, ++*resc * sizeof(model_t))))
 475                 uerror("cannot reallocate result array");
 476
 477         rptr = *result + *resc - 1;
 478         rptr->spoly  = pclone(divisor);
 479         rptr->init   = pclone(init);
 480         rptr->flags  = flags;
 481         rptr->xorout = pclone(xorout);
 482         rptr->name   = NULL;
 483
 484         /* compute check value for this model */
 485         mcheck(rptr);
 486
 487         /* callback to notify new model */
 488         ufound(rptr);
 489 }