6
$\begingroup$

This is a theoretical question, to improve my understanding of hash functions. Hash functions have a one-wayness such that they are protected from the first preimage attack. From my understanding, if $H(X)=Y$, knowing $Y$, I should not be able to know $X$ is the fundamental behind the first preimage attack.

The question: Does the security of a hash function from the preimage attack also depend on the secrecy of the length of $X$?

If the adversary knows the length of $X$, then it can easily brute force $X$ for smaller lengths of $X$. I understand that smaller length of $X$ will get appended and pre-processed into larger blocks but that does not stop the adversary from brute-forcing since there are no secrets in the pre-processing.

$\endgroup$
  • $\begingroup$ In general, The length of message will be encoded as a part of input for hash function, such as SHA1, SHA3, MD5, SM3. This make it harder to find a preimage. So it means that find a collision by image is hard. When make the length of message encoded in input, find a collision will be harder. $\endgroup$ – Land Jun 7 at 4:50
5
$\begingroup$

I think you are misinterpreting the security notion of pre-images. That $X$ is considered unknown for a $Y$ doesn't make $X$ a secret in the cryptographic sense. My answer basically evolves around this.

From my understanding, if $H(X)=Y$, knowing $Y$, I should not be able to know $X$ is the fundamental behind the first preimage attack.

First of all, somebody could have hashed my name, and I certainly know my name. It should not be computationally feasible to find $X$ given $Y$, using reverse computations. That's different from knowing $X$ if you have $Y$. Brute force is excluded from that notion, of course you can e.g. try all names from this Q/A site and find that it $Y$ is the hash over my name.

Does the security of a hash function from the preimage attack also depend on the secrecy of the length of $X$.

No, because this is not about the size of the input domain; it's about reversing the operation. Getting $X$ from $H(X)=Y$ is only computationally infeasible for a random $Y$, for which there is no indication on the possible values of $X$ - and yes, that includes size. $Y$ might as well be picked at random for the notion of security. Finding any $X$ from the near infinite input domain would then break the security of the algorithm.

$X$ is not considered to be a secret at all for within the security notion of a secure hash. However, if $X$ is defined to be a randomized secret by you then brute force would be the only way of finding $X$ given $Y$. In that case you would have to adhere to the normal requirements for a secret key, say 128 bits of securely randomized bits (brute force in $2^{127}$ on average). Or an equivalent input domain for your subset of all possible values of $X$.

If the adversary knows the length of X, then it can easily brute force X for smaller lengths of X.

Let's simplify that. It takes $2^n - 1$ hash operations to test all values that have a bit size that is smaller than $n$: $2^0 + 2^1 + \dots + 2^{n - 1} = 2^n - 1$ after all. So smaller lengths of X are always relatively easy to crack; you just start with the smallest sizes and work your way up.

So testing all bit values up and including $n$ only takes about $2 \cdot 2^n$ operations. Twice as much work doesn't make much of an impact on an exponential scale. It takes even less computing time if the input is a number of bytes, as many bit sizes don't need to be tested.

In other words, there is already a problem if the adversary knows that the length of $X$ is sufficiently small for them to brute force it; the adversary doesn't need to know the exact size. Double the effort will test all possible smaller values.

I understand that smaller length of X will get appended and pre-processed into larger blocks but that does not stop the adversary from brute-forcing since there are no secrets in the pre-processing.

Nothing will stop a adversary from brute forcing $X$ except from having the possible values of $X$ being well distributed over a sufficiently large input domain.


