Quoting RFC #1321, Section 1:

"It is conjectured that it is computationally infeasible to produce
two messages having the same message digest, or to produce any
message having a given prespecified target message digest."

This conjecture has now been determined to be false. In fact, a single 
laptop can perform both these tasks in a few minutes using a suitable 
algorithm.

However, one might also conjecture that the probability of any two 
arbitrary messages having the same [MD5] hash code would be 2^(-128).

Does the existence of a collision-generation algorithm for MD5 
contradict this second conjecture?

(In othe words, it is possible to *maliciously* alter a message without 
affecting the MD5 hash, but what is the probability of an *accidental* 
modification going undetected? Is it 2^(-128)? Or is it some higher 
probability?)

Post a reply to this message

Invisible wrote:

> However, one might also conjecture that the probability of any two 
> arbitrary messages having the same [MD5] hash code would be 2^(-128).

Actually, according to the Birthday Paradox, the probability in this 
case is much lower.

All I *really* want to know is the probability of a random alteration to 
a file going undetected by an MD5 hash comparison. But this depends on 
just how "random" MD5 really is. Apparently it's not something anybody 
has looked at much. The existence of a collision algorithm seems to 
suggest that it's not all that random, but I don't know...

Post a reply to this message

Invisible <voi### [at] devnull> wrote:
> All I *really* want to know is the probability of a random alteration to 
> a file going undetected by an MD5 hash comparison.

  I think it's quite unlikely.

  I wonder how much more unlikely it would be if you calculated two MD5
codes: The first one is calculated in the regular way, and the second one
is calculated starting from the second byte in the file forwards, and taking
the first byte as if it was the last (iow. effectively as if you had removed
the first byte of the file and appended it to the end of the file).

  A random change which would keep one of the MD5 sums the same would
quite unlikely keep the other one the same too. I have no idea about the
probabilities, though.

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
> Invisible <voi### [at] devnull> wrote:
>> All I *really* want to know is the probability of a random alteration to 
>> a file going undetected by an MD5 hash comparison.
> 
>   I think it's quite unlikely.

I think it's astronomically unlikely. I'd just like to be able to put a 
hard number on that though. ;-)

>   I wonder how much more unlikely it would be if you calculated two MD5
> codes: The first one is calculated in the regular way, and the second one
> is calculated starting from the second byte in the file forwards, and taking
> the first byte as if it was the last (iow. effectively as if you had removed
> the first byte of the file and appended it to the end of the file).
> 
>   A random change which would keep one of the MD5 sums the same would
> quite unlikely keep the other one the same too. I have no idea about the
> probabilities, though.

Alternatively, take the MD5 *and* the SHA-1 hash as well. Or better yet, 
take the MD4, MD5, SHA-1, SHA-256, WIRLPOOL and RIPEMD hashes.

But let's face it, "md5sums" is a psuedo-standard file format that is 
quite widely recognised.

The real reason we're interested in this is for checking that CDs are 
readable. Currently, we "check" the CD by looking at the directory 
listing and confirming that every file is present and has the correct 
size in bytes.

In other words, we check that the Table Of Contents on the CD has been 
burned correctly. :-P

In a sense, the important point about MD5 is that checking a CD this way 
ensures that every single bit of data is physically read from the 
surface of the disk. If you can do that, the data is probably correct 
anyway...

(Let us not forget that the CD itself puts the data through two seperate 
layers of Reed-Solomon codes anyway, not to mention filesystem metadata 
probably has CRC32 checksums in there.)

If a CD is defective, you're far more likely to get read/write errors 
from the operating system than actual garbage data, so perhaps the 
actual hash value is irrelevant.




