Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Sun, 24 Jun 2012 11:21:12 +0400
From: Solar Designer <>
Subject: Re: FreeSec crypt()

On Wed, Jun 13, 2012 at 10:53:18AM -0400, Rich Felker wrote:
> On Wed, Jun 13, 2012 at 04:07:54PM +0400, Solar Designer wrote:
> > > 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.
> I suppose this is worth considering. I was assuming it would be
> difficult to preserve (require otherwise-unneeded locking), but for
> crypt_r each caller could be responsible for its own copy.
> However, on the other hand I'm not sure I see the benefit. Why would
> you call crypt or crypt_r multiple times with the same key/salt except
> possibly for password cracking (in which case you'll want a highly
> optimized-for-speed implementation)?

You're right.  Additionally, preserving this requires that we keep
sensitive data around (from the previous password hashed).  I've dropped
this stuff now.

> > > 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)?
> I didn't compare, but yes I do prefer cleaner source. I'm a bit
> surprised that you found the difference in code size to be >136 bytes
> though. Are you sure the code size changed by that much?

Yes, and I was surprised too.  However, I've re-introduced those changes
now, and along with other changes I made there appears to be almost no
size increase from them.

> > > > 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.
> For purely computational code that doesn't recurse or loop arbitrarily
> long based on the input or read and write all over memory, static
> analysis can determine the absence of UB.

Are you performing such static analysis on musl?

> > 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.
> I'm open to seeing them if they're really that small and non-invasive.

I've added a runtime self-test now.  The cost appears to be 200 to 300
bytes of code and read-only data.

Another reason to have this for crypt() when we don't have it for many
other functions is that it is more difficult to recover from improperly
hashed passwords (than from some other bug in another libc interface).
Rather than just fix the bug, we might have to add backwards
compatibility code.  Even worse, those improperly computed hashes may be
a security risk that is not necessarily avoided by simply installing
fixed software.

> > value or you return an error indication (what to return from crypt() on
> > error is a separate non-trivial topic).
> I saw the notes on this. What real-world code breaks from the
> conformant behavior?

I think the majority of daemons, etc. that do authentication with
crypt() don't handle possible NULL returns.  This is just starting to
change now.  They don't really break under normal conditions because
normally crypt() returns the hashed password and not NULL; but if it
does somehow return NULL (e.g., because the salt read from the shadow
file is invalid), then I'd expect most users of crypt() to crash.

...Attached is my latest revision of crypt_freesec.  I've reduced the
table sizes even further (7 KB, may be precomputed) and I made certain
other changes as discussed.  I'd appreciate another review, and some
fuzzing against another implementation wouldn't hurt.


View attachment "crypt_freesec.h" of type "text/plain" (2493 bytes)

View attachment "crypt_freesec.c" of type "text/plain" (22333 bytes)

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.