[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <2e8f5f9559d37db93dc15d431b5956aa@smtp.hushmail.com>
Date: Wed, 16 Sep 2015 21:26:24 +0200
From: magnum <john.magnum@...hmail.com>
To: john-dev@...ts.openwall.com
Subject: Re: larger bitmaps and hash tables
On 2015-09-16 19:42, Solar Designer wrote:
> On Wed, Sep 16, 2015 at 07:02:37PM +0200, magnum wrote:
>> I have committed a patch where params.h defines PH_MASK_6 as
>> (PASSWORD_HASH_SIZE_6 - 1), and changed ALL formats to use PH_MASK_6. So
>> we could commit this, or something similar if/when desired.
>
> I think we'll be changing all hash table sizes at once, not just the
> 6th. So maybe you can prepare us for that?
Done in 36393e763. I did not actually change any size yet. This was
significantly harder to do with pure one-liner-fu. It may have missed
something or included some spurious 0xff that was NOT a hash mask. I did
review all of it twice and did some machine checks as well so I'm pretty
sure it's OK.
However:
* Trip format was not touched. I'm not sure what to do with it.
* ntlmv1_mschapv2_fmt_plug.c and some other formats didn't have bits
enough even for our old sizes. A problem is once we change params.h
sizes, we can't immediately see which formats need tweaking (for
example, ntlmv1 and mschapv2 would probably need one or two more
functions NULL'ed). I'm not sure what happens if we use a size of 20
bits and the function actually only delivers 16... but I guess there
won't be any problem except some excess memory use?
> I think we'll obsolete the smallest two sizes, shifting everything else
> by two sizes. The new smallest size will be a 4096-bit entry bitmap and
> a 1024-entry hash table (with the current SHR=2), which is 8.5 KB total
> on a 64-bit system (so is still in L1 cache).
>
> This frees up the highest two sizes for reuse, and I think we may make
> them 30 and 32 bits. The latter would exist only in 64-bit builds
> unless we increase SHR (maybe we should introduce "magic SHR" on 32-bit,
> where an extra 2 or 3 bits would be skipped for the largest sizes).
>
> So we'll have: 12, 16, 20, 24, 27, 30, 32.
How are we going to define the actual PASSWORD_HASH_SIZE_6? Isn't it
still an int? Can we just define it as ULL with no problems?
> The binary_hash_*() functions will need to be merged into one, accepting
> the size in bits (or mask?) The get_hash_*() functions will stay (but
> be revised to support these larger sizes).
Isn't it faster/simpler to just have it always deliver 32 bits and then
mask them off at the caller? Maybe a few formats would suffer? Not many
I'm sure.
> Also, that patch was only good up to 31-bit since it kept
> password_hash_sizes[] at "unsigned int". Would need to use a 64-bit
> type right there to include a 32-bit maximum size, or alternatively
> would need to specify masks rather than sizes. (BTW, size_t wouldn't
> hold a value of exactly 2^32 on 32-bit.)
Yes, and that answers my question about SIZE_6. Anyway, we're a good bit
ahead now, with all formats prepared.
magnum
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.
