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.