home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / sci / crypt / 2710 < prev    next >
Encoding:
Internet Message Format  |  1992-07-21  |  5.0 KB
  1. Path: sparky!uunet!wupost!micro-heart-of-gold.mit.edu!bu.edu!wang!news
  2. From: radai@huji.ac.il (Y Radai)
  3. Newsgroups: sci.crypt
  4. Subject: Re: Security of CRC
  5. Message-ID: <5122@shum.huji.ac.il>
  6. Date: 21 Jul 92 16:01:46 GMT
  7. References: <1992Jun27.005817.21922@ncar.ucar.edu> <1992Jul7.221658.11091@magnus.acs.ohio-state.edu> <bontchev.710613252@fbihh> <1992Jul10.075925.1@zodiac.rutgers.edu> <5024@shum.huji.ac.il> <1992Jul14.180747.1@zodiac.rutgers.edu>
  8. Sender: news@wang.com
  9. Reply-To: radai@shum.huji.ac.il (Y Radai)
  10. Organization: The Hebrew University of Jerusalem, Israel
  11. Lines: 80
  12.  
  13.  
  14.   I wrote:
  15. >> While your statement [that knowing a single <file,CRC> pair is sufficient to
  16. >> modify other files "invisibly"] is presumably correct, ....
  17.  
  18.   Jerry Leichter replies:
  19. >"Presumably"?  If you are going to be the apostle of CRC's for viral protec-
  20. >tion, you should be able to check my claim.  Either it's correct or not.  I
  21. >*think* it's correct, but one's proofs (especially informal ones) should be
  22. >checked by one's peers.
  23. >We've discussed our disagreements about CRC's for some two years now.  If you
  24. >still not do not feel competent to check so simple a statement about CRC's as
  25. >mine was, you should stop recommending them.
  26.  
  27. EXACTLY AS YOU, I *think* your statement is correct (though imho its relevance
  28. is far less than you believe).  We therefore have the following peculiar situa-
  29. tion: *You* think your statement is correct but you're not 100% certain; that's
  30. just fine and dandy.  *I* think it's correct but I'm not 100% certain; that
  31. (according to you) makes me "incompetent"!!  What can I say, Jerry?  You're a
  32. real paragon of consistency and fairness.
  33.  
  34. >>                             I find it not
  35. >> particularly relevant to the subject of whether CRC is secure for viral
  36. >> detection, since the premises of the theorem are completely unrealistic when
  37. >> CRC is used for that purpose.  First (as I mentioned in my reply to
  38. >> Miroslav), any decent integrity checker includes a file-length checker.
  39. >
  40. >It is trivial to use the same kinds of techniques as I described to modify
  41. >any sufficiently-long "don't care" section of the modified message, rather
  42. >than appending new bits.  The "don't care" section doesn't even have to
  43. >consist of contiguous bits - you just need "enough" of them (though some
  44. >particular combinations of bits won't work).
  45.  
  46. Just where, pray tell, are you going to find these "don't care" sections?
  47. There are *very few* PC programs which contain enough "don't care" bytes for a
  48. virus to insert itself into without affecting the behavior of the host program
  49. or causing it to hang completely.
  50.  
  51. >Since early viruses were often caught by changes in file lengths, modern
  52. >viruses already use techniques that avoid changing the length.
  53.  
  54. Oh really?  *All* modern viruses?  *Most* of them?  A *few* of them?  Let's see
  55. just how knowledgeable you are about viruses.  Give me a list of techniques
  56. which are used by modern viruses to avoid changing the file length (you can
  57. limit the list to methods used by existing viruses so you won't be divulging
  58. any secrets) and a rough estimate of how many PC viruses you think there are
  59. which use such techniques.  (Then I'll give you the *correct* answers.)
  60.  
  61. >I challenge you to come up with any design useable by a large population of
  62. >unsophisticated users that does not allow a targetted virus to easily find the
  63. >checksum database.
  64.  
  65. Fine (though I presume you mean not a targetted *virus*, but a targetted
  66. *integrity checker* or a target*ing* virus).  As a matter of fact, I've already
  67. presented the basic ideas in my reply to Miroslav, to which I refer you, par-
  68. ticularly the parts concerning use of diskettes (and why they're necessary even
  69. with a cryptographic hash function) and getting users to follow the rules.
  70.  
  71. >CRC's as file change detectors are like the first group of cryptosystems.  If
  72. >you want to play in the big leagues, whether for cryptography or for file
  73. >change detection, you have to be willing to pay the costs.
  74.  
  75. You seem to have forgotten a fact which you once knew very well: CRC has been
  76. suggested even in the "big leagues"!!  Readers of sci.crypt are certainly
  77. familiar with the many contributions of Prof. Michael Rabin to cryptography,
  78. and if anyone's in the "big leagues" of cryptography, it's him.  Now as you
  79. well know, he published a paper "Fingerprinting by Random Polynomials" (*),
  80. which describes a *CRC-like* system for integrity checking in (what I have
  81. called) an *intra*-machine environment (which is the environment which is
  82. relevant for detection of viral infection).  The system I am recommending is
  83. essentially the same as Rabin's, but it's augmented by special techniques to
  84. take care of viruses which exploit DOS loopholes, precautions to ensure that
  85. the generator and table of fingerprints (= checksums = hash values) are
  86. inaccessible to attackers, and measures to enforce the rules.
  87.  
  88.                                      Y. Radai
  89.                                      Hebrew Univ. of Jerusalem, Israel
  90.                                      RADAI@VMS.HUJI.AC.IL
  91.  
  92. (*) Harvard Univ. Tech. Rep. TR-15-81 (1981).
  93.