Re: Help-wanted tasks for musl

Re: Help-wanted tasks for musl

[idunham]

>> Analysis of Gregor's pkgsrc failure results
>> Gregor Richards has run the whole NetBSD pkgsrc build (over 10k
packages) against musl and posted reports to the mailing list and wiki.
Some analysis on the most frequent causes of failure could be extremely
helpful to improving compatibility. It would also be nice to identify
major dependency failures that can be fixed (either in the upstream
package if it's buggy, or in musl if it's due to missing features) so
that the packages which depend on them can be tested too. I'm looking
to get results in the form of "we should fix X and Y and Z and then
lots more packages will work".
> ISTR that Gregor has something that gives him scores for how important
different packages are.

This is mvd.txt in the results tarball. (see musl.codu.org)
Higher scores (at the top) mean more valuable/more packages stopped here.
And looking at what it says, I see these scores:
Ruby193-base: 904
pari: 674
qt3-libs: 394
qt4-libs: 358
....
libf2c: 282
....
g95: 152
....
SDL: 135

> I look at this once in a while already, but now that I've done a little
repartitioning, should be able to do a little more...
> Just for a brief overview of a few things:
> -SDL: patches haven't been merged
> -There are at least a dozen packages that should be building, per my own
tests without pkgsrc, but aren't.
> -e2fsprogs provides libcomerr, so I suspect blocks zephyr, which blocks
libpurple/pidgin/...
> -avahi is semi-important
> -ruby has been one of the higher-priority ones to fix
> -R needs g77 or gfortran a/k/a g95 (I have g77, but that's not in
pkgsrc...).
> Also needs lapack & blas which need the same.
> Octave needs all of the above, plus more...
> I suspect that applying musl patches to gcc-core, and untarring gfortran
on that, would be adequate-that's what I did for g77.
> -qt3 & qt4 libs won't build OOB.

Re: Help-wanted tasks for musl

[Gregor Richards]

Ruby and pari fail for uninteresting reasons I haven't diagnosed yet. 
i.e., it's something about the whole stack, not musl in particular. SDL 
works now, and should be reported as such when the new pkgsrc results 
come out. The Fortran stuff is just because pkgsrc doesn't know how to 
build GCC for musl; I just added the ability for Snowflake to build 
gfortran, so in the future that might work, but it's not ready in the 
current pkgsrc run.

With valediction,
  - Gregor Richards

On 08/19/2012 05:46 PM, idunham@lavabit.com wrote:
>>> Analysis of Gregor's pkgsrc failure results
>>> Gregor Richards has run the whole NetBSD pkgsrc build (over 10k
> packages) against musl and posted reports to the mailing list and wiki.
> Some analysis on the most frequent causes of failure could be extremely
> helpful to improving compatibility. It would also be nice to identify
> major dependency failures that can be fixed (either in the upstream
> package if it's buggy, or in musl if it's due to missing features) so
> that the packages which depend on them can be tested too. I'm looking
> to get results in the form of "we should fix X and Y and Z and then
> lots more packages will work".
>> ISTR that Gregor has something that gives him scores for how important
> different packages are.
>
> This is mvd.txt in the results tarball. (see musl.codu.org)
> Higher scores (at the top) mean more valuable/more packages stopped here.
> And looking at what it says, I see these scores:
> Ruby193-base: 904
> pari: 674
> qt3-libs: 394
> qt4-libs: 358
> ....
> libf2c: 282
> ....
> g95: 152
> ....
> SDL: 135
>
>> I look at this once in a while already, but now that I've done a little
> repartitioning, should be able to do a little more...
>> Just for a brief overview of a few things:
>> -SDL: patches haven't been merged
>> -There are at least a dozen packages that should be building, per my own
> tests without pkgsrc, but aren't.
>> -e2fsprogs provides libcomerr, so I suspect blocks zephyr, which blocks
> libpurple/pidgin/...
>> -avahi is semi-important
>> -ruby has been one of the higher-priority ones to fix
>> -R needs g77 or gfortran a/k/a g95 (I have g77, but that's not in
> pkgsrc...).
>> Also needs lapack & blas which need the same.
>> Octave needs all of the above, plus more...
>> I suspect that applying musl patches to gcc-core, and untarring gfortran
> on that, would be adequate-that's what I did for g77.
>> -qt3 & qt4 libs won't build OOB.
>
>
>
>

Help-wanted tasks for musl

[Rich Felker]

Hi all,
Here are some tasks I could really use some help on, based on current
topics and requests that have come up on the list and IRC. Any
volunteers? See below...

Rich



Research on NSCD protocol

Interfacing with a proxy/cache daemon using nscd protocol is one of
the proposed options for allowing musl to deal with NIS/LDAP/etc. user
databases. In order to evaluate the option, we need to know how the
protocol works and what's involved in making queries and receiving
responses. Documenting how it works would be really helpful. I'm not
looking for big, complete protocol documentation, just simple
descriptions and examples of how queries are conducted.


Analysis of Gregor's pkgsrc failure results

Gregor Richards has run the whole NetBSD pkgsrc build (over 10k
packages) against musl and posted reports to the mailing list and
wiki. Some analysis on the most frequent causes of failure could be
extremely helpful to improving compatibility. It would also be nice to
identify major dependency failures that can be fixed (either in the
upstream package if it's buggy, or in musl if it's due to missing
features) so that the packages which depend on them can be tested too.
I'm looking to get results in the form of "we should fix X and Y and Z
and then lots more packages will work".


Preparing MD5 and SHA crypt for integration

See the threads on the list. Basically we need source with appropriate
license status (MIT/BSD/permissive or public domain) that's optimized
for size.


Regression testing

This is a big project, but there are lots of things that can be done
to contribute without doing it all. Basically it entails reading the
git log, identifying all bugs fixed, and for each bug, formulating a
test that reflects whether the bug exists or not.

Re: Help-wanted tasks for musl

[idunham]

> Hi all,
> Here are some tasks I could really use some help on, based on current
> topics and requests that have come up on the list and IRC. Any
> volunteers? See below...

> Interfacing with a proxy/cache daemon using nscd protocol is one of
> the proposed options for allowing musl to deal with NIS/LDAP/etc. user
> databases. In order to evaluate the option, we need to know how the
> protocol works and what's involved in making queries and receiv
> Analysis of Gregor's pkgsrc failure results
>
> Gregor Richards has run the whole NetBSD pkgsrc build (over 10k
> packages) against musl and posted reports to the mailing list and
> wiki. Some analysis on the most frequent causes of failure could be
> extremely helpful to improving compatibility. It would also be nice to
> identify major dependency failures that can be fixed (either in the
> upstream package if it's buggy, or in musl if it's due to missing
> features) so that the packages which depend on them can be tested too.
> I'm looking to get results in the form of "we should fix X and Y and Z
> and then lots more packages will work".
>
ISTR that Gregor has something that gives him scores for how important
different packages are.

I look at this once in a while already, but now that I've done a little
repartitioning, should be able to do a little more...
Just for a brief overview of a few things:
-SDL: patches haven't been merged
-There are at least a dozen packages that should be building, per my own
tests without pkgsrc, but aren't.
-e2fsprogs provides libcomerr, so I suspect blocks zephyr, which blocks
libpurple/pidgin/...
-avahi is semi-important
-ruby has been one of the higher-priority ones to fix
-R needs g77 or gfortran a/k/a g95 (I have g77, but that's not in pkgsrc...).
Also needs lapack & blas which need the same.
Octave needs all of the above, plus more...
I suspect that applying musl patches to gcc-core, and untarring gfortran
on that, would be adequate-that's what I did for g77.
-qt3 & qt4 libs won't build OOB.
> Regression testing
>
> This is a big project, but there are lots of things that can be done
> to contribute without doing it all. Basically it entails reading the
> git log, identifying all bugs fixed, and for each bug, formulating a
> test that reflects whether the bug exists or not.
>
Is git shortlog |grep -i bug going to be enough to catch them all, or not?

Re: Help-wanted tasks for musl

[William Haddon]

On 08/19/2012 04:10 AM, idunham@lavabit.com wrote:
> I look at this once in a while already, but now that I've done a little
> repartitioning, should be able to do a little more...
> Just for a brief overview of a few things:
> -SDL: patches haven't been merged
> -There are at least a dozen packages that should be building, per my own
> tests without pkgsrc, but aren't.
> -e2fsprogs provides libcomerr, so I suspect blocks zephyr, which blocks
> libpurple/pidgin/...
>    
I have successfully built e2fsprogs on musl without patching using

CFLAGS=-D_GNU_SOURCE ../src/configure --disable-tls --disable-nls 
--disable-uuidd --disable-fsck \
--disable-e2initrd-helper --disable-defrag --enable-symlink-install 
--enable-elf-shlibs

The result includes e2fsck and libcom_err. Some of the "--disable"s are 
there because I didn't want various features rather than because they 
didn't compile, but I don't remember which is which. Most of them can 
probably be removed. I do know that --disable-defrag is necessary 
because the e4defrag program doesn't compile on musl. However it can be 
made to compile by replacing all the instances of loff_t with off64_t 
and adding a wrapper for the mincore syscall.

- Will Haddon
> -avahi is semi-important
> -ruby has been one of the higher-priority ones to fix
> -R needs g77 or gfortran a/k/a g95 (I have g77, but that's not in pkgsrc...).
> Also needs lapack&  blas which need the same.
> Octave needs all of the above, plus more...
> I suspect that applying musl patches to gcc-core, and untarring gfortran
> on that, would be adequate-that's what I did for g77.
> -qt3&  qt4 libs won't build OOB

Re: Help-wanted tasks for musl

[boris brezillon]

2012/8/19 Rich Felker <dalias@aerifal.cx>:
> Hi all,
> Here are some tasks I could really use some help on, based on current
> topics and requests that have come up on the list and IRC. Any
> volunteers? See below...
>
> Rich
>
>
>
> Research on NSCD protocol
>
> Interfacing with a proxy/cache daemon using nscd protocol is one of
> the proposed options for allowing musl to deal with NIS/LDAP/etc. user
> databases. In order to evaluate the option, we need to know how the
> protocol works and what's involved in making queries and receiving
> responses. Documenting how it works would be really helpful. I'm not
> looking for big, complete protocol documentation, just simple
> descriptions and examples of how queries are conducted.
>
>
> Analysis of Gregor's pkgsrc failure results
>
> Gregor Richards has run the whole NetBSD pkgsrc build (over 10k
> packages) against musl and posted reports to the mailing list and
> wiki. Some analysis on the most frequent causes of failure could be
> extremely helpful to improving compatibility. It would also be nice to
> identify major dependency failures that can be fixed (either in the
> upstream package if it's buggy, or in musl if it's due to missing
> features) so that the packages which depend on them can be tested too.
> I'm looking to get results in the form of "we should fix X and Y and Z
> and then lots more packages will work".
>
>
> Preparing MD5 and SHA crypt for integration
>
> See the threads on the list. Basically we need source with appropriate
> license status (MIT/BSD/permissive or public domain) that's optimized
> for size.
Did you take a look at tropicssl? It's an ssl lib (BSD license) used
in embedded systems.
But I'm not sure it's optimized for size.
>
>
> Regression testing
>
> This is a big project, but there are lots of things that can be done
> to contribute without doing it all. Basically it entails reading the
> git log, identifying all bugs fixed, and for each bug, formulating a
> test that reflects whether the bug exists or not.

Re: Help-wanted tasks for musl

[Szabolcs Nagy]

* Rich Felker <dalias@aerifal.cx> [2012-08-19 00:26:11 -0400]:
> Preparing MD5 and SHA crypt for integration
> 
> See the threads on the list. Basically we need source with appropriate
> license status (MIT/BSD/permissive or public domain) that's optimized
> for size.
> 

i'm looking into this

fun fact:
the sha based crypt (the modern one designed in 2007,
but it follows the old weird md5 crypt algo)
has limits on the rounds but no mention of limits on keys

http://www.akkadia.org/drepper/SHA-crypt.txt

eventhough

step 11. is O(keylen * log(keylen))
step 14. is O(keylen^2) (!)
step 16. the reference implementation uses alloca(keylen) (!!)
step 21. is O(keylen * rounds)

(md5 crypt is O(keylen) with fixed iteration count)

and there are alignment optimizations in the
reference implementation..
i guess that's some bad joke

Re: Help-wanted tasks for musl

[Szabolcs Nagy]

* Szabolcs Nagy <nsz@port70.net> [2012-08-19 13:49:14 +0200]:
> * Rich Felker <dalias@aerifal.cx> [2012-08-19 00:26:11 -0400]:
> > Preparing MD5 and SHA crypt for integration
> > 
> > See the threads on the list. Basically we need source with appropriate
> > license status (MIT/BSD/permissive or public domain) that's optimized
> > for size.
> > 
> 
> i'm looking into this
> 
> fun fact:
> the sha based crypt (the modern one designed in 2007,
> but it follows the old weird md5 crypt algo)
> has limits on the rounds but no mention of limits on keys
> 
> http://www.akkadia.org/drepper/SHA-crypt.txt
> 
> eventhough
> 
> step 11. is O(keylen * log(keylen))
> step 14. is O(keylen^2) (!)
> step 16. the reference implementation uses alloca(keylen) (!!)
> step 21. is O(keylen * rounds)
> 

i have preliminary code for md5 and sha crypt
http://port70.net/~nsz/crypt/

but i found other design problems with sha crypt

1) keylen is not limited while the algo is O(keylen^2)
(see above)

2)* according to the spec 'rounds=<N>$' prefix should
be recognized as an iteration specification, but the
reference implementation (and in glibc) accepts empty
or whitespace only N as well, ie.

  '$5$rounds=  $' is treated as '$5$rounds=0$'