By the way, do you know how MD5 works? It's kind of interesting. I'm 
currently trying to implement it in Haskell - but I'm being thwarted 
because it uses that brain-deadness known as "little-endian integers". 
(These really shouldn't exist...)

Basically, you take your file and split it into 512-bit blocks, padding 
the final block to make it exactly 512 bits. (Actually it's slightly 
more complicated than that.) Then, starting from the hash value

   0123456789ABCDEFFEDCBA9876543210

you process each block using the MD5 "compression function", which 
updates the hash value. Add the new hash value to the previous hash 
value to get a final output, and then repeat for the next block. When 
all blocks have been processed, whatever the final hash value is, *that* 
is the MD5 hash value.

In particular, if you change one particular message block in such a way 
that the compression function maps it to the same value, then the MD5 
hash of the whole file will be unchanged. So you really want to 
scrutinise that compression function...

The compression function itself consists of a loop repeated 16 times, 
each time with different parameters. At each loop, you rotate the hash 
round, and mutate one of the 32-bit words within it. You do this by 
adding a mash value to it; this mash value is derived from

- A table of constants (derived from the sin(x) function)
- A bit-wise combination of the other 32-bit words in the hash. (The 
exact combination varies throughout the loop.)
- A 32-bit word from the input block. (The exact one is determined by 
the loop counter, but with a nontrivial relationship.)

The mash value is also bit-rotated by a loop-specific amount first.

And that, my friends, is basically the MD5 algorithm... It certainly 
*looks* like it should give your data a good mashing, but on the other 
hand, there are loads of places where you can say "hmm, if somehow the 
same numbers got here, the results would be identical".

Post a reply to this message

Invisible wrote:

> The compression function itself consists of a loop repeated 16 times, 
> each time with different parameters.

Gah! 64 times... >_<

Maybe I should just stop typing now? :-S

Post a reply to this message

Invisible escribió:
> By the way, do you know how MD5 works?

I would assume Warp knows... :)

Post a reply to this message

Invisible wrote:
> Quoting RFC #1321, Section 1:
> 
> "It is conjectured that it is computationally infeasible to produce
> two messages having the same message digest, or to produce any
> message having a given prespecified target message digest."
> 
> This conjecture has now been determined to be false. In fact, a single 
> laptop can perform both these tasks in a few minutes using a suitable 
> algorithm.

Do you have a cite for this? I'd heard of the first problem being 
broken, but not the second one.

> However, one might also conjecture that the probability of any two 
> arbitrary messages having the same [MD5] hash code would be 2^(-128).
> 
> Does the existence of a collision-generation algorithm for MD5 
> contradict this second conjecture?

Only if you do it on purpose. Obviously, to *arbitrary* messages will 
have low probablility of a hit.

> (In othe words, it is possible to *maliciously* alter a message without 
> affecting the MD5 hash, but what is the probability of an *accidental* 
> modification going undetected? Is it 2^(-128)? Or is it some higher 
> probability?)

It's still a low probability. You have to alter the message in a way 
that takes specifically into account how MD5 works. That's why the same 
technique doesn't work on other hashes.

> Actually, according to the Birthday Paradox, the probability in this case is much
lower.

Not with only two messages.

> But this depends on just how "random" MD5 really is. Apparently it's not something
anybody has looked at much. 

People looked for any collision for a decade or more before the folks 
who professionally analyze cryptographic systems figured out how to 
cause a collision. It's sufficiently unlikely a random change in a file 
will cause you any grief that you need to worry about it.

The reason people worry about it is they fear an active, intelligent 
adversary changing that which has been signed.

> In a sense, the important point about MD5 is that checking a CD this way ensures
that every single bit of data is physically read from the surface of the disk. If you
can do that, the data is probably correct anyway... 

Since the TOC is at the start of the CD, I find this much more likely to 
be broken. Checksum the TOC, the first file, and the last file, and 
*then* you don't have to read the whole CD. I'd say 1/3rd of my CDs that 
coaster have a good TOC and no actual file data on them.

> there are loads of places where you can say "hmm, if somehow the same numbers got
here, the results would be identical".

And that's exactly how they went about cracking it. :-)

-- 
   Darren New / San Diego, CA, USA (PST)
     Remember the good old days, when we
     used to complain about cryptography
     being export-restricted?

Post a reply to this message

