# Security level of the hash of the sum of two uniformly random keys

I generate two uniformly random 127-bit integers $$a$$ and $$b$$.

I calculate $$c=a+b$$, which means $$c$$ can always be represented as a 128-bit integer.

$$c$$ will not be uniformly randomly distributed, but I need to use it as entropy for a private key. I do not have the option of calculating $$c=(a + b)\ mod\ 2^{127}$$.

How can I reason about the security level of the key $$k=H_{128}(c)$$, where $$H_{128}()$$ is a cryptographically secure hash such as SHA256 with the result truncated to 128 bits.

Furthermore, how is the security level of $$k$$ affected if an adversary can control $$b$$. The adversary will have no knowledge of $$a$$, and will attempt to decrypt data I have encrypted using $$k$$.

how is the security level of $$k$$ affected if an adversary can control $$b$$. The adversary will have no knowledge of $$a$$, and will attempt to decrypt data I have encrypted using $$k$$.

I pick the second question first because it happens to be easier to analyze.

Now, if $$H_{128}$$ acts like a random function, it doesn't matter which value of $$b$$ the attacker picks; lets assume he sets it to some arbitrary value that he knows. Then, his best approach would be to select arbitrary values of $$a'$$, compute $$H_{128}(a'+b)$$, and see if that decrypts. A value of $$a'$$ will succeed if:

• He happens to guess $$a$$, that is, $$a = a'$$ - probability $$2^{-127}$$

• He guesses some wrong $$a' \ne a$$, however $$H_{128}(a+b) = H_{128}(a'+b)$$. Because we're modeling $$H_{128}$$ as a random function, that has probability circa $$2^{-128}$$ of happening.

Hence, any guess $$a'$$ has a probability of $$2^{-127}+2^{-128} = 1.5 \cdot 2^{-127}$$ of succeeding. If this is the best attack (and if $$H_{128}$$ is a random function, it is), then we have about 126.5 bits of security (which is not bad, given that there are only 127 bits of entropy, that is, information that the attacker does not know, in the system).

What if the attacker doesn't know $$b$$?

Doing a thorough analysis is a bit more involved; in this case, the optimal attack would involve a search starting at the most likely value of $$a+b = 2^{128}-1$$, and working our way to less likely values; finding the expected amount of work is more than I care to do at the moment.

On the other hand, we can do a quick analysis by observing that the attacker not knowing $$b$$ doesn't make like any easier for him, so we're at least as good as the previous case (126.5 bits of security). And, because we have a 128 bit key, we can't have more than 128 bits of security, and so it's somewhere between 126.5 and 128.