Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

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!)

share|improve this question
add comment

2 Answers

up vote 11 down vote accepted

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.

share|improve this answer
    
Thanks for weighing in with the clear pointers. Some questions: I opted for BCrypt not so much for 'slow' as much as for 'can be made slow enough for bruteforce not to be viable', even as technology progresses. If I understand, you're saying: as the secret is controlled, increase the entropy of the secret rather than the 'slowness' of the algorithm, in order to achieve the same resistance, correct? Regarding the confidentiality: I don't really understand the link to the question; what am I missing? Do you think some of the plaintext used for the MAC should be confidential? –  Gijs Oct 12 '12 at 19:23
    
As for "iPhone syndrome": ouch. I disagree, but I see your point. SHA-3 was an example; surely NIST isn't themselves saying that it's worse than SHA-2, either? The reason I didn't go with HMAC+SHA-2 to begin with (I'm aware rolling your own is a bad idea) was that in my limited searching around, there were concerns about it after the SHA-1 issues that surfaced, hence looking further. Searching some more it seems those concerns have faded somewhat now that quite some time has passed and nothing horrible has reared its head. Would you say the latter is an accurate summary? –  Gijs Oct 12 '12 at 19:32
    
@Gijs Brute force only works if you have a small enough number of possibilities. Even a "small" key like 128 bits is unlikely to be broken by brute force. The reason we need bcrypt is that most people have passwords which are extremely short. Your server doesn't have that limitation. –  Brendan Long Oct 12 '12 at 20:19
3  
Security of HMAC relies on some properties of the underlying hash function. These properties may suffer from issues similar to those which allow for building collisions; although it seems that the problem is not as dire (e.g. HMAC/MD4 is broken, but with effort 2^58, which is high, whereas MD4 collisions are "instantaneous": generating a MD4 collision costs less than compute MD4 over two messages). Therefore, it is possible that the known theoretical weaknesses on SHA-1 might impact HMAC/SHA-1. However, as far as we know, HMAC/SHA-256 is fine (and HMAC/Keccak is equally fine). –  Thomas Pornin Oct 12 '12 at 20:35
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.