Index: src/__phutil_library_map__.php
===================================================================
--- src/__phutil_library_map__.php
+++ src/__phutil_library_map__.php
@@ -1595,6 +1595,7 @@
     'PhabricatorInlineSummaryView' => 'infrastructure/diff/view/PhabricatorInlineSummaryView.php',
     'PhabricatorInternationalizationManagementExtractWorkflow' => 'infrastructure/internationalization/management/PhabricatorInternationalizationManagementExtractWorkflow.php',
     'PhabricatorInternationalizationManagementWorkflow' => 'infrastructure/internationalization/management/PhabricatorInternationalizationManagementWorkflow.php',
+    'PhabricatorIteratedMD5PasswordHasher' => 'infrastructure/util/password/PhabricatorIteratedMD5PasswordHasher.php',
     'PhabricatorJavelinLinter' => 'infrastructure/lint/linter/PhabricatorJavelinLinter.php',
     'PhabricatorJumpNavHandler' => 'applications/search/engine/PhabricatorJumpNavHandler.php',
     'PhabricatorKeyValueDatabaseCache' => 'applications/cache/PhabricatorKeyValueDatabaseCache.php',
@@ -1764,6 +1765,9 @@
     'PhabricatorPHIDType' => 'applications/phid/type/PhabricatorPHIDType.php',
     'PhabricatorPHPMailerConfigOptions' => 'applications/config/option/PhabricatorPHPMailerConfigOptions.php',
     'PhabricatorPagedFormExample' => 'applications/uiexample/examples/PhabricatorPagedFormExample.php',
+    'PhabricatorPasswordHasher' => 'infrastructure/util/password/PhabricatorPasswordHasher.php',
+    'PhabricatorPasswordHasherTestCase' => 'infrastructure/util/password/__tests__/PhabricatorPasswordHasherTestCase.php',
+    'PhabricatorPasswordHasherUnavailableException' => 'infrastructure/util/password/PhabricatorPasswordHasherUnavailableException.php',
     'PhabricatorPaste' => 'applications/paste/storage/PhabricatorPaste.php',
     'PhabricatorPasteCommentController' => 'applications/paste/controller/PhabricatorPasteCommentController.php',
     'PhabricatorPasteConfigOptions' => 'applications/paste/config/PhabricatorPasteConfigOptions.php',
@@ -4327,6 +4331,7 @@
     'PhabricatorInlineSummaryView' => 'AphrontView',
     'PhabricatorInternationalizationManagementExtractWorkflow' => 'PhabricatorInternationalizationManagementWorkflow',
     'PhabricatorInternationalizationManagementWorkflow' => 'PhabricatorManagementWorkflow',
+    'PhabricatorIteratedMD5PasswordHasher' => 'PhabricatorPasswordHasher',
     'PhabricatorJavelinLinter' => 'ArcanistLinter',
     'PhabricatorKeyValueDatabaseCache' => 'PhutilKeyValueCache',
     'PhabricatorLegalpadConfigOptions' => 'PhabricatorApplicationConfigOptions',
@@ -4491,6 +4496,9 @@
     'PhabricatorPHDConfigOptions' => 'PhabricatorApplicationConfigOptions',
     'PhabricatorPHPMailerConfigOptions' => 'PhabricatorApplicationConfigOptions',
     'PhabricatorPagedFormExample' => 'PhabricatorUIExample',
+    'PhabricatorPasswordHasher' => 'Phobject',
+    'PhabricatorPasswordHasherTestCase' => 'PhabricatorTestCase',
+    'PhabricatorPasswordHasherUnavailableException' => 'Exception',
     'PhabricatorPaste' =>
     array(
       0 => 'PhabricatorPasteDAO',
Index: src/applications/auth/controller/config/PhabricatorAuthEditController.php
===================================================================
--- src/applications/auth/controller/config/PhabricatorAuthEditController.php
+++ src/applications/auth/controller/config/PhabricatorAuthEditController.php
@@ -276,6 +276,8 @@
       $form->appendRemarkupInstructions($help);
     }
 