Darren New wrote:
> Invisible wrote:
>> Quoting RFC #1321, Section 1:
>>
>> "It is conjectured that it is computationally infeasible to produce
>> two messages having the same message digest, or to produce any
>> message having a given prespecified target message digest."
>>
>> This conjecture has now been determined to be false. In fact, a single 
>> laptop can perform both these tasks in a few minutes using a suitable 
>> algorithm.
> 
> Do you have a cite for this? I'd heard of the first problem being 
> broken, but not the second one.

Wikipedia. (So... utterly trustworthy then. Mind you, I believe there's 
a reference at the bottom.)

You know how it is - somebody posts a near-break, somebody else extends 
it, somebody else makes it go faster, etc.

>> However, one might also conjecture that the probability of any two 
>> arbitrary messages having the same [MD5] hash code would be 2^(-128).
>>
>> Does the existence of a collision-generation algorithm for MD5 
>> contradict this second conjecture?
> 
> Only if you do it on purpose. Obviously, two *arbitrary* messages will 
> have low probablility of a hit.

Well... the fact that collisions can be constructed prove that they 
exist, which might suggest the function is "less random" than it should 
be...

>> (In othe words, it is possible to *maliciously* alter a message 
>> without affecting the MD5 hash, but what is the probability of an 
>> *accidental* modification going undetected? Is it 2^(-128)? Or is it 
>> some higher probability?)
> 
> It's still a low probability. You have to alter the message in a way 
> that takes specifically into account how MD5 works. That's why the same 
> technique doesn't work on other hashes.

True. I'd just like to put a number to it, that's all. ;-)

>> Actually, according to the Birthday Paradox, the probability in this 
>> case is much lower.
> 
> Not with only two messages.

Probability is defined as "if you did this X times, Y times the event 
would occur". So even with 2 messages, it matters.

>> But this depends on just how "random" MD5 really is. Apparently it's 
>> not something anybody has looked at much. 
> 
> People looked for any collision for a decade or more before the folks 
> who professionally analyze cryptographic systems figured out how to 
> cause a collision. It's sufficiently unlikely a random change in a file 
> will cause you any grief that you need to worry about it.

Well, if people searched for decades without finding any collisions, 
they must be reasonably rare then. (At least, for the kinds of messages 
people tried hashing.) That suggests that at least the function doesn't 
collide *massively* more often than it should...

> The reason people worry about it is they fear an active, intelligent 
> adversary changing that which has been signed.

Ah yeah, sure, MD5 isn't cryptographically secure. I get that. I'm just 
wondering how useful it is for detecting random alterations.

>> In a sense, the important point about MD5 is that checking a CD this 
>> way ensures that every single bit of data is physically read from the 
>> surface of the disk. If you can do that, the data is probably correct 
>> anyway... 
> 
> I'd say 1/3rd of my CDs that 
> coaster have a good TOC and no actual file data on them.

...which is why just checking that you can "see" the filenames is no 
good at all. Clearly the person who wrote the official procedure is a 
legal expert not a computer expert...

>> there are loads of places where you can say "hmm, if somehow the same 
>> numbers got here, the results would be identical".
> 
> And that's exactly how they went about cracking it. :-)

The worrying thing being, how likely is it that such a thing might just 
happen by accident? :-}

Post a reply to this message

Orchid XP v7 escribió:
> Well... the fact that collisions can be constructed prove that they 
> exist, which might suggest the function is "less random" than it should 
> be...

The fact that the digest is smaller than the input data proves that 
collisions exist. If the digest is 1 byte smaller than the input data, 
there are 256 collisions possible.

The question is how easily you can "construct" a collision (if the only 
  way is testing *all* combinations of bits, the hash function would be 
"ideal").

Post a reply to this message

> By the way, do you know how MD5 works? It's kind of interesting. I'm 
> currently trying to implement it in Haskell - but I'm being thwarted 
> because it uses that brain-deadness known as "little-endian integers". 
> (These really shouldn't exist...)

Someone at Oxford has done it, but I think it uses the FFI.
http://web.comlab.ox.ac.uk/oucl/work/ian.lynagh/md5/haskell-md5-0.1.0/

Post a reply to this message

Nicolas Alvarez wrote:

> The question is how easily you can "construct" a collision.

Actually, I think the question is how evenly scattered the collisions 
are... ;-)

