If secret S is not known to an attacker, while constant K and SHA3(K + SHA3(S)) are known to an attacker, is S discoverable?

Question

I'm trying to understand how secure S is from an attacker. Let's say in an instance where they have enormous hashing power available to them, as would be the case where they own cryptocurrency mining rigs.

In other words, the attacker must not be able to find out the secret S:

• S = "my secret phrase"

But the attacker has full knowledge of both:

• constant K = "a publicly known constant"
• a combined hash of both K and the hash of S = SHA3(K + SHA3(S)) = 9cc2679d4eb37c26cb82db4fdec8ac3787b3eff6efd18ec839397798a9ed402f

Answer 1

• First look at $\operatorname{SHA3}(S)$

  $\operatorname{SHA3}$ is a cryptographic hash function built for pre-image, secondary pre-image, and collision resistance. If you use $\operatorname{SHA3}-512$ then you will get 512-bit first and second pre-image resistance and 256-bit collision resistance.

  In your case, the pre-image resistance is important and the success of finding the pre-image is a negligible event. On average the attacker needs to try $2^{512}$ different inputs to find a pre-image.

  The only problematic case here is the size of the secret. If the secret is smaller the 512-bit then the pre-image security is not 512-bit, it is $= \min\{512,bitLen(secret)\}$ since the attacker needs to search only this space. Therefore keep the secret at least larger than 256^‡ bit to achieve at least 256-bit security.

• $h = \operatorname{SHA3}(K + \operatorname{SHA3}(S))$

  The attacher gets the $K$ and $h$. As above, this time with full pre-image (512-bit) resistance will prevent the attacker to get $SHA3(S)$ yet alone accessing $S$. However, they can still search for $S$ so still, we have $ \min\{512,bitLen(secret)\}$ security. Good secret size for $S$ is required, again.

Even a single $\operatorname{SHA3}$ call is enough, the double $\operatorname{SHA3}$ call is overkill with a good key (secret) size.

Your construction is similar to HMAC where the double hash is used since MD hash functions are vulnerable to length extension attacks. SHA3, on the other hand, has resistance to this like BLAKE2.

There is already MAC construction from SHA3 called KMAC which is in simple terms thanks to resistance to length extension attacks

$$\operatorname{KMAC}(key,m) = \operatorname{SHA3}( key\mathbin\|m)$$

in your notation

$$\operatorname{KMAC}(S,K) = \operatorname{SHA3}( S\mathbin\|K)$$

This is secure a secure MAC and doesn't reveal the key to the attacker by any means. You can simply use KMAC to achieve what you want with a good key size!

_{^‡Some may argue that 128-bit security is enough. However, future developments like Cryptographical Quantum computers are a threat to 128-bit pre-images of hash functions and as a countermeasure to multi-target attacks, too, one should use at least 256-bit security.}

Answer 2

I'm trying to understand how secure S is from an attacker.

To attack a single instance (with a specific value of K), the only attack available to the attacker is to take a huge number of guesses at $S$; compute $SHA3(K+SHA3(S))$ for each one, and check to see if the target value happens to occur. This can be easily seen by observing that this tag is a function of $SHA3(S)$ - we believe that SHA3 is preimage resistant.

Now, if the attacker has a large number of tags (all with the same K), he could attack them in parallel - either by comparing the computed value against all the target tags, or (if he doesn't have all the tags available at once) building a rainbow table. However, neither approach reduces the time taken to attack a specific tag.

So, to answer your question: how secure S is would depend on how unguessable it is. If it is a single phrase such as 'my secret phrase', well, that might be one of the values an attacker tries early, and so he would find it quickly. On the other hand, if the secret phrase is, say CNjlOQn,FXyEPAxNSYz/0VAP0Gxd,osl4zQlXQNqE7K5gPjiwld3n1f$rcmh well, it would appear to be a pretty safe bet that the attacker would not happen to try that value.