3
$\begingroup$

The tag wiki for says, in part:

SHA-256 ... processes the input in 512-bit block and has a 256-bit output, for a 128-bit security level.

I'm not a cryptographer, just an interested amateur, but how does it follow that SHA-256 has only a 128-bit security level? (More generally about the whole SHA-2 and SHA-3 families.) Also, against what type of attack is this considered?

I looked to Wikipedia which didn't really help my confusion. The cryptanalytic results listed (up to 2014) are all for reduced-rounds variants, and most for SHA-256 are on the order of $2^{250}$ complexity or more. The comparison of SHA functions gives the security of each SHA-2 and SHA-3 family function as half the output hash length, but provides no clarification of how this figure is derived.

Is the security level related to the relationship between the input processing block size and the output hash length?

Please go easy on me with the math; plain English explanations backed up with some math are preferred.

$\endgroup$
  • $\begingroup$ Birthday attacks. $\endgroup$ – man and laptop Jun 4 '15 at 9:44
  • $\begingroup$ @user3491648 Well, that makes some modicum of sense, I suppose. But birthday attacks do have some fairly specific requirements (specifically that the attacker is able to control both inputs) which aren't really generally applicable, right? So how does that justify boiling down the entire "security level" of the hash function to half the hash length? Now, don't get me wrong; I recognize that birthday attacks are valid in some situations (and I should have thought of that) but they aren't always useful. $\endgroup$ – a CVn Jun 4 '15 at 9:47
  • $\begingroup$ One oould use a candidate eTCR hash instead of a candidate collision-resistant hash. $\:$ Otherwise, I'm not aware of any "natural" property one could ask for that is [efficiently falsifiable and [between collision-resistance and second preimage resistance]]. $\;\;\;\;$ $\endgroup$ – user991 Jun 4 '15 at 10:09
  • 1
    $\begingroup$ "Security levels" are (very rough) worst-case estimates agreed upon mostly by consensus, incorporating all publicly known attacks. If birthday attacks don't apply in some scenario, one may well use a hash function whose alleged security level is too low; however one needs to re-evaluate this from case to case. This is why cryptographic engineering generally simplifies these considerations to one single number which implementors can rely on to represent the worst possible security level some primitive can provide. $\endgroup$ – yyyyyyy Jun 4 '15 at 10:10
  • $\begingroup$ @yyyyyyy Sounds to me like the beginnings of a decent answer. $\endgroup$ – a CVn Jun 4 '15 at 10:50
5
$\begingroup$

You can't say SHA-2 has a security level of half its hash length without any given context. 128 bit against what type of attack? What is the attacker trying to do? Perform a collision? Ok yes it has 128 bit against collisions. Perform a preimage? Nope it has 256 bit security against preimage attacks.

Any algorithm is considered n bit strength if the expected number of operations for the average case is 2^n. For unbroken cryptographic hashes the strength is 2^(n/2) against collisions and 2^n against preimages. Collisions are simply "easier" than preimage attacks due to the birthday problem. They take less operations so you need a larger search space (digest length) to achieve the same level of security.

So the statement that SHA-256 has 128 bit security is incomplete and it ignores the fact that collisions are not always relevant. Against many type of scenarios a collision is of no value. An example where collisions are not a threat would be hashed passwords. For an attacker to break a specific password they need to find a preimage of the password hash. In that application SHA-256 has 256 bit security because collisions present no security risk(i.e. attacker determines abc and xyz both hash 1234 and that doesn't match any password hash). It doesn't help that the word collision is used in common language to scenarios which refer to a preimage. Also keep in mind there are two types of preimage attacks and once algorithms become partially compromised they may have differing levels of security depending on if it is a first or second preimage attack. Of course once an algorithm is compromised you should look to migrate to a more secure algorithm but that distinction could be relevant in some situations.

$\endgroup$
  • 1
    $\begingroup$ I'm not sure that password hashing is the best example. A bad break of a hash's collision resistance could cause problems. A contrived example: the hash function $H(x) = C$ for some constant $C$ is pre-image resistant but unsuitable for password hashing (since all passwords hash to the same $C$). $\endgroup$ – Tim McLean Jun 4 '15 at 23:04
1
$\begingroup$

Hmmm. The person who wrote this took quite some liberties. Somewhat unavoidable for the excerpt, because you can't explain all the nuances in a few words, but the wiki body should be more precise.

Roughly speaking, the security level (also called strength) of a cryptographic algorithm is the amount of computation that's necessary to break it. It's the logarithm number of required elementary operations; for example, an algorithm with a 128-bit security level is one that requires $2^{128}$ operations. What counts as one operation is not defined precisely; typically, it's one call to the function in question, and other computations of roughly the same complexity.

The security level does not consider specific attacks: it measures the minimum amount of computation by an optimally clever adversary. In other words, it takes the best known attacks into account.

What is missing in this statement is that the security level considers a specific problem. For example, the security level of AES-128-CBC encryption would be based on decrypting a message without having the key. It's still meaningful to talk about “the security level of AES-128” because the value is the same for all common problems. To state that AES-256 has a 256-bit security level, on the other hand, is not quite true: that's the security level for encryption, but there are problems such as MAC forgery that can be broken by brute-forcing one block's worth, and an AES-256 block is only 128 bits.

A cryptographic hash like SHA-256 has several fundamental properties, and the strength is not the same for all of them:

  • Preimage resistance: given $h$, find $m$ such that $h = \mathrm{SHA256}(m)$. This has a 256-bit security level.
  • Second preimage resistance: given $m_1$, find $m_2$ such that $m_1 \ne m_2$ and $\mathrm{SHA256}(m_1) = \mathrm{SHA256}(m_2)$. This has a 256-bit security level.
  • Collision resistance: find $m_1$ and $m_2$ such that $m_1 \ne m_2$ and $\mathrm{SHA256}(m_1) = \mathrm{SHA256}(m_2)$. This has a (roughly) 128-bit security level because this problem is susceptible to a birthday attack.

As we saw with AES-256, the security level is not necessarily the key size, even for algorithms that are not broken. The key size is not always the determining factor for brute force attacks, just like the hash size is not always the determining factor for a hash. In both cases, birthday attacks halve the security level for problems that only require finding a collision.

Even for encryption algorithms, the security level is not always the key size. That's the case for AES with any key size and decent modes, but here are some examples where it isn't:

  • For DES, a key has only 56 “useful” bits, but is represented as 8 bytes with 8 parity bits. So a 64-bit key only has a 56-bit security level (i.e. the original security level back when the algorithm was considered unbroken, less so now that it's partly broken).
  • 2DES — successive DES operations with two keys — only has a 57-bit theoretical security level because meet-in-the-middle attacks effectively make the second key only double the amount of computations required to break it.
  • 3DES — successive DES with 3 keys — has a 112-bit security level (the strength of two keys).
  • Asymmetric algorithms generally have a security level that's significantly less than their key size, because they're based on mathematical objects which have some structure that allow better attacks than trying all possible keys. The definition of an elementary operation can lead to relatively large variations, so strengths quoted for asymmetric algorithms are estimates. Security strength of RSA in relation with the modulus size is an instructive read on this topic. keylength.com lists references on the strength of some common algorithms.
$\endgroup$

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.