Post a reply to this message

Tim Attwood wrote:
>> By the way, do you know how MD5 works? It's kind of interesting. I'm 
>> currently trying to implement it in Haskell - but I'm being thwarted 
>> because it uses that brain-deadness known as "little-endian integers". 
>> (These really shouldn't exist...)
> 
> Someone at Oxford has done it, but I think it uses the FFI.
> http://web.comlab.ox.ac.uk/oucl/work/ian.lynagh/md5/haskell-md5-0.1.0/ 

In fact, *several* people have done it - ranging from FFI bindings to 
existing MD5 libraries to pure Haskell implementations in different forms.

I'm mainly trying to implement it in Haskell for fun; it'll probably go 
too slow to be useful. (But we'll see about that...)

Post a reply to this message

Orchid XP v7 wrote:
> Wikipedia.

Of course. Duh. Still getting used to these intratubes, ya know.

>> Only if you do it on purpose. Obviously, two *arbitrary* messages will 
>> have low probablility of a hit.
> 
> Well... the fact that collisions can be constructed prove that they 
> exist, which might suggest the function is "less random" than it should 
> be...

First, yes, of course they exists. As soon as you have meesages >128 
bits, you by necessity have collisions. Second, the function isn't 
supposed to be random, it's supposed to be non-invertible.

> True. I'd just like to put a number to it, that's all. ;-)

Two arbitrary files? Probably very close to 2^(-128)

>>> Actually, according to the Birthday Paradox, the probability in this 
>>> case is much lower.
>>
>> Not with only two messages.
> 
> Probability is defined as "if you did this X times, Y times the event 
> would occur". So even with 2 messages, it matters.

The birthday paradox says "how many people can you put in a room before 
there's a probability that two have the same birthday."  If there's only 
two, it's still 1/365.

So if you're just looking at one hash and saying "how many files will 
make this hash", there's no birthday paradox probability involved. If 
you look at a big pile of files, and you ask "how likely is it that two 
have the same hash", the birthday paradox comes into it.

But if you're talking 2^(-128) to start with, you can go an awful long 
time before you have to worry about it.

> Well, if people searched for decades without finding any collisions, 
> they must be reasonably rare then. (At least, for the kinds of messages 
> people tried hashing.) That suggests that at least the function doesn't 
> collide *massively* more often than it should...

Correct. It was best-of-breed for a long time, and then still used under 
warnings for a long time later.

> Ah yeah, sure, MD5 isn't cryptographically secure. I get that. I'm just 
> wondering how useful it is for detecting random alterations.

Nobody can give you a perfect assurance. I would guess, however, that 
you're much more likely to have the disk get scratched and unreadable as 
you pick it up out of the tray than to have an existing change cause a 
collision in the MD5 hash.

Hell, you're much more likely to get struck by lightning as you head 
home from work than have an accidental collision in an MD5 hash.

> The worrying thing being, how likely is it that such a thing might just 
> happen by accident? :-}

Very slim, or it would have happened much earlier.

-- 
   Darren New / San Diego, CA, USA (PST)
     Remember the good old days, when we
     used to complain about cryptography
     being export-restricted?

Post a reply to this message

Darren New wrote:

>> Well... the fact that collisions can be constructed prove that they 
>> exist, which might suggest the function is "less random" than it 
>> should be...
> 
> First, yes, of course they exists. As soon as you have meesages >128 
> bits, you by necessity have collisions. Second, the function isn't 
> supposed to be random, it's supposed to be non-invertible.

Indeed. But I'm using it for its randomness...

> Hell, you're much more likely to get struck by lightning as you head 
> home from work than have an accidental collision in an MD5 hash.

Depends where you live. Apparently in the USA the chance of being killed 
by lightning is only 1 in 700,000. That's actually quite a *high* 
probability. o_O

