Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [compression-function]

The tag has no usage guidance.

0
votes
1answer
87 views

What characteristics define a function to be a block cipher

I'm trying to understand what characteristics or properties make the result of a function a block cipher. I understand that for a function to be a block cipher it has to be invertible and can't be a ...
2
votes
0answers
40 views

Is the concatenation of one-way compression functions one-way?

Given two independently keyed compression functions $h_1$ and $h_2$: $h_b(x): \{0,1\}^{3n} \to \{0,1\}^{n}$, where $b \in \{1,2\}$. Let $h(x) = h_1(x) \| h_2(x)$. Given at least one of $h_1$ and $...
3
votes
1answer
34 views

For a hash over a finite space without size reduction, is a public permutation sufficient?

Suppose the application is a Lamport signature scheme. Is the following a secure hash $\{0,1\}^n \rightarrow \{0,1\}^n$? $$ H(x) = x \oplus P(x) $$ where $P$ is a public permutation that permutes an ...
10
votes
1answer
169 views

Why was Davies–Meyer chosen over Miyaguchi–Preneel most of the time?

The only Miyaguchi–Preneel MD hash I know is Whirlpool. I suppose there are likely others. Why do most MD hashes choose Davies–Meyer? If anything, Davies–Meyer relies on related-key resistance while ...
1
vote
0answers
75 views

Is it possible to apply a pseudo-random permutation (a keyed permutation) to construct a sponge function?

The description of the sponge function on Crypto.Stackexchange contains the following text (source): The cryptographic sponge is a construction scheme for hash functions (and other symmetric ...
2
votes
1answer
62 views

Is it possible to make use of a pseudo-random permutation to construct a one-way compression function?

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 $...
3
votes
3answers
277 views

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 ...
0
votes
0answers
121 views

Davies-Meyer with DES insecure

I'm stuck in coming up with a collision for a hash function $H$, which is built using a Davies-Meyer construction chained in a Merkle-Damgard fashion. I I guess its actually easy using the fact that ...
1
vote
0answers
86 views

Davies-Meyer without XORing in the previous state

A Davies-Meyer ccompression function operates with $H_{i} = E(m_{i}, H_{i-1}) \oplus H_{i-1}$. Why not use $H_{i} = E(m_{i}, H_{i-1})$ instead?
0
votes
0answers
112 views

Collision resistant Davies-meyer compression function

We suppose $(E,D)$ is a secure $PRP$ , defined on $$(\{0, 1\}^n,\{0, 1\}^n,\{0, 1\}^n) $$ i was asked to find a collision for this compression function : $$ h(H, m) = E(H, m) ⊕ H $$ knowing that ...
2
votes
2answers
130 views

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. ...
4
votes
0answers
80 views

Which compression functions are MACs?

The original HMAC paper based the security proof on the fact that the compression function of the Hash is already a MAC (appropriately keyed). How does this relate to common assumptions for ...
11
votes
2answers
257 views

Which compression functions are PRFs?

In a 2006 paper Bellare showed that HMAC remains secure even if collision resistance for MD5/SHA-1 is broken as long they are still PRFs. The Wikipedia article on cryptographic hash functions ...