{"id":4536,"date":"2012-10-05T13:24:43","date_gmt":"2012-10-05T13:24:43","guid":{"rendered":"https:\/\/www.schneier.com\/when_will_we_se\/"},"modified":"2020-01-27T13:11:12","modified_gmt":"2020-01-27T13:11:12","slug":"when_will_we_se","status":"publish","type":"post","link":"https:\/\/www.schneier.com\/blog\/archives\/2012\/10\/when_will_we_se.html","title":{"rendered":"When Will We See Collisions for SHA-1?"},"content":{"rendered":"

On a NIST-sponsored hash function mailing list<\/a>, Jesse Walker (from Intel; also a member of the Skein<\/a> team) did some back-of-the-envelope calculations to estimate how long it will be before we see a practical collision attack against SHA-1. I’m reprinting his analysis here, so it reaches a broader audience.<\/p>\n

According to E-BASH<\/a>, the cost of one block of a SHA-1 operation on already deployed commodity microprocessors is about 214<\/sup> cycles. If Stevens’ attack<\/a> of 260<\/sup> SHA-1 operations serves as the baseline, then finding a collision costs about 214<\/sup> * 260<\/sup> ~ 274<\/sup> cycles.<\/p>\n

A core today provides about 231<\/sup> cycles\/sec; the state of the art is 8 = 23<\/sup> cores per processor for a total of 23<\/sup> * 231<\/sup> = 234<\/sup> cycles\/sec. A server typically has 4 processors, increasing the total to 22<\/sup> * 234<\/sup> = 236<\/sup> cycles\/sec. Since there are about 225<\/sup> sec\/year, this means one server delivers about 225<\/sup> * 236<\/sup> = 261<\/sup> cycles per year, which we can call a “server year.”<\/p>\n

There is ample evidence that Moore’s law will continue through the mid 2020s. Hence the number of doublings in processor power we can expect between now and 2021 is:<\/p>\n

3\/1.5 = 2 times by 2015 (3 = 2015 – 2012)<\/p>\n

6\/1.5 = 4 times by 2018 (6 = 2018 – 2012)<\/p>\n

9\/1.5 = 6 times by 2021 (9 = 2021 – 2012)<\/p><\/blockquote>\n

So a commodity server year should be about:<\/p>\n

261<\/sup> cycles\/year in 2012<\/p>\n

22<\/sup> * 261<\/sup> = 263<\/sup> cycles\/year by 2015<\/p>\n

24<\/sup> * 261<\/sup> = 265<\/sup> cycles\/year by 2018<\/p>\n

26<\/sup> * 261<\/sup> = 267<\/sup> cycles\/year by 2021<\/p><\/blockquote>\n

Therefore, on commodity hardware, Stevens’ attack should cost approximately:<\/p>\n

274<\/sup> \/ 261<\/sup> = 213<\/sup> server years in 2012<\/p>\n

274<\/sup> \/ 263<\/sup> = 211<\/sup> server years by 2015<\/p>\n

274<\/sup> \/ 265<\/sup> = 29<\/sup> server years by 2018<\/p>\n

274<\/sup> \/ 267<\/sup> = 27<\/sup> server years by 2021<\/p><\/blockquote>\n

Today Amazon rents compute time on commodity servers for about $0.04 \/ hour ~ $350 \/year. Assume compute rental fees remain fixed while server capacity keeps pace with Moore’s law. Then, since log2<\/sub>(350) ~ 8.4 the cost of the attack will be approximately:<\/p>\n

213<\/sup> * 28.4<\/sup> = 221.4<\/sup> ~ $2.77M in 2012<\/p>\n

211<\/sup> * 28.4<\/sup> = 219.4<\/sup> ~ $700K by 2015<\/p>\n

29<\/sup> * 28.4<\/sup> = 217.4<\/sup> ~ $173K by 2018<\/p>\n

27<\/sup> * 28.4<\/sup> = 215.4<\/sup> ~ $43K by 2021<\/p><\/blockquote>\n

A collision attack is therefore well within the range of what an organized crime syndicate can practically budget by 2018, and a university research project by 2021.<\/p>\n

Since this argument only takes into account commodity hardware and not instruction set improvements (e.g., ARM 8 specifies a SHA-1 instruction), other commodity computing devices with even greater processing power (e.g., GPUs), and custom hardware, the need to transition from SHA-1 for collision resistance functions is probably more urgent than this back-of-the-envelope analysis suggests.<\/p><\/blockquote>\n

Any increase in the number of cores per CPU, or the number of CPUs per server, also affects these calculations. Also, any improvements in cryptanalysis will further reduce the complexity of this attack.<\/p>\n

The point is that we in the community need to start the migration away from SHA-1 and to SHA-2\/SHA-3 now.<\/p>\n","protected":false},"excerpt":{"rendered":"

On a NIST-sponsored hash function mailing list<\/a>, Jesse Walker (from Intel; also a member of the Skein<\/a> team) did some back-of-the-envelope calculations to estimate how long it will be before we see a practical collision attack against SHA-1. I’m reprinting his analysis here, so it reaches a broader audience.<\/p>\n

\n

According to E-BASH<\/a>, the cost of one block of a SHA-1 operation on already deployed commodity microprocessors is about 214<\/sup> cycles. If Stevens’ attack<\/a> of 260<\/sup> SHA-1 operations serves as the baseline, then finding a collision costs about 214…<\/sup><\/p>\n<\/blockquote>\n<\/div>

Read More \u2192<\/a><\/div>","protected":false},"author":0,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"_wpas_customize_per_network":false},"categories":[1],"tags":[304,147,331,192,194],"class_list":["post-4536","post","type-post","status-publish","format-standard","hentry","category-uncategorized","tag-cryptanalysis","tag-cryptography","tag-hashes","tag-nist","tag-sha-1"],"yoast_head":"\nWhen Will We See Collisions for SHA-1? - Schneier on Security<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/www.schneier.com\/blog\/archives\/2012\/10\/when_will_we_se.html\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"When Will We See Collisions for SHA-1? - Schneier on Security\" \/>\n<meta property=\"og:description\" content=\"On a NIST-sponsored hash function mailing list, Jesse Walker (from Intel; also a member of the Skein team) did some back-of-the-envelope calculations to estimate how long it will be before we see a practical collision attack against SHA-1. I’m reprinting his analysis here, so it reaches a broader audience. According to E-BASH, the cost of one block of a SHA-1 operation on already deployed commodity microprocessors is about 214 cycles. If Stevens’ attack of 260 SHA-1 operations serves as the baseline, then finding a collision costs about 214...\" \/>\n<meta property=\"og:url\" content=\"https:\/\/www.schneier.com\/blog\/archives\/2012\/10\/when_will_we_se.html\" \/>\n<meta property=\"og:site_name\" content=\"Schneier on Security\" \/>\n<meta property=\"article:published_time\" content=\"2012-10-05T13:24:43+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2020-01-27T13:11:12+00:00\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data1\" content=\"2 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\\\/\\\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\\\/\\\/www.schneier.com\\\/blog\\\/archives\\\/2012\\\/10\\\/when_will_we_se.html#article\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/www.schneier.com\\\/blog\\\/archives\\\/2012\\\/10\\\/when_will_we_se.html\"},\"author\":{\"name\":\"\",\"@id\":\"\"},\"headline\":\"When Will We See Collisions for SHA-1?\",\"datePublished\":\"2012-10-05T13:24:43+00:00\",\"dateModified\":\"2020-01-27T13:11:12+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\\\/\\\/www.schneier.com\\\/blog\\\/archives\\\/2012\\\/10\\\/when_will_we_se.html\"},\"wordCount\":408,\"commentCount\":62,\"keywords\":[\"cryptanalysis\",\"cryptography\",\"hashes\",\"NIST\",\"SHA-1\"],\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\\\/\\\/www.schneier.com\\\/blog\\\/archives\\\/2012\\\/10\\\/when_will_we_se.html#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\\\/\\\/www.schneier.com\\\/blog\\\/archives\\\/2012\\\/10\\\/when_will_we_se.html\",\"url\":\"https:\\\/\\\/www.schneier.com\\\/blog\\\/archives\\\/2012\\\/10\\\/when_will_we_se.html\",\"name\":\"When Will We See Collisions for SHA-1? - Schneier on Security\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/www.schneier.com\\\/#website\"},\"datePublished\":\"2012-10-05T13:24:43+00:00\",\"dateModified\":\"2020-01-27T13:11:12+00:00\",\"author\":{\"@id\":\"\"},\"breadcrumb\":{\"@id\":\"https:\\\/\\\/www.schneier.com\\\/blog\\\/archives\\\/2012\\\/10\\\/when_will_we_se.html#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\\\/\\\/www.schneier.com\\\/blog\\\/archives\\\/2012\\\/10\\\/when_will_we_se.html\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\\\/\\\/www.schneier.com\\\/blog\\\/archives\\\/2012\\\/10\\\/when_will_we_se.html#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\\\/\\\/www.schneier.com\\\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"When Will We See Collisions for SHA-1?\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\\\/\\\/www.schneier.com\\\/#website\",\"url\":\"https:\\\/\\\/www.schneier.com\\\/\",\"name\":\"Schneier on Security\",\"description\":\"\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\\\/\\\/www.schneier.com\\\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"When Will We See Collisions for SHA-1? - Schneier on Security","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/www.schneier.com\/blog\/archives\/2012\/10\/when_will_we_se.html","og_locale":"en_US","og_type":"article","og_title":"When Will We See Collisions for SHA-1? - Schneier on Security","og_description":"On a NIST-sponsored hash function mailing list, Jesse Walker (from Intel; also a member of the Skein team) did some back-of-the-envelope calculations to estimate how long it will be before we see a practical collision attack against SHA-1. I’m reprinting his analysis here, so it reaches a broader audience. According to E-BASH, the cost of one block of a SHA-1 operation on already deployed commodity microprocessors is about 214 cycles. If Stevens’ attack of 260 SHA-1 operations serves as the baseline, then finding a collision costs about 214...","og_url":"https:\/\/www.schneier.com\/blog\/archives\/2012\/10\/when_will_we_se.html","og_site_name":"Schneier on Security","article_published_time":"2012-10-05T13:24:43+00:00","article_modified_time":"2020-01-27T13:11:12+00:00","twitter_card":"summary_large_image","twitter_misc":{"Est. reading time":"2 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/www.schneier.com\/blog\/archives\/2012\/10\/when_will_we_se.html#article","isPartOf":{"@id":"https:\/\/www.schneier.com\/blog\/archives\/2012\/10\/when_will_we_se.html"},"author":{"name":"","@id":""},"headline":"When Will We See Collisions for SHA-1?","datePublished":"2012-10-05T13:24:43+00:00","dateModified":"2020-01-27T13:11:12+00:00","mainEntityOfPage":{"@id":"https:\/\/www.schneier.com\/blog\/archives\/2012\/10\/when_will_we_se.html"},"wordCount":408,"commentCount":62,"keywords":["cryptanalysis","cryptography","hashes","NIST","SHA-1"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/www.schneier.com\/blog\/archives\/2012\/10\/when_will_we_se.html#respond"]}]},{"@type":"WebPage","@id":"https:\/\/www.schneier.com\/blog\/archives\/2012\/10\/when_will_we_se.html","url":"https:\/\/www.schneier.com\/blog\/archives\/2012\/10\/when_will_we_se.html","name":"When Will We See Collisions for SHA-1? - Schneier on Security","isPartOf":{"@id":"https:\/\/www.schneier.com\/#website"},"datePublished":"2012-10-05T13:24:43+00:00","dateModified":"2020-01-27T13:11:12+00:00","author":{"@id":""},"breadcrumb":{"@id":"https:\/\/www.schneier.com\/blog\/archives\/2012\/10\/when_will_we_se.html#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/www.schneier.com\/blog\/archives\/2012\/10\/when_will_we_se.html"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/www.schneier.com\/blog\/archives\/2012\/10\/when_will_we_se.html#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/www.schneier.com\/"},{"@type":"ListItem","position":2,"name":"When Will We See Collisions for SHA-1?"}]},{"@type":"WebSite","@id":"https:\/\/www.schneier.com\/#website","url":"https:\/\/www.schneier.com\/","name":"Schneier on Security","description":"","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/www.schneier.com\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"}]}},"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.schneier.com\/wp-json\/wp\/v2\/posts\/4536","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.schneier.com\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.schneier.com\/wp-json\/wp\/v2\/types\/post"}],"replies":[{"embeddable":true,"href":"https:\/\/www.schneier.com\/wp-json\/wp\/v2\/comments?post=4536"}],"version-history":[{"count":1,"href":"https:\/\/www.schneier.com\/wp-json\/wp\/v2\/posts\/4536\/revisions"}],"predecessor-version":[{"id":56593,"href":"https:\/\/www.schneier.com\/wp-json\/wp\/v2\/posts\/4536\/revisions\/56593"}],"wp:attachment":[{"href":"https:\/\/www.schneier.com\/wp-json\/wp\/v2\/media?parent=4536"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.schneier.com\/wp-json\/wp\/v2\/categories?post=4536"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.schneier.com\/wp-json\/wp\/v2\/tags?post=4536"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}