Re: crypt* files in crypt directory

[Solar Designer <solar@openwall.com>]

On Tue, Aug 07, 2012 at 10:24:21PM -0400, Rich Felker wrote:
> First, the compatibility code for the sign extension bug. How
> important is it to keep this?

Not very important, but nice to keep musl's code revision closer to
upstream.

> Part of my question is that I'm having a
> hard time understanding how it's useful. For passwords that were
> subject to collisions due to this bug, it seems like there's nothing
> that can be done except discarding the old hashes, since they're
> vulnerable.

Not everyone cares about the security risk this much.  Some sysadmins
may prefer not to inconvenience their users.  They would change all
existing hashes to use the $2x$ prefix when they deploy a fixed version
of the code on a system that was known to have the bug before that
point.  That way, all users can continue to log in normally, but newly
changed passwords would be free from the bug.

> So my understanding is that the bug-compatibility code
> just serves to keep the subset of old hashes of 8-bit passwords that
> were _not_ subject to collisions from becoming unusable. I.e. the
> bug-compat code only benefits users who:
> 
> 1. Used passwords containing 8-bit characters
> 2. Happened to be using a password that was not subject to the
> collision bug, and
> 3. Did not regenerate hashes after the bug was fixed.

This could be true, but the sysadmin does not know which hashes were
subject to the collision impact of the bug and which were not (short of
trying to crack the passwords or adding code to analyze them upon login
and substitute different hash prefixes).

So a possible decision to use $2x$ for older hashes may be made based on
other criteria only (security risk vs. user annoyance).

I think very few systems actually made use of the $2x$ prefix.  Maybe
some websites did.

> I'm uncertain whether there's any portion of musl's user base that
> this would be useful to.

Maybe not.

> Second, what can be done to reduce size?

I felt the size was acceptable already.  However, if you must, the
instances of BF_ENCRYPT that are outside of BF_body may be made slower
with little impact on overall speed.  For example, they may be made a
function rather than a macro, and the function would only be inlined in
builds optimized for speed rather than size.

> I think the first step is
> replacing the giant macros (BF_ROUND, BF_ENCRYPT, etc.) with
> functions so that the code doesn't get generated in duplicate unless
> aggressive inlining is enabled by CFLAGS.

I see that you did this - and I think you took it too far.  The code
became twice slower on Pentium 3 when compiling with gcc 3.4.5 (approx.
140 c/s down to 77 c/s).  Adding -finline-functions
-fold-unroll-all-loops regains only a fraction of the speed (112 c/s);
less aggressive loop unrolling results in lower speeds.

The impact on x86-64 is less.  With Ubuntu 12.04's gcc 4.6.3 on FX-8120
I get 490 c/s for the original code, 450 c/s for your code without
inlining/unrolling, and somehow only 430 c/s with -finline-functions
-funroll-loops.

I think you should revert the changes for the instance of BF_ENCRYPT
that is inside of BF_body.

I also think that this code should be optimized for speed even when the
rest of musl is optimized for size.  In this case, better speed may mean
better security, because it lets the sysadmin configure a higher
iteration count for new passwords.

> But are there other things
> that would help? With the data tables being 4k in size, I'm thinking
> a reasonable target size for the whole file might be 7k.
> 
> Actually while writing this, I made some quick changes and seem to
> have already achieved that goal. See the attached file. It's untested,
> so I might have broken something in the process. I'm not sure I'll
> have time to test it well right away, so I'd appreciate comments on
> whether it works as well as any other possible improvements... :-)

It passes wrapper.c's tests once I re-added _crypt_gensalt_blowfish_rn()
to make these files compile together again.

Alexander