microwaving rfid's

[Owen Lewis]

> -----Original Message-----
> From: ukcrypto-admin@chiark.greenend.org.uk
> [mailto:ukcrypto-admin@chiark.greenend.org.uk]On Behalf Of Brian Beesley
> Sent: 05 March 2004 09:32
> To: ukcrypto@chiark.greenend.org.uk
> Subject: Re: microwaving rfid's
>
> > http://www.md5crk.com/
> >
> There are valid criticisms as to the MD5 algorithm but whether there is
> sufficient computer power available to make this a _real_ problem
> right now
> is debatable. Whether the agencies concerned are "white hat" (with
> essentially unlimited funding), "black hat" (with essentially unlimited
> manpower) or pure research is essentially irrelevant.


Thanks for the interesting post and link.

Something does seem not right though. As the MD5crk folks say, MD5 is widely
used to authenticate financial transactions. They also claim that the
current cost of custom-building a MD5 cracker would be c. GBP 60K (which is
peanuts). Serious criminals run a business (which is why some business is
known as 'organised crime')and business is about obtaining a return on your
investment; a reward for your risk.

AIUI, the MD5 hash on an electronic financial instrument replaces the
manuscript signature on the paper instrument that would have been used
thirty years ago for the same purpose of ordering value transfer. How much
harder is it to create and submit in timely fashion a substitute electronic
financial instrument with the correct 'collided' hash than it would have
been (is) to do forge a signature on a paper one? Rather harder I do
believe.

Successful fraud utilising a forged signature is certainly known (though
relatively uncommon). Why are such significant events successful so rarely?
Because of the other checks on the authenticity of a transaction that are
employed in addition to examination of a signature. In general, these checks
should rise in severity and number with the size of transaction under
consideration. Security, as in golf, needs the use more than a single club
if one is to beat the opposition consistently.

> I've long advocated using at least two different "secure" hash
> functions so
> that there is still some integrity even if one of the functions
> turns out to
> be broken in design or implementation, or not secure enough to
> withstand the
> continuing increase in available computer power.

Then we are really saying the same thing, though I would rather devise
different security cross-checks rather than a second signature constructed
to different rules (e.g. pictograph?) on the same document. Granted though,
that for some specific purposes, a second signature could have particularly
useful functions. But any security engineer whose design relies solely on
the strength of a single security measure should be put against a wall and
shot after reciting Murphy's Law ten thousand times. I am minded too of the
crack someone (Schneier?) published on Roger Needham's TEA cipher shortly
after TEA was released; this required the availability of a totally
impractical number of plain-texts.

So the bottom line is that I cannot see that the point to which the md5crk
folk drive is of great significance. As they point out, that occasional
collisions must occur within the finite number field is certain. given that
one can find duplicate hashes (and in what period of time?) what is the
probability of this duplicate being the hash of a fraudulent electronic
instrument of ones own devising (putting say 10M into your Cayman bank
rather than my local Barclays account)? We agree that a thousand monkeys
typing for all infinity will, at some point, produce a typescript, error
free of the complete works of Shakespeare. Fine. Now what is the probability
of a second group of monkeys typing out the complete works of Tolstoy within
a useful period of the 'success' achievement of the first group, so that the
work of the second group can be passed off as the work of the first?

All this having been said, there is clearly no argument for the indefinite
retention of MD5 as the hash of choice. However, the real world effect of
finding examples of hash collisions does seem less than earth shaking. There
seems to be no risk of an imminent financial disaster. The effect of
cracking keys for a significant cipher in a matter of minutes is altogether
a more serious matter.

Owen