[<prev] [next>] [thread-next>] [day] [month] [year] [list]
Message-ID: <20150913123409.GA19486@openwall.com>
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.
