sordidarray

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.

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.

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.

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.

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.

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.

New.

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?

PHP's thread support sucks. Period.

According to Cal Henderson at Flickr, PHP "leaks memory like a sieve." (http://www.afup.org/IMG/pdf/flickr_php.pdf) (of course this is an implementation issue)

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.

Cheers.