Fdtxjr

Are all passive ability checks floors for active ability checks?

How do I hide Chekhov's Gun?

Does this sum go infinity?

Do the common programs (for example: "ls", "cat") in Linux and BSD come from the same source code?

Simplify an interface for flexibly applying rules to periods of time

Why does overlay work only on the first tcolorbox?

Tikz picture of two mathematical functions

What is the significance behind "40 days" that often appears in the Bible?

If I am holding an item before I cast Blink, will it move with me through the Ethereal Plane?

Is it insecure to send a password in a `curl` command?

Why do passenger jet manufacturers design their planes with stall prevention systems?

Why do newer 737s use two different styles of split winglets?

Official degrees of earth’s rotation per day

What is "focus distance lower/upper" and how is it different from depth of field?

Why does a Star of David appear at a rally with Francisco Franco?

Math equation in non italic font

Planetary tidal locking causing asymetrical water distribution

Knife as defense against stray dogs

Is a party consisting of only a bard, a cleric, and a warlock functional long-term?

Describing a chess game in a novel

As a new Ubuntu desktop 18.04 LTS user, do I need to use ufw for a firewall or is iptables sufficient?

How could a scammer know the apps on my phone / iTunes account?

Examples of transfinite towers

What options are left, if Britain cannot decide?

Compression function is not collision resistant but Merkle-Damgard is collision resistant

Generalize the Merkle–Damgård construction for any compression functionCollision in Merkle–Damgård without a collision in compression functionWhat is the “compression function” in Merkle-Damgård?Does Lamport's authentication scheme still work if the hash function is not collision-resistant?Different literature padding for Merkle-DamgardMerkle–Damgård padded block concatenated outside the compression function hash?Why can an arbitrary compression function mapping $0,1^m+2^m rightarrow 0,1^m$ not seriously be considered collision resistant?Confused about Merkle Damgard Transform - short messages?Why do you need padding block at the end of Merkle damgard if the input is multiple of block length?AES-128 as compression function in Merkle-Damgard construction

6

1

$begingroup$

Is it possible that you can still have a collision resistance in Merkle-Damgard even if the compression function has a collision?

hash collision-resistance merkle-damgaard

share|improve this question

edited Mar 12 at 9:50

kelalaka

8,43822351

asked Mar 12 at 7:57

ZoeyZoey

404

$endgroup$

add a comment | 

6

1

$begingroup$

Is it possible that you can still have a collision resistance in Merkle-Damgard even if the compression function has a collision?

hash collision-resistance merkle-damgaard

share|improve this question

edited Mar 12 at 9:50

kelalaka

8,43822351

asked Mar 12 at 7:57

ZoeyZoey

404

$endgroup$

add a comment | 

$begingroup$

Is it possible that you can still have a collision resistance in Merkle-Damgard even if the compression function has a collision?

hash collision-resistance merkle-damgaard

share|improve this question

edited Mar 12 at 9:50

kelalaka

8,43822351

asked Mar 12 at 7:57

ZoeyZoey

404

$endgroup$

share|improve this question

edited Mar 12 at 9:50

kelalaka

8,43822351

asked Mar 12 at 7:57

ZoeyZoey

404

share|improve this question

edited Mar 12 at 9:50

kelalaka

8,43822351

asked Mar 12 at 7:57

ZoeyZoey

404

edited Mar 12 at 9:50

kelalaka

8,43822351

edited Mar 12 at 9:50

kelalaka

8,43822351

asked Mar 12 at 7:57

ZoeyZoey

404

asked Mar 12 at 7:57

ZoeyZoey

404

2 Answers
2

active

oldest

votes

7

$begingroup$

Yes, a hash built per the Merkle-Damgård construction can be collision-resistant even if its compression function has a known collision.

Consider SHA-256. Note its round function $F:0,1^256times0,1^512to0,1^256$ where the first argument is the state and the second is a message block. Now define $F'$ identical to $F$, except that $F'(0^256,0^512)$ is defined to be $F(0^256,1^512)$.

$F'$ has a known collision, yet the variant of SHA-256 using $F'$ is collision resistant, because we can't find a way to bring the state of SHA-256 to all-zero, which would essentially be a preimage attack.

share|improve this answer

edited Mar 12 at 8:21

answered Mar 12 at 8:13

fgrieufgrieu

81.6k7175347

$endgroup$

add a comment | 

2

$begingroup$

For a very realistic example, see the analysis contained in Black-Box Analysis of the Block-Cipher-Based Hash-Function Constructions from PGV by Black, Rogaway, and Shrimpton.

They explore all the ways of building a Merkle-Damgaard hash function with an ideal cipher as the underlying compression function, finally classifying which are secure and which are not.

Interestingly, they find a category of constructions with the property you mention:

... group-2 schemes ... are collision resistant even though their compression functions are not.

As an example, their $H_13$ uses $f(h_i, m_i) = E_h_i oplus m_i(m_i)$ as the compression function. Although this round function leads to a secure MD hash function, by itself it is not even one-way. To find a preimage of $y$, first choose arbitrary $k$, then compute $m : = E^-1_k(y)$ and $h := m oplus k$. Then $(h,m)$ is a preimage of $y$.

share|improve this answer

answered Mar 13 at 0:00

MikeroMikero

5,63311725

$endgroup$

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "281"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f67959%2fcompression-function-is-not-collision-resistant-but-merkle-damgard-is-collision%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

7

$begingroup$

Yes, a hash built per the Merkle-Damgård construction can be collision-resistant even if its compression function has a known collision.

