Let $f_k(B)$ denote the underlying function (a pseudo-random permutation) of a block cipher: it uses an $x$-bit key $k$ to encrypt an $y$-bit block $B$.
The question: is it possible to make use of $f_k(B)$ to construct a cryptographically secure One-way compression function that transforms any sequence of $y$ bits to a sequence of $y/2$ bits? If yes, then what is an example of how to do it? If no, then why?
For example, consider the following construction. Let $V$ denote a sequence of $x$ zero bits: $$V = 0^x.$$ Then $W$ denotes the inverse of $V$: $$W = 1^x.$$ Consider a function that outputs the first half of a bitstring $T$, where
$$T = f_V(b) \oplus f_W(B),$$ assuming that $B$ denotes the input, $b$ denotes the inverse of $B$ and $\oplus$ denotes a standard XOR.
Can we use such function as a compression function?
1 Answer
This is possible in the ideal cipher model, and is the basis of the Davies-Meyer and other hashes; see https://en.wikipedia.org/wiki/One-way_compression_function. There has been a lot of work looking at this, but I think a good place to start is the paper Black-Box Analysis of the Block-Cipher-Based Hash-Function Constructions from PGV. It is important, however, to be aware that the ideal cipher model is very strong. For example, AES suffers from related-key attacks and so is not a good basis for such constructions. In addition, due to DES weak keys, some of these constructions are completely broken with DES. However, it does explain the rationale behind the SHA256 and other SHA constructions that essentially construct a type of block cipher and apply a Davies-Meyer type transformation.
-
$\begingroup$ So it does not make any sense to talk about the fixed-length input compression from $y$ bits to $y/2$ bits? All described schemes are iterated and output $y$ bits from the variable-length input... $\endgroup$ Commented Nov 10, 2018 at 9:07
-
$\begingroup$ Actually, you will notice that they all start with a basic construction that takes $2n$ bits to $n$ bits, which is the same as you are looking at. They then iterate to get something from a general input length (as in Merkle-Damgård). $\endgroup$ Commented Nov 10, 2018 at 16:21
b = \overline{B}$\endgroup$