Disclaimer:

This is not the first time this issue has been discussed. Andreas
Steinmetz posted about the problem for an Apache httpd release in 2003.
  http://www.securityfocus.com/archive/1/339138
  http://www.securityfocus.com/bid/8707
Philipp Krammer reported that he notifed the vendor over five years
ago, in January 2003. http://www.securityfocus.com/archive/1/339163

What's new is
  1) The vendor has released another major version of the 
     affected software, Apache web server 2.2, with the same flaw.
  2) While no official patch is available (due to the vendor's inaction),
     an unofficial patch is now available.

-Peter
http://www.tux.org/~peterw/

Background:

Apache web server supports three different algorithms for 
"encrypted" passwords for HTTP Basic authentication:
 - Unix-style crypt() passwords: uses a 12 bit salt (4096
   possible values) and only the first 8 characters of the 
   cleartext password are used
 - SHA hashes: no salt; any given password can have only one
   {SHA} representation
 - MD5 passwords: based on the BSD MD5 crypt routine, this
   provides for 48 bits of salt, for a theoretical 281 trillion
   (281,474,976,710,656) possible representations of any password

Apache web server includes a command-line utility called 'htpasswd'
for managing the files used for HTTP Basic authentication. It can be 
used (depending on the host OS) to create encrypted passwords with 
any of the supported algorithms. 

Problem:

The htpasswd utility uses predictable salts for the salted algoritms
(Unix-style "CRYPT" and MD5). htpasswd uses the standard C rand()
function to generate "random" salts. In order to use rand(), htpasswd
seeds the random number generator with the srand() function. And that's
where the Apache developers made a critical mistake -- htpasswd 
merely uses the time of day (seconds since the Epoch, time(NULL)) to
seed the random number generator. 

As a result:
 - Salts created by htpasswd are very predictable. 
 - The universe of salts for htpasswd is far less than the MD5 algorithm
   provides for -- 29 bits vs. 48, or 0.000191 percent of the range that
   should be used for MD5.
 - Any passwords encrypted by htpasswd within the same second of
   system clock time will have the same salt, e.g.
      $ htpasswd -nbm user1 pass1; htpasswd -nbm user2 pass2; \
        htpasswd -nbm user3 pass2
      user1:$apr1$7jv93/..$2J9qu4mN2zms5O42vw/XE.
      user2:$apr1$7jv93/..$55cRqVaWTSB1YQpeD5uYe0
      user3:$apr1$7jv93/..$55cRqVaWTSB1YQpeD5uYe0
   All three users have the same salt, "7jv93/..", and user2 and user3 
   have the same encrypted password representation. 

Clearly, this is not good.

Furthermore, as you can see in that example, and as Andreas Krennmair
reported to the Apache Group in 2004, the htpasswd utility does not
use the full 48 bits of salt for the MD5 algorithm -- the last two
characters are always "..". So htpasswd tries creates 36-bit salt strings. 
Given that the srand() problem both reduces the universe to something 
like 29 bits[0] *and* makes the salt highly predictable, this 36-vs-48 
distinction is a moot point -- as long as the srand() seeding is bad.

The problem appears completely contained within the htpasswd utility;
Apache web server handles all properly encrypted passwords as it should.

Workarounds:

1) If you are concerned about the possibilty of the vastly reduced 
   salt space making your password tables vulnerable to pre-computed
   dictionary attacks, use an updated htpasswd utility to re-encrypt
   all MD5 or CRYPT passwords.

2) Use an alternate tool for generating your password hashes. 
   Implementations of the CRYPT and "apr1" MD5 algorithms are available
   for various programming languages and platforms -- you don't need to
   use the inferior tool from the Apache project.

Solution:

htpasswd should at least use a more random seed for the srand() calls
so that rand() can produce less predictable salts. It should also, as
Andreas Krennmair noted, make full use of the 48-bit-wide salt capability 
of its "apr1" MD5 algorithm.

Patches:

Patches are available in Apache's "issues" database that correct both the 
weak seeding of srand() and, thanks to Andreas, the 36/48 bit salt size 
for MD5: 
  http://issues.apache.org/bugzilla/show_bug.cgi?id=31440

Here's sample output from a patched htpasswd utility:

$ htpasswd -nbm user1 pass1; htpasswd -nbm user2 pass2; \
  htpasswd -nbm user3 pass2
user1:$apr1$wMdual6C$4.JZNIEfbWvF7OKvpsTGO0
user2:$apr1$LCXYBrpM$6ypjd9FWcVjt6niwCHst71
user3:$apr1$7vefL1ic$6WdQmN9sMUQvQvMGVyHU//

The patch I submitted to the Apache group
 1) by default makes use of the /dev/urandom device that is available
    on most modern open systems OSes 
 2) allows the user to specify another seed source (such as /dev/random)
    via an environment variable
 3) prints a warning if it has to fall back to using time()

Users of Microsoft Windows or other target platforms that lack /dev/urandom
might want to improve on this approach with appropriate APIS such as
RtlGenRandom on Windows. Also, the patch provides no updates to the htpasswd 
man page documentation.

History:

Vulnerability reported via vendor's bug tracking database, and source
code patch made available, on 25 January 2008.

Vendor security contact notified via email on 4 February 2008.

Vendor response: 

None, as of 13 February 2008.

----------------------------------------------------------------------
[0] For any given PRNG. In theory, different machines could have 
different PRNG algorithms, providing some additional security. But in
my tests, most common Linux flavors (Linux being perhaps the most 
popular platfor for Apache web server) use the same PRNG and physically
different systems produce the same output from htpasswd for any given 
clock time / time() value. 29 bits are enough to represent every time()
value since before the first release of Apache web server. As noted in
Bugzilla, the narrower the timeframe an attacker is interesetd in, the
smaller the list of possible salts.