Re: What is md5sum?

From: P.T. Breuer (ptb_at_oboe.it.uc3m.es)
Date: 06/30/04 

Date: Wed, 30 Jun 2004 11:28:54 +0200

Micha? Kosmulski <M.Kosmulski@nospam.elka.pw.edu.pl> wrote:
> [ptb]
> > They aren't. They're in "silly mode". You seem to believe in infinitely
> > large numbers - cease, desist. The universe you can touch and smell is
> > finite. There aren't 2^128 different files out there and there aren't
> > going to be.
> There is no need to be 2^128 different files. 2 is enough to get a collision
> if it's the right two files.

Provide me them, or a construction that provides them (and a computer
program that lists all of them and calculates the md5sums won't work -
it would die before getting anywhere at all).

> > Even more than that, it's factually correct. Adjust your logic away
> > from silly classical socratean nonsense. Cease believing in the
> > infinite, the continuum hypthesis, the axiom of choice, and other
> > acts of unsupported and unsupportable faith, and simply believe in
> > what you can test.
> Strangely enough, mathematics seems to be used for quite a few things
> these days. While it is not a strict representation of our world (which
> it doesn't try to be), it gives quite good results. I don't know how far

That's OK - but remember that it's an approximation. An "abstraction",
if you prefer. A "theory". The theory has rules of formal logic and
that's all fine. The problem comes when you try and move from the
theoretical realm across into making predictions using the theory. Then
you have several problems to consider. At least:

  1) are the formal logical rules of reasoning a proper abstraction of
     the way the universe is?
  2) are the logical hypotheses (tenets, beliefs) proper abstractions
     of the sitauation in the real universe?

Nobody has bothered to consider that there aren't and can't be 2^128
(say 2^100, to please you!) files examined by any computer anywhere on
earth, therefore no computer can ever carry out the constructive
procedure you propose.

> engineering would be today if someone rejected using integrals since
> "they are a sum of infinitely many infinitely small components, and that

Riehmannian integration has a perfectly well-defined theory that does
not require infinistesimals (although you can use nonstandard logics
which do use infinitesimals in order to construct the Riehamannian
theory). It's constructed on notions of limits - that is, you can get
as close as you like to the integral by making calculations as fine as
you like.

More math shows that the classic Riehman integral remains an integal also
under a more general approach, which is more used today.

> doesn't make sense".

What you say is nonsense, but the Riehman integral does make sense.
Whether that means that integrals physically exist is another question.
You may well argue that nothing in the universe has an integral area
(you get into fractals and quantum problems when you look closely).

> As for "simply believe in what you can test" - can
> you can prove to me that "2+2=4" ?

Easily. It's one of the earliest exercises in math. 2 is defined as
1+1 and so I merely have to show that 2+(1+1) = 4, which is defined as
3+1. It thus suffices to show that 2+(1+1) = (2+1)+1, because 3 is
defined as 2+1. In general we want n+(m+1) = (n+m)+1. Thankfully that
is how addition is defined: by the rule n+(m+1) = (n+m)+1 for numbers
m+1 which are greater than zero, and by n+0 = n in the case of 0.

Now try and show that two apples plus two apples equals four apples.

> > Find any two. You will get the Turing prize!
> A dramatic misunderstanding ! One doesn't have to show them to prove
> they exist.

Oh, yes one does. What makes you think you don't? (you are supposed to
think about how you may convince me).

> A somewhat different example, perhaps easier to grasp:
> 1. Find a random three digit number (only three digits, so you can't say
> we're dealing with infinitely large numbers here) which ends with 0, 2,
> 4, 6 or 8.

OK : 124

> 2. I can tell you the number you chose is even. But I don't know what
> that number is !

Sure, you can tell me about the properties of the number I chose. So?
Can you show me that there is a decimal sequence that is impossible to
describe? (there must be one, since you can only describe at most
countably many, even being charitable, and elementary Cantorian theory
tells us that the cardinality of the decimal sequences is inommensurable
with that of the counting numbers). Fine - describe it!

What's the matter? You "know" that there is such a nonempty set, but
you find yourself unable to "choose" a representative element to show
me?

Great. Now you know that "choosing" is not as axiomatic a thing as you
may think. In fact it IS an axiom - formally unprovable, and formally
impossible to contradict - that you may choose an element of any set.

Fantastic, so even though you "know" that there "are" two files with
the same md5sum, you find yourself curiously unable to CHOOSE a pair to
show me!

> > No, you don't understand - to have, say, a one in a thousand chance of
> > there being two files somewhere in earth with the same md5sum, you
> > would have to produce of the order of 2^90 different files. Do you know
> > how much energy that would take? More than you think, is the answer.
> Again - you don't have to have all 2^128 numbers stored in any way to
> find a collision.

You have to have somewhere close.

> Just any 2 which have the same hash code.

Show me them.

> The fact
> that noone has found a collision so far doesn't mean that it's
> impossible that e.g. tomorrow someone finds one.

It's not impossible that the moon will decide to change its orbit and
crash on your head tomorrow. But I am willing to bet you all the money
on earth (and what I own) that tomorrow nobody will find two files with
the same md5sum. That is truth.

> People seem to have little understanding of how probability works.

No, you don't. And nobody knows how probability works, because it's not
a physical theory - try reading some books on the subject of how
probability theory may relate to reality, if at all.

> The fact that probability of something is very low doesn't mean it's
> never going to happen.

You seem unfortunately confused between probability and statistics. The
probability of something being low says nothing at all about whether
the event associated with that probability will happen or not.

> It _probably_ won't ever happend, but it could.

You seem confused. What are the experiments you are performing? Are you
going to run the universe once, see if it happens, then stop the
universe, restart it and run the experiment again?

> So, we should not be afraid of someone finding a collision in MD5, but
> strictly speaking, it is possible and might happen some day.

No, it will not happen any day. Let me put it this way - if you think
it is possible, then why not bet me on it? I am happy to bet you!

Peter

Relevant Pages

  • Re: probabilistic definition of an ultrafilter?
    ... Obviously it can't be an explicit *construction* of a free ultrafilter ... member of U iff X is, with unit probability, a superset of any finite ... "randomly chosen first-order formula". ... In this case your condition says that X is a superset ...
    (sci.logic)
  • Re: What is md5sum?
    ... > When did I say that the rest of the universe is wrong?? ... When you say that md5sum does not identify a files contents uniquely. ... draw mechanism was capable of producing them, ... Unfortunately this mathematical construction is not physically FEASIBLE ...
    (comp.os.linux.setup)
  • Re: Uncountable sets in CZF?
    ... | Does the construction of L require AC to begin with? ... context, namely the universe. ... Therefore L is a submodel (not ... necessarily proper) of V. ...
    (sci.math)
  • Re: Dont get Axiom of Choice?
    ... Goedel's result does give an obvious interpretation ... Cohen's construction in effect supplies a value to ... AC was proved consistent was by trimming down the ... universe to something small enough to make AC true. ...
    (sci.math)
  • Re: Is there a Platonistic interpretation of the empty set?
    ... Other than a mark on paper, what, ... "world" the empty set is the basis of everything that exists, ... since using the classic construction: ... It is like a "seed" that generates the entire universe or ...
    (sci.math)