Fwd: Potential SHA 1 Hack Using Distributed Computing - Near Miss(es) May be Good Enough

[Aram Perez]

Anyone know more about this?

Begin forwarded message:

> From: "Steven W. Teppler"
> Date: August 13, 2007 4:41:56 PM PDT
> To: ST-ISC at MAIL.ABANET.ORG
> Subject: Potential SHA 1 Hack Using Distributed Computing - Near  
> Miss(es) May be Good Enough
>
> From DarkReading, via Heise Security:
>
>
> Cracking SHA-1 using distributed computing
>
>
>
> Researchers at the Technical University of Graz
> <http://portal.tugraz.at/pls/portal/url/page/TU_Graz>  have launched a
> distributed computing project to find a new kind of vulnerability  
> in the
> SHA-1 hash algorithm, which is used in numerous Internet  
> applications such
> as encrypted connections and e-mails. Hash algorithms like SHA-1  
> perform a
> sequence of mathematical operations on a block of data, for example a
> message, which generates a unique fixed length value or "digest"  
> from the
> arbitrary length message. Even minor changes to the original  
> message have a
> great effect on the digest, making changes easy to detect.
>
>
> <http://oas.wwwheise.de/RealMedia/ads/adstream_lx.ads/www.heise.de/ 
> security_
> uk/news/343347123/Middle1/he-test-contentads/zaehler.html/ 
> 343433386136643834
> 36633065623730?_RM_EMPTY_> 	
>
> However, collisions do occur: the algorithm produces the same  
> digest for two
> or more different messages. In the presence of a collision, the  
> variant
> messages involved cannot be distinguished from each other using the  
> digest,
> although indeed most of the variant messages would often not be  
> very useful,
> as they would consist of human-meaningless data. But finding  
> collisions is
> excessively arduous using simplistic methods. However, in 2005,  
> Chinese
> researchers demonstrated that the search for collisions can in  
> principle be
> optimized so that the number of attempts falls below the  
> theoretical minimum
> of 280. Then around  <http://www.heise-security.co.uk/news/77244> a  
> year ago
> a way to control the content of a possibly quite substantial  
> proportion of
> the manipulated message was made public.
>
> The cryptologists at the Technical University of Graz are taking a  
> slightly
> different approach: they are not looking directly for collisions,  
> but for
> "near misses", where SHA-1 produces very similar digests from two  
> different
> messages. They believe that two near misses with the same minimal
> differences might actually compensate for each other, producing the  
> same
> outcome as a true collision.
>
> To test this theory, the researchers have launched
> <http://boinc.iaik.tugraz.at/sha1_coll_search/>  a distributed  
> computing
> project. The trusty old Boinc <http://boinc.berkeley.edu/>  client  
> known
> from other such projects such as Seti at Home is also being used in  
> Graz. Those
> who wish to help find collisions are advised to read the manual on the
> project's website.
>
> The successor of SHA-1 is currently being redeveloped from scratch
> <http://www.heise-security.co.uk/news/84229>  because the algorithms
> originally intended to be used in the SHA-2 family all are similar  
> to SHA-1
> and therefore vulnerable to the same kind of attacks.
>
> Steven
>
>
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com