Re: FreeSec crypt()

[Solar Designer <solar@openwall.com>]

On Tue, Jun 12, 2012 at 09:18:42PM -0400, Rich Felker wrote:
> Thanks. Here's a _really_ quick draft, untested, of the direction I
> wanted to take it with making the tables static-initialized. Note that
> doing so allowed removing all of the table-creation code and most of
> the existing tables. For me, it's weighing in at ~12k.

This sounds good, yet it's an increase from ~5k for the version I posted
(~6k with tests).  I understand that you're avoiding having memory pages
that would be written to by each DES-crypt-using process and thus not
shared - but that would only happen when this code is actually used,
which I think it usually won't be (this is backwards compatibility
stuff; we need to introduce modern crypt() flavors for actual use).

That said, the decision is yours to make, and you appear to have made it.

> I also removed
> some unused code for things like keeping salt/keys between multiple
> runs since the data is not preserved across multiple runs anyway,

It can be preserved if you make the (tiny) struct _crypt_extended_local
static.

> and the lookup tables for bitshifts.

As discussed on IRC, I had tried that, but reverted my changes because
they resulted in code size increase (greater than the savings from not
having those tables).  Apparently, the table lookups helped avoid mov's
(on 2-operand archs like x86) and add/sub (becomes part of effective
address calculation).  Did you check how this affected total size in
your case?  Or do you prefer cleaner source code anyway (makes sense)?

> > Also, we could want to add a runtime self-test, which would detect
> > possible miscompiles.
> 
> I understand your motivation for doing this with security-critical
> things, but really most/all of libc is security-critical, and we can't
> have runtime miscompilation tests all over the place. Moreover, the
> vast majority of cases of GCC "miscompiling" something turn out to be
> code that's invoking undefined behavior; the only non-UB example I've
> encountered while working on musl is gcc 4.7's bad breakage, which is
> so bad you can't even get programs to start...

I agree that the vast majority of cases may involve UB, but so what - we
can't be 100% certain we don't have any cases of UB in our source code
even if we review it very carefully.  We might miss things, and besides
source code changes over time may introduce UB (e.g., changes in
variable declarations may result in code that continues to work
correctly, but actually depends on undefined behavior).

We have a fairly large chunk of code here (a few KB), which we can have
self-tested by a few hundred bytes of code more.  I think this is worth
it.  Besides, the self-test may serve to zeroize sensitive data - and in
a more reliable way than a memset() would (which may be optimized out,
and it would not necessarily zeroize stack and registers).  In fact, I
am using this approach to zeroization in crypt_blowfish.  Yes, the
self-test needs to run _after_ hashing the real password, and then
depending on self-test result you either return the originally computed
value or you return an error indication (what to return from crypt() on
error is a separate non-trivial topic).

>  * This version is derived from the original implementation of FreeSec
...

Can you please add a comment documenting your changes, too?

I notice that you fully dropped the tests - are you going to have
compile-time tests elsewhere?

Thanks,

Alexander