Date: Sun, 13 Sep 2015 15:34:09 +0300 From: Aleksey Cherepanov <lyosha@...nwall.com> To: john-dev@...ts.openwall.com Subject: experiment with functions to reject computed hashes I was curious if it is possible to make a function to reject computed hashes useless for us. Such function has to: - never reject hashes from given set, - reject as many as possible other hashes. I tried the following function: T1[(v >> a) & 0xF] ^ T2[(v >> b) & 0xF] == 0 where results means reject, v is some integer from hash, a and b are some shifts so that 4 bits do not overlap (maybe it is not really needed), T1 and T2 are tables with 16 values each (0 - 255). It is easy to implement this function with SSE using shuffle instruction. a and b should be either 0 and word_size_in_bits-4 to remove 2 ops, or they should be chosen to produce more same values for given hashes. I used hill climbing to find T1 and T2 for random sets. Actually there can be more tables. I attached my code, it has tunable count of tables. So far, the code can produce 2 tables for some sets of 2^5 hashes that reject half of values to be rejected and accept everything else. For that, I fill tables with random values 0-255 and then replace random elements in each table with 0 and 1 randomly, updating state when good replacement occurs. Usually initial state accepts all values. Mutations improve reject ratio. It sticks often but otherwise works quickly, so restarts are needed. So generated function can reject almost half of candidates using ~7 sse instructions (not counting load of tables but counting final &0x0..0ff), cracking 32 hashes. In john, it might be used in the end of crypt_all() to report that there are no possible passwords. But for such use, all computed candidates should fail the check. So it would be ~1/4 for MAX_KEYS_PER_CRYPT == 2. My algo does not scale at all. Naive hill climbing is a wrong approach because it needs high redundancy. And I am not sure that ^ is a good way to combine tables, especially 3+ tables. What do you think? Thanks! -- Regards, Aleksey Cherepanov View attachment "t.py" of type "text/x-python" (5419 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.