{"id":15754,"date":"2017-03-01T09:07:24","date_gmt":"2017-03-01T14:07:24","guid":{"rendered":"http:\/\/www.megalextoria.com\/wordpress\/?p=15754"},"modified":"2017-03-01T09:07:24","modified_gmt":"2017-03-01T14:07:24","slug":"cryptographers-demonstrate-collision-in-popular-sha-1-algorithm","status":"publish","type":"post","link":"http:\/\/www.megalextoria.com\/wordpress\/index.php\/2017\/03\/01\/cryptographers-demonstrate-collision-in-popular-sha-1-algorithm\/","title":{"rendered":"Cryptographers Demonstrate Collision in Popular SHA-1 Algorithm"},"content":{"rendered":"<div class=\"panel-pane pane-entity-field pane-node-body\">\n<div class=\"pane-content\">\n<div class=\"field field-name-body field-type-text-with-summary field-label-hidden\">\n<div class=\"field-items\">\n<div class=\"field-item even\">\n<p><a href=\"https:\/\/www.eff.org\/deeplinks\/2017\/02\/cryptographers-demonstrate-collision-popular-sha-1-algorithm\"><img decoding=\"async\" class=\"alignnone size-full\" src=\"http:\/\/www.megalextoria.com\/wordpress\/wp-content\/uploads\/2017\/03\/eff-og-3.png\" alt=\"\" \/><\/a><\/p>\n<p>On February 23rd, a joint team from the\u00a0<a href=\"https:\/\/www.cwi.nl\/\">CWI Amsterdam<\/a>\u00a0and Google announced that they had\u00a0<a href=\"https:\/\/www.cwi.nl\/news\/2017\/cwi-and-google-announce-first-collision-industry-security-standard-sha-1\">generated<\/a>\u00a0the\u00a0<a href=\"https:\/\/security.googleblog.com\/2017\/02\/announcing-first-sha1-collision.html\">first ever collision<\/a>\u00a0in the SHA-1 cryptographic hashing algorithm. SHA-1 has\u00a0<a href=\"http:\/\/2012.sharcs.org\/slides\/stevens.pdf\">long been considered theoretically insecure<\/a>\u00a0by cryptanalysts due to weaknesses in the algorithm design, but this marks the first time researchers were actually able to demonstrate a real-world example of the insecurity. In addition to being a powerful Proof of Concept (POC), the computing power that went into generating the proof was notable:<\/p>\n<blockquote><p>We then leveraged Google\u2019s technical expertise and cloud infrastructure to compute the collision which is one of the largest computations ever completed.<\/p>\n<p>Here are some numbers that give a sense of how large scale this computation was:<\/p>\n<ul>\n<li>Nine quintillion (9,223,372,036,854,775,808) SHA1 computations in total<\/li>\n<li>6,500 years of CPU computation to complete the attack first phase<\/li>\n<li>110 years of GPU computation to complete the second phase<\/li>\n<\/ul>\n<\/blockquote>\n<p>The CWI Amsterdam and Google researchers launched\u00a0<a href=\"https:\/\/shattered.io\/\">shattered.io<\/a>, a site explaining the attack and linking to two distinct pdf files:\u00a0<a href=\"https:\/\/shattered.io\/static\/shattered-1.pdf\">shattered-1.pdf<\/a>\u00a0and\u00a0<a href=\"https:\/\/shattered.io\/static\/shattered-2.pdf\">shattered-2.pdf<\/a>\u00a0with different contents but the same SHA-1 checksum.<\/p>\n<h2 id=\"what-is-sha-1-anyway\">What is SHA-1, anyway?<\/h2>\n<p>SHA-1 is part of a class of algorithms known as collision-resistant hashing functions, which create a short digest of some arbitrary data. That can be a piece of text, a database entry, or a file, just to name a few examples. For instance, the SHA-1 result or &#8216;checksum&#8217; of the first sentence in this paragraph is\u00a0<code>472825ab28b45d64cd234a22398bba755dd56485<\/code>. Creating a digest of data is useful in many contexts. For example, making a cryptographic signature for a digest is more convenient and faster than signing the entire contents of a message, a fact that many cryptographic systems have taken advantage of. Lots of software uses this type of hashing function, and relies on the collision-resistance property to verify that the contents of the original message haven&#8217;t been corrupted or tampered with.<\/p>\n<h2 id=\"sunsetting-sha-1\">Sunsetting SHA-1<\/h2>\n<p>While a brute-force attack (simply trying all the possibilities until a collision is found) remains impractical, low-level analysis of the algorithm has revealed deep fractures in its design. Over time, as these theoretical attacks against the algorithm have\u00a0<a href=\"https:\/\/www.schneier.com\/blog\/archives\/2009\/06\/ever_better_cry.html\">gotten better<\/a>, many have moved away from SHA-1 to guarantee security. In 2014, the\u00a0<a href=\"https:\/\/cabforum.org\/2014\/10\/16\/ballot-118-sha-1-sunset\/\">CA Browser Forum<\/a>\u00a0(an organization which comprises the trust-roots for the web) passed a ballot which prevented new HTTPS certificates from being issued using SHA-1 after 2015. And earlier this year, the major browsers started to\u00a0<a href=\"https:\/\/security.googleblog.com\/2016\/11\/sha-1-certificates-in-chrome.html\">remove<\/a>\u00a0<a href=\"https:\/\/blog.mozilla.org\/security\/2016\/10\/18\/phasing-out-sha-1-on-the-public-web\/\">support<\/a>\u00a0for HTTPS sites which serve SHA-1 certificates. In general, companies and software projects were moving away from relying on SHA-1. Next-generation hashing algorithms such as SHA-256 and SHA-3 have been available for a long time, and provide far better guarantees against collisions.<\/p>\n<h2 id=\"so-whats-the-big-deal\">So what&#8217;s the big deal?<\/h2>\n<p>Unfortunately, the migration away from SHA-1 has not been universal. Some programs, such as the version control system\u00a0<a href=\"https:\/\/git-scm.com\/\">Git<\/a>, have SHA-1 hard-baked into its code. This makes it difficult for projects which rely on Git to ditch the algorithm altogether. The encrypted e-mail system\u00a0<a href=\"https:\/\/en.wikipedia.org\/wiki\/Pretty_Good_Privacy\">PGP<\/a>\u00a0also relies on it in certain places.<\/p>\n<p>While initially promising to deprecate SHA-1 in a similar time-frame as the other browsers, Internet Explorer has pushed that date back to mid-2017. This means that sites with certificates signed by the insecure function will still be trusted for IE users. And while the collision was demonstrated on two pdf files, there is nothing stopping others from crafting a malicious X.509 certificate with the same checksum as a valid certificate, and using that to impersonate a legitimate HTTPS site. History (and Moore&#8217;s law) shows us that this only becomes easier over time. The first full collision of the then-popular MD5 hashing algorithm was\u00a0<a href=\"https:\/\/eprint.iacr.org\/2004\/264\">demonstrated<\/a>\u00a0in August 2004. Less than seven months later, an X.509 collision was\u00a0<a href=\"https:\/\/eprint.iacr.org\/2005\/067\">shown<\/a>.<\/p>\n<p>Last year, we\u00a0<a href=\"https:\/\/www.eff.org\/deeplinks\/2016\/12\/what-happened-crypto-2016\">pointed out that<\/a>\u00a0a SHA-1 collision in 2017 was entirely foreseeable, and will happen again in the future. To have robust protections against cryptographic vulnerabilities, software projects have to take these vulnerabilities seriously\u00a0<em>before<\/em>\u00a0they turn into demonstrated attacks, when they are still theoretical but within the realm of possibility. Otherwise, the time it takes to migrate away from these insecure algorithms will be well used by attackers, as well.<\/p>\n<p><center><br \/>\n<b><\/b><br \/>\n<\/center><\/p>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<div class=\"panel-separator\">\n<\/div>\n<p class=\"raindrops-press-this\">Source: <em><a href=\"https:\/\/www.eff.org\/deeplinks\/2017\/02\/cryptographers-demonstrate-collision-popular-sha-1-algorithm\">Cryptographers Demonstrate Collision in Popular SHA-1 Algorithm | Electronic Frontier Foundation<\/a><\/em><\/p>\n","protected":false},"excerpt":{"rendered":"<p>On February 23rd, a joint team from the\u00a0CWI Amsterdam\u00a0and Google announced that they had\u00a0generated\u00a0the\u00a0first ever collision\u00a0in the SHA-1 cryptographic hashing algorithm. SHA-1 has\u00a0long been considered theoretically insecure\u00a0by cryptanalysts due to weaknesses in the algorithm design, but this marks the first time researchers were actually able to demonstrate a real-world example of the insecurity. In addition to being a powerful Proof of Concept (POC), the computing power that went into generating the proof was notable: We then leveraged Google\u2019s technical expertise and cloud infrastructure to compute the collision which is one of the largest computations ever completed. Here are some numbers that give a sense of how large scale this computation was: Nine quintillion (9,223,372,036,854,775,808) SHA1 computations in total 6,500 years of CPU computation to complete the attack first phase 110 years of GPU computation to complete the second phase The CWI Amsterdam and Google researchers launched\u00a0shattered.io, a site explaining the attack and linking to two distinct pdf files:\u00a0shattered-1.pdf\u00a0and\u00a0shattered-2.pdf\u00a0with different contents but the same SHA-1 checksum. What is SHA-1, anyway? SHA-1 is part of a class of algorithms known as collision-resistant hashing functions, which create a short digest of some arbitrary data. That can be a piece of text, a database [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4,15],"tags":[513,1517,2463],"class_list":["post-15754","post","type-post","status-publish","format-standard","hentry","category-computer-arcana","category-news-and-politics","tag-cryptography","tag-security","tag-sha-1"],"_links":{"self":[{"href":"http:\/\/www.megalextoria.com\/wordpress\/index.php\/wp-json\/wp\/v2\/posts\/15754","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.megalextoria.com\/wordpress\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.megalextoria.com\/wordpress\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.megalextoria.com\/wordpress\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.megalextoria.com\/wordpress\/index.php\/wp-json\/wp\/v2\/comments?post=15754"}],"version-history":[{"count":0,"href":"http:\/\/www.megalextoria.com\/wordpress\/index.php\/wp-json\/wp\/v2\/posts\/15754\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.megalextoria.com\/wordpress\/index.php\/wp-json\/wp\/v2\/media?parent=15754"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.megalextoria.com\/wordpress\/index.php\/wp-json\/wp\/v2\/categories?post=15754"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.megalextoria.com\/wordpress\/index.php\/wp-json\/wp\/v2\/tags?post=15754"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}