13
$\begingroup$

I understand that password storage generally uses hashing for security due to it being irreversible and that the stored hash is just compared to the hash of the password inputed by a user attempting to log in. As hashes are fixed length, does that mean that even if not specified when creating the password, all login systems would need to have some sort of maximum input length (although probably very high)? Allowing inputs larger than the output length would risk collision. This would mean that 2 different passwords could be hashed and appear to match.

$\endgroup$
9
  • 20
    $\begingroup$ There is a practical reason, not related to the security: preventing DoS by sending arbitrarily large amounts of data. $\endgroup$
    – Trang Oul
    Commented Jul 26, 2023 at 7:02
  • 11
    $\begingroup$ Note that only allowing inputs of size at most the output size will still yield collisions. Even if you fix the input size to be exactly the output size, practical hash functions still likely have collisions. $\endgroup$
    – marcelm
    Commented Jul 26, 2023 at 9:20
  • 1
    $\begingroup$ @TrangOul DoS is considered a security violation. $\endgroup$ Commented Jul 26, 2023 at 17:10
  • 2
    $\begingroup$ You will have collisions as soon as two users decide to use 'password1' as their passwords. You should ofc 'salt' users passwords before hashing them to avoid being able to recover the original password from the hash. $\endgroup$ Commented Jul 26, 2023 at 20:05
  • 1
    $\begingroup$ @user253751 Depending on which "security" do you mean. It is a system security violation, but not data security. Your system might not be available during the DoS, but data should be safe. $\endgroup$
    – Trang Oul
    Commented Jul 27, 2023 at 6:37

9 Answers 9

22
$\begingroup$

No. There is no* limit on the length of the input to for most* good cryptographic hash functions. As a result, password hashing can support passwords of unlimited length and do not need to impose a limit on the maximum length of the password.

Of course collisions are possible and exist, but they are believed to be exceptionally difficult for anyone to find, so for engineering purposes we can essentially ignore the possibility of collisions, assuming we have chosen an appropriate hash function. See the following:

Separately: I expect you're going to be very interested in What technical reasons are there to have low maximum password lengths?. One ancient password hash function -- which wasn't very good -- did have a maximum length limit, for reasons that aren't relevant today. No one today should be using that ancient hash any longer.


$\endgroup$
4
  • 1
    $\begingroup$ Length limits are not confined to completely ancient algorithms. bcrypt, which is still widely used, and as far as I know not considered "broken", truncates the input to 72 bytes. That's quite long, but definitely still "practically relevant". $\endgroup$
    – IMSoP
    Commented Jul 27, 2023 at 14:06
  • $\begingroup$ @IMSoP, thank you for the correction! $\endgroup$
    – D.W.
    Commented Jul 27, 2023 at 18:31
  • $\begingroup$ There is a limit on the input size of the Cryptographic hash functions like SHA-256 has $2^{64-1}$ SHA512 has $2^{128}-1$. This is due to MOV attack (Handbook of Applied Cryptography; Chapter 9, Example 9.23),and even SHA3 has. $\endgroup$
    – kelalaka
    Commented Oct 19, 2023 at 16:44
  • $\begingroup$ Also, this answer misses the important part that we don't use Cryptographic hash functions for password hashing since we want iteration, memory-hardness, thread count, and even cache hardness ( bScrypt). AFAIK, almost all password hashing algorithms have input limit (Argon2) $\endgroup$
    – kelalaka
    Commented Oct 19, 2023 at 16:55
9
$\begingroup$

Yes, passwords need maximum length, but not because of collision risk (see other answers regarding collisions).

Reason for setting maximum length - possibility of denial of service attack.
Someone might start feeding petabytes into password field, pushing your setup to CPU/memory limits, which would impact other users.

Relevant note: For password hashing one SHOULD use CPU-heavy hash functions (Argon2, bcrypt ok; SHA, CRC32 not ok). It should be CPU-heavy to make brute force attacks harder/impossible, in case your database would be leaked.

$\endgroup$
6
  • 1
    $\begingroup$ -1 for even suggesting to use SHA-3. The SHA family of hashing algorithms is considered a fast hashing algorithm that should not be used for password hashing. You should be using something like Argon2 or bcrypt. $\endgroup$
    – Nzall
    Commented Jul 27, 2023 at 7:57
  • $\begingroup$ Thanks. Edited answer accordingly. $\endgroup$ Commented Jul 27, 2023 at 9:25
  • $\begingroup$ Thanks for the edit. Close vote retracted. $\endgroup$
    – Nzall
    Commented Jul 27, 2023 at 10:39
  • 1
    $\begingroup$ Note that the "CPU-heavy" part of the hashing should not significantly change depending on the length of your password – it should take roughly the same for a 10-character password and a 50 character one. $\endgroup$ Commented Jul 27, 2023 at 22:10
  • $\begingroup$ @PaŭloEbermann: Sure, but a 1MB password would take longer $\endgroup$ Commented Jul 28, 2023 at 15:15
8
$\begingroup$

As hashes are fixed length, does that mean that even if not specified when creating the password, all login systems would need to have some sort of maximum input length (although probably very high)?

