FreeSec DES-based crypt(3)

FreeSec DES-based crypt(3)

[Solar Designer]

Rich, all -

musl uses a DES-based crypt(3) implementation called FreeSec - the same
one that *BSD's use.  Unfortunately, its handling of invalid salt
strings (with characters other than from the defined base-64 alphabet)
differs from UFC-crypt's (which is standard in glibc) to an extent far
greater than desired (yes, some deviations from UFC-crypt are in fact
desired, in my opinion).  Also, this may have security implications
(yes, *BSD's are sort of affected) where lots of different invalid salts
are treated as just one.  This may affect e.g. some web apps that use
PHP's crypt() improperly (their fault, but still).

Thus, I propose that you replace the code in musl with my revision of
it, which has the above issues corrected:

http://cvsweb.openwall.com/cgi/cvsweb.cgi/Owl/packages/glibc/

The files are crypt_freesec.c and crypt_freesec.h.  These are also used
in PHP 5.3.x, so they receive a lot of testing.

Another issue is that somehow the speed of your FreeSec code in musl is
extremely poor - it runs about 50 times slower than expected (e.g., than
it does in glibc on Owl).  This is as tested with "john --test
--format=crypt" with JtR 1.7.7 on x86_64.  I suggest that you run this
test too, both before and after you replace the FreeSec code.

Alexander

Re: FreeSec DES-based crypt(3)

[Rich Felker]

On Mon, May 02, 2011 at 05:43:33PM +0400, Solar Designer wrote:
> Another issue is that somehow the speed of your FreeSec code in musl is
> extremely poor - it runs about 50 times slower than expected (e.g., than
> it does in glibc on Owl).  This is as tested with "john --test
> --format=crypt" with JtR 1.7.7 on x86_64.  I suggest that you run this
> test too, both before and after you replace the FreeSec code.

You are right, and the reason, as suspected, is that the state is
reinitialized on each call to crypt (crypt is just a wrapper for
crypt_r with state on the stack). I tried eliminating the des_init
function and instead just using memcpy from a static const
initial_state object, but as this structure is very large, it
increased the object size by ~35k. Using a non-const static object
would be even worse, as it would increase the non-sharable data size
of any process by this amount. I could consider using malloc to obtain
a permanent des state, allocated and initialized on first use, with
fallback to the stack if malloc fails. But I'm wondering if it's
really desirable for crypt to be fast anyway. Surely JtR wants a fast
crypt, but my impression was always that slow crypt was a cheap way to
get some added defense against brute force login attempts and such...

Thoughts?

Rich

P.S. crypt is in no way integrated with other parts of libc, so
linking with -lfastcrypt (separate library) is a potentially viable
option for situations where you want a fast one.

Re: FreeSec DES-based crypt(3)

[Solar Designer]

On Mon, May 02, 2011 at 09:49:52AM -0400, Rich Felker wrote:
> I could consider using malloc to obtain
> a permanent des state, allocated and initialized on first use, with
> fallback to the stack if malloc fails.

This makes sense.

You might be over-estimating the cost of non-const static storage,
though.  It will only consume address space, not actual memory, until a
process actually invokes crypt(3) for a DES-based hash, in which case
the cost will be the same as above.

> But I'm wondering if it's
> really desirable for crypt to be fast anyway. Surely JtR wants a fast
> crypt, but my impression was always that slow crypt was a cheap way to
> get some added defense against brute force login attempts and such...

There's a difference between inherently slow crypt and merely a slow
implementation, and remote attacks are better dealt with in a different
way, in my opinion.  I don't want to discuss another bikeshed, so I'd
rather not go into detail.

JtR doesn't actually care much - it has its own optimized DES code (it'd
care about SHA-crypt's speed, because it doesn't support that natively
yet), but I just thought that you'd want musl not to be 50x slower than
glibc at this.

> P.S. crypt is in no way integrated with other parts of libc, so
> linking with -lfastcrypt (separate library) is a potentially viable
> option for situations where you want a fast one.

I think you'd want the default to be fast.  The approach with malloc
sounds fine to me - that way, you initially preserve the address space
as well.

Thanks,

Alexander

