Re: FreeSec DES-based crypt(3)

[Solar Designer <solar@openwall.com>]

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