# Does there exist an “almost-ideal” compression function to compress an arbitrarily long bitstring into a single pseudo-random (unbiased) byte?

I need a function $F$ that compresses an arbitrary (unbounded from above) number of bytes into a single byte. The goal is creating a single unpredictable byte from an arbitrary bitstring.

Here are the requirements:

1. Pseudo-randomness: the resulting byte should look uncorrelated and unbiased in comparison with the input. This is why Pearson hashing is unacceptable (because it is not even needed to compute this hash to know that the outputs for 0000 and FF00 will be different). Note: see the detailed clarification of Property 1 in Edit #1 below.
2. Let $S$ denote the collection of all possible (different) bitstrings, assuming that all bitstrings are of the same non-zero length and this length is a multiple of 8. Let $L$ denote the number of elements of $S$. Let $T$ denote a collection of all outputs that correspond to each element of $S$. Then $T$ must contain $L/256$ occurrences of each byte. That is, for example, if I will compress all possible two-byte inputs, I will have 256 occurrences of each byte in the collection of all outputs. This requirement makes standard cryptographic hash functions unacceptable.
3. Table lookups are allowed, but if and only if all tables are “Nothing up my sleeve” and are generated/precomputed by an open algorithm, so everyone can observe the entire process of their creation.
4. The algorithm should be as fast/efficient as possible. This is another reason why standard cryptographic hash functions are not acceptable. Consider a situation when $F$ is used only for 8/16/24/32-bit inputs. Then I think that using 128/256/512-bit hash functions to compress such inputs does not seem efficient.
5. The algorithm is not required to be online. The entire input is allowed to be stored in RAM.

Is there any algorithm that matches the above requirements?

EDIT #1

I will clarify the property 1 as follows.

Let $G(V, W)$ denote an infinite family of all possible functions where any function $G_i$, given a bitstring $V$, generates a collection (array) that contains $W$ different bitstrings of equal length, assuming that $V$ will be the first element of the generated collection and the length (in bits) of each bitstring in this collection is a multiple of 8.

Let $G_1$ denote any chosen (fixed) function from the family of $G$. The algorithm of $G_1$ is open for everyone (as well as the algorithm of $F$). The simplest example of $G_1$ is a function that creates a collection where each successive element $b_i$ is a binary representation of $(b_{i-1} + 1) \bmod{2^N}$, where $N$ is the length of $V$.

Alice chooses any bitstring $B_1$ such that its length is equal to $8X$. Then Alice obtains the collection $S_1$: $$S_1 = G_1(B_1, X) = (B_1, B_2, \ldots, B_{X-1}, B_X).$$ Then Alice computes the bitstring $Y_1$: $$Y_1 = F(B_1) \mathbin\Vert F(B_2) \mathbin\Vert \ldots \mathbin\Vert F(B_{X-1}) \mathbin\Vert F(B_X).$$

Then $Y_1$ is given to the attackers, so the exact value of $X$ is open to them.

The attackers know that $G_1$ was used to generate each $i$-th element $B_i$, and they are allowed to choose any function from the family of $G$, denote it by $G_k$, then choose any $8X$-bit sequence $B_n$, then generate the collection $$S_2 = G_k(B_n, X) = (C_1, C_2, \ldots, C_{X-1}, C_X),$$

and then compute the corresponding bitstring $Y_2$: $$Y_2 = F(C_1) \mathbin\Vert F(C_2) \mathbin\Vert \ldots \mathbin\Vert F(C_{X-1}) \mathbin\Vert F(C_X)$$

(the attackers are not allowed to replace $F$ with another function).

The desirable property of $F$ is that the cost of finding any suitable combination of $G_k$ and $B_n$ that corresponds to $Y_2 = Y_1$ should be as close to $\sqrt{2^{8X}}$ as possible.

SUMMARY

This question implies a bijective function (or a Permutation-Based Compression Function) that can be described by the following quote (taken from the Abstract of “The MD6 hash function: A proposal to NIST for SHA-3”):

The compression function can be viewed as encryption with a fixed key (or equivalently, as applying a fixed random permutation of the message space) followed by truncation.

and optimized for 8-bit words architecture and for all bitstrings such that their lengths are multiples of 8 (similar to how MD6 compression function operates, so that no unnecessary computations are performed if all inputs are short, and all parameters are configurable for different input sizes).

