Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
Let's say we have keyed hash function which transforms $256$-bit input into $256$-bit output and the attacker knows the key (let's say the key is $256$-bit long). Now let's consider we will construct an input block as:
Now output could be kind of randomized. I think there is no way to find the $128$-bit message. Am I right? Is the message safe in this case?
If we consider the keyed hash function with $\ell=256$ keyspace than we can formalize as
$$H(k,m): \{0,1\}^{\ell} \times \{0,1\}^{256} \to \{0,1\}^{256}$$
Now assume that $H$ is a Cryptographically Secure keyed Hash function. That hash has pre-image, second pre-image, and collision resistance. The cryptographic strength of this hash functions is like the HMAC, the strength depends upon the size of the secret key that is used. Assuming that we have good enough key size from brute force $\ell > 128$ and the $H$ has no other weakness.
Now, assume that the attacker knows the key, in this case, it is just a usual hash function.
I think there is no way to find the 128-bit message. Am I right? Is the message safe in this case?
To find the actual message, the attacker needs to execute a pre-image attack. That has a cost of $\mathcal{O}(2^{256})$ since the attackers know the key. The pre-image attack can return an input $x$ such that $H(x) = target$ and the $x$ can be different than the 128-bit message or it can return many messages that one is the target.
The attacker has a better way since the input is 128-bit. They can search for the 128-bit. 128-bit is still beyond the search and considered secure. The collective power of Bitcoin miners can reach $\approx 2^{92}$ in a year, and one still needs $2^{36}$ years to reach a 128-bit search. In this calculation, the random 128-bit is discarded since it is not part of the security. If the random is considered secret (it shouldn't), then the attacker's job is just the pre-image.
Now output could be kind of randomized
We expect from the hash function to have avalanche criteria that is a bit change in the input should flip each output bit with 50% probability. The avalanche criteria is an important design criterion since if a few bit changes it may easier to find some collisions.
A special note: fixing a key to a keyed hash functions need a special analysis. Some keys can turn the hash function into a weak hash function. Since we don't know the hash function and the key we can not talk about this.