Apparently the changes of winning the National Lottery (absurdly 
improbable) is x * 10^(-8), for some "small" x. (I don't remember what 
it is.) 2^(-128) works out as x * 10^(-39) - the theoretical probability 
of winning the Lottery several times back to back. I guess even if we 
assume MD5 is moderately screwed, you'd still have to estimate the 
collision probability at 10^(-24) or something. That's still fairly 
improbable...

>> The worrying thing being, how likely is it that such a thing might 
>> just happen by accident? :-}
> 
> Very slim, or it would have happened much earlier.

Yeah, I'm fairly sure it's quite a low probability too. I'd just like to 
be able to put an objective figure to it. ;-)

Post a reply to this message

Orchid XP v7 wrote:
> Depends where you live. Apparently in the USA the chance of being killed 
> by lightning is only 1 in 700,000. That's actually quite a *high* 
> probability. o_O

Exactly. Far far larger than 2^-128.

> Apparently the changes of winning the National Lottery 

Funny enough, I saw where someone had looked up the death statistics, 
and figured out you had a 2000x better chance of being killed between 
the time you bought your lottery ticket and the time the big winner was 
announced than the chance of you actually being the big winner.

> Yeah, I'm fairly sure it's quite a low probability too. I'd just like to 
> be able to put an objective figure to it. ;-)

If you could give a reliable objective number, you'd know enough of how 
it works to calculate it without going thru the actual math.

-- 
   Darren New / San Diego, CA, USA (PST)
     Remember the good old days, when we
     used to complain about cryptography
     being export-restricted?

Post a reply to this message

Orchid XP v7 wrote:

> I'm mainly trying to implement it in Haskell for fun; it'll probably go 
> too slow to be useful. (But we'll see about that...)

Oh my *God*, I've just spent my entire evening trying to make this damn 
thing work! I was thwarted by the following:

- I mis-typed certain magic numbers, causing the output to be a few 
digits wrong. >_<

- I forget the final state-add step. I spent literally *ages* trying to 
figure out why all the output was correct up until the very last stage.

- The hash is little-endian. Damn thing! I actually had the right 
output, it just looked wrong because you have to turn it half-backwards 
according to the dumb RFC. *sigh*

So yays! My program now correctly hashes the 0-byte string to yield an 
MD5 hash of D41D8CD98F00B204E9800998ECF8427E.

Now all I need to do is implement the very fiddly bit-padding algorithm 
and I'm golden...

It's TF2 time!

Post a reply to this message

Orchid XP v7 <voi### [at] devnull> wrote:
> So yays! My program now correctly hashes the 0-byte string to yield an 
> MD5 hash of D41D8CD98F00B204E9800998ECF8427E.

  I could do that much faster than you. Probably in something like
10 seconds. ;)

-- 
                                                          - Warp

Post a reply to this message

Warp escribió:
> Orchid XP v7 <voi### [at] devnull> wrote:
>> So yays! My program now correctly hashes the 0-byte string to yield an 
>> MD5 hash of D41D8CD98F00B204E9800998ECF8427E.
> 
>   I could do that much faster than you. Probably in something like
> 10 seconds. ;)
> 

if (data.length == 0) {
	return "D41D8CD98F00B204E9800998ECF8427E";
} else {
	error("Not implemented yet");
}

Post a reply to this message

Nicolas Alvarez <nic### [at] gmailisthebestcom> wrote:
>         error("Not implemented yet");

  error("I'll implement this when I have the time.")

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
> Orchid XP v7 <voi### [at] devnull> wrote:
>> So yays! My program now correctly hashes the 0-byte string to yield an 
>> MD5 hash of D41D8CD98F00B204E9800998ECF8427E.
> 
>   I could do that much faster than you. Probably in something like
> 10 seconds. ;)

Well, I now have the full algorithm working. :-P

Or at least, it seems to work for messages shorter than 52 bytes anyway. 
It seems there's still a glitch in the padding algorithm that makes it 
go wrong for messages longer than 1 block...