3)* reference implementation and glibc accepts negative
rounds in an implementation defined way, ie.

  '$5$rounds=-4294965296$' is treated as
  '$5$rounds=2000$' on a 32bit system and as
  '$5$rounds=999999999$' on a 64bit one

(according to spec N is clamped into 1000...999999999
so the correct treatment would be '$5$rounds=1000$')

4) if the rounds part is not closed by '$' then it is
treated as a salt, but in the output there will be a $
after the salt so it will look like a proper rounds setting,
so output should be treated carefully when the salt has to
be parsed back, ie.

  '$5$rounds=1000' setting will result in an output like
  '$5$rounds=1000$<hash>'

where the salt is 'rounds=1000'

the output can be correctly parsed (based on the $s)
but it's not possible to use the output as a setting
like in the md5 crypt case

i don't know if this is a real issue, but it seems ugly


* the cause of 2) and 3) is that the reference implementation
recognizes rounds=<N>$ if strtoul returns with the end
pointer on a '$'

so strtoul semantics should be assumed for the '<N>$' part

which depends on ULONG_MAX value in case of negative numbers
and may modify errno etc

Re: Help-wanted tasks for musl

[Szabolcs Nagy]

* Szabolcs Nagy <nsz@port70.net> [2012-08-19 18:56:52 +0200]:
> 3)* reference implementation and glibc accepts negative
> rounds in an implementation defined way, ie.
> 
>   '$5$rounds=-4294965296$' is treated as
>   '$5$rounds=2000$' on a 32bit system and as
>   '$5$rounds=999999999$' on a 64bit one
> 
> (according to spec N is clamped into 1000...999999999
> so the correct treatment would be '$5$rounds=1000$')
> 

i was wrong here about the correct treatment

the spec says that N is an unsigned decimal so negative
numbers must not be recognized at all
(so in this case the default rounds should be used and
'rounds=-4294965296' should be treated as salt)

but i guess the spec does not matter much in this case,
either we should be bug compatible with glibc or reject
such salts

Re: Help-wanted tasks for musl

[Rich Felker]

On Sun, Aug 19, 2012 at 07:29:21PM +0200, Szabolcs Nagy wrote:
> * Szabolcs Nagy <nsz@port70.net> [2012-08-19 18:56:52 +0200]:
> > 3)* reference implementation and glibc accepts negative
> > rounds in an implementation defined way, ie.
> > 
> >   '$5$rounds=-4294965296$' is treated as
> >   '$5$rounds=2000$' on a 32bit system and as
> >   '$5$rounds=999999999$' on a 64bit one
> > 
> > (according to spec N is clamped into 1000...999999999
> > so the correct treatment would be '$5$rounds=1000$')
> > 
> 
> i was wrong here about the correct treatment
> 
> the spec says that N is an unsigned decimal so negative
> numbers must not be recognized at all
> (so in this case the default rounds should be used and
> 'rounds=-4294965296' should be treated as salt)
> 
> but i guess the spec does not matter much in this case,
> either we should be bug compatible with glibc or reject
> such salts

The characters '=', '-', and '$' are not valid in salt, are they?
My preference would be to reject anything that looks like a setting
but actually gets treated as salt, rather than hashing it in some
implementation-specific way that leads to buggy, non-portable password
hashes.

Rich

Re: Help-wanted tasks for musl

[Szabolcs Nagy]

* Rich Felker <dalias@aerifal.cx> [2012-08-19 20:51:28 -0400]:
> The characters '=', '-', and '$' are not valid in salt, are they?
> My preference would be to reject anything that looks like a setting
> but actually gets treated as salt, rather than hashing it in some
> implementation-specific way that leads to buggy, non-portable password
> hashes.
> 

it's not clear what the acceptable characters are..
originally the [a-zA-Z0-9./] is the base64 set used

but the implementations tend to accept anything for salt
(it will go through some hash or encryption function
anyway, the only exception is '$' which is a separator
around the salt and maybe the characters used by the
passwd file format)

otherwise i'd rather be more strict with the input than
deal with weird corner cases, but i don't know what are
the practices (ie rejecting '=' or '-' is reasonable or not)

Re: Help-wanted tasks for musl

[Rich Felker]

On Mon, Aug 20, 2012 at 03:35:02AM +0200, Szabolcs Nagy wrote:
> * Rich Felker <dalias@aerifal.cx> [2012-08-19 20:51:28 -0400]:
> > The characters '=', '-', and '$' are not valid in salt, are they?
> > My preference would be to reject anything that looks like a setting
> > but actually gets treated as salt, rather than hashing it in some
> > implementation-specific way that leads to buggy, non-portable password
> > hashes.
> > 
> 
> it's not clear what the acceptable characters are..
> originally the [a-zA-Z0-9./] is the base64 set used

In all the other hashes we support, only the used base64 set is
allowed. Anything else is treated as a fatal error. Is this wrong?

> but the implementations tend to accept anything for salt
> (it will go through some hash or encryption function
> anyway, the only exception is '$' which is a separator
> around the salt and maybe the characters used by the
> passwd file format)

I agree it would be nicer to just pass the salt through the encryption
algorithm as part of the input, but in practice they all decode it as
a base64 number and use that number...

> otherwise i'd rather be more strict with the input than
> deal with weird corner cases, but i don't know what are
> the practices (ie rejecting '=' or '-' is reasonable or not)

It's what blowfish does, at least.

Rich

Re: Help-wanted tasks for musl

[Szabolcs Nagy]

* Rich Felker <dalias@aerifal.cx> [2012-08-19 21:39:50 -0400]:
> On Mon, Aug 20, 2012 at 03:35:02AM +0200, Szabolcs Nagy wrote:
> > it's not clear what the acceptable characters are..
> > originally the [a-zA-Z0-9./] is the base64 set used
> 
> In all the other hashes we support, only the used base64 set is
> allowed. Anything else is treated as a fatal error. Is this wrong?
> 

old des format accepts any char for salt
(except ':', '\n', '\0' and first char cannot be '_')

new des format (starting with '_')
and blowfish decode the salt so they
depend on the base64 set

> I agree it would be nicer to just pass the salt through the encryption
> algorithm as part of the input, but in practice they all decode it as
> a base64 number and use that number...
> 

sha and md5 crypt does not decode the salt
it is directly passed to a hash function

Re: Help-wanted tasks for musl

[Rich Felker]

On Mon, Aug 20, 2012 at 03:58:54AM +0200, Szabolcs Nagy wrote:
> > I agree it would be nicer to just pass the salt through the encryption
> > algorithm as part of the input, but in practice they all decode it as
> > a base64 number and use that number...
> > 
> 
> sha and md5 crypt does not decode the salt
> it is directly passed to a hash function

Ah, that makes it uglier then, because presumably some of these
malformed things you mentioned are "valid" salt.

By the way, if "strtoul" is used in the definition of what makes a
valid unsigned long, then a '-' sign is valid, and the result is
implementation-specific since it involves reduction modulo
ULONG_MAX+1. For low values like -100, it won't matter, since the high
values get clipped to 1000, but for example -4294967295 would become 1
on 32-bit systems and get clipped to 1000 on 64-bit systems...

BTW², this is a very good general reason why "strtou*" are broken
interfaces that should never be used directly in software that wants
consistent cross-platform behavior. To use them safely you need to
skip leading whitespace manually (if you want to support it at all),
then check that the first non-whitespace character is not a '-' before
passing the tail to strtou*.

Rich

Re: Help-wanted tasks for musl

[Szabolcs Nagy]

