[Date Prev][Date Next] [Thread Prev][Thread Next] [Date Index] [Thread Index]

Re: MD5 collisions found - alternative?

On Tue, Aug 24, 2004 at 12:20:24PM -0400, Phillip Hofmeister wrote:
> On Tue, 24 Aug 2004 at 10:50:38AM -0400, Daniel Pittman wrote:
> > Be aware that this sort of technique "multi-encryption" technique can
> > lead to significant exposures when applied to traditional crypto; it can
> > produce results that allow a vastly simpler attack on the protected
> > information.
> > 
> > I would not put my name to a recommendation about how to make a
> > cryptographic product or protocol "more secure" unless I had sufficient
> > background in the area to know the full implications of my recommended
> > actions.
> If I understand your postulate correctly:
> If I, the user, encrypt a message with algorithm X and the cipher text
> is intercepted by the attacker.  The attacker can make his chances of
> brute forcing the text BETTER by encrypting my cipher text with algorithm
> Y.  This simply does not hold up.

For random values of X and Y, you are correct, there is no reason to assume
that you will get an easier time of it.  However, there are plenty of
examples where (for instance) applying the same algorithm N times
does not produce N times the security, or even the same level of security. 
The same adverse interaction occurs when you mix different algorithms.

However, the weakness typically occurs when the same (or otherwise
equivalent or transformed) key is used for both algorithms.  You don't so
much brute-force the text as the key in most attacks, and application of the
same (or equivalent) key multiple times often has the effect of weakening
the key's "secretness".  This often occurs by being able to analyse the
resultant message and cutting out large swathes of keyspace to search based
on the properties of the ciphertext.

So an attacker applying another algorithm after the fact, not knowing the
original key used (if he did, why would he need to break the ciphertext the
hard way?) is unlikely to make it any easier on himself.

In the case of hashing algorithms, there's one 'key' involved -- the
plaintext -- and for password security, you don't need to retrieve the key
necessarily, just an equivalent one.  There's no guarantee that XORing MD5
and SHA-1 isn't going to produce something that is quite simple to generate
equivalent plaintext for, by, for example, making it mathematically
impossible for one bit in the resultant hash value to be a certain value
(because MD5 and SHA-1 always set the same bit to the same value given the
same input).  That cuts your hash search space in half right there.

It's those sorts of tricky interactions (which aren't immediately obvious)
which I'm sure led Daniel to warn of the dangers of simplistic "security

- Matt

Attachment: signature.asc
Description: Digital signature

Reply to: