Apache tool generates password hashes using predictable salts

A password generation tool distributed with the Apache HTTP server has a flaw that could make dictionary attacks on passwords encoded using it easier. The tool, called htpasswd, generates MD5 hashes for Basic HTTP Authentication from passwords and salts.

Salts are intended to make attacks on password hashes using dictionaries and rainbow tables difficult or infeasible. But some salting implementations make password cracker's job unnecessarily easy. Peter Watkins has reported that htpasswd fails to use the full potential numerical range for salts, thus reducing the effective length from 48 to 29 bits. According to Watkins, this represents just 0.000191 per cent of the range potentially usable by the hash algorithm, making it easier to predict salts than it should be. This means that it becomes worthwhile attempting to calculate the hash using rainbow tables despite the use of a salt.

According to the report, the reason for the problem is that htpasswd initialises the pseudo random number generator rand() by seeding srand() with the current time using a granularity of one second. Thus every password generated within the same second will have the same salt (UYuQl/..):

~$ htpasswd -nbm user1 pass1; htpasswd -nbm user2 pass2;  htpasswd -nbm 
user3 pass2
user1:$apr1$UYuQl/..$ViUB8TjwOV4bSX7TT65Nh1
user2:$apr1$UYuQl/..$hCaYQ2z9z8nBEUtYH.SqJ1
user3:$apr1$UYuQl/..$hCaYQ2z9z8nBEUtYH.SqJ1

This means that if User2 and User3 have the same password, the hash will be the same for both. In addition, all salts end with the characters /...

As a solution, Watkins suggests using a different tool for generating hashes - one that uses randomly generated salts. The alternative tool needs to support the "apr1" MD5 algorithm. Patches for htpasswd are already available for Apache 1.3.39 and 2.2.8 from the Apache bug database. These ensure that the tool uses the full 48 bit salt space, reportedly by making use of /dev/urandom and /dev/random.

The patched version no longer supplies predictable salts:

$ 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//

See also:

• Apache web server 2.2: htpasswd predictable salt weakness, report from Peter Watkins

(mba)