Due to various attacks, if you want to use a secret with a hash you should use a well vetted keyed hash such as HMAC (or KMAC for SHA-3) as already indicated in the other answer. In that case you have two input parameters: a key and the message instead of just the message for a secure hash.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for your answer. Your last statement above "Nothing will stop a adversary from brute forcing X except from having the possible values of X being well distributed over a sufficiently large input domain.", is exactly my point. However, I do not see it commonly documented. The output size of the hash is documented very well but no requirements on the input sizes. There are applications where the hash is used to ensure the integrity of the inputs but not reveal the inputs. For those applications, the size of the inputs becomes an important criterion to ensure secrecy of the input. $\endgroup$ – Cryptography Learner Jun 8 at 0:56
  • $\begingroup$ Given that the input length is always a number of bytes and all input byte values are equally probably, also brute-forcing the shorter inputs increases the effort required by less than 0.5%. $\endgroup$ – Marcel Waldvogel Jun 8 at 8:52
  • $\begingroup$ Knowing an upper bound for the input length might make a big difference to an attacker, who might be more tempted to start a brute-force attack if she knows that there is a guarantee to succeed with a particular amount of work. $\endgroup$ – Marcel Waldvogel Jun 8 at 8:53
  • $\begingroup$ Interesting how little extra effort is required for the smaller sizes; I didn't do the calculations. As for the size issue: true, but keeping the size secret is actually against Kerckhoff's principle. That basically means that you simply have to use a secure size for the input message that is marked as a secret. Yeah, knowing the size may be an incentive, but the attacker may well decide to brute force not knowing the size anyway. $\endgroup$ – Maarten Bodewes Jun 8 at 15:10
5
$\begingroup$

The questions

  1. Does the security of a hash function from the preimage attack also depend on the secrecy of the length of X.?

The preimage attack: given a hash function $h$ and a hash value $y$ the computationally bounded adversary tries to find a pre-image $x$ such that $y = h(x)$.

This is like an adversary trying to find a password given the hash of it with the known hash function. Note that one doesn't need to find the actual input value for the success of the pre-image attack. Any password with the same hash value will be work for the adversary.

There is no known practically successful pre-image attack on any cryptographic hash functions, even those that are practically broken with collision attacks like MD5 and SHA-1. There is a pre-image attack on MD5 that requires $2^{123.4}$ complexity by Sasaki and Aoki Finding Preimages in Full MD5 Faster than Exhaustive Search in 2009. This is still far from practical usage though it is faster than direct searching.

To hash a value one needs to apply the standard encoding of the message that includes the padding mechanism so that the hash fits into the block size of the hash function. NIST defines them for their standards. The block size can be like 512 bits in SHA256 or 1024 bits in SHA512.

If ever we find a successful pre-image attack, it will also reveal the size of the found pre-image and that was not necessarily the input used to generate the hash value. The padding mechanism, however, can prevent some attacks. Usually, the adversary has lots of freeness for the attack since hash functions can hash any size. This is used in SHA-1 collision attack (identical-prefix collision attack). If the size is limited, that can be a big problem too.

  1. If the adversary knows the length of X, then it can easily brute force X for smaller lengths of X. I understand that smaller lengths of X will get appended and pre-processed into larger blocks but that does not stop the adversary from brute-forcing since there are no secrets in the pre-processing.

If the message space is small, then the adversary simply brute-forces all possible inputs. The current computational capabilities of the adversaries can be evaluated from public information. For example, the bitcoin miners reached $\approx 2^{92}$ SHA-256 hashes per year on 06 August 2019.

During the candidate input generation and testing the hash value, the adversary will also apply the padding mechanism.

for each candidate in [0..2^t]
    paddedCandiate = pad(candidate)
    if hash(paddedCandiate) == y
       return candidate

where $t$ is the predetermined bound. This search space can be easily parallelized by dividing space into segments.

The padding mechanism is not a secret and nothing to do with the secrecy of the mechanism. In unkeyed hash functions, there is no secret.

If you fear that your small input space is vulnerable, you might look at keyed hash functions like HMAC, KMAC.

| improve this answer | |
$\endgroup$
  • $\begingroup$ "If ever we find a successful pre-image attack, it will also reveal the input size since it finds the input." conflicts with "Note that one doesn't need to find the actual input value for the success of the pre-image attack. Any password with the same hash value will be work for the adversary." $\endgroup$ – Marcel Waldvogel Jun 8 at 8:57
  • $\begingroup$ @MarcelWaldvogel Yes, it should be a not the. I hope I made it more non-conflicting. $\endgroup$ – kelalaka Jun 8 at 9:08
2
$\begingroup$

If $f$ is a cryptographically secure hash function and $X$ is kept secret while $f(X)=Y$ is published, then an attacker can find $X$ if and only if $X$ contains too little entropy. That is, there are too few possibilities what $X$ may be, and the attacker can try them all out and test if $Y$ results.

Knowing only the length of $X$ does not help, given that $X$ is not too short.

| improve this answer | |
$\endgroup$

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.