Path: gmdzi!unido!mcsun!uunet!samsung!brutus.cs.uiuc.edu!wuarchive!
mailrus!accuvax.nwu.edu!tank!eecae!netnews.upenn.edu!vax1.cc.lehigh.edu!
sei.cmu.edu!krvw
From: well!r...@apple.com (RSA Data Security)
Newsgroups: comp.virus
Subject: Digital signatures for virus protection
Message-ID: <0004.8911061211.AA07948@ge.sei.cmu.edu>
Date: 4 Nov 89 00:58:48 GMT
Sender: Virus Discussion List <VIR...@IBM1.CC.Lehigh.EDU>
Lines: 46
Approved: kr...@sei.cmu.edu
Posted: Sat Nov  4 01:58:48 1989

The most effective method available to detect *any* change to a
program is through the use of digital signatures.  A "message digest"
(much more mathematically secure than a checksum) is encrypted with
the private key of a public key cryptosystem (the private key may be
yours or someone you trust).  The verification process is then as
follows:

- -	recompute the message  digest
- -	decrypt the encrypted message digest with the public key
	of the "signer" - the public key need not be secret
- -	compare the two

If they match, the file is unaltered.  No one can recompute and
attach a mailicious signature since only the signer holds the private
key.  One paper by Maria Pozzo & Terry Gray of UCLA in January 1987
describes in detail how an operating system can use digital
signatures based on public key cryptosystems to execute only
"trusted" programs.

Since no one can "forge" a signature, it is possible that
software developers can "sign" their programs, essentially taking
responsibility for their contents.  This would provide a strong
incentive for the publisher to ensure a program was clean before
signing it.  Note: there are simple, effective ways to validate
public keys before using them to verify signatures.

There are inexpensive commercial products available now for DOS, Mac
OS, UNIX and VMS that do exactly this.  They use a *secure* message
digest algorithm which is 60 times faster than DES on 32 bit
machines.  The digest size is 128 bits (anything less is *not*
cryptographically secure - there are a number of papers on the
subject).

Simple uses of DES has even been shown to be unsafe for checksums; it
is vulnerable to attacks based on the birthday paradox which says
that as the number of *useful* message variants approaches the square
root of the total number of possible checksums (2^64 with DES), the
probability that an attacker can match a checksum with a useful
modified message exceeds 50%.  Since (at least in DOS) you can add
any number of bits to the end of a program without affecting its
execution, programs are particularly vulnerable.

Disclaimer: RSA Data Security designs, develops and markets the
above mentioned software.

Jim Bidzos