[-- Attachment #1: Type: text/plain, Size: 555 bytes --]

* Rich Felker <dalias@aerifal.cx> [2012-08-19 22:12:23 -0400]:
> On Mon, Aug 20, 2012 at 03:58:54AM +0200, Szabolcs Nagy wrote:
> > sha and md5 crypt does not decode the salt
> > it is directly passed to a hash function
> 
> Ah, that makes it uglier then, because presumably some of these
> malformed things you mentioned are "valid" salt.
> 

i modified my sha crypt implementation so it is very strict
about the rounds= part of the salt and checks for key length

otherwise it should be compatible with the glibc one

(i only attach the sha256 version)

[-- Attachment #2: crypt_sha256.c --]
[-- Type: text/x-csrc, Size: 8867 bytes --]

/*
 * public domain sha256 crypt implementation
 *
 * original sha crypt design: http://people.redhat.com/drepper/SHA-crypt.txt
 * in this implementation at least 32bit int is assumed
 * key length is limited, the $5$ prefix is mandatory and rounds= setting
 * must contain a valid iteration count, on error "*" is returned
 */
#include <ctype.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <stdint.h>

/* public domain sha256 implementation based on fips180-3 */

struct sha256 {
	uint64_t len;    /* processed message length */
	uint32_t h[8];   /* hash state */
	uint8_t buf[64]; /* message block buffer */
};

static uint32_t ror(uint32_t n, int k) { return (n >> k) | (n << (32-k)); }
#define Ch(x,y,z)  (z ^ (x & (y ^ z)))
#define Maj(x,y,z) ((x & y) | (z & (x | y)))
#define S0(x)      (ror(x,2) ^ ror(x,13) ^ ror(x,22))
#define S1(x)      (ror(x,6) ^ ror(x,11) ^ ror(x,25))
#define R0(x)      (ror(x,7) ^ ror(x,18) ^ (x>>3))
#define R1(x)      (ror(x,17) ^ ror(x,19) ^ (x>>10))

static const uint32_t K[64] = {
0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2
};

static void processblock(struct sha256 *s, const uint8_t *buf)
{
	uint32_t W[64], t1, t2, a, b, c, d, e, f, g, h;
	int i;

	for (i = 0; i < 16; i++) {
		W[i] = (uint32_t)buf[4*i]<<24;
		W[i] |= (uint32_t)buf[4*i+1]<<16;
		W[i] |= (uint32_t)buf[4*i+2]<<8;
		W[i] |= buf[4*i+3];
	}
	for (; i < 64; i++)
		W[i] = R1(W[i-2]) + W[i-7] + R0(W[i-15]) + W[i-16];
	a = s->h[0];
	b = s->h[1];
	c = s->h[2];
	d = s->h[3];
	e = s->h[4];
	f = s->h[5];
	g = s->h[6];
	h = s->h[7];
#define ROUND(a,b,c,d,e,f,g,h,i) \
		t1 = h + S1(e) + Ch(e,f,g) + K[i] + W[i]; \
		t2 = S0(a) + Maj(a,b,c); \
		d += t1; \
		h = t1 + t2;
	for (i = 0; i < 64; ) {
		ROUND(a,b,c,d,e,f,g,h,i); i++;
		ROUND(h,a,b,c,d,e,f,g,i); i++;
		ROUND(g,h,a,b,c,d,e,f,i); i++;
		ROUND(f,g,h,a,b,c,d,e,i); i++;
		ROUND(e,f,g,h,a,b,c,d,i); i++;
		ROUND(d,e,f,g,h,a,b,c,i); i++;
		ROUND(c,d,e,f,g,h,a,b,i); i++;
		ROUND(b,c,d,e,f,g,h,a,i); i++;
	}
	s->h[0] += a;
	s->h[1] += b;
	s->h[2] += c;
	s->h[3] += d;
	s->h[4] += e;
	s->h[5] += f;
	s->h[6] += g;
	s->h[7] += h;
}

static void pad(struct sha256 *s)
{
	unsigned r = s->len % 64;

	s->buf[r++] = 0x80;
	if (r > 56) {
		memset(s->buf + r, 0, 64 - r);
		r = 0;
		processblock(s, s->buf);
	}
	memset(s->buf + r, 0, 56 - r);
	s->len *= 8;
	s->buf[56] = s->len >> 56;
	s->buf[57] = s->len >> 48;
	s->buf[58] = s->len >> 40;
	s->buf[59] = s->len >> 32;
	s->buf[60] = s->len >> 24;
	s->buf[61] = s->len >> 16;
	s->buf[62] = s->len >> 8;
	s->buf[63] = s->len;
	processblock(s, s->buf);
}

void sha256_init(struct sha256 *s)
{
	s->len = 0;
	s->h[0] = 0x6a09e667;
	s->h[1] = 0xbb67ae85;
	s->h[2] = 0x3c6ef372;
	s->h[3] = 0xa54ff53a;
	s->h[4] = 0x510e527f;
	s->h[5] = 0x9b05688c;
	s->h[6] = 0x1f83d9ab;
	s->h[7] = 0x5be0cd19;
}

void sha256_sum(struct sha256 *s, uint8_t md[20])
{
	int i;

	pad(s);
	for (i = 0; i < 8; i++) {
		md[4*i] = s->h[i] >> 24;
		md[4*i+1] = s->h[i] >> 16;
		md[4*i+2] = s->h[i] >> 8;
		md[4*i+3] = s->h[i];
	}
}

void sha256_update(struct sha256 *s, const void *m, unsigned long len)
{
	const uint8_t *p = m;
	unsigned r = s->len % 64;

	s->len += len;
	if (r) {
		if (len < 64 - r) {
			memcpy(s->buf + r, p, len);
			return;
		}
		memcpy(s->buf + r, p, 64 - r);
		len -= 64 - r;
		p += 64 - r;
		processblock(s, s->buf);
	}
	for (; len >= 64; len -= 64, p += 64)
		processblock(s, p);
	memcpy(s->buf, p, len);
}

static unsigned char b64[] =
"./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";

static char *to64(char *s, unsigned int u, int n)
{
	while (--n >= 0) {
		*s++ = b64[u % 64];
		u /= 64;
	}
	return s;
}

/* key limit is not part of the original design, added for DoS protection */
#define KEY_MAX 65535
#define SALT_MAX 16
#define ROUNDS_DEFAULT 5000
#define ROUNDS_MIN 1000
#define ROUNDS_MAX 999999999

/* hash n bytes of the repeated md message digest */
static void hashmd(struct sha256 *s, unsigned int n, const void *md)
{
	unsigned int i;

	for (i = n; i > 32; i -= 32)
		sha256_update(s, md, 32);
	sha256_update(s, md, i);
}

static char *sha256crypt(const char *key, const char *setting, char *output)
{
	struct sha256 ctx;
	unsigned char md[32], kmd[32], smd[32];
	unsigned int i, r, klen, slen;
	char rounds[20] = "";
	const char *salt;
	char *p;

	/* reject large keys */
	for (i = 0; i <= KEY_MAX && key[i]; i++);
	if (i > KEY_MAX)
		return 0;
	klen = i;

	/* setting: $5$rounds=n$salt$ (rounds=n$ and closing $ are optional) */
	if (strncmp(setting, "$5$", 3) != 0)
		return 0;
	salt = setting + 3;

	r = ROUNDS_DEFAULT;
	if (strncmp(salt, "rounds=", sizeof "rounds=" - 1) == 0) {
		unsigned long u;
		char *end;

		/*
		 * this is a deviation from the reference:
		 * bad rounds setting is rejected if it is
		 * - empty
		 * - unterminated (missing '$')
		 * - not a decimal number
		 * - negative
		 * - whitespace prefixed or has sign
		 * - very long (>=20 digits)
		 * the reference implementation treats these bad
		 * rounds as part of the salt or parse them with
		 * strtoul semantics which may cause problems
		 */
		salt += sizeof "rounds=" - 1;
		for (i = 0; i < 20 && isdigit(salt[i]); i++);
		if (i == 0 || salt[i] != '$')
			return 0;
		u = strtoul(salt, &end, 10);
		if (end != salt + i)
			/* cannot happen unless strtoul is broken */
			return 0;
		salt += i + 1;
		if (u < ROUNDS_MIN)
			r = ROUNDS_MIN;
		else if (u > ROUNDS_MAX)
			r = ROUNDS_MAX;
		else
			r = u;
		/* needed when rounds is zero prefixed or out of bounds */
		sprintf(rounds, "rounds=%u$", r);
	}

// TODO: reject bad characters in the salt that may cause /etc/shadow parsing problems
	for (i = 0; i < SALT_MAX && salt[i] && salt[i] != '$'; i++);
	slen = i;

	/* B = sha(key salt key) */
	sha256_init(&ctx);
	sha256_update(&ctx, key, klen);
	sha256_update(&ctx, salt, slen);
	sha256_update(&ctx, key, klen);
	sha256_sum(&ctx, md);

	/* A = sha(key salt repeat-B alternate-B-key) */
	sha256_init(&ctx);
	sha256_update(&ctx, key, klen);
	sha256_update(&ctx, salt, slen);
	hashmd(&ctx, klen, md);
	for (i = klen; i > 0; i >>= 1)
		if (i & 1)
			sha256_update(&ctx, md, sizeof md);
		else
			sha256_update(&ctx, key, klen);
	sha256_sum(&ctx, md);

	/* DP = sha(repeat-key), this step takes O(klen^2) time */
	sha256_init(&ctx);
	for (i = 0; i < klen; i++)
		sha256_update(&ctx, key, klen);
	sha256_sum(&ctx, kmd);

	/* DS = sha(repeat-salt) */
	sha256_init(&ctx);
	for (i = 0; i < 16 + md[0]; i++)
		sha256_update(&ctx, salt, slen);
	sha256_sum(&ctx, smd);

	/* iterate A = f(A,DP,DS), this step takes O(rounds*klen) time */
	for (i = 0; i < r; i++) {
		sha256_init(&ctx);
		if (i % 2)
			hashmd(&ctx, klen, kmd);
		else
			sha256_update(&ctx, md, sizeof md);
		if (i % 3)
			sha256_update(&ctx, smd, slen);
		if (i % 7)
			hashmd(&ctx, klen, kmd);
		if (i % 2)
			sha256_update(&ctx, md, sizeof md);
		else
			hashmd(&ctx, klen, kmd);
		sha256_sum(&ctx, md);
	}

	/* output is $5$rounds=n$salt$hash */
	p = output;
	p += sprintf(p, "$5$%s%.*s$", rounds, slen, salt);
	p = to64(p, (md[0]<<16)|(md[10]<<8)|md[20], 4);
	p = to64(p, (md[21]<<16)|(md[1]<<8)|md[11], 4);
	p = to64(p, (md[12]<<16)|(md[22]<<8)|md[2], 4);
	p = to64(p, (md[3]<<16)|(md[13]<<8)|md[23], 4);
	p = to64(p, (md[24]<<16)|(md[4]<<8)|md[14], 4);
	p = to64(p, (md[15]<<16)|(md[25]<<8)|md[5], 4);
	p = to64(p, (md[6]<<16)|(md[16]<<8)|md[26], 4);
	p = to64(p, (md[27]<<16)|(md[7]<<8)|md[17], 4);
	p = to64(p, (md[18]<<16)|(md[28]<<8)|md[8], 4);
	p = to64(p, (md[9]<<16)|(md[19]<<8)|md[29], 4);
	p = to64(p, (md[31]<<8)|md[30], 3);
	*p = 0;
	return output;
}

char *__crypt_sha256(const char *key, const char *setting, char *output)
{
	static const char testkey[] = "Xy01@#\x01\x02\x80\x7f\xff\r\n\x81\t !";
	static const char testsetting[] = "$5$rounds=1234$abc0123456789$";
	static const char testhash[] = "$5$rounds=1234$abc0123456789$3VfDjPt05VHFn47C/ojFZ6KRPYrOjj1lLbH.dkF3bZ6";
	char testbuf[128];
	char *p, *q;

	p = sha256crypt(key, setting, output);
	/* self test and stack cleanup */
	q = sha256crypt(testkey, testsetting, testbuf);
	if (!p || q != testbuf || memcmp(testbuf, testhash, sizeof testhash))
		return "*";
	return p;
}

[-- Attachment #3: crypt_sha256_test.c --]
[-- Type: text/x-csrc, Size: 3035 bytes --]

#include <stdio.h>
#include <string.h>
#include <crypt.h>

char *__crypt_sha256(const char *pw, const char *salt, char *output);

static const struct {
	char *h;
	char *s;
	char *k;
} t[] = {
{"$5$rounds=1234$abc0123456789$3VfDjPt05VHFn47C/ojFZ6KRPYrOjj1lLbH.dkF3bZ6", "$5$rounds=1234$abc0123456789$", "Xy01@#\x01\x02\x80\x7f\xff\r\n\x81\t !"},
{"*", "$55$", ""},
{"$5$$3c2QQ0KjIU1OLtB29cl8Fplc2WN7X89bnoEjaR7tWu.", "$5$$", ""},
{"$5$salt$HrcUzzoef72uxM/YhTU5BAi419Fblqlq//zyM.rIOG0", "$5$salt$", ""},
{"$5$salt1234$BvcCH7hKo17/ntDgDlEwYxXx8mpvE8S57LUDZTL7XQC", "$5$salt1234$", ""},
{"$5$salt1234$R0UaMrtBbZLZnp/gkgrFvfvgaP9ttQfKe8s6270zumD", "$5$salt1234$", "a"},
{"$5$salt1234$yIGonLACDTBOAHFFhBoa70V4StnUS2PdbWDzNZrS8UC", "$5$salt1234$", "abc"},
{"$5$salt1234$1145V3OxW91Wl.LSS3pmBHvb2jV3ujiUhD7DgpoJtw9", "$5$salt1234$", "Aa@\xaa 0123456789"},
{"$5$aaaaaaaaaaaaaaaa$q.VQjybA0pKixryyW2EZyePZ/VjbS6iTBEwbRHQxpIA", "$5$aaaaaaaaaaaaaaaaaaaa$", "aaaaaaaaaaaaaaaaaaaa"},
{"$5$rounds=1000$$ZIwsx59lFMWVo3Yt6IxpZVn0IhpY8Yg4gxC21zUDBI4", "$5$rounds=1$", "a"},
{"$5$rounds=1000$$ZIwsx59lFMWVo3Yt6IxpZVn0IhpY8Yg4gxC21zUDBI4", "$5$rounds=1000$", "a"},
{"$5$rounds=1234$$i.IiuqtWmTzupHAZtfV/PB33Usz.MwGHq9BKFAEj.B3", "$5$rounds=1234$", "a"},
{"$5$rounds=1234$$i.IiuqtWmTzupHAZtfV/PB33Usz.MwGHq9BKFAEj.B3", "$5$rounds=00001234$", "a"},
/* incompatible with glibc crypt (sha crypt design bugs) */
{"*", "$5$rounds=$", ""},
{"*", "$5$rounds=1234", ""},
{"*", "$5$rounds=123x$", ""},
{"*", "$5$rounds=+1234$", ""},
{"*", "$5$rounds= 1234$", ""},
{"*", "$5$rounds=1234567890123456789012345678901234567890$", ""},
{"*", "$5$rounds=  +00$", ""},
{"*", "$5$rounds=-4294965296$", ""},
/* official tests: */
{"$5$saltstring$5B8vYYiY.CVt1RlTTf8KbXBH3hsxY/GNooZaBBGWEc5",
	"$5$saltstring", "Hello world!"},
{"$5$rounds=10000$saltstringsaltst$3xv.VbSHBb41AL9AvLeujZkZRBAwqFMz2.opqey6IcA",
	"$5$rounds=10000$saltstringsaltstring", "Hello world!"},
{"$5$rounds=5000$toolongsaltstrin$Un/5jzAHMgOGZ5.mWJpuVolil07guHPvOW8mGRcvxa5",
	"$5$rounds=5000$toolongsaltstring", "This is just a test"},
{"$5$rounds=1400$anotherlongsalts$Rx.j8H.h8HjEDGomFU8bDkXm3XIUnzyxf12oP84Bnq1",
	"$5$rounds=1400$anotherlongsaltstring", "a very much longer text to encrypt.  This one even stretches over morethan one line."},
{"$5$rounds=77777$short$JiO1O3ZpDAxGJeaDIuqCoEFysAe1mZNJRs3pw0KQRd/",
	"$5$rounds=77777$short", "we have a short salt string but not a short password"},
{"$5$rounds=123456$asaltof16chars..$gP3VQ/6X7UUEW3HkBn2w1/Ptq2jxPyzV/cZKmF/wJvD",
	"$5$rounds=123456$asaltof16chars..", "a short string"},
{"$5$rounds=1000$roundstoolow$yfvwcWrQ8l/K0DAWyuPMDNHpIVlTQebY9l/gL972bIC",
	"$5$rounds=10$roundstoolow", "the minimum number is still observed"},
};

int main()
{
	char a[128];
	char *p;
	int i, err = 0;

	for (i = 0; i < sizeof t/sizeof *t; i++) {
		p = __crypt_sha256(t[i].k, t[i].s, a);
		if (strcmp(p, t[i].h) != 0) {
			printf("crypt(%s, %s) got %s want %s crypt: %s\n",
				t[i].k, t[i].s, p, t[i].h, crypt(t[i].k, t[i].s));
			err = 1;
		}
	}
	return err;
}

Re: Help-wanted tasks for musl

[Szabolcs Nagy]

[-- Attachment #1: Type: text/plain, Size: 2019 bytes --]

* Szabolcs Nagy <nsz@port70.net> [2012-08-28 22:09:42 +0200]:
> * Rich Felker <dalias@aerifal.cx> [2012-08-19 22:12:23 -0400]:
> > On Mon, Aug 20, 2012 at 03:58:54AM +0200, Szabolcs Nagy wrote:
> > > sha and md5 crypt does not decode the salt
> > > it is directly passed to a hash function
> > 
> > Ah, that makes it uglier then, because presumably some of these
> > malformed things you mentioned are "valid" salt.
> > 
> 
> i modified my sha crypt implementation so it is very strict
> about the rounds= part of the salt and checks for key length
> 

removed the unrolling, modified key limit and added salt check:

@@ -60,20 +61,17 @@
 	f = s->h[5];
 	g = s->h[6];
 	h = s->h[7];
-#define ROUND(a,b,c,d,e,f,g,h,i) \
-		t1 = h + S1(e) + Ch(e,f,g) + K[i] + W[i]; \
-		t2 = S0(a) + Maj(a,b,c); \
-		d += t1; \
-		h = t1 + t2;
-	for (i = 0; i < 64; ) {
-		ROUND(a,b,c,d,e,f,g,h,i); i++;
-		ROUND(h,a,b,c,d,e,f,g,i); i++;
-		ROUND(g,h,a,b,c,d,e,f,i); i++;
-		ROUND(f,g,h,a,b,c,d,e,i); i++;
-		ROUND(e,f,g,h,a,b,c,d,i); i++;
-		ROUND(d,e,f,g,h,a,b,c,i); i++;
-		ROUND(c,d,e,f,g,h,a,b,i); i++;
-		ROUND(b,c,d,e,f,g,h,a,i); i++;
+	for (i = 0; i < 64; i++) {
+		t1 = h + S1(e) + Ch(e,f,g) + K[i] + W[i];
+		t2 = S0(a) + Maj(a,b,c);
+		h = g;
+		g = f;
+		f = e;
+		e = d + t1;
+		d = c;
+		c = b;
+		b = a;
+		a = t1 + t2;
 	}
 	s->h[0] += a;
 	s->h[1] += b;
@@ -168,7 +166,7 @@
 }
 
 /* key limit is not part of the original design, added for DoS protection */
-#define KEY_MAX 65535
+#define KEY_MAX 256
 #define SALT_MAX 16
 #define ROUNDS_DEFAULT 5000
 #define ROUNDS_MIN 1000
@@ -241,8 +239,10 @@
 		sprintf(rounds, "rounds=%u$", r);
 	}
 
-// TODO: reject bad characters in the salt that may cause /etc/shadow parsing problems
-	for (i = 0; i < SALT_MAX && salt[i] && salt[i] != '$'; i++);
+	for (i = 0; i < SALT_MAX && salt[i] && salt[i] != '$'; i++)
+		/* reject characters that interfere with /etc/shadow parsing */
+		if (salt[i] == '\n' || salt[i] == ':')
+			return 0;
 	slen = i;
 
 	/* B = sha(key salt key) */

[-- Attachment #2: crypt_sha256.c --]
[-- Type: text/x-csrc, Size: 8695 bytes --]

/*
 * public domain sha256 crypt implementation
 *
 * original sha crypt design: http://people.redhat.com/drepper/SHA-crypt.txt
 * in this implementation at least 32bit int is assumed,
 * key length is limited, the $5$ prefix is mandatory, '\n' and ':' is rejected
 * in the salt and rounds= setting must contain a valid iteration count,
 * on error "*" is returned.
 */
#include <ctype.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <stdint.h>

/* public domain sha256 implementation based on fips180-3 */

struct sha256 {
	uint64_t len;    /* processed message length */
	uint32_t h[8];   /* hash state */
	uint8_t buf[64]; /* message block buffer */
};

static uint32_t ror(uint32_t n, int k) { return (n >> k) | (n << (32-k)); }
#define Ch(x,y,z)  (z ^ (x & (y ^ z)))
#define Maj(x,y,z) ((x & y) | (z & (x | y)))
#define S0(x)      (ror(x,2) ^ ror(x,13) ^ ror(x,22))
#define S1(x)      (ror(x,6) ^ ror(x,11) ^ ror(x,25))
#define R0(x)      (ror(x,7) ^ ror(x,18) ^ (x>>3))
#define R1(x)      (ror(x,17) ^ ror(x,19) ^ (x>>10))

static const uint32_t K[64] = {
0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2
};

static void processblock(struct sha256 *s, const uint8_t *buf)
{
	uint32_t W[64], t1, t2, a, b, c, d, e, f, g, h;
	int i;

	for (i = 0; i < 16; i++) {
		W[i] = (uint32_t)buf[4*i]<<24;
		W[i] |= (uint32_t)buf[4*i+1]<<16;
		W[i] |= (uint32_t)buf[4*i+2]<<8;
		W[i] |= buf[4*i+3];
	}
	for (; i < 64; i++)
		W[i] = R1(W[i-2]) + W[i-7] + R0(W[i-15]) + W[i-16];
	a = s->h[0];
	b = s->h[1];
	c = s->h[2];
	d = s->h[3];
	e = s->h[4];
	f = s->h[5];
	g = s->h[6];
	h = s->h[7];
	for (i = 0; i < 64; i++) {
		t1 = h + S1(e) + Ch(e,f,g) + K[i] + W[i];
		t2 = S0(a) + Maj(a,b,c);
		h = g;
		g = f;
		f = e;
		e = d + t1;
		d = c;
		c = b;
		b = a;
		a = t1 + t2;
	}
	s->h[0] += a;
	s->h[1] += b;
	s->h[2] += c;
	s->h[3] += d;
	s->h[4] += e;
	s->h[5] += f;
	s->h[6] += g;
	s->h[7] += h;
}

static void pad(struct sha256 *s)
{
	unsigned r = s->len % 64;

	s->buf[r++] = 0x80;
	if (r > 56) {
		memset(s->buf + r, 0, 64 - r);
		r = 0;
		processblock(s, s->buf);
	}
	memset(s->buf + r, 0, 56 - r);
	s->len *= 8;
	s->buf[56] = s->len >> 56;
	s->buf[57] = s->len >> 48;
	s->buf[58] = s->len >> 40;
	s->buf[59] = s->len >> 32;
	s->buf[60] = s->len >> 24;
	s->buf[61] = s->len >> 16;
	s->buf[62] = s->len >> 8;
	s->buf[63] = s->len;
	processblock(s, s->buf);
}

void sha256_init(struct sha256 *s)
{
	s->len = 0;
	s->h[0] = 0x6a09e667;
	s->h[1] = 0xbb67ae85;
	s->h[2] = 0x3c6ef372;
	s->h[3] = 0xa54ff53a;
	s->h[4] = 0x510e527f;
	s->h[5] = 0x9b05688c;
	s->h[6] = 0x1f83d9ab;
	s->h[7] = 0x5be0cd19;
}

void sha256_sum(struct sha256 *s, uint8_t md[20])
{
	int i;

	pad(s);
	for (i = 0; i < 8; i++) {
		md[4*i] = s->h[i] >> 24;
		md[4*i+1] = s->h[i] >> 16;
		md[4*i+2] = s->h[i] >> 8;
		md[4*i+3] = s->h[i];
	}
}

void sha256_update(struct sha256 *s, const void *m, unsigned long len)
{
	const uint8_t *p = m;
	unsigned r = s->len % 64;

	s->len += len;
	if (r) {
		if (len < 64 - r) {
			memcpy(s->buf + r, p, len);
			return;
		}
		memcpy(s->buf + r, p, 64 - r);
		len -= 64 - r;
		p += 64 - r;
		processblock(s, s->buf);
	}
	for (; len >= 64; len -= 64, p += 64)
		processblock(s, p);
	memcpy(s->buf, p, len);
}

static unsigned char b64[] =
"./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";

static char *to64(char *s, unsigned int u, int n)
{
	while (--n >= 0) {
		*s++ = b64[u % 64];
		u /= 64;
	}
	return s;
}

/* key limit is not part of the original design, added for DoS protection */
#define KEY_MAX 256
#define SALT_MAX 16
#define ROUNDS_DEFAULT 5000
#define ROUNDS_MIN 1000
#define ROUNDS_MAX 999999999

/* hash n bytes of the repeated md message digest */
static void hashmd(struct sha256 *s, unsigned int n, const void *md)
{
	unsigned int i;

	for (i = n; i > 32; i -= 32)
		sha256_update(s, md, 32);
	sha256_update(s, md, i);
}

static char *sha256crypt(const char *key, const char *setting, char *output)
{
	struct sha256 ctx;
	unsigned char md[32], kmd[32], smd[32];
	unsigned int i, r, klen, slen;
	char rounds[20] = "";
	const char *salt;
	char *p;

	/* reject large keys */
	for (i = 0; i <= KEY_MAX && key[i]; i++);
	if (i > KEY_MAX)
		return 0;
	klen = i;

	/* setting: $5$rounds=n$salt$ (rounds=n$ and closing $ are optional) */
	if (strncmp(setting, "$5$", 3) != 0)
		return 0;
	salt = setting + 3;

	r = ROUNDS_DEFAULT;
	if (strncmp(salt, "rounds=", sizeof "rounds=" - 1) == 0) {
		unsigned long u;
		char *end;

		/*
		 * this is a deviation from the reference:
		 * bad rounds setting is rejected if it is
		 * - empty
		 * - unterminated (missing '$')
		 * - not a decimal number
		 * - negative
		 * - whitespace prefixed or has sign
		 * - very long (>=20 digits)
		 * the reference implementation treats these bad
		 * rounds as part of the salt or parse them with
		 * strtoul semantics which may cause problems
		 */
		salt += sizeof "rounds=" - 1;
		for (i = 0; i < 20 && isdigit(salt[i]); i++);
		if (i == 0 || salt[i] != '$')
			return 0;
		u = strtoul(salt, &end, 10);
		if (end != salt + i)
			/* cannot happen unless strtoul is broken */
			return 0;
		salt += i + 1;
		if (u < ROUNDS_MIN)
			r = ROUNDS_MIN;
		else if (u > ROUNDS_MAX)
			r = ROUNDS_MAX;
		else
			r = u;
		/* needed when rounds is zero prefixed or out of bounds */
		sprintf(rounds, "rounds=%u$", r);
	}

	for (i = 0; i < SALT_MAX && salt[i] && salt[i] != '$'; i++)
		/* reject characters that interfere with /etc/shadow parsing */
		if (salt[i] == '\n' || salt[i] == ':')
			return 0;
	slen = i;

	/* B = sha(key salt key) */
	sha256_init(&ctx);
	sha256_update(&ctx, key, klen);
	sha256_update(&ctx, salt, slen);
	sha256_update(&ctx, key, klen);
	sha256_sum(&ctx, md);

	/* A = sha(key salt repeat-B alternate-B-key) */
	sha256_init(&ctx);
	sha256_update(&ctx, key, klen);
	sha256_update(&ctx, salt, slen);
	hashmd(&ctx, klen, md);
	for (i = klen; i > 0; i >>= 1)
		if (i & 1)
			sha256_update(&ctx, md, sizeof md);
		else
			sha256_update(&ctx, key, klen);
	sha256_sum(&ctx, md);

	/* DP = sha(repeat-key), this step takes O(klen^2) time */
	sha256_init(&ctx);
	for (i = 0; i < klen; i++)
		sha256_update(&ctx, key, klen);
	sha256_sum(&ctx, kmd);

	/* DS = sha(repeat-salt) */
	sha256_init(&ctx);
	for (i = 0; i < 16 + md[0]; i++)
		sha256_update(&ctx, salt, slen);
	sha256_sum(&ctx, smd);

	/* iterate A = f(A,DP,DS), this step takes O(rounds*klen) time */
	for (i = 0; i < r; i++) {
		sha256_init(&ctx);
		if (i % 2)
			hashmd(&ctx, klen, kmd);
		else
			sha256_update(&ctx, md, sizeof md);
		if (i % 3)
			sha256_update(&ctx, smd, slen);
		if (i % 7)
			hashmd(&ctx, klen, kmd);
		if (i % 2)
			sha256_update(&ctx, md, sizeof md);
		else
			hashmd(&ctx, klen, kmd);
		sha256_sum(&ctx, md);
	}

	/* output is $5$rounds=n$salt$hash */
	p = output;
	p += sprintf(p, "$5$%s%.*s$", rounds, slen, salt);
	p = to64(p, (md[0]<<16)|(md[10]<<8)|md[20], 4);
	p = to64(p, (md[21]<<16)|(md[1]<<8)|md[11], 4);
	p = to64(p, (md[12]<<16)|(md[22]<<8)|md[2], 4);
	p = to64(p, (md[3]<<16)|(md[13]<<8)|md[23], 4);
	p = to64(p, (md[24]<<16)|(md[4]<<8)|md[14], 4);
	p = to64(p, (md[15]<<16)|(md[25]<<8)|md[5], 4);
	p = to64(p, (md[6]<<16)|(md[16]<<8)|md[26], 4);
	p = to64(p, (md[27]<<16)|(md[7]<<8)|md[17], 4);
	p = to64(p, (md[18]<<16)|(md[28]<<8)|md[8], 4);
	p = to64(p, (md[9]<<16)|(md[19]<<8)|md[29], 4);
	p = to64(p, (md[31]<<8)|md[30], 3);
	*p = 0;
	return output;
}

char *__crypt_sha256(const char *key, const char *setting, char *output)
{
	static const char testkey[] = "Xy01@#\x01\x02\x80\x7f\xff\r\n\x81\t !";
	static const char testsetting[] = "$5$rounds=1234$abc0123456789$";
	static const char testhash[] = "$5$rounds=1234$abc0123456789$3VfDjPt05VHFn47C/ojFZ6KRPYrOjj1lLbH.dkF3bZ6";
	char testbuf[128];
	char *p, *q;

	p = sha256crypt(key, setting, output);
	/* self test and stack cleanup */
	q = sha256crypt(testkey, testsetting, testbuf);
	if (!p || q != testbuf || memcmp(testbuf, testhash, sizeof testhash))
		return "*";
	return p;
}

Re: Help-wanted tasks for musl

[Szabolcs Nagy]

[-- Attachment #1: Type: text/plain, Size: 355 bytes --]

* Szabolcs Nagy <nsz@port70.net> [2012-08-29 01:35:06 +0200]:
> * Szabolcs Nagy <nsz@port70.net> [2012-08-28 22:09:42 +0200]:
> > 
> > i modified my sha crypt implementation so it is very strict
> > about the rounds= part of the salt and checks for key length
> > 
> 
> removed the unrolling, modified key limit and added salt check:
> 

same for sha512


[-- Attachment #2: crypt_sha512.c --]
[-- Type: text/x-csrc, Size: 10809 bytes --]

/*
 * public domain sha512 crypt implementation
 *
 * original sha crypt design: http://people.redhat.com/drepper/SHA-crypt.txt
 * in this implementation at least 32bit int is assumed,
 * key length is limited, the $6$ prefix is mandatory, '\n' and ':' is rejected
 * in the salt and rounds= setting must contain a valid iteration count,
 * on error "*" is returned.
 */
#include <ctype.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <stdint.h>

/* public domain sha512 implementation based on fips180-3 */
/* >=2^64 bits messages are not supported (about 2000 peta bytes) */

struct sha512 {
	uint64_t len;     /* processed message length */
	uint64_t h[8];    /* hash state */
	uint8_t buf[128]; /* message block buffer */
};

static uint64_t ror(uint64_t n, int k) { return (n >> k) | (n << (64-k)); }
#define Ch(x,y,z)  (z ^ (x & (y ^ z)))
#define Maj(x,y,z) ((x & y) | (z & (x | y)))
#define S0(x)      (ror(x,28) ^ ror(x,34) ^ ror(x,39))
#define S1(x)      (ror(x,14) ^ ror(x,18) ^ ror(x,41))
#define R0(x)      (ror(x,1) ^ ror(x,8) ^ (x>>7))
#define R1(x)      (ror(x,19) ^ ror(x,61) ^ (x>>6))

static const uint64_t K[80] = {
0x428a2f98d728ae22ULL, 0x7137449123ef65cdULL, 0xb5c0fbcfec4d3b2fULL, 0xe9b5dba58189dbbcULL,
0x3956c25bf348b538ULL, 0x59f111f1b605d019ULL, 0x923f82a4af194f9bULL, 0xab1c5ed5da6d8118ULL,
0xd807aa98a3030242ULL, 0x12835b0145706fbeULL, 0x243185be4ee4b28cULL, 0x550c7dc3d5ffb4e2ULL,
0x72be5d74f27b896fULL, 0x80deb1fe3b1696b1ULL, 0x9bdc06a725c71235ULL, 0xc19bf174cf692694ULL,
0xe49b69c19ef14ad2ULL, 0xefbe4786384f25e3ULL, 0x0fc19dc68b8cd5b5ULL, 0x240ca1cc77ac9c65ULL,
0x2de92c6f592b0275ULL, 0x4a7484aa6ea6e483ULL, 0x5cb0a9dcbd41fbd4ULL, 0x76f988da831153b5ULL,
0x983e5152ee66dfabULL, 0xa831c66d2db43210ULL, 0xb00327c898fb213fULL, 0xbf597fc7beef0ee4ULL,
0xc6e00bf33da88fc2ULL, 0xd5a79147930aa725ULL, 0x06ca6351e003826fULL, 0x142929670a0e6e70ULL,
0x27b70a8546d22ffcULL, 0x2e1b21385c26c926ULL, 0x4d2c6dfc5ac42aedULL, 0x53380d139d95b3dfULL,
0x650a73548baf63deULL, 0x766a0abb3c77b2a8ULL, 0x81c2c92e47edaee6ULL, 0x92722c851482353bULL,
0xa2bfe8a14cf10364ULL, 0xa81a664bbc423001ULL, 0xc24b8b70d0f89791ULL, 0xc76c51a30654be30ULL,
0xd192e819d6ef5218ULL, 0xd69906245565a910ULL, 0xf40e35855771202aULL, 0x106aa07032bbd1b8ULL,
0x19a4c116b8d2d0c8ULL, 0x1e376c085141ab53ULL, 0x2748774cdf8eeb99ULL, 0x34b0bcb5e19b48a8ULL,
0x391c0cb3c5c95a63ULL, 0x4ed8aa4ae3418acbULL, 0x5b9cca4f7763e373ULL, 0x682e6ff3d6b2b8a3ULL,
0x748f82ee5defb2fcULL, 0x78a5636f43172f60ULL, 0x84c87814a1f0ab72ULL, 0x8cc702081a6439ecULL,
0x90befffa23631e28ULL, 0xa4506cebde82bde9ULL, 0xbef9a3f7b2c67915ULL, 0xc67178f2e372532bULL,
0xca273eceea26619cULL, 0xd186b8c721c0c207ULL, 0xeada7dd6cde0eb1eULL, 0xf57d4f7fee6ed178ULL,
0x06f067aa72176fbaULL, 0x0a637dc5a2c898a6ULL, 0x113f9804bef90daeULL, 0x1b710b35131c471bULL,
0x28db77f523047d84ULL, 0x32caab7b40c72493ULL, 0x3c9ebe0a15c9bebcULL, 0x431d67c49c100d4cULL,
0x4cc5d4becb3e42b6ULL, 0x597f299cfc657e2aULL, 0x5fcb6fab3ad6faecULL, 0x6c44198c4a475817ULL
};

static void processblock(struct sha512 *s, const uint8_t *buf)
{
	uint64_t W[80], t1, t2, a, b, c, d, e, f, g, h;
	int i;

	for (i = 0; i < 16; i++) {
		W[i] = (uint64_t)buf[8*i]<<56;
		W[i] |= (uint64_t)buf[8*i+1]<<48;
		W[i] |= (uint64_t)buf[8*i+2]<<40;
		W[i] |= (uint64_t)buf[8*i+3]<<32;
		W[i] |= (uint64_t)buf[8*i+4]<<24;
		W[i] |= (uint64_t)buf[8*i+5]<<16;
		W[i] |= (uint64_t)buf[8*i+6]<<8;
		W[i] |= buf[8*i+7];
	}
	for (; i < 80; i++)
		W[i] = R1(W[i-2]) + W[i-7] + R0(W[i-15]) + W[i-16];
	a = s->h[0];
	b = s->h[1];
	c = s->h[2];
	d = s->h[3];
	e = s->h[4];
	f = s->h[5];
	g = s->h[6];
	h = s->h[7];
	for (i = 0; i < 80; i++) {
		t1 = h + S1(e) + Ch(e,f,g) + K[i] + W[i];
		t2 = S0(a) + Maj(a,b,c);
		h = g;
		g = f;
		f = e;
		e = d + t1;
		d = c;
		c = b;
		b = a;
		a = t1 + t2;
	}
	s->h[0] += a;
	s->h[1] += b;
	s->h[2] += c;
	s->h[3] += d;
	s->h[4] += e;
	s->h[5] += f;
	s->h[6] += g;
	s->h[7] += h;
}

static void pad(struct sha512 *s)
{
	unsigned r = s->len % 128;

	s->buf[r++] = 0x80;
	if (r > 112) {
		memset(s->buf + r, 0, 128 - r);
		r = 0;
		processblock(s, s->buf);
	}
	memset(s->buf + r, 0, 120 - r);
	s->len *= 8;
	s->buf[120] = s->len >> 56;
	s->buf[121] = s->len >> 48;
	s->buf[122] = s->len >> 40;
	s->buf[123] = s->len >> 32;
	s->buf[124] = s->len >> 24;
	s->buf[125] = s->len >> 16;
	s->buf[126] = s->len >> 8;
	s->buf[127] = s->len;
	processblock(s, s->buf);
}

static void sha512_init(struct sha512 *s)
{
	s->len = 0;
	s->h[0] = 0x6a09e667f3bcc908ULL;
	s->h[1] = 0xbb67ae8584caa73bULL;
	s->h[2] = 0x3c6ef372fe94f82bULL;
	s->h[3] = 0xa54ff53a5f1d36f1ULL;
	s->h[4] = 0x510e527fade682d1ULL;
	s->h[5] = 0x9b05688c2b3e6c1fULL;
	s->h[6] = 0x1f83d9abfb41bd6bULL;
	s->h[7] = 0x5be0cd19137e2179ULL;
}

static void sha512_sum(struct sha512 *s, uint8_t md[20])
{
	int i;

	pad(s);
	for (i = 0; i < 8; i++) {
		md[8*i] = s->h[i] >> 56;
		md[8*i+1] = s->h[i] >> 48;
		md[8*i+2] = s->h[i] >> 40;
		md[8*i+3] = s->h[i] >> 32;
		md[8*i+4] = s->h[i] >> 24;
		md[8*i+5] = s->h[i] >> 16;
		md[8*i+6] = s->h[i] >> 8;
		md[8*i+7] = s->h[i];
	}
}

static void sha512_update(struct sha512 *s, const void *m, unsigned long len)
{
	const uint8_t *p = m;
	unsigned r = s->len % 128;

	s->len += len;
	if (r) {
		if (len < 128 - r) {
			memcpy(s->buf + r, p, len);
			return;
		}
		memcpy(s->buf + r, p, 128 - r);
		len -= 128 - r;
		p += 128 - r;
		processblock(s, s->buf);
	}
	for (; len >= 128; len -= 128, p += 128)
		processblock(s, p);
	memcpy(s->buf, p, len);
}

static unsigned char b64[] =
"./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";

static char *to64(char *s, unsigned int u, int n)
{
	while (--n >= 0) {
		*s++ = b64[u % 64];
		u /= 64;
	}
	return s;
}

/* key limit is not part of the original design, added for DoS protection */
#define KEY_MAX 256
#define SALT_MAX 16
#define ROUNDS_DEFAULT 5000
#define ROUNDS_MIN 1000
#define ROUNDS_MAX 999999999

/* hash n bytes of the repeated md message digest */
static void hashmd(struct sha512 *s, unsigned int n, const void *md)
{
	unsigned int i;

	for (i = n; i > 64; i -= 64)
		sha512_update(s, md, 64);
	sha512_update(s, md, i);
}

static char *sha512crypt(const char *key, const char *setting, char *output)
{
	struct sha512 ctx;
	unsigned char md[64], kmd[64], smd[64];
	unsigned int i, r, klen, slen;
	char rounds[20] = "";
	const char *salt;
	char *p;

	/* reject large keys */
	for (i = 0; i <= KEY_MAX && key[i]; i++);
	if (i > KEY_MAX)
		return 0;
	klen = i;

	/* setting: $6$rounds=n$salt$ (rounds=n$ and closing $ are optional) */
	if (strncmp(setting, "$6$", 3) != 0)
		return 0;
	salt = setting + 3;

	r = ROUNDS_DEFAULT;
	if (strncmp(salt, "rounds=", sizeof "rounds=" - 1) == 0) {
		unsigned long u;
		char *end;

		/*
		 * this is a deviation from the reference:
		 * bad rounds setting is rejected if it is
		 * - empty
		 * - unterminated (missing '$')
		 * - not a decimal number
		 * - negative
		 * - whitespace prefixed or has sign
		 * - very long (>=20 digits)
		 * the reference implementation treats these bad
		 * rounds as part of the salt or parse them with
		 * strtoul semantics which may cause problems
		 */
		salt += sizeof "rounds=" - 1;
		for (i = 0; i < 20 && isdigit(salt[i]); i++);
		if (i == 0 || salt[i] != '$')
			return 0;
		u = strtoul(salt, &end, 10);
		if (end != salt + i)
			/* cannot happen unless strtoul is broken */
			return 0;
		salt += i + 1;
		if (u < ROUNDS_MIN)
			r = ROUNDS_MIN;
		else if (u > ROUNDS_MAX)
			r = ROUNDS_MAX;
		else
			r = u;
		/* needed when rounds is zero prefixed or out of bounds */
		sprintf(rounds, "rounds=%u$", r);
	}

	for (i = 0; i < SALT_MAX && salt[i] && salt[i] != '$'; i++)
		/* reject characters that interfere with /etc/shadow parsing */
		if (salt[i] == '\n' || salt[i] == ':')
			return 0;
	slen = i;

	/* B = sha(key salt key) */
	sha512_init(&ctx);
	sha512_update(&ctx, key, klen);
	sha512_update(&ctx, salt, slen);
	sha512_update(&ctx, key, klen);
	sha512_sum(&ctx, md);

	/* A = sha(key salt repeat-B alternate-B-key) */
	sha512_init(&ctx);
	sha512_update(&ctx, key, klen);
	sha512_update(&ctx, salt, slen);
	hashmd(&ctx, klen, md);
	for (i = klen; i > 0; i >>= 1)
		if (i & 1)
			sha512_update(&ctx, md, sizeof md);
		else
			sha512_update(&ctx, key, klen);
	sha512_sum(&ctx, md);

	/* DP = sha(repeat-key), this step takes O(klen^2) time */
	sha512_init(&ctx);
	for (i = 0; i < klen; i++)
		sha512_update(&ctx, key, klen);
	sha512_sum(&ctx, kmd);

	/* DS = sha(repeat-salt) */
	sha512_init(&ctx);
	for (i = 0; i < 16 + md[0]; i++)
		sha512_update(&ctx, salt, slen);
	sha512_sum(&ctx, smd);

	/* iterate A = f(A,DP,DS), this step takes O(rounds*klen) time */
	for (i = 0; i < r; i++) {
		sha512_init(&ctx);
		if (i % 2)
			hashmd(&ctx, klen, kmd);
		else
			sha512_update(&ctx, md, sizeof md);
		if (i % 3)
			sha512_update(&ctx, smd, slen);
		if (i % 7)
			hashmd(&ctx, klen, kmd);
		if (i % 2)
			sha512_update(&ctx, md, sizeof md);
		else
			hashmd(&ctx, klen, kmd);
		sha512_sum(&ctx, md);
	}

	/* output is $6$rounds=n$salt$hash */
	p = output;
	p += sprintf(p, "$6$%s%.*s$", rounds, slen, salt);
	p = to64(p, (md[0]<<16)|(md[21]<<8)|md[42], 4);
	p = to64(p, (md[22]<<16)|(md[43]<<8)|md[1], 4);
	p = to64(p, (md[44]<<16)|(md[2]<<8)|md[23], 4);
	p = to64(p, (md[3]<<16)|(md[24]<<8)|md[45], 4);
	p = to64(p, (md[25]<<16)|(md[46]<<8)|md[4], 4);
	p = to64(p, (md[47]<<16)|(md[5]<<8)|md[26], 4);
	p = to64(p, (md[6]<<16)|(md[27]<<8)|md[48], 4);
	p = to64(p, (md[28]<<16)|(md[49]<<8)|md[7], 4);
	p = to64(p, (md[50]<<16)|(md[8]<<8)|md[29], 4);
	p = to64(p, (md[9]<<16)|(md[30]<<8)|md[51], 4);
	p = to64(p, (md[31]<<16)|(md[52]<<8)|md[10], 4);
	p = to64(p, (md[53]<<16)|(md[11]<<8)|md[32], 4);
	p = to64(p, (md[12]<<16)|(md[33]<<8)|md[54], 4);
	p = to64(p, (md[34]<<16)|(md[55]<<8)|md[13], 4);
	p = to64(p, (md[56]<<16)|(md[14]<<8)|md[35], 4);
	p = to64(p, (md[15]<<16)|(md[36]<<8)|md[57], 4);
	p = to64(p, (md[37]<<16)|(md[58]<<8)|md[16], 4);
	p = to64(p, (md[59]<<16)|(md[17]<<8)|md[38], 4);
	p = to64(p, (md[18]<<16)|(md[39]<<8)|md[60], 4);
	p = to64(p, (md[40]<<16)|(md[61]<<8)|md[19], 4);
	p = to64(p, (md[62]<<16)|(md[20]<<8)|md[41], 4);
	p = to64(p, md[63], 2);
	*p = 0;
	return output;
}

char *__crypt_sha512(const char *key, const char *setting, char *output)
{
	static const char testkey[] = "Xy01@#\x01\x02\x80\x7f\xff\r\n\x81\t !";
	static const char testsetting[] = "$6$rounds=1234$abc0123456789$";
	static const char testhash[] = "$6$rounds=1234$abc0123456789$BCpt8zLrc/RcyuXmCDOE1ALqMXB2MH6n1g891HhFj8.w7LxGv.FTkqq6Vxc/km3Y0jE0j24jY5PIv/oOu6reg1";
	char testbuf[128];
	char *p, *q;

	p = sha512crypt(key, setting, output);
	/* self test and stack cleanup */
	q = sha512crypt(testkey, testsetting, testbuf);
	if (!p || q != testbuf || memcmp(testbuf, testhash, sizeof testhash))
		return "*";
	return p;
}

Re: Help-wanted tasks for musl

[Rich Felker]

[-- Attachment #1: Type: text/plain, Size: 759 bytes --]

On Wed, Aug 29, 2012 at 01:35:06AM +0200, Szabolcs Nagy wrote:
> * Szabolcs Nagy <nsz@port70.net> [2012-08-28 22:09:42 +0200]:
> > * Rich Felker <dalias@aerifal.cx> [2012-08-19 22:12:23 -0400]:
> > > On Mon, Aug 20, 2012 at 03:58:54AM +0200, Szabolcs Nagy wrote:
> > > > sha and md5 crypt does not decode the salt
> > > > it is directly passed to a hash function
> > > 
> > > Ah, that makes it uglier then, because presumably some of these
> > > malformed things you mentioned are "valid" salt.
> > > 
> > 
> > i modified my sha crypt implementation so it is very strict
> > about the rounds= part of the salt and checks for key length
> > 
> 
> removed the unrolling, modified key limit and added salt check:

see the attached for my proposed changes.

rich

[-- Attachment #2: crypt_sha256.c --]
[-- Type: text/plain, Size: 8584 bytes --]

/*
 * public domain sha256 crypt implementation
 *
 * original sha crypt design: http://people.redhat.com/drepper/SHA-crypt.txt
 * in this implementation at least 32bit int is assumed,
 * key length is limited, the $5$ prefix is mandatory, '\n' and ':' is rejected
 * in the salt and rounds= setting must contain a valid iteration count,
 * on error "*" is returned.
 */
#include <ctype.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <stdint.h>

/* public domain sha256 implementation based on fips180-3 */

struct sha256 {
	uint64_t len;    /* processed message length */
	uint32_t h[8];   /* hash state */
	uint8_t buf[64]; /* message block buffer */
};

static uint32_t ror(uint32_t n, int k) { return (n >> k) | (n << (32-k)); }
#define Ch(x,y,z)  (z ^ (x & (y ^ z)))
#define Maj(x,y,z) ((x & y) | (z & (x | y)))
#define S0(x)      (ror(x,2) ^ ror(x,13) ^ ror(x,22))
#define S1(x)      (ror(x,6) ^ ror(x,11) ^ ror(x,25))
#define R0(x)      (ror(x,7) ^ ror(x,18) ^ (x>>3))
#define R1(x)      (ror(x,17) ^ ror(x,19) ^ (x>>10))

static const uint32_t K[64] = {
0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2
};

static void processblock(struct sha256 *s, const uint8_t *buf)
{
	uint32_t W[64], t1, t2, a, b, c, d, e, f, g, h;
	int i;

	for (i = 0; i < 16; i++) {
		W[i] = (uint32_t)buf[4*i]<<24;
		W[i] |= (uint32_t)buf[4*i+1]<<16;
		W[i] |= (uint32_t)buf[4*i+2]<<8;
		W[i] |= buf[4*i+3];
	}
	for (; i < 64; i++)
		W[i] = R1(W[i-2]) + W[i-7] + R0(W[i-15]) + W[i-16];
	a = s->h[0];
	b = s->h[1];
	c = s->h[2];
	d = s->h[3];
	e = s->h[4];
	f = s->h[5];
	g = s->h[6];
	h = s->h[7];
	for (i = 0; i < 64; i++) {
		t1 = h + S1(e) + Ch(e,f,g) + K[i] + W[i];
		t2 = S0(a) + Maj(a,b,c);
		h = g;
		g = f;
		f = e;
		e = d + t1;
		d = c;
		c = b;
		b = a;
		a = t1 + t2;
	}
	s->h[0] += a;
	s->h[1] += b;
	s->h[2] += c;
	s->h[3] += d;
	s->h[4] += e;
	s->h[5] += f;
	s->h[6] += g;
	s->h[7] += h;
}

static void pad(struct sha256 *s)
{
	unsigned r = s->len % 64;

	s->buf[r++] = 0x80;
	if (r > 56) {
		memset(s->buf + r, 0, 64 - r);
		r = 0;
		processblock(s, s->buf);
	}
	memset(s->buf + r, 0, 56 - r);
	s->len *= 8;
	s->buf[56] = s->len >> 56;
	s->buf[57] = s->len >> 48;
	s->buf[58] = s->len >> 40;
	s->buf[59] = s->len >> 32;
	s->buf[60] = s->len >> 24;
	s->buf[61] = s->len >> 16;
	s->buf[62] = s->len >> 8;
	s->buf[63] = s->len;
	processblock(s, s->buf);
}

void sha256_init(struct sha256 *s)
{
	s->len = 0;
	s->h[0] = 0x6a09e667;
	s->h[1] = 0xbb67ae85;
	s->h[2] = 0x3c6ef372;
	s->h[3] = 0xa54ff53a;
	s->h[4] = 0x510e527f;
	s->h[5] = 0x9b05688c;
	s->h[6] = 0x1f83d9ab;
	s->h[7] = 0x5be0cd19;
}

void sha256_sum(struct sha256 *s, uint8_t md[20])
{
	int i;

	pad(s);
	for (i = 0; i < 8; i++) {
		md[4*i] = s->h[i] >> 24;
		md[4*i+1] = s->h[i] >> 16;
		md[4*i+2] = s->h[i] >> 8;
		md[4*i+3] = s->h[i];
	}
}

void sha256_update(struct sha256 *s, const void *m, unsigned long len)
{
	const uint8_t *p = m;
	unsigned r = s->len % 64;

	s->len += len;
	if (r) {
		if (len < 64 - r) {
			memcpy(s->buf + r, p, len);
			return;
		}
		memcpy(s->buf + r, p, 64 - r);
		len -= 64 - r;
		p += 64 - r;
		processblock(s, s->buf);
	}
	for (; len >= 64; len -= 64, p += 64)
		processblock(s, p);
	memcpy(s->buf, p, len);
}

static unsigned char b64[] =
"./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";

static char *to64(char *s, unsigned int u, int n)
{
	while (--n >= 0) {
		*s++ = b64[u % 64];
		u /= 64;
	}
	return s;
}

/* key limit is not part of the original design, added for DoS protection */
#define KEY_MAX 256
#define SALT_MAX 16
#define ROUNDS_DEFAULT 5000
#define ROUNDS_MIN 1000
#define ROUNDS_MAX 999999

/* hash n bytes of the repeated md message digest */
static void hashmd(struct sha256 *s, unsigned int n, const void *md)
{
	unsigned int i;

	for (i = n; i > 32; i -= 32)
		sha256_update(s, md, 32);
	sha256_update(s, md, i);
}

static char *sha256crypt(const char *key, const char *setting, char *output)
{
	struct sha256 ctx;
	unsigned char md[32], kmd[32], smd[32];
	unsigned int i, r, klen, slen;
	char rounds[20] = "";
	const char *salt;
	char *p;

	/* reject large keys */
	klen = strnlen(key, KEY_MAX+1);
	if (klen > KEY_MAX)
		return 0;

	/* setting: $5$rounds=n$salt$ (rounds=n$ and closing $ are optional) */
	if (strncmp(setting, "$5$", 3) != 0)
		return 0;
	salt = setting + 3;

	r = ROUNDS_DEFAULT;
	if (strncmp(salt, "rounds=", sizeof "rounds=" - 1) == 0) {
		unsigned long u;
		char *end;

		/*
		 * this is a deviation from the reference:
		 * bad rounds setting is rejected if it is
		 * - empty
		 * - unterminated (missing '$')
		 * - begins with anything but a decimal digit
		 * the reference implementation treats these bad
		 * rounds as part of the salt or parse them with
		 * strtoul semantics which may cause problems
		 * including non-portable hashes that depend on
		 * the host's value of ULONG_MAX.
		 */
		salt += sizeof "rounds=" - 1;
		if (!isdigit(*salt))
			return 0;
		u = strtoul(salt, &end, 10);
		if (*end != '$')
			return 0;
		salt = end+1;
		if (u < ROUNDS_MIN)
			r = ROUNDS_MIN;
		else if (u > ROUNDS_MAX)
			r = ROUNDS_MAX;
		else
			r = u;
		/* needed when rounds is zero prefixed or out of bounds */
		sprintf(rounds, "rounds=%u$", r);
	}

	for (i = 0; i < SALT_MAX && salt[i] && salt[i] != '$'; i++)
		/* reject characters that interfere with /etc/shadow parsing */
		if (salt[i] == '\n' || salt[i] == ':')
			return 0;
	slen = i;

	/* B = sha(key salt key) */
	sha256_init(&ctx);
	sha256_update(&ctx, key, klen);
	sha256_update(&ctx, salt, slen);
	sha256_update(&ctx, key, klen);
	sha256_sum(&ctx, md);

	/* A = sha(key salt repeat-B alternate-B-key) */
	sha256_init(&ctx);
	sha256_update(&ctx, key, klen);
	sha256_update(&ctx, salt, slen);
	hashmd(&ctx, klen, md);
	for (i = klen; i > 0; i >>= 1)
		if (i & 1)
			sha256_update(&ctx, md, sizeof md);
		else
			sha256_update(&ctx, key, klen);
	sha256_sum(&ctx, md);

	/* DP = sha(repeat-key), this step takes O(klen^2) time */
	sha256_init(&ctx);
	for (i = 0; i < klen; i++)
		sha256_update(&ctx, key, klen);
	sha256_sum(&ctx, kmd);

	/* DS = sha(repeat-salt) */
	sha256_init(&ctx);
	for (i = 0; i < 16 + md[0]; i++)
		sha256_update(&ctx, salt, slen);
	sha256_sum(&ctx, smd);

	/* iterate A = f(A,DP,DS), this step takes O(rounds*klen) time */
	for (i = 0; i < r; i++) {
		sha256_init(&ctx);
		if (i % 2)
			hashmd(&ctx, klen, kmd);
		else
			sha256_update(&ctx, md, sizeof md);
		if (i % 3)
			sha256_update(&ctx, smd, slen);
		if (i % 7)
			hashmd(&ctx, klen, kmd);
		if (i % 2)
			sha256_update(&ctx, md, sizeof md);
		else
			hashmd(&ctx, klen, kmd);
		sha256_sum(&ctx, md);
	}

	/* output is $5$rounds=n$salt$hash */
	p = output;
	p += sprintf(p, "$5$%s%.*s$", rounds, slen, salt);
	p = to64(p, (md[0]<<16)|(md[10]<<8)|md[20], 4);
	p = to64(p, (md[21]<<16)|(md[1]<<8)|md[11], 4);
	p = to64(p, (md[12]<<16)|(md[22]<<8)|md[2], 4);
	p = to64(p, (md[3]<<16)|(md[13]<<8)|md[23], 4);
	p = to64(p, (md[24]<<16)|(md[4]<<8)|md[14], 4);
	p = to64(p, (md[15]<<16)|(md[25]<<8)|md[5], 4);
	p = to64(p, (md[6]<<16)|(md[16]<<8)|md[26], 4);
	p = to64(p, (md[27]<<16)|(md[7]<<8)|md[17], 4);
	p = to64(p, (md[18]<<16)|(md[28]<<8)|md[8], 4);
	p = to64(p, (md[9]<<16)|(md[19]<<8)|md[29], 4);
	p = to64(p, (md[31]<<8)|md[30], 3);
	*p = 0;
	return output;
}

char *__crypt_sha256(const char *key, const char *setting, char *output)
{
	static const char testkey[] = "Xy01@#\x01\x02\x80\x7f\xff\r\n\x81\t !";
	static const char testsetting[] = "$5$rounds=1234$abc0123456789$";
	static const char testhash[] = "$5$rounds=1234$abc0123456789$3VfDjPt05VHFn47C/ojFZ6KRPYrOjj1lLbH.dkF3bZ6";
	char testbuf[128];
	char *p, *q;

	p = sha256crypt(key, setting, output);
	/* self test and stack cleanup */
	q = sha256crypt(testkey, testsetting, testbuf);
	if (!p || q != testbuf || memcmp(testbuf, testhash, sizeof testhash))
		return "*";
	return p;
}

Re: Help-wanted tasks for musl

[Szabolcs Nagy]

* Rich Felker <dalias@aerifal.cx> [2012-08-29 10:30:12 -0400]:
> see the attached for my proposed changes.
> 

looks ok

> /* key limit is not part of the original design, added for DoS protection */
> #define KEY_MAX 256
> #define SALT_MAX 16
> #define ROUNDS_DEFAULT 5000
> #define ROUNDS_MIN 1000
> #define ROUNDS_MAX 999999
> 

i'd add a comment like

/* max rounds limit is lower than in the reference */

Re: Help-wanted tasks for musl

[Rich Felker]

On Wed, Aug 29, 2012 at 05:14:59PM +0200, Szabolcs Nagy wrote:
> * Rich Felker <dalias@aerifal.cx> [2012-08-29 10:30:12 -0400]:
> > see the attached for my proposed changes.
> > 
> 
> looks ok
> 
> > /* key limit is not part of the original design, added for DoS protection */
> > #define KEY_MAX 256
> > #define SALT_MAX 16
> > #define ROUNDS_DEFAULT 5000
> > #define ROUNDS_MIN 1000
> > #define ROUNDS_MAX 999999
> > 
> 
> i'd add a comment like
> 
> /* max rounds limit is lower than in the reference */

Committed. I also put strict rounds count checks in place for the
existing hashes. Previously the only limit was on blowfish where the
limit kept the runtime down to minutes instead of months/years, but
that was of little practical benefit. Anyone who thinks the limits are
too low/too high/whatever is welcome to bikeshed this...

Rich

Re: Help-wanted tasks for musl

[Szabolcs Nagy]

* Rich Felker <dalias@aerifal.cx> [2012-08-29 13:01:32 -0400]:
> Committed. I also put strict rounds count checks in place for the
> existing hashes. Previously the only limit was on blowfish where the
> limit kept the runtime down to minutes instead of months/years, but
> that was of little practical benefit. Anyone who thinks the limits are
> too low/too high/whatever is welcome to bikeshed this...
> 

i think the current setting is too low :)
i'd use the same setting for both
(sha512 can be significantly faster on 64bit than on 32bit)

the limit need not be more than 1M but should be at least 100k
(one can easily wait these out on a fast machine)

a quick search on the web found several
cases where sha crypt is promoted with
high rounds:

$6$rounds=65536
https://wiki.archlinux.org/index.php/SHA_password_hashes

$5$rounds=73500
http://security.stackexchange.com/questions/15083/is-there-repetition-in-the-solaris-11-hash-routine-can-i-add-some

$5$rounds=80000 (this is the default in passlib!)
http://packages.python.org/passlib/lib/passlib.context-tutorial.html

$6$rounds=100000
http://lwn.net/Articles/489234

$6$rounds=1000000 (!!)
http://twerner.blogspot.hu/2010/01/improving-password-security-in-debian.html

bug:
somehow i forgot to add 'static' to sha256
hash functions (sha256_init, sha256_update,
sha256_sum) so they are visible