0
$\begingroup$

After reading that about "37% of the 256-bit outputs" of SHA-256 are unreachable when fed only 256-bit inputs [1] I'm curious & confused. The formula from the proof here considers a fixed "h-bit" input & output. How does this translate to the maximum number of internal states that are reachable within SHA3?

Does this mean ~37% of the internal states of SHA3 are unreachable after each of its $f$-function evaluations? I'm thinking it's analogous because $f$ takes a 200-byte internal state & produces a new 200-byte internal state. Is that correct?

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ None of your sources are actually about the internal states of hash function. Rather, they answer the question how much entropy you loose, if you repeatedly hash a fixed size input, to a same size output, even if the hash function is a perfect random oracle. $\endgroup$
    – Henrick Hellström
    Commented Jul 22, 2023 at 3:20
  • $\begingroup$ I'm still wrapping my head around the differences between random permutations & random functions. It's quite confusing to me how SHA3's f function could be a bijective permutation when it's doing a bunch of indexed XOR, NOT & AND operations. It seems it should be very likely to introduce hamming differences between its inputs & outputs, which wouldn't be a reshuffling of bits, but a new set of bits altogether. This made me believe that f couldn't actually be a random permutation, but a random function instead. Clearly, my intuition is obstructing my path to understanding. $\endgroup$
    – aiootp
    Commented Jul 24, 2023 at 15:50
  • 1
    $\begingroup$ Entropy preservation through cryptographic hash function $\endgroup$
    – kelalaka
    Commented Sep 12, 2023 at 15:25

1 Answer 1

Reset to default
1
$\begingroup$

How does this translate to the maximum number of internal states that are reachable within SHA3?

That depends on what you're asking.

If you are considering only 256 bit inputs (which the SHA-256 question did), well, there will be precisely [1] $2^{256}$ states reached (which is far below the 37% value of SHA-256).

On the other hand, if you are considering arbitrary length inputs (which you didn't for the case for SHA-256), it looks quite likely that all states are reachable.

Remember, all the rate bits can be set to anything (by setting the next message block appropriately).

So, the question is: given that the rate bits can be anything, are there any set of 'capacity bit' settings which are unreachable. That is, if the output of the permutation has the capacity bits within that set, then the capacity bits of the input must also be in that set (and that set does not contain the 'all 0' setting - that's what SHA-3 starts with).

We don't know whether this is true - apriori, this looks quite unlikely.

[1]: This is "precisely" because two different 256 bit inputs will never result in the same state - we're not filling up the rate bits (and so collision while inputting the bits), and because the permutation will never cause a collision.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Yes, I am considering arbitrary length inputs & the maximum number of internal states that can be reached -after- f does its work on the internal state. You saying that it's quite likely all states can be reached makes a lot of sense to me if f is a permutation which has unique outputs for each unique input (that would make it a bijective permutation?). I was unaware that f had that property though. Is that what you're saying? $\endgroup$
    – aiootp
    Commented Jul 21, 2023 at 18:58
  • 1
    $\begingroup$ @aiootp: well, a random permutation has an extremely high probability of having that property, hence we can expect that the specific permutation f also does. $\endgroup$
    – poncho
    Commented Jul 21, 2023 at 19:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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