Iterative hashing increases number of security bits?

Question

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?

Answer 1

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.

Answer 2

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.