+    $footer = $provider->renderConfigurationFooter();
+
     $crumbs = $this->buildApplicationCrumbs();
     $crumbs->addTextCrumb($crumb);
 
@@ -305,6 +307,7 @@
       array(
         $crumbs,
         $form_box,
+        $footer,
         $xaction_view,
       ),
       array(
Index: src/applications/auth/provider/PhabricatorAuthProvider.php
===================================================================
--- src/applications/auth/provider/PhabricatorAuthProvider.php
+++ src/applications/auth/provider/PhabricatorAuthProvider.php
@@ -437,4 +437,8 @@
       $content);
   }
 
+  public function renderConfigurationFooter() {
+    return null;
+  }
+
 }
Index: src/applications/auth/provider/PhabricatorAuthProviderPassword.php
===================================================================
--- src/applications/auth/provider/PhabricatorAuthProviderPassword.php
+++ src/applications/auth/provider/PhabricatorAuthProviderPassword.php
@@ -11,8 +11,91 @@
 
   public function getConfigurationHelp() {
     return pht(
-      'You can select a minimum password length by setting '.
-      '`account.minimum-password-length` in configuration.');
+      "(WARNING) Examine the table below for information on how password ".
+      "hashes will be stored in the database.\n\n".
+      "(NOTE) You can select a minimum password length by setting ".
+      "`account.minimum-password-length` in configuration.");
+  }
+
+  public function renderConfigurationFooter() {
+    $hashers = PhabricatorPasswordHasher::getAllHashers();
+    $hashers = msort($hashers, 'getStrength');
+    $hashers = array_reverse($hashers);
+
+    $yes = phutil_tag(
+      'strong',
+      array(
+        'style' => 'color: #009900',
+      ),
+      pht('Yes'));
+
+    $no = phutil_tag(
+      'strong',
+      array(
+        'style' => 'color: #990000',
+      ),
+      pht('Not Installed'));
+
+    $best_hasher_name = null;
+    try {
+      $best_hasher = PhabricatorPasswordHasher::getBestHasher();
+      $best_hasher_name = $best_hasher->getHashName();
+    } catch (PhabricatorPasswordHasherUnavailableException $ex) {
+      // There are no suitable hashers. The user might be able to enable some,
+      // so we don't want to fatal here. We'll fatal when users try to actually
+      // use this stuff if it isn't fixed before then. Until then, we just
+      // don't highlight a row. In practice, at least one hasher should always
+      // be available.
+    }
+
+    $rows = array();
+    $rowc = array();
+    foreach ($hashers as $hasher) {
+      $is_installed = $hasher->canHashPasswords();
+
+      $rows[] = array(
+        $hasher->getHumanReadableName(),
+        $hasher->getHashName(),
+        $hasher->getHumanReadableStrength(),
+        ($is_installed ? $yes : $no),
+        ($is_installed ? null : $hasher->getInstallInstructions()),
+      );
+      $rowc[] = ($best_hasher_name == $hasher->getHashName())
+        ? 'highlighted'
+        : null;
+    }
+
+    $table = new AphrontTableView($rows);
+    $table->setRowClasses($rowc);
+    $table->setHeaders(
+      array(
+        pht('Algorithm'),
+        pht('Name'),
+        pht('Strength'),
+        pht('Installed'),
+        pht('Install Instructions'),
+      ));
+
+    $table->setColumnClasses(
+      array(
+        '',
+        '',
+        '',
+        '',
+        'wide',
+      ));
+
+    $header = id(new PHUIHeaderView())
+      ->setHeader(pht('Password Hash Algorithms'))
+      ->setSubheader(
+        pht(
+          'Stronger algorithms are listed first. The highlighted algorithm '.
+          'will be used when storing new hashes. Older hashes will be '.
+          'upgraded to the best algorithm over time.'));
+
+    return id(new PHUIObjectBoxView())
+      ->setHeader($header)
+      ->appendChild($table);
   }
 
   public function getDescriptionForCreate() {
Index: src/applications/people/storage/PhabricatorUser.php
===================================================================
--- src/applications/people/storage/PhabricatorUser.php
+++ src/applications/people/storage/PhabricatorUser.php
@@ -112,9 +112,9 @@
     if (!strlen($envelope->openEnvelope())) {
       $this->setPasswordHash('');
     } else {
-      $this->setPasswordSalt(md5(mt_rand()));
+      $this->setPasswordSalt(md5(Filesystem::readRandomBytes(32)));
       $hash = $this->hashPassword($envelope);
-      $this->setPasswordHash($hash);
+      $this->setPasswordHash($hash->openEnvelope());
     }
     return $this;
   }
