[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20130717164726.GA21323@openwall.com>
Date: Wed, 17 Jul 2013 20:47:26 +0400
From: Solar Designer <solar@...nwall.com>
To: john-dev@...ts.openwall.com
Subject: Re: md5 hash comparisons
Hi Sayantan,
On Wed, Jul 17, 2013 at 10:02:37PM +0530, Sayantan Datta wrote:
> How many bits or bytes are necessary to uniquely identify md5 hash ? I know
> 4 bytes aren't enough and causes many false positives to pass
> through. Although 8 bytes seems to be enough but I'm not sure.
8 bytes will almost always be enough, but there's no reason not to check
the full hash in cmp_exact() on host.
Your only question should be: what is the optimal partial hash size for
the initial on-GPU comparison? You tune this one solely for maximum
performance of the whole thing. With smaller partial hashes used in the
initial comparison, you may make that comparison faster, but your code
(maybe on host) will need to deal with the false positives more often.
It is realistic that 4 bytes or so may be optimal. But like I said your
code does need to deal with the occasional false positives (not report
them as correct guesses).
> Also how
> many hashes are loaded simultaneously for cracking ? I expect 1000 - 2000 ,
> is that assumption enough ?
No! It will vary from 1 hash to hundreds of million hashes (people
already ran John on ~150M hashes at once), and I would not be surprised
if someone tries 1 billion soon. Indeed, you can't easily support
on-GPU comparison when the combined size of partial hashes exceeds the
GPU card's global memory - so that's a reasonable limit.
> Depending upon the the number of bytes required
> for comparisons I might be able to increase the loaded hash count.
Right.
> Will it produce any false positives if I chose 0, 4, 8, 12 th bytes only
> for hash comparisons.
0 bytes?! Yes, it will. ;-) Also for 4 bytes, very often. For 8
bytes, occasionally. Like I said, your code needs to deal with this.
Please take a look at myrice's PG-test branch and his use of bitmaps.
Thanks,
Alexander
Powered by blists - more mailing lists
Confused about mailing lists and their use?
Read about mailing lists on Wikipedia
and check out these
guidelines on proper formatting of your messages.