At least some hash algorithms have some limit to the input length, though those are usually astronomically high, so not an issue in any sense. E.g. SHA-256 embeds the input length as a 64-bit number in the data it internally processes. Of course SHA-256 is not a password hash, but some algorithms used for password hashing use standard hashes internally (like PBKDF), and similar considerations might also apply to the ones that don't.

Then, you might also put some limit out of logistical reasons, so you don't need to run the password hash over gigabytes of data even if some joker decides to try entering a password of such length.

Allowing inputs larger than the output length would risk collision. This would mean that 2 different passwords could be hashed and appear to match.

But this sounds like you're thinking about the output length of the hash, and those are far shorter. E.g. bcrypt produces a 24 (or 23) byte hash, and something that uses SHA-256 would produce 256 bits, or 32 bytes. While those would be sufficient as password lengths, they're not really very high limits and someone using a long passphrase might get hit by them.

However, having the password longer than the hash output length doesn't matter. Hash algorithms are designed to produce a practically random output, so for a 24-byte (192-bit) hash, you'd need on the order of $ 2^{96} $ or $ 10^{30} $ inputs to have an approximately 50 % chance of two of them hashing to the same value. Due to passwords usually being composed of letters (or nearly enough) and not arbitrary bytes, the hash output also makes far better use of the space than the passwords themselves do. That is, the number of 24-character passwords is much smaller than the number of 24-byte hashes, so the length of passwords can be somewhat greater than the hash output length without that leading to a significant risk of collisions.

In any case, hash collisions within an arbitrary pair or passwords also don't matter, since the password hash is used to compare the single hash from the attempted login password with the single stored hash. Someone guessing passwords could in theory find one that matches the hash without being the original password, but that won't make it any easier, as each attempt would still only have a 1 in $ 2^{192} $ chance of matching.

$\endgroup$
3
  • 1
    $\begingroup$ Another reason why input should be allowed to be longer than output is that entropy per symbol in a password is often abysmally low, or at least far lower than possible, in order to allow easier memorization and handle input restrictions. That needs to be compensated with sufficiently increased length. $\endgroup$ Commented Jul 27, 2023 at 8:24
  • $\begingroup$ @Deduplicator, yes, that's exactly what I was trying to point out at the end of the second-to-last paragraph. Edited a bit. $\endgroup$
    – ilkkachu
    Commented Jul 27, 2023 at 8:43
  • $\begingroup$ Since you mention bcrypt in a later paragraph, it might be worth mentioning it in the section on input length as well, since most implementations truncate input to 72 bytes or even less. $\endgroup$
    – IMSoP
    Commented Jul 27, 2023 at 13:56
3
$\begingroup$

Hashes are designed to avoid collisions as much as possible. A perfect hash would completely avoid any collision between passwords up to the length of the hash.

For typical hash lengths, that means that collisions on passwords longer than the original are so rare that they simply preclude any brute-force search.

E.g. with a hash of $128$ bits, pessimistically assuming that $2^{64}$ passwords (up to length $128$ bits, roughly $20$ characters) can hash to the same value, the probability of finding one by chance is only $2^{-64}$.

If you account for arbitrarily long passwords, the probability of collisions indeed increases, but these are just unreachable.

$\endgroup$
3
$\begingroup$

Indeed, all hash functions do produce output of a fixed length, regardless of the length of the input. This does mean that there's a theoretical possibility of collisions — two different inputs producing the same hash. However, for cryptographic hash functions like SHA-256, the number of possible hash values is so large (about 2 256 2 256 ) that the probability of two random inputs producing the same hash (a random collision) is astronomically small.

That said, a system could technically have a maximum password length, but this limit wouldn't be due to the risk of collisions. It would most likely be due to other considerations such as storage, performance, or usability. For instance, it could be computationally expensive to hash a very large input, or it could be impractical for users to enter a very long password.

In terms of security, the risk of collision from long inputs is not a concern in practice. The security of a hash function against collisions is typically evaluated based on its resistance to deliberate collision attacks, where an attacker tries to find two inputs that produce the same hash. This is a much harder problem than finding a collision by chance.

So while it's true in theory that allowing longer inputs increases the chances of a collision, in practice, the chances are still so low that it's not a concern for password storage. The main considerations for password security should be using a secure, slow hash function (like bcrypt or Argon2), using a unique salt for each user, and following best practices for password strength and handling.

$\endgroup$
1
$\begingroup$

You should never store a password, even encrypted, or salted, or salted and encrypted. So for storage, the password length wouldn't matter. Your passwords should be salted and hashed; salting makes sure that an attacker cannot use pre-calculated tables, cannot detect weak passwords, and cannot find weak passwords after stealing a database of hashes. And after hashing, short and long passwords should be hashed to hashcodes of the same length, so the hash doesn't give any information about the password.

Once the password entropy is the same as the possible entropy of your hashes, adding more characters is pointless, it won't improve the quality of the password. On the other hand, telling a user that their password is too long is also quite inconvenient.

