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
pgpYAHi6pouRx.pgp
Description: PGP signature
