Bug 31440 - htpasswd salt generation weakness
htpasswd salt generation weakness
Status: RESOLVED FIXED
Product: Apache httpd-2
Classification: Unclassified
Component: support
2.0.51
PC Linux
: P3 normal (vote)
: ---
Assigned To: Apache HTTPD Bugs Mailing List
: PatchAvailable
Depends on:
Blocks:
  Show dependency tree
 
Reported: 2004-09-27 18:46 UTC by Andreas Krennmair
Modified: 2009-08-27 10:49 UTC (History)
1 user (show)



Attachments
fix to the htpasswd salt generation weakness (823 bytes, patch)
2004-09-27 18:48 UTC, Andreas Krennmair
Details | Diff
patch against httpd-2.2.8 to resolve weak PRNG seeding (3.39 KB, patch)
2008-01-25 10:10 UTC, Peter Watkins
Details | Diff
patch for httpd 1.3.39 (3.47 KB, patch)
2008-01-25 19:56 UTC, Peter Watkins
Details | Diff
Another similar bug discovered in htdbm.c (1.05 KB, patch)
2009-08-27 10:42 UTC, Boya Sun
Details | Diff
Resubmitted: Another similar bug discovered in htdbm.c (892 bytes, patch)
2009-08-27 10:47 UTC, Boya Sun
Details | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Andreas Krennmair 2004-09-27 18:46:45 UTC
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/
$
Comment 1 Andreas Krennmair 2004-09-27 18:48:45 UTC
Created attachment 12871 [details]
fix to the htpasswd salt generation weakness
Comment 2 Andreas Krennmair 2004-09-27 18:49:51 UTC
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/
$
Comment 3 Peter Watkins 2008-01-25 10:10:34 UTC
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
Comment 4 Peter Watkins 2008-01-25 19:56:56 UTC
Created attachment 21433 [details]
patch for httpd 1.3.39

same idea, but for the 1.3.x codebase
Comment 5 Andreas Krennmair 2008-01-27 15:05:09 UTC
> 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.
Comment 6 Peter Watkins 2008-01-28 11:46:04 UTC
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.

Comment 7 Andreas Krennmair 2008-01-28 11:59:50 UTC
You are right, I stand corrected. Now if only somebody could apply the patches
to SVN trunk...
Comment 8 Paul Querna 2008-02-19 08:28:24 UTC
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
Comment 9 Paul Querna 2008-02-19 09:09:18 UTC
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

Comment 10 Ruediger Pluem 2008-05-30 14:49:25 UTC
Proposed for backport to 2.2.x as r661890
(http://svn.apache.org/viewvc?view=rev&revision=661890)

Comment 11 Ruediger Pluem 2008-06-02 14:24:30 UTC
Backported as r662572 (http://svn.apache.org/viewvc?rev=662572&view=rev).
Comment 12 Boya Sun 2009-08-27 10:42:03 UTC
Created attachment 24178 [details]
Another similar bug discovered in htdbm.c
Comment 13 Boya Sun 2009-08-27 10:43:35 UTC
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
Comment 14 Boya Sun 2009-08-27 10:47:10 UTC
Created attachment 24179 [details]
Resubmitted: Another similar bug discovered in htdbm.c
Comment 15 Boya Sun 2009-08-27 10:49:10 UTC
(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