How certain is it that a shorter password can't match the salted hash of a long one?

We (collectively) salt passwords, then hash them; maybe even run them through something like PBKDF2 first (depending on how the password will be used).

The end result is that we have a string $p$ and map it to a fixed-length string $p'$ using a surjective transformation with the property that it is difficult to find any particular $p$ that maps to a given $p'$.

The fact that there are $\aleph_0$ possible $p$ strings and only a finite amount of possible $p'$ strings means that there is an infinite number of $p$ strings that map to any particular $p'$.

The difficulty of guessing a password when the attacker has access to the salted hash comes from the fact that the $p\to p'$ mapping function is relatively expensive, limiting the rate at which attempts can be made to find a suitable $p$ for $p'$. (Essentially, the attacker is brute forcing a hash collision, not guessing the actual password.)

Intuitively, increasing the length of $p$ seems to increase the number of attempts required to find it; however, since the attacker isn't actually trying to find the original $p$, just some $p_1$ that has the same hash, I wonder to what extent we can guarantee that increasing the length of $p$ really increases the time required to obtain a collision; both in general and in practical particular cases.

Mathematically: if we have a $p_0$ salted password with length $x$ that maps to $p'_0$, what's the likelihood of a $p_1$ string with length $<x$ to map to the same $p'_0$?

Do PBKDF2 and/or mainstream cryptographic hash functions contain some mechanism to decrease this likelihood?

I don't think it can be possible to guarantee this in the general case where passwords can be arbitrarily long. If the salted password is longer than the hash length $\ell$, then there are going to be several passwords that map to the same hash; assuming that the hashes are approximately evenly distributed, we exhaust the entirety of hash space just with passwords of length $\ell+1$, which means that some passwords of length $\ell$ will also map to some of the same hashes.

This means that there is a critical length $\ell_c$ above which adding more characters to the password doesn't increase the time required to obtain it a collision.

I think in most cases this isn't a practical problem because password hashes can be very long; humans are unlikely to choose passwords longer than $\ell_c$, if $\ell_c$ is on the order of hash length.

However, I feel (and I realize I should be able to work this out from first principles) that increasing password length doesn't actually scale guessing difficulty exponentially, as one would intuitively think, because the likelihood of a hash collision with a shorter string also increases with increasing password length. I feel certain that someone has actually worked out the math and I'd be interested in the result, I probably chose the wrong search terms because I couldn't immediately find it.

I'm also interested in a practical aspect: if I use a realistically long password of ~15 characters, what are the chances that a much shorter string will map to the same hash, effectively weakening my password? Is this purely a question of luck (with astronomical chances)?

EDIT: some naïve math, mostly ignoring salts for now: if the hash is, say, 64 characters long, then there are 256^64 different hashes. All passwords shorter than 16 characters will map to 256^16-1 different hashes, and passwords that are exactly 16 characters long will map to 256^16 different hashes. The chance of these sets overlapping is a birthday problem, but we're not interested in the probability of any short and any long password having the same hash, only the probability of a specific long password having the same hash as any short password, so we can ignore the birthday aspect and the odds do look very good.

EDIT: formalizing my question above: given a $p_0$ password of length $x$, and a $p_1$ password of length $x+1$, we tend to believe the expected value of the time required to crack $p_1$ using brute force would be 256 times the expected value of time required to crack $p_0$, but what is the actual ratio, also considering hash collisions? It must be a function of $x$, approaching 1 as $x$ approaches the length of the hash. Again, this looks quite easy to work out but probably someone has already done it, and I don't like doing math enough to also like redoing it :).

EDIT: I realize most of this is not of any practical concern. My interest is "academic" (in the informal sense).

[originally posted on security.SE] There's a sister site, crypto.stackexchange.com, that might be better suited to answering your questions about the mathematical properties of hash functions. However, from a practical standpoint:

(Essentially, the attacker is brute forcing a hash collision, not guessing the actual password.)

