* Help-wanted tasks for musl @ 2012-08-19 4:26 Rich Felker 2012-08-19 8:10 ` idunham ` (2 more replies) 0 siblings, 3 replies; 21+ messages in thread From: Rich Felker @ 2012-08-19 4:26 UTC (permalink / raw) To: musl 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. ^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: Help-wanted tasks for musl 2012-08-19 4:26 Help-wanted tasks for musl Rich Felker @ 2012-08-19 8:10 ` idunham 2012-08-19 16:18 ` William Haddon 2012-08-19 8:44 ` boris brezillon 2012-08-19 11:49 ` Szabolcs Nagy 2 siblings, 1 reply; 21+ messages in thread From: idunham @ 2012-08-19 8:10 UTC (permalink / raw) To: musl > 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? ^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: Help-wanted tasks for musl 2012-08-19 8:10 ` idunham @ 2012-08-19 16:18 ` William Haddon 0 siblings, 0 replies; 21+ messages in thread From: William Haddon @ 2012-08-19 16:18 UTC (permalink / raw) To: musl 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 ^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: Help-wanted tasks for musl 2012-08-19 4:26 Help-wanted tasks for musl Rich Felker 2012-08-19 8:10 ` idunham @ 2012-08-19 8:44 ` boris brezillon 2012-08-19 11:49 ` Szabolcs Nagy 2 siblings, 0 replies; 21+ messages in thread From: boris brezillon @ 2012-08-19 8:44 UTC (permalink / raw) To: musl 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. ^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: Help-wanted tasks for musl 2012-08-19 4:26 Help-wanted tasks for musl Rich Felker 2012-08-19 8:10 ` idunham 2012-08-19 8:44 ` boris brezillon @ 2012-08-19 11:49 ` Szabolcs Nagy 2012-08-19 16:56 ` Szabolcs Nagy 2 siblings, 1 reply; 21+ messages in thread From: Szabolcs Nagy @ 2012-08-19 11:49 UTC (permalink / raw) To: musl * 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 ^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: Help-wanted tasks for musl 2012-08-19 11:49 ` Szabolcs Nagy @ 2012-08-19 16:56 ` Szabolcs Nagy 2012-08-19 17:29 ` Szabolcs Nagy 0 siblings, 1 reply; 21+ messages in thread From: Szabolcs Nagy @ 2012-08-19 16:56 UTC (permalink / raw) To: musl * 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 ^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: Help-wanted tasks for musl 2012-08-19 16:56 ` Szabolcs Nagy @ 2012-08-19 17:29 ` Szabolcs Nagy 2012-08-20 0:51 ` Rich Felker 0 siblings, 1 reply; 21+ messages in thread From: Szabolcs Nagy @ 2012-08-19 17:29 UTC (permalink / raw) To: musl * 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 ^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: Help-wanted tasks for musl 2012-08-19 17:29 ` Szabolcs Nagy @ 2012-08-20 0:51 ` Rich Felker 2012-08-20 1:35 ` Szabolcs Nagy 0 siblings, 1 reply; 21+ messages in thread From: Rich Felker @ 2012-08-20 0:51 UTC (permalink / raw) To: musl 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 ^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: Help-wanted tasks for musl 2012-08-20 0:51 ` Rich Felker @ 2012-08-20 1:35 ` Szabolcs Nagy 2012-08-20 1:39 ` Rich Felker 0 siblings, 1 reply; 21+ messages in thread From: Szabolcs Nagy @ 2012-08-20 1:35 UTC (permalink / raw) To: musl * 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) ^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: Help-wanted tasks for musl 2012-08-20 1:35 ` Szabolcs Nagy @ 2012-08-20 1:39 ` Rich Felker 2012-08-20 1:58 ` Szabolcs Nagy 0 siblings, 1 reply; 21+ messages in thread From: Rich Felker @ 2012-08-20 1:39 UTC (permalink / raw) To: musl 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 ^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: Help-wanted tasks for musl 2012-08-20 1:39 ` Rich Felker @ 2012-08-20 1:58 ` Szabolcs Nagy 2012-08-20 2:12 ` Rich Felker 0 siblings, 1 reply; 21+ messages in thread From: Szabolcs Nagy @ 2012-08-20 1:58 UTC (permalink / raw) To: musl * 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 ^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: Help-wanted tasks for musl 2012-08-20 1:58 ` Szabolcs Nagy @ 2012-08-20 2:12 ` Rich Felker 2012-08-28 20:09 ` Szabolcs Nagy 0 siblings, 1 reply; 21+ messages in thread From: Rich Felker @ 2012-08-20 2:12 UTC (permalink / raw) To: musl 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 ^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: Help-wanted tasks for musl 2012-08-20 2:12 ` Rich Felker @ 2012-08-28 20:09 ` Szabolcs Nagy 2012-08-28 23:35 ` Szabolcs Nagy 0 siblings, 1 reply; 21+ messages in thread From: Szabolcs Nagy @ 2012-08-28 20:09 UTC (permalink / raw) To: musl [-- 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; } ^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: Help-wanted tasks for musl 2012-08-28 20:09 ` Szabolcs Nagy @ 2012-08-28 23:35 ` Szabolcs Nagy 2012-08-29 0:15 ` Szabolcs Nagy 2012-08-29 14:30 ` Rich Felker 0 siblings, 2 replies; 21+ messages in thread From: Szabolcs Nagy @ 2012-08-28 23:35 UTC (permalink / raw) To: musl [-- 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; } ^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: Help-wanted tasks for musl 2012-08-28 23:35 ` Szabolcs Nagy @ 2012-08-29 0:15 ` Szabolcs Nagy 2012-08-29 14:30 ` Rich Felker 1 sibling, 0 replies; 21+ messages in thread From: Szabolcs Nagy @ 2012-08-29 0:15 UTC (permalink / raw) To: musl [-- 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; } ^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: Help-wanted tasks for musl 2012-08-28 23:35 ` Szabolcs Nagy 2012-08-29 0:15 ` Szabolcs Nagy @ 2012-08-29 14:30 ` Rich Felker 2012-08-29 15:14 ` Szabolcs Nagy 1 sibling, 1 reply; 21+ messages in thread From: Rich Felker @ 2012-08-29 14:30 UTC (permalink / raw) To: musl [-- 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; } ^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: Help-wanted tasks for musl 2012-08-29 14:30 ` Rich Felker @ 2012-08-29 15:14 ` Szabolcs Nagy 2012-08-29 17:01 ` Rich Felker 0 siblings, 1 reply; 21+ messages in thread From: Szabolcs Nagy @ 2012-08-29 15:14 UTC (permalink / raw) To: musl * 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 */ ^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: Help-wanted tasks for musl 2012-08-29 15:14 ` Szabolcs Nagy @ 2012-08-29 17:01 ` Rich Felker 2012-08-30 8:40 ` Szabolcs Nagy 0 siblings, 1 reply; 21+ messages in thread From: Rich Felker @ 2012-08-29 17:01 UTC (permalink / raw) To: musl 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 ^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: Help-wanted tasks for musl 2012-08-29 17:01 ` Rich Felker @ 2012-08-30 8:40 ` Szabolcs Nagy 0 siblings, 0 replies; 21+ messages in thread From: Szabolcs Nagy @ 2012-08-30 8:40 UTC (permalink / raw) To: musl * 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 ^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: Help-wanted tasks for musl @ 2012-08-19 21:46 idunham 2012-08-19 22:19 ` Gregor Richards 0 siblings, 1 reply; 21+ messages in thread From: idunham @ 2012-08-19 21:46 UTC (permalink / raw) To: musl >> 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. ^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: Help-wanted tasks for musl 2012-08-19 21:46 idunham @ 2012-08-19 22:19 ` Gregor Richards 0 siblings, 0 replies; 21+ messages in thread From: Gregor Richards @ 2012-08-19 22:19 UTC (permalink / raw) To: musl 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. > > > > ^ permalink raw reply [flat|nested] 21+ messages in thread
end of thread, other threads:[~2012-08-30 8:40 UTC | newest] Thread overview: 21+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2012-08-19 4:26 Help-wanted tasks for musl Rich Felker 2012-08-19 8:10 ` idunham 2012-08-19 16:18 ` William Haddon 2012-08-19 8:44 ` boris brezillon 2012-08-19 11:49 ` Szabolcs Nagy 2012-08-19 16:56 ` Szabolcs Nagy 2012-08-19 17:29 ` Szabolcs Nagy 2012-08-20 0:51 ` Rich Felker 2012-08-20 1:35 ` Szabolcs Nagy 2012-08-20 1:39 ` Rich Felker 2012-08-20 1:58 ` Szabolcs Nagy 2012-08-20 2:12 ` Rich Felker 2012-08-28 20:09 ` Szabolcs Nagy 2012-08-28 23:35 ` Szabolcs Nagy 2012-08-29 0:15 ` Szabolcs Nagy 2012-08-29 14:30 ` Rich Felker 2012-08-29 15:14 ` Szabolcs Nagy 2012-08-29 17:01 ` Rich Felker 2012-08-30 8:40 ` Szabolcs Nagy 2012-08-19 21:46 idunham 2012-08-19 22:19 ` Gregor Richards
Code repositories for project(s) associated with this public inbox https://git.vuxu.org/mirror/musl/ This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for NNTP newsgroup(s).