I'm just amazed that I managed to implement an algorithm as complex and 
fiddly as MD5 in only 2 days. Heh.

Post a reply to this message

Orchid XP v7 <voi### [at] devnull> wrote:
> Well, I now have the full algorithm working. :-P

> Or at least, it seems to work for messages shorter than 52 bytes anyway. 

  Then it's not a full working algorithm, is it?-)

  Testing that the algorithm works for all possible inputs would be a rather
laborious job. Just testing that it can produce any MD5 value would be a
rather impossible job, taking into account how many there are.

  I wonder how they make sure that an implementation is correct...

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
> Orchid XP v7 <voi### [at] devnull> wrote:
>> Well, I now have the full algorithm working. :-P
> 
>> Or at least, it seems to work for messages shorter than 52 bytes anyway. 
> 
>   Then it's not a full working algorithm, is it?-)

Well, it's damn near. :-P

>   Testing that the algorithm works for all possible inputs would be a rather
> laborious job. Just testing that it can produce any MD5 value would be a
> rather impossible job, taking into account how many there are.
> 
>   I wonder how they make sure that an implementation is correct...

Test all code paths, I assume.

For example, I am pretty damn confident that the compression function in 
my implementation is correct. I've tested it with dozens of different 
input blocks, and it's always produced the right output. There's no 
particular reason why it shouldn't for other input blocks. It processes 
them all the same way...

Now, the padding algorithm, *that* changes for every message size. For 
some sizes it seems to work, but not for all of them. I need to test it 
with a large array of sizes to check it's working. (Or rather, to figure 
out why currently it isn't.)

Post a reply to this message

Warp wrote:
> Orchid XP v7 <voi### [at] devnull> wrote:
>> Well, I now have the full algorithm working. :-P
> 
>> Or at least, it seems to work for messages shorter than 52 bytes anyway. 
> 
>   Then it's not a full working algorithm, is it?-)

Ah-HAH! One more bug, annihilated. >:-)

In the midst of a complex padding algorithm, I forgot to add on the 
running count of the number of bytes processed. The "size" figure 
appended onto the end of the bitstream was always the size of the last 
block, not the whole message. (IOW, message size mod 512.) Oops!

The program now appears to give correct results for every case I've 
tried. (I.e., not very many. However, I threw a 2 MB file at it, and it 
gave me the right answer. This indicates that it's not *completely* 
broken...)

And yes, it's just a tad slower than C. ( = exaggeration.)

Post a reply to this message

Warp wrote:
>   I wonder how they make sure that an implementation is correct...

Generally, code coverage and intermediate results, along with a set of 
test vectors designed to cover all paths through and often showing the 
intermediate results.

It's somewhat easier when your specification is "here's the C code to do 
it" rather than an ambiguous description of what you're supposed to do. 
Especially since there isn't any "real world" right or wrong answer, 
other than "match what the C code outputs."

Plus, of course, it's designed to go wildly arwy with the slightest 
peturbation of the process, so even tiny bugs tend to produce completely 
different results. Which is its own debugging problem.

-- 
   Darren New / San Diego, CA, USA (PST)
     Remember the good old days, when we
     used to complain about cryptography
     being export-restricted?

Post a reply to this message

Darren New wrote:

> Plus, of course, it's designed to go wildly arwy with the slightest 
> peturbation of the process, so even tiny bugs tend to produce completely 
> different results. Which is its own debugging problem.

I got 2 bits wrong in one of the magic numbers. Totally messed up the 
output... until I found and fixed the bug.

Post a reply to this message

Invisible wrote:

> However, one might also conjecture that the probability of any two 
> arbitrary messages having the same [MD5] hash code would be 2^(-128).

Random fact:

2^(-128) ~= 2.93 * 10^(-39)

Winning the National Lottery (assuming you only bought 1 ticket) has a 
probability of roughly 7.15 * 10^(-8).

If my arithmetic is right, that means that winning the National Lottery 
jackpot 5 times back-to-back is still more than 637 times *more* likely 
than something with a probability of 2^(-128) happening.