Consider SHA-256. Note its round function $F:0,1^256times0,1^512to0,1^256$ where the first argument is the state and the second is a message block. Now define $F'$ identical to $F$, except that $F'(0^256,0^512)$ is defined to be $F(0^256,1^512)$.

$F'$ has a known collision, yet the variant of SHA-256 using $F'$ is collision resistant, because we can't find a way to bring the state of SHA-256 to all-zero, which would essentially be a preimage attack.

share|improve this answer

edited Mar 12 at 8:21

answered Mar 12 at 8:13

fgrieufgrieu

81.6k7175347

$endgroup$

add a comment | 

7

$begingroup$

Yes, a hash built per the Merkle-Damgård construction can be collision-resistant even if its compression function has a known collision.

Consider SHA-256. Note its round function $F:0,1^256times0,1^512to0,1^256$ where the first argument is the state and the second is a message block. Now define $F'$ identical to $F$, except that $F'(0^256,0^512)$ is defined to be $F(0^256,1^512)$.

$F'$ has a known collision, yet the variant of SHA-256 using $F'$ is collision resistant, because we can't find a way to bring the state of SHA-256 to all-zero, which would essentially be a preimage attack.

share|improve this answer

edited Mar 12 at 8:21

answered Mar 12 at 8:13

fgrieufgrieu

81.6k7175347

$endgroup$

add a comment | 

$begingroup$

Yes, a hash built per the Merkle-Damgård construction can be collision-resistant even if its compression function has a known collision.

Consider SHA-256. Note its round function $F:0,1^256times0,1^512to0,1^256$ where the first argument is the state and the second is a message block. Now define $F'$ identical to $F$, except that $F'(0^256,0^512)$ is defined to be $F(0^256,1^512)$.

$F'$ has a known collision, yet the variant of SHA-256 using $F'$ is collision resistant, because we can't find a way to bring the state of SHA-256 to all-zero, which would essentially be a preimage attack.

share|improve this answer

edited Mar 12 at 8:21

answered Mar 12 at 8:13

fgrieufgrieu

81.6k7175347

$endgroup$

share|improve this answer

edited Mar 12 at 8:21

answered Mar 12 at 8:13

fgrieufgrieu

81.6k7175347

answered Mar 12 at 8:13

fgrieufgrieu

81.6k7175347

answered Mar 12 at 8:13

fgrieufgrieu

81.6k7175347

2

$begingroup$

For a very realistic example, see the analysis contained in Black-Box Analysis of the Block-Cipher-Based Hash-Function Constructions from PGV by Black, Rogaway, and Shrimpton.

They explore all the ways of building a Merkle-Damgaard hash function with an ideal cipher as the underlying compression function, finally classifying which are secure and which are not.

Interestingly, they find a category of constructions with the property you mention:

... group-2 schemes ... are collision resistant even though their compression functions are not.

As an example, their $H_13$ uses $f(h_i, m_i) = E_h_i oplus m_i(m_i)$ as the compression function. Although this round function leads to a secure MD hash function, by itself it is not even one-way. To find a preimage of $y$, first choose arbitrary $k$, then compute $m : = E^-1_k(y)$ and $h := m oplus k$. Then $(h,m)$ is a preimage of $y$.

share|improve this answer

answered Mar 13 at 0:00

MikeroMikero

5,63311725

$endgroup$

add a comment | 

2

$begingroup$

For a very realistic example, see the analysis contained in Black-Box Analysis of the Block-Cipher-Based Hash-Function Constructions from PGV by Black, Rogaway, and Shrimpton.

They explore all the ways of building a Merkle-Damgaard hash function with an ideal cipher as the underlying compression function, finally classifying which are secure and which are not.

Interestingly, they find a category of constructions with the property you mention:

... group-2 schemes ... are collision resistant even though their compression functions are not.

As an example, their $H_13$ uses $f(h_i, m_i) = E_h_i oplus m_i(m_i)$ as the compression function. Although this round function leads to a secure MD hash function, by itself it is not even one-way. To find a preimage of $y$, first choose arbitrary $k$, then compute $m : = E^-1_k(y)$ and $h := m oplus k$. Then $(h,m)$ is a preimage of $y$.

share|improve this answer

answered Mar 13 at 0:00

MikeroMikero

5,63311725

$endgroup$

add a comment | 

$begingroup$

For a very realistic example, see the analysis contained in Black-Box Analysis of the Block-Cipher-Based Hash-Function Constructions from PGV by Black, Rogaway, and Shrimpton.

They explore all the ways of building a Merkle-Damgaard hash function with an ideal cipher as the underlying compression function, finally classifying which are secure and which are not.

Interestingly, they find a category of constructions with the property you mention:

... group-2 schemes ... are collision resistant even though their compression functions are not.

As an example, their $H_13$ uses $f(h_i, m_i) = E_h_i oplus m_i(m_i)$ as the compression function. Although this round function leads to a secure MD hash function, by itself it is not even one-way. To find a preimage of $y$, first choose arbitrary $k$, then compute $m : = E^-1_k(y)$ and $h := m oplus k$. Then $(h,m)$ is a preimage of $y$.

share|improve this answer

answered Mar 13 at 0:00

MikeroMikero

5,63311725

$endgroup$

share|improve this answer

answered Mar 13 at 0:00

MikeroMikero

5,63311725

answered Mar 13 at 0:00

MikeroMikero

5,63311725

answered Mar 13 at 0:00

MikeroMikero

5,63311725