Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!ucbvax!UIAMVS.BITNET!AWCTTYPA
From: AWCTTYPA@UIAMVS.BITNET ("David A. Lyons")
Newsgroups: comp.sys.apple
Subject: viruses and checksums
Message-ID: <8903091726.aa16737@SMOKE.BRL.MIL>
Date: 9 Mar 89 22:05:00 GMT
Sender: daemon@ucbvax.BERKELEY.EDU
Organization: The Internet
Lines: 43

>Date:         Wed, 8 Mar 89 17:29:00 EST
>From:         ALBRO%NIEHS.BITNET@CUNYVM.CUNY.EDU
>Subject:      RE: viruses and checksums
>
>I was under the impression that, in contrast to a checksum, which
>would give the same number regardless of the order of the bytes in a
>set, a CRC would come out differently if you had the same bytes in a
>different order.

Interesting...I don't have a definition of "checksum" handy.  In my
previous messages, when I said "checksum" I meant a very broad class
of functions of ordered groups of bytes, with would include CRCs.

(By the way, "CRC" standads for Cyclic Redundancy Check, or
something much like that.)

>If that is the case, introducing new code into a file (even with a
>separate checksum of zero) would always be detected by a CRC.  Is
>this right?

A CRC is very _likely_ to detect a change, but its a simple exercise
to show that it won't _always_.

The result of the CRC computation is going to be, say 2 bytes long.
(It doesn't really matter... choose any reasonable length.)  The
checksum contains far fewer bits than the data being checked, so (by
the pigeonhole principle, I think?), it's obvious that the CRC
function cannot be one-to-one:  there is at least one CRC value that
will result from doing the same CRC calculation on two separate
inputs.

For the CRC to be useful, you want its results to be fairly evenly
distributed (if it usually gave the same value, transmission errors
would be less likely to be detected).  In practice, probably _all_
CRC values can be generated by zillions and zillions of different
inputs, but that still leaves you with a very good chance of
detecting a change _unless_ the person or program changing your data
"knows" the exact CRC calculation being used.

 --David A. Lyons              bitnet: awcttypa@uiamvs
   DAL Systems                 CompuServe:  72177,3233
   P.O. Box 287                GEnie mail:    D.LYONS2
   North Liberty, IA 52317     AppleLinkPE: Dave Lyons