• @fgrieu: I edited the question and clarified what I meant by "look uncorrelated". – lyrically wicked Jun 6 '18 at 7:46
• A set does not have a "first element"; did you mean "smallest"? – fkraiem Jun 6 '18 at 13:13
• What are you actually trying to accomplish? What are you going to do with such a beast as this? – Squeamish Ossifrage Jun 7 '18 at 15:28
• I see nothing that differs from: a family of hash functions for bytestrings of non-zero length, with a single-byte output, and exactly unbiased for any fixed input length; with security criteria that a random member of that family is computationally indistinguishable from a random function with this property (an appropriate random oracle); and further with a simple implementation having memory access pattern fixed for a given input length. That seems well defined, and is achieved by the truncated PRP for each length approach. The challenge is the balance between security and simplicity. – fgrieu Jun 8 '18 at 5:16
• @lyricallywicked The summary doesn't explain why you're looking for this. It also uses the technical term ‘pseudorandom permutation’ in a context that doesn't match even the syntax of a PRP because nobody has said anything about a key. You mentioned a family $G$, but then $F$ is not a member of the family $G$, and I didn't follow the story with $G$. What is the application for this that imposes these requirements? – Squeamish Ossifrage Jun 8 '18 at 14:48

I read property 2 to mean "every output byte value has exactly equal frequency". That's an uncommon design goal in cryptography. If that's what you really want then I recommend choosing a family of permutation functions with a separate function for each possible input length. Apply the appropriate permutation function to the input string (the one that matches the input length), then truncate the resulting bit string to 8 bits.

This grants you exactly equal frequencies. Note that you have an $n$ bit input string, and a bijective function that returns an $n$ bit output. Consider how many outputs are possible. That number is $2^n$. All possible bit strings are required to be possible output strings by the definition of a permutation function.

Next consider how many of those strings begin with a given 8 bit prefix. Well, the first 8 bits are constant and the remaining $n - 8$ bits can take on any value. (And must be able to take on any value.) Easy. There are $2^{n-8}$ possible output strings with a given 8 bit prefix. That's independent of the value of the prefix, so you can see that every prefix within all $2^n$ possible output strings occur with precisely equal frequency.

Use a pseudorandom permutation for your permutation function. This let's you conclude the prefix is pseudorandom as well. The tough part is finding fast PRPs for each possible input length. I suggest looking at XXTEA. It is a block cipher (therefore a PRP family) and is unusual in the property that it is defined for a variable block length. That's not to imply that it's secure or practical for cryptographic purposes. But if you don't need security it's fine.

One big problem with this method is that it has no preimage resistance. Simply choose any bitstring that begins with the 8 bit image value, then apply the inverse of the permutation function to get your preimage. I assume you know that an 8 bit output function is too small to qualify as secure even if it weren't so straightforward to compute preimages. (Just brute force preimages.) Even if you managed to find a fast one way permutation it wouldn't matter because brute force is an option.

This set of properties are rather unusual. If you're not sure if you need precisely-equal frequencies then there are things like hash functions which are fast. You can revise your question if you want those types of options. Property 2 actually reduces the randomness of the function. Property 3 implies you care about side channel attacks, but the 8 bit output is too small to rely on for security purposes. Property 4 suggests speed is important, but have you done any benchmarking to find out if optimizing this one function for speed will give you good returns? And if speed does matter, have you considered other designs with relaxed requirements? Those might be faster overall especially if you can use fast insecure hash functions.

• It's late for me. If you have questions or clarifications or edits then I can revise this answer later. I have a couple more ideas I haven't explored, but those won't be as easy to prove correct. The other ideas are not faster. Nor do they improve security. – Future Security Jun 6 '18 at 6:28
• The truncated PRPs of various length approach is fine, if perhaps a bit overkill. But XXTEA won't cover all input length. The preimage resistance is limited by the 1-byte output width, not the possibility of walking back the PRP (we can't without the discarded output). – fgrieu Jun 6 '18 at 7:02
• I think that the requirement #2 is needed, and this is why I used the "compression" tag (not "hash") for this question. – lyrically wicked Jun 6 '18 at 7:22
• @lyricallywicked I was thinking about CBC-MAC as an alternative to Pearson hashing. Specifically one with a 8 bit block size. This eliminates the need for table look up, but it doesn't help with property 1. (For any instance of CBC-MAC there is a table for Pearson hashing that behaves identically.) One alternative (still not secure) might be to do some CBC-like encryption (anything that propagates differences in plaintext forward, with a constant IV, even with normal block sizes, as long it doesn't expand the message) then do CBC-MAC with 8 bit blocks processing bytes in the opposite order. – Future Security Jun 7 '18 at 5:55
• @lyricallywicked And to clarify I don't recommend such a monstrous hack as if it were secure, but I can't think of any reason why it might have obvious statistical biases by non-crypto standards. I recommended using a larger block because 8 bits is too small to avoid block collisions. Although my second idea sounds harder to implement to me than modifying XXTEA or writing a custom algorithm. Additionally I found this eprint.iacr.org/2004/125.pdf which (from the abstract) looks like a way to implement a variable length PRP. It's probably overkill if it's cryptographically secure. – Future Security Jun 7 '18 at 6:05

