SHA-1 has been broken. Not a reduced-round version. Not a simplified version. The real thing.
1860ba06cb51de8ca806e1c74ca315eb7fd42ed746dfb99f55de2d3b5b9319b6<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<html>
<head>
<title>Schneier on Security: SHA-1 Broken</title>
<!-- robots content="noindex" -->
<base href="http://www.schneier.com/">
<link rel="STYLESHEET" type="text/css" href="schneier-safe.css">
<link rel="STYLESHEET" type="text/css" href="blog.css">
<link rel="alternate" type="application/atom+xml" title="Atom" href="http://www.schneier.com/blog/atom.xml">
<link rel="alternate" type="application/rss+xml" title="RSS 1.0" href="http://www.schneier.com/blog/index.rdf">
<link rel="alternate" type="application/rss+xml" title="RSS 2.0" href="http://www.schneier.com/blog/index.xml">
<link rel="EditURI" type="application/rsd+xml" title="RSD" href="http://www.schneier.com/blog/rsd.xml">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<link rel="start" href="http://www.schneier.com/blog/" title="Home">
<link rel="prev" href="http://www.schneier.com/blog/archives/2005/02/rsa_conference.html" title="RSA Conference">
<link rel="next" href="http://www.schneier.com/blog/archives/2005/02/unicode_url_hac_1.html" title="Unicode URL Hack">
<!-- /robots -->
<script type="text/javascript" language="javascript">
<!--
var HOST = 'www.schneier.com';
// Copyright (c) 1996-1997 Athenia Associates.
// http://www.webreference.com/js/
// License is granted if and only if this entire
// copyright notice is included. By Tomer Shiran.
function setCookie (name, value, expires, path, domain, secure) {
var curCookie = name + "=" + escape(value) + (expires ? "; expires=" + expires : "") + (path ? "; path=" + path : "") + (domain ? "; domain=" + domain : "") + (secure ? "secure" : "");
document.cookie = curCookie;
}
function getCookie (name) {
var prefix = name + '=';
var c = document.cookie;
var nullstring = '';
var cookieStartIndex = c.indexOf(prefix);
if (cookieStartIndex == -1)
return nullstring;
var cookieEndIndex = c.indexOf(";", cookieStartIndex + prefix.length);
if (cookieEndIndex == -1)
cookieEndIndex = c.length;
return unescape(c.substring(cookieStartIndex + prefix.length, cookieEndIndex));
}
function deleteCookie (name, path, domain) {
if (getCookie(name))
document.cookie = name + "=" + ((path) ? "; path=" + path : "") + ((domain) ? "; domain=" + domain : "") + "; expires=Thu, 01-Jan-70 00:00:01 GMT";
}
function fixDate (date) {
var base = new Date(0);
var skew = base.getTime();
if (skew > 0)
date.setTime(date.getTime() - skew);
}
function rememberMe (f) {
var now = new Date();
fixDate(now);
now.setTime(now.getTime() + 365 * 24 * 60 * 60 * 1000);
now = now.toGMTString();
if (f.author != undefined)
setCookie('mtcmtauth', f.author.value, now, '/', '', '');
if (f.email != undefined)
setCookie('mtcmtmail', f.email.value, now, '/', '', '');
if (f.url != undefined)
setCookie('mtcmthome', f.url.value, now, '/', '', '');
}
function forgetMe (f) {
deleteCookie('mtcmtmail', '/', '');
deleteCookie('mtcmthome', '/', '');
deleteCookie('mtcmtauth', '/', '');
f.email.value = '';
f.author.value = '';
f.url.value = '';
}
//-->
</script>
<!--
<rdf:RDF xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
xmlns:trackback="http://madskills.com/public/xml/rss/module/trackback/"
xmlns:dc="http://purl.org/dc/elements/1.1/">
<rdf:Description
rdf:about="http://www.schneier.com/blog/archives/2005/02/sha1_broken.html"
trackback:ping="http://www.schneier.com/cgi-bin/mt/mt-tb.cgi/130"
dc:title="SHA-1 Broken"
dc:identifier="http://www.schneier.com/blog/archives/2005/02/sha1_broken.html"
dc:subject=""
dc:description="SHA-1 has been broken. Not a reduced-round version. Not a simplified version. The real thing. The research team of Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu (mostly from Shandong University in China) have been quietly circulating a paper describing..."
dc:creator="schneier"
dc:date="2005-02-15T19:15:28-06:00" />
</rdf:RDF>
-->
</head>
<body>
<table class="main" cellspacing=0>
<tr><td class="bodycolor"></td><td class="kludge"> </td><td class="masthead"><p class="mastname"><!-- robots content="noindex" -->Bruce Schneier<!-- /robots --></td><td class="kludge"> </td><td class="bodycolor"></td></tr>
<tr><td class="menua">
<!-- robots content="noindex" -->
<P class="menusingle"><a class="menulink" href="index.html">Home</a>
<P class="menusingle"><a class="menulink" href="blog/">Weblog</a>
<P class="menusingle"><a class="menulink" href="crypto-gram.html">Crypto-Gram Newsletter</a>
<P class="menusingle"><a class="menulink" href="books.html">Books</a>
<P class="menusingle"><a class="menulink" href="essays.html">Essays and Op Eds</a>
<P class="menusingle"><a class="menulink" href="essays-comp.html">Computer Security Articles</a>
<P class="menusingle"><a class="menulink" href="news.html">In the News</a>
<P class="menusingle"><a class="menulink" href="schedule.html">Speaking Schedule</a>
<P class="menusingle"><a class="menulink" href="passsafe.html">Password Safe</a>
<P class="menusingle"><a class="menulink" href="resources.html">Cryptography and Computer Security Resources</a>
<P class="menusingle"><a class="menulink" href="contact.html">Contact Information</a>
<!-- /robots -->
</td>
<td class="kludge"> </td>
<td class="contentcell">
<!-- begin page content -->
<div class="indivbody">
<!-- robots content="noindex" -->
<h1>Schneier on Security</h1>
<p>A weblog covering security and security technology.</p>
<p align="right">
<a href="http://www.schneier.com/blog/archives/2005/02/rsa_conference.html">« RSA Conference</a> |
<a href="http://www.schneier.com/blog/">Main</a>
| <a href="http://www.schneier.com/blog/archives/2005/02/unicode_url_hac_1.html">Unicode URL Hack »</a>
</p>
<!-- /robots -->
<h2>February 15, 2005</h2>
<!-- robots content="noindex" -->
<h3>SHA-1 Broken</h3>
<!-- /robots -->
<p>SHA-1 has been broken. Not a reduced-round version. Not a simplified version. The real thing.</p>
<p>The research team of Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu (mostly from Shandong University in China) have been quietly circulating a paper describing their results:</p>
<ul>
<li>collisions in the the full SHA-1 in 2**69 hash operations, much less than the brute-force attack of 2**80 operations based on the hash length.
<p><li>collisions in SHA-0 in 2**39 operations.</p>
<p><li>collisions in 58-round SHA-1 in 2**33 operations.</p>
</ul>
<p>This attack builds on previous attacks on SHA-0 and SHA-1, and is a major, major cryptanalytic result. It pretty much puts a bullet into SHA-1 as a hash function for digital signatures (although it doesn't affect applications such as HMAC where collisions aren't important). </p>
<p>The paper isn't generally available yet. At this point I can't tell if the attack is real, but the paper looks good and this is a reputable research team.</p>
<p>More details when I have them. </p>
<p>Update: See <a href="http://www.schneier.com/blog/archives/2005/02/cryptanalysis_o.html">here</a></p>
<div id="a000130more"><div id="more">
</div></div>
<p class="posted"><a href="http://www.schneier.com/blog/archives/2005/02/sha1_broken.html">Posted on February 15, 2005 at 07:15 PM</a>
</div>
<div class="trackbacks">
<h2 id="trackbacks">Trackback Pings</h2>
<p class="techstuff">TrackBack URL for this entry:<br>
http://www.schneier.com/cgi-bin/mt/mt-tb.cgi/130</p>
<p>Listed below are links to weblogs that reference <a href="http://www.schneier.com/blog/archives/2005/02/sha1_broken.html">SHA-1 Broken</a>:</p>
<p id="p1013">
» <a href="http://scottstuff.net/scott/archives/000371.html">SHA-1 Broken</a> from *scottstuff*<br>
Bruce Schneier: SHA-1 has been broken. Not a reduced-round version. Not a simplified version. The real thing. The research team of Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu (mostly from Shandong University in China) have been quietly circulating a pa... <a href="http://scottstuff.net/scott/archives/000371.html">[Read More]</a>
</p>
<p class="posted">Tracked on February 15, 2005 07:45 PM</p>
<p id="p1020">
» <a href="http://james.seng.cc/archives/2005/02/16/sha-1_broken.html">SHA-1 broken</a> from James Seng's Blog<br>
<p>From <a href="http://www.schneier.com/blog/archives/2005/02/sha1_broken.html">Bruce Schneier</a>:</p>
<p><blockquote>SHA-1 has been broken. Not a reduced-round version. Not a simplified version. The real thing.</blockquote></p>
<p>The research team of Xiaoyun Wan</p> <a href="http://james.seng.cc/archives/2005/02/16/sha-1_broken.html">[Read More]</a>
</p>
<p class="posted">Tracked on February 15, 2005 09:00 PM</p>
<p id="p1022">
» <a href="http://www.jal.org/blog/archive/2005/02/running_out_of_hash_functions.html">Running out of hash functions</a> from Descriptive Epistemology<br>
Bruce says, SHA-1 has been broken. Not a reduced-round version. Not a simplified version. The real thing. The research team of Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu (mostly from Shandong University in China) have been quietly circulating a... <a href="http://www.jal.org/blog/archive/2005/02/running_out_of_hash_functions.html">[Read More]</a>
</p>
<p class="posted">Tracked on February 15, 2005 09:51 PM</p>
<p id="p1023">
» <a href="http://www.fastchicken.co.nz/blog/PermaLink,guid,452e9e0f-5efa-44c2-a641-f6e87d715894.aspx">SHA-1 broken.</a> from The Chicken Coop<br>
<a href="http://www.fastchicken.co.nz/blog/PermaLink,guid,452e9e0f-5efa-44c2-a641-f6e87d715894.aspx">[Read More]</a>
</p>
<p class="posted">Tracked on February 15, 2005 09:52 PM</p>
<p id="p1024">
» <a href="http://blog.haqd.com/archives/pof/2005/02/sha1_has_been_b.php">sha-1 has been broken</a> from Party of Five<br>
From Bruce Schneier’s weblog: The research team of Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu (mostly from Shandong University... <a href="http://blog.haqd.com/archives/pof/2005/02/sha1_has_been_b.php">[Read More]</a>
</p>
<p class="posted">Tracked on February 15, 2005 09:55 PM</p>
<p id="p1026">
» <a href="http://www.hellblazer.com/archives/2005/02/sha1_broken.html">SHA-1 Broken</a> from Hellblazer<br>
Via Schneier.SHA-1 has been broken. Not a reduced-round version. Not a simplified version. The real thing. The research team of Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu (mostly from Shandong University in China) have been quietly circulating a paper... <a href="http://www.hellblazer.com/archives/2005/02/sha1_broken.html">[Read More]</a>
</p>
<p class="posted">Tracked on February 15, 2005 10:20 PM</p>
<p id="p1027">
» <a href="http://www.cwalsh.org/blog/archives/000315.php">SHA-1 Broken</a> from The Security Blanket<br>
So says Bruce Schneier. Wow..... <a href="http://www.cwalsh.org/blog/archives/000315.php">[Read More]</a>
</p>
<p class="posted">Tracked on February 15, 2005 10:25 PM</p>
<p id="p1028">
» <a href="http://ddll.sdf1.net/archives/003046.html">SHA-1 Bites The Dust</a> from The Slakinski Log<br>
SHA-1 has been broken. Not a reduced-round version. Not a simplified version. The real thing. *sigh* I liked SHA-1 over MD5... Larger versions of SHA are to big for simple hash functions... so I guess its back to MD5... <a href="http://ddll.sdf1.net/archives/003046.html">[Read More]</a>
</p>
<p class="posted">Tracked on February 15, 2005 10:28 PM</p>
<p id="p1029">
» <a href="http://www.hermann-uwe.de/blog/sha-1-broken">SHA-1 Broken!</a> from Uwe Hermann<br>
<p>Let me quote <a href="http://www.schneier.com/blog/archives/2005/02/sha1_broken.html">Bruce Schneier</a> here, as I couldn't possibly express it any clearer:</p>
<p><a href="http://en.wikipedia.org/wiki/SHA-1">SHA-1</a> has been broken. Not a reduced-r</p> <a href="http://www.hermann-uwe.de/blog/sha-1-broken">[Read More]</a>
</p>
<p class="posted">Tracked on February 15, 2005 10:55 PM</p>
<p id="p1030">
» <a href="http://blogs.mit.edu/semenko/posts/6291.aspx">Two Short Updates</a> from Semenko Attacks<br>
<a href="http://blogs.mit.edu/semenko/posts/6291.aspx">[Read More]</a>
</p>
<p class="posted">Tracked on February 15, 2005 10:58 PM</p>
<p id="p1031">
» <a href="http://pardini.net/blog/arkivos/2005/02/16/sha-1-quebrado/">SHA-1 Quebrado!</a> from pardine's<br>
Parece que é fato. Pelo menos é o que diz o Bruce Schneier. Deu também no Slashdot. E agora? <a href="http://pardini.net/blog/arkivos/2005/02/16/sha-1-quebrado/">[Read More]</a>
</p>
<p class="posted">Tracked on February 15, 2005 11:00 PM</p>
<p id="p1033">
» <a href="http://www.educatedguesswork.org/movabletype/archives/2005/02/the_news_gets_w.html">The news gets worse for SHA-1</a> from Educated Guesswork<br>
Bruce Schneier is reporting that the Wang, Yin, Yu team has reduced the difficulty of finding collisons in SHA-1 to 269 operations: collisions in the the full SHA-1 in 2**69 hash operations, much less than the brute-force attack of 2**80... <a href="http://www.educatedguesswork.org/movabletype/archives/2005/02/the_news_gets_w.html">[Read More]</a>
</p>
<p class="posted">Tracked on February 15, 2005 11:34 PM</p>
<p id="p1035">
» <a href="http://www.scottious.net/archives/2005/02/sha1_broken.html">SHA-1 Broken?</a> from :: Scottious.net ::<br>
According to Bruce Schneier, a team of analysts from Shandong University in China have broken SHA-1 (Secure Hash Algorithm) Well, nothing official yet, so don’t worry just yet. Just when you think all is safe, SHA-1 gets cracked. Great, one... <a href="http://www.scottious.net/archives/2005/02/sha1_broken.html">[Read More]</a>
</p>
<p class="posted">Tracked on February 16, 2005 12:02 AM</p>
<p id="p1036">
» <a href="http://www.trilithium.com/johan/2005/02/sha-1-broken/">Big weakness in SHA-1 found</a> from Scatter/Gather thoughts<br>
Bruce Schneier reports that SHA-1 is broken. Detailed results and techniques used are not yet published, but Schneier says that the paper looks good and that the Chinese research team behind it is reputable. <a href="http://www.trilithium.com/johan/2005/02/sha-1-broken/">[Read More]</a>
</p>
<p class="posted">Tracked on February 16, 2005 12:32 AM</p>
<p id="p1037">
» <a href="http://www.marius.org/2005/02/15/sha1_broken.html">SHA-1 Broken</a> from marius dot org<br>
Bruce Schneier posts that SHA-1 has been broken: SHA-1 has been broken. Not a reduced-round version. Not a simplified version. The real thing. The research team of Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu (mostly from Shandong University in China) h... <a href="http://www.marius.org/2005/02/15/sha1_broken.html">[Read More]</a>
</p>
<p class="posted">Tracked on February 16, 2005 12:56 AM</p>
<p id="p1040">
» <a href="http://blog.koehntopp.de/archives/697-Tschuess-MD5,-tschuess-SHA-1.html">Tschüß MD5, tschüß SHA-1</a> from Die wunderbare Welt von Isotopp<br>
Bruce Schneier hat einen Artikel online SHA-1 broken. SHA-1 has been broken. Not a reduced-round version. Not a simplified version. The real thing. Damit haben wir jetzt so eine Art Prüfsummenknappheit... Es wird Zeit für einen AES-Wettbewerb für Prüfsumm <a href="http://blog.koehntopp.de/archives/697-Tschuess-MD5,-tschuess-SHA-1.html">[Read More]</a>
</p>
<p class="posted">Tracked on February 16, 2005 01:08 AM</p>
<p id="p1041">
» <a href="http://balrog.de/security/archives/2005/02/16/82_bruce-schneier-sha-1-broken">Bruce Schneier: SHA-1 Broken?</a> from The Quiet Earth<br>
Slowly but surely the number of usable cryptographic hash algorithms is wandering asymptotically against zero. You're reading correctly. Zero. MD-4: broken. MD-5: all but broken.
Now Bruce Schneier blogs that SHA-1 is the next candidate for that. Appa... <a href="http://balrog.de/security/archives/2005/02/16/82_bruce-schneier-sha-1-broken">[Read More]</a>
</p>
<p class="posted">Tracked on February 16, 2005 01:32 AM</p>
<p id="p1042">
» <a href="http://geekswithblogs.net/ssimakov/archive/0001/01/01/23142.aspx">SHA-1 Broken</a> from Sergey Simakov blog<br>
<a href="http://geekswithblogs.net/ssimakov/archive/0001/01/01/23142.aspx">[Read More]</a>
</p>
<p class="posted">Tracked on February 16, 2005 01:32 AM</p>
<p id="p1043">
» <a href="http://sbserve/DotText/simon/archive/2005/02/17/4636.aspx">SHA-1 broken</a> from simon's ramblings<br>
<a href="http://sbserve/DotText/simon/archive/2005/02/17/4636.aspx">[Read More]</a>
</p>
<p class="posted">Tracked on February 16, 2005 05:44 AM</p>
<p id="p1044">
» <a href="http://log.does-not-exist.org/elsewhere/001988.html">http://log.does-not-exist.org/elsewhere/001988.html</a> from (void *)<br>
Bruce Schneier: SHA-1 Broken... <a href="http://log.does-not-exist.org/elsewhere/001988.html">[Read More]</a>
</p>
<p class="posted">Tracked on February 16, 2005 07:39 AM</p>
<p id="p1045">
» <a href="http://blogs.point2.com/blogs/sreilly/archive/2005/02/16/50.aspx">Good news and bad news</a> from Reilly's Ramblings<br>
The good news: Bruce Schneier (cryptography superstar) has a blog.
The bad news: today's post... <a href="http://blogs.point2.com/blogs/sreilly/archive/2005/02/16/50.aspx">[Read More]</a>
</p>
<p class="posted">Tracked on February 16, 2005 08:50 AM</p>
<p id="p1046">
» <a href="http://web.ics.purdue.edu/~kuliniew/wp/archives/2005/02/16/sha1-broken/">Another One Bites the Dust</a> from Paul Kuliniewicz<br>
Bruce Schneier reports that collisions have been found in SHA-1, through an attack that requires 269 operations (instead of the 280 needed to brute-force it). <a href="http://web.ics.purdue.edu/~kuliniew/wp/archives/2005/02/16/sha1-broken/">[Read More]</a>
</p>
<p class="posted">Tracked on February 16, 2005 08:55 AM</p>
<p id="p1047">
» <a href="http://www.sahw.com/wp/archivos/2005/02/16/el_algoritmo_sha1_ha_sido_roto/">El algoritmo SHA-1 ha sido roto</a> from Sergio Hernando<br>
Al menos eso se deprende al leer a Bruce Schneier, que comenta que un grupo de investigación chino ha roto el algoritmo de encriptación SHA1.
Habrá que estar al tanto de las noticias oficiales por parte del equipo investigador, que de momento no ha... <a href="http://www.sahw.com/wp/archivos/2005/02/16/el_algoritmo_sha1_ha_sido_roto/">[Read More]</a>
</p>
<p class="posted">Tracked on February 16, 2005 09:30 AM</p>
<p id="p1048">
» <a href="http://nuglops.com/blog/index.php?p=1021"> SHA-1 Broken</a> from NUGLOPS<br>
It's still not really practically breakable unless this is something bigger than what I'm guessing. SHA-0 was broken a few months ago, and MD5 a while before that. What does it mean for you? Not much.
Some attacker would have to be REALLY dedicate... <a href="http://nuglops.com/blog/index.php?p=1021">[Read More]</a>
</p>
<p class="posted">Tracked on February 16, 2005 09:32 AM</p>
<p id="p1049">
» <a href="http://www.e2ksecurity.com/archives/001297.html">SHA-1 broken</a> from Exchange Security<br>
<p>
collisions in the the full SHA-1 in 2**69 hash operations, much less than the brute-force attack of 2**80 operations based on the hash length. ...It pretty much puts a bullet into SHA-1 as a hash function for digital signatures (although it doesn'...</p> <a href="http://www.e2ksecurity.com/archives/001297.html">[Read More]</a>
</p>
<p class="posted">Tracked on February 16, 2005 09:34 AM</p>
<p id="p1050">
» <a href="http://pluralsight.com/blogs/keith/archive/2005/02/16/5907.aspx">SHA-1 Broken</a> from Security Briefs<br>
<a href="http://pluralsight.com/blogs/keith/archive/2005/02/16/5907.aspx">[Read More]</a>
</p>
<p class="posted">Tracked on February 16, 2005 09:35 AM</p>
<p id="p1051">
» <a href="http://lange.dhs.org/people/matt/blog/archives/000034.html">SHA-1 Broken</a> from Matthew Lange's Security Blog<br>
As reported on Schneier's blog, SHA-1 has been broken. The NIST is recommending the use of SHA-256 and SHA-512 and plans to phase out the use of SHA-1.... <a href="http://lange.dhs.org/people/matt/blog/archives/000034.html">[Read More]</a>
</p>
<p class="posted">Tracked on February 16, 2005 09:45 AM</p>
<p id="p1053">
» <a href="http://jeffsbasement.net/blog.php/archives/2005/02/16/wow-sha-1-broken">Wow, SHA-1 Broken</a> from Jeff's Web Journal<br>
I am by no means a security buff, but encryption is one of my hobbies and interests. In the early/mid 90s the US National Security Agency designed the Secure Hasing Algoritm family. These were meant to replace aging one-way encryption techniques with... <a href="http://jeffsbasement.net/blog.php/archives/2005/02/16/wow-sha-1-broken">[Read More]</a>
</p>
<p class="posted">Tracked on February 16, 2005 09:53 AM</p>
<p id="p1054">
» <a href="http://www.corante.com/mooreslore/archives/2005/02/16/encryption_must_become_flexible.php">Encryption Must Become Flexible</a> from Moore's Lore<br>
Word that the SHA-1 encryption scheme has been broken in China, which follows news from John Hopkins on how RFID car keys can be hacked, brings me to a sad conclusion. Permanent hardware encryption isn't going to happen. (The image,... <a href="http://www.corante.com/mooreslore/archives/2005/02/16/encryption_must_become_flexible.php">[Read More]</a>
</p>
<p class="posted">Tracked on February 16, 2005 10:05 AM</p>
<p id="p1055">
» <a href="http://www.dynamic-cast.com/mt-archives/000074.html">SHA-1 Broken?</a> from herveyw's blog<br>
Bruce Schneier is reporting that SHA-1 has been broken. Interesting.... <a href="http://www.dynamic-cast.com/mt-archives/000074.html">[Read More]</a>
</p>
<p class="posted">Tracked on February 16, 2005 10:07 AM</p>
<p id="p1056">
» <a href="http://www.financialcryptography.com/mt/archives/000355.html">Shandong team attacks SHA-1</a> from Financial Cryptography<br>
The draft paper on the Chinese team's exploits of message digests has now alleged that SHA-1 falls to the same cryptanalytic attack as that which broke the others. Over on Bruce Schneier's blog he reports presumably from the RSA conference.... <a href="http://www.financialcryptography.com/mt/archives/000355.html">[Read More]</a>
</p>
<p class="posted">Tracked on February 16, 2005 10:15 AM</p>
<p id="p1057">
» <a href="http://blogs.aspitalia.com/cp/post910.aspx">SHA1 Compromesso</a> from ITHost<br>
<a href="http://blogs.aspitalia.com/cp/post910.aspx">[Read More]</a>
</p>
<p class="posted">Tracked on February 16, 2005 10:33 AM</p>
<p id="p1058">
» <a href="http://farm.tucows.com/blog/_archives/2005/2/16/327236.html">[Miscellaneous] Hit and Run</a> from The Farm: The Tucows Developers' Hangout<br>
I'm rather busy today, so here's a hit-and-run collection of links for you!<ul>
<li>Computer security guru <a href="http://www.schneier.com/">Bruce Schneier</a> reports in his weblog
that "</ul></li> <a href="http://farm.tucows.com/blog/_archives/2005/2/16/327236.html">[Read More]</a>
</p>
<p class="posted">Tracked on February 16, 2005 10:38 AM</p>
<p id="p1059">
» <a href="http://r00tshell.com/node/38">SHA-1 Broken</a> from r00tshell.com<br>
<p>SHA-1 has been broken. Not a reduced-round version. Not a simplified version. The real thing.</p>
<p>The research team of Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu (mostly from Shandong University in China) have been quietly circulating a paper descr</p> <a href="http://r00tshell.com/node/38">[Read More]</a>
</p>
<p class="posted">Tracked on February 16, 2005 10:39 AM</p>
<p id="p1060">
» <a href="http://www.aaronweiker.com/PermaLink,guid,ac47a6fa-70a8-4267-b4fb-9f925359b43c.aspx">SHA1 Broken</a> from Aaron Weiker Weblog<br>
<a href="http://www.aaronweiker.com/PermaLink,guid,ac47a6fa-70a8-4267-b4fb-9f925359b43c.aspx">[Read More]</a>
</p>
<p class="posted">Tracked on February 16, 2005 10:56 AM</p>
<p id="p1061">
» <a href="http://www.robertpeake.com/archives/37-Hashing-Hashed.html">Hashing Hashed</a> from Robert Peake<br>
Bruce Scheiner repoprts that a reputable team in China appears to have found significant collision problems with the SHA-1 algorithm. Of course, this is just as I revised my old article on PHP Cryptography to include a footnote on the MD5 section that SHA <a href="http://www.robertpeake.com/archives/37-Hashing-Hashed.html">[Read More]</a>
</p>
<p class="posted">Tracked on February 16, 2005 11:08 AM</p>
<p id="p1062">
» <a href="http://www.neilturner.me.uk/smaller/2005/02/sha1_broken.html">SHA-1 Broken</a> from Neil's Smaller World<br>
The SHA-1 hashing algorithm has been broken. This, coupled with the defeat of MD5, could have major implications. <a href="http://www.neilturner.me.uk/smaller/2005/02/sha1_broken.html">[Read More]</a>
</p>
<p class="posted">Tracked on February 16, 2005 11:10 AM</p>
<p id="p1063">
» <a href="http://blog.hexagon.at/2005/02/16/sha-1-broken/">SHA-1 Broken</a> from Hexagon Business Weblog<br>
Nach MD5 ist nun auch der zweite wichtige Security-Hash auf "Kollisionskurs".... <a href="http://blog.hexagon.at/2005/02/16/sha-1-broken/">[Read More]</a>
</p>
<p class="posted">Tracked on February 16, 2005 12:55 PM</p>
<p id="p1066">
» <a href="http://blog.joehuffman.org/archive/2005/02/16/1402.aspx">SHA-1 broken</a> from The View From North Central Idaho<br>
<a href="http://blog.joehuffman.org/archive/2005/02/16/1402.aspx">[Read More]</a>
</p>
<p class="posted">Tracked on February 16, 2005 01:08 PM</p>
<p id="p1070">
» <a href="http://www.mostlylucid.co.uk/archive/2005/02/16/1676.aspx">SHA-1 has been broken...what's the big deal?</a> from Scott Galloway's Personal Blog<br>
<a href="http://www.mostlylucid.co.uk/archive/2005/02/16/1676.aspx">[Read More]</a>
</p>
<p class="posted">Tracked on February 16, 2005 01:21 PM</p>
<p id="p1071">
» <a href="http://www.unixwiz.net/archives/2005/02/crypto_hashes_i.html">Crypto hashes in the news again</a> from Steve Friedl's Weblog<br>
Last summer, I wrote about the weakenesses found in the MD5 hash while I introduced my tech tip on hashes in general. Now Bruce Schneier reports that SHA is under attack, and it seems like a great time to repost... <a href="http://www.unixwiz.net/archives/2005/02/crypto_hashes_i.html">[Read More]</a>
</p>
<p class="posted">Tracked on February 16, 2005 01:26 PM</p>
<p id="p1073">
» <a href="http://notblog.com/bloggenspiel/archives/002696.html">SHA-1 is teh broke</a> from bloggenspiel<br>
Senior year, Nate (and possibly myself... I remember being involved somehow, but I'm not sure how) did some proof-of-concept work regarding hashing algorithms and large data sets (namely Nate's mp3 collection). He/We found that SHA-1 hiccupped several ... <a href="http://notblog.com/bloggenspiel/archives/002696.html">[Read More]</a>
</p>
<p class="posted">Tracked on February 16, 2005 02:47 PM</p>
<p id="p1074">
» <a href="http://rhyndman.typepad.com/robhyndman/2005/02/sha1_has_been_b.html">SHA-1 Has Been Broken</a> from robhyndman.com<br>
Bruce Schneier is reporting that SHA-1 has been broken. <a href="http://rhyndman.typepad.com/robhyndman/2005/02/sha1_has_been_b.html">[Read More]</a>
</p>
<p class="posted">Tracked on February 16, 2005 03:15 PM</p>
<p id="p1075">
» <a href="http://maurus.net/archives/2005/02/17/sha-1-has-been-broken/">SHA-1 has been broken</a> from maurus.net<br>
SHA-1 has been broken. It's already all over the net, but Bruce Schneier says it best. <a href="http://maurus.net/archives/2005/02/17/sha-1-has-been-broken/">[Read More]</a>
</p>
<p class="posted">Tracked on February 16, 2005 07:01 PM</p>
<p id="p1077">
» <a href="http://www.softwaremaker.net/blog/PermaLink,guid,4153f866-626a-4d07-99b0-a04e80511d97.aspx">Needing Quantum Cryptography soon</a> from Softwaremaker<br>
<a href="http://www.softwaremaker.net/blog/PermaLink,guid,4153f866-626a-4d07-99b0-a04e80511d97.aspx">[Read More]</a>
</p>
<p class="posted">Tracked on February 16, 2005 09:06 PM</p>
<p id="p1079">
» <a href="http://e2e.prestonhunt.com/maelstrom/storydetail.php?id=94">http://e2e.prestonhunt.com/maelstrom/storydetail.php?id=94</a> from Preston Hunt's Blog<br>
<a>SHA-1</a> has been broken. Amazing. <a href="http://e2e.prestonhunt.com/maelstrom/storydetail.php?id=94">[Read More]</a>
</p>
<p class="posted">Tracked on February 17, 2005 12:38 AM</p>
<p id="p1080">
» <a href="http://blog.rockme.org/archives/3-SHA-1-Broken.html">SHA-1 Broken</a> from [=]rockme.org[=] Patrick's Blog<br>
So pretty much everybody has been writing about Bruce Schneier's recent post about a team of Chinese researchers "breaking" SHA-1. I'm not going to go into the gory details, but rather relate a slightly amusing story.
So, one of the classes I'm taking <a href="http://blog.rockme.org/archives/3-SHA-1-Broken.html">[Read More]</a>
</p>
<p class="posted">Tracked on February 17, 2005 01:37 AM</p>
<p id="p1081">
» <a href="http://www.e-bi.org/index.php?blog=5">SHA-1 Broken</a> from Business Intelligence Blog<br>
According to Bruce Schneier's weblog:
SHA-1 has been broken. Not a reduced-round version. Not a simplified version. The real thing.
Stephen Friedl has an informed overview of cryptographic hashes (which predates Bruce Schneier's post): An Illustr... <a href="http://www.e-bi.org/index.php?blog=5">[Read More]</a>
</p>
<p class="posted">Tracked on February 17, 2005 03:50 AM</p>
<p id="p1082">
» <a href="http://xqus.com/archives/2005/02/17/sha-1-broken/">SHA-1 Broken</a> from xqus.com<br>
Bruce Schneier writes in his blog:
SHA-1 has been broken. Not a reduced-round version. Not a simplified version. The real thing.
...
This attack builds on previous attacks on SHA-0 and SHA-1, and is a major, major cryptanalytic result. It pr... <a href="http://xqus.com/archives/2005/02/17/sha-1-broken/">[Read More]</a>
</p>
<p class="posted">Tracked on February 17, 2005 05:28 AM</p>
<p id="p1083">
» <a href="http://blog.sprinx.cz/techblog/archive/2005/02/17/412.aspx">Bylo prolomeno SHA-1</a> from TechBlog<br>
<a href="http://blog.sprinx.cz/techblog/archive/2005/02/17/412.aspx">[Read More]</a>
</p>
<p class="posted">Tracked on February 17, 2005 07:29 AM</p>
<p id="p1084">
» <a href="http://www.simiandesign.com/blog-fu/2005/02/index.php#002708">SHA-1 Broken.</a> from Link-Fu<br>
SHA-1 Broken by the Chinese team of Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu. This is pretty major in terms of cryptoanalysis.... <a href="http://www.simiandesign.com/blog-fu/2005/02/index.php#002708">[Read More]</a>
</p>
<p class="posted">Tracked on February 17, 2005 07:37 AM</p>
<p id="p1085">
» <a href="http://lab.mediaworksit.net/blog/index.php?p=6">SHA-1 probijen</a> from Lab<br>
SHA-1 hash razbijen. <a href="http://lab.mediaworksit.net/blog/index.php?p=6">[Read More]</a>
</p>
<p class="posted">Tracked on February 17, 2005 08:03 AM</p>
<p id="p1086">
» <a href="http://www.secosoft.net/archives/2005/02/16/sha-1-broken/">SHA-1 Broken</a> from Matt's Weblog<br>
Bruce Schneier has a little writeup on this on his blog. This is so huge I can hardly believe it. This will have wide ranging implications for the entire cryptographic community. Every cryptographic application that I have ever written has used ... <a href="http://www.secosoft.net/archives/2005/02/16/sha-1-broken/">[Read More]</a>
</p>
<p class="posted">Tracked on February 17, 2005 09:47 AM</p>
<p id="p1087">
» <a href="http://www.gnxp.com/MT2/archives/003610.html">China In The News</a> from Gene Expression<br>
Here are five links that I thought noteworthy today. The first is news that Chinese researchers have broken the SHA-1 hashing algorithm which was developed by the National Security Agency and which allows crytographic security for such mundane things a... <a href="http://www.gnxp.com/MT2/archives/003610.html">[Read More]</a>
</p>
<p class="posted">Tracked on February 17, 2005 02:41 PM</p>
<p id="p1090">
» <a href="http://blogs.aspadvice.com/xsherry/archive/2005/02/17/2695.aspx">SHA-1 has been broken.</a> from XanderLand<br>
<a href="http://blogs.aspadvice.com/xsherry/archive/2005/02/17/2695.aspx">[Read More]</a>
</p>
<p class="posted">Tracked on February 17, 2005 03:40 PM</p>
<p id="p1091">
» <a href="http://blogs.aspadvice.com/xsherry/archive/0001/01/01/2695.aspx">SHA-1 has been broken.</a> from XanderLand<br>
<a href="http://blogs.aspadvice.com/xsherry/archive/0001/01/01/2695.aspx">[Read More]</a>
</p>
<p class="posted">Tracked on February 17, 2005 03:42 PM</p>
<p id="p1092">
» <a href="http://differentriver.com/archives/2005/02/17/sha-1-broken/">SHA-1 Broken</a> from Different River<br>
Bruce Schneier reports that SHA-1, an algorithm used for computing (and authenticating) digital signatures, has been cracked. This is (potentially, if it pans out) a major setback for digital signatures. Click for details. <a href="http://differentriver.com/archives/2005/02/17/sha-1-broken/">[Read More]</a>
</p>
<p class="posted">Tracked on February 17, 2005 05:19 PM</p>
<p id="p1093">
» <a href="http://www.hutuworm.org/archives/2005/02/sha1_broken.html">SHA-1 Broken</a> from hutuworm<br>
From Bruce Schneier's blog: SHA-1 has been broken. Not a reduced-round version. Not a simplified version. The real thing. The research team of Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu (mostly from Shandong University in China) have been quietly... <a href="http://www.hutuworm.org/archives/2005/02/sha1_broken.html">[Read More]</a>
</p>
<p class="posted">Tracked on February 17, 2005 07:46 PM</p>
<p id="p1094">
» <a href="http://www.identityblog.com/2005/02/17.html#a146">The Curse of the Secret Question</a> from Kim Cameron's Identity Weblog<br>
I was at Bruce Schneier's site reading about the problems with SHA-1 and came across <a href="http://www.identityblog.com/2005/02/17.html#a146">[Read More]</a>
</p>
<p class="posted">Tracked on February 17, 2005 07:57 PM</p>
<p id="p1096">
» <a href="http://www.sharpchannel.com/index.php?p=28">Sha-1 Broken by Chinese Research Team</a> from SharpChannel<br>
As a Chinese, I'm proud of the excellent research conducted by research team in Shandong University. I remember that they broke MD-5 algorithm not long time ago...
The major breakthrough:
collisions in the the full SHA-1 in 2**69 hash operations, ... <a href="http://www.sharpchannel.com/index.php?p=28">[Read More]</a>
</p>
<p class="posted">Tracked on February 17, 2005 08:07 PM</p>
<p id="p1097">
» <a href="http://256bit.org/~chrisbra/blog/archives/2-Mangel-an-vertrauenswuerdigen-Hash-Algorithmen.html">Mangel an vertrauenswürdigen Hash-Algorithmen</a> from 256bit.org Blog<br>
Es scheint, dass uns so langsam die vertrauenswürdige Hash-Algorithmen ausgehen.
Bruce Schneier schreibt dazu:
QUOTE: SHA-1 has been broken. Not a reduced-round version. Not a simplified version. The real thing.
Nachdem im August letzten Jahres <a href="http://256bit.org/~chrisbra/blog/archives/2-Mangel-an-vertrauenswuerdigen-Hash-Algorithmen.html">[Read More]</a>
</p>
<p class="posted">Tracked on February 18, 2005 03:11 AM</p>
<p id="p1100">
» <a href="http://www.merill.net/PermaLink,guid,d14d5df5-a74c-4fba-bc6b-9ca19bc9bf4a.aspx">SHA-1 Broken</a> from Merill Fernando's Web Log<br>
<a href="http://www.merill.net/PermaLink,guid,d14d5df5-a74c-4fba-bc6b-9ca19bc9bf4a.aspx">[Read More]</a>
</p>
<p class="posted">Tracked on February 18, 2005 09:37 AM</p>
<p id="p1104">
» <a href="http://www.frankw.net/archive/sha1_hashing_algorithm_broken">SHA-1 hashing algorithm broken</a> from Funtime Franky<br>
Well, what can I say? Especially interesting is the news today that the real-deal version of the SHA-1 algorithm, a 1-way cryptographic hashing algorithm, has been broken by Xiaoyun Wang and Hongbo Yu from Shandong University and Yiqun Lisa Yin... <a href="http://www.frankw.net/archive/sha1_hashing_algorithm_broken">[Read More]</a>
</p>
<p class="posted">Tracked on February 18, 2005 07:22 PM</p>
<p id="p1105">
» <a href="http://sbserve/DotText/simon/archive/0001/01/01/4636.aspx">SHA-1 broken</a> from simon's ramblings<br>
<a href="http://sbserve/DotText/simon/archive/0001/01/01/4636.aspx">[Read More]</a>
</p>
<p class="posted">Tracked on February 18, 2005 08:54 PM</p>
<p id="p1110">
» <a href="http://www.scottious.net/archives/2005/02/sha1_broken_1.html">SHA-1 Broken</a> from :: Scottious.net ::<br>
According to Bruce Schneier, a team of analysts from Shandong University in China have broken SHA-1 (Secure Hash Algorithm) Well, nothing official yet, so don’t worry just yet. Just when you think all is safe, SHA-1 gets cracked. Great, one... <a href="http://www.scottious.net/archives/2005/02/sha1_broken_1.html">[Read More]</a>
</p>
<p class="posted">Tracked on February 19, 2005 09:11 AM</p>
<p id="p1115">
» <a href="http://blog.mctaylor.com/archives/000068.html">SHA-1 - needs replacing</a> from factless<br>
So after everyone was suprised and concerned over the theorical and practical attacks on MD5 last year, you think there... <a href="http://blog.mctaylor.com/archives/000068.html">[Read More]</a>
</p>
<p class="posted">Tracked on February 19, 2005 11:17 AM</p>
<p id="p1118">
» <a href="http://blogs.bartdesmet.net/bart/archive/2005/02/19/629.aspx">SHA1 also unsecure?</a> from B# .NET Blog<br>
<a href="http://blogs.bartdesmet.net/bart/archive/2005/02/19/629.aspx">[Read More]</a>
</p>
<p class="posted">Tracked on February 19, 2005 11:43 AM</p>
<p id="p1122">
» <a href="http://isag.meng.auth.gr/blogentis/Oneiros/2005/02/20/sha1broken">SHA1 broken</a> from Αστέρης Μασούρας<br>
As Bruce Schneier reported
earlier this week, the SHA-1 hashing algorithm has been broken
by a team of Chinese researchers. <a href="http://isag.meng.auth.gr/blogentis/Oneiros/2005/02/20/sha1broken">[Read More]</a>
</p>
<p class="posted">Tracked on February 19, 2005 04:42 PM</p>
<p id="p1127">
» <a href="http://www.suramya.com/blog/archives/74-SHA-1-Broken-by-Crytography-Team.html">SHA-1 Broken by Crytography Team</a> from Suramya's blog<br>
I was catching up on all my unread email when I saw an email telling Bugtraq on how the SHA-1 encryption algorithim has been broken by a research team of Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu (mostly from Shandong University in China). These guys ha <a href="http://www.suramya.com/blog/archives/74-SHA-1-Broken-by-Crytography-Team.html">[Read More]</a>
</p>
<p class="posted">Tracked on February 19, 2005 09:42 PM</p>
<p id="p1130">
» <a href="http://blogs.bartdesmet.net/bart/archive/0001/01/01/629.aspx">SHA1 also insecure?</a> from B# .NET Blog<br>
<a href="http://blogs.bartdesmet.net/bart/archive/0001/01/01/629.aspx">[Read More]</a>
</p>
<p class="posted">Tracked on February 20, 2005 05:51 AM</p>
<p id="p1136">
» <a href="http://blog.justbe.com/jb/2005/02/sha1_encryption.html">SHA-1 Encryption broken</a> from jB: no - that's definitely not good enough<br>
I am slowly starting to catch up on the news and mails that came in the last week, but the first couple will be the major ones I've come across so far... Starting with the news being all around the web that Bruce Schneier has found a way to break <a href="http://blog.justbe.com/jb/2005/02/sha1_encryption.html">[Read More]</a>
</p>
<p class="posted">Tracked on February 20, 2005 09:35 AM</p>
<p id="p1140">
» <a href="http://www.codeattest.com/blogs/martin/2005/02/sha-1-broken.html">SHA-1 broken</a> from Martin Kulov's Blog<br>
As you might already know SHA-1 is broken. Well it is not that I will not sleep calm anymore, but it is a reminder that every secure system has one limitation - time. <a href="http://www.codeattest.com/blogs/martin/2005/02/sha-1-broken.html">[Read More]</a>
</p>
<p class="posted">Tracked on February 20, 2005 07:00 PM</p>
<p id="p1143">
» <a href="http://weblogs.asp.net/erobillard/archive/2005/02/21/377189.aspx">SHA-1 Broken</a> from Eli Robillard's World of Blog.<br>
<a href="http://weblogs.asp.net/erobillard/archive/2005/02/21/377189.aspx">[Read More]</a>
</p>
<p class="posted">Tracked on February 21, 2005 01:08 AM</p>
<p id="p1145">
» <a href="http://ferguson-consulting.biz/archive/2005/02/21/156.aspx">SHA-1 Broken</a> from Ferguson Consulting<br>
<a href="http://ferguson-consulting.biz/archive/2005/02/21/156.aspx">[Read More]</a>
</p>
<p class="posted">Tracked on February 21, 2005 02:12 AM</p>
<p id="p1162">
» <a href="http://www.iay.org.uk/blog/2005/02/no_plan_b.html">SHA-1 and XMLDSIG: No Plan B?</a> from Technology Stir Fry<br>
People in the know are reporting that the 160-bit Secure Hash Algorithm has been broken by a group in China. When the group's paper is published we'll all be able to judge, but the initial reports indicate that SHA-1 has... <a href="http://www.iay.org.uk/blog/2005/02/no_plan_b.html">[Read More]</a>
</p>
<p class="posted">Tracked on February 21, 2005 04:44 AM</p>
<p id="p1188">
» <a href="http://blogs.msdn.com/spatdsg/archive/2005/02/21/377786.aspx">SHA-1 Broken? Tell me it aint so...</a> from Spat's WebLog<br>
<a href="http://blogs.msdn.com/spatdsg/archive/2005/02/21/377786.aspx">[Read More]</a>
</p>
<p class="posted">Tracked on February 21, 2005 09:43 PM</p>
<p id="p1189">
» <a href="http://www.ekampf.com/blog/PermaLink.aspx?guid=2cde1be2-d3b7-43f7-90ef-a7b1ff6e1e36">SHA-1 broken</a> from Eran Kampf's Blog<br>
<a href="http://www.ekampf.com/blog/PermaLink.aspx?guid=2cde1be2-d3b7-43f7-90ef-a7b1ff6e1e36">[Read More]</a>
</p>
<p class="posted">Tracked on February 22, 2005 04:47 AM</p>
<p id="p1192">
» <a href="http://chy168.twbbs.org/serendipity/index.php?/archives/5-caeacSHA-1.html">王小雲再破SHA-1</a> from Hungyen's blog<br>
SHA-1 has been broken. Not a reduced-round version. Not a simplified version. The real thing.
The research team of Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu (mostly from Shandong University in China) have been quietly circulating a paper describing t <a href="http://chy168.twbbs.org/serendipity/index.php?/archives/5-caeacSHA-1.html">[Read More]</a>
</p>
<p class="posted">Tracked on February 22, 2005 09:11 AM</p>
<p id="p1196">
» <a href="http://spaces.msn.com/members/geekspace61/blog/cns!1pnFMasma1xq-OZUDDSW7Mtw!266.entry">Interesting Security News</a> from <br>
Interesting Security News <a href="http://spaces.msn.com/members/geekspace61/blog/cns!1pnFMasma1xq-OZUDDSW7Mtw!266.entry">[Read More]</a>
</p>
<p class="posted">Tracked on February 22, 2005 01:31 PM</p>
<p id="p1197">
» <a href="http://spaces.msn.com/members/geekspace61/blog/cns!1pnFMasma1xq-OZUDDSW7Mtw!266.entry">Interesting Security News</a> from <br>
Interesting Security News <a href="http://spaces.msn.com/members/geekspace61/blog/cns!1pnFMasma1xq-OZUDDSW7Mtw!266.entry">[Read More]</a>
</p>
<p class="posted">Tracked on February 22, 2005 01:35 PM</p>
<p id="p1219">
» <a href="http://weblogs.asp.net/rhurlbut/archive/2005/02/23/379030.aspx">SHA1 concerns and implementing SHA256 and beyond</a> from Robert Hurlbut's .NET Blog<br>
<a href="http://weblogs.asp.net/rhurlbut/archive/2005/02/23/379030.aspx">[Read More]</a>
</p>
<p class="posted">Tracked on February 23, 2005 12:18 PM</p>
<p id="p1220">
» <a href="http://weblogs.asp.net/rhurlbut/archive/0001/01/01/379030.aspx">SHA1 concerns and implementing SHA256 and beyond</a> from Robert Hurlbut's .NET Blog<br>
<a href="http://weblogs.asp.net/rhurlbut/archive/0001/01/01/379030.aspx">[Read More]</a>
</p>
<p class="posted">Tracked on February 23, 2005 12:19 PM</p>
<p id="p1226">
» <a href="http://www.longwin.com.tw/~jon/blog/archives/000507.html">Schneier on Security</a> from Tsung's Blog<br>
SHA-1 Broken Cryptanalysis of SHA-1 連 SHA-1 都不安全了? ... :( Slashot 的一些相關新聞 SHA-1 Broken More on Newly Broken SHA-1... <a href="http://www.longwin.com.tw/~jon/blog/archives/000507.html">[Read More]</a>
</p>
<p class="posted">Tracked on February 23, 2005 07:12 PM</p>
</div>
<div class="commentform">
<h2 id="comments">Comments</h2>
</div>
<div class="commentbody">
<div id="c1542">
<p>Time for NIST to have another competition?</p>
</div>
<p class="posted">Posted by: David Magda at February 15, 2005 07:36 PM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1543">
<p>So what hash functions are available that don't have a substantially similar construction? AFAIK, RIPEMD160 and the SHA256-384-512 series are of the same sort, and the attack could in principle work for them as well. There's Tiger, which appears quite different, and Whirlpool. Any other suggestions?</p>
<p>This is, it would appear, a collision attack, not a preimage attack, so I guess we have some time to phase out the old hash functions.</p>
</div>
<p class="posted">Posted by: <a target="_blank" title="http://stormwyrm.blogspot.com" href="http://www.schneier.com/cgi-bin/mt/mt-comments.cgi?__mode=red;id=1543">Rafael Sevilla</a> at February 15, 2005 08:25 PM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1546">
<p>Feb. 7, 2005 Hashing out encryption: </p>
<p><br />
http://www.fcw.com/fcw/articles/2005/0207/web-hash-02-07-05.asp</p>
<p>Federal agencies have been put on notice that National Institute of Standards and Technology officials plan to phase out a widely used cryptographic hash function known as SHA-1 in favor of larger and stronger hash functions such as SHA-256 and SHA-512.</p>
</div>
<p class="posted">Posted by: <a target="_blank" title="http://itheresies.blogspot.com/" href="http://www.schneier.com/cgi-bin/mt/mt-comments.cgi?__mode=red;id=1546">David Mohring</a> at February 15, 2005 08:56 PM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1547">
<p>2**69 operations is still an awful lot of operations. What is it that lets us say that 2**69 is "broken" but 2**80 is "not broken"?</p>
</div>
<p class="posted">Posted by: <a href="mailto:jordan.lampe@gmail.com">Jordan</a> at February 15, 2005 09:03 PM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1549">
<p>> (although it doesn't affect applications such as HMAC)</p>
<p>Bruce,</p>
<p>Pardon my ignorance but can you elaborate why this doesn't affect HMAC?</p>
</div>
<p class="posted">Posted by: <a target="_blank" title="http://www.shaftek.org/blog/" href="http://www.schneier.com/cgi-bin/mt/mt-comments.cgi?__mode=red;id=1549">Yakov Shafranovich</a> at February 15, 2005 09:16 PM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1550">
<p>That's 2**11 less operations. Let's say breaking this (2**69 ops) takes the NSA a week. If it had been 2**80, it would have taken 2048 weeks, or 39 years. If it would have taken the NSA (or whomever) a year to break SHA-1 before, it could be broken in 4 hours.</p>
<p>My guess would be it would still take a lot longer than a week - but would now be in the realm of possibility, whereas before it would have been in the lifetime(s) range. However, this is totally a wild-assed-guess, based on the assumption that it was expected to take 100+ years before this to crack.</p>
</div>
<p class="posted">Posted by: <a href="mailto:rjesup_spam@wgate.com">Randell Jesup</a> at February 15, 2005 09:19 PM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1551">
<p>"...whereas before it would have been in the lifetime(s) range."</p>
<p>Either way, it's well within the statute of limitations for whatever crime you've committed. ;-)</p>
</div>
<p class="posted">Posted by: <a target="_blank" title="http://www.martin-studio.com/" href="http://www.schneier.com/cgi-bin/mt/mt-comments.cgi?__mode=red;id=1551">Anthony Martin</a> at February 15, 2005 09:25 PM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1552">
<p>He said 69!!!!!!!!</p>
<p>COOOOOOOOLLLLLL!!!!!!!!!!!!!!</p>
</div>
<p class="posted">Posted by: <a href="mailto:blowme@fu.com">Mr Anon</a> at February 15, 2005 09:32 PM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1553">
<p>I don't think any public calculation has successfully solved a problem which required as much as 2^69 work. It will be interesting to see if this motivates people to search for an actual SHA-1 collision. Exhibiting a collision always has more impact than a theoretical break.</p>
<p>Of course, these researchers have yet to publish their techniques. Isn't it kind of contradictory to the spirit of academic research to keep your methodology secret for so long? It's been six months now since their MD5 results.</p>
</div>
<p class="posted">Posted by: <a href="mailto:halmail2@finney.org">Hal</a> at February 15, 2005 09:46 PM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1554">
<p>Regarding how long it should take to break... Let's assume that a single CPU can tackle 2**32 ops/sec. (About 4 billion, so assuming each op is one cycle, about 4 GHz... Gross oversimplification, but it makes the math pretty easy.) So, how long would it take to do 2**69 ops?</p>
<p>2**37 seconds of CPU time. About 4000 years.</p>
<p>So, if you have a 4000 node cluster, it ought to take about a year, which would be well within the statute of limitations, for most crimes and jurisdictions... :)</p>
<p>Brute forcing, using the same hypothetical cluster, would have taken over 2000 years. So, I guess today's lesson is that it isn't completely broken, but it certainly ain't secure.</p>
</div>
<p class="posted">Posted by: Will at February 15, 2005 09:53 PM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1555">
<p>2^69 is still a lot of work, with current processors and electricity prices. But with Moore's progression and the lessons of history, people who were planning on 2^80 complexity for a bit of futureproofing will be very unhappy with 2^69.</p>
<p>I'm not clear on why anyone would've been using 80 bits in the first place. A 20% reduction in 80 bits is a big deal, but a 20% reduction in 256 bits is still way outside what we'd consider practical in the forseeable future. Bits are cheap, use lots!</p>
</div>
<p class="posted">Posted by: <a href="mailto:leadacid@hotmail.com">Myself</a> at February 15, 2005 10:13 PM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1556">
<p>With the maxim about attacks getting better I'd be worried that with the rate that the SHA family attacks have improved in the last few months we could see even more serious breaks within a year or two. Not long ago we had reason for deep concern, now we've got reason for outright worry.</p>
</div>
<p class="posted">Posted by: Jonathan Conway at February 15, 2005 10:18 PM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1557">
<p>Jordan is correct - 2^69 is still a large data space to search.<br />
However, as Randell points out, this is a lot better than 2^80.<br />
Assume you had 100,000 CPUs each capable of 4,000,000,000 tests per second.<br />
That works out to 1,475,739 seconds to find a collision or about 17 days.<br />
It is unlikely that such equipment exists, but it gives an idea of a possible worst case.<br />
However, many digital signatures need to be secure much longer than 3 weeks.<br />
Think of a contract for a 30-year mortgage.<br />
The previous brute force mechanism (2^80) might have been secure for up to 95 years and reasonable.<br />
</p>
</div>
<p class="posted">Posted by: <a href="mailto:fake@fakefake.com">Fuzzy</a> at February 15, 2005 10:20 PM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1558">
<p>How effective is this attack? For example can it change "attack at dawn" to "attack at dusk" in a file that<br />
has been compressed and then had a sha-1 md made?<br />
Because at the end of the day isn't that the point of MDs?</p>
<p>-A curious cryptographer...</p>
</div>
<p class="posted">Posted by: <a target="_blank" title="http://www.partow.net" href="http://www.schneier.com/cgi-bin/mt/mt-comments.cgi?__mode=red;id=1558">Arash Partow</a> at February 15, 2005 10:23 PM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1559">
<p>It is not 2^11 fewer operations. It is 2^11 _times_ fewer operations, roughy 1/2050th the work. </p>
<p>The point isn't so much that it takes less time but that it has an large and now known weakness. It is very likely other weaknesses will come to light making it useless for secure hashing.<br />
</p>
</div>
<p class="posted">Posted by: cjr at February 15, 2005 10:23 PM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1561">
<p>@Bruce<br />
I don't know if you saw the Cryptographer's Panel today, but Avi Shamir mentioned the Chinese team's report and the need for better hashing.</p>
</div>
<p class="posted">Posted by: <a target="_blank" title="http://davi.poetry.org/" href="http://www.schneier.com/cgi-bin/mt/mt-comments.cgi?__mode=red;id=1561">Davi Ottenheimer</a> at February 15, 2005 10:34 PM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1562">
<p>oh my. its amazing how human brainpower [and some patience and creativity] can ultimately defeat ANYTHING presented to it. </p>
<p>Good for the chinese team! [congratulations!] </p>
<p>time to build something better than SHA1</p>
</div>
<p class="posted">Posted by: <a target="_blank" title="http://www.coldstream.ca" href="http://www.schneier.com/cgi-bin/mt/mt-comments.cgi?__mode=red;id=1562">Sean</a> at February 15, 2005 10:49 PM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1565">
<p>I think it is important to note that (from what I've heard, I haven't seen the paper either...) this collision attack is not very "real world" useful. Their attack is focused on taking a certain number of operations to come up with two hunks of data that result in the same hash. </p>
<p>In my opinion, a "real world" attack would be one which given a blob which has already been hashed, would come up with another blob which results in the same hash. To my knowledge, nobody has any useful attacks in that direction yet, although some would argue based upon this research that it may just be a matter of time. </p>
<p>Then we of course need to get into whether that is really useful either. If I find out that "I agree to purchase 100 units for $500" and "*(\D$Hw&72d98a %93di(hd eLKH%ap$#" results in the same hash, how helpful is that to me? How is a lawyer is going to prove to a jury that I may have actually signed the garbage instead of the purchase agreement? So, there is even more work to be done to make it a useful real world attack, wherein you might take the original signed text (modified for your evil purposes), append a null character, and then add garbage until the hashes are equal--and hope the UI was poorly written and just displays up to the first null.</p>
</div>
<p class="posted">Posted by: <a target="_blank" title="http://geminisecurity.com" href="http://www.schneier.com/cgi-bin/mt/mt-comments.cgi?__mode=red;id=1565">Peter</a> at February 15, 2005 11:38 PM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1567">
<p>If this solution lends itself to distributed computation, and one in a million people online were to participate in such a project, the first publicly generated SHA-1 collision should be produced by the end of 2010.</p>
<p>That is assuming the use of cheap modern desktops, Moore's law, and linear growth of online population in line with the predictions of Computer Industry Almanac (140 million new users/year, and thus net growth of 140 new participants/year -- probably under-estimating growth of participation here).</p>
<p>If participation were higher, say one in a thousand, we'd be cracking them at a rate of one every other month.</p>
</div>
<p class="posted">Posted by: <a target="_blank" title="http://www.wandreilagh.org" href="http://www.schneier.com/cgi-bin/mt/mt-comments.cgi?__mode=red;id=1567">Gavin Weld White</a> at February 16, 2005 12:11 AM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1568">
<p>Peter, let me guess.. you're from slashdot?</p>
</div>
<p class="posted">Posted by: John at February 16, 2005 12:12 AM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1569">
<p>Would a combination of multiple hash algorithms make it more difficult to obtain collissions?</p>
<p>say MD5 + SHA?<br />
</p>
</div>
<p class="posted">Posted by: <a target="_blank" title="http://teyc.editthispage.com/" href="http://www.schneier.com/cgi-bin/mt/mt-comments.cgi?__mode=red;id=1569">Chui Tey</a> at February 16, 2005 12:31 AM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1570">
<p>> 2**69 operations is still an awful lot of<br />
> operations. What is it that lets us say that<br />
> 2**69 is "broken" but 2**80 is "not broken"?<br />
The 2**80 is a brute-force attack. Less than brute force means that it is "broken", for the reason cjr gave. ("broken" and defeatable in practice are two different things). The only exception to this convention I'm aware of is in public-key cryptography.<br />
AFAIK, all known public-key algorithms are vulnerable to less than brute-force attack. The key sizes are boosted to compensate, for lack of any alternative. </p>
</div>
<p class="posted">Posted by: <a href="mailto:mscibing@yahoo.com">Andrew Wade</a> at February 16, 2005 12:34 AM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1571">
<p>Where people take p = password</p>
<p>p' = sha1(p)<br />
or <br />
p' = sha1(p, nonce)</p>
<p>This case is reasonably safe as you're allowed collisions in the problem space (different users can (and probably do) choose the same password)... as long as p' is not exposed to the attacker. </p>
<p>The problem sets in when you use MD5 or SHA1 for digital signatures:</p>
<p>For example:</p>
<p>md5sum file</p>
<p>This allows an attacker *theoretically* to change file and compute the same hash from a different bag of bytes. This eliminates the trust you might have had in the file being made available to you. </p>
<p>One ISP I know "verified" downloads from a nearby mirror using a similar method. It wasn't until I pointed out that an attacker could change the source by contributing to the application. Verification of checksums / hashes is not the be all and end all, but this break by the researchers makes it more difficult to trust the class of hashes which have been shown to be weak for verification purposes.</p>
<p>Andrew</p>
</div>
<p class="posted">Posted by: Anonymous at February 16, 2005 01:17 AM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1572">
<p>Very impressive if it pans out. In some ways, the writing was on the wall with their earlier work, but you still just someone don't beleive it's coming. WOW! </p>
<p>Looking forward to a public release after they get any typos out (understandable). </p>
</div>
<p class="posted">Posted by: Anonymous at February 16, 2005 01:26 AM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1574">
<p>The design structure of all hash functions in the MDx and SHA family is based on an unbalanced Feistel network structure opearting in a non-linear feedback shift register mode which we told last year june in our new hash function design paper called CRUSH mentioning that this structure is a single point of failure for cryptography.</p>
<p>Regards<br />
Praveen Gauravaram<br />
</p>
</div>
<p class="posted">Posted by: <a target="_blank" title="http://www.isrc.qut.edu.au" href="http://www.schneier.com/cgi-bin/mt/mt-comments.cgi?__mode=red;id=1574">Praveen</a> at February 16, 2005 01:51 AM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1576">
<p>SHA-1 is broken but not yet cracked. This is a compressor function collision, getting to a full hash function collision has not yet happened.</p>
<p>We have a couple of years (but not much more) to plan a transition to more secure algorithms. </p>
</div>
<p class="posted">Posted by: <a href="mailto:hallam@gmail.com">Phill</a> at February 16, 2005 02:00 AM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1578">
<p>Okay, could someone a bit more well-versed in the Hows and Whys of cryptography step up and explain why a hash algorithm that is "broken", when used in an HMAC setup, is suddenly "not broken"?</p>
<p>Is it simply because we're suddenly involving a secret key?</p>
<p>If so, could not these advances mean that obtaining that secret key may be a bit easier than we previously thought, too?<br />
</p>
</div>
<p class="posted">Posted by: Mike at February 16, 2005 02:07 AM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1580">
<p>I notice everyone are still using Moore's law in their calculations, didn't they notice things are changing, we're hitting the limit.</p>
<p>http://www.gotw.ca/publications/concurrency-ddj.htm<br />
</p>
</div>
<p class="posted">Posted by: <a href="mailto:lcordier@airwavetech.co.za">Louis Cordier</a> at February 16, 2005 02:34 AM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1583">
<p>Digital signatures aside, I think this attack would be devestating to the current wave of file-sharing networks. The one I am most familiar with is the ed2k network, especially using the eMule client. eMule has since distanced itself from the original MD4 (yes, you read it right) used for integrity checking in favor of SHA-1. However, if even this has been cracked, there's now nothing stopping an attacker from substituting random garbage for blocks of legitimate content...and without anyone being the wiser until it's too late. The blocks would continue to pass virally from node to node with no way to determine whether they're legit or not. Score +1 for the **AA's of the world =(</p>
</div>
<p class="posted">Posted by: Mike at February 16, 2005 02:52 AM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1585">
<p>if SHA-1 is broken now,<br />
what are the alternatives now?<br />
Any suggestions?</p>
<p>Louis Cordier: <br />
It is true that ordinary processors dont double their raw processing speed every 18 months anymore.<br />
However, the trend goes now to multi-core processors. A multi-core processor is perfect for cracking SHA-1 since there are a lot of independent calculations to do.</p>
</div>
<p class="posted">Posted by: Jan-Eric Duden at February 16, 2005 04:51 AM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1586">
<p>I agree with my collegues above: 2^69 is still huge.</p>
<p>And what I might like to add is that we are talking about _speculation_ as long as the paper is not published. Until we don't see the paper (with all the qualifications that must be fulfilled for the attack to work), I think it is quite dangerous to discuss sheer assumptions. (although I am very exited to get my hands on this paper and nervous about the possible consequences)</p>
</div>
<p class="posted">Posted by: <a href="mailto:gondrom@sw-architect.de">Tobias Gondrom</a> at February 16, 2005 04:55 AM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1588">
<p>@Mike<br />
> However, if even this has been<br />
> cracked, there's now nothing stopping<br />
> an attacker from substituting random <br />
> garbage for blocks of legitimate<br />
> content<br />
It isn't _that_ broken. Computing power is still stopping the attackers.</p>
<p>And also in your scenario. If I were the attacker, I would simply tell you that my random bytes had the legitimate SHA1-value. You still wouldn't find out I fooled you until the whole file was downloaded.</p>
<p>SHA1 in p2p-networks serves as a way for users to compare two files. You still have to trust the one giving you the SHA1-value. Integrety of the file is not assured.</p>
</div>
<p class="posted">Posted by: Johannes at February 16, 2005 05:06 AM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1589">
<p>If the argument that it was attacked by 2^69 computations is true (we don't have proof yet) then we can safely say it is broken as it is less than B'day on SHA-1. It is the time for us to look at new designs. The good start is to have a new kind of iterative structure first than Merkle-Damgard structure. So the question is what kind of abstract structure or a hash function model can resist these attacks. Once the compression function is attacked, the attack can be extended to other blocks as well with further research. So hash value and the chaning value should be different and chaning value should be more than the hash value. Interesting to see Stefan Lucks proposed structure.<br />
The future research should proceed on these lines. We need to have secure hash functions and give importance to efficiency once you achieve security in the first instance. Anyway, the performance expected from a hash function depends on the application<br />
</p>
</div>
<p class="posted">Posted by: <a target="_blank" title="http://www.isrc.qut.edu.au" href="http://www.schneier.com/cgi-bin/mt/mt-comments.cgi?__mode=red;id=1589">Praveen</a> at February 16, 2005 05:08 AM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1590">
<p>Andrew Wade wrote:<br />
> The 2**80 is a brute-force attack. Less than</p>
<p>> brute force means that it is "broken", for the</p>
<p>> reason cjr gave. ("broken" and defeatable in</p>
<p>> practice are two different things). The only</p>
<p>> exception to this convention I'm aware of is in</p>
<p>> public-key cryptography.</p>
<p>> AFAIK, all known public-key algorithms are</p>
<p>> vulnerable to less than brute-force attack. The</p>
<p>> key sizes are boosted to compensate, for lack</p>
<p>> of any alternative.</p>
<p><br />
All hashes are necessarily vulnerable to less than brute-force attack as well, simply because they are hashes. Anytime hashtext is allowed to be shorter than the corresponding plaintext, collisions must occur because the possible combinations are more finite. There is no way around this, so like for public-key cryptography, one must compensate by having longer hashtext. The perceived usefulness of modern hashes appears to exceed the perceived usefulness of the 8-bit checksum by a magnitude proportional to how many more collisions the 8-bit checksum would have in the given application. Defining "broken" as "requiring less than brute force" therefore renders the term "broken" meaningless since, in the absence of more "secure" hashing algorithms, making the hashtext longer necessarily reduces collisions. However, because when the length of the hashtext reaches the length of the plaintext, you essentially have symmetric cryptography with a known key and algorithm (unless of course the algorithm allows collisions when hashtext length equals plaintext length, currently seen as undesirable), there is a paradox where a longer hashtext is also less secure. The true usefulness of a hash is proportional to how much processing it takes to find a collision. If we assume that the more processing it takes to calculate a hash in the first place, the more processing it would take to find a collision, the challenge becomes the development of hash algorithms that take more processing power. If available processing power were to cease increasing, the practicality of finding collisions would also cease to increase, and there would be no further need or use for newer hash algorithms that take more processing power. As long as that doesn't happen, expect each hash algorithm to be replaced periodically with a newer one that takes more steps to calculate. After all is said and done, that is really the only way to stay ahead of the game.</p>
</div>
<p class="posted">Posted by: Anonymous at February 16, 2005 05:21 AM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1591">
<p>what now? With MD5 and SHA-1 being cracked, what hash function is considered secure? </p>
</div>
<p class="posted">Posted by: <a target="_blank" title="http://www.bogado.net" href="http://www.schneier.com/cgi-bin/mt/mt-comments.cgi?__mode=red;id=1591">Victor Bogado</a> at February 16, 2005 06:00 AM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1593">
<p>I have a number of hash functions here in source code format:</p>
<p>http://www.maradns.org/download/sums-20011111.tar.bz2</p>
<p>And papers for these hash functions:</p>
<p>http://www.maradns.org/download/sums-papers-20010818.tar.bz2</p>
<p>Some interesting stuff is here:</p>
<p>Tiger: 192-bit hash. Not broken yet.</p>
<p>Whirlpool: 512-bit hash; uses a Rijndael (AES) variant as the compression function.</p>
<p>AEShash: Hash algorithm that uses Rijndael as the compression function.</p>
<p>- Sam<br />
</p>
</div>
<p class="posted">Posted by: <a target="_blank" title="http://www.samiam.org/" href="http://www.schneier.com/cgi-bin/mt/mt-comments.cgi?__mode=red;id=1593">Sam Trenholme</a> at February 16, 2005 06:21 AM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1596">
<p>Maybe we should start encoding meta-data along with the hash, so instead of trusting only on the hash to confirm that the message is from who sign it, we would encode along the message, the size, type and whatever characteristic could define the message. </p>
<p>For instance, suppose I sign the message "Hi, I'm Victor", along with the hash it would contain the size (14 bytes), type (English text), encoding (7bits ASCII) and how about the range of codes used in the messages (from U+0027 - U+0074).</p>
<p>A good hash would give a uniformly distributed random hash for the message, so it is safe to assume that even if we could find a collision, it would be highly unprovable that it would satisfy all the meta-data. In some cases it could be provable that this kind of hash is unbreakable, since there is a finite number of messages that satisfy the meta-data (if you could hash all possibilities and verify that there were no collisions you're 100% safe).</p>
</div>
<p class="posted">Posted by: <a target="_blank" title="http://www.bogado.net" href="http://www.schneier.com/cgi-bin/mt/mt-comments.cgi?__mode=red;id=1596">Victor Bogado</a> at February 16, 2005 06:50 AM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1597">
<p>History shows that reducing the brute-force key space of an algorithm is only the beginning of the end: I am sure that the attack will be optimized and improved, so that the key space will be further reduced. This has been shown during several attacks on FEAL, too.</p>
<p>That means that we should not trust that in near future the key space stays at 2**69. When similar hash algorithms also shows the SHA-1 weakness, then we need an new hash algorithm nearly immediatly.</p>
</div>
<p class="posted">Posted by: Simon Steinmeyer at February 16, 2005 07:16 AM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1599">
<p>I'm not a cryptographer but to those who want to know why HMAC use of a hash function is not broken, it's because, as somebody else suggested, of the key.</p>
<p><br />
With a digital signature all you have to do is find another blob of data which hashes to the same hash. You are free to choose any blob of data.</p>
<p><br />
With HMAC you are not free to choose any other blob of data because a secret key is always added to the data before it is hashed and you don't know that secret key. So you still need to guess the key or the person verifying the HMAC will get a different hash than you.</p>
<p>(On a side-note, how the heck do I get line breaks when I post comments?)</p>
</div>
<p class="posted">Posted by: <a href="mailto:mikemc@tarantella.com">Mike</a> at February 16, 2005 07:32 AM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1600">
<p>Oh, they show up in the real post but not in the preview. Marvelous.</p>
</div>
<p class="posted">Posted by: <a href="mailto:mikemc@tarantella.com">Mike</a> at February 16, 2005 07:33 AM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1601">
<p>Pardon my ignorance, but what good does it do me if I can find a few collisions with a digital signature on a document? Aren't the collisions going to be a bunch of gibberish that hashes to the same value? How would I use the gibberish to cause trouble? I can see a DOS scenario, where I replace a good message with gibberish, but I can't see how I could massage a message to say something intelligible but different, like "deposit this in another account," or "I inhaled," or whatever.</p>
</div>
<p class="posted">Posted by: Scott Stanfield at February 16, 2005 07:58 AM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1602">
<p>The importance is that often there is someplace in the document that you can change willy-nilly, while retaining semantic meaning. </p>
<p>for CRC-32, all you needed was 4 bytes in a row, and you could completely control the hash of the document. I don't know how many are needed for SHA, but let's say that it is on the order of 80 bytes:</p>
<p>- In a jpeg, you could add a comment<br />
- In a MS .doc, you could add meta-data<br />
- in an exe, you might be able to add stuff at the end, outside the instruction stream.<br />
- In HTML, add stuff in a javascript comment or after the closing html tag</p>
<p>For anything but raw text, it really isn't that hard to find a large number of contiguous bytes you can modify without changing the semantic meaning.</p>
</div>
<p class="posted">Posted by: <a href="mailto:johan@mailinator.com">johan</a> at February 16, 2005 08:11 AM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1603">
<p>Scott, you ignore the fact that forcing a collision can be done not only with a gibberish message but also with a message containing a few bytes of gibberish. Consider the case where a cryptosignature is used to keep a machine from running untrusted software. An executable file can contain a few bytes of gibberish without compromising its ability to run (just stick it in an unused constant somewhere), and then be signed as if it came from a trusted source. This is a bad thing indeed.</p>
</div>
<p class="posted">Posted by: <a href="mailto:kennykb@acm.org">Kevin</a> at February 16, 2005 08:13 AM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1604">
<p>A few people here are questioning the meaningfulness of this attack, because they think that a collision to a known plaintext "I'm Bill." would look something like ",#&($@<?}*(&³µG" - which would be basically useless, I would usually think the same.</p>
<p>BUT, remember the MD5 attack... when I first saw it, I was VERY impressed NOT because they DID find a collision, no! But because the collision had only A FEW bytes changed to the original message.</p>
<p>Look here: http://www.x-ways.net/md5collision.html</p>
<p>You can see there are ONLY 24 bits (or even less) changed (which is 2.4% of this 1024bit message).</p>
<p>So this scenario IS a reason to panic. And as soon as they will publish a SHA-1 collision with the same 'features' as the MD5 collision, we are in trouble.</p>
</div>
<p class="posted">Posted by: <a href="mailto:none@none.com">RXD</a> at February 16, 2005 08:16 AM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1605">
<p>http://eprint.iacr.org/2004/199</p>
<p>Previous attacks by the same team of researchers</p>
</div>
<p class="posted">Posted by: vipul at February 16, 2005 08:22 AM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1606">
<p>hmmm.</p>
<p>SHA-1 has 2**80 unique hash-numbers. fine.<br />
But isnt the odd to get one 1/2**79, because statistically, I hit one after 2**79 tries after trying all?</p>
<p>please excuse my bad english.</p>
<p><br />
-- <br />
grisu</p>
</div>
<p class="posted">Posted by: <a href="mailto:grisu@guru.at">grisu</a> at February 16, 2005 08:35 AM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1607">
<p>Concatenating MD5 and SHA1 doesn't give you as much extra security as you'd think, because of this beautiful result from Joux at last year's Crypto. Basically, if it takes you 2^{69} work to cause a collision in SHA1 in a general context (from most any starting hash value), the most it can take to find a collision for SHA1 || MD5 is about 2^{75}--you find 64 places in the message where you can insert a colliding value for SHA1, and then do a 2^{64} search to find a collision between those in MD5. (If this isn't clear, go read the Crypto 2004 paper--the result is not hard to understand at all!)</p>
<p>HMAC is harder to attack because the attacker doesn't know the internal values of the hash function when she's choosing her message blocks. To the extent that she needs to know what some bits of the hash chaining value are to choose the next message bit, her attack is blocked. But since Wang & company ahven't published details of their attacks, it's really not possible to know how big a problem this is.</p>
<p>The eprint archive has a nice paper by Phil Hawkes and Greg Rose trying to reconstruct the Wang attack on MD5, which is probably getting a lot of downloads right now....</p>
<p>--John Kelsey</p>
</div>
<p class="posted">Posted by: <a href="mailto:kelsey.j@ix.netcom.com">John Kelsey</a> at February 16, 2005 08:42 AM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1608">
<p>Please explain me one thing.<br />
Everyone keep saying: SHA-1 is broken... It takes 2^69 operation to broke it...</p>
<p>I dont understand.<br />
Every hashing algorithm will have collisions. Every. Because we have limited hash space to represent unlimited variants of data. Yes? Yes.<br />
So EVERY algorithm can be broken. They manage to collide in 2^69 tries of 2^80 possibilites. ENORMOUS LUCK. Its not something to remember.<br />
Lets say, after introduction od SHA-256 I broke it in 20 tries. Luck. Then you say SHA-256 is broken??? How could you use word broken... I merly manage to collide.<br />
So concluding. Using your words, every hashing function is broken. Only time and luck is important.<br />
I think that it doesnt matter if someone find colision or not. It wont change nothing. Keys must became longer, as computing power grows greater, to keep teoretical computing time relatively impassible long. And of that time is 2^99999 years, and someone manage to find collision id 5 days? It changes nothing. He got lucky.</p>
</div>
<p class="posted">Posted by: Piw at February 16, 2005 08:46 AM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1609">
<p>Just to clarify, SHA-1 produce a hash of 160 bits (20 bytes). Collisions can be found with 2**(bits/2) by the brithday attack - go look at google for hash and birthday attack for explanation.</p>
<p>160 bit hash => 2**80 steps to find a collision.</p>
<p>SHA-256 has a 256 bit hash (32 bytes) and works with a similar algorithm to SHA-1. So 2**128 steps is brute force. Using that (or SHA-512) would give a period of grace, but the attack may well be applicable to these, so a hash with a completely new basis would be "a good thing" (tm).</p>
<p>With the rider that anything new probably needs several years of cryptanalysis before we would trust it ...</p>
</div>
<p class="posted">Posted by: hamish at February 16, 2005 09:00 AM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1612">
<p>rainbow hash tables anyone?</p>
</div>
<p class="posted">Posted by: hendler at February 16, 2005 10:01 AM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1614">
<p>Bruce,</p>
<p>You didn't actually read the paper, did you? If you did, you would have noticed the footnote which says that the attack isn't on "the real thing".</p>
<p>Stop spreading rumors.</p>
</div>
<p class="posted">Posted by: <a href="mailto:hello@hotmail.com">Anonymous</a> at February 16, 2005 10:19 AM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1619">
<p>I like the way your titillating announcement of the work of Wang, et al upholds predictions you made late last year, Bruce. How lucky for you!</p>
<p>For reference: http://www.computerworld.com/securitytopics/security/story/0,,95343,00.html</p>
<p>Btw, how obnoxious is it to reference something that no one else can read?</p>
<p>Hey - other anon person, you're anon - why don't you post a link to your resource???</p>
<p>*disgusted*</p>
</div>
<p class="posted">Posted by: Anon at February 16, 2005 10:59 AM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1623">
<p>After last summer's announcement of the initial hash research, I wrote what many have said is a good overview of the subject:<br />
An Illustrated Guide to Cryptographic Hashes<br />
http://www.unixwiz.net/techtips/iguide-crypto-hashes.html</p>
</div>
<p class="posted">Posted by: <a target="_blank" title="http://www.unixwiz.net/blog/" href="http://www.schneier.com/cgi-bin/mt/mt-comments.cgi?__mode=red;id=1623">Steve Friedl</a> at February 16, 2005 11:38 AM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1624">
<p>Having actually implemented both SHA-1 and MD5 in assembly (while I was in college, in a calculus class), the length of the actual data is appended to the last null-padded block. So, even small changes in the size have a significant impact on the final sum, and cannot be covered up by any blocks of data coming after it (except for man-in-the-middle, but that is useless in most situations). Other meta-data should be used as a signature, where it is included in the original data, outside the data, where it is hashed, and then both hashes are hashed (basically what PGP does).</p>
<p>In the message "Hi, I'm Victor" there are 12 different characters. If only these 12 characters are allowed, there are 12**14 = 1283918464548864 or 1.28e+15 possibilities that could satisfy all the meta-data. The total possibilities for a SHA-1 sum is 2**160 ~= 1.46e+48. Using 1 bit as a flag for each sum would require 2**160 /8 ~= 1.83e+47 ~= 1.62e+32 PB (1PB= 1024*1TB= 1024*1024*1GB, I think) of storage. In the much reduced 12**14 number of possibilites, this would still require a minimum of 12**14 *20 ~= 2.57e+16 ~= 23,914,845 GB ~= 22.8 PB of storage, if each sum was unique (we cannot use the 1 bit mapping in this reduction).</p>
<p>Using the techniques of this not yet published paper could reduce the storage requirement, but the only messages that could be proved to have a unique hash are those that are shorter in length than the hash. In the case of SHA-1, this is 20 bytes.</p>
<p>Using the vulnerabilities to prove the authenticity of a short message is not yet too practical.</p>
<p>A pretty secure hash method would be something like the following:</p>
<p>fast:<br />
d1= hash1(message);<br />
d2= hash2(message);<br />
d3= hash1((message+d1)+d2);</p>
<p>slow:<br />
d1= hash1(message);<br />
d2= hash2(message);<br />
d3= hash1((d1+message)+d2);</p>
<p>The 2 hash functions MUST be different to a good degree (I believe SHA-1 and MD5 suffice, from my experience). The + operator is equivalent to appending the right operand onto the left, i.e. "a"+"b"="ab". d1, d2, and d3 are the message digests. All three digests MUST be distributed, along with what format the digests are in (hexadecimal or base64), along with what hash functions were used, along with the designation "slow" if the slow method is used ("fast" is default).</p>
<p>The fast method could be computed fairly quickly by doing the 2 hashes on each block (making use of the processor cache), except for the final blocks. The slow method should be more secure, as only d1 and d2 could take advantage of the cache effect (d3 would have to be computed from scratch).</p>
<p>Creating a collision on d1 and d2 would be pretty difficult, d3 would be much more. d1 and d2 MUST be hashes of only the original message, as hash2(mesage+d1) could make it easier to find a collision (as the effective message would then be different).</p>
<p>I am not a cryptographer, but this scheme seems obviuosly much harder to crack for many reasons.</p>
<p>As far as I know, this scheme is original, but is similar to PGP and 3DES. I think this is an obvious possible solution, and as such cannot be patented.</p>
<p>Tell me what you think.<br />
</p>
</div>
<p class="posted">Posted by: Joshua Stephanoff at February 16, 2005 11:38 AM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1626">
<p>It's important to qualify what is meant by "broken" -- the ability to find collisions weakens the use of a cryptographic hash in digital signatures.</p>
<p>The speedup is about 0.0005 over the brute force average for finding a collision. </p>
</div>
<p class="posted">Posted by: <a href="mailto:kudzu@tenebras.com">Michael Sierchio</a> at February 16, 2005 11:47 AM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1627">
<p>Interesting, but not quite as interesting as colluding Poker Bots.</p>
</div>
<p class="posted">Posted by: <a target="_blank" title="http://www.casinorobots.com/poker/collusion.htm" href="http://www.schneier.com/cgi-bin/mt/mt-comments.cgi?__mode=red;id=1627">CasinoRobots.com</a> at February 16, 2005 12:00 PM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1630">
<p>>rainbow hash tables anyone?</p>
<p>>Posted by: hendler at February 16, 2005 10:01 AM</p>
<p>Creating rainbow tables for an algorithm has nothing to do if it is broken or not.</p>
<p>rainbow tables use the hashing algorithm the way it is supposed to be used and creates a "dictionary" of cleartext->hashes value.</p>
<p>You can generate rainbow tables for any algorithm you know the workings of (preferably have source code too). The thing is having enough disk space to store that information.. </p>
<p>Try this: Use a rainbow table generator which tells you the etsimated key space and disk space, enter the following parameters.<br />
Charset: full<br />
Hash: SHA1 Min Len: 1 Max Len: 263<br />
Chain count: 57,000,000 No of Tables:<br />
9,999,999,999 (maximum)</p>
<p>With this data, the program i am using says the key space is 1.#INF, disk space: 1.665.497.180.-45 GB, and success probability: -1.#INDO (-1.#J%)<br />
Obviously, this is too large for the program to even calculate the key space. </p>
<p>And that's for the domain, if you want to calculate the range try:<br />
Sha1, min 1, max 160, charset hex, chain count 40000000, no of tables 9999999999.<br />
The RANGE key space is merely 4.867*10^192. </p>
<p>I hope you get the message.. If you want to do rainbow tables, better have a lot of disks.. But since NIST couldn't do it to validate the algorithm, then neither can you.</p>
</div>
<p class="posted">Posted by: <a target="_blank" title="http://www.cryptogram.gr" href="http://www.schneier.com/cgi-bin/mt/mt-comments.cgi?__mode=red;id=1630">Kryptogramma</a> at February 16, 2005 12:23 PM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1631">
<p>How is the 2^69 hash operations assertion to be understood? Is the cost the same no matter what the message input size? Also, can collisions be found for any input message?</p>
</div>
<p class="posted">Posted by: Anonymous at February 16, 2005 12:25 PM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1632">
<p>Re compute power:</p>
<p>The IBM/SONY/Toshiba Cell processor has 1 ppc64 core and 8 special processors (SPE's) per 30-watt chip, clocked at 4.5 GHz. Each SPE can dispatch two instructions per clock; each SPE has 128 registers that are 128-bits wide and are joined with 4 128-bit busses running at half clock speed. This provides something on the order of 100+ (and maybe more) general purpose Giga integer ops for things like code-breaking. </p>
<p>Conclusion: 1000 Sony playstation-3's appropriately hacked would draw 30KW of power (a bit on the high-end for a suburban home, but achievable) and could achieve 2^36 ops/sec x 2^16 secs/day x 2^10 consoles == 2^62 ops/day -- OK, but each round might take 2^8 (?) ops so its maybe 2^54 rounds/day within reach of a crazy retired .com CEO, from their garage. That's an awesome large number... </p>
</div>
<p class="posted">Posted by: <a target="_blank" title="http://www.linas.org/math/sl2z.html" href="http://www.schneier.com/cgi-bin/mt/mt-comments.cgi?__mode=red;id=1632">Linas Vepstas</a> at February 16, 2005 12:35 PM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1633">
<p>If you're using a supercomputer that does 40 teraflops (40 trillion operations per second), then it would take... *thinks*... between 12 and 13 years, and about 6 years on average.</p>
</div>
<p class="posted">Posted by: <a href="mailto:cheekysod@gmail.com">John</a> at February 16, 2005 12:36 PM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1634">
<p>It's not inconsistent with the tennents of research to not be publicly trumpeting this research.</p>
<p>First of all, I presume that the current distribution is for the purposes of refereeing for a peer-reviewed publication. They may also be asking for verification of their results -- given that it could be extremely embarassing to have this wrong (in proportion to the notoriety gained by having this right.</p>
<p>This is also somewhat sensitive information, so they may want 'white hats' to have a couple of weeks knowledge to prepare for the stuff that hits the fan when this becomes public knowledge.</p>
</div>
<p class="posted">Posted by: <a target="_blank" title="http://www.bcgreen.com" href="http://www.schneier.com/cgi-bin/mt/mt-comments.cgi?__mode=red;id=1634">Stephen SamueL</a> at February 16, 2005 12:57 PM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1637">
<p>One way of looking at it is that breaking SHA-1 with 2**69 operations is still more work than brute forcing MD5 with 2**64 operations.<br />
</p>
</div>
<p class="posted">Posted by: <a href="mailto:dark@xs4all.nl">Richard Braakman</a> at February 16, 2005 01:34 PM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1639">
<p>I wrote the "MD5 To Be Considered Harmful Someday" paper that discussed attacks given only Wang's test vectors. This is...a bit different.</p>
<p>It's a 2^69 attack against SHA-1, which has the distinct problem of being 32x the complexity of bruting MD5 (2^5 = 32). We never did see a MD5 brute; we needed Wang's reduction to a 2^24 to 2^32 for us to eventually end up with vectors.</p>
<p>I don't expect to ever see SHA-1 collision vectors. We still need to migrate away, but this is akin to Dobbertin's proof of possibility right now. Respond, don't panic.<br />
</p>
</div>
<p class="posted">Posted by: <a target="_blank" title="http://www.doxpara.com" href="http://www.schneier.com/cgi-bin/mt/mt-comments.cgi?__mode=red;id=1639">Dan Kaminsky</a> at February 16, 2005 01:53 PM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1641">
<p>Don't tell me not to panic! I will panic immediately, THANK YOU!</p>
</div>
<p class="posted">Posted by: <a href="mailto:tracy.milburn@gmail.com">Tracy Milburn</a> at February 16, 2005 02:37 PM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1642">
<p>What's the practical implication of this research?</p>
<p>For example, how hard is it to create an X.509 certificate that looks like a valid Microsoft code-signing certificate with the attacker's public key? I'm assuming it is relatively trivial for the attacker to create a certificate extension containing the appropriate random garbage, but is it really 2^69 operations to select the right garbage?</p>
</div>
<p class="posted">Posted by: Anonymous at February 16, 2005 02:40 PM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1646">
<p>theory-edge,<br />
mailing list/discussion for cutting edge developments in mathematics & algorithmics, click my initials</p>
</div>
<p class="posted">Posted by: <a target="_blank" title="http://groups.yahoo.com/group/theory-edge" href="http://www.schneier.com/cgi-bin/mt/mt-comments.cgi?__mode=red;id=1646">vzn</a> at February 16, 2005 05:44 PM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1647">
<p>MY PERSONAL TOP SECRET TO BREAK CODES: ParaModulation SATisfiability (Para-SAT) and Quantum Computing (Schor-like).</p>
<p>Dictionary Attacks ARE INSUFFICIENT!!!.<br />
</p>
</div>
<p class="posted">Posted by: <a href="mailto:anonymous@anonymous@anonymous@anonymous.com">open4free</a> at February 16, 2005 06:22 PM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1650">
<p>948fad80398ce3df645c91da456c2669e7fed61f<br />
crack this hash :)</p>
</div>
<p class="posted">Posted by: <a target="_blank" title="http://www.aol.com" href="http://www.schneier.com/cgi-bin/mt/mt-comments.cgi?__mode=red;id=1650">Patrick</a> at February 16, 2005 07:42 PM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1652">
<p>>And that's for the domain, if you want to calculate the range try:<br />
>Sha1, min 1, max 160, charset hex, chain count 40000000, no of tables 9999999999.<br />
correction on my previous post:<br />
min here should be 160 as the key length is fixed. Sorry about that.</p>
</div>
<p class="posted">Posted by: <a target="_blank" title="http://www.cryptogram.gr" href="http://www.schneier.com/cgi-bin/mt/mt-comments.cgi?__mode=red;id=1652">Kryptogramma</a> at February 16, 2005 08:20 PM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1654">
<p>Actually, this sort of attack has real uses, assuming you have the computing power to do it, which organizations that can produce fast hardware implementations on custom chips can.</p>
<p>If you can produce two SHA1 strings that collide and are a multiple of the fundamental hash length, any two strings that begin with those two will also collide.</p>
<p>This means that I can trivially produce any number of strings, whose last bits I can choose, and they will collide.</p>
<p>Consider a message format where the first two bytes are the length of the first object and then after that object are other objects. I can pick any chunks that collide, pad out to object length, and then follow with objects of my choosing. The two final strings will collide in their hashes, be different, and have a lot of content over which I have control.</p>
<p>You can do the same thing for the end of a message.</p>
</div>
<p class="posted">Posted by: <a href="mailto:davids@webmaster.com">David Schwartz</a> at February 16, 2005 08:53 PM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1656">
<p>grisu: No, it's 2^40 operations. Google for 'birthday paradox'.</p>
<p>DS<br />
</p>
</div>
<p class="posted">Posted by: <a href="mailto:davids@webmaster.com">David Schwartz</a> at February 16, 2005 08:56 PM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1661">
<p>Yeah... so... why isn't the paper generally available yet? Is it unfinished (and thus premature)? Or do the authors just have a penchant for childishness? Perhaps they'd rather sell it copy-by-copy for a low low price of only 500 RMB! Act now!</p>
<p>All I'm seeing so far is "Bruce Sez he saw something that could have meant that maybe SHA-1 is broken."</p>
<p>Which is great and all, but since there are so many crypto people in the hizzy (and would-be crypto people, too), why doesn't someone work out how reasonable it is to take this purely based on trust and reputation. And what impact it has on someone's reputation to say something was broken without being able to point to proof.</p>
<p>Is peer review a dead art? Replaced by cult of personality?</p>
</div>
<p class="posted">Posted by: Anonymous at February 16, 2005 11:19 PM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1662">
<p>I really wish people would stop saying "broken". Yes, I know that cryptographically it is broken. But practically, at least for now, SHA-1 is still plenty strong. 2^69 attempts is a whole lot harder than finding a non-crypto flaw in a system. As Schneier himself admitted in his most recent book, crypto isn't the weak link in most systems. Focusing on a (significant) weakness in a crypto algorithm gives the impression that the crypto is what makes the system secure, when in fact even a flawed algorithm like SHA-1 is still the strongest link in the security chain.</p>
</div>
<p class="posted">Posted by: Jeremy at February 16, 2005 11:22 PM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1667">
<p><br />
Even when these same people "broke" MD5, it was still a pretty limited break for most practical purposes. They could, maybe, generate two messages with the same hash, but that was far and away different from being able to generate messages that collide with a given hash.</p>
<p>> Is peer review a dead art? Replaced by cult of personality?</p>
<p>Yes to both. And Bruce is up there at the front of the seething masses.<br />
</p>
</div>
<p class="posted">Posted by: Anonymous at February 17, 2005 01:04 AM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1669">
<p>Just Re: SHA-1/MD5 and all the "hash-bash": I think it's important to emphasize that we are NOT talking about finding a collision to an arbitrary (i.e. chosen) plaintext message. Just colliding two random ones, at better than Bday paradox. So we're not all doomed just yet, contrary to the girl who stood outside Moscone today with the sign (see http://hisown.com/temp/02160020.JPG and ...21.JPG ;-)</p>
<p>J</p>
</div>
<p class="posted">Posted by: <a href="mailto:jl(butdontspam)@hisown.com">J (again)</a> at February 17, 2005 01:13 AM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1679">
<p>> Is peer review a dead art? Replaced by cult of personality?</p>
<p>>> Yes to both. And Bruce is up there at the front of the seething masses.</p>
<p>I posted the *disgusted* comment yesterday - and am so happy to see that I'm not the only one NOT sitting on the "Bruce Sez" bandwagon...</p>
<p>Double-nots aside, it's a good day!</p>
</div>
<p class="posted">Posted by: Anonymous2 at February 17, 2005 09:24 AM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1689">
<p>When this team broke MD5, they published two strings which had the same MD5 hash. It's trivial to verify - once you've got your head around the byte-ordering issues :-)</p>
<p>So for me the question is: has this team actually created two distinct strings which hash to the same SHA-1 value?</p>
<p>If they have, why not just post them so we can all verify it? But if not, then I don't think it's reasonable for anyone to claim point-blank that SHA-1 has been "broken". "Weakened", maybe.</p>
<p>Based on Bruce's reputation, I'd say they've probably done it - but it would be helpful if he could clarify this by saying outright that the paper does (or does not) include an actual SHA-1 collision.</p>
</div>
<p class="posted">Posted by: <a href="mailto:B.Candler@pobox.com">Brian Candler</a> at February 17, 2005 12:08 PM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1696">
<p>Even though an attacker can replace a document with digital signature with a garbage document with the same hash, it should be easy to convince any judge or jury that if someone can produce a readable document with the same hash, it is likely that such a document is original. The question in my mind is how many tries would it take to create a document that is at least 50% similar to the original document and produces the same hash.</p>
<p>I guess the lesson with digital signature is that any digital signature scheme should allow multiple hashes to be used! It's probably very very difficult to find 2 messages that produce identical MD5 *and* SHA-1 hash values. Is it?</p>
</div>
<p class="posted">Posted by: <a target="_blank" title="http://merlot.usc.edu/william/usc" href="http://www.schneier.com/cgi-bin/mt/mt-comments.cgi?__mode=red;id=1696">Bill Cheng</a> at February 17, 2005 02:08 PM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1702">
<p>Cryptography has a long history of people saying, "don't worry, it's just a scratch."<br />
This announcement means that it is time to look very seriously at the entire SHA-x family, and its alternatives. It is almost guaranteed that any weakness will be a foundation for more powerful attacks in the future. Expect (2 ^ 69) to have a considerably smaller exponent within 12 months.<br />
</p>
</div>
<p class="posted">Posted by: Bretty at February 17, 2005 07:33 PM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1705">
<p>Exciting news!</p>
<p>For people who have doubts about the news, please read this:</p>
<p>Chinese researchers compromise SHA-1 hashing algorithm</p>
<p>http://www.commsdesign.com/news/showArticle.jhtml?articleID=60401254</p>
<p>>>>>>>>>>>>>>>>>>>>>>>>>></p>
<p>......</p>
<p>Shamir and others said they believe the work of the Chinese trio will probably be proven to be correct based on their academic reputations, although details of the paper are still under review.</p>
<p>......</p>
<p>"This break of SHA-1 is stunning," said Ronald Rivest, a professor at MIT who co-developed the RSA algorithm with Shamir. "Digital signatures have become less secure. This is another reminder that conservatism is needed in the choice of an algorithm," added Rivest at the panel session.</p>
<p>Rivest noted that one member of the China team, Lisa Yin, was a PHD student who studied under him at MIT. Another member of the team was responsible for cracking the earlier MD5 hashing algorithm.</p>
<p>"I have strong reasons to believe the results [of the paper] are correct," Rivest said.</p>
<p>......</p>
</div>
<p class="posted">Posted by: <a href="mailto:tonysu@yahoo.com">Tony Su</a> at February 17, 2005 10:12 PM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1706">
<p>Another article at http://www.theregister.co.uk/2005/02/17/sha1_hashing_broken/ says that it is official that SHA-1 was broken ...</p>
<p>If it is based on the same source here, the conclusion may be pre-mature, but it does contain something extra ... </p>
<p>"A collision has been discovered in the full version in 269 hash operations, making it just possible to mount a successful brute-force attack with the most powerful machines available today."</p>
<p>"A collision has been discovered" ?!!! Can anyone confirm that? I sure can wait for 2**xxx days :)</p>
</div>
<p class="posted">Posted by: <a href="mailto:tonysu@yahoo.com">Tony Su</a> at February 17, 2005 10:40 PM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1717">
<p>What I've seen is a 58/80 step collision which is said to have taken 2^{33} hashing operations. This is up on the web at http://makeashorterlink.com/?D1605138A</p>
<p>They don't have the ability to do 2^{69} operations (that's a lot of work!). But since the previous best attack was estimated at 2^{71} work to break 53/80 steps, this is a pretty nice demonstration.</p>
<p>--John</p>
</div>
<p class="posted">Posted by: Anonymous at February 18, 2005 11:38 AM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1723">
<p>HERE's the paper<br />
http://theory.csail.mit.edu/~yiqun/shanote.pdf<br />
</p>
<p><br />
transend the divine water<br />
red ocean ninja clan</p>
</div>
<p class="posted">Posted by: <a href="mailto:transend@postmaster.co.uk">transend</a> at February 18, 2005 01:25 PM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1742">
<p>Wowie! Thanks, transend!!! ^_^</p>
</div>
<p class="posted">Posted by: Mike at February 18, 2005 05:33 PM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1746">
<p>just fyi, I found the summary paper on Lisa's web site</p>
<p>http://theory.csail.mit.edu/~yiqun/shanote.pdf</p>
<p>The paper on MD5 collision by Wang last year<br />
http://eprint.iacr.org/2004/199.pdf </p>
</div>
<p class="posted">Posted by: <a href="mailto:weidongshao@yahoo.com">Weidong Shao</a> at February 18, 2005 07:41 PM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1753">
<p>>>><br />
Please explain me one thing.<br />
Everyone keep saying: SHA-1 is broken... It takes 2^69 operation to broke it...</p>
<p>I dont understand.<br />
Every hashing algorithm will have collisions. Every. Because we have limited hash space to represent unlimited variants of data. Yes? Yes.<br />
So EVERY algorithm can be broken. They manage to collide in 2^69 tries of 2^80 possibilites. ENORMOUS LUCK. Its not something to remember.<br />
Lets say, after introduction od SHA-256 I broke it in 20 tries. Luck. Then you say SHA-256 is broken??? How could you use word broken... I merly manage to collide.<br />
So concluding. Using your words, every hashing function is broken. Only time and luck is important.<br />
I think that it doesnt matter if someone find colision or not. It wont change nothing. Keys must became longer, as computing power grows greater, to keep teoretical computing time relatively impassible long. And of that time is 2^99999 years, and someone manage to find collision in 5 days? It changes nothing. He got lucky.<br />
<<<</p>
<p>But with a collision in hand, it becomes easier to find more collisions.</p>
<p>That, and anyone so astronomically lucky isn't going to a computer scientist, they're going to be living off the lottery.</p>
</div>
<p class="posted">Posted by: Adeodatus at February 19, 2005 12:43 AM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1765">
<p>Great academic exercise. In the real world though, attackers are going to look for much easier ways to break in than using brute force against a hash. Why bother digging a tunnel into someone's house if he leaves a window open? Those storing and transmitting classified or very sensitive info should be using a cryptologic system anyway and not just a SHA-1 or MD5 hash.<br />
</p>
</div>
<p class="posted">Posted by: Mike at February 19, 2005 11:53 AM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1792">
<p>Scott, you ignore the fact that forcing a collision can be done not only with a gibberish message but also with a message containing a few bytes of gibberish. Consider the case where a cryptosignature is used to keep a machine from running untrusted software. An executable file can contain a few bytes of gibberish without compromising its ability to run (just stick it in an unused constant somewhere), and then be signed as if it came from a trusted source. This is a bad thing indeed.</p>
<p>---------------<br />
http://www.ptdd.com<br />
http://www.yiwodisk.com<br />
</p>
</div>
<p class="posted">Posted by: <a target="_blank" title="http://www.ptdd.com" href="http://www.schneier.com/cgi-bin/mt/mt-comments.cgi?__mode=red;id=1792">ptdd</a> at February 19, 2005 09:02 PM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1795">
<p>hi,how are you!</p>
</div>
<p class="posted">Posted by: <a href="mailto:baibing66@yahoo.com">baibing</a> at February 20, 2005 05:55 AM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1801">
<p>Adeodatus, you are right.</p>
<p>Best solution for the time being is to migrate to higher range.</p>
<p>It doesn't make sense to migrating to 256bit, from the existing 160 bit and wait till 256bit get cracked (by assuming that today's technology won't grow rapidly, which is a big joke).</p>
<p>I feel better to adopt higher than 256 (something like 512), the probability of cracking hash (in what ever way) will reduce at least 1%</p>
</div>
<p class="posted">Posted by: <a href="mailto:jaleelpa@yahoo.com">Jaleel</a> at February 20, 2005 11:47 AM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1815">
<p>"It doesn't make sense to migrating to 256bit, from the existing 160 bit and wait till 256bit get cracked (by assuming that today's technology won't grow rapidly, which is a big joke)."<br />
Unless I'm missing something (and it's not the birthday paradox), 128 bit hashes aren't brute-forceable with today's technology.<br />
The fastest supercomputers in the world are about 2^48 times faster than the electromechanical Mark-I, arguably the first functional computer.<br />
A 256 bit hash takes 2^64 times as long to brute force as a 128 bit hash, if you have unlimited memory.<br />
In short, 256 bits is plenty. </p>
</div>
<p class="posted">Posted by: <a href="mailto:mscibing@yahoo.com">Andrew Wade</a> at February 21, 2005 12:49 AM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1817">
<p>I love chickens</p>
</div>
<p class="posted">Posted by: <a target="_blank" title="http://www.com" href="http://www.schneier.com/cgi-bin/mt/mt-comments.cgi?__mode=red;id=1817">nekyf_s_bradva</a> at February 21, 2005 04:58 AM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1825">
<p>www.video-poker.tvheaven.com</p>
</div>
<p class="posted">Posted by: <a target="_blank" title="http://www.video-poker.tvheaven.com" href="http://www.schneier.com/cgi-bin/mt/mt-comments.cgi?__mode=red;id=1825">AQlex</a> at February 21, 2005 08:11 AM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1827">
<p>F5fPxdTq8eJeuqSVejGmq2bp0hU1rv9UelE23rOyfSJQWPR94NpiPSRjVpWraaNby5wlkxMIu4csKR0=</p>
<p>crack this :)</p>
</div>
<p class="posted">Posted by: roger smith at February 21, 2005 09:30 AM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1831">
<p>Thanks transend for the link to the paper</p>
<p>http://www.cgisecurity.com</p>
</div>
<p class="posted">Posted by: <a target="_blank" title="http://www.cgisecurity.com" href="http://www.schneier.com/cgi-bin/mt/mt-comments.cgi?__mode=red;id=1831">http://www.cgisecurity.com</a> at February 21, 2005 10:35 AM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1835">
<p>After another posting on /. about PGP shifting to a stronger algorithm and reading some of the thread's comments I was wondering...</p>
<p>One Way Hash functions takes a large set of data <br />
(source) and produce a relatively short string. Since there is no way (very limited chance) of producing the original source data from the hash. All attacks are basically equivalent to "buffer overflow" attacks. Where the attacker modifies the source to produce an equivalent hash. Since we believe the hash is authentic to start with, why not add a source-size parameter to the hash. Most of these attacks modify and append data to the source data to make the hashes match. Given the additional (trusted) information about the<br />
source's size it would basically limit the usefulness of this type of attack. This will then <br />
basically be a protocol/conformity constraint on the modified source data which would make things<br />
a bit more difficult for any attacker. Other parameters could also be employed, for example a source-symbol frequency, etc. <br />
</p>
</div>
<p class="posted">Posted by: <a href="mailto:lcordier@airwavetech.co.za">Louis Cordier</a> at February 21, 2005 11:38 AM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1839">
<p>Q. What do you get when you break a cryptographic hashing algorithm? </p>
<p>A. A new compression algorithm. </p>
</div>
<p class="posted">Posted by: <a href="mailto:foo@foo.vapour.net">foo</a> at February 21, 2005 02:06 PM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1844">
<p>www.beyond-science.com broke every laws of physics </p>
<p>also look at http://www.texas-holdem-playing-cards.com/</p>
</div>
<p class="posted">Posted by: <a target="_blank" title="http://www.texas-holdem-playing-cards.com/" href="http://www.schneier.com/cgi-bin/mt/mt-comments.cgi?__mode=red;id=1844">zetalimit</a> at February 21, 2005 04:42 PM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1851">
<p>> Unless I'm missing something (and it's not the birthday paradox), 128 bit hashes aren't brute-forceable with today's technology.<br />
I was missing something, and 128 bit hashes are brute-forceable. See the newer thread for a low-memory technique:<br />
http://www.schneier.com/blog/archives/2005/02/cryptanalysis_o.html</p>
<p>I still think 256 bit hashes have a comfortable margin.</p>
</div>
<p class="posted">Posted by: <a href="mailto:mscibing@yahoo.com">Andrew Wade</a> at February 21, 2005 11:01 PM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<div id="c1881">
<p>How is the 2^69 hash operations assertion to be understood? Is the cost the same no matter what the message input size? Also, can collisions be found for any input message?</p>
</div>
<p class="posted">Posted by: <a target="_blank" title="http://www.ptdd.com" href="http://www.schneier.com/cgi-bin/mt/mt-comments.cgi?__mode=red;id=1881">puser</a> at February 22, 2005 09:30 PM</p>
<hr class="comment-separator">
</div>
<div class="commentbody">
<h2>Post a comment</h2>
<form method="post" action="http://www.schneier.com/cgi-bin/mt/mt-comments.cgi" name="comments_form" onsubmit="if (this.bakecookie[0].checked) rememberMe(this)">
<input type="hidden" name="static" value="1">
<input type="hidden" name="entry_id" value="130">
<div id="name_email">
<p><label for="author">Name:</label><br>
<input tabindex="1" id="author" name="author"></p>
<p><label for="email">Email Address:</label><br>
<input tabindex="2" id="email" name="email"></p>
</div>
<p><label for="url">URL:</label><br>
<input tabindex="3" type="text" name="url" id="url">
Remember Me?
<input type="radio" id="remember" onclick="rememberMe(this.form)" name="bakecookie"><label for="remember">Yes</label><input type="radio" id="forget" name="bakecookie" onclick="forgetMe(this.form)" value="Forget Info" style="margin-left: 15px;"><label for="forget">No</label><br style="clear: both;">
</p>
<p><label for="text">Comments:</label> <br/>
<textarea tabindex="4" id="text" name="text" rows="10" cols="40"></textarea></p>
<div align="center">
<input type="submit" name="preview" tabindex="5"
value=" Preview ">
<input style="font-weight: bold;" type="submit" name="post"
tabindex="6" value=" Post ">
</div>
</form>
<script type="text/javascript" language="javascript">
<!--
if (document.comments_form.email != undefined)
document.comments_form.email.value = getCookie("mtcmtmail");
if (document.comments_form.author != undefined)
document.comments_form.author.value = getCookie("mtcmtauth");
if (document.comments_form.url != undefined)
document.comments_form.url.value = getCookie("mtcmthome");
if (getCookie("mtcmtauth") || getCookie("mtcmthome")) {
document.comments_form.bakecookie[0].checked = true;
} else {
document.comments_form.bakecookie[1].checked = true;
}
//-->
</script>
</div>
<!-- end page content -->
<!-- robots content="noindex" -->
<p class="disclaim">Schneier.com is a personal website. Opinions expressed are not necessarily those of <a href="http://www.counterpane.com/">Counterpane Internet Security, Inc.</a>
</td>
<td class="kludge"> </td>
<td class="rightcol">
<table class="sidephoto" cellspacing=0><tr>
<td><img src="/images/bruce-blog.jpg" width=150 height=225 alt="Bruce Schneier">
</td></tr></table>
<table class="sidebox" cellspacing=0><tr><td class="sidemast">Weblog Menu</td></tr>
<tr><td class="sidebody">
<h3 class="first">Recent Entries</h3>
<ul>
<li><a href="http://www.schneier.com/blog/archives/2005/02/dmca_in_court.html">DMCA in Court</a></li>
<li><a href="http://www.schneier.com/blog/archives/2005/02/airport_screene.html">Airport Screeners Cheat to Pass Tests</a></li>
<li><a href="http://www.schneier.com/blog/archives/2005/02/choicepoint.html">ChoicePoint</a></li>
<li><a href="http://www.schneier.com/blog/archives/2005/02/the_economist_o.html">The <em>Economist</em> on High-Tech Passports</a></li>
<li><a href="http://www.schneier.com/blog/archives/2005/02/keystroke_loggi.html">Keystroke Logging for Profit</a></li>
<li><a href="http://www.schneier.com/blog/archives/2005/02/hunter_s_thomps.html">Hunter S. Thompson</a></li>
<li><a href="http://www.schneier.com/blog/archives/2005/02/hacking_a_bicyc_1.html">Hacking a Bicycle Rental System</a></li>
<li><a href="http://www.schneier.com/blog/archives/2005/02/cryptanalysis_o.html">Cryptanalysis of SHA-1</a></li>
<li><a href="http://www.schneier.com/blog/archives/2005/02/security_risks.html">Security Risks of Frequent-Shopper Cards</a></li>
<li><a href="http://www.schneier.com/blog/archives/2005/02/pirated_windows.html">Pirated Windows to Remain Unpatched</a></li>
</ul>
<h3>Archives</h3>
<ul>
<li><a href="http://www.schneier.com/blog/archives/2005/02/index.html">February 2005</a></li>
<li><a href="http://www.schneier.com/blog/archives/2005/01/index.html">January 2005</a></li>
<li><a href="http://www.schneier.com/blog/archives/2004/12/index.html">December 2004</a></li>
<li><a href="http://www.schneier.com/blog/archives/2004/11/index.html">November 2004</a></li>
<li><a href="http://www.schneier.com/blog/archives/2004/10/index.html">October 2004</a></li>
</ul>
<h3>Search</h3>
<form method="get" action="http://www.schneier.com/cgi-bin/search/search.pl">
<input id="search" name="Terms" size="15"><br>
<input type="radio" name="Realm" value="blog" checked>blog only<br>
<input type="radio" name="Realm" value="whole site">whole site<br>
<input type="submit" value="Search">
</form>
</td></tr></table>
<table class="sidebox" cellspacing=0><tr><td class="sidemast">Syndication</td></tr>
<tr><td class="sidebody">
<a href="http://www.schneier.com/blog/index.rdf">RSS 1.0</a> (full text)
<br><a href="http://www.schneier.com/blog/index.xml">RSS 2.0</a> (excerpts)
</td></tr></table>
<table class="sidebox" cellspacing=0><tr><td class="sidemast">Crypto-Gram Newsletter</td></tr>
<tr><td class="sidebody">
If you prefer to receive Bruce Schneier's comments on security as a monthly e-mail digest, subscribe to Schneier on Security's sister publication, Crypto-Gram.
<br><a href="crypto-gram.html">read more</a>
</td></tr></table>
<!-- /robots -->
</td></tr>
</table>
</body>
</html>
© 2022 Packet Storm. All rights reserved.
%7Cutmcsr%3D(direct)%7Cutmcmd%3D(none)){kind=small}
Follow us on Twitter
Follow us on Facebook
Subscribe to an RSS Feed