BCrypt's 72-character limit and using it as a general digest algorithm

Question

Goal: have token/cookie-based authentication that doesn't require keeping sessions on the server

TL;DR: What, if any, is the accepted mechanism to work around the 72-character limitation of BCrypt?

Long version:

After reading this answer I attempted to implement authentication on a REST-based server using BCrypt as a hashing algorithm and a rotating server-side secret. The basic idea was that upon successful authentication with a username and password, the server would set a cookie containing a hash based on concatenating the following:

• The server-side secret
• The user ID and groups to which the user belongs
• The time at which point the token was given out

This would then be hashed with a salt, and the result would go in the cookie, to be read and verified by the server (possible because the user ID, groups and date are transmitted in the plain by the client, and the server-side secret is in memory, with the secret serving as a guarantee that the client didn't make all the other values up themselves).

This all worked well until I realized that BCrypt has a 72-character limit on the plaintext being hashed (anything after those 72 characters does not influence the output hash).

This is a problem because the above data amounted to more than 72 characters, and allowing either the time, user ID, groups or secret key to be 'last' in the input and not influence the output opens holes in the system's security (either old tokens are infinitely valid, or people can modify their user ID / role arbitrarily).

Ironically, when I finally figured out why my system was producing identical hashes based on differing input and googled around, it seems this kind of situation was foreseen by some.

Anyhow, the question: What, if any, is the accepted mechanism to work around the 72-character limitation of BCrypt?

Some pre-emptive thoughts: Making up your own variations on standard crypto algorithms is something I've been warned about for as long as I can remember, so I am not 100% sure what would be the best course of action.

Obvious options include:

• chunking the input and applying BCrypt to each in turn and/or in cascaded fashion;
• using another (non-cryptographic?) hash on the input to reduce its size
• using plain compression (but that might be ineffective with such a small bit of plaintext)
• switching to another algorithm (SHA-3 was recently finalized, for instance).

(there may be other things wrong with the above idea, in which case I would of course be happy to be corrected!)

Answer 1

The accepted mechanism is "don't do it".

What is bcrypt good at ? It is good at being slow. Why would you want a cryptographic function, or just any function, to be slow ? This makes sense only when the input to the function is a low-entropy secret, which means "some value which the adversary could conceivably, and realistically, explore exhaustively". Passwords are low-entropy secrets: it is well-known then when human beings are allowed to choose secret strings in the privacy of their brain, most will select "witty" passwords which are utterly weak against dictionary attacks. The only remaining defense is to enforce the use of an inherently slow hashing process, which is equivalent to sending all involved computers (and, in particular, the attacker's computers) back to the early 1980s, when 1 MHz was a very high CPU frequency.

In your case, the "secret value" is the server's secret; it should not be of low entropy (the server is a machine, not a human; it can remember long keys). If the server's secret is a low-entropy value, then you are doing it wrong.

Therefore, no need for bcrypt or any other deliberately slowed function here. What you actually want is a Message Authentication Code: you want to store some values on the client side (as a cookie), but you also want to check that you are not fed back forged values; this is a matter of integrity, and a MAC is the right tool for that. Use HMAC/SHA-256, with the "server's secret" as the MAC key (your homemade hashing of several values, including the server secret, is just a homemade MAC in disguise, so you could just do it right by reusing the standard, robust, expert-vetted solution, and that's HMAC).

---

Of course, once we begin to use client-side storage, it becomes tempting to store values which the client himself should not learn. To the integrity requirement, we add confidentiality. For that, we need encryption. Doing encryption properly is difficult, and combining encryption and a MAC even more. In that case, do yourself a favour: use an authenticated encryption mode, which will do it properly with minimum hassle (I recommend EAX).

---

By suggesting Keccak (SHA-3), you demonstrate that you are afflicted with a very common disease, which can be called the "iPhone syndrome": you crave for the newest gadget. Stop it. When dealing with security in general and cryptography in particular, this will lead only to massive suffering. In cryptography, "new" is another name for "bad".

The best kind of cryptographic algorithms is old algorithms which are still alive. There is no better criterion for security. In that sense, SHA-2 is better than SHA-3, and will remain so in the future, until a problem is found with these functions. The NIST people themselves explicitly recommend SHA-2 and deny any suggestion that SHA-3 would be better than SHA-2.

Answer 2

You could use another key derivation function such as scrypt or pbkdf2+sha2 (or sha3).

Although I think this approach to authentication is very wasteful of bandwidth, memory and CPU and to top it off its less secure. In order for key stretching to be effective, it must be heavy, and you'll need to make this calculation for every request. I think you are better off issuing a cryptographic nonce, and back the server state with a fast non-relational database like memcachd. Sure its not "RESTful", but its a more efficent and a more secure design.

The best cryptographers use cryptography when there is no other choice. Plan on failure.

Answer 3

It sounds like you are trying to maintain session state without the usual approach of storing the session data on the server end.

Here's a better cookbook:

1. Authenticate the username and password (Here you can use bcrypt for password validation)
2. Put all the session information you want to store in a serialized blob
3. Encrypt the blob with a strong, secret server key, using authenticated encryption
4. Send the blob in a cookie/hidden form field/... (base64 encoded)

Upon the next call:

1. Decrypt/verify the blob
2. Unserialize the session data
3. Profit!

All these steps have been battle-tested.