Hacker News Reader

Comment by atoponce | Hacker News Reader

The sha256/512crypt algorithms, as well as md5crypt, hash the input based on each character in the password. This is why the execution time increases. bcrypt does not do this.

bcrypt is constant-time, not because it truncates at 72 characters. It's constant-time, because it slurps the password and salt once into the state (initial setup), then spends the rest of the time manipulating that state based on the cost (expand key).

Yes, you could pre-hash with sha256crypt or sha512crypt, and that completely works around the password-length performance issue. You pre-hash with bcrypt to get around a maximum length restriction, not to get around a performance bottleneck.

View on HN

> bcrypt is constant-time, not because it truncates at 72 characters. It's constant-time, because it slurps the password and salt once into the state (initial setup)

And why do you think that initial setup is constant-time? Because it truncates at 72 characters! Otherwise it would be O(n), and so bcrypt overall would be O(n) + O(m) (if n is password length and m is cost factor).

It's quite simply impossible to have any hash function not be at least O(n) without truncation. That would imply that the data does not even need to be read to compute the hash.

Your point is still relevant in that without truncation, shacrypt would be O(n*m) and bcrypt would be O(n) + O(m), but NEITHER is O(m) without truncation. If shacrypt truncated, it would be O(m), just like bcrypt is O(m) with truncation. If both prehash instead of truncate, then both are O(n) + O(m).

From my testing with Python's base64, hashlib, and passlib.hash modules, SHA-256 prehashing and base64 encoding is only approximately one one-hundredths the total execution time of bcrypt_sha256 for a 4 KB "password". This is why slurping in the password during the initial state isn't noticeably adding to the overall execution time of password prehashing with bcrypt, and it is analogous to why PBKDF2, scrypt, and Argon2 all show constant time in execution regardless of password length- slurping in the password during initialization is a fraction of the execution time.

Reply on news.ycombinator.com