Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!netnews.upenn.edu!vax1.cc.lehigh.edu!sei.cmu.edu!krvw From: well!rsa@lll-crg.llnl.gov (RSA Data Security) Newsgroups: comp.virus Subject: Re: Authentication/Signature/Checksum Algorithms Message-ID: <0008.9001081228.AA09399@ge.sei.cmu.edu> Date: 5 Jan 90 17:26:20 GMT Sender: Virus Discussion List Lines: 69 Approved: krvw@sei.cmu.edu In response to Y. Radai's post: To protect against viruses, the best protection can be obtained by using a fast hashing algorithm together with an assymetric cryptosystem (like RSA). This is also by far the most cost-effective (based on compute-time) approach. A good "message digest" should be a one-way function: it should be impossible to invert the digest and it should be computationally infeasible to find two useful messages producing the same digest in any reasonable amount of time. The algorithm must read every bit of the message. Therefore, the best one is the fastest one deemed to be secure. This should not be left to individual users to develop as Jeunemann and Coppersmith, among others, have shown that this is not a trivial undertaking. Let's use Snefru and MD2 (Internet RFC 1113) as examples of good ones. The digest attached to a program or message should then be encrypted with the private half of a public-key pair. What is the computational cost of enhancing this process with public-key? Since RSA can be securely used with small public-key exponents such as 3 (see Internet RFC's 1113-1115 and/or CCITT X.509) a small number of multiplies is required to perform a public-key operation such as *signature verification*, where one decrypts an encrypted digest with the public key of the sender (and then compares it to a freshly computed digest). Therefore, the "added" computational cost of using RSA on an AT-type machine is approximately 80 milliseconds (raising a 512-bit number to 3 mod a 512 bit number) REGARDLESS of the size of the file being verified (the digest is fixed, and less than 512 bits, requiring one block exponentiation). Of course the 80 ms gets smaller on faster machines like Suns. I think anyone would agree that that is a fair tradeoff for signer identity verification. Since one "signs" files only once, this "cost" is irrelevant. The cost of verifying, over and over, is what is important. So what do you get for your milliseconds? You always know the source of the digest (and you get non-repudiation, providing an incentive to signers to make sure programs are clean before signing them). No one can change a program and recalculate the digest to spoof you. If schemes like this became widespread, the lack of signer identification would be a hole people would quickly exploit. You also get a secure way to *distribute* software over networks. Pretty hard to do if everyone "does their own thing". The Internet RFC's, if widely adopted, provide a perfect mechanism for this. Regardless of the hashing algorithm employed, there are powerful benefits available if RSA is used with it. And the computational cost is negligible. It may be true that simpler methods are adequate for some people. That determination requires a risk analysis, and people will make their own decisions. It has been shown, however, that if a system can be defeated, it will be. Certainly secure software distribution requires something more than an unprotected hash, since keys will presumably not be shared. This is where public-key has the most value. Using X9.9 is OK if (1) you trust DES (2) can live with its speed, and (3) don't need to distribute trusted software in a large network. X9.9 key management becomes a serious problem in a network like the Internet. It does have the advantage of being a standard, but it was developed for a relatively small community of wholesale banks, not large networks. Note aboput standards: RSA was named as a supported algorithm in the NIST/OSI Implementor's Workshop Agreements (for strong authentication, in the Directory SIG) of December 1989. Jim Bidzos RSA Data Security, Inc.