home *** CD-ROM | disk | FTP | other *** search
/ The World of Computer Software / World_Of_Computer_Software-02-385-Vol-1of3.iso / t / tags18.zip / CRCSET.DOC < prev    next >
Text File  |  1991-07-13  |  35KB  |  1,070 lines

  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7.  
  8.  
  9.  
  10.  
  11.  
  12.  
  13.  
  14.  
  15.  
  16.  
  17.  
  18.  
  19.  
  20.  
  21.  
  22.  
  23.  
  24.  
  25.  
  26.  
  27.  
  28.                               CRCSET version 1.31
  29.                        Copyright (c) 1991 by Kevin Dean
  30.  
  31.                                   Kevin Dean
  32.                          Fairview Mall P.O. Box 55074
  33.                            1800 Sheppard Avenue East
  34.                               Willowdale, Ontario
  35.                                CANADA    M2J 5B9
  36.                            CompuServe ID: 76336,3114
  37.  
  38.  
  39.  
  40.  
  41.  
  42.  
  43.  
  44.  
  45.  
  46.  
  47.  
  48.  
  49.  
  50.  
  51.  
  52.  
  53.  
  54.  
  55.  
  56.  
  57.  
  58.  
  59.  
  60.  
  61.                                    Contents
  62.                                    --------
  63.  
  64.                    Warranty ............................  1
  65.  
  66.                    License .............................  2
  67.  
  68.                    Introduction ........................  3
  69.  
  70.                    What is a CRC? ......................  4
  71.  
  72.                    How CRCSET Works ....................  8
  73.  
  74.                    How to Use CRCSET ................... 13
  75.  
  76.                    Vulnerability ....................... 16
  77.  
  78.  
  79.                                    Warranty
  80.  
  81.         The author of CRCSET (hereafter referred to as "the author") makes no
  82. warranty of any kind, expressed or implied, including without limitation, any
  83. warranties of merchantability and/or fitness for a particular purpose.  The
  84. author shall not be liable for any damages, whether direct, indirect, special,
  85. or consequential arising from a failure of this program to operate in the
  86. manner desired by the user.  The author shall not be liable for any damage to
  87. data or property which may be caused directly or indirectly by use of the
  88. program.
  89.  
  90.         In no event will the author be liable to the user for any damages,
  91. including any lost profits, lost savings, or other incidental or consequential
  92. damages arising out of the use or inability to use the program, or for any
  93. claim by any other party.
  94.  
  95.  
  96.  
  97.  
  98.  
  99.  
  100.  
  101.  
  102.  
  103.  
  104.  
  105.  
  106.  
  107.  
  108.  
  109.  
  110.  
  111.  
  112.  
  113.  
  114.  
  115.  
  116.  
  117.  
  118.  
  119.  
  120.  
  121.  
  122.  
  123.  
  124.  
  125.  
  126.  
  127.  
  128.  
  129.  
  130.  
  131.  
  132.  
  133.  
  134.  
  135.  
  136.  
  137.  
  138.                                   - Page 1 - 
  139.  
  140.  
  141.                                     License
  142.  
  143.         This program is public domain.  As such, it may be freely distributed
  144. by anyone by any means.  No person or organization may charge for this program
  145. except for a minimal charge to cover handling and distribution.
  146.  
  147.         Having said that, I would also like to add that this algorithm has
  148. taken a lot of time and work to develop.  If you like this program, send me a
  149. postcard and let me know.  I would also be interested in copies of your own
  150. programs if you feel that that is appropriate.
  151.  
  152.         Also, if you have any questions or would like to see some more
  153. features in the program, drop me a note by surface or electronic mail (my
  154. address is on the first page of this file).  I will answer all mail regarding
  155. this program.
  156.  
  157.         Customization is available.
  158.  
  159.  
  160.  
  161.  
  162.  
  163.  
  164.  
  165.  
  166.  
  167.  
  168.  
  169.  
  170.  
  171.  
  172.  
  173.  
  174.  
  175.  
  176.  
  177.  
  178.  
  179.  
  180.  
  181.  
  182.  
  183.  
  184.  
  185.  
  186.  
  187.  
  188.  
  189.  
  190.  
  191.  
  192.  
  193.  
  194.  
  195.  
  196.  
  197.  
  198.  
  199.  
  200.                                   - Page 2 - 
  201.  
  202.  
  203.                                  Introduction
  204.  
  205.         CRCSET is an anti-virus utility.  Its purpose is to protect programs
  206. (in which supporting code is linked) with one of the most effective weapons
  207. against computer viruses: the Cyclic Redundancy Check, or CRC.  A full
  208. understanding of the CRC is not required to use this utility; if you like, you
  209. can skip over the discussion of the CRC to the section entitled "How to Use
  210. CRCSET".
  211.  
  212.         There are many utilities that perform CRC checks on other programs
  213. (VALIDATE.COM by McAfee associates is one) but most of these are external
  214. programs that are usually run only once, if at all.  The CRC generated by
  215. these utilities must be compared to a value in an external file; if the values
  216. match, the program is not infected.
  217.  
  218.         This approach has two problems: the first is that the CRC check is
  219. run only once when the user gets the program, if at all.  Most people would
  220. never run the check a second time.  The second problem is that the CRC is
  221. stored in an external file (e.g. the documentation).  If someone wants to tack
  222. a virus onto the program, it becomes a simple matter to run the validation
  223. program, copy the CRC values to the documentation, and distribute the infected
  224. program.  Anyone running the validation program would find the same CRC in the
  225. program as in the documentation, and in comes the virus.
  226.  
  227.         Another (increasingly popular) approach is for the CRC to be stored in
  228. the program itself (the .EXE file) and for the program to do its own check
  229. every time it is loaded.  This method is much more effective than the previous
  230. one because it means that the moment the program is infected and the CRC
  231. changes, the infection will be detected the next time the program is run.
  232.  
  233.         There is a potential problem with this method, but before I get into
  234. that, we need some background.
  235.  
  236.  
  237.  
  238.  
  239.  
  240.  
  241.  
  242.  
  243.  
  244.  
  245.  
  246.  
  247.  
  248.  
  249.  
  250.  
  251.  
  252.  
  253.  
  254.  
  255.  
  256.  
  257.  
  258.  
  259.  
  260.  
  261.  
  262.                                   - Page 3 - 
  263.  
  264.  
  265.                                 What is a CRC?
  266.  
  267.         The CRC, or Cyclic Redundancy Check, is an error-checking algorithm
  268. used in many types of computer operations, especially in data transfer.  For
  269. example, whenever your computer writes to disk, the disk controller calculates
  270. the CRC of the data being written and writes it with the data.  If your disk
  271. should somehow become corrupted, the CRC check will fail when you next try to
  272. read the data and the disk controller will return with an error, forcing DOS
  273. to display the critical error "Data error reading drive C:".  Most file
  274. transfer protocols (like Xmodem, Zmodem, and some derivatives of Kermit) also
  275. use a CRC check to validate the data being transmitted; if the CRC transmitted
  276. with the data does not match the CRC calculated by the receiving program, then
  277. the transmission has failed and the sending program is asked to retry the
  278. transmission.
  279.  
  280.         The actual calculation of the CRC is very simple.  The algorithm
  281. consists of two parts, a CRC polynomial and a CRC register, and is really an
  282. exercise in modulo-2 arithmetic.  The rules for modulo-2 arithmetic are shown
  283. in the following table:
  284.  
  285.                                    0 + 0 = 0
  286.                                    0 + 1 = 1
  287.                                    1 + 0 = 1
  288.                                    1 + 1 = 0
  289.  
  290. For those of you familiar with binary logic, these rules are equivalent to
  291. the exclusive-or operation.  Note: under modulo-2 arithmetic, subtraction is
  292. equivalent to addition.
  293.  
  294.         There is nothing magical about modulo-2 arithmetic and it has no
  295. special properties that make it better suited to CRC calculations than
  296. standard arithmetic; rather, since modulo-2 arithmetic doesn't carry from one
  297. column to the next (i.e. 1 + 1 = 0 with no carry), it's just easier to
  298. implement in hardware and software than any other method.  Consider the
  299. following:
  300.  
  301. 1. Binary addition, normal rules of carry
  302.      101101001
  303.    + 110110111
  304.    -----------
  305.     1100100000
  306.  
  307. 2. Binary addition, modulo-2 arithmetic (no carry)
  308.      101101001
  309.    + 110110111
  310.    -----------
  311.      011011110
  312.  
  313. The first addition requires us to carry any overflow from right to left.  The
  314. second addition requires no carry operations and can be performed much faster
  315. both by humans and by computers.
  316.  
  317.         The CRC algorithm can best be illustrated by the following diagram of
  318. a 4-bit CRC generator:
  319.  
  320.  
  321.  
  322.  
  323.  
  324.                                   - Page 4 - 
  325.  
  326.  
  327.                                  CRC polynomial
  328.                ------------1-----------0-----------1-----------1
  329.                |     3     |     2           1     |     0     |
  330.                |   -----   v   -----       -----   v   -----   v
  331.                + <-| x |<- + <-| x |<------| x |<- + <-| x |<- +
  332.                ^   -----       -----       -----       -----
  333.                |                  CRC register
  334.                ---- binary data stream
  335.  
  336. Each '+' symbol represents modulo-2 addition.  The numbers above the CRC
  337. register are the bit numbers of the register.
  338.  
  339.         The CRC is calculated as follows:
  340.  
  341. 1. Initialize the CRC register to 0.
  342.  
  343. 2. Add the incoming bit of the data stream to the outgoing bit (bit 3) of the
  344.    CRC register.
  345.  
  346. 3. Send the result of step 1 into the polynomial feedback loop.
  347.  
  348. 4. Add the value in the feedback loop to the bits in the CRC register as it is
  349.    shifted left.  The bits affected are determined by the CRC polynomial (i.e.
  350.    there is an addition for every bit in the polynomial that is equal to 1; if
  351.    the bit is 0, it is not fed back into the register).  In this case, the
  352.    polynomial represented is 1011.
  353.  
  354. 5. Repeat steps 2-4 for every bit in the data stream.
  355.  
  356. 6. The CRC is the final value in the register.
  357.  
  358. Let's try this with the data stream 11010111 and the polynomial 1011.  The
  359. result will be a 4-bit CRC.
  360.  
  361.         The output stream to the left is the result of each addition operation
  362. at the left-most gate.  This is the value that is fed into the polynomial
  363. feedback loop during the left shift.
  364.  
  365.                      ------------1-----------0-----------1-----------1
  366.                      |     3     |     2           1     |     0     |
  367.                      |   -----   v   -----       -----   v   -----   v
  368.                      + <-| 0 |<- + <-| 0 |<------| 0 |<- + <-| 0 |<- +
  369.                      ^   -----       -----       -----       -----
  370.                      |
  371.                      ---- 11010111
  372.  
  373.                      ------------1-----------0-----------1-----------1
  374.                      |     3     |     2           1     |     0     |
  375.                      |   -----   v   -----       -----   v   -----   v
  376.                 1 <- + <-| 1 |<- + <-| 0 |<------| 1 |<- + <-| 1 |<- +
  377.                      ^   -----       -----       -----       -----
  378.                      |
  379.                      ---- 1010111
  380.  
  381.  
  382.  
  383.  
  384.  
  385.  
  386.                                   - Page 5 - 
  387.  
  388.  
  389.                      ------------1-----------0-----------1-----------1
  390.                      |     3     |     2           1     |     0     |
  391.                      |   -----   v   -----       -----   v   -----   v
  392.                10 <- + <-| 0 |<- + <-| 1 |<------| 1 |<- + <-| 0 |<- +
  393.                      ^   -----       -----       -----       -----
  394.                      |
  395.                      ---- 010111
  396.  
  397.                      ------------1-----------0-----------1-----------1
  398.                      |     3     |     2           1     |     0     |
  399.                      |   -----   v   -----       -----   v   -----   v
  400.               100 <- + <-| 1 |<- + <-| 1 |<------| 0 |<- + <-| 0 |<- +
  401.                      ^   -----       -----       -----       -----
  402.                      |
  403.                      ---- 10111
  404.  
  405.                      ------------1-----------0-----------1-----------1
  406.                      |     3     |     2           1     |     0     |
  407.                      |   -----   v   -----       -----   v   -----   v
  408.              1000 <- + <-| 1 |<- + <-| 0 |<------| 0 |<- + <-| 0 |<- +
  409.                      ^   -----       -----       -----       -----
  410.                      |
  411.                      ---- 0111
  412.  
  413.                      ------------1-----------0-----------1-----------1
  414.                      |     3     |     2           1     |     0     |
  415.                      |   -----   v   -----       -----   v   -----   v
  416.             10001 <- + <-| 1 |<- + <-| 0 |<------| 1 |<- + <-| 1 |<- +
  417.                      ^   -----       -----       -----       -----
  418.                      |
  419.                      ---- 111
  420.  
  421.                      ------------1-----------0-----------1-----------1
  422.                      |     3     |     2           1     |     0     |
  423.                      |   -----   v   -----       -----   v   -----   v
  424.           100010 <- + <-| 0 |<- + <-| 1 |<------| 1 |<- + <-| 0 |<- +
  425.                      ^   -----       -----       -----       -----
  426.                      |
  427.                      ---- 11
  428.  
  429.                      ------------1-----------0-----------1-----------1
  430.                      |     3     |     2           1     |     0     |
  431.                      |   -----   v   -----       -----   v   -----   v
  432.           1000101 <- + <-| 0 |<- + <-| 1 |<------| 1 |<- + <-| 1 |<- +
  433.                      ^   -----       -----       -----       -----
  434.                      |
  435.                      ---- 1
  436.  
  437.                      ------------1-----------0-----------1-----------1
  438.                      |     3     |     2           1     |     0     |
  439.                      |   -----   v   -----       -----   v   -----   v
  440.          10001011 <- + <-| 0 |<- + <-| 1 |<------| 0 |<- + <-| 1 |<- +
  441.                      ^   -----       -----       -----       -----
  442.                      |
  443.                      ----
  444.  
  445.         The CRC is 0101.
  446.  
  447.  
  448.                                   - Page 6 - 
  449.  
  450.  
  451.         What should be obvious at this point is that if a single bit in the
  452. data stream is changed, the value in the CRC register is corrupted completely.
  453. The feedback loop ensures that the error is propagated throughout the entire
  454. calculation.
  455.  
  456.         Most CRC algorithms use either a 16- or 32-bit polynomial.  The longer
  457. the polynomial, the more effective it is at catching errors; a 16-bit CRC, for
  458. example, catches more than 99.99% of all errors in a data stream.
  459.  
  460.         All other CRC algorithms are analogous to the 4-bit algorithm
  461. presented here.  There are some optimizations that can process several bits at
  462. a time; the source code included with this program uses a lookup table that
  463. can process 8 bits at once.  For further discussion of the CRC algorithm and
  464. its variations, I recommend "C Programmer's Guide to Serial Communications" by
  465. Joe Campbell, published by Howard W. Sams & Company.
  466.  
  467.  
  468.  
  469.  
  470.  
  471.  
  472.  
  473.  
  474.  
  475.  
  476.  
  477.  
  478.  
  479.  
  480.  
  481.  
  482.  
  483.  
  484.  
  485.  
  486.  
  487.  
  488.  
  489.  
  490.  
  491.  
  492.  
  493.  
  494.  
  495.  
  496.  
  497.  
  498.  
  499.  
  500.  
  501.  
  502.  
  503.  
  504.  
  505.  
  506.  
  507.  
  508.  
  509.  
  510.                                   - Page 7 - 
  511.  
  512.  
  513.                                How CRCSET Works
  514.  
  515.         The idea of storing a program's CRC in the executable file itself has
  516. one drawback: since the CRC is part of the program, it becomes part of the
  517. data stream that is used to calculate the CRC.  In other words, you have to
  518. know what the CRC of the program is in order to calculate it!  At compile and
  519. link time, this is downright impossible; changing the slightest thing in your
  520. code will change the CRC the next time you recompile.
  521.  
  522.         Most algorithms that store the CRC in the program itself get around
  523. this drawback by breaking up the program into three chunks:
  524.  
  525.            +------------------------+-----+------------------------+
  526.            | <-- Program part 1 --> | CRC | <-- Program part 2 --> |
  527.            +------------------------+-----+------------------------+
  528.  
  529. The CRC is then calculated as the concatenation of parts 1 and 2, i.e. when
  530. the CRC is calculated, it skips over itself completely in the calculation.
  531. What it sees is this:
  532.  
  533.               +------------------------+------------------------+
  534.               | <-- Program part 1 --> | <-- Program part 2 --> |
  535.               +------------------------+------------------------+
  536.  
  537.         In order for a virus to infect any program that uses this method, it
  538. must somehow find the location of the CRC within the file and recalculate the
  539. CRC using the following data stream:
  540.  
  541.       +------------------------+------------------------+---------------+
  542.       | <-- Program part 1 --> | <-- Program part 2 --> | <-- Virus --> |
  543.       +------------------------+------------------------+---------------+
  544.  
  545. It must then overwrite the old CRC with the new one.
  546.  
  547.         I won't explain how (I don't want to give any virus-writers any
  548. ideas), but with the right technique the CRC can be found, recalculated, and
  549. rewritten in under 30 seconds.
  550.  
  551.         CRCSET overcomes this limitation by making both the polynomial and the
  552. CRC part of the data stream.  In order to calculate the CRC, CRCSET looks for
  553. a predefined string in the program (the default is DEAN_CRC), replaces the
  554. first four bytes with a 32-bit polynomial, sets the next four bytes (the true
  555. CRC) to 0, and calculates an intermediate CRC assuming that the true CRC is 0.
  556. Then, through the magic of matrix algebra, CRCSET calculates what the true CRC
  557. should have been in order to yield itself instead of the intermediate CRC at
  558. the end.  Let's take a look at a 4-bit CRC calculation as an example.
  559.  
  560.         Let's assume that the polynomial in use is 1011, that the CRC
  561. calculated up to the point where we reach the search string (represented by
  562. the bit pattern STUVWXYZ) is 0010, and that the bit pattern 1100 follows the
  563. search string:
  564.  
  565.  
  566.  
  567.  
  568.  
  569.  
  570.  
  571.  
  572.                                   - Page 8 - 
  573.  
  574.  
  575.                ------------1-----------0-----------1-----------1
  576.                |     3     |     2           1     |     0     |
  577.                |   -----   v   -----       -----   v   -----   v
  578.                + <-| 0 |<- + <-| 0 |<------| 1 |<- + <-| 0 |<- +
  579.                ^   -----       -----       -----       -----
  580.                |
  581.                ---- STUVWXYZ1100
  582.  
  583. 1. Replace the first four bits (STUV) with the CRC polynomial (1011):
  584.  
  585.                ------------1-----------0-----------1-----------1
  586.                |     3     |     2           1     |     0     |
  587.                |   -----   v   -----       -----   v   -----   v
  588.                + <-| 0 |<- + <-| 0 |<------| 1 |<- + <-| 0 |<- +
  589.                ^   -----       -----       -----       -----
  590.                |
  591.                ---- 1011WXYZ1100
  592.  
  593. 2. Calculate the value of the CRC register with the polynomial in the data
  594.    stream:
  595.  
  596.                ------------1-----------0-----------1-----------1
  597.                |     3     |     2           1     |     0     |
  598.                |   -----   v   -----       -----   v   -----   v
  599.                + <-| 1 |<- + <-| 0 |<------| 0 |<- + <-| 1 |<- +
  600.                ^   -----       -----       -----       -----
  601.                |
  602.                ---- WXYZ1100
  603.  
  604. 3. Replace the next four bits (WXYZ) with simple variables (X3, X2, X1, X0):
  605.  
  606.                ------------1-----------0-----------1-----------1
  607.                |     3     |     2           1     |     0     |
  608.                |   -----   v   -----       -----   v   -----   v
  609.                + <-| 1 |<- + <-| 0 |<------| 0 |<- + <-| 1 |<- +
  610.                ^   -----       -----       -----       -----
  611.                |
  612.                ---- (X3)(X2)(X1)(X0)1100
  613.  
  614. 4. Propagate X3+(bit 3) through the feedback loop:
  615.  
  616.            ---------------1-----------0------------1--------------1
  617.            |     3        |     2           1      |     0        |
  618.            |   --------   v   -----       ------   v   --------   v
  619.            + <-| X3+1 |<- + <-| 0 |<------| X3 |<- + <-| X3+1 |<- +
  620.            ^   --------       -----       ------       --------
  621.            |
  622.            ---- (X2)(X1)(X0)1100
  623.  
  624.  
  625.  
  626.  
  627.  
  628.  
  629.  
  630.  
  631.  
  632.  
  633.  
  634.                                   - Page 9 - 
  635.  
  636.  
  637. 5. Propagate X2+(bit 3) through the feedback loop:
  638.  
  639.         ------------------1------------0------------1-----------------1
  640.         |     3           |     2            1      |     0           |
  641.         |   -----------   v   ------       ------   v   -----------   v
  642.         + <-| X3+X2+1 |<- + <-| X3 |<------| X2 |<- + <-| X3+X2+1 |<- +
  643.         ^   -----------       ------       ------       -----------
  644.         |
  645.         ---- (X1)(X0)1100
  646.  
  647.    In bit 1, for example, we have (X2+(bit 3))+(bit 0) = (X2+X3+1)+(X3+1) = X2
  648.    since the X3 terms cancel, no matter what the value of X3 is.
  649.  
  650. 6. Propagate X1+(bit 3) through the feedback loop:
  651.  
  652.         ------------------1------------0------------1--------------------1
  653.         |     3           |     2            1      |     0              |
  654.         |   -----------   v   ------       ------   v   --------------   v
  655.         + <-| X2+X1+1 |<- + <-| X2 |<------| X1 |<- + <-| X3+X2+X1+1 |<- +
  656.         ^   -----------       ------       ------       --------------
  657.         |
  658.         ---- (X0)1100
  659.  
  660. 7. Propagate X0+(bit 3) through the feedback loop:
  661.  
  662.      ------------------1------------0---------------1--------------------1
  663.      |     3           |     2            1         |     0              |
  664.      |   -----------   v   ------       ---------   v   --------------   v
  665.      + <-| X1+X0+1 |<- + <-| X1 |<------| X3+X0 |<- + <-| X2+X1+X0+1 |<- +
  666.      ^   -----------       ------       ---------       --------------
  667.      |
  668.      ---- 1100
  669.  
  670. 8. Propagate the next bit through the feedback loop:
  671.  
  672.          -------------1---------------0--------------1---------------1
  673.          |     3      |     2               1        |     0         |
  674.          |   ------   v   ---------       --------   v   ---------   v
  675.          + <-| X0 |<- + <-| X3+X0 |<------| X2+1 |<- + <-| X1+X0 |<- +
  676.          ^   ------       ---------       --------       ---------
  677.          |
  678.          ---- 100
  679.  
  680. 9. Repeat step 8 for all remaining bits:
  681.  
  682.      ---------------------1---------------0--------------1---------------1
  683.      |     3              |     2               1        |     0         |
  684.      |   --------------   v   ---------       --------   v   ---------   v
  685.      + <-| X3+X2+X1+1 |<- + <-| X3+X0 |<------| X2+1 |<- + <-| X3+X2 |<- +
  686.      ^   --------------       ---------       --------       ---------
  687.      |
  688.      ----
  689.  
  690.  
  691.  
  692.  
  693.  
  694.  
  695.  
  696.                                  - Page 10 - 
  697.  
  698.  
  699.         We want the CRC in the register to be equal to the unknown CRC we
  700. started inserting at step 4, i.e. we need:
  701.  
  702.                      N   Value calculated for bit N  Bit N
  703.                     ---  --------------------------  -----
  704.                      3      X3 + X2 + X1      + 1   =  X3
  705.                      2      X3           + X0       =  X2
  706.                      1           X2           + 1   =  X1
  707.                      0      X3 + X2                 =  X0
  708.  
  709. If we collect all the variables on the left and all the constants on the
  710. right (keeping in mind that we are dealing with modulo-2 arithmetic):
  711.  
  712.                                   X2 + X1      = 1
  713.                              X3 + X2      + X0 = 0
  714.                                   X2 + X1      = 1
  715.                              X3 + X2      + X0 = 0
  716.  
  717. The value 1010 is the intermediate CRC mentioned earlier.
  718.  
  719.         Here we have an interesting situation.  The first and third equations
  720. are the same and so are the second and fourth.  What we come down to is this:
  721.  
  722.                                   X2 + X1      = 1
  723.                              X3 + X2      + X0 = 0
  724.  
  725. We have four variables and only two equations.  There is no unique solution;
  726. in fact, there are four (2 to the power of (4 - number of independent
  727. equations)) separate and distinct sets of values that will satisfy these
  728. equations.
  729.  
  730.         Since CRCSET needs a numeric solution, we have to arbitrarily set bits
  731. to get one.  For arguments sake, let's set X2 to 1.
  732.  
  733.                                    1 + X1      = 1
  734.                              X3 +  1      + X0 = 0
  735.  
  736. In other words:
  737.  
  738.                                        X1      = 0
  739.                              X3 +         + X0 = 1
  740.  
  741. By setting X2 to 1, we have also fixed X1.  Now let's set X0 to 0.
  742.  
  743.                              X3 +         +  0 = 1
  744.  
  745. In other words:
  746.  
  747.                              X3                = 1
  748.  
  749. We now have a solution for the CRC of the program: 1100.  There are three
  750. others: 0101, 0010, and 1011.  If we replace the string WXYZ with any of these
  751. values, the CRC calculation process will yield that value at the end, e.g.:
  752.  
  753.  
  754.  
  755.  
  756.  
  757.  
  758.                                  - Page 11 - 
  759.  
  760.  
  761.                ------------1-----------0-----------1-----------1
  762.                |     3     |     2           1     |     0     |
  763.                |   -----   v   -----       -----   v   -----   v
  764.                + <-| 0 |<- + <-| 0 |<------| 1 |<- + <-| 0 |<- +
  765.                ^   -----       -----       -----       -----
  766.                |
  767.                ---- 101111001100
  768.                         ----
  769.  
  770. yields
  771.  
  772.                ------------1-----------0-----------1-----------1
  773.                |     3     |     2           1     |     0     |
  774.                |   -----   v   -----       -----   v   -----   v
  775.                + <-| 1 |<- + <-| 1 |<------| 0 |<- + <-| 0 |<- +
  776.                ^   -----       -----       -----       -----
  777.                |
  778.                ----
  779.  
  780. If you're not sure about this, try it with pen and paper.  Plug in each of the
  781. four values and you should get that same value at the end of the CRC
  782. calculation process.  To help you out, here are the values of the CRC register
  783. for each step of the solution (the first value is the value after step 2 of
  784. the calculation):
  785.  
  786.            CRC
  787.           -----
  788.           1100: 1001, 0010, 1111, 0101, 1010, 0100, 0011, 0110, 1100
  789.           0101: 1001, 1001, 0010, 0100, 0011, 1101, 1010, 1111, 0101
  790.           0010: 1001, 1001, 1001, 0010, 0100, 0011, 1101, 0001, 0010
  791.           1011: 1001, 0010, 0100, 0011, 1101, 1010, 0100, 1000, 1011
  792.  
  793.         The fact that there is not a unique solution isn't really important;
  794. only about 30% of the time will there be a unique solution.  This does not
  795. diminish the effectiveness of the CRC calculation because whichever of the
  796. four values the CRC is set to, any virus installing itself in the program will
  797. still change it.  The fact that we did not get a unique solution does mean,
  798. however, that it is possible to get the following situation:
  799.  
  800.                                   X2 + X1      = 1
  801.                              X3 + X2      + X0 = 1
  802.                                   X2 + X1      = 1
  803.                              X3 + X2      + X0 = 0
  804.  
  805. Here equations 2 and 4 contradict each other.  There are no values of X3 to X0
  806. that will satisfy these equations.  If the CRCSET program comes across this
  807. situation, it will simply try again with another polynomial.
  808.  
  809.         For illustration, I have used only a 4-bit CRC; the CRCSET algorithm
  810. uses 32 bits.  The principle is the same; it just takes more time (and ink,
  811. paper, patience, caffeine, pizza, and chocolate chip cookies).
  812.  
  813.  
  814.  
  815.  
  816.  
  817.  
  818.  
  819.  
  820.                                  - Page 12 - 
  821.  
  822.  
  823.                                How to Use CRCSET
  824.  
  825.         This is the easy part.
  826.  
  827.         For C programmers, add the files VALIDCRC.C, VIRUSDAT.C, and
  828. BUFALLOC.C to the list of files required to build the program you are working
  829. on (in Turbo C, for example, add them to the project file).  Add a call to
  830. validatecrc("PROGNAME.EXE") somewhere in your program.  The function
  831. validatecrc() returns:
  832.  
  833.         - CRC_VALID (0) if the CRC is valid,
  834.         - CRC_INVALID (1) if it is invalid,
  835.         - CRC_ISZERO (2) if the CRC polynomial has been reset to 0 (which will
  836.           always yield a CRC of 0),
  837.         - CRC_NOMEM (3) if not enough memory was available to load the
  838.           program's image, or
  839.         - CRC_FILEERR (4) if the program file was not found or some other
  840.           error occurred trying to open it.
  841.  
  842. Return values and function prototypes are defined in the header file
  843. VIRUSCRC.H.
  844.  
  845.         NOTE: For compatibility with earlier releases of CRCSET, the function
  846. isvalidcrc() has been defined as a macro in VIRUSCRC.H; isvalidcrc() returns 1
  847. if the CRC is valid and 0 if it is not.
  848.  
  849.         For Turbo Pascal programmers, add the unit VirusCRC to your "uses"
  850. clause and call the function ValidateCRC('PROGNAME.EXE').  ValidateCRC
  851. returns:
  852.  
  853.         - crcValid (0) if the CRC is valid,
  854.         - crcInvalid (1) if it is invalid,
  855.         - crcIsZero (2) if the CRC polynomial has been reset to 0 (which will
  856.           always yield a CRC of 0),
  857.         - crcNoMem (3) if not enough memory was available to load the
  858.           program's image, or
  859.         - crcFileErr (4) if the program file was not found or some other error
  860.           occurred trying to open it.
  861.  
  862. Return values are defined in the interface part of the VirusCRC unit.
  863.  
  864.         NOTE: For compatibility with earlier releases of CRCSET, the function
  865. IsValidCRC has been defined in the VirusCRC unit; IsValidCRC returns TRUE if
  866. the CRC is valid and FALSE if it is not.
  867.  
  868.         Example programs TESTCRC.C and TESTCRC.PAS have been provided.  You
  869. may also find the files BUFALLOC.C and ALLOCBUF.PAS useful in other programs.
  870. Each contains a C or Pascal function that allocates a buffer of flexible size
  871. depending on the amount of memory available.  This function is used by the CRC
  872. validation routine to allocate a file buffer.  Its use should be clear from
  873. the internal documentation.
  874.  
  875.         Once you have compiled your program, you have to calculate its CRC.
  876. The program CRCSET.EXE has been provided for this purpose.  The syntax is:
  877.  
  878.     CRCSET [-<string>] file [file [file [...]]]
  879.     <string> is an 8-character (0-padded) string in which to store CRC data
  880.              (default is DEAN_CRC),
  881.  
  882.                                  - Page 13 - 
  883.  
  884.  
  885.     [file]   is one or more files for which a CRC is to be calculated.
  886.  
  887. The string for which CRCSET.EXE searches is stored in the variable _viruscrc
  888. in C and _VirusCRC in Turbo Pascal.  The default is DEAN_CRC but you may
  889. change it if there is a conflict (i.e. if there is more than one instance of
  890. DEAN_CRC in the program, CRCSET.EXE will not know which one holds the CRC and
  891. so will not set it).  CRCSET replaces the string with a randomly-generated
  892. polynomial and the CRC itself.
  893.  
  894.         For example, to set the CRC for either of the test programs, the
  895. command is:
  896.  
  897.                               CRCSET TESTCRC.EXE
  898.  
  899. If you change the string in one of the test programs to something like
  900. "MyName", you would enter:
  901.  
  902.                           CRCSET -MyName TESTCRC.EXE
  903.  
  904. The case of the string on the command line must match exactly the case of the
  905. string in the program.  Also, any strings shorter than 8 characters must be
  906. padded with 0's (ASCII 0, not the character '0') in the program.
  907.  
  908.         If you run TESTCRC before running CRCSET on it, TESTCRC will abort
  909. with a warning that it may have been infected.  After you set the CRC, run
  910. TESTCRC to assure yourself that its CRC is valid.
  911.  
  912.         If you want to test the reliability of the CRC check, change a few
  913. bytes in TESTCRC.EXE (be careful, changing bytes in the code segment can hang
  914. the program, so try bytes in the data segment, towards the end).  Run TESTCRC
  915. again, and it should warn you that it may have been infected.
  916.  
  917.         Despite its complexity, CRCSET.EXE takes only a few seconds to
  918. calculate the CRC of the target file.  I have made some optimizations to the
  919. algorithm that make the calculation time almost constant regardless of the
  920. size of the file.
  921.  
  922.         Once a CRC has been determined for your program, it takes little time
  923. for the validation function to verify it every time the program is run.
  924.  
  925.         CRCSET will display the name of the file that it is working on and
  926. one or more of the following messages:
  927.  
  928.         CRC search string "<string>" found more than once.
  929.  
  930.                 The search string specified occurs more than once in the file.
  931.         This is an error, since CRCSET has no way of knowing which occurrence
  932.         of the string it is supposed to replace with the polynomial and CRC.
  933.         Change the search string in _viruscrc (C version) or _VirusCRC (Turbo
  934.         Pascal version), recompile, and try again with the new string as an
  935.         argument to CRCSET (e.g. CRCSET -NewStrng PROG.EXE).
  936.  
  937.  
  938.  
  939.  
  940.  
  941.  
  942.  
  943.  
  944.                                  - Page 14 - 
  945.  
  946.  
  947.         CRC search string "<string>" not found.
  948.  
  949.                 The search string specified does not occur in the file.  Make
  950.         sure that the string passed to CRCSET is correct and also that the
  951.         validation module is being linked (i.e. that there is a call to the
  952.         validatecrc() or ValidateCRC somewhere in your program).
  953.  
  954.         Testing polynomial abcdef12 ... no solution.
  955.  
  956.                 The matrix generated by CRCSET using the polynomial abcdef12
  957.         does not have a solution.  CRCSET will try again with another
  958.         polynomial.
  959.  
  960.         Testing polynomial abcdef12 ... CRC is 34567890.
  961.         It is unique.
  962.  
  963.                 The matrix generated by CRCSET using the polynomial abcdef12
  964.         has the unique solution 34567890, i.e. 34567890 is the CRC of your
  965.         program under the polynomial abcdef12.  A unique solution will occur
  966.         only about 30% of the time.
  967.  
  968.         Testing polynomial abcdef12 ... CRC is 34567890.
  969.         It is not unique (2^N solutions).
  970.  
  971.                 The matrix generated by CRCSET using the polynomial abcdef12
  972.         has the non-unique solution 34567890, i.e. 34567890 is the CRC of your
  973.         program under the polynomial abcdef12.  The number of free variables
  974.         (the number of bits in the CRC whose value is irrelevant to the
  975.         solution) is N; each bit has two possible values, so there are 2^N
  976.         possible solutions.  It is theoretically possible that all 32 bits
  977.         will be free variables, but this is extremely unlikely.  The fact that
  978.         there is not a unique solution does not diminish the effectiveness of
  979.         the CRC validation in any way.
  980.  
  981.         Note: the validation function (both the C and Pascal versions) finds
  982. the name of the running program in _argv[0] or ParamStr(0) if the program is
  983. running under DOS versions 3 or greater and searches the DOS PATH for the
  984. program under DOS version 2.
  985.  
  986.  
  987.  
  988.  
  989.  
  990.  
  991.  
  992.  
  993.  
  994.  
  995.  
  996.  
  997.  
  998.  
  999.  
  1000.  
  1001.  
  1002.  
  1003.  
  1004.  
  1005.  
  1006.                                  - Page 15 - 
  1007.  
  1008.  
  1009.                                  Vulnerability
  1010.  
  1011.         The CRCSET algorithm, like every other anti-virus algorithm, is
  1012. vulnerable to attack.  Hand-tweaking the code to bypass the virus protection
  1013. is always possible.  Direct attack to determine the storage location of the
  1014. polynomial and the CRC and to change it is also possible, but, on a program of
  1015. any reasonable size (greater than 20k), this can take upwards of half an hour
  1016. on a 386.  Any virus that ties up the computer for that long wins no points
  1017. for discretion.  Any user that doesn't do anything about a system lockup
  1018. lasting over 30 seconds probably has many other doors open for viruses anyway.
  1019. :-)
  1020.  
  1021.         There is no substitute for proper precautions: downloading from a
  1022. reputable BBS, avoiding pirated software, scanning programs for viruses before
  1023. using them, and so on.  This program was developed with the knowledge that
  1024. most people don't take these precautions (based on a sample size of at least 1
  1025. - me); rather than leave it up to the end user to protect against viruses,
  1026. with this we programmers can take on some of the burden by protecting the
  1027. programs we write against them.
  1028.  
  1029.  
  1030.  
  1031.  
  1032.  
  1033.  
  1034.  
  1035.  
  1036.  
  1037.  
  1038.  
  1039.  
  1040.  
  1041.  
  1042.  
  1043.  
  1044.  
  1045.  
  1046.  
  1047.  
  1048.  
  1049.  
  1050.  
  1051.  
  1052.  
  1053.  
  1054.  
  1055.  
  1056.  
  1057.  
  1058.  
  1059.  
  1060.  
  1061.  
  1062.  
  1063.  
  1064.  
  1065.  
  1066.  
  1067.  
  1068.                                  - Page 16 - 
  1069.  
  1070.