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.


"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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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