Assuming the probability of a random file mutation leaving the MD5 hash 
unchanged really *is* 2^(-128), it's a pretty unlikely event. You should 
probably worry more about the building being burned to the ground...

Post a reply to this message

>> However, one might also conjecture that the probability of any two 
>> arbitrary messages having the same [MD5] hash code would be 2^(-128).
>
> Random fact:
>
> 2^(-128) ~= 2.93 * 10^(-39)
>
> Winning the National Lottery (assuming you only bought 1 ticket) has a 
> probability of roughly 7.15 * 10^(-8).
>
> If my arithmetic is right, that means that winning the National Lottery 
> jackpot 5 times back-to-back is still more than 637 times *more* likely 
> than something with a probability of 2^(-128) happening.
>
> Assuming the probability of a random file mutation leaving the MD5 hash 
> unchanged really *is* 2^(-128), it's a pretty unlikely event. You should 
> probably worry more about the building being burned to the ground...

If you are only worried about one file per week and you don't backup off 
site, then sure...

Post a reply to this message

scott wrote:
>>> However, one might also conjecture that the probability of any two 
>>> arbitrary messages having the same [MD5] hash code would be 2^(-128).
>>
>> Random fact:
>>
>> 2^(-128) ~= 2.93 * 10^(-39)
>>
>> Winning the National Lottery (assuming you only bought 1 ticket) has a 
>> probability of roughly 7.15 * 10^(-8).
>>
>> If my arithmetic is right, that means that winning the National 
>> Lottery jackpot 5 times back-to-back is still more than 637 times 
>> *more* likely than something with a probability of 2^(-128) happening.
>>
>> Assuming the probability of a random file mutation leaving the MD5 
>> hash unchanged really *is* 2^(-128), it's a pretty unlikely event. You 
>> should probably worry more about the building being burned to the 
>> ground...
> 
> If you are only worried about one file per week and you don't backup off 
> site, then sure...

1. We backup off-site, but - absurdly enough, when you think about it - 
we don't *archive* anything off-site. So when a project is finished, it 
gets put into a pair of CDs, deleted from the servers, and stored in our 
own building. So actually, our "current" projects are protected better 
than the finished ones... Hmm, actually, we should probably fix that! ._.

2. Let's look at the rules of probability:

Pr(A and B) = Pr(A) * Pr(A)
Pr(A or  B) = Pr(A) + Pr(B)

[Subject to various assumptions.] In particular, we have

   Pr(A and B) < Pr(A)
   Pr(A or  B) > Pr(A)

So ANDs decrease the probability, and ORs increase it. Thus, the 
probability of winning the Lottery today AND next week AND the week 
after AND... becomes quite small. However, the probability of file A 
being corrupt OR file B being corrupt OR... increases as we add more 
files. BUT NOT AS FAST!

If the probability of a single file being corrupted but not detected by 
MD5 is 2.93 * 10^(-39) then the probability of any single file out of 
1,000 files being so-corrupted is... 2.93 * 10^(-36). Which is still 
pretty tiny. (It's about 2x more likely than 5 wins on the Lottery - 
which is astronomically unlikely in the first place.)

With 1 million files per month, we get 2.96 * 10^(-33) as the 
probability of one of them getting corrupted but us not noticing. That's 
nearer to 4 consecutive Lottery wins... I don't think I'll worry too 
much. ;-)

Post a reply to this message

On 16 Nov 2007 17:08:14 -0500, Warp wrote:
> Nicolas Alvarez <nic### [at] gmailisthebestcom> wrote:
>>         error("Not implemented yet");
>
>   error("I'll implement this when I have the time.")

error("This feature is only available in the registered version.");

-- 
Joel Yliluoma - http://iki.fi/bisqwit/

Post a reply to this message

Joel Yliluoma wrote:

>>>         error("Not implemented yet");

>>   error("I'll implement this when I have the time.")

> error("This feature is only available in the registered version.");

Joel wins.

Post a reply to this message