🚀 go-pugleaf

  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