0
$\begingroup$

If I have some data I hash with SHA256 as hash=SHA256(data) and then copy only the first 8 bytes of the hash instead of the whole 32 bytes. How easy is it to find a hash collision with different data? Is it $2^{64}$ or $2^{32}$?

And uf I need to reduce a hash of some data to a smaller size ($n$ bits) is there any way to ensure the search space $2^n$?

$\endgroup$
3
$\begingroup$

Even in a perfect world (the random oracle model) there's no way to ensure first-preimage and second-preimage resistane of more than $2^n$ and collision resistance of more than $2^{n/2}$. (Wie $n$ bytes as the output size of the hash function.) That's the maximum you will ever be able to archive.

Cutting off some bytes of the output of a secure hash algorithm doesn't hurt the security more than you have to expect. With an output of $8$ bytes ($n = 64$ bits) from (for example) SHA-256 you have first-preimage and second-preimage resistance of $2^{64}$ and collision resistance of $2^{32}$.

$\endgroup$
  • $\begingroup$ Would making n=80bits and doing a million or so iterations of SHA256 add enough security that a one month bruteforce is out of the question? Do you have any recommendations on minimum bit size, and key stretching needed to throw out the possibility of something being bruteforced to find a collision in a reasonable amount of time? $\endgroup$ – Harry Feb 23 '15 at 12:07
  • $\begingroup$ @Harry: It's all about the entropy and against what attack you want to protect yourself. 80 bit (10 output bytes) is (in the moment) enough for let's say password hashing for a web site (first- and second-preimage resistance), but not for hashing a document to sign it with asymmetric encryption (collision resistance). Be warned, 80 bit could be in realm of possibility to be breakable in 2020 or so. Use it only if you really need to. 128 bit is recommended. $\endgroup$ – Nova Feb 23 '15 at 13:24
  • $\begingroup$ @Harry: For the number of iterations of PKBDF2, yes, 1 million is good. That won't help you with passwords like "password". Even the highest amount wouldn't help you there. The iterations are only to help mediocre passwords to get a good security value. Bad passwords will stay bad. See here for more informations: stackoverflow.com/questions/6054082/… $\endgroup$ – Nova Feb 23 '15 at 13:25
  • $\begingroup$ I'm not really asking about a password. I am distributing a hash of something and I want it to not be bruteforced until the original data is shown and then verified against the hash. So I'm looking for the smallest size hash of that data that can't be bruteforced between the time the hash is shown and the data is produced to verify it matches the hash. I know 128bits or higher for a hash is "Recommended" but I guess I'm asking if there's a way to go smaller than 128 and still be in the realm of acceptable. $\endgroup$ – Harry Feb 23 '15 at 21:51
  • $\begingroup$ @Harry: Yes, with this you will need first-preimage resistance. 80 bit should be enough. $\endgroup$ – Nova Feb 23 '15 at 22:28

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.