# Iterative hashing increases number of security bits?

Whatsapp uses 5200 iterations of SHA-512 over user's public key and identity according to WhatsApp Security Whitepaper.

I wonder why?

According to: Why iterate 5200 times when computing Safety Numbers in Signal? this question on Information Security.SE: It is to increase security bits to 112.

I do understand why 30 digit number has $$\approx 99$$ bits entropy and so $$\approx 99$$ security bits.

$$\log_2(10)*30 \approx 99$$

But how does iterative hashing affects security bits? It does not affect entropy as far as I understand.

Math in the post indeed shows:

$$\log_2(10^{30} * 5200) \approx 112$$. Which is recommended number of security bits at keylength.com

Moreover, Signal source code comments state that too on the source code

Where can I read more on why '5200' iterations of hashing placed into the 'log' as multiplication and why does it affect security bits at all?

• Adding 1 bit to the strength of a "password" (say, by flipping a coin and appending 0 or 1 based on the result) doubles the number of hashes it would take to crack the password. Doubling the number of iterations also doubles the number of SHA-512 hashes needed to crack a password. The error is that you conflate security and entropy. We treat password stretching as increasing the effective strength of a password (hash). We do not say that the entropy of the outcome of the hash increases, no matter how many times it's iterated. (This isn't quite a password, but it doesn't matter.) Mar 2 '20 at 3:21

how does iterative hashing affects security (measured in) bits?

It does so by increasing the number of operations likely required to solve the problem by brute force, because an operation is what's iterated in each attempt of break.

(iterative hashing) does not affect entropy

Indeed, iterative hashing does not increase¹ entropy. It can still increase security.

$$n$$-bit security means that adversary needs to perform $$2^n$$ operations to break the system.

Yes, for some definition of operation, and certainty to break the system.

If there's an attack with $$N$$ operations that succeeds with probability $$p$$, and $$p$$ grows linearly with $$N$$ until $$p=1$$ as in key search, then the system has at most $$n=\log_2(N/p)=\log_2(N)-\log_2(p)\text{ bit security}$$

This formula works including for low $$p$$ and any $$N\ge1$$. Customarily, it is used also when $$p$$ only grows about linearly with $$N$$ until $$p$$ reaches a non-negligible value, e.g. because $$p=e^{-N_0/N}$$ as in preimage search.

The question's Whatsapp system re-formats 32-byte ECC public keys into 30-decimal digit strings that appear nearly uniformly distributed. The main design goal is to make it hard to generate a private key which matching public key re-formats to one (or more) given strings obtained by re-formatting one (or more) target public key(s); that is, make second preimage search difficult.

A brute force preimage attack against this system generates key pairs; hashes the public key 5200 times with SHA-512; and makes a test against the targeted value(s). Each private key test has probability $$p=10^{-30}$$ to match a given string. Each test costs 5200 iterations of SHA-512 and comparatively little else (an increment of the private key, an ECC point addition of a constant point to the previous public key, typically one (at most 6) comparison against 5 digits of the given string of the modular reduction modulo $$10^5$$ of part of the SHA-512 hash).

It follows that security is $$\log_2(5200)+30\log_2(10)\approx112.00$$-bit when the cost is counted in SHA-512 hashes, which is the natural metric here, and there's a single target key. For $$s$$ target strings/keys, the probability of success of each test is increased by a factor $$s$$, thus security is reduced by $$\log_2(s)$$ bit.

Notes:

A former version of this answer was about the security increase with increased iteration count in a cryptosystem where there are sizably much other operations beyond iterated hashing. That's not relevant in the question's context, thus removed.

¹ : The simplest forms of iterative hashing, including the one in the question's Whatsapp context even slightly reduce entropy; see this.

• Thank you for the explanation. Could you please explain what's $i_0$? As far as I understand – security level, n-bit security means that adversary needs to perform $2^n$ operations to crash break the system. So original security level was $\log_2(10^{30}) \approx 99$ Adding number of hash iterations adds number of operations $\log_2(10^{30}*5200) \approx 112$. Does time affects 'security level' bits in any matter ? Mar 2 '20 at 14:28
• @Alexander Smirnov : I have revised to answer for the Whatsapp context. I'll further tweak it, but not right now.
– fgrieu
Mar 2 '20 at 18:00

The answer you refer is unfortunately misleading. Also the comment in the source code is misleading. The answer you refer does not say that entropy is higher. It uses wording the bits of security which is not standard and is misleading. Some use wording security strength which approximately means to break this algorithm by brute-forcing one needs to try 2^(that many) values. What the author of the answer means is that CPU time needed to calculate a hash with iterations is approximately the same as a single calculation of a longer hash.

But entropy depends on the size of the hash space only. And in particular the probability of hash collisions remains the same.

I answered now the question you refer (see your link and there my answer) and hope I explained it better what some people mean by such misleading wording.

• "But entropy depends on the size of the hash space only." No. If you have a non-uniform statistical distribution of input values, then the hash has less entropy. The size of the input space only can be used in entropy calculations instead of a probability mass function if it is known that the possible value of an unknown input can be modeled as a uniform distribution. It's probabilities, not counts. Mar 2 '20 at 3:02
• @FutureSecurity: You are absolutely right. It''s probabilities, to be more precisely - distribution of probabilities :) But here is only a brief version of my answer in the thread referred. I didn't want to duplicate it. And if you read that answer you will see the remark assuming that hashes are distributed equally :) I will keep this answer as it is, brief, expecting that the main discussion will happen in the thread referred. Mar 2 '20 at 18:30