I noticed a salt generation weakness when using htpasswd in MD5 mode on platforms where rand() returns only a 32 bit value: since the MD5 salt is 48 bits wide, the last 2 or 3 characters are always filled with '.'. $ htpasswd -m -c /tmp/htpasswdtest a New password: Re-type new password: Adding password for user a $ cat /tmp/htpasswdtest a:$apr1$sTQf/...$v6RZCfMprmLq5vMTzpwH2/ $
Created attachment 12871 [details] fix to the htpasswd salt generation weakness
This attached patch would lead to a more random MD5 salt: $ ./htpasswd -m -c /tmp/htpasswdtest2 b New password: Re-type new password: Adding password for user b $ cat /tmp/htpasswdtest2 b:$apr1$iOJN8Jax$rQLDvG0ALByOBtHgN2wk7/ $
Created attachment 21429 [details] patch against httpd-2.2.8 to resolve weak PRNG seeding Andreas, I think you're on the right track, but your patch only adds the appearance of greater randomness. The core problem here is poor seeding of the PRNG. Every salted output from htpasswd starts with using time() to feed srand(). Even with your patch, htpasswd will always use the same seed at the any given time. The most important thing that needs to change is the calls to srand(). Here's a patch that keeps your nice 48-bit padding and adds better seeding. If the user sets a RANDOM_SEED environment variable, htpasswd will use that file/device. If not, it will try to use /dev/urandom. If it cannot use /dev/urandom or the user provides an unusable file/device name, it will fall back to using time() but will print a warning to STDERR. Also (untested!) if the user is on a platform with 32-bit integers, htpasswd will re-seed the PRNG as needed, to improve the chances of a true 48-bit salt. -Peter
Created attachment 21433 [details] patch for httpd 1.3.39 same idea, but for the 1.3.x codebase
> Andreas, I think you're on the right track, but your patch only adds the > appearance of greater randomness. The core problem here is poor seeding of the > PRNG. Every salted output from htpasswd starts with using time() to feed > srand(). Even with your patch, htpasswd will always use the same seed at the > any given time. This is not a matter of randomness (or at least that was not my point), it's a matter of how the salt of the hash looks like. With the old method (which I fixed with my patch from 2004), an attacker could base a precomputation attack on the assumption that the salt only has 32 bits, even though the format would allow up to 48 bits of salt. Of course, even with 32 bits of salt, a precomputation still seems quite infeasible, but it still doesn't exhaust the possible maximum of 48 bits of salt (which obviously must have been in the mind of the original authors, otherwise they would have spread the 32 bits of rand() to 6 bytes instead of 8 bytes). And that was the original point of my patch.
Any attacker who has the same PRNG as the system where htpasswd runs would be foolish to blindly precompute even a 32 bit apr1 dictionary. 32 bits of time() represents 136 years worth of htpasswd execution with the current srand() code. In a given month, there are less than 22 bits worth of salt when using srand(time(NULL)), 17 bits in a day, 12 bits in an hour, 6 bits in a minute, 0 in a second. 29 bits is all it takes to stretch back to the beginning of Apache, before the apr1 MD5 algorithm appeared in 1.3.6 -- even with your improvement. To "fix" htpasswd so it takes full advantage of the apr1 spec's 48 bits of salt, it is necessary to fix the srand() problem, too. With your generate_salt() and my seed_prng(), htpasswd finally produces nicely random 48-bit salts for apr1.
You are right, I stand corrected. Now if only somebody could apply the patches to SVN trunk...
Using generate_salt instead of to64 makes sense..... The second patch to use better PRNG seeding, we should just use the APR APIs for randomness, apr_generate_random_bytes: http://apr.apache.org/docs/apr/1.2/group__apr__random.html
Committed improved salt string generation in r629159: http://svn.apache.org/viewvc?view=rev&revision=629159 Committed improved rand seed generation in r629164: http://svn.apache.org/viewvc?view=rev&revision=629164
Proposed for backport to 2.2.x as r661890 (http://svn.apache.org/viewvc?view=rev&revision=661890)
Backported as r662572 (http://svn.apache.org/viewvc?rev=662572&view=rev).
Created attachment 24178 [details] Another similar bug discovered in htdbm.c
Hi All, In support/htdbm.c, there are code segments which are very similar to the bug being solved in htpasswd.c, where "srand" is changed to "seed_rand". However, in the file support/htdbm.c, under "case ALG_APMD5:" and "case ALG_CRYPT:", "srand" function is still in use. But according to this bug, shouldn't "srand" be also changed to "seed_rand"? The patch is against revision 806655, but I think probably more details are needed to really fix the bug if there is really a problem. Boya
Created attachment 24179 [details] Resubmitted: Another similar bug discovered in htdbm.c
(In reply to comment #14) > Created an attachment (id=24179) [details] > Resubmitted: Another similar bug discovered in htdbm.c Sorry, submitted the wrong patch. Resubmitted the right patch