What is the probability to produce a collision under two different hash functions?

The name of the pictureThe name of the pictureThe name of the pictureClash 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) ?










share|improve this question







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.























    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) ?










    share|improve this question







    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.





















      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) ?










      share|improve this question







      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






      share|improve this question







      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.











      share|improve this question







      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.









      share|improve this question




      share|improve this question






      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




      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.




















          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.






          share|improve this answer




















            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',
            convertImagesToLinks: false,
            noModals: false,
            showLowRepImageUploadWarning: true,
            reputationToPostImages: null,
            bindNavPrevention: true,
            postfix: "",
            noCode: true, onDemand: true,
            discardSelector: ".discard-answer"
            ,immediatelyShowMarkdownHelp:true
            );



            );






            Simon is a new contributor. Be nice, and check out our Code of Conduct.









             

            draft saved


            draft discarded


















            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






























            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.






            share|improve this answer
























              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.






              share|improve this answer






















                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.






                share|improve this answer












                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.







                share|improve this answer












                share|improve this answer



                share|improve this answer










                answered 2 hours ago









                Thomas Pornin

                66.8k12173252




                66.8k12173252




















                    Simon is a new contributor. Be nice, and check out our Code of Conduct.









                     

                    draft saved


                    draft discarded


















                    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.













                     


                    draft saved


                    draft discarded














                    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













































































                    Comments

                    Popular posts from this blog

                    What does second last employer means? [closed]

                    Installing NextGIS Connect into QGIS 3?

                    One-line joke