Openwall GNU/*/Linux - a small security-enhanced Linux distro for servers
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Sun, 20 Sep 2015 02:57:57 +0200
From: magnum <john.magnum@...hmail.com>
To: john-dev@...ts.openwall.com
Subject: Re: fast hash early exit vs. large hash list

On 2015-09-19 17:23, Aleksey Cherepanov wrote:

I appreciate you chiming in, just so we have that clear.

> On Sat, Sep 19, 2015 at 04:33:37PM +0300, Solar Designer wrote:
>> On Sat, Sep 19, 2015 at 12:17:13PM +0300, Aleksey Cherepanov wrote:
>>> Check against millions of hashes may just need 2 ints, not fully
>>> stored state.
>>
>> Yes, although in Fred's testcase 1.7+ million correct passwords (and
>> more than that with --fork and some duplication in post-rules
>> candidates) would proceed all the way to cmp_*() where we'd want to
>> check the full 128 bits.  Testing them with scalar code may consume a
>> second, which is like a few percent of the total running time, thus is
>> "significant". ;-)
>
> cmp_* might be vectorized too.

Maybe cmp_all() but hardly the other two. Right?

> So it might be affordable to consider index 9 as 0, that's max len =
> 31. But then, index 2 is used. It would be 0 if max len = 7. It would
> a constant if len = 8. A constant would ok too.

I had some vague idea that we could have eg. resume_md5(binary, length) 
and it could take such things in account. But then we'd also have to 
call a corresponding md5() function that would reverse to that very 
length. It just gets too complex for our shared stuff! Again, I'm all 
for doing hard-core reversing in formats that doesn't use the shared 
code, but I think we should KISS in simd-intrinsics.c. And I think 
that's what we do right now. Any improvements to THAT are definitely 
welcome, but they just can't be this complex.

> It is possible to assume word with index 2 as any and reverse with all
> variants producing 2^32 "correct" values for each hash. It is possible
> to do that "on demand": when password is set with new word, reverse
> all hashes with this word. But it does not seem right, because other
> projects reverse more rounds and does not seem to do it at such
> expenses. So it may be needed to investigate formulas further or to
> investigate some implementations with "deep" reverse (for instance,
> Open Source BarsWF that you mentioned).

I think in a nutshell we should read BarsWF (and other) code and 
contemplate a lot.

Thanks!
magnum

Powered by blists - more mailing lists

Your e-mail address:

Powered by Openwall GNU/*/Linux - Powered by OpenVZ