# Is a hashing algorithm considered broken if a collision happens under $2^{n/2}$?

If for example we would find a hash collision for SHA256 with $$h(x) = h(x')$$ for $$x \ne x'$$ and $$x, \space x' < 128$$ bit (meaning both $$x$$ and $$x'$$ are smaller than 128 bit), would SHA256 be considered broken?

Is it then always possible to create more collisions in a feasible time or could this hash collision just be considered an "anomaly"?

• I think you mean $x,x' < 128$-bit Feb 13, 2019 at 21:05

If for example we would find a hash collision for SHA256 with $$h(x) = h(x')$$
Yes, pretty much. Now, I'm not certain what you meant by "$$x \land x' < 128$$ bit" (total bit length is less than 128 bits, or they disagree in at most 128 bits???), however, it doesn't really matter; finding any collision would demonstrate that SHA256 isn't quite as collision resistant as we had thought.
If $$x, x'$$ had the same length (or, more generally, used the same number of SHA-256 blocks when hashing), then it's easy to find more collisions; we would have $$h(x || Pad_x || y) = h(x' || Pad_{x'} || y)$$ for any string $$y$$ (where $$Pad_x, Pad_{x'}$$ is the padding that SHA-256 applies when hashing $$x, x'$$).