You can set a limit but high enough that no reasonable user would ever exceed that length. For example if I have to enter a password manually, a 10,000 character password would be impossible to enter in practice. And when you set the limit, assume that other people than you will feel may feel a length is still reasonable that you feel unreasonable.

Set the limit so high that no sane user will ever notice. As a bad example, one multi billion dollar company doesn't accept a password auto-generated by my iPhone. The passwords are three groups of five letters separated by hyphens. 17 characters. Their site only allowed fifteen. That's obviously very very inconvenient, annoying and error prone. Assume that I use a password generated by my software, and then I append a description of the password usage (it's stored by my device and I never enter it manually, so I don't mind if it's long), so that is easily 40 characters. Assume people using other, longer schemes as well. So if I really wanted to set a limit, it would be either something like 100 characters, or something that the software is guaranteed to handle well.

And make sure you don't have any stupid rules like "the same character must not be used more than twice". If I decided to have a 60 character password, I bet there will be characters occurring more than twice.

Another very important thing: If you change the rules, make sure that I can still enter existing passwords! If you decide to change maximum password length from 21 to 20 chars, or decide that I must use a special character, you better still let me enter my existing 21 letter password without special characters and don't lock me out.

$\endgroup$
0
$\begingroup$

A lot has already been said and I agree with most of it. But there is one thing I don't see mentioned:

Theoretically a collision can occur between two strings that are both much shorter than the output from the hash, so if you should use this as an argument for having a limit on the length of the passwords, you should find the collision between the shortest possible set of inputs, for most (modern) hashes that is hard. And if the passwords are salted I don't see any problem that can arise from a collision.

I hate sites that stop me from using whatever my password manager generated, which is a long string of random characters, because they deem it too long, simply for the inconvenience it causes me.

Yes, not setting a (short) limit means that people can log in to my account "just" by trying a password that hashed to the same string as mine, but as long as the site uses a reasonable hash (not e.g. CRC-16) chances are low that any guess they try will hash to the same as my password.

$\endgroup$
3
  • $\begingroup$ This is not at all a good reason for anyone to limit the length of passwords. If it is feasible to find a shorter password which hashes to the same value as a longer password, the hashing algorithm is broken. $\endgroup$ Commented Jul 27, 2023 at 0:48
  • 1
    $\begingroup$ I was trying to argue against limiting the length of passwords. So I have no idea what you mean. $\endgroup$ Commented Jul 27, 2023 at 8:13
  • $\begingroup$ I think I somehow misunderstood your original answer. It seems like you are actually making the same point I made in my comment. Sorry for the noise. $\endgroup$ Commented Jul 28, 2023 at 22:30
0
$\begingroup$

Ignoring that fact that passphrases are salted, and assuming that you are looking for a collision with one specific user.

If passphrases are randomly drawn from ASCII, then each character is represented by about 6.55 bits. As such, once the cleartext passphrase exceeds about 625 characters it is likely that more than one passphrase will hash to the same 4096-bit value.

At that point the amount of work put into guessing a candidate passphrase which will hash to the required 4096-bit value is very roughly the same as simply guessing that 4096-bit value. Any attack is likely to be thrown out because of the number of retries involved, or will become impractical because of an enforced delay between retries.

Guessing a passphrase which collides with that of /any/ user out of a large population is another matter, which is why there's an increasing emphasis on multi-factor authentication. I don't know how this eventually played out, but a few months ago there was speculation that somebody had had his Bitcoin wallet emptied simply by a random attack which struck lucky.

$\endgroup$
0
$\begingroup$

I suspect you're implicitly using the probability of a collision here is a proxy for the "guessability" of a working password. The issue with this is that to the extent that adding a max length constraint reduces the probability of a collision it also reduces the number of possible passwords at the same rate which in the best case exactly counteracts the effect of reducing the probability of a collision.

By definition the average number of passwords which evaluate to a given hash value (assuming a secure hash, regardless of the particular input constraints) is going to be the total number of possible inputs divided by the total number of possible outputs. Simplifying (ignoring the details of any additional password constraints), this would be $ |C|^n \over 2^m$ where $|C|$ is the number of valid characters, $n$ is the length of the string and $m$ is the number of bits of the hash.

Now for any given password the probability of randomly guessing (if the password is chosen in a secure manner this is the best you can do) a working password (one which evaluates to the same hash) from the set of all possible valid passwords will be equal to the number of passwords which evaluate to the same hash divided by the total number of valid passwords which on average would would be $|C|^n/2^m \over |C|^n $ which evaluates to $1 \over 2^m$ and the term involving the length of the password cancels out.

However, since we know the hash value was generated from a valid password the numerator in this case has to be $\geq 1$ and the probability of guessing the correct password therefore has to be $\geq {1 \over |C|^n}$. So if $n$ is small enough that $|C|^n \lt 2^m$ and therefore ${1 \over |C|^n}\gt{1 \over 2^m}$ the "guessability" of any given (secure) password in the system will begin to be defined by the maximum length constraint rather then by the number of bits of the hash and the maximum length constraint will have the effective of reducing rather than increasing the security of the system.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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