Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!uwm.edu!uwvax!tank!cps3xx!netnews.upenn.edu!vax1.cc.lehigh.edu!sei.cmu.edu!krvw From: RADAI1@HBUNOS.BITNET (Y. Radai) Newsgroups: comp.virus Subject: Re: Authentication/Signature/Checksum Algorithms Message-ID: <0014.9001041612.AA05020@ge.sei.cmu.edu> Date: 4 Jan 90 11:01:04 GMT Sender: Virus Discussion List Lines: 136 Approved: krvw@sei.cmu.edu In V2 #258 Ralph Merkle referred to previous discussions in this group on authentication algorithms, and suggested his own one-way hash function Snefru which has the advantage of not requiring secret information and which has better performance than a DES-based system. It's my understanding that the advantages of Snefru are its much faster software implementation and possibility of larger key size than DES, and several ways of choosing between greater security and greater speed. So Ralph Merkle recommends Snefru and Bob Bosen recommends the DES- based X9.9 (he also mentions ISO 8731-2). And going outside of this forum we find that Fred Cohen recommends an RSA-based algorithm, Ro- bert Jueneman recommends his Quadratic Congruential MDC, Prof. Rabin recommends the CRC algorithm using a randomly selected irreducible polynomial, and so forth. Interestingly, none of these authors seems to give any argumentation why his algorithm is any better than the others (except for Merkle's comparison of Snefru with DES). Bob Bosen says in Issue 265 that a sophisticated authentication al- gorithm is clearly better than some programmer's guess at an authenti- cation algorithm (he now adds the condition that both implementing programs are well-written and convenient and "apply the algorithm across all program code without exception"). I can't say that this is incorrect, but even with this addition, I still don't share his emphasis on sophistication of the algorithm. The added sophistication of (say) X9.9, compared to CRC with a person- ally chosen generator, may be well worth the added time in the case of authentication of bank transfers and other conventional applications. But have you considered the possibility, Bob, that this sophistication may be wasted when dealing with viruses? If we were to try to draw a graph showing sophistication on the X- axis and security on the Y-axis, I think everyone would agree that the curve "levels off", i.e. there is a certain point, beyond which making the algorithm more sophisticated has negligible value in increasing security. The difference between the positions of Bob, Ross Green- berg, and myself is partly where we think the curve levels off. Bob's position is that this happens only at a late stage of sophistication, while Ross seems to think it happens at a very early stage. My opin- ion is that for *anti-viral purposes* this point is reached much ear- lier than for more ordinary uses of authentication algorithms, though not quite as early as Ross believes. The reason I think the anti-viral situation is special is that in this environment there are considerations which probably have no coun- terpart in ordinary message authentication. For example: (1) A virus must perform all its work, including circumvention of anti-viral protection (e.g. forging of checksums) if that's what its author desires, on the computer which it's attacking and in a very short time (short enough so that it will not be noticed by the user). (2) By its very nature, a virus is designed to attack a large per- centage of the users of a particular system. From the point of view of the virus writer, any technique which results in circumventing the anti-viral protection of only a single user (or a very few users) is not worthwhile, since if that were what he desired, he could achieve the same thing much more easily by means of an immediate-acting Tro- jan, and against that *no* alteration-detecting program, no matter how sophisticated, can warn us in time. (3) Ordinarily, a virus writer is not in a position to know what checksum algorithms may be in use on the computers on which his virus is unleashed. And any technique for forging the checksums of one al- gorithm will probably not work against any other checksum algorithm. Therefore a checksum-forging technique would increase the percentage of disks infected by only a very small amount, making it a waste of time and effort from his point of view. (An exception would occur if the virus author is satisfied with attacking an environment which is sufficiently limited so that most computers in it use the same check- sum program.) Taking these conditions, mainly (1), into account, it seems to me that a checksum algorithm, expressed as a function F on files, will provide sufficient security for anti-viral purposes if the following two conditions are satisfied: (A) For any given file f, F(f) is (in general) different for each computer. (This condition amounts essentially to requiring a key unique to each computer.) (B) Given a file f, it is computationally infeasible (without know- ledge of the key) to construct a file f' from it containing the de- sired addition of (or replacement of ordinary code by) viral code such that F(f') = F(f). In making this claim, it is assumed that the checksum base, key and program are kept offline (i.e. not located on an accessible disk or in memory while a virus may be active), thus preventing discovery or com- putation of the user's key or circumvention of the checksum program. If the above opinion is correct, then I think that all the algori- thms mentioned in the second paragraph of this posting are adequate for anti-viral purposes, including the relatively unsophisticated CRC algorithm if the generator is selected randomly or personally, and hence the added sophistication of algorithms such as X9.9 is wasted in view of the extra run time which they require. Concerning speed, it can be argued that we shouldn't exclude slower algorithms, since the more algorithms which are in use, the less worthwhile it will be for anyone to try checksum-forging techniques. On the other hand, if one algorithm has a clear superiority over the others in speed, users are hardly likely to choose a slower algorithm because of such an argument. And when speed is the issue it seems to me that CRC, because of its greater simplicity, is better than any of the more sophisticated algorithms satisfying conditions (A) and (B). It's possible, of course, that I'm wrong on one or more opinions ex- pressed above: Perhaps Dr. Merkle or some other crypto-expert can show that conditions (A) and (B) are not sufficient even in the viral environment expressed by (1)-(3) above, so that CRC, even with a ran- dom generator, is insecure. Or that I'm wrong in assuming that such a CRC satisfies these conditions. Or perhaps some other algorithm is faster than CRC and no less secure. But what is needed is evidence and argumentation relative to the *viral environment*, and this I have not yet seen in Bob's writings. I now come to Ross Greenberg's posting in Issue 266. Now I fully agree with him that sophisticated checkers may go unused because of the time required. But Ross implies that users will always prefer a "good enough" fast checker like that of FluShot+ over a slow sophisti- cated one. But can we be so sure that FluShot+ is really good enough? How many of its users have the slightest idea how its security com- pares with that of other programs? I don't know whether his algorithm satisfies condition (B) above, but it certainly does not satisfy (A), i.e. for any given file all users will get the same checksum, and that's a potential security hole, at least in the "limited environment" situation mentioned at the end of (3) above. But since this hole can be plugged very simply and at no cost in speed, why not do so, Ross? One final remark. Bob Bosen writes: >In his mailing of Dec 07 '89, Y. Radai seems to be taking the position >that since I am in favor of sophisticated authentication algorithms, I >must be against sophisticated program implementations. Nothing could >be further from the truth. Such a position may indeed be far from the truth. But so is the no- tion that I was taking such a position! I was not assuming that you were *against* sophisticated program implementations; I was merely concerned by your not having *mentioned* the need for very careful im- plementation in a given system. That's a big difference. Y. Radai Hebrew Univ. of Jerusalem, Israel RADAI1@HBUNOS.BITNET