🚀 go-pugleaf

  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