Yes, it is possible to devise a function as asked.

## Existence and theoretical construction

Define ${\mathcal F}_{n,m}$ to be the set of function $\Bbb Z_n\to\Bbb Z_m$. It has $m^n$ elements. The question is about functions of bytestrings of $l>0$ byte(s) to a single byte, which we can assimilate to functions $\{0,1\}^{8l}\to\{0,1\}^8$, and thus to members of ${\mathcal F}_{2^{8l},2^8}$.

Define ${\mathcal G}_{n,m}$ as the subset of ${\mathcal F}_{n,m}$ matching the question's property 2: each of the $m$ output elements is reached exactly $n/m$ times; otherwise said, the output is perfectly equidistributed. If $n\bmod m\ne0$, ${\mathcal G}_{n,m}$ is empty. With $n\bmod m=0$ (which is the case for $n=2^{8l}$ and $m=2^8$ of the question and assumed from now on), that set has $n!/((n/m)!)^m$ elements. As $l$ grows, that's an increasingly severe restriction, but even for a single byte input, tremendously many functions remain: $$\begin{array}{c|ccc} l\text{ (bytes)}&|{\mathcal F}_{2^{8l},2^8}|&|{\mathcal G}_{2^{8l},2^8}|l&|{\mathcal F}_{2^{8l},2^8}|/|{\mathcal G}_{2^{8l},2^8}|\\ \hline 1&2^{2048}&2^{1683.996\dots}&2^{364.003\dots}\\ 2 &2^{524288}&2^{522933.814\dots}&2^{1354.186\dots}\\ 3 &2^{134217728}&2^{134215353.934\dots}&2^{2374.066\dots}\\ \ge3 &2^{(2^{8l+3})}&2^{\approx2^{8l+3}-1020l+k}&2^{\approx1020l-k}& \end{array}$$ with $k=\displaystyle\frac{1793-255\log_2(\pi)}2=685.934\dots$.

A method to build some function $G$ in ${\mathcal G}_{n,m}$ is to pick a permutation $P$ of $\Bbb Z_n$, and set $G(x)=P(x)\bmod m$; that $G$ is perfectly equidistributed. Conversely, from any function $G$ in ${\mathcal G}_{n,m}$, we can build a permutation $P$ of $\Bbb Z_n$ with $G(x)=P(x)\bmod m$. Proof: define $I(x)$ to be the number of $x'\in\Bbb Z_n$ with $x'<x$ and $G(x')=G(x)$, then define $P(x)=m\,I(x)+G(x)$.

It follows that to pick a uniformly random member of ${\mathcal G}_{n,m}$ (which gives ideal security per any reasonable criteria), we can pick a uniformly random permutation $P$ of $\Bbb Z_n$ among the $n!$ there is, and define $G(x)=P(x)\bmod m$.

Translated to the question's ${\mathcal G}_{2^{8l},2^8}$, that's picking an arbitrary permutation of the $l$-byte input space among the $2^{8l}!$ ones, and keeping (say) the last byte.

Thus, as stated by Future Security's answer, we plausibly get a secure construction (per some reasonable definition) by picking a good block cipher of variable block size $l$-byte; fixing a nothing-up-my-sleeve key for that block cipher; and defining the function as the last byte of the output of that block cipher.

For $l=1$, our function is the block cipher. As $l$ grows, a secure block cipher arguably becomes increasingly overkill, because so much output is discarded.

## Towards a practical construction

For small $l$, we could use some ARX $8l$-bit block cipher with a balanced Feistel structure, perhaps enhanced to use addition modulo $2^{4l}$ when mixing the round function's output (using XOR always generates an even permutation, which is recognizable for $l=1$; that's no big deal if we truly fix the key, but if we used it as a tweak that would be a distinguishable weakness).

Constructing an exactly equidistributed function for large $l$ is needed only for the sake of having something that formally answers the question: for large input (for sure for $l\ge32$), it is computationally impossible to recognize that a secure hash truncated to its last byte in not exactly equidistributed, and that gives a practical construction.

Despite the above, the following constructs an exactly equidistributed function for large $l$, with the convenient property of processing the input only once. I conjecture that for $b/2$-bit security and $8l\ge2b$ we can process the input by $b$-bit blocks with a $2b$-bit clock cipher, as follows:

