From: agermain@cmp.com (Germain Arthur)
Date: Wed, 25 Oct 95 06:31:28 PDT
To: fc@all.net (Dr. Frederick B. Cohen)
Subject: RE: MD5 weakness ? [was Re: Netscape Log
Message-ID: <1995Oct25.093123.1151.341076@smtpgate.cmp.com>
MIME-Version: 1.0
Content-Type: text/plain



I have unsubscribed from this mailing list. Please remove my name from   
your personal address lists. Thanks.

ahg3

 ----------
From:  Dr. Frederick B. Cohen[SMTP:fc@all.net]
Sent:  Tuesday, October 24, 1995 4:01 PM
To:  cypherpunks
Subject:  Re: MD5 weakness ? [was Re: Netscape Logic Bomb detailed by   
IETF]


...
> I believe Dr. Cohen's point is that no-one knows, AFAIK, how to prove   
that a
> one-way hash is truly one-way (uninvertible). We cannot prove that MD5   
is
> secure, ergo we cannot (completely) trust it. [Please correct if this   
is a
> substantially incorrect inference.]
>
> One of the standard responses is "it's the best we can do". When people   
said
> this about PGP, FBC made some (IMHO) interesting comments about the
> encryption he uses in various circumstances. Perhaps he would like to   
share
> his personal choices of one-way hash functions with us.

Since you asked:

It's a really complex issue.

 As a fundamental, we know that any "one-way" hash function must
be many-to-one, which means that, in practice, there are always large
numbers (2^large numbers) of sources for any given hash.  This means
that forgeries are always possible.

 I know of no way to prove that (and no convincing argument that
the workload for creating) a forgery is hard for any "one-way" hash
function.  This seems to mean that we are always betting on faith about
these things.

 The techniques that seem to be reasonably good are; modular
exponentiation in a modulus that's the product of two appropriate primes
(a.k.a.  RSA but throw out the private key when you create it); certain
classes of non-linear feedback shift registers of high degree; and some
general class of mixing algorithms like MD5.

 The RSA-type hash is slow, and some great mathematician may show
up tomorrow and lay waste to the whole thing.  Non-linear feedback shift
registers have the advantage that we don't know how to factor
high-degree equations, so we don't know how to make simple closed form
solutions to find output values.  MD5-type systems are good because they
combine diffusion and confusion and avoid a lot of the more well-known
flaws as far as we know.

 None of these reasons are particularly convincing, so I think we
have to take a risk management approach.  So the ultimate question here
is, how much are we willing to bet that nobody can break one of these in
the intended application over a particular time frame.

 I trust the RSA and NLFSR systems, if reasonably well
implemented, for a single short time-frame low-valued transaction.  For
example, pick a good pseudo-random number and create an RSA one-way hash
of 512 bits (the random number issue is of course another whole area),
encrypt the first bloack, Xor with the second block, encrypt the result,
etc.  till done, then Xor again with the original random seed, send the
file and the hash along with the one-way key, and get a confirmation
back within a few days.

 I don't trust any of them as a basis for running a major part of
an economy over open communications links, and I especially don't trust
them when combined or when the security of one depends on another.  To
run an economy, I think you need more redundancy, more personnel
security, more stop-loss capabilities, physically secure devices,
independent checks and balances, etc.

 Someone on this list mentioned that the banking system trusts
the RSA and MD5, etc.  but this seems to me to be a mischaracterization.
They trust these systems to an extent, but they have key change
requirements, regular audits, physical security, relatively secured
communications lines (when compared to the Internet), strong procedural
controls (most of the time), and other such protections, and they still
get hammered for a few million now and then.

 This is probably enough for now, since the list is probably
getting tired of my posts and I have made the major points.

 --
 -> See: Info-Sec Heaven at URL http://all.net
Management Analytics - 216-686-0090 - PO Box 1480, Hudson, OH 44236