On Mon, Mar 31, 2003 at 07:28:57PM +0100, Matthew Wilcox wrote: > Let's try using some numbers. An md5sum is 16 bytes -- 128 bits. > On average, you need 2^64 samples to find a collision. So you need around > 600 million samples per second to find one collision in a year (assuming > you're going for a brute-force attack and you're not exploiting some > of the weaknesses of md5). Let's assume your 3GHz processor takes 1000 > cycles to calculate an md5sum (I don't know what it really is.. a real > number wouldn't hurt at this point..), so it can do 3 million samples/s. > 200 of them will do it. > > It's an accomplishment, but it's affordable. Voters supplying a salt > makes it non-doable. Excuse me, maybe I am missing something, but as far as I understand it, it's not sufficient to just find *any* collision; rather, you have to find a collision that actually makes sense (that is, starts with a valid debian login id). There are 2^128 possible 128-bit md5 hashes and, given 1000 eligible voters and 16-digit hexadecimal tokens, 1000*16^16 possible strings. According to bc(1), that gives a probability of .00000000000000005421 that a valid collision exists for any given secret. By adding some random noise in the form of a salt, you are increasing the feasibility of actually doing this. I have no clue whatsoever about this, really, so just ignore me if I'm wrong. - Michael -- Sometimes I worry about being a success in a mediocre world. -- Lily Tomlin
Attachment:
pgp6m3Y1j8ZfT.pgp
Description: PGP signature