🚀 go-pugleaf

  I wrote:
>> While your statement [that knowing a single <file,CRC> pair is sufficient to
>> modify other files "invisibly"] is presumably correct, ....

  Jerry Leichter replies:
>"Presumably"?  If you are going to be the apostle of CRC's for viral protec-
>tion, you should be able to check my claim.  Either it's correct or not.  I
>*think* it's correct, but one's proofs (especially informal ones) should be
>checked by one's peers.
>We've discussed our disagreements about CRC's for some two years now.  If you
>still not do not feel competent to check so simple a statement about CRC's as
>mine was, you should stop recommending them.

EXACTLY AS YOU, I *think* your statement is correct (though imho its relevance
is far less than you believe).  We therefore have the following peculiar situa-
tion: *You* think your statement is correct but you're not 100% certain; that's
just fine and dandy.  *I* think it's correct but I'm not 100% certain; that
(according to you) makes me "incompetent"!!  What can I say, Jerry?  You're a
real paragon of consistency and fairness.

>>							 I find it not
>> particularly relevant to the subject of whether CRC is secure for viral
>> detection, since the premises of the theorem are completely unrealistic when
>> CRC is used for that purpose.  First (as I mentioned in my reply to
>> Miroslav), any decent integrity checker includes a file-length checker.
>
>It is trivial to use the same kinds of techniques as I described to modify
>any sufficiently-long "don't care" section of the modified message, rather
>than appending new bits.  The "don't care" section doesn't even have to
>consist of contiguous bits - you just need "enough" of them (though some
>particular combinations of bits won't work).

Just where, pray tell, are you going to find these "don't care" sections?
There are *very few* PC programs which contain enough "don't care" bytes for a
virus to insert itself into without affecting the behavior of the host program
or causing it to hang completely.

>Since early viruses were often caught by changes in file lengths, modern
>viruses already use techniques that avoid changing the length.

Oh really?  *All* modern viruses?  *Most* of them?  A *few* of them?  Let's see
just how knowledgeable you are about viruses.  Give me a list of techniques
which are used by modern viruses to avoid changing the file length (you can
limit the list to methods used by existing viruses so you won't be divulging
any secrets) and a rough estimate of how many PC viruses you think there are
which use such techniques.  (Then I'll give you the *correct* answers.)

>I challenge you to come up with any design useable by a large population of
>unsophisticated users that does not allow a targetted virus to easily find the
>checksum database.

Fine (though I presume you mean not a targetted *virus*, but a targetted
*integrity checker* or a target*ing* virus).  As a matter of fact, I've already
presented the basic ideas in my reply to Miroslav, to which I refer you, par-
ticularly the parts concerning use of diskettes (and why they're necessary even
with a cryptographic hash function) and getting users to follow the rules.

>CRC's as file change detectors are like the first group of cryptosystems.  If
>you want to play in the big leagues, whether for cryptography or for file
>change detection, you have to be willing to pay the costs.

You seem to have forgotten a fact which you once knew very well: CRC has been
suggested even in the "big leagues"!!  Readers of sci.crypt are certainly
familiar with the many contributions of Prof. Michael Rabin to cryptography,
and if anyone's in the "big leagues" of cryptography, it's him.  Now as you
well know, he published a paper "Fingerprinting by Random Polynomials" (*),
which describes a *CRC-like* system for integrity checking in (what I have
called) an *intra*-machine environment (which is the environment which is
relevant for detection of viral infection).  The system I am recommending is
essentially the same as Rabin's, but it's augmented by special techniques to
take care of viruses which exploit DOS loopholes, precautions to ensure that
the generator and table of fingerprints (= checksums = hash values) are
inaccessible to attackers, and measures to enforce the rules.

                                     Y. Radai
                                     Hebrew Univ. of Jerusalem, Israel
                                     RADAI@VMS.HUJI.AC.IL

(*) Harvard Univ. Tech. Rep. TR-15-81 (1981).