Aryeh Gregor <Simetrical+wikilist at gmail.com> wrote:
As I noted above, there are hash functions whose security is provable based on the exact same assumptions used to prove security of various popular asymmetric encryption schemes. As I also noted above, there are problems with naively trying to use public-key encryption instead of hash functions. It makes more sense to just use known-secure hash functions directly instead of trying to twist public-key encryption to our needs, if we're that worried about Whirlpool (et al.) being broken anytime soon.
Password length disclosure can be overcome by padding all password inputs to the maximum length allowed, as you noted. Practically, though, a scheme like this adds an extra roadblock (if the key is not just stored in the database) which an attacker must overcome. Assuming even basic conscientiousness on the part of the administrator this would add a non-trivial extra compromise for the attacker to pull off. Getting all Wikipedia password hashes and going to work on them is just one data dump script bug away, though.
For what it's worth, even ancient and thoroughly-broken hash functions like MD4 don't have readily-usable preimage attacks.
These attacks (typically aimed at digital signatures) do not allow themselves the luxury of assuming the extremely small pre-image space that is typical for user-entered passwords, though. This makes brute-force attacks feasible and the
only practical constraint on the attacker becomes the hash function's run time.
Several years ago MD5 was brute-forced on the credit card number space in only a couple of days. Credit card numbers have ~10^16 permutations; even assuming strong passwords (upper and lower case letters, digits, and special characters) that is
only ~70^10 for a "very strong" 10 digit password, or ~10^18 and so of about equal complexity.
Mediawiki luckily already salts its password hashes with the user name, which makes site-wide brute force attacks impractical, though not targeted account brute force attacks. Given the stakes involved this is probably sufficiently strong, though in other contexts compromising a single account may be unacceptable. And I'm sure one could perform some interesting social engineering-based attacks as "User:Jimbo Wales" :-)