• init a $2b$-bit block to the first $2b$ bits of input
• encipher the block
• while there remains at least $b$ bits of input
• XOR these $b$ bits into the right side of the block
• encipher the block
• append to the remaining input a single one bit then just enough zero bit(s) to form a $b$-bit block [with big-endian convention for bytes and $b\bmod8=0$, that's equivalent to appending one 0x80 byte and $b/8-1-(l\bmod(b/8))$ 0x00 byte(s)]
• XOR these $b$ bits into the right side of the block
• XOR a bitstring representing the input length into the other side of the block
• encipher the block
• output the rightmost byte of the block.

It can be proved by induction that when $(c+2)b$ bits of input have been processed, the block is the image of the processed input by a function in ${\mathcal G}_{2^{(c+2)b},2^{2b}}$. If follows that the final outcome is the image of the input by a function in ${\mathcal G}_{2^{8l},2^8}$ as thought.

For 128-bit conjectured security we could use the 512-bit block cipher in the round function of SHA-512, without the final 8 modular additions so that it remains a permutation, and with a message/key all-zero (saving all message expansion and mixing operations) since SHA-512 has enough nothing-up-my-sleeves constants (but if we need a tweak, we can use the message for that; entering the round number there could give extra security margin).

Note: The best attack is conjectured to be trying to encipher $2b$-bit values until finding a collision in the left half of the result (requiring $\mathcal O(b/2)$ effort), which then trivially allows to find $3b$-bit distinct prefixes $M_0$ and $M_1$ such that for all $M$, $M_0\|M$ and $M_1\|M$ yield the same result, which is a distinguishable property making no obvious reference to the nothing-up-my-sleeve constant.

Note: I we processed input by blocks of the full width $2b$ of the block cipher rather than half, it would require only two encryptions to exhibit $4b$-bit distinct prefixes $M_0$ and $M_1$ with that property.

• The problem is, how to find an universal family of functions defined for all $2b$-bit block sizes where $b \in \{8, 12, 16, 20, 24, \ldots \}$. The only example I have seen is a function $f$ described in Chapter 2.5 and Chapter 9 of “The MD6 hash function: A proposal to NIST for SHA-3”. – lyrically wicked Jun 10 '18 at 11:33
• @lyrically wicked: as stated, past some input size like 32-byte (perhaps less, I have not studied that in detail), a truncated hash is computationally indistinguishable from what's asked. Do you nevertheless want a construction that covers that case (as in the answer's last section)? Independently, can speed be ignored almost entirely to get something simpler? If yes on both counts, does it matter that the whole input must be stored in RAM (which allows a single simple do-it-all method)? Is demonstrable security a must? – fgrieu Jun 10 '18 at 13:04
• "does it matter that the whole input must be stored in RAM (which allows a single simple do-it-all method)?" The whole input is allowed to be stored in RAM, so it does not matter. Can you explain what you meant by "a single simple do-it-all method"? – lyrically wicked Mar 13 at 6:37

If you feel that 128/256/512-bit hash functions to compress such inputs does not seem efficient, CRC32 is the answer. Although that's not a cryptographic solution in a crypto forum, unless you consider that it uses finite fields.

Simply XOR the resultant four bytes into one. And for speed, CPUs post Intel i5 contain the CRC32 instruction that makes it super speedy. Just check that the parity bit is dropped as that will form a correlated output.

Following revision of the look up tables restriction, Pearson hashing comes into scope. Take the wiki pseudo code and amend with another independent lookup table (T2) like so:-

h := 0
for each c in C loop
h := T1[ h xor c ]
h := T2[ h xor c ]
end loop
return h


Both tables T1 and T2 are simple random and arbitrary permutations of 0-255. No need for goofy Galois maths. Just randomly scramble the sequence so there is clearly nothing up anyone's sleeves. I prefer to make them derangements but that's not necessary. Mr Pearson's original published table has a fixed point and that still seems to produce a good distribution of outputs.

This would be my choice of algorithm. Due to the inclusion of 3368 bits of information entropy into the algorithm via T1 and T2, you get almost ideal hashing with a few lines of actual code. Padding is not required due to the single byte block size. The hash will collide at $\frac{1}{e}$ or 36.8%. That's exactly the collision rate of fully cryptographic hashes operating as pseudo random functions. And it's very fast as both tables will easily cache in the smallest (quickest) RAM.

• The function proposed in answer (call it $F$) inherits from CRC a recognizable property: it is affine. That is, for any three inputs of equal length, noted $x$, $y$, $z$, it holds that $F(x\oplus y\oplus z)=F(x)\oplus F(y)\oplus F(z)$. Apply that with $y=\mathtt{'00'}$, $z=\mathtt{'01'}$, compute $d=F(\mathtt{'00'})\oplus F(\mathtt{'01'})$ once for all, and it comes that for any byte $x$, $F(x\oplus\mathtt{'01'})=F(x)\oplus d$. Which is a property that is antagonist to any reasonable definition of "look uncorrelated in comparison with the input" in a crypto context. – fgrieu Jun 7 '18 at 13:14
• Although that's not a cryptographic solution in a crypto forum, unless you consider that it uses finite fields. What is this supposed to mean? Using finite arithmetic does not automagically make something cryptography. – Ella Rose Jun 7 '18 at 17:07