
Author 
Message 
anon_private... 
Posted: Mon Oct 18, 2010 4:49 pm 



Hi,
Regarding SHA attacks what does:
complexity 261 mean?
complexity 251 mean?
complexity 240 mean?
Any primer refs welcome.
Thanks
A


Back to top 

Greg Rose... 
Posted: Mon Oct 18, 2010 7:17 pm 



In article <8b8c825b8440445db383f53b9043e71f at (no spam) a37g2000yqi.googlegroups.com>,
anon_private <not_here.5.species8350 at (no spam) xoxy.net> wrote:
[quote]Hi,
Regarding SHA attacks what does:
complexity 261 mean?
complexity 251 mean?
complexity 240 mean?
[/quote]
I *think* that something has gone wrong with
formatting somewhere, and that "261" is really "2
to the power 61". If I am correct, that means
that the amount of computational work required to
do whatever (which I think is finding a collision
in SHA1) is equivalent to running the compression
function of SHA1 about 2 to the power 61 times.
Greg.



Back to top 

Joseph Ashwood... 
Posted: Tue Oct 19, 2010 12:24 am 



"anon_private" <not_here.5.species8350 at (no spam) xoxy.net> wrote in message
news:8b8c825b8440445db383f53b9043e71f at (no spam) a37g2000yqi.googlegroups.com...
[quote]Hi,
Regarding SHA attacks what does:
complexity 261 mean?
complexity 251 mean?
complexity 240 mean?
Any primer refs welcome.
[/quote]
Just seconding the statement by Greg Rose. It is almost certain that it is 2
to the 61st power. Normally we write this using ^ to represent
exponentiation. 2^61 means that it would require roughly
2,000,000,000,000,000,000 operations. 2^51 would be 2,000,000,000,000,000
(three fewer digits). 2^40 is 1,099,511,627,776 (three fewer digits again).
While these numbers seem large, its important to realize that it takes
Intel's high spec cpus (8 cores at 3.06GHz) slightly less than 45 seconds to
reach 2^40 potential operations, so 2^40 is not a big number.
The convention of using base 2 exponentiation is a matter of most of the
computation being performed on computers, so everything ends up base 2
anyway.
Joe


Back to top 

Francois Grieu... 
Posted: Tue Oct 19, 2010 2:37 am 



On 19/10/2010 04:49, anon_private wrote:
[quote]Regarding SHA attacks what does:
complexity 261 mean?
complexity 251 mean?
complexity 240 mean?
[/quote]
I share the general opinion here that what is
meant is: the cost of finding two differents
messages with the same hash can be made similar
to about 2^61 (or 2^51, 2^40) calculations of
hashes of small messages. The numbers coincide
well with the best known collision attacks at
some point in time against the hash initialy
known as SHA, now withdrawn and refered to as
SHA0.
[quote]Any primer refs welcome.
[/quote]
Try the HAC, Chapter 9
http://www.cacr.math.uwaterloo.ca/hac/
Francois Grieu


Back to top 

anon_private... 
Posted: Wed Oct 20, 2010 1:53 am 



On Oct 19, 9:37 am, Francois Grieu <fgr... at (no spam) gmail.com> wrote:
[quote]On 19/10/2010 04:49, anon_private wrote:
Regarding SHA attacks what does:
complexity 261 mean?
complexity 251 mean?
complexity 240 mean?
I share the general opinion here that what is
meant is: the cost of finding two differents
messages with the same hash can be made similar
to about 2^61 (or 2^51, 2^40) calculations of
hashes of small messages. The numbers coincide
well with the best known collision attacks at
some point in time against the hash initialy
known as SHA, now withdrawn and refered to as
SHA0.
Any primer refs welcome.
Try the HAC, Chapter 9http://www.cacr.math.uwaterloo.ca/hac/
Francois Grieu
[/quote]
Thanks to all for helping me with my reading. As is obvious, I am new
to this subject.
I was surprised by Josephs information regarding the speed of some of
the processors. Evidently, the Venus CPU is about 45 times faster than
the high spec cpus. With these speeds I am surpised that the hashe's
are so secure.
Best wishes.
A


Back to top 

Joseph Ashwood... 
Posted: Wed Oct 20, 2010 8:42 pm 



"anon_private" <not_here.5.species8350 at (no spam) xoxy.net> wrote in message
news:f33ed9869d8b479095a8e08511b5814c at (no spam) c10g2000yqh.googlegroups.com...
[quote]I was surprised by Josephs information regarding the speed of some of
the processors. Evidently, the Venus CPU is about 45 times faster than
the high spec cpus.
[/quote]
It is important to remember that Venus is a 128 GFLOP cpu, it's a very
complex situation but a FLOP is not necessarily an operation, and very often
floating point operations (FLOP) are not applicable to cryptography,
complicating things further. COmplicating matters more Venus is not only 8
cores, but also a VLIW system, so a single "instruction" can be multiple
instructions, however most of the time only one of those instructions is
actually active. That's why I ignored such systems and the complexities of
the math. I can't quickly locate a clock speed for Venus, but it is an 8
core design, so multiply the clock speed by 8 and you'll get an
approximation. These are just quick approximations, in truth each algorithm
operation is multiple cpu instructions, so the 2^40 work to break SHA1
would likely take a few minutes.
[quote]With these speeds I am surpised that the hashe's
are so secure.
[/quote]
Don't be, SHA and SHA1 are considered insecure because of the attacks. The
power of exponents takes over at higher complexities. Lets assume that 2^40
work can be done in 1 second. 2^41 would take 2 seconds, 2^42 = 4 seconds.
2^64 = 194 days. 2^80 = over 34000 years. 2^128 = several million universe
lifetimes. 2^80 is considered the minimum for security, and it is argued
that 2^128 is needed.
In terms of absolute limits. If you consider the estimated mass of the
universe, the number of atoms this represents, and various of constants, the
universe only has the possibility to perform about 2^330 operations, so that
is an approximate upper limit for classical computations.
Joe


Back to top 

WTShaw... 
Posted: Fri Oct 22, 2010 11:34 am 



On Oct 20, 9:42 pm, "Joseph Ashwood" <ashw... at (no spam) msn.com> wrote:
[quote]
In terms of absolute limits. If you consider the estimated mass of the
universe, the number of atoms this represents, and various of constants, the
universe only has the possibility to perform about 2^330 operations, so that
is an approximate upper limit for classical computations.
Joe
[/quote]
But, operations need not be classic, or linear as is the common
prejudice; Long Live Einstein, Asimov, Gamow, et al!


Back to top 


All times are GMT  5 Hours
The time now is Sun Apr 20, 2014 1:39 pm

