Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

When designing a hash function, what should be the secure input and output lengths? In particular, what lengths do I need for collision resistance?

share|improve this question
    
Input lengths are variable from 0 bits up, do you mean message block size? –  Richie Frame Feb 11 at 10:17
    
Yes, input length for the underlying compression function (or permutation), and output length for the hash function. –  Dingo13 Feb 11 at 12:57
    
The output size for collision resistance should be twice the security level. So for a 128 bit level, use 256 bit hashes. –  CodesInChaos Feb 11 at 18:02
    
This is related to the birthday attack. This concerns all hash functions, independent of its actually design. –  gmoktop Feb 12 at 7:27
add comment

2 Answers

up vote 1 down vote accepted

Security properties of hash functions are generally concerned with collision resistance, but preimage resistance is also important.

For most common hash functions with an $n$-bit digest size, a successful preimage attack has generic $2^n$ maximum complexity, and a successful collision attack has generic $2^{n/2}$ maximum complexity.

Most common hash functions also use a message block expansion that takes a message block twice the size of its internal state, and the digest size is generally the entire internal state or a truncation. The message is expanded from twice the state to however many bits is required for the rounds. Round input sizes vary with the design, SHA-2 uses a round input that is $1/8$ of the internal state. Blake uses the entire message block each round I believe. Other hash functions such as Keccak vary the message block size in order to change the security level. When designing a hash function the message block size can be important for security, and the size is dependent on the design.

The current NIST recommendation is 224-bit digests providing 112-bit resistance against collisions and at least 112-bit resistance against preimages. This recommendation makes several assumptions, notably that the attacker has the resources of a nation state, and that you do not need the hash to be secure for more than a given period of time. These are good assumptions. An additional assumption that is not made, but should be mentioned, is the possibility of undisclosed vulnerabilities that weaken the hash. The round count must be large enough (given round complexity) to prevent a short-cut attack.

If the time the hash needs to be secure exceeds 20 years (as of 2010), more than 112-bits of security are required. 128-bits of security should meet the requirements of all but the most paranoid for the next 35 years. Paranoia (or prudence) could add 6 to 16-bits of security to compensate for potential vulnerabilities or shortcut attacks. 256-bits of security should meet the requirements of anyone, forever (thanks to thermodynamics).

share|improve this answer
    
"...For most common hash functions with an n-bit digest size, a successful preimage attack has generic $2^n$ maximum complexity" A notable exception is Keccak/SHA-3, where preimages can be found in $2^{n/2}$ steps by meet-in-the-middle. –  Brock Hansen Feb 13 at 17:29
    
Preimage resistance for Keccak is dependent on capacity, and the capacity for SHA-3 has not been standardized yet. The initial plan was $n/2$-bit, but NIST will most likely standardize with n-bit resistance due to public comments –  Richie Frame Feb 13 at 19:38
add comment

Hashes should work on any number of input bits (almost all I/O parameters in cryptography are defined in bits). The output size for collision resistance should be twice the security level. So for a 128 bit level, use 256 bit hashes.

share|improve this answer
    
Reiterating (read: blatantly copying) the comment of Codes. –  owlstead Feb 12 at 14:45
1  
I'm feeling like one of these small clean up fishes swimming after the shark now :) –  owlstead Feb 12 at 14:46
    
On the positive side: sharks aren't as dangerous as rumour has it… as long as they “feel clean”. ;) –  e-sushi Feb 15 at 2:55
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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