Date: Thu, 09 Sep 2021 17:08:50 +0300 From: Aleksey Cherepanov <aleksey.4erepanov@...il.com> To: john-dev <john-dev@...ts.openwall.com> Subject: Re: precomputed attacks for john: rainbow tables and other ways Aleksey Cherepanov <aleksey.4erepanov@...il.com> writes: > I just tried my previous idea about splitting wordlist into parts based > on prefix of hash. But I stored only indexes of candidates and > compressed everything. > > So to attack a hash, I would pick respective file and try candidates > from it only. Also I would know that other files would not help. So for > a particular hash I could say that the attack is exhausted reliably. > Unlike regular RT, one might attack all hashes with given prefix in > single run. > I like that I hashed everything only once. But compression takes a lot > of time. I am not sure if it scales this way, but I would define such > possible baseline (with and without compression): > - ~1024x speed-up, ~3x work to prepare, storing ~2 bytes per candidate, > - ~1024x speed-up, ~1x work to prepare, storing 4 bytes per candidate. > All with 100% success. > > I think speed-up is very flexible in such method, but for small > keyspaces compression would degrade. OTOH for larger keyspaces, 4 bytes > per candidate without compression is not possible. But I guess very fast > and very specific compression could be used. Yes, it is possible to pack everything well without many computations. It is possible to write most significant byte once for a subgroup getting 2.04 bytes per candidate index. Also it is possible to store increments between indexes of candidates and pack 2 of them into 3 bytes, getting 1.57 bytes per candidate. 98% of increments are below 4096. 86% are below 2048, so it is possible to pack it better messing with bits. But that's for 10-bit prefix / 1024 groups. Choosing bigger prefix would cause bigger gaps between candidates, so such dense packing would not be possible. I got some ideas about usability. Let's say we have 2^40 keyspace and use 4-byte prefix to split candidates into groups. So there are 2^32 groups, on average each group has 256 candidates. We would store 5 bytes per index of candidate and consume 5TB on hdd (plus several GBs onto index). Now let's say we get 100k hashes in a contest with all different prefixes (worst case). Without any computations, we know that (2^32 minus 100k) groups do not contain passwords for these hashes. We have approximately 100k * 256 candidates to try. That's a few seconds with single thread on cpu, assuming we have fast hdd and fast function to get candidate from index. That's cool but let's calculate hashing speeds: let's choose descrypt as relatively slow format, I have 3.5M c/s in john on cpu with single thread. So 100k hashes (with same salt) would take 8 seconds to be checked against the precomputed attack (assuming fast hdd). 2^40 would take 87 hours to be prepared with one thread (maybe plus some additional time to repack everything because 2^32 files seem a bad idea). The speed-up seems great. But there are GPUs. Some GPUs give 1.4G c/s for descrypt. That's 785 seconds or 13 minutes to perform just full attack live. So with same speed, bigger keyspace and 100% success rate, a precomputed attack might be competitive to single gpu. But this approach is limited by space consumption. I am curious if there are other approaches. For the contests, it looks like small keyspaces are useful only early, then it is better to run attacks specific to the contest. Early use of prepared attack means that its approach should have great cracking speed. Other use in contests might be pattern discovery to help regular cracking. It may tolerate low speed of cracking to try bigger keyspace. Also it may tolerate low success rates, because we would try a small subset of hashes anyway. For pattern discovery, regular rainbow tables seem a good fit. Interesting, LHT is mentioned. LHT stands for "Lossy Hash Table". Also there is a link to Matt's "Probabilistic Password Cracker". :-) https://www.tobtu.com/cracker.php Thanks! -- Regards, Aleksey Cherepanov
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.