Hashing a key: less entropy than the key itself

Question

A web API needs to store a 'key' for authentication, in much the same fashion as a password but at 128 characters. My concern is that the salted SHA1 hash for the key has less entropy than the key itself (40 characters vs. 128 characters).

I understand that the hash is necessary in case the database is compromised, but in this case from the outside, assuming no database breach is this setup more susceptible to brute-forcing than if I were to store and match the unhashed key?

Note: this horrible setup does not replace the real password setup. Someone who 'calls the shots' wants a second password to access a certain feature, and he wants it to be long and to be called a 'key'. After coding it I will have opportunity to demonstrate how silly this is. My question here only pertains to the susceptibility of a 128-character string being brute-forced vs. its 40-character salted hash being brute-forced.

Answer 1

Entropy is a big word for a mathematical concept (in the context of cryptography), which is thus named out of an approximate analogy with the "entropy" as used in physics. Here, "n bits of entropy" means, more or less, that there are 2ⁿ possible values for the key.

For security, there is no practical difference beyond 100 bits of entropy. We want our keys to be safe from exhaustive search and this is achieved when trying out all possible keys, or at least a substantial portion of the key space, is ludicrously unfeasible with existing technology. Cryptographers have long used "80 bits" as the threshold for that; 100 bits ought to account for improvements in technology and a comfortable margin (at these sizes, energy dominates, not Moore's law). Beyond that size, exhaustive search is utterly defeated, and there is no bigger defeat than that.

Therefore, while your "128-character key" has potentially 512 bits of entropy (assuming the "characters" are hexadecimal digits) and the SHA-1 hash has "only" 160 bits (the output size of SHA-1), both are still very far into the "cannot do it" realm, and it does not make sense, from a security point of view, to say that one is "more secure" than the other. Both are immune from exhaustive search.

Correspondingly, there is no need for a salt here. Salts are about preventing parallelism and precomputations: they assume that the attacker can run an exhaustive search on one key, and will want to run the same attack on several keys. Salts ensure that the attack cost for ten keys will be ten times the cost for one key. With a 100+ bits key, the cost for one attack is way beyond what can be done, so there is little point in preventing parallelism. Said otherwise, if the salts change anything to the security situation, then the attacker is a god, and you should sacrifice oxen to appease him, not try to counter him with your puny hash functions.

Answer 2

SHA1 produces a 160 bit output. It is often represented in base16, which would produce a 40 characters string. Regardless of its base representation, it is still a 160 bit hash. SHA1 is not an ideal hash function as it suffers from known weaknesses, SHA-256 is a better choice, and SHA3 will be common place very soon.

Rainbow tables are lookup tables that allow an attacker to quickly determine the plain-text input to a specific hash function. An example generation would be all alpha-numeric-mixedcase strings between 6-9 characters long. Making a table for purely hex input, a-f,0-9 means a much smaller input space and thus easier to generate. 128 characters 8-byte ASCII is 128*8 or 1024 bits of information, and 128 characters in hexadecimal encoding is 128*4 which is 512 bits of information. Even 512 bits is a large enough space to prevent brute force. There is no "short cut" in attacking a large input size to a hash function, but nothing is stopping you from using SHA-512.

There are likely other more serious threats to a security system that has an arbitrary password system. The reason why we hash passwords is to defend against a database breach. This is because an attacker is forced to break the password hash in order for it to be useful. If you are not planning on failure, you are doing it wrong.

Answer 3

If you were to have a 40 character input and a 40 character hash, we would assume the ratio of password to hashes would be around 1 to 1. That means for every password there is going to be a single hash, but it is not guaranteed that one password will have exactly one hash, it is only approximate.

Considering having 128 characters and producing a 40 character hash, there will be about 3.2 passwords for every hash if you consider every possible combination of 128 characters.

It is possible for a 128 character password to have the same hash as a 1 character password! It is not very likely but it is definitely possible and is a potential weakness.

In conclusion, when you have more inputs than outputs, you will have to reuse some of the outputs to fulfill all the inputs.

Answer 4

Keep in mind from a security standpoint, hash functions like SHA-X, MD5, and other "fast" hashes are prone to rainbow tables [1]. Although it's difficult to compute 160 bits of entropy, if a hash function can be run in parallel across a very large domain of inputs then a hacker could store this precomputation and with ease be able to reverse any weak passwords.

Salting helps this dramatically, especially if there is a different salt used for every password, however it is far more efficient to use a slow, memory inefficient hash function such as bcrypt or scrypt due to parallelism on GPU. See [2] for an explanation of password size and cost to crack passwords of different lengths.

[1] - http://en.wikipedia.org/wiki/Rainbow_table

[2] - https://raw.githubusercontent.com/tarcieri/scrypt/modern-readme/kdf-comparison.png