Trying to understand the well known property of these collisions when used with SHA1, SHA256, etc. where a given key is larger than the block size of the digest function. In these cases the smaller of the collisions will have a size of 20 characters for SHA1 and 32 for SHA256 (1/2 the hexadecimal digest length), so does this mean to brute force a PBKDF2-HMAC-SHA1 an attacker only needs to consider passphrases of 20 characters or less? And therefore 32 or less if using SHA256? Are longer passphrases effectively pointless? Thanks.
$\begingroup$
$\endgroup$
$\begingroup$
$\endgroup$
"brute force a PBKDF2-HMAC-SHA1" is not about collisions (at least, if a single hash is targeted, or if there's salt at the input of the password hash). It's a preimage attack.
The hash output by SHA-1 is 160-bit. That's 20 bytes (not characters; these are different notions, and why we have character encodings). It can take $2^{160}$ values. The output of PBKDF2-HMAC-SHA-1 has a parameterizable size that can be smaller (by truncation) or larger (essentially by aggregating 20-byte results), but the parameter is often set to 20 bytes, and we'll assume that.
Does this mean to brute force a PBKDF2-HMAC-SHA-1 an attacker only needs to consider passphrases of 20 characters or less?
No. It implies that a random value the size of the hash has probability $2^{-160}$ to match a given hash. The practical consequence is that trying at random is hopeless.
Passwords are often restricted to a subset of ASCII with about 95 characters, thus there are about $2^{131.714}$ passwords of 20 such characters or less (most of them exactly 20-character). If PBKDF2 is parametrized to perform 1000 SHA-1 hashes per PBKDF2 (which is the lowest parametrization ever consider by its definition, and has become grossly insufficient), hashing half these passwords would require over $2^{140}$ hashes, that is over $2^{40}$ (a million million) times more than wasted so far by humanity bitcoin-mining. That's just not an option.
Password search typically does not try all possible passwords over more than few characters; commonly ≈6 among ≈70 characters (only very powerful attackers could target all combinations of 10 characters when there's even mild password/key stretching). What password search does is try passwords that people could plausibly choose, approximately in decreasing likelihood of being chosen.
