![]() | |||||||||||||
Messages in this thread |
On Friday 16 January 2004 21:59, Timothy Miller wrote: > Valdis.Kletnieks@vt.edu wrote:> > On Fri, 16 Jan 2004 15:22:39 EST, Timothy Miller <miller@techsource.com> said: > >>Think about it! If we had a filesystem that actually DID this, and it > >>was in the Linux kernel, it would spread far and wide. It's bound to > >>happen that someone will identify a collision. We then report that to > >>the committee offering the reward and then donate it to OSDL to help > >>Linux development.> >> > Actually, it's *not* "bound to happen". Figure out the number of blocks > > you'd need to have even a 1% chance of a birthday collision in a 2**128 > > space.> >> > And you'd need that many disk blocks on *a single system*. > >> > Then figure out the chances of a collision on a small machine that only > > has 20 or 30 terabytes (yes, in this case terabytes is small).>> Certainly. No one machine is going to find it in a reasonable period. > OTOH, if a million machines were doing it, it increases the chances by > just that much. Let's take a look at the chances. 30 terabytes is, in a best-case scenario (with 512-byte blocks) about 6e10 blocks. That would be roughly 6e10*6e10*(2**(-128)), or about 1e-17. With a hundred million machines, the chances of a collision would be about 1e-9, disregarding the fact that all these machines have a large chance of containing similar blocks -- their data isn't truly random, so some blocks have a larger chance of occurring than others. The data sets on the machines are probably reasonably static, so if the collision isn't found *at once* the chances of it occurring later are much smaller. So, even under the most positive assumptions, with a hundred million machines with 30 terabytes of storage each, it's extremely probable that you won't find a collision. (A 96-bit hash could have been broken with this setup however. :) ) -- Bart - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/ | ||||||||||||
| Last update: 2005-03-22 13:00 [W:0.406 / U:0.300 seconds] ©2003-2008 Jasper Spaans | |||||||||||||