0
$\begingroup$

Let $B$ denote a non-empty bitstring of arbitrary length. Then let $n$ denote the length of $B$.

The question: does there exist a cryptographic hash function $H$ that outputs a hash $h$ of $B$ such that the length of $h$ is equal to $n$ and collision resistance of $H$ is either $2^{n/2}$ or negligibly less than $2^{n/2}$ (other standard cryptographic properties, such as pre-image resistance equal to $2^n$, are also implied)? If yes, what can be an example of such function?

I should also emphasize that $H$ is allowed to be significantly slower than standard hash functions, and the entire input is allowed to be stored in RAM.

EDIT
Of course, a function with this abstract property is not a standard “hash function” in the usual meaning. One example of similar function would be MD6 compression function (described in Chapter 2.5 and Chapter 9 of the document “The MD6 hash function: A proposal to NIST for SHA-3”), which was designed without any claimed limits on the security level. That is, the security depends on the length of the output, not on the length of the internal block size. It accepts the input of arbitrary length and outputs a truncated bitstring, assuming that the number of rounds increases when the length of the input increases. Yes, the output is truncated (and becomes smaller than the size of the input), but since the input size is variable, we can simply pad the input by any number of bits to obtain the output of any size. One problem is that this function requires an additional algorithm (described in Chapter 9.2 of the document) to detect what specific parameters will be optimal for the corresponding length of the input. This is different from Keccak family of fixed pseudo-random permutations, which is designed without any additional optimizing algorithms for different block sizes (1600, 800, 400, ...). Also, non-iterative cryptographic hash functions may be relevant.

$\endgroup$
  • $\begingroup$ An XOF (like SHAKE) should come close even though their collision resistance is usually fixed-bounded. $\endgroup$ – SEJPM Sep 29 '18 at 15:49
  • $\begingroup$ Keccak-based hash function will satisfy the described requirement, but if and only if I will extend the underlying permutation to 3200, 6400 bits etc., which would be very problematic. $\endgroup$ – lyrically wicked Sep 29 '18 at 16:05
  • 1
    $\begingroup$ Which begs the question why you would need a hash with more than 256 bit collision resistance? $\endgroup$ – SEJPM Sep 29 '18 at 16:08
  • $\begingroup$ @SEJPM: I don't need such function for practical purposes. I am only interested in a possible cryptographic hash function that is expected to match the described property. It's nothing more than abstract problem that I would want to see a possible solution to. $\endgroup$ – lyrically wicked Sep 30 '18 at 2:14
1
$\begingroup$

I am not entirely sure I got your question right, so let me rephrase it: you want a function $H$, that takes as inputs strings of bits, and outputs other strings of bits, such that:

  • There is nothing secret in $H$; it is deterministic, easily computable, and uses no secret key.
  • If $m$ has length $k$ bits, then $H(m)$ also has length exactly $k$ bits.
  • It should be computationally hard to find two distinct inputs $m$ and $m'$ (with the same common length $k$ bits) such that $H(m) = H(m')$. The "hardness" here means that the effort to find a collision should be at least in $O(2^{k/2})$.

With these requirements, a very simple solution is to use the identity, i.e. $H(m) = m$ for all strings $m$. The identity can be computed very efficiently: it has cost zero. There are no collisions at all, so the hardness of finding a collision is infinite. However, I suppose that the identity is not appropriate in your use case; i.e. you actually want more than just "resistance to collisions".

So let's add some extra requirements. You want a publicly computable function $H$ that preserves length ($H(m)$ has the same length, in bits, as $m$, for all strings $m$), and that fulfill the three classical notions of security for hash functions:

  • Resistance to preimages: given output $t$, it should be computationally hard to find input $m$ such that $H(m) = t$.
  • Resistance to second preimages: given input $m$, it should be computationally hard to find input $m'$ such that $m\neq m'$ but $H(m) = H(m')$.
  • Resistance to collisions: given a bit length $k$, it should be computationally hard to find inputs $m$ and $m'$ of length $k$ bits, such that $m\neq m'$ but $H(m) = H(m')$.

Note that, in our case, we must use the bit length as parameter. In usual hash function, the input length is arbitrary but the output length is fixed an implicit in the definition of the hash function. For your function $H$, you must add the bit length $k$ as parameter to the security notions. For preimages and second preimages, this is easily obtained as the length of the challenge: when I give you $t$ and challenge you to find $m$ such that $H(m) = t$, then I also necessarily give you the bit length $k$, which is the length of $t$. But for the "collisions" challenge, I must specify the bit length $k$ explicitly, otherwise you could (smugly) solve the problem for a very short length, and show me that collision.

The variable-length property of $H$ makes the problem a bit harder to analyze. With a normal hash function with a fixed output size ($k$ bits), but accepting inputs of arbitrary sizes, it can be shown that the best resistances you can hope for are on the order of $2^k$ for preimages and second preimages, and $2^{k/2}$ for collisions. However, with a length-preserving function, you can get farther some of these limits; indeed, if you use the identity (i.e. $H(m) = m$), then resistance to preimages is nil (simply set $t = m$) but resistance to second preimages and collisions is infinite (there is simply no collision at all).

All of that being said, an easy solution is to use a key derivation function. One standard KDF is HKDF: it can take inputs of arbitrary size, and produce outputs of configurable size, so you can simply use HKDF with an output size equal to the input size. This has some caveats, though:

  • Maximum output size of HKDF is limited to 255 times the output size of the underlying hash function. If you build HKDF over SHA-256, then you will get an output of at most 8160 bytes (65280 bits).

  • You will heuristically get your collision resistance target ($2^{k/2}$) but, again, only up to some limit. If the internal hash function is SHA-256, then for $k \gt 256$, you might not get more than $2^{128}$ resistance to collisions. This does not matter in practice, since anything beyond about $2^{100}$ is equivalent to infinite for the foreseeable future.

Another candidate is SHAKE, one of the variants of SHA-3. SHA-3 is based on Keccak, a "sponge function" in which you first accumulate the input into an internal state, then produce output from that state; with "plain" SHA-3 you just get enough bits to reach the defined output size for the hash function, but with SHAKE you let it flow for as long as you want. If you define $H$ to be "SHAKE256, with an output size equal to the input size", then you should get a reasonable solution. Note that SHAKE output size is not practically limited; however, like with HKDF, there is an internal limit which will set a maximum to the collision resistance you can hope for, in a theoretical point of view.

(Having such a limit is mostly necessary for any function that works but first absorbing the data into an internal fixed-size state, then producing output deterministically from that state alone. This should not be a problem in practice, since you can put that limit far away into the land of "cannot do that in practice". If you want to talk theory with adversaries of truly unlimited power, then take care that there is no known proof that secure hash functions can actually exist at all.)

$\endgroup$
  • $\begingroup$ But since both these solutions (SHA-256-based HKDF and unmodified Keccak-based SHAKE) have the theoretical limit on the collision resistance, they don't satisfy the theoretical property that I described. I am looking for a theoretically possible cryptographic hash function that fully satisfies this property. $\endgroup$ – lyrically wicked Sep 29 '18 at 16:47
  • $\begingroup$ On a pure theoretical / math point of view, we don’t even know if hash functions can exist at all. Therefore, your question can only be answered with heuristic arguments of the kind “we don’t know how to break this faster than that”. These arguments tend not to make sense outside of the realm of the physically feasible. $\endgroup$ – Thomas Pornin Sep 30 '18 at 1:22
  • $\begingroup$ I edited the question to add a detailed clarification. $\endgroup$ – lyrically wicked Sep 30 '18 at 2:09

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.