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

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

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

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) 258 attempts to find a hash (as 258 distinct inputs would yield 258 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 259. Thats where the approximately comes from. Am I right?

• In big O notation, O(2^{59})=O(2^{58})=O(1), and even if it is really a function of n, O(2^n)=O(2^{n-1}). What the cryptographers actually mean when they misuse the notation in such statements is beyond me. Commented Jun 10, 2015 at 13:37
• Strictly speaking, cryptographers do not misues the big O notation -- the Wikipedia page does, but that's Wikipedia. Cryptographers say "2^59" without the "O", and mean "2^59 evaluations of the attacked hash function". Commented Jun 10, 2015 at 14:10
• Note that O(2^n)=O(2^{n-1}) holds. Commented Jun 10, 2015 at 16:19

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

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 230 evaluations for a 59-bit output).

That being said, the average attack cost is indeed 259, not 258, 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 259, 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 230 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 259 distinct inputs, and hash them all, then you will not get all 259 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 259 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.

• Hi thanks for your answer. I updated my question as it is indeed not very clear. (hopefully its better now) With the last part of your question I do not agree on totally. The "exact" attempt on average value is in my eyes somewhere inbetween 2^58 and 2^59. Likely very much closer to 2^59, see my update... Commented Jun 10, 2015 at 13:44
• You keep talking about collisions, which is wrong. This is not a question of collisions. Thinking about it in terms of collisions is a wrong method and is bound to lead to incorrect conclusions. The same can be said about "namespaces": this is not the right mathematical tool for this problem. Commented Jun 10, 2015 at 14:09
• I dont see why my wording is not OK here. When doing a preimage attack, we will try different inputs and check wether the outputs "collide" with the given hash. For the "namespace" issue do you have a better suggestion? I would say it is a valuespace, but never heard this wording Commented Jun 10, 2015 at 14:49
• Beside still thinking "collision" is a correct word here, it seems not to be used in this context thus I removed it to prevent confusion Commented Jun 10, 2015 at 15:14
• @yyannecc In this field, "collision" is a term of art and as thus has a very specific meaning, far more limited than it might apply in general English discourse. Commented Jun 11, 2015 at 0:30
1. O(259) 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 259

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

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

• thanks for answering. to 1: yes I already updated the question and moved the note to the top. Maybe I should just substitute that big O notation. 2: What still is not clear to be is if - on average - really 2^59 attempts are needed. See the second part of my question. I think the exact value for average attempts is somewhere in between 2^58 and 2^59 Commented Jun 10, 2015 at 19:46
• @yyannecc, yes if you are concerned with the average cost, that is indeed 2^58. I will update my answer. Commented Jun 10, 2015 at 19:49
• mh I disagree. The cost on average would be 2^58 if we would have a perfect hash distribution which is not reallistic. See the other answer. Creating 2^58 hashes would only cover about 63% of the 2^58 bit space as collisions would occure. Thus the exact value is somewhere in between 2^58 and 2^59 Commented Jun 10, 2015 at 20:18
• @yyannecc, no if you have an imperfect hash distribution, then it is even less than 2^58. If you hash to the same value every time, your cost is 1. Commented Jun 10, 2015 at 23:35
• @yyannecc: what you call a "perfect hash" would make sense only if the input space was of the same size as the output space, which is not the case here. Since the input space is larger than the output space, collisions are inevitable, and, most importantly, the attacker can force it (by using random inputs in the larger space). Thus, the best that you can hope for is a random oracle. In that sense, if you found your "perfect hash", cryptographers would call it a "weak, biased hash" and it would lower security. Commented Jun 11, 2015 at 0:48