When designing a hash function, what should be the secure input and output lengths? In particular, what lengths do I need for collision resistance?
$\begingroup$
$\endgroup$
4
-
$\begingroup$ Input lengths are variable from 0 bits up, do you mean message block size? $\endgroup$– Richie FrameFeb 11, 2014 at 10:17
-
$\begingroup$ Yes, input length for the underlying compression function (or permutation), and output length for the hash function. $\endgroup$– Dingo13Feb 11, 2014 at 12:57
-
$\begingroup$ The output size for collision resistance should be twice the security level. So for a 128 bit level, use 256 bit hashes. $\endgroup$– CodesInChaosFeb 11, 2014 at 18:02
-
$\begingroup$ This is related to the birthday attack. This concerns all hash functions, independent of its actually design. $\endgroup$– gmoktopFeb 12, 2014 at 7:27
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
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).
answered Feb 13, 2014 at 10:18
-
$\begingroup$ "...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. $\endgroup$ Feb 13, 2014 at 17:29
-
$\begingroup$ 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 $\endgroup$ Feb 13, 2014 at 19:38
$\begingroup$
$\endgroup$
3
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.
answered Feb 12, 2014 at 14:45
-
$\begingroup$ Reiterating (read: blatantly copying) the comment of Codes. $\endgroup$– Maarten Bodewes ♦Feb 12, 2014 at 14:45
-
1$\begingroup$ I'm feeling like one of these small clean up fishes swimming after the shark now :) $\endgroup$– Maarten Bodewes ♦Feb 12, 2014 at 14:46
-
$\begingroup$ On the positive side: sharks aren't as dangerous as rumour has it… as long as they “feel clean”. ;) $\endgroup$– e-sushiFeb 15, 2014 at 2:55