🚀 go-pugleaf

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.