Mixing
What is the probability to produce a collision under two different hash functions?
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
Given 2 (weak) hash functions, namely MD5 and SHA1
The fact that there exists 2 different inputs that will result in the same output under both hashing functions is explained in "Can there be two hash functions without common collisions?"
I would like to quantify the probability of this type of inputs to be forged.
Namely:
MD5(x) = MD5(y)
whilst
SHA1(x) = SHA1(y)
So if I keep the two hashes of a file, how much harder is it to forge another file that yield the same hashes rather than either of those individually ?
I expect it to be more than the added probability of each, but by how much (order of magnitude) ?
hash collision-resistance
asked 3 hours ago
Simon
1061
New contributor
Simon is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |Â
up vote
1
down vote
favorite
Given 2 (weak) hash functions, namely MD5 and SHA1
The fact that there exists 2 different inputs that will result in the same output under both hashing functions is explained in "Can there be two hash functions without common collisions?"
I would like to quantify the probability of this type of inputs to be forged.
Namely:
MD5(x) = MD5(y)
whilst
SHA1(x) = SHA1(y)
So if I keep the two hashes of a file, how much harder is it to forge another file that yield the same hashes rather than either of those individually ?
I expect it to be more than the added probability of each, but by how much (order of magnitude) ?
hash collision-resistance
asked 3 hours ago
Simon
1061
New contributor
Simon is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
Given 2 (weak) hash functions, namely MD5 and SHA1
The fact that there exists 2 different inputs that will result in the same output under both hashing functions is explained in "Can there be two hash functions without common collisions?"
I would like to quantify the probability of this type of inputs to be forged.
Namely:
MD5(x) = MD5(y)
whilst
SHA1(x) = SHA1(y)
So if I keep the two hashes of a file, how much harder is it to forge another file that yield the same hashes rather than either of those individually ?
I expect it to be more than the added probability of each, but by how much (order of magnitude) ?
hash collision-resistance
asked 3 hours ago
Simon
1061
New contributor
Simon is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Given 2 (weak) hash functions, namely MD5 and SHA1
The fact that there exists 2 different inputs that will result in the same output under both hashing functions is explained in "Can there be two hash functions without common collisions?"
I would like to quantify the probability of this type of inputs to be forged.
Namely:
MD5(x) = MD5(y)
whilst
SHA1(x) = SHA1(y)
So if I keep the two hashes of a file, how much harder is it to forge another file that yield the same hashes rather than either of those individually ?
I expect it to be more than the added probability of each, but by how much (order of magnitude) ?
hash collision-resistance
hash collision-resistance
asked 3 hours ago
Simon
1061
New contributor
Simon is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 3 hours ago
Simon
1061
New contributor
Simon is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 3 hours ago
Simon
1061
New contributor
Simon is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 3 hours ago
Simon
1061
asked 3 hours ago
Simon
1061
1061
New contributor
Simon is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Simon is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Simon is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |Â
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
3
down vote
A "simple" answer (but somewhat wrong) would be the following: define function $H$ which is the concatenation of MD5 and SHA-1; i.e. on input $x$, $H(x)$ will be the 288-bit string consisting of MD5($x$) (128 bits) followed by SHA-1($x$) (160 bits). If you have distinct two messages $x$ and $y$ such that MD5($x$) = MD5($y$) and SHA-1($x$) = SHA-1($y$), then, by definition, $x$ and $y$ are a colliding pair for $H$. Since $H$ has a 288-bit output, finding a collision for $H$ requires an average effort of, at most, $2^144$ invocations, since that's the best you can expect from a "perfect" hash function.
What's wrong in the paragraph above is that the $H$ function, as described above, is far from the "perfect" state. In 2004, Joux published (Multicollisions in Iterated Hash Functions. Application to Cascaded Constructions) an attack that works on "iterated" hash functions such as MD5 and SHA-1, which shows that even if MD5 and SHA-1 were both ideally strong (given their output size), the concatenation would not be stronger than the strongest of the two. In other words, even without leveraging known attacks on MD5 and SHA-1, a collision on the concatenated hash function $H$ can be found in about $2^80$ invocations. This work was generalized in 2006 by Hoch and Shamir (Breaking the ICE - Finding Multicollisions in Iterated Concatenated and Expanded (ICE) Hash Functions).
Now, both MD5 and SHA-1 have known structural attacks. In an answer to a previous question on that subject, @poncho explains how to use the known attacks on SHA-1 (with cost $2^61$) to make a simultaneous MD5+SHA-1 collision in effort $2^67$. Amusingly, this does not leverage any specific weakness of MD5; it would also work for a perfect 128-bit hash function instead of MD5.
answered 2 hours ago
Thomas Pornin
66.8k12173252
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
A "simple" answer (but somewhat wrong) would be the following: define function $H$ which is the concatenation of MD5 and SHA-1; i.e. on input $x$, $H(x)$ will be the 288-bit string consisting of MD5($x$) (128 bits) followed by SHA-1($x$) (160 bits). If you have distinct two messages $x$ and $y$ such that MD5($x$) = MD5($y$) and SHA-1($x$) = SHA-1($y$), then, by definition, $x$ and $y$ are a colliding pair for $H$. Since $H$ has a 288-bit output, finding a collision for $H$ requires an average effort of, at most, $2^144$ invocations, since that's the best you can expect from a "perfect" hash function.
What's wrong in the paragraph above is that the $H$ function, as described above, is far from the "perfect" state. In 2004, Joux published (Multicollisions in Iterated Hash Functions. Application to Cascaded Constructions) an attack that works on "iterated" hash functions such as MD5 and SHA-1, which shows that even if MD5 and SHA-1 were both ideally strong (given their output size), the concatenation would not be stronger than the strongest of the two. In other words, even without leveraging known attacks on MD5 and SHA-1, a collision on the concatenated hash function $H$ can be found in about $2^80$ invocations. This work was generalized in 2006 by Hoch and Shamir (Breaking the ICE - Finding Multicollisions in Iterated Concatenated and Expanded (ICE) Hash Functions).
Now, both MD5 and SHA-1 have known structural attacks. In an answer to a previous question on that subject, @poncho explains how to use the known attacks on SHA-1 (with cost $2^61$) to make a simultaneous MD5+SHA-1 collision in effort $2^67$. Amusingly, this does not leverage any specific weakness of MD5; it would also work for a perfect 128-bit hash function instead of MD5.
answered 2 hours ago
Thomas Pornin
66.8k12173252
add a comment |Â
up vote
3
down vote
A "simple" answer (but somewhat wrong) would be the following: define function $H$ which is the concatenation of MD5 and SHA-1; i.e. on input $x$, $H(x)$ will be the 288-bit string consisting of MD5($x$) (128 bits) followed by SHA-1($x$) (160 bits). If you have distinct two messages $x$ and $y$ such that MD5($x$) = MD5($y$) and SHA-1($x$) = SHA-1($y$), then, by definition, $x$ and $y$ are a colliding pair for $H$. Since $H$ has a 288-bit output, finding a collision for $H$ requires an average effort of, at most, $2^144$ invocations, since that's the best you can expect from a "perfect" hash function.
What's wrong in the paragraph above is that the $H$ function, as described above, is far from the "perfect" state. In 2004, Joux published (Multicollisions in Iterated Hash Functions. Application to Cascaded Constructions) an attack that works on "iterated" hash functions such as MD5 and SHA-1, which shows that even if MD5 and SHA-1 were both ideally strong (given their output size), the concatenation would not be stronger than the strongest of the two. In other words, even without leveraging known attacks on MD5 and SHA-1, a collision on the concatenated hash function $H$ can be found in about $2^80$ invocations. This work was generalized in 2006 by Hoch and Shamir (Breaking the ICE - Finding Multicollisions in Iterated Concatenated and Expanded (ICE) Hash Functions).
Now, both MD5 and SHA-1 have known structural attacks. In an answer to a previous question on that subject, @poncho explains how to use the known attacks on SHA-1 (with cost $2^61$) to make a simultaneous MD5+SHA-1 collision in effort $2^67$. Amusingly, this does not leverage any specific weakness of MD5; it would also work for a perfect 128-bit hash function instead of MD5.
answered 2 hours ago
Thomas Pornin
66.8k12173252
add a comment |Â
up vote
3
down vote
up vote
3
down vote
A "simple" answer (but somewhat wrong) would be the following: define function $H$ which is the concatenation of MD5 and SHA-1; i.e. on input $x$, $H(x)$ will be the 288-bit string consisting of MD5($x$) (128 bits) followed by SHA-1($x$) (160 bits). If you have distinct two messages $x$ and $y$ such that MD5($x$) = MD5($y$) and SHA-1($x$) = SHA-1($y$), then, by definition, $x$ and $y$ are a colliding pair for $H$. Since $H$ has a 288-bit output, finding a collision for $H$ requires an average effort of, at most, $2^144$ invocations, since that's the best you can expect from a "perfect" hash function.
What's wrong in the paragraph above is that the $H$ function, as described above, is far from the "perfect" state. In 2004, Joux published (Multicollisions in Iterated Hash Functions. Application to Cascaded Constructions) an attack that works on "iterated" hash functions such as MD5 and SHA-1, which shows that even if MD5 and SHA-1 were both ideally strong (given their output size), the concatenation would not be stronger than the strongest of the two. In other words, even without leveraging known attacks on MD5 and SHA-1, a collision on the concatenated hash function $H$ can be found in about $2^80$ invocations. This work was generalized in 2006 by Hoch and Shamir (Breaking the ICE - Finding Multicollisions in Iterated Concatenated and Expanded (ICE) Hash Functions).
Now, both MD5 and SHA-1 have known structural attacks. In an answer to a previous question on that subject, @poncho explains how to use the known attacks on SHA-1 (with cost $2^61$) to make a simultaneous MD5+SHA-1 collision in effort $2^67$. Amusingly, this does not leverage any specific weakness of MD5; it would also work for a perfect 128-bit hash function instead of MD5.
answered 2 hours ago
Thomas Pornin
66.8k12173252
A "simple" answer (but somewhat wrong) would be the following: define function $H$ which is the concatenation of MD5 and SHA-1; i.e. on input $x$, $H(x)$ will be the 288-bit string consisting of MD5($x$) (128 bits) followed by SHA-1($x$) (160 bits). If you have distinct two messages $x$ and $y$ such that MD5($x$) = MD5($y$) and SHA-1($x$) = SHA-1($y$), then, by definition, $x$ and $y$ are a colliding pair for $H$. Since $H$ has a 288-bit output, finding a collision for $H$ requires an average effort of, at most, $2^144$ invocations, since that's the best you can expect from a "perfect" hash function.
What's wrong in the paragraph above is that the $H$ function, as described above, is far from the "perfect" state. In 2004, Joux published (Multicollisions in Iterated Hash Functions. Application to Cascaded Constructions) an attack that works on "iterated" hash functions such as MD5 and SHA-1, which shows that even if MD5 and SHA-1 were both ideally strong (given their output size), the concatenation would not be stronger than the strongest of the two. In other words, even without leveraging known attacks on MD5 and SHA-1, a collision on the concatenated hash function $H$ can be found in about $2^80$ invocations. This work was generalized in 2006 by Hoch and Shamir (Breaking the ICE - Finding Multicollisions in Iterated Concatenated and Expanded (ICE) Hash Functions).
Now, both MD5 and SHA-1 have known structural attacks. In an answer to a previous question on that subject, @poncho explains how to use the known attacks on SHA-1 (with cost $2^61$) to make a simultaneous MD5+SHA-1 collision in effort $2^67$. Amusingly, this does not leverage any specific weakness of MD5; it would also work for a perfect 128-bit hash function instead of MD5.
answered 2 hours ago
Thomas Pornin
66.8k12173252
answered 2 hours ago
Thomas Pornin
66.8k12173252
answered 2 hours ago
Thomas Pornin
66.8k12173252
answered 2 hours ago
Thomas Pornin
66.8k12173252
66.8k12173252
add a comment |Â
add a comment |Â
Simon is a new contributor. Be nice, and check out our Code of Conduct.
Simon is a new contributor. Be nice, and check out our Code of Conduct.
Simon is a new contributor. Be nice, and check out our Code of Conduct.
Simon is a new contributor. Be nice, and check out our Code of Conduct.
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f63542%2fwhat-is-the-probability-to-produce-a-collision-under-two-different-hash-function%23new-answer', 'question_page');
);
Post as a guest
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
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
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
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