Re: FreeSec DES-based crypt(3)

[Rich Felker]

On Mon, May 02, 2011 at 10:03:36PM +0400, Solar Designer wrote:
> On Mon, May 02, 2011 at 09:49:52AM -0400, Rich Felker wrote:
> > I could consider using malloc to obtain
> > a permanent des state, allocated and initialized on first use, with
> > fallback to the stack if malloc fails.
> 
> This makes sense.
> 
> You might be over-estimating the cost of non-const static storage,
> though.  It will only consume address space, not actual memory, until a
> process actually invokes crypt(3) for a DES-based hash, in which case
> the cost will be the same as above.

Well actually it's a little bit more complicated than that. What
happens is that it can fragment the .data segment. For instance if all
the .data being written to in most programs was previously in a single
page, but the 35k des state got assigned an address between .data
symbols which are commonly used, then with the des state, a minimal
program would now take an extra dirty page. In the long term, I plan
to isolate the modules which have significant amounts of
unlikely-to-be-used static state together in the linking order to
avoid this type of problem.

There still are a couple issues with the malloc approach. One is that
it does use additional memory. Using the stack, the memory is already
reserved as commit charge (Linux reserves at least 128k commit charge
for stack to each process, in my experience) and will be reused by
other function calls immediately. Using malloc, the 35k is permanently
reserved for DES use only. The other issue, which I don't care about
but some people may, is that valgrind will show this as a memory leak.

> way, in my opinion.  I don't want to discuss another bikeshed, so I'd
> rather not go into detail.

Don't worry, I don't consider this a bikeshed. You're an expert on
crypto and anti-bloat is my specialty and a major defining aspect of
musl, so in a way these topics are closer to the nuclear reactor than
the bikeshed.

> yet), but I just thought that you'd want musl not to be 50x slower than
> glibc at this.

I would, but I want to balance it with other considerations and
achieve all goals at the same time. :)

I wonder... is there any way to cut down on the size of this data
without affecting (or perhaps even improving) the performance of the
code? Then making the data static const would be reasonable. In my
experience giant tables suggest 1980s/early-90s style optimization
that's often counterproductive today...

Rich

Re: FreeSec DES-based crypt(3)

[Solar Designer]

Rich,

I am sorry for not continuing this discussion for so long.

On Mon, May 02, 2011 at 03:01:35PM -0400, Rich Felker wrote:
> I wonder... is there any way to cut down on the size of this data
> without affecting (or perhaps even improving) the performance of the
> code?

Yes, Eric Young's fcrypt() in OpenSSL uses 2 KB tables.  However, it
does not readily implement the extended BSDI-style hashes, and you would
not be able to add them easily (they use 24-bit salts, whereas fcrypt's
2 KB is possible due to some clever bit rotates to apply the usual
12-bit salts only).  Also, there may be licensing issues.

The next step is 4 KB, and it lets you do 24-bit salts.  This is what
JtR uses when it somehow does not use a bitslice implementation (which
it normally does) and when 128 KB tables turn out to be slower.  I don't
mind licensing this code under LGPL or whatever for use in musl.
However, there's no crypt(3) interface, and some parts needed for it are
not implemented (e.g., instead of doing DES final permutation on
computed hashes, JtR's loader undoes it on hashes that it loads for
cracking).

Overall, you'd spend/waste lots of time on this until you get clean,
portable, and reliable code with functionality that is the same as what
the FreeSec code currently has.  I briefly thought of this before I
integrated FreeSec into the glibc package on Owl, but decided that I had
better uses for my time.  Of course, 35 KB is more of an issue for musl
than it is for glibc...  I vaguely recall that it was 20 KB, though
(16 KB plus 4 KB).

Oh, the 2 KB and 4 KB figures above include only the main tables (S-P or
S-P-E).  There are some additional ones for key setup.  I think that in
fcrypt() those are tiny, but in JtR they're large (optimized for speed
only, not size).  So you'd need to implement smaller key setup as well
(or take it from elsewhere).  It's not hard to do, but it's extra work.

Maybe it'd be simpler to re-work FreeSec to make it use smaller tables.

I hope this helps.

Alexander