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

   1 /* reveng.c
   2  * Greg Cook, 24/Feb/2016
   3  */
   4
   5 /* CRC RevEng, an 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 <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                 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 }