big O for finding hash of length n O(2^n) or O(2^(n-1))?

Question

note The wikipedia article does not use the big O notation correctly. Thus O(2ⁿ) just means 2ⁿ attempts

I read on wikipedia (CGA) that finding a collision preimage for a cryptographich hash of length 59 bit it is approximately O(2⁵⁹) in big O notation. However in my eyes it is O(2⁵⁸) as on average we will find the same output after searching creating half the target namespace (namespace = range 0 up to 2⁵⁹).

I guess it is because of the approximately both statements would be correct? In an academic paper, what is preferrable to use?

So I assume we will on average need to create half of the (target) 59 bit namespace to find a preimage. Now if we would have crypto hash functions that would perfectly distribute the output (which we do not have) over the 59 bit space, we would only need (on average) 2⁵⁸ attempts to find a hash (as 2⁵⁸ distinct inputs would yield 2⁵⁸ distinct outputs, assuming perfect distribution). As stated in the answer we do not have perfect hash functions, thus distinct inputs will give same outputs, thus on average attempt is closer to 2⁵⁹. Thats where the approximately comes from. Am I right?

Answer 1

First, you misread the page: this is not about collisions. The Wikipedia page says:

the cost of finding a set of CGA Parameters that yield the desired 59 bits is approximately O(2⁵⁹)

The important word here is "desired". The attacker wants to find an input that hashes to a specific, given output. This is called a preimage attack. By contrast, a collision attack is about finding two distinct inputs that hash to the same value, without any constraint on that common output value; this is not at all the same thing (and collisions are in fact vastly easier, down to about 2³⁰ evaluations for a 59-bit output).

---

That being said, the average attack cost is indeed 2⁵⁹, not 2⁵⁸, because this is a hash function, not a block cipher. You speak of "searching half the namespace" but there is, in fact, no such thing as a "namespace" in that case.

When you try to brute-force a 59-bit key, there is a defined space of possible keys (all 59-bit sequences) of size 2⁵⁹, and you know that one of them is the solution, and you can try them all in due order, without ever trying twice the same. Under these conditions, you can expect to find the right one after, on average, trying half of the possible keys.

This is not so here. In the case of CGA, the problem is about finding an input (which is quite larger than 59 bits) such that the output is a specific target 59-bit sequence. As you try various possible inputs, you get the corresponding outputs, but (that's the critical point) these outputs are (from your point of view) random (as in "random oracle"), and, in particular, you may get the same one several times. In fact, it is expected that you will get your first duplicate after trying about 2³⁰ inputs or so (that's the so-called birthday paradox), and, as you accumulate such random outputs, you will get more and more collisions. If you try 2⁵⁹ distinct inputs, and hash them all, then you will not get all 2⁵⁹ possible outputs, but substantially fewer (about 63% of them).

In other words, when you do the brute force attack on the hash function, some of your effort is wasted, because it yields 59-bit outputs that you already had with another possible input. This lowers the success rate, and thus increases the overall attack cost.

Assuming the hash function behaves like a random oracle (i.e. no known structural weakness), then the probability of finding the right 59-bit output every time you try some new input is exactly 2^-59, and, by definition, this means that you have to try on average 2⁵⁹ times before finding a match. This is an average: you may get lucky and find a match earlier; you may also get unlucky and find a match later, with no upper limit. This (again) contrasts with the "search the key for a block cipher" situation, where you know that the attack will work after trying, at most, all possible keys; in the preimage attack for a hash function, you do not even get such a guarantee, only an average.

Answer 2

1. O(2⁵⁹) is the same as O(1). Wikipedia is misusing notation.

   It should say

   For a CGA with Sec equal to 0, this means that the cost of finding a set of CGA Parameters that yield the desired 59 bits is approximately 2⁵⁹

2. You are correct that the average cost of finding a value with the same hash is 2⁵⁸. The actual cost might be as little as 1, and it may be as high as 2⁵⁹. The probably of finding it increases linearly with respect attempts. Thus, the average cost is 2⁵⁸.

   That however, assumes a perfect distribution. In the case of an imperfect distribution, it is even less than 2⁵⁸. In the exterme, if everything hashes to the same value, your cost is 1.