How much of SHA3's internal state can be reached?

aiootp

7/21/24, 6:33 PM

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?

1 + 2

cryptanalysis

key-derivation

pseudo-random-function

Henrick Hellström

7/22/24, 3:20 AM

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.

aiootp

7/24/24, 3:50 PM

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.

Score:1

Crypto

poncho

7/21/24, 6:39 PM

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.

+ 2

aiootp

7/21/24, 6:58 PM

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?

poncho

7/21/24, 7:00 PM

@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.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: How much of SHA3's internal state can be reached?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.