Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!brutus.cs.uiuc.edu!jarthur!polyslo!vlsi3b15!vax1.cc.lehigh.edu!sei.cmu.edu!krvw From: RADAI1@HBUNOS.BITNET (Y. Radai) Newsgroups: comp.virus Subject: Re: Signature Programs Message-ID: <0010.9002132006.AA19225@ge.sei.cmu.edu> Date: 13 Feb 90 15:08:07 GMT Sender: Virus Discussion List Lines: 181 Approved: krvw@sei.cmu.edu There have been a few responses to my postings on signature (or checksum) programs and algorithms in V2 #256 and V3 #4, resp., mainly by Bob Bosen. Let me begin by briefly summarizing my earlier postings: In the first posting I pointed out that what has to ensure security on a computer is not simply an algorithm, but rather a *program* which implements it in a given operating system. And even a program based on the most sophisticated checksum algorithm in the world is circum- ventable if it is not written very carefully, since there are liable to be (and in PC-DOS/MS-DOS definitely *are*) loopholes in the system which are independent of the checksum algorithm and which a virus writer could exploit. Bob Bosen responded to this point only by saying that in the compa- rison of algorithms, both implementing programs must be well-written and convenient and "apply the algorithm across all program code without exception". Well, that last phrase may suggest to some people that it's necessary to checksum the boot sector and partition record also, but otherwise, this requirement is insufficient, at least as I understand Bob's words. And even if we interpret it in such a broad manner that it becomes theoretically correct, this rule is rather useless; it gives the checksum-program writer no clue whatsoever as to how to plug most of the loopholes. I considered, and still consider, this emphasis on the implementing program, rather than on the algorithm, to be fully justified. One way of putting it is that given a choice between a sophisticated algo- algorithm with poor implementation and a mediocre algorithm with good implementation, I would prefer the latter. Of course, it's not really an either-or matter; there's nothing to prevent us from striving for quality in *both* aspects. And as long as one is aware that a naive implementation of an algorithm is very dangerous, and is aware of the great difficulty of conceiving of all of the loopholes, I suppose it makes sense to ask which of several algorithms is best, given the *assumption* that all are implemented equally well. So in my later posting, I suspended discussion of im- plementation and restricted myself to algorithms. I mentioned six of them and expressed the opinion that for anti-viral purposes (which I characterized by three properties but there are actually more), any algorithm which satisfied a certain pair of conditions should be suf- ficiently secure. I considered the best algorithm to be the fastest of those satisfying these two conditions, my guess being that this would be CRC. However, I specifically mentioned three points on which I might be wrong. I concluded by challenging people to supply evi- dence and argumentation relative to the viral environment. Bob Bosen took up my challenge as far as argumentation is involved: > Specifically, in his opinion (1), Mr. Radai says that a >virus must perform all its work ... "on the computer which it's attacking >and in a very short time". That is not necessarily true. In networked >environments with shared file systems, (and especially if remote >execution is available), viruses could execute on different computers and >take as much time as they needed. Also, as pointed out by Bill Murray, >viral infections during the process of software distribution may be done >off-line at the convenience of the attackers. But as Bill correctly pointed out, we have in mind two different ap- plications of authentication software: (I) for recognizing contamina- tion of the program in the target execution environment; (II) for en- suring that programs are received as they are shipped. (II) is un- doubtedly important, but my articles were concerned only with (I) (sorry I didn't state this explicitly), hence Bob's reference to in- fection during software distribution is not relevant to my remarks. As for networked environments, he's right, there are *some* such environments in which property (1) would not hold. However, the average user does *not* operate in such an environment. Why should *he* choose a slow program just because it adds security in *such* an environment? >I must also disagree with Mr. Radai's opinion (2), wherein he posits "By >its very nature, a virus is designed to attack a large percentage of the >users of a particular system." Why? What's to prevent a virus writer from >launching a "surgical strike" against a small population of familiar >computers that are known to control assets or information of great value? I must say I find this response rather surprising, considering that the answer to your question is contained in the continuation of the very same paragraph from which you're quoting me. In case it wasn't clear, I'll rephrase that answer: There's nothing at all to prevent such a strike, but if such a strike is made, there's no reason why it has to be a *viral* strike. The great advantage of writing a virus, as compared to an ordinary immediate-acting Trojan horse (which I'll abbreviate here to simply "a Trojan") is that by delaying its damag- ing effects and replicating itself, it can spread rapidly to a large population of users and thus ultimately cause damage to many more users. But it has the disadvantage that the delay of damage gives checksum programs a chance to detect the infection. Now if you're talking about performing damage to only a *small* population, then there's not much advantage to writing a virus rather than a Trojan. A Trojan is easier to write and can't be detected by a checksum pro- gram. So to your question of what's to prevent a viral strike against a small population, I counterpose the question What's to prevent a *Trojan* attack against a small population? What could your sophisti- cated algorithm do against that?? The answer is Nothing. Even ISO 8731-2 raised to the X9.9-th power would be helpless against an imme- diate-acting Trojan. >As to Mr. Radai's opinion (3), he says that "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." That's true TODAY. .... > .... But if our society is >ever going to overcome its current vulnerability, we'll need reliable, >low-cost defense mechanisms that are worthy of widespread use. This >implies a necessity for economies of scale. Therefore, this opinion (3) >will not necessarily be true for very long. I appreciate this looking to the future (which is why I mentioned loopholes which have not yet been exploited in any existing virus). However, I'm less enthusiastic about this particular point. I presume that when Bob talks of the need for "reliable low-cost mechanisms" and "economies of scale" he is referring to his previously expressed opin- ion that someday there may be only a few high-quality programs used by millions of people. Frankly, I find the "few" part of this rather unlikely. If anything, the trend seems to be in the opposite direc- tion. (For example, there's a new algorithm MD4 which has been de- scribed by Ronald Rivest.) And even if the situation envisioned by Bob should someday arise, I think it would still be quite difficult to exploit. In any case, properties (2) and (3) were less important to my case than (1). And there's an important fourth property of the environ- ment which I neglected to mention. Almost all types of attacks pro- posed by cryptanalysts against signature algorithms involve *knowledge of the signature* of one or more files, which is natural in Applica- tion (II). It therefore requires a very secure algorithm. But in the environment I am considering (Application (I)), such knowledge and hence such attacks are impossible even with an unsophisticated algo- rithm such as CRC, provided different users use different keys, and the checksum base etc. are kept offline while a virus may be in memory. > From what I've >read in this forum of late, it does appear that Ross Greenberg and Y. >Radai are at one end of this spectrum and that Bill Murray, Ralph Merkle, >Jim Bidzos, Fred Cohen, and the others mentioned in Mr. Radai's Jan. 4 >posting are more or less at the other end with me. (If I've >misrepresented your views here, gentlemen, I hope you'll forgive and >correct me for it. I'm reading between the lines.) First, don't forget that the "others" mentioned in my posting include Prof. Michael Rabin, and that the algorithm which he advocated was the same, relatively unsophisticated, algorithm which I consider (tenta- tively) to be the best. (I take this opportunity to point out that the algorithm of Rabin's to which I am referring is from a little- known paper of his, and is not to be confused with a better-known algorithm of his which involves taking the square root of the message [= the file] modulo the product of two secret primes.) As concerns your lumping me together with Ross Greenberg at the low end of the sophistication spectrum, that picture is not far from cor- rect only if you limit yourself to the *algorithm* involved. As re- gards security of the *implementing program*, I'm miles away from Ross. Although I have said that I tentatively consider CRC to be the best algorithm for the purposes which I am considering, I wish to empha- size that I am in no way committed to it. If someone can produce evidence that some other algorithm is both more secure in the environ- ment with which I am concerned and is faster or almost as fast as CRC, I'm willing to alter my opinion. However, what it takes to convince me (and I think a lot of other readers) is not a proclamation that Committee X has adopted Algorithm Y as its standard, but *an actual comparison of programs which implement the various algorithms*. In comparing speed, we will, of course, take into account what Bob has pointed out, namely that a program can be written to implement a sophisticated algorithm on a small part of the file and a fast algo- rithm on the rest. Obviously, such "hybrids" could also be among the contenders. Comparing security is much trickier since the results will depend strongly on what test viruses we can think of. So no such test can ever be conclusive. But it should be more convincing than mere proc- lamations and appeals to the authority of some committee or other. (By the way, I made a challenge to compare the security of programs by such tests over a month ago; why no response?) It is only when we have the results of such comparisons that each user will be in a position to decide which program is best suited to his needs. My guess is that for Application (I) there won't be many users who will choose a program which is based on a sophisticated algorithm. Y. Radai Hebrew Univ. of Jerusalem, Israel RADAI1@HBUNOS.BITNET