Tim Starling schrieb: I don't know that much about the mathematical details of hashing, but i'd like to drop a pointer to an article if found interesting in this context: "Stop using unsafe keyed hashes, use HMAC" http://rdist.root.org/2009/10/29/stop-using-unsafe-keyed-hashes-use-hmac/ So, how does your proposal relate to HMAC? -- daniel

On Wed, Aug 18, 2010 at 11:37 PM, Tim Starling &lt;tstarling(a)wikimedia.org&gt; wrote: <snip> <snip> <snip> Let me preface my comment by saying that I haven't studied WHIRLPOOL, and the following may not apply to it at all. However, it is known that some block cypher based hashes behave poorly when fed repeated copies of the same block. In the worst cases the hash space is substantially truncated from its full size (which probably is not the case for any serious cryptographic hash function). Under less severe cases, cryptanalysis can find a new block cipher W' such that N applications of block cipher W is the same as one application of W'. If WHIRLPOOL is vulnerable to that kind of attack then it would negate the effect of using str_repeat in your code. Like I said, I don't know if either concern applies to WHIRLPOOL. However, these concerns only occur because the 256-bit string you are repeating is a fundamental divisor of the 512-bit block size used by WHIRLPOOL. So, it is trivial to avoid the whole issue simply by using a different repeated block size. For example 97 copies of a 33 byte string should have essentially the same computational performance, while making any associated cryptanalysis threat impossible (or at least less likely). My only other comment is something you presumably already know. Your proposal is still nothing but an arms race. It makes hashes harder to crack by making the hash function itself much more computationally expensive. However, you'd still have to periodically boost the rep rate with the intention of staying far in front of the hackers. As a complementary approach it would be nice if there was something in Mediawiki to aid in the selection of strong passwords. Regardless of hash function, it will still take about two billion times longer to find one 10 character password in [A-Za-z0-9] as it does to find a 6 character password in [a-z]. Even if password strength testing algorithms were disabled on Wikipedia sites, it would still be a nice addition to have in the Mediawiki codebase in general. -Robert Rohde

On Thu, Aug 19, 2010 at 2:37 AM, Tim Starling &lt;tstarling(a)wikimedia.org&gt; wrote: Seems reasonable. That seems reasonable. It could probably be done a lot faster on GPUs, I guess. On Thu, Aug 19, 2010 at 4:45 AM, Daniel Kinzler &lt;daniel(a)brightbyte.de&gt; wrote: As Tim said, it doesn't -- we aren't using keyed hashes, and we're only concerned about preimage attacks (not collision or second-preimage). Preimage attacks imply second-preimage attacks, and second-preimage attacks imply collision attacks. Thus something that's secure against collision is also secure against preimage and second-preimage, but a function with collision and second-preimage attacks might have no preimage attacks. For instance, MD5 has tons of trivial collision attacks against it, but no preimage attacks (not sure about second-preimage attacks offhand). Whirlpool has no known collision attacks, and thus no known preimage or second-preimage attacks. On Thu, Aug 19, 2010 at 5:02 AM, Robert Rohde &lt;rarohde(a)gmail.com&gt; wrote: In principle, we could evade any concern like this by just using a provably secure hash function. The usual reason not to use those is that they're slow, but that's an advantage in our case. For instance (from an exercise in my cryptography course), let p be a prime, q a prime dividing p - 1, and let G be the subgroup of Z_p^* of order q. Let g be a randomly chosen generator for G, and let a_1, ..., a_k be randomly chosen elements of G. If x, y_1, ..., y_k are integers in the range 1 to q, define H(x, y_1, ..., y_k) = g^x a_1^y_1 ... a_k^y_k. Then under the discrete logarithm assumption for G, it's easy to prove that H is collision-resistant. You can make similar functions based on other hard problems -- http://en.wikipedia.org/wiki/Provably_secure_cryptographic_hash_function gives another example using factorization, whose correctness is probably more obvious. There are two problems with using such a function. One is that there's probably no readily available implementation, so we'd have to write our own, which might be vulnerable to side-channel attacks. Another is that we're more worried about brute-forcing than about the algorithm being broken, so we'd have to write it in C to avoid giving one or two orders of magnitude advantage to the attacker, and then shared hosts can't use it. Perhaps the way to solve both problems is to submit the code for inclusion in future versions of the PHP hash module, after at least casual review by some cryptographers. This would require significant extra work, of course. Another thing to consider is if we could pick a function that's particularly inconvenient to execute on GPUs. Those are a great way for crackers to easily outdo any CPU implementation. For a basic implementation, anyway, Tim's proposal sounds like it's much better than what we have now. Fancy stuff like provably correct hash functions is probably overkill. On Thu, Aug 19, 2010 at 5:02 AM, Robert Rohde &lt;rarohde(a)gmail.com&gt; wrote: I agree we should have a good system available for those who want it, and it should probably be enabled by default for sysops. However, as I've said elsewhere, these strength testing things are counterproductive for unprivileged users on open wikis. For such users, a compromised account is approximately as bad as just forgetting your password -- the result in either case is you just lose access to the account. If it's compromised, it might be somewhat worse (because the attacker might prevent an e-mail reset), but on the other hand, forgetting your password is at least a couple orders of magnitude more likely. As such, to minimize harm to users, we should encourage them to use easy-to-remember passwords, not strong passwords. On Thu, Aug 19, 2010 at 10:12 AM, Jonathan Leybovich &lt;jleybov(a)yahoo.com&gt; wrote: If you just delete the private key, this is the same as any old hash function, but with various additional deficiencies. For instance, public-key encryption is not designed to hide length information, while hash functions are -- although due to padding, this might not be a big deal. More seriously, public-key encryption schemes are invariably probabilistic, which makes them useless for our purposes. We'd have to adapt the scheme to remove any randomization. And there might be other problems. There's really no reason to go to all this trouble -- people have designed and studied dedicated hash functions for a reason. On Thu, Aug 19, 2010 at 10:50 AM, Ryan Lane &lt;rlane32(a)gmail.com&gt; wrote: SMS has loads of vulnerabilities: http://en.wikipedia.org/wiki/SMS#Vulnerabilities I don't see anyone signing up to get an e-mail or text message every time they want to log in, either. At best, this pushes the authentication problem back to their e-mail or SMS provider. In that case, why not just use OpenID? Not if the password is not stored on the computer and the private key is. Yes, so let's not worry about it, shall we? We aren't the NSA here. On Thu, Aug 19, 2010 at 2:18 PM, Jonathan Leybovich &lt;jleybov(a)yahoo.com&gt; 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. For what it's worth, even ancient and thoroughly-broken hash functions like MD4 don't have readily-usable preimage attacks. (MD4 was published in 1990, broken in 1995, and only in 2008 was a preimage attack published -- which still requires 2^102 evaluations, instead of 2^128.) We don't have to worry much about the hash functions being broken.