Re: [Caml-list] Computing with big numbers?
That depends on the threat model. If the question is, presuming no active attack, how likely is it to break?, then the cryptanalytic results against the hash are irrelevant. If the question is how secure is it if someone is maliciously manipulating files, then they are certainly relevant. If you're operating between reasonably secure machines, where an attacker having write access is already more catastrophic than a failure of Unison, then the first is what matters. If someone else has control over some of the files, then you've gotta watch the second. --- On Thu, 12/4/08, Florian Hars [EMAIL PROTECTED] wrote: From: Florian Hars [EMAIL PROTECTED] Subject: Re: [Caml-list] Computing with big numbers? To: Alan Schmitt [EMAIL PROTECTED] Cc: [EMAIL PROTECTED] Date: Thursday, December 4, 2008, 8:06 AM Alan Schmitt schrieb: But I don't think this applies here, as the hashes I'm looking at are the one used by Unison to identify file contents. Then it is *especially* relevant, as it is quite trivial to generate several files with different content and the same MD5 hash, all you need is a Playstation 3: http://www.win.tue.nl/hashclash/Nostradamus/ - Florian -- But our moral language is fragmented; our contemporaries reject the Kantian hunch that choosing those things most admirable and plausible as ends in themselves is the best practice; autonomous sources of the good are everywhere brown and broken. Thus we have PHP. http://lambda-the-ultimate.org/node/1463 ___ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs ___ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
Re: [Caml-list] Computing with big numbers?
On 4 déc. 08, at 17:06, Florian Hars wrote: Alan Schmitt schrieb: But I don't think this applies here, as the hashes I'm looking at are the one used by Unison to identify file contents. Then it is *especially* relevant, as it is quite trivial to generate several files with different content and the same MD5 hash, all you need is a Playstation 3: http://www.win.tue.nl/hashclash/Nostradamus/ Thanks for the link, but I wasn't considering a malicious attack: if someone were able to modify my files, I would not worry about Unison not detecting (thus not propagating) a malicious change. Alan PGP.sig Description: This is a digitally signed message part ___ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
Re: [Caml-list] Computing with big numbers?
Alan Schmitt wrote: Hello, In preparation for a talk I'm going to give, I wanted to estimate how good 128 bits MD5 hashes were: how many hashes must be taken before the probability for a collision become non negligible? (I'm assuming equi-probability of every hash.) The brute force approach is simply to enumerate the non-collision probability for k different hashes, and compute until it becomes lower than 1. This probability is (writing N for 2 ^ 128): N * (N-1) * (N - 2) * ... * (N - k) --- N^k I tried computing this using the bignum library that comes with OCaml, and it slows down to a crawl very fast (for k ~ 1000). So I tried to be more subtle and approximate the result (using Stirling's approximation of factorials), but OCaml's floats are not precise enough to yield anything significant. (I'm trying to compute the log of the approximation of N! / (N^k * (N-k)!), which is N (ln N) - N - (k (ln N) + (N - k)(ln (N - k)) - (N - k)).) Is there a library with better floating point precision than the OCaml one? If I understand your problem correctly, this is the so-called birthday problem with 2^128 days in a year. The Wikipedia article gives useful approximations: http://en.wikipedia.org/wiki/Birthday_problem Martin -- http://mjambon.com/ ___ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
Re: [Caml-list] Computing with big numbers?
Hi, In preparation for a talk I'm going to give, I wanted to estimate how good 128 bits MD5 hashes were: how many hashes must be taken before the probability for a collision become non negligible? (I'm assuming equi-probability of every hash.) I reckon that by saying how good 128 bits MD5 hashes were you are aware of the recent attacks that make MD5's effective security less than 128-bit. The Wikipedia has a good summary: http://en.wikipedia.org/wiki/MD5 Cheers, Dario Teixeira ___ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
