Date: Mon, 06 Sep 2021 23:49:16 +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 Royce Williams <royce@...hsolvency.com> writes: > A while back, I did some crude caching of all descrypt salts for targeted > terms here: > > https://github.com/roycewilliams/kens-salty-rainbow > > And yes, I'm deliberately making ironic use of the word "rainbow" here. :D Heh, that's an interesting position on TMTO spectrum. 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. In my test, keyspace is 16M (256 * 256 * 256). I split it into 1024 files based on 10 bits from hash. Each file contains binary array of 4-byte integers for indexes of candidates (not plaintexts). Each file is ~64kb, sizes vary slightly. Then I compressed all files together as `tar c out | time xz -0 > out.tar.xz`. Resulting size is 34176740 bytes, that's 2.04 bytes per candidate. I iterated indexes of candidates sequentially in one thread, so output files are sorted by construction. I tried to store 3 bytes instead of 4, but it gave 45020660 bytes of output from xz (I guess xz has heuristics to find binary tables of numbers). Times: - 7.3s to hash every candidate and write index to appropriate file, - 13.1s to compress the files. 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. Thanks! -- Regards, Aleksey Cherepanov View attachment "ossl7.c" of type "text/x-csrc" (1493 bytes)
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.