[Date Prev][Date Next] [Thread Prev][Thread Next] [Date Index] [Thread Index]

Re: Debian Project Leader Election 2003 Results

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

- Michael

Sometimes I worry about being a success in a mediocre world.
		-- Lily Tomlin

Attachment: pgp6m3Y1j8ZfT.pgp
Description: PGP signature

Reply to: