Bits of security vs collision resistance?

Question

I have been doing some research on security, and I am confused on the bits of security vs collision resistance, and I was wondering if someone could clarify my understanding.

For instance, if you have an AES has a 128-bit block, being used with a 256-bit key, that provides 256 bits of security, because the key length determines the bits of security in this case.

But if you have SHA-256, that offers 256/2 = 128 bits of collision resistance. Does that mean that the bits of security of SHA256 is 128 bits? Or is bits of collision resistance just in a whole different category than bits of security?

I wrote down what I think captures bits of security based on the type of primitive being used:

1. Bits of security for a block cipher depends on the key length (so like the example above with AES 128 with a 256 bit key)
2. Bits of security for a MAC is min(key bits of security, hash bits of security)
3. Bits of security for a hash function is l/2 or l-bits?

My question is do we aim for bits of collision (when applicable) over bits of security?

Any help is appreciated!!! Thank you!

Answer 1

I am confused on the bits of security vs collision resistance

Well, here is what "bits of security" means; we say that a primitive offers $\ell$ bits of security if the best known attack against that primitive takes roughly $2^\ell$ operations. Yes, that is somewhat imprecise (what is "roughly" and what is an operation?), but it is generally sufficient for discussions.

1. Bits of security for a block cipher depends on the key length (so like the example above with AES 128 with a 256 bit key)

Pretty much (assuming that the block cipher itself doesn't have any nongeneric attacks, and if we don't talk about birthday bound attacks or attacks against the ciphermode).

Nit: in general parlance, "AES 128" is AES with a 128 bit key; we'd call AES with a 256 bit key "AES 256"

2. Bits of security for a MAC is min(key bits of security, hash bits of security)

Well, here is where the general "bits of security" breaks down somewhat. It is impractical to do any operation that does $2^{64}$ sequential steps (even if each step takes a nanosecond, we're talking about more than 500 years). In most cases (e.g. doing a brute force attack against a key), this is not an issue; we can easily run things in parallel (e.g. rent a large number of cloud computers, or use a GPU farm), and so a large organization would have little issue in performing, say, $2^{64}$ operations in aggregate. However, the generic attack against "size of the MAC" would be "generate the message we'd like, insert the guess of the MAC, and send that to the device under attack". Since the device under attack would need to process each guess in succession, we cannot parallelize it (unless we have a large number of devices, all with the valid key; generally not the case), and so, in practice, attacks against the "hash length" (as you term it) are considerably harder than attacks against the key.

3. Bits of security for a hash function is l/2 or l-bits?

Depends on the attack you need to be strong against. If it's a collision attack (that is, the attacker "wins" if he is able to find two messages that hash to the same value), it's at most l/2 (as there are generic attacks that work in $2^{l/2}$ time. On the other hand, if you don't care about a collision attack, and care only about a preimage or a second preimage attack, it can be as much as l-bits (as the best generic attack takes $2^l$ time

Answer 2

The security level of a cipher is relating to the number of operations required to break the cipher where $n$ bits of security means $2^n$ operations are required to break it.

Whereas the security level of a hash function is measured in terms of collision resistance, and pre-image resistance, where $n$ bit security means $2^n$ operations are required to find a collision or pre-image collision.

Collision/pre-image resistance are generally desired properties of hash functions but they are irrelevant to the security of an encryption scheme. Using OTP as an example, it is trivial to create a collision for any given ciphertext, but this doesn't impact the security.