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

[Christian Rechberger]

Quoting Paul Hoffman <[EMAIL PROTECTED]>:


At 11:31 PM +0200 8/14/07, Christian Rechberger wrote:
The mentioned article is indeed confusing, the information in there  
took apparently several hops.


Welcome to the world of public cryptography! :-) At least I haven't  
seen anyone so far suggest that you will find pre-images.


Stay tuned, you never know ;-)
Something similar happened last year with our example for "meaningful   
collisions" for SHA-1 to reduced to 80% of its steps. We gave two  
meaningful but different ASCII texts followed by some random chunk as  
an example of our new technique back then. Suddenly someone invented  
HTML as an example of another application that ended up on a newsticker.




To address your questions: Indeed, we have our own "path", but more  
importantly we developed a new method to speed-up generation and  
testing of candidate message pairs and apply it to SHA-1. The  
resulting work factor is still quite high, hence we ask for  
contributions via the BOINC framework.


Is there any estimation of how high? Specifically, do you believe  
there is a good chance of having less work effort than the current  
Wang strategy?


Seriously, if we wouldn't be convinced that the new method is more  
efficient than anything else we know of and hence interesting enough  
to explore further, we wouldn't have started such a project. So yes,  
this is much faster than Wang's published method, and based on all we  
know also faster than what is estimated for Wang's latest unpublished  
methods.


Exact comparison is a complicated and delicate issue, and I have to  
put you of to our upcoming paper on that issue. Your contribution of  
CPU cycles is of course very welcome.


More information on cryptanalytic details, type of collision, and  
resulting work factor will appear later this year.


That's good to hear. It would also be interesting if you could keep  
a running meter of approximately how much work you are getting from  
the participants. This isn't nearly as "sexy" as finding ETs or even  
protein folding...


We first plan to provide support for more platforms to increase the  
size of our potential user base, but next, some meaningful statistics  
are indeed on our todo-list.


-Christian
  (only sporadic access to mail this week)

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]

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

[Paul Hoffman]

At 11:31 PM +0200 8/14/07, Christian Rechberger wrote:
The mentioned article is indeed confusing, the information in there 
took apparently several hops.


Welcome to the world of public cryptography! :-) At least I haven't 
seen anyone so far suggest that you will find pre-images.


To address your questions: Indeed, we have our own "path", but more 
importantly we developed a new method to speed-up generation and 
testing of candidate message pairs and apply it to SHA-1. The 
resulting work factor is still quite high, hence we ask for 
contributions via the BOINC framework.


Is there any estimation of how high? Specifically, do you believe 
there is a good chance of having less work effort than the current 
Wang strategy? For example, if you are sure that your result will be 
around 2^70, well that is interesting in theory but probably not 
worth any publicity you have gotten so far. If you are sure it will 
be around 2^55, I'll certainly give you some of my spare CPU cycles.


More information on cryptanalytic details, type of collision, and 
resulting work factor will appear later this year.


That's good to hear. It would also be interesting if you could keep a 
running meter of approximately how much work you are getting from the 
participants. This isn't nearly as "sexy" as finding ETs or even 
protein folding...


--Paul Hoffman, Director
--VPN Consortium

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]

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

[Christian Rechberger]

Quoting Paul Hoffman <[EMAIL PROTECTED]>:


At 11:00 PM -0700 8/13/07, Aram Perez wrote:

Anyone know more about this?


I have the same question. I could not find any description of *why*  
they think that finding near-misses is going to help the research.  
It's not clear if they are taking their own path, or trying to  
improve Wang's path, or what.


The mentioned article is indeed confusing, the information in there  
took apparently several hops.


To address your questions: Indeed, we have our own "path", but more  
importantly we developed a new method to speed-up generation and  
testing of candidate message pairs and apply it to SHA-1. The  
resulting work factor is still quite high, hence we ask for  
contributions via the BOINC framework.


More information on cryptanalytic details, type of collision, and  
resulting work factor will appear later this year.


-Christian


-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]

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

[Paul Hoffman]

At 4:49 PM -0300 8/14/07, Mads Rasmussen wrote:

Have a look at

http://boinc.iaik.tugraz.at/sha1_coll_search


Did that, in specific 



Note the lack of information about what they are actually doing. "We 
developed new cryptanalytic methods..." sounds great, but is 
meaningless without specifics.


--Paul Hoffman, Director
--VPN Consortium

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]

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

[Mads Rasmussen]

Have a look at

http://boinc.iaik.tugraz.at/sha1_coll_search

Aram Perez wrote:

Anyone know more about this?


--
Mads Rasmussen
LEA - Laboratório de Ensaios e Auditoria
ICP-Brasil   
(Brazilian PKI Cryptographic Certification Laboratory)

Office: +55 11 4208 3873
Mobile: +55 11 9407 4493
Mobile: +55 11 9655 8885
Skype: mads_work
http://www.lea.gov.br

   


-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]

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

[Paul Hoffman]

At 11:00 PM -0700 8/13/07, Aram Perez wrote:

Anyone know more about this?


I have the same question. I could not find any description of *why* 
they think that finding near-misses is going to help the research. 
It's not clear if they are taking their own path, or trying to 
improve Wang's path, or what.


--Paul Hoffman, Director
--VPN Consortium

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]

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: [EMAIL PROTECTED]
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
  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.


   

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   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
  a distributed  
computing
project. The trusty old Boinc   client  
known
from other such projects such as [EMAIL PROTECTED] 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
  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 [EMAIL PROTECTED]