Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
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.