5

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.

2
  • Why do you use 128 char keys? That's overkill. Mar 5, 2013 at 7:21
  • Because someone who 'calls the shots' wants to call it a 'key' and of course a 'key' is long! It is a red-herring issue, I know, and I plan on demonstrating how silly it is after it is coded. Please let's not get hung up on that obvious silliness and rather discuss the question if the original password is less susceptible to brute-force than the salted SHA1 hash, disregarding an attacker having access to the database.
    – dotancohen
    Mar 5, 2013 at 7:29

4 Answers 4

9

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 2n 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.

3
  • Or bears. Sacrifices of bears please the gods. They're more challenging than oxen.
    – Jeff Ferland
    Mar 5, 2013 at 14:21
  • Thank you for this very practical standpoint. If the case that 160 bits of entropy are 'enough for anyone' then why are 1024 and even 4096 bit certs available? For that matter, I think that IE will now reject certs with less than 1024 bit entropy.
    – dotancohen
    Mar 5, 2013 at 15:21
  • 1
    Keys in certificates are not "bunches of bits" but mathematical objects with a lot of internal structure (this is needed to do the asymmetric encryption and digital signatures). They can be attacked through mathematics much more efficiently than with brute force. A 1024-bit RSA key is (very roughly) about as "strong" as a 77-bit key for a symmetric encryption algorithm. Mar 5, 2013 at 15:24
1

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.

4
  • Thank you Rook, I understand the implications of a rainbow table attack, I even mention it in the first sentence of the second paragraph. The question is, since the the original password is larger than 160 bits, is the salted and hashed password more susceptible to brute force than the original password itself.
    – dotancohen
    Mar 5, 2013 at 7:25
  • @dotancohen no, a larger input is much harder to break. The only way it would be made weaker is if the hash function had a serious vulnerability. Also you could use sha256
    – rook
    Mar 5, 2013 at 7:36
  • you multiply with the size of the charset, need a log2 there. Hex: 4*len; ASCII: 7*len Mar 5, 2013 at 7:49
  • @CodesInChaos Nothing occupies 7 bits, an ASCII character always uses 8 bits even if it is not an "extended ascii" character. Also I don't know under what cases anyone would encode a blob of binary in 7-bit or why you would even mention this obscure method of encoding. As for my math, you are correct it is late...
    – rook
    Mar 5, 2013 at 7:57
1

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.

2
  • 1
    Number of states is exponential in length Mar 5, 2013 at 7:51
  • 1
    While the pigeonhole principle creates a fundamental limit, real hash functions are not random oracles and so collisions can exist even when the input space is the same size as the output space.
    – forest
    May 29, 2018 at 6:09
-2

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

3
  • I'd like to see the attacker with a 512-bit rainbow table. Actually, I wouldn't. I'm hardly a religious diplomat qualified to meet with gods, and I would probably get our galaxy popped. Jul 22, 2014 at 3:06
  • Where'd you get 512 bits from? Jul 24, 2014 at 22:16
  • The OP isn't working with passwords, but 128-character keys of some sort. If they're hex, that's 512 bits of entropy. Edit: See Rook's answer and CodesInChaos's comments to it. Jul 24, 2014 at 22:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .