Godel's Incompleteness Theorems are probably some of--if not the most---misunderstood concepts in all of mathematics (rivaling Cantor's Uncountability Theorem).
While the usual analogy for the first theorem is drawn to the liar's paradox ("This is a false statement."), it's important to remember that it is only an analogy. The first theorem states, in layman's terms, that we can construct a valid mathematical statement which is complete and utter nonsense. (Much like "This is a false statement." is neither true nor false, but nonsensical.)
The second incompleteness theorem simply states (again, in layman's terms) that the consistency (where we say something is consistent if it contains no contradictions) of certain systems cannot be shown from the rules of the system itself. (Or alternatively and more correctly, if you're able to show the consistency of these systems using their own rules, then they're inconsistent.)
That said, please remember that these are mathematical theorems and as such their "applications" to other areas such as metaphysics, even by their creator, are not rigorous or necessarily meaningful. They live where they belong: in the depths of mathematical logic, in the heart of mathematics.
Currently such attacks are infeasible, but there are some very interesting, and very promising families of collision-based attacks (such as herding) which may yield results in that area, although such attacks may only work in specific cases.
Yes, that's why I specifically said, "in current use." No one should be using SHA-3 hash functions. SHA-256 and SHA-1 are much slower than MD5 and very much slower than MD4. The "Getting much better" comment was in reference to speed improvements as well as security improvements (such as removal of vulnerability to length-extension attacks).
The effort required to implement bcrypt in new systems is indeed small, and such a method is the suggested way to do, but depending on the amount of users, the effort required to port an existing database over to bcrypt (e.g., Facebook) could be immense, and the result disastrous if not done with great care.
Ptacek said, and I quote, "... a crappy web app ..." so why do you only cite me as making the "incorrect assumption that only poorly written web apps have their databases compromised?"
Again, I agree that is the case in new systems, but I disagree that one is "effed," as the article puts it, if they have a large database of salted hashes.
I'm not "arguing for the sake of arguing." I'm trying to explain my point to you, and I'm doing so in a polite manner, which is exactly what I'd expect from you.
The weaknesses in SHA-1 make it a poor cryptographic hash, which make it a poor pseudorandom function, which has a significant potential to make it a poor password hash.
My point, for the second time, is that you're not "effed" if you use salted hashes.
I'm not trying to "prove" anything. I'm stating my opinion on the matter. This isn't a pissing contest, rather, a forum for discussion.
I never said SHA-1, a cryptographically insecure hash, was a good choice. It's important to note in your differences that, for the most part, cryptographic hash functions in current use have gotten much slower (e.g., SHA-256 vs MD5), but are also getting much better (SHA-3 competition).
The argument I have is this: The passwords that are going to be hitting Rapidshare in your scenario are the crappy or short ones, whether you use bcrypt, scrypt, PBKDF2, salted hashes or HMAC. Encourage them to use bcrypt or some other iterative technique for the security benefits, but don't exaggerate and tell them that they're "effed" if they have salted hashes. They're still a long way away from storing passwords in plaintext.
The bruteforce attack described in the article primarily affects short and dictionary-based passwords. If the password is of sufficient length and complexity (the keyspace is large enough), then bruteforcing becomes computationally infeasible. What the article proposes is, essentially, to use a more computationally expensive algorithm for the benefit of protecting shorter, weaker, passwords. I disagree, and think that increasing the computational cost of the algorithm itself should be used to enhance the security of passwords, rather than having their security depend entirely on that increased cost.
Good passwords stored as a salted hash, or preferably, as an HMAC, are in no way insecure. I feel that implying otherwise is a disservice.
A poorly-written web app whose SQL database is compromised has bigger problems than protecting the integrity of poorly chosen passwords (especially if they store financial information).
Losing such a collection of salted hashes does not render one "royally screwed." Those hashes (or HMACs) are still cryptographically secure, which means it's computationally infeasible to find a first preimage provided the password doesn't suck. You seem to think (or are at least implying) that bcrypt is impervious to standard iterative bruteforce attacks, but that's just not the case. Much like PBKDF2, and other iterative hashing techniques, bcrypt is more resistant, but still "vulnerable" to such an "attack." bcrypt's main advantage over other iterative techniques, in my opinion, is the 4KiB of s-boxes used by Blowfish.
I disagree wholeheartedly. The article is based around the fallacy we've seen time and time again, of throwing more cryptography at a problem that cryptography alone cannot solve. In the end, a crappy password is a crappy password. Successfully discouraging your users from using a crappy password has much better repercussions (for the user, for you, and for the web in general) than switching from a hash-based authentication system to bcrypt. Use bcrypt for additional security, but do not use it in an attempt to solve the problem of crappy passwords that the article falsely claims bcrypt solves.
To be more technical, bcrypt, like PBKDF2 and other schemes of that nature, add a significant amount of additional computation by iteratively applying a primitive, but still maintain a relatively small circuit size (in comparison to the primitive itself, which is usually designed to fit onto smart cards and the like). Creating and using algorithms which are "memory-hard" or require larger circuits reduces the number of circuits one can place on some area of silicon and drives up the cost of an attack. In other words, mounting an attack on bcrypt or PBKDF2 is still cheaper and potentially much faster than we'd like it to be (which is the reason those algorithms are "tunable"--you scale the number of iterations up as computers become faster). This, along with some example memory-hard functions was the topic of Percival's paper, "Stronger Key Derivation via Sequential Memory-Hard Functions," which correctly cites Bernstein as the source of emphasis on practicality in measuring an attack not by computational complexity, but the cost of launching the attack. See http://www.bsdcan.org/2009/schedule/attachments/87_scrypt.pd... if you're interested in reading further.
PHP's sigils are superfluous. Perl (from which PHP derives their use) utilizes sigils with respect to typing in order to denote scalar variables ($), arrays (@) and hashes (%). What does PHP use the $ sigil for? Everything but references (&). Why? Because.
PHP's standard library is extremely disorganized. What's the function to put a string into hexadecimal? bin2hex. What's the function to put a string into base64? base64_encode. How do you turn a base64 string back into a "binary" string? base64_decode. How do you turn a hexadecimal string back into a "binary" string? Oh wait... an explicit function doesn't exist for that. Not to mention the various inconsistent ways in which functions are named: afnctn(), afunction(), a_function(), et cetera ad nauseum. Many functions also have an inconsistent order of parameters.
PHP doesn't support integral values larger than that of a signed 32 bit integer. Even better, when you overflow an int, you get a float back! Did you know pack() and unpack() support arguments for the unsigned ints that PHP doesn't support? Genius!
Last I checked, PHP didn't use lexical scoping. Do you know how downright stupid and annoying that is?
The downright stupidity of some of the PHP users just baffles me at times. One look on the PHP manual (Especially at any of the pages about the cryptographic functions, such as md5() and sha1() ) is enough to make any seasoned programmer's blood pressure skyrocket.
While the usual analogy for the first theorem is drawn to the liar's paradox ("This is a false statement."), it's important to remember that it is only an analogy. The first theorem states, in layman's terms, that we can construct a valid mathematical statement which is complete and utter nonsense. (Much like "This is a false statement." is neither true nor false, but nonsensical.)
The second incompleteness theorem simply states (again, in layman's terms) that the consistency (where we say something is consistent if it contains no contradictions) of certain systems cannot be shown from the rules of the system itself. (Or alternatively and more correctly, if you're able to show the consistency of these systems using their own rules, then they're inconsistent.)
That said, please remember that these are mathematical theorems and as such their "applications" to other areas such as metaphysics, even by their creator, are not rigorous or necessarily meaningful. They live where they belong: in the depths of mathematical logic, in the heart of mathematics.