@@ -170,19 +170,37 @@
     if (!strlen($this->getPasswordHash())) {
       return false;
     }
-    $password_hash = $this->hashPassword($envelope);
-    return ($password_hash === $this->getPasswordHash());
+
+    return PhabricatorPasswordHasher::comparePassword(
+      $this->getPasswordHashInput($envelope),
+      // TODO: For now, we need to add a prefix.
+      new PhutilOpaqueEnvelope('md5:'.$this->getPasswordHash()));
   }
 
-  private function hashPassword(PhutilOpaqueEnvelope $envelope) {
-    $hash = $this->getUsername().
-            $envelope->openEnvelope().
-            $this->getPHID().
-            $this->getPasswordSalt();
-    for ($ii = 0; $ii < 1000; $ii++) {
-      $hash = md5($hash);
-    }
-    return $hash;
+  private function getPasswordHashInput(PhutilOpaqueEnvelope $password) {
+    $input =
+      $this->getUsername().
+      $password->openEnvelope().
+      $this->getPHID().
+      $this->getPasswordSalt();
+
+    return new PhutilOpaqueEnvelope($input);
+  }
+
+  private function hashPassword(PhutilOpaqueEnvelope $password) {
+
+    $hasher = PhabricatorPasswordHasher::getBestHasher();
+
+    $input_envelope = $this->getPasswordHashInput($password);
+    $output_envelope = $hasher->getPasswordHashForStorage($input_envelope);
+
+    // TODO: For now, we need to strip the type prefix until we can upgrade
+    // the storage.
+
+    $raw_output = $output_envelope->openEnvelope();
+    $raw_output = substr($raw_output, strlen('md5:'));
+
+    return new PhutilOpaqueEnvelope($raw_output);
   }
 
   const CSRF_CYCLE_FREQUENCY  = 3600;
Index: src/infrastructure/util/password/PhabricatorIteratedMD5PasswordHasher.php
===================================================================
--- /dev/null
+++ src/infrastructure/util/password/PhabricatorIteratedMD5PasswordHasher.php
@@ -0,0 +1,46 @@
+<?php
+
+final class PhabricatorIteratedMD5PasswordHasher
+  extends PhabricatorPasswordHasher {
+
+  public function getHumanReadableName() {
+    return pht('Iterated MD5');
+  }
+
+  public function getHashName() {
+    return 'md5';
+  }
+
+  public function getHashLength() {
+    return 40;
+  }
+
+  public function canHashPasswords() {
+    return function_exists('md5');
+  }
+
+  public function getInstallInstructions() {
+    // This should always be available, but do something useful anyway.
+    return pht('To use iterated MD5, make the md5() function available.');
+  }
+
+  public function getStrength() {
+    return 1.0;
+  }
+
+  public function getHumanReadableStrength() {
+    return pht("Okay");
+  }
+
+  protected function getPasswordHash(PhutilOpaqueEnvelope $envelope) {
+    $raw_input = $envelope->openEnvelope();
+
+    $hash = $raw_input;
+    for ($ii = 0; $ii < 1000; $ii++) {
+      $hash = md5($hash);
+    }
+
+    return new PhutilOpaqueEnvelope($hash);
+  }
+
+}
Index: src/infrastructure/util/password/PhabricatorPasswordHasher.php
===================================================================
--- /dev/null
+++ src/infrastructure/util/password/PhabricatorPasswordHasher.php
@@ -0,0 +1,336 @@
+<?php
+
+/**
+ * Provides a mechanism for hashing passwords, like "iterated md5", "bcrypt",
+ * "scrypt", etc.
+ *
+ * Hashers define suitability and strength, and the system automatically
+ * chooses the strongest available hasher and can prompt users to upgrade as
+ * soon as a stronger hasher is available.
+ *
+ * @task hasher   Implementing a Hasher
+ * @task hashing  Using Hashers
+ */
+abstract class PhabricatorPasswordHasher extends Phobject {
+
+  const MAXIMUM_STORAGE_SIZE = 128;
+
+
+/* -(  Implementing a Hasher  )---------------------------------------------- */
+
+
+  /**
+   * Return a human-readable description of this hasher, like "Iterated MD5".
+   *
+   * @return string Human readable hash name.
+   * @task hasher
+   */
+  abstract public function getHumanReadableName();
+
+
+  /**
+   * Return a short, unique, key identifying this hasher, like "md5" or
+   * "bcrypt". This identifier should not be translated.
+   *
+   * @return string Short, unique hash name.
+   * @task hasher
+   */
+  abstract public function getHashName();
+
+
+  /**
+   * Return the maximum byte length of hashes produced by this hasher. This is
+   * used to prevent storage overflows.
+   *
+   * @return int  Maximum number of bytes in hashes this class produces.
+   * @task hasher
+   */
+  abstract public function getHashLength();
+
+
+  /**
+   * Return `true` to indicate that any required extensions or dependencies
+   * are available, and this hasher is able to perform hashing.
+   *
+   * @return bool True if this hasher can execute.
+   * @task hasher
+   */
+  abstract public function canHashPasswords();
+
+
+  /**
+   * Return a human-readable string describing why this hasher is unable
+   * to operate. For example, "To use bcrypt, upgrade to PHP 5.5.0 or newer.".
+   *
+   * @return string Human-readable description of how to enable this hasher.
+   * @task hasher
+   */
+  abstract public function getInstallInstructions();
+
+
+  /**
+   * Return an indicator of this hasher's strength. When choosing to hash
+   * new passwords, the strongest available hasher which is usuable for new
+   * passwords will be used, and the presence of a stronger hasher will
+   * prompt users to update their hashes.
+   *
+   * Generally, this method should return a larger number than hashers it is
+   * preferable to, but a smaller number than hashers which are better than it
+   * is. This number does not need to correspond directly with the actual hash
+   * strength.
+   *
+   * @return float  Strength of this hasher.
+   * @task hasher
+   */
+  abstract public function getStrength();
+
+
+  /**
+   * Return a short human-readable indicator of this hasher's strength, like
+   * "Weak", "Okay", or "Good".
+   *
+   * This is only used to help administrators make decisions about
+   * configuration.
+   *
+   * @return string Short human-readable description of hash strength.
+   * @task hasher
+   */
+  abstract public function getHumanReadableStrength();
+
+
+  /**
+   * Produce a password hash.
+   *
+   * @param   PhutilOpaqueEnvelope  Text to be hashed.
+   * @return  PhutilOpaqueEnvelope  Hashed text.
+   * @task hasher
+   */
+  abstract protected function getPasswordHash(PhutilOpaqueEnvelope $envelope);
+
+
+/* -(  Using Hashers  )------------------------------------------------------ */
+
+
+  /**
+   * Get the hash of a password for storage.
+   *
+   * @param   PhutilOpaqueEnvelope  Password text.
+   * @return  PhutilOpaqueEnvelope  Hashed text.
+   * @task hashing
+   */
+  final public function getPasswordHashForStorage(
+    PhutilOpaqueEnvelope $envelope) {
+
+    $name = $this->getHashName();
+    $hash = $this->getPasswordHash($envelope);
+
+    $actual_len = strlen($hash->openEnvelope());
+    $expect_len = $this->getHashLength();
+    if ($actual_len > $expect_len) {
+      throw new Exception(
+        pht(
+          "Password hash '%s' produced a hash of length %d, but a ".
+          "maximum length of %d was expected.",
+          $name,
+          new PhutilNumber($actual_len),
+          new PhutilNumber($expect_len)));
+    }
+
+    return new PhutilOpaqueEnvelope($name.':'.$hash->openEnvelope());
+  }
+
+
+  /**
+   * Parse a storage hash into its components, like the hash type and hash
+   * data.
+   *
+   * @return map  Dictionary of information about the hash.
+   * @task hashing
+   */
+  private static function parseHashFromStorage(PhutilOpaqueEnvelope $hash) {
+    $raw_hash = $hash->openEnvelope();
+    if (strpos($raw_hash, ':') === false) {
+      throw new Exception(
+        pht(
+          'Malformed password hash, expected "name:hash".'));
+    }
+
+    list($name, $hash) = explode(':', $raw_hash);
+
+    return array(
+      'name' => $name,
+      'hash' => new PhutilOpaqueEnvelope($hash),
+    );
+  }
+
+
+  /**
+   * Get all available password hashers. This may include hashers which can not
+   * actually be used (for example, a required extension is missing).
+   *
+   * @return list<PhabicatorPasswordHasher> Hasher objects.
+   * @task hashing
+   */
+  public static function getAllHashers() {
+    $objects = id(new PhutilSymbolLoader())
+      ->setAncestorClass('PhabricatorPasswordHasher')
+      ->loadObjects();
+
+    $map = array();
+    foreach ($objects as $object) {
+      $name = $object->getHashName();
+
+      $potential_length = strlen($name) + $object->getHashLength() + 1;
+      $maximum_length = self::MAXIMUM_STORAGE_SIZE;
+
+      if ($potential_length > $maximum_length) {
+        throw new Exception(
+          pht(
+            'Hasher "%s" may produce hashes which are too long to fit in '.
+            'storage. %d characters are available, but its hashes may be '.
+            'up to %d characters in length.',
+            $name,
+            $maximum_length,
+            $potential_length));
+      }
+
+      if (isset($map[$name])) {
+        throw new Exception(
+          pht(
+            'Two hashers use the same hash name ("%s"), "%s" and "%s". Each '.
+            'hasher must have a unique name.',
+            $name,
+            get_class($object),
+            get_class($map[$name])));
+      }
+      $map[$name] = $object;
+    }
+
+    return $map;
+  }
+
+
+  /**
+   * Get all usable password hashers. This may include hashers which are
+   * not desirable or advisable.
+   *
+   * @return list<PhabicatorPasswordHasher> Hasher objects.
+   * @task hashing
+   */
+  public static function getAllUsableHashers() {
+    $hashers = self::getAllHashers();
+    foreach ($hashers as $key => $hasher) {
+      if (!$hasher->canHashPasswords()) {
+        unset($hashers[$key]);
+      }
+    }
+    return $hashers;
+  }
+
+
+  /**
+   * Get the best (strongest) available hasher.
+   *
+   * @return PhabicatorPasswordHasher Best hasher.
+   * @task hashing
+   */
+  public static function getBestHasher() {
+    $hashers = self::getAllUsableHashers();
+    msort($hashers, 'getStrength');
+
+    $hasher = last($hashers);
+    if (!$hasher) {
+      throw new PhabricatorPasswordHasherUnavailableException(
+        pht(
+          'There are no password hashers available which are usable for '.
+          'new passwords.'));
+    }
+
+    return $hasher;
+  }
+
+
+  /**
+   * Get the hashser for a given stored hash.
+   *
+   * @return PhabicatorPasswordHasher Corresponding hasher.
+   * @task hashing
+   */
+  public static function getHasherForHash(PhutilOpaqueEnvelope $hash) {
+    $info = self::parseHashFromStorage($hash);
+    $name = $info['name'];
+
+    $usable = self::getAllUsableHashers();
+    if (isset($usable[$name])) {
+      return $usable[$name];
+    }
+
+    $all = self::getAllHashers();
+    if (isset($all[$name])) {
+      throw new PhabricatorPasswordHasherUnavailableException(
+        pht(
+          'Attempting to compare a password saved with the "%s" hash. The '.
+          'hasher exists, but is not currently usable. %s',
+          $name,
+          $all[$name]->getInstallInstructions()));
+    }
+
+    throw new PhabricatorPasswordHasherUnavailableException(
+      pht(
+        'Attempting to compare a password saved with the "%s" hash. No such '.
+        'hasher is known to Phabricator.',
+        $name));
+  }
+
+
+  /**
+   * Test if a password is using an weaker hash than the strongest available
+   * hash. This can be used to prompt users to upgrade, or automatically upgrade
+   * on login.
+   *
+   * @return bool True to indicate that rehashing this password will improve
+   *              the hash strength.
+   * @task hashing
+   */
+  public static function canHashBeUpgraded(PhutilOpaqueEnvelope $hash) {
+    $current_hasher = self::getHasherForHash($hash);
+    $best_hasher = self::getBestHasher();
+
+    return ($current_hasher->getHashName() != $best_hasher->getHashName());
+  }
+
+
+  /**
+   * Generate a new hash for a password, using the best available hasher.
+   *
+   * @param   PhutilOpaqueEnvelope  Password to hash.
+   * @return  PhutilOpaqueEnvelope  Hashed password, using best available
+   *                                hasher.
+   * @task hashing
+   */
+  public static function generateNewPasswordHash(
+    PhutilOpaqueEnvelope $password) {
+    $hasher = self::getBestHasher();
+    return $hasher->getPasswordHashForStorage($password);
+  }
+
+
+  /**
+   * Compare a password to a stored hash.
+   *
+   * @param   PhutilOpaqueEnvelope  Password to compare.
+   * @param   PhutilOpaqueEnvelope  Stored password hash.
+   * @return  bool                  True if the passwords match.
+   * @task hashing
+   */
+  public static function comparePassword(
+    PhutilOpaqueEnvelope $password,
+    PhutilOpaqueEnvelope $hash) {
+
+    $hasher = self::getHasherForHash($hash);
+    $password_hash = $hasher->getPasswordHashForStorage($password);
+
+    return ($password_hash->openEnvelope() == $hash->openEnvelope());
+  }
+
+}
Index: src/infrastructure/util/password/PhabricatorPasswordHasherUnavailableException.php
===================================================================
--- /dev/null
+++ src/infrastructure/util/password/PhabricatorPasswordHasherUnavailableException.php
@@ -0,0 +1,5 @@
+<?php
+
+final class PhabricatorPasswordHasherUnavailableException extends Exception {
+
+}
Index: src/infrastructure/util/password/__tests__/PhabricatorPasswordHasherTestCase.php
===================================================================
--- /dev/null
+++ src/infrastructure/util/password/__tests__/PhabricatorPasswordHasherTestCase.php
@@ -0,0 +1,42 @@
+<?php
+
+final class PhabricatorPasswordHasherTestCase extends PhabricatorTestCase {
+
+  public function testHasherSyntax() {
+    $caught = null;
+    try {
+      PhabricatorPasswordHasher::getHasherForHash(
+        new PhutilOpaqueEnvelope('xxx'));
+    } catch (Exception $ex) {
+      $caught = $ex;
+    }
+
+    $this->assertEqual(
+      true,
+      ($caught instanceof Exception),
+      pht('Exception on unparseable hash format.'));
+
+    $caught = null;
+    try {
+      PhabricatorPasswordHasher::getHasherForHash(
+        new PhutilOpaqueEnvelope('__test__:yyy'));
+    } catch (Exception $ex) {
+      $caught = $ex;
+    }
+
+    $this->assertEqual(
+      true,
+      ($caught instanceof PhabricatorPasswordHasherUnavailableException),
+      pht('Fictional hasher unavailable.'));
+  }
+
+  public function testMD5Hasher() {
+    $hasher = new PhabricatorIteratedMD5PasswordHasher();
+
+    $this->assertEqual(
+      'md5:4824a35493d8b5dceab36f017d68425f',
+      $hasher->getPasswordHashForStorage(
+        new PhutilOpaqueEnvelope('quack'))->openEnvelope());
+  }
+
+}