Strictly speaking true, but in practice utterly irrelevant. Even a single-round unsalted fast hash is going to only allow an attacker to guess maybe a few hundred billion candidates a second, and that's if they throw a LOT of GPU or ASIC parallelization at it. Let's round up to 2⁴⁰, just over a trillion, for convenience. Let's further hypothesize that the site is using a 256-bit digest - the shortest commonly used for modern code, though of course many obsolete "secure" hash functions use less - and that the digests are in fact approximately evenly distributed. We know there's one preimage - the password (or in your case password+salt) - that generates the target digest (the hash output that we're trying to "break") and is a reasonable length (let's say 16 bytes, 128 bits, or less). The odds of there existing a second such preimage in the same length space is approximately 1 in 2¹²⁸; absurdly small[1]. Furthermore, even if you somehow knew such a second preimage existed, finding it by brute force would be expected to take approximately 2⁸⁸ seconds, or roughly 710,000,000 times the lifetime of the universe. Good luck!

[1] Given evenly distributed digests of length 256, there is a 1 in 2²⁵⁶ chance that any two random inputs collide. If you have about 2¹²⁸ possible inputs - all the possibilities of length 16 bytes or less, minus the actual password - then there is about a 1 in 2¹²⁸ chance that one of those will collide. The exact number would require operations more advanced than subtraction to find, but it really doesn't matter; at this order of magnitude, being off by a factor of millions wouldn't make any practical difference.

Mathematically: if we have a $p_0$ salted password with length $x$ that maps to $p'_0$, what's the likelihood of a $p_1$ string with length $<x$ to map to the same $p'_0$?

See above for answers in the practical range. This approximation breaks down as $x$ approaches the length of $p'_0$ - if your password and digest are both 256 bits long, it is not actually guaranteed that there are any collisions within the other ~2²⁵⁷ candidate passwords of length 256 or less, despite what the approximation above would suggest - but again it doesn't matter. 256 bits is so large a possibility space that it's hard to even conceive of. There could be 47 quadrillion (arbitrary huge-seeming number) collisions in that space but your odds of ever finding even one of them by brute force with every GPU that will be manufactured in 2023 devoted solely to that task for a century would still be irrelevantly low.

Do PBKDF2 and/or mainstream cryptographic hash functions contain some mechanism to decrease this likelihood?

Aside from "attempt to achieve a roughly evenly spread mapping of preimage to digest, and thus make brute forcing a collision / getting collisions-by-luck as good as impossible", probably not? Crypto-SE might know better.

This means that there is a critical length l_c above which adding more characters to the password doesn't increase the time required to obtain

Assuming your passwords are fully random (including permitting all the non-printing characters/illegal UTF-8 byte sequences/etc.), that's true! It happens around the length of the digest minus the length of the salt, I think. Realistic passwords that are composed purely of things you can actually type on a keyboard, and probably "encoded" as something like words in an actual human language so that you have any hope of memorizing it (think about how e.g. Diceware passphrase generation works, where each set of 6^6 possibilities - ~15.5 bits of entropy - from rolling 6d6 is mapped to a reasonably common English word), would have to be quite a lot longer in encoded length to reach the same entropy (Diceware words will be on average way longer than the two bytes their entropy doesn't quite equal), but the point of no benefit would eventually come nonetheless. However, it the point of "it is functionally impossible to brute force this" comes much sooner, and the point of "it isn't financially worth it to brute force this" comes much sooner still unless you're, like, Satoshi Nakamoto.

I'm also interested in a practical aspect: if I use a realistically long password of ~15 characters, what are the chances that a much shorter string will map to the same hash, effectively weakening my password?

See above (depends on the length of the digest and how evenly inputs are distributed across the digest space), but for all intents and purposes, zero.

Is this purely a question of luck?

Technically yes but practically no, or at least not the kind you're thinking of; if a password hash collision does occur, it is absurdly more likely that the developer made a mistake (such as using PHP's PBKDF2 function with PHP 7.x or older and deploying to a server that doesn't offer the requested hash function, in which case every user's "hash" will be the string "false" because PHP was made by smart people with good ideas about error handling). That type of human error is the risk you take any time you use any product - including but not limited to software and websites - and it utterly swamps the risk you're talking about here. For that matter, so does every other risk you take in your life, such as every time you exist where a tree could, in theory, fall on you. "Purely a question of luck" but not a question worth worrying about.