cvs.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                 return;
 261         }
 262
 263         /* Find the potential contribution of the bottom bit of Init */
 264         palloc(&pone, 1UL);
 265         piter(&pone);
 266         if(blen < (dlen << 1)) {
 267                 palloc(&apoly, dlen); /* >= 1 */
 268                 psum(&apoly, pone, (dlen << 1) - 1UL - blen); /* >= 0 */
 269                 psum(&apoly, pone, (dlen << 1) - 1UL - alen); /* >= 1 */
 270         } else {
 271                 palloc(&apoly, blen - dlen + 1UL); /* > dlen */
 272                 psum(&apoly, pone, 0UL);
 273                 psum(&apoly, pone, blen - alen); /* >= 1 */
 274         }
 275         if(plen(apoly) > dlen) {
 276                 mat[dlen] = pcrc(apoly, divisor, pzero, pzero, 0);
 277                 pfree(&apoly);
 278         } else {
 279                 mat[dlen] = apoly;
 280         }
 281
 282         /* Find the actual contribution of Init */
 283         apoly = pcrc(*aptr, divisor, pzero, pzero, 0);
 284         bpoly = pcrc(*bptr, divisor, pzero, apoly, 0);
 285
 286         /* Populate the matrix */
 287         palloc(&apoly, 1UL);
 288         for(jptr=mat; jptr<mat+dlen; ++jptr)
 289                 *jptr = pzero;
 290         for(iptr = jptr++; jptr < mat + (dlen << 1); iptr = jptr++)
 291                 *jptr = pcrc(apoly, divisor, *iptr, pzero, P_MULXN);
 292         pfree(&apoly);
 293
 294         /* Transpose the matrix, augment with the Init contribution
 295          * and convert to row echelon form
 296          */
 297         for(i=0UL; i<dlen; ++i) {
 298                 apoly = pzero;
 299                 iptr = mat + (dlen << 1);
 300                 for(j=0UL; j<dlen; ++j)
 301                         ppaste(&apoly, *--iptr, i, j, j + 1UL, dlen + 1UL);
 302                 if(ptst(apoly))
 303                         ppaste(&apoly, bpoly, i, dlen, dlen + 1UL, dlen + 1UL);
 304                 j = pfirst(apoly);
 305                 while(j < dlen && !pident(mat[j], pzero)) {
 306                         psum(&apoly, mat[j], 0UL); /* pfirst(apoly) > j */
 307                         j = pfirst(apoly);
 308                 }
 309                 if(j < dlen)
 310                         mat[j] = apoly; /* pident(mat[j], pzero) || pfirst(mat[j]) == j */
 311                 else
 312                         pfree(&apoly);
 313         }
 314         palloc(&bpoly, dlen + 1UL);
 315         psum(&bpoly, pone, dlen);
 316
 317         /* Iterate through all solutions */
 318         do {
 319                 /* Solve the matrix by Gaussian elimination.
 320                  * The parity of the result, masked by each row, should be even.
 321                  */
 322                 cy = 1;
 323                 apoly = pclone(bpoly);
 324                 jptr = mat + dlen;
 325                 for(i=0UL; i<dlen; ++i) {
 326                         /* Compute next bit of Init */
 327                         if(pmpar(apoly, *--jptr))
 328                                 psum(&apoly, pone, dlen - 1UL - i);
 329                         /* Toggle each zero row with carry, for next iteration */
 330                         if(cy) {
 331                                if(pident(*jptr, pzero)) {
 332                                        /* 0 to 1, no carry */
 333                                        *jptr = bpoly;
 334                                        cy = 0;
 335                                } else if(pident(*jptr, bpoly)) {
 336                                        /* 1 to 0, carry forward */
 337                                        *jptr = pzero;
 338                                }
 339                         }
 340                 }
 341
 342                 /* Trim the augment mask bit */
 343                 praloc(&apoly, dlen);
 344
 345                 /* Test the Init value and add to results if correct */
 346                 calout(resc, result, divisor, apoly, flags, args, argpolys);
 347                 pfree(&apoly);
 348         } while(!cy);
 349         pfree(&pone);
 350         pfree(&bpoly);
 351
 352         /* Free the matrix. */
 353         for(jptr=mat; jptr < mat + (dlen << 1); ++jptr)
 354                 pfree(jptr);
 355         free(mat);
 356 }
 357
 358 static void
 359 calout(int *resc, model_t **result, const poly_t divisor, const poly_t init, int flags, int args, const poly_t *argpolys) {
 360         /* Calculate Xorout, check it against all the arguments and
 361          * add to results if consistent.
 362          */
 363         poly_t xorout;
 364         const poly_t *aptr, *iptr;
 365         unsigned long alen, ilen;
 366
 367         if(args < 1) return;
 368
 369         /* find argument of the shortest length */
 370         alen = plen(*(aptr = iptr = argpolys));
 371         for(++iptr; iptr < argpolys + args; ++iptr) {
 372                 ilen = plen(*iptr);
 373                 if(ilen < alen) {
 374                         aptr = iptr; alen = ilen;
 375                 }
 376         }
 377
 378         xorout = pcrc(*aptr, divisor, init, pzero, 0);
 379         /* On little-endian algorithms, the calculations yield
 380          * the reverse of the actual xorout: in the Williams
 381          * model, the refout stage intervenes between init and
 382          * xorout.
 383          */
 384         if(flags & P_REFOUT)
 385                 prev(&xorout);
 386
 387         /* Submit the model to the results table.
 388          * Could skip the shortest argument but we wish to check our
 389          * calculation.
 390          */
 391         chkres(resc, result, divisor, init, flags, xorout, args, argpolys);
 392         pfree(&xorout);
 393 }
 394
 395 static void
 396 calini(int *resc, model_t **result, const poly_t divisor, int flags, const poly_t xorout, int args, const poly_t *argpolys) {
 397         /* Calculate Init, check it against all the arguments and add to
 398          * results if consistent.
 399          */
 400         poly_t rcpdiv, rxor, arg, init;
 401         const poly_t *aptr, *iptr;
 402         unsigned long alen, ilen;
 403
 404         if(args < 1) return;
 405
 406         /* find argument of the shortest length */
 407         alen = plen(*(aptr = iptr = argpolys));
 408         for(++iptr; iptr < argpolys + args; ++iptr) {
 409                 ilen = plen(*iptr);
 410                 if(ilen < alen) {
 411                         aptr = iptr; alen = ilen;
 412                 }
 413         }
 414
 415         rcpdiv = pclone(divisor);
 416         prcp(&rcpdiv);
 417         /* If the algorithm is reflected, an ordinary CRC requires the
 418          * model's XorOut to be reversed, as XorOut follows the RefOut
 419          * stage.  To reverse the CRC calculation we need rxor to be the
 420          * mirror image of the forward XorOut.
 421          */
 422         rxor = pclone(xorout);
 423         if(~flags & P_REFOUT)
 424                 prev(&rxor);
 425         arg = pclone(*aptr);
 426         prev(&arg);
 427
 428         init = pcrc(arg, rcpdiv, rxor, pzero, 0);
 429         pfree(&arg);
 430         pfree(&rxor);
 431         pfree(&rcpdiv);
 432         prev(&init);
 433
 434         /* Submit the model to the results table.
 435          * Could skip the shortest argument but we wish to check our
 436          * calculation.
 437          */
 438         chkres(resc, result, divisor, init, flags, xorout, args, argpolys);
 439         pfree(&init);
 440 }
 441
 442 static void
 443 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) {
 444         /* Checks a model against the argument list, and adds to the
 445          * external results table if consistent.
 446          * Extends the result array and update the external pointer if
 447          * necessary.
 448          */
 449         model_t *rptr;
 450         poly_t xor, crc;
 451         const poly_t *aptr = argpolys, *const eptr = argpolys + args;
 452
 453         /* If the algorithm is reflected, an ordinary CRC requires the
 454          * model's XorOut to be reversed, as XorOut follows the RefOut
 455          * stage.
 456          */
 457         xor = pclone(xorout);
 458         if(flags & P_REFOUT)
 459                 prev(&xor);
 460
 461         for(; aptr < eptr; ++aptr) {
 462                 crc = pcrc(*aptr, divisor, init, xor, 0);
 463                 if(ptst(crc)) {
 464                         pfree(&crc);
 465                         break;
 466                 } else {
 467                         pfree(&crc);
 468                 }
 469         }
 470         pfree(&xor);
 471         if(aptr != eptr) return;
 472
 473         if(!(*result = realloc(*result, ++*resc * sizeof(model_t))))
 474                 uerror("cannot reallocate result array");
 475
 476         rptr = *result + *resc - 1;
 477         rptr->spoly  = pclone(divisor);
 478         rptr->init   = pclone(init);
 479         rptr->flags  = flags;
 480         rptr->xorout = pclone(xorout);
 481         rptr->name   = NULL;
 482
 483         /* compute check value for this model */
 484         mcheck(rptr);
 485
 486         /* callback to notify new model */
 487         ufound(rptr);
 488 }