3
$\begingroup$

In the SHA-3 standard (page 31) the security of SHA-3 is defined quantitatively, for example, they are saying SHA3-256 provides 256 bits of preimage resistance. How is this number of bits to be interpreted?

The definition of preimage resistance that I know doesn't speak of bits, but of a running time $t$ (and a success probability $\epsilon$).

Intuitively, I'd interpret it like this: An attacker can only find a preimage (with a decent probability) after running $t = 2^{256} \cdot t_H$, where $t_H$ is the time required to calculate one hash. Is that correct?

Bonus: Is there a (citable) source for this? The SHA-3 standard has shockingly few references, and the Keccak reference doesn't speak about preimage resistance at all.

Improve this question
$\endgroup$
  • 1
    $\begingroup$ The Keccak reference does talk about preimage resistance... this is part of the "flat sponge claim". $\endgroup$ – Aleph Jan 29 '19 at 16:38
6
$\begingroup$

Aleph's comment and pointer to the Keccak reference goes a very long way to answering this question (p. 9):

Keccak security claim

The key words here are "workload equivalent to $N$ calls to $\mathrm{Keccak-}f[r + c]$ or its inverse." Invocations of the Keccak permutation are being used as the unit of time. Your intuitive take that it's hash function invocations isn't very far off from this, but note that a single SHA-3 call may result in one or more permutation calls, so Claim 1 is more stringent.

In a more abstract setting, where we're talking about the sponge construction in general and not a concrete implementation like Keccak, we talk about the permutation (and its inverse) as an oracle that the adversary can freely call (often people say "query") as they see fit. Then the security of the construction is expressed in terms of how many queries the adversary makes. The oracle calls are treated as outputting the result of a random permutation in constant time.

See also: the Keccak team's more generic treatment of sponge functions.

Improve this answer
$\endgroup$
  • $\begingroup$ but note that a single SHA-3 call may result in one or more permutation calls – this is however in the order of the number of rounds, right? So the success probability would only be slightly higher when allowing $2^n$ hash evaluations? $\endgroup$ – Marian Jan 30 '19 at 12:25
  • $\begingroup$ But actually my question is more general, how do NIST define their security levels? In the linked standard, they also give numbers for SHA2's preimage resistance (also 256 bits for SHA256), which cannot be defined in terms of Keccak permutation calls. Do they use my $2^n$ definition (justified as in my comment above)? $\endgroup$ – Marian Jan 30 '19 at 12:28
  • 1
    $\begingroup$ @Marian NIST defines bits of security in this way $\endgroup$ – Ruggero Jan 30 '19 at 12:58
  • $\begingroup$ @Ruggero Great, thanks, that was sort of what I was searching for, I was just expecting it to be a little more complicated. So indeed their definition is even looser than mine and they sweep all of our discussion above under the $\mathcal O$ carpet ;) $\endgroup$ – Marian Jan 30 '19 at 16:13
0
$\begingroup$

How is this number of bits to be interpreted?

In Cryptography we talk about the number of bits. 256 bits means that you need to search in $2^{256}$ elements or say 256-bit search space.

Running time is a vague term. What is the CPU, memory, computer, server, hardware are you talking about? This and the other not mentioned ones can change the running time.

The definition of preimage resistance that, but of a running time $t$ (and a success probability $\epsilon$).

It is the formalization of running time as done in CS for big-Oh ($\mathcal{O}$) notation. We consider polynomial time adversaries so that we set a bound for them otherwise we cannot talk about unbounded adversaries.

So we say a polynomial time adversary with $\epsilon$ advantage. If the epsilon is negligible then the adversary has no advantage.

An attacker can only find a preimage (with a decent probability) after running $t = 2^{256} \cdot t_H$, where $t_H$ is the time required to calculate one hash. Is that correct?

Again, In Cryptography the running time is not considered while calculating the security. However, when designing people consider fast and secure algorithms are better. But, this has a drawback in hash function since searcing a preimage is shorter. And, similarly for block ciphers,too, shorter brute-force time.

Bonus:

See Rogaway at al. Cryptographic Hash-Function Basic as already you looked and a good Cryptography book as Katz-Lindell's book.

Improve this answer
$\endgroup$
  • $\begingroup$ I think you got a little caught by that "New contributor" note near my name – My question was a bit deeper than what you replied to. Thank you anyway! $\endgroup$ – Marian Jan 30 '19 at 11:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.