{"id":15142,"date":"2022-06-18T20:09:41","date_gmt":"2022-06-19T00:09:41","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=15142"},"modified":"2026-06-08T13:55:28","modified_gmt":"2026-06-08T17:55:28","slug":"tr-249-parallel-collision-search-with-application-to-hash-functions-and-discrete-logarithms","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1994\/tr-249-parallel-collision-search-with-application-to-hash-functions-and-discrete-logarithms\/","title":{"rendered":"TR-249: Parallel Collision Search with Application to Hash Functions and Discrete Logarithms"},"content":{"rendered":"\n<section class=\"w-screen px-6 cu-section cu-section--white ml-offset-center md:px-8 lg:px-14\">\n    <div class=\"space-y-6 cu-max-w-child-5xl  md:space-y-10 cu-prose-first-last\">\n\n            <div class=\"cu-textmedia flex flex-col lg:flex-row mx-auto gap-6 md:gap-10 my-6 md:my-12 first:mt-0 max-w-5xl\">\n        <div class=\"justify-start cu-textmedia-content cu-prose-first-last\" style=\"flex: 0 0 100%;\">\n            <header class=\"font-light prose-xl cu-pageheader md:prose-2xl cu-component-updated cu-prose-first-last\">\n                                    <h1 class=\"cu-prose-first-last font-semibold !mt-2 mb-4 md:mb-6 relative after:absolute after:h-px after:bottom-0 after:bg-cu-red after:left-px text-3xl md:text-4xl lg:text-5xl lg:leading-[3.5rem] pb-5 after:w-10 text-cu-black-700 not-prose\">\n                        TR-249: Parallel Collision Search with Application to Hash Functions and Discrete Logarithms\n                    <\/h1>\n                \n                                \n                            <\/header>\n\n                    <\/div>\n\n            <\/div>\n\n    <\/div>\n<\/section>\n\n\n\n<p>Carleton University<br><a href=\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1994\/\">Technical Report<\/a> <strong>TR-249<\/strong><br>July 1994<\/p>\n\n\n\n<h2 id=\"parallel-collision-search-with-application-to-hash-functions-and-discrete-logarithms\" class=\"wp-block-heading\">Parallel Collision Search with Application to Hash Functions and Discrete Logarithms<\/h2>\n\n\n\n<p>Paul C. van Oorschot &amp; Michael J. Wiener<\/p>\n\n\n\n<h3 id=\"abstract\" class=\"wp-block-heading\">Abstract<\/h3>\n\n\n\n<p>Current techniques for collision search with feasible memory requirements involve pseudo-random walks through some space where one must wait for the result of the current step before the next step can begin. These techniques are serial in nature, and direct parallelization is inefficient. We present a simple new method of parallelizing collision searches that greatly extends the reach of practical attacks. The new method is illustrated with applications to hash functions and discrete logarithms in cyclic groups. In the case of hash functions, we begin with two messages; the first is a message that we want our target to digitally sign, and the second is a message that the target is willing to sign. Using collision search adapted for hashing collisions, one can find slightly altered versions of these messages such that the two new messages give the same hash result. As a particular example, a $10 million custom machine for applying parallel collision search to the l\\1D5 hash function could complete an attack with an expected run time of 24 days. This machine would be specific to l\\1D5, but could be used for any pair of messages. For discrete logarithms in cyclic groups, ideas from Pollard&#8217;s rho and lambda methods for index computation are combined to allow efficient parallel implementation using the new method. As a concrete example, we consider an elliptic curve cryptosystem over GF(2155) with the order of the curve having largest prime factor of approximate size 1036. A $10 million machine custom built for this finite field could compute a discrete logarithm with an expected run time of 36 days.<\/p>\n\n\n\n<p><a href=\"https:\/\/carleton.ca\/scs\/wp-content\/uploads\/sites\/260\/TR-249.pdf\">TR-249.pdf<\/a><\/p>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Carleton UniversityTechnical Report TR-249July 1994 Parallel Collision Search with Application to Hash Functions and Discrete Logarithms Paul C. van Oorschot &amp; Michael J. Wiener Abstract Current techniques for collision search with feasible memory requirements involve pseudo-random walks through some space where one must wait for the result of the current step before the next step [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":11914,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_acf_changed":false,"_cu_dining_location_slug":"","footnotes":"","_links_to":"","_links_to_target":""},"cu_page_type":[],"class_list":["post-15142","page","type-page","status-publish","hentry"],"acf":{"cu_post_thumbnail":""},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/15142","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/comments?post=15142"}],"version-history":[{"count":4,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/15142\/revisions"}],"predecessor-version":[{"id":24395,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/15142\/revisions\/24395"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/11914"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=15142"}],"wp:term":[{"taxonomy":"cu_page_type","embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/cu_page_type?post=15142"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}