Optimal compression ratio in compression function [closed]

So we'll have a transform that maps any of $A=2^a$ possible inputs to $B=2^b$ possible outputs. $a$ is generally fixed as the number of bits in the input, and $b$ is determined by the transform used. We'll name the difference $d=a-b$.

There's 3 main groups:

• $d$ is large and the output is much shorter than the input - we see this in SHA1, SHA2 and a lot of other hashes like it, where they use it to absorb blocks.

• $d=0$, so it's bijective. As far as I know SHA3 is the only hash that does this, and it has a large hidden internal state. Side question, for cases where there isn't some extra internal state, it being bijective implies it's reversible, which is quite bad for hashes right?

• $d<1$ is small and the output is the same length as the input - a compression function, the interesting one and the one I'm concerned with. Around what value of $d$ should I aim for? Some considerations are obvious, like keep $d$ very small if the transform is iterated such as in a password hash, but otherwise I'm at a loss. Of course we can't just choose $d$ since it's based on the transform, but we can design the transform and pick constants to get $d$ around the desired value. So what order of magnitude should $d$ be? Maybe $d\approx a^{-\frac{1}{2}}$?

Main purpose of this is for hashing. I was going to try making my own hash.

closed as unclear what you're asking by tylo, e-sushiSep 18 '17 at 15:26

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

• Same size input and output space does not a bijective function make. – Meir Maor Sep 17 '17 at 7:12
• Please expand aim for. Are you writing your own hash function and are asking about the Merkle Damgard architecture? – Paul Uszak Sep 17 '17 at 7:47
• Also fundamental: bijective does not mean easy to reverse due to size of output space. Try matching up (e.g.) 256 bits of output with it's corresponding 256 bits of input... – Paul Uszak Sep 17 '17 at 8:13
• To be picky: common standard hash functions (including MD5 and of the SHA family) accept variable-size messages and have an input space with $A=2^{(2^k)}-1$ elements, with $k=64$ or $k=128$, not matching $A=2^a$ for any integer $a$. – fgrieu Sep 17 '17 at 20:05
• It's quite unclear what your goal is. How large should $d$ be depends on your goal - or if it even makes sense to have a fixed $d$. Also, with $d$ being a integer as defined in the beginning and assuming $d \geq 0$ (you don't mention expansions), $d < 1$ is equal to $d = 0$. – tylo Sep 18 '17 at 14:03

You said ‘hash’, but you didn't say what properties you wanted. For example, the ChaCha core $$C\colon \{0,1\}^{256} \times \{0,1\}^{128} \to \{0,1\}^{512}$$ is called a hash function and used in CTR mode to make a one-time pad $$C(k, 0) \mathbin\| C(k, 1) \mathbin\| \cdots$$ to encrypt a message under key $$k$$. Poly1305 is called a universal hash function family and is used to make a one-time authenticator for a message under a single-use secret key, but is useless for encrypting messages.

Are you talking about building a variable-size collision-/preimage-/second-preimage-resistant unkeyed function $$H\colon \{0,1\}^* \to \{0,1\}^n$$ out of a fixed-size function $$f\colon \{0,1\}^a \to \{0,1\}^b$$? That's one of the outmoded definitions of ‘hash function’ in cryptography—outmoded because there are other properties like (enhanced) target collision resistance, prefix-PRF, etc., that turn out to be at least as important in protocol design, and are sometimes summarized as indifferentiability from a random oracle. And if that is what you're looking for, it's hard to imagine how $$d$$ could turn out to be anything other than a nonnegative integer.

But assuming that is what you're looking for, here are some comments on common values of $$a$$, $$b$$, and $$d$$:

The design principle of SHA-256 is to iterate a block cipher $$E_k$$ in Davies–Meyer form:

1. Break the padded message into 512-bit chunks $$m_0, m_1, \dots, m_{\ell - 1}$$.
2. Let $$h_{-1} = \mathrm{IV}$$ be the standard 256-bit initialization vector.
3. Compute $$h_i = E_{m_i}(h_{i - 1}) \oplus h_{i - 1}$$.
4. Reveal $$h_{\ell - 1}$$ as the hash.

Here a = 768 and b = 256, so d = 512.

The design principle of BLAKE2 is similar, except it uses a tweakable block cipher $$E_{k,t}(m)$$ instead of an ordinary block cipher, in HAIFA form, which fixes some potential pathologies of naive Davies–Meyer or Merkle–Damgård form, so that it goes beyond collision and second-preimage-resistance to simulate a random oracle in other dimensions.

The design principle of SHA3-256 is to iterate a fixed permutation $$\pi$$ in sponge form:

1. Break the padded message into 1088-bit chunks $$m_0, m_1, \dots, m_{\ell - 1}$$.
2. Let $$h_{-1} = 0^{1600}$$.
3. Compute $$h_i = \pi(h_{i - 1} \oplus (m_i \mathbin\| 0^{512}))$$.
4. Reveal the first 256 bits of $$\pi(h_{\ell - 1})$$ as the hash.

Here a = 2688 and b = 1600, so d = 1088.

Which is better—HAIFA or sponge? It depends on whom you ask! There's no evidence to suspect any weakness in BLAKE2 or SHA-3. Maybe it's easier to make something faster out of HAIFA—certainly BLAKE2 is much faster than SHA-3. Maybe it's easier to prove security reductions of compositions to primitives when the primitive is a single fixed permutation instead of a PRF made out of a PRP.

Note that in all of these compositions one of the basic components is a permutation—$$E_k$$, $$E_{k,t}$$, or $$\pi$$—but the fact that the component is reversible doesn't mean there's any security problem in the composition. Knowing the first 256 bits of $$\pi(s)$$ for a random permutation $$\pi\colon \{0,1\}^{1600} \to \{0,1\}^{1600}$$ doesn't help you to guess a 256-bit secret $$s$$: you'd have to fill in 1344 bits you don't know, which is unimaginably harder than just guessing $$s$$ in the first place!

• I would disagree regarding the values you provided for a, b, and d for sha3-256. Provided you consider domain extension there are 2^1088 unique initial rate values mapping to a 2^1600 sized state space, bounded by a 2^512 sized capacity. a=1088, b=1600, d=-512. Thus (2^1088)/(2^512) possible collisions through a single round of sha3-256. Note that my argument only works when the rate size is greater than the capacity. I don't think anybody can produce a capacity collision without violating the padding, but it is possible. – Q-Club Sep 18 '17 at 0:13
• If you take $a$ to be the length of a message block rather than the length of the input to the internal compression function (chaining value and message block), then sure. I'm only surmising what $a$, $b$, and $d$ mean—the question wasn't clear. In your case, for SHA-256, we would then have $a = 512$, $b = 256$, and $d = 256$. – Squeamish Ossifrage Sep 18 '17 at 0:15
• I would agree! Although I stand by my theory that mod 2^32 addition is witchcraft. – Q-Club Sep 18 '17 at 0:38
• You used the expression "one-time pad". I guess you intended to mean that this pad is only used once - and that's fine. But it has nothing to do with the one-time pad as a cipher (and the generated bitstream does not fullfill the assumptions of OTP). I suggest calling this a keystream. – tylo Sep 18 '17 at 13:58
• Should we avoid calling historical one-time pad systems that too, because those pads were repeated, were generated by biased human typewriters, etc.? Over and over again people see the term ‘one-time pad’ and cook up a scheme to choose a pad badly, thinking they have outdone modern cryptography. The promise of unbreakable encryption becomes less sexy when you point out that modern cryptography just provides a really efficient practical way to generate one-time pads, and the reason we moved on from historical cryptography is that the pads were ad hoc and biased and hard to manage. – Squeamish Ossifrage Sep 18 '17 at 19:30

The problem with your question is that you've generalized a formula for (at least 2 - what hash does bullet point 3 refer to) dissimilar architectures.

SHA1/2 uses the MD construct, whilst SHA3 uses absorption instead as it is a novel "sponge" design. These cannot be sensibly compared with respect to a compression behaviour /metric. The security parameters are totally different. One type of architecture is not necessarily better than another, unless you figure that the most recent must be the best. You need to decide a basic hash primitive, be it conventional, sponge or something new(?) A new fundamental building block would be fascinating.

You will then find that d follows naturally.

And now a warning. It's hard to develop a secure cryptographic hash. Just because you can't invert it, doesn't mean that crypto geeks can't either. They almost certainly can. The only functional (non educational) use for a DIY hash is as a randomness extractor as invert ability is acceptable.