From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.org/gmane.linux.lib.musl.general/1779 Path: news.gmane.org!not-for-mail From: Szabolcs Nagy Newsgroups: gmane.linux.lib.musl.general Subject: Re: Help-wanted tasks for musl Date: Tue, 28 Aug 2012 22:09:42 +0200 Message-ID: <20120828200942.GF1104@port70.net> References: <20120819042611.GA8731@brightrain.aerifal.cx> <20120819114914.GD16602@port70.net> <20120819165652.GE16602@port70.net> <20120819172921.GF16602@port70.net> <20120820005128.GB27715@brightrain.aerifal.cx> <20120820013502.GG16602@port70.net> <20120820013950.GC27715@brightrain.aerifal.cx> <20120820015854.GH16602@port70.net> <20120820021223.GE27715@brightrain.aerifal.cx> Reply-To: musl@lists.openwall.com NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="6c2NcOVqGQ03X4Wi" X-Trace: ger.gmane.org 1346184599 21742 80.91.229.3 (28 Aug 2012 20:09:59 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Tue, 28 Aug 2012 20:09:59 +0000 (UTC) To: musl@lists.openwall.com Original-X-From: musl-return-1780-gllmg-musl=m.gmane.org@lists.openwall.com Tue Aug 28 22:10:00 2012 Return-path: Envelope-to: gllmg-musl@plane.gmane.org Original-Received: from mother.openwall.net ([195.42.179.200]) by plane.gmane.org with smtp (Exim 4.69) (envelope-from ) id 1T6S6o-0005FR-4t for gllmg-musl@plane.gmane.org; Tue, 28 Aug 2012 22:09:58 +0200 Original-Received: (qmail 22285 invoked by uid 550); 28 Aug 2012 20:09:55 -0000 Mailing-List: contact musl-help@lists.openwall.com; run by ezmlm Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: Original-Received: (qmail 22277 invoked from network); 28 Aug 2012 20:09:55 -0000 Content-Disposition: inline In-Reply-To: <20120820021223.GE27715@brightrain.aerifal.cx> User-Agent: Mutt/1.5.21 (2010-09-15) Xref: news.gmane.org gmane.linux.lib.musl.general:1779 Archived-At: --6c2NcOVqGQ03X4Wi Content-Type: text/plain; charset=us-ascii Content-Disposition: inline * Rich Felker [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) --6c2NcOVqGQ03X4Wi Content-Type: text/x-csrc; charset=us-ascii Content-Disposition: attachment; filename="crypt_sha256.c" /* * 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 #include #include #include #include /* 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; } --6c2NcOVqGQ03X4Wi Content-Type: text/x-csrc; charset=us-ascii Content-Disposition: attachment; filename="crypt_sha256_test.c" #include #include #include 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; } --6c2NcOVqGQ03X4Wi--