SHA1 reported broken

ecksor

http://www.schneier.com/blog/archives/2005/02/sha1_broken.html

Sounds like a pretty sore one although the full implications of it will require a bit of thought.

tck

those chinese strike again

test999

ecksor, thanks for the link.

Martyr

I'd say its still pretty secure unless someone were hiding something from the government.

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...

you might want to check this out too (for those interested)
its about near collisions in sha-0,sha-1

http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-get.cgi/2004/CS/CS-2004-09.ps

test999

Err, no, SHA-1 is officially phooked.

'Step away from the broken (in)secure hash algorithm now please...'
nuthin to see here folks....

I'm recommending anyone who uses it, should use SHA-256 or 512 instead.

apart from Bruce Schneier's site, has it been confirmed by others? (and I don't mean El Reg)

ecksor

Can you post your line of reasoning for saying that nobody should use it at all?

hmmm

"Broken" is probably a bit harsh. It is showing signs of weakness which cannot be exploited in any realistic sense now, but may in the future. Best to move to a better hash algorithm, but no need to run for the exit if you are currently using it.

nagero

hmmm wrote:

"Broken" is probably a bit harsh. It is showing signs of weakness which cannot be exploited in any realistic sense now, but may in the future. Best to move to a better hash algorithm, but no need to run for the exit if you are currently using it.

Plans to move up were underway before this announcement.

Hashing out encryption

It also takes time for implementations of SHA 256-512 to become widespread and to be included in all the relevant standards/RFCs.

nagero

ecksor

hmmm wrote:

"Broken" is probably a bit harsh.

It is accurate in this context I believe. If you demonstrate any cryptographic algorithm to provide less practical security than it advertises then is deemed to have been broken. The question of whether or not it still remains practical for use in various applications is a separate question.

test999

ecksor wrote:

Can you post your line of reasoning for saying that nobody should use it at all?

If you are planning on using SHA-1, I would recommend you don't use it.
If you are currently using SHA-1, I would recommend you move away from it.

If you were, e.g. working in a finance environment, and about to roll out a corporate security policy; specifying the use of SHA-1, would be a bad idea.

scojones

It's not a big deal, it's still pretty safe, but yeah I wouldn't use it now. It's not as if it was destroyed like WEP or anything. You'd still need a crud load of processing power to be able to do anything. Very interesting development... If you're using it for passwords you're fine.

ecksor

test999 wrote:

If you are planning on using SHA-1, I would recommend you don't use it.
If you are currently using SHA-1, I would recommend you move away from it.

If you were, e.g. working in a finance environment, and about to roll out a corporate security policy; specifying the use of SHA-1, would be a bad idea.

That is not what I asked you. The attack that has been found isn't even relevant to all applications of SHA1.

My question is how you have reached the conclusion that you have. Is it just based on the fact that any attack is bad news or have you done or got access to a more detailed analysis?

Capt'n Midnight

flink in first post wrote:

* 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.

* collisions in SHA-0 in 2**39 operations.

* collisions in 58-round SHA-1 in 2**33 operations.

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).

So, how long would it take to do 2**69 ops?
2**37 seconds of CPU time. About 4000 years.
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...

[edit - image too big]
http://www.corestore.org/cm200.htm - an OLD connection machine, the point here is that each cube contains up to 8096 processors. I'd be fairly sure our friends down at the NSA have several very large rooms full of these, for when they aren't using the rooms across the corridor that house the multi-exabyte arrays of look up tables.

Anyone know if you can perform multiple searchs at the same time. Do you need to do a seperate search for each message or can you just compare your list of intercepts with you list of hashes as you calculate them ?

test999

ecksor wrote:

That is not what I asked you. The attack that has been found isn't even relevant to all applications of SHA1.

My question is how you have reached the conclusion that you have. Is it just based on the fact that any attack is bad news or have you done or got access to a more detailed analysis?

Explain what applications of SHA-1 you are referring to.

I was speaking of digital signatures.

If you are signing a document, and that dsig is called into question in court in a years time, ten years time, it's likely the possibility of a duplicate signature will call the validity of the signature into doubt. Non-repudiation is virtually impossible to enforce now, without having to deal with the implications of having used a hash function in the future.

If what you have signed has value, expect it to be attacked.

The NIST's intention to move away from 80bits of security by 2010 has significance. NIST chose 2010 based upon the computational infeasibility of the work factor associated with SHA-1 before wing-wang and ding-dong from China and Princeton made their discoveries.

ecksor

test999 wrote:

Explain what applications of SHA-1 you are referring to.

Well, HMAC for one, as is mentioned in the link I posted above.

I was speaking of digital signatures.

Ok, I don't see how this affects digital signatures (where I assume you mean SHA1 being used as the primitive for generating a HMAC).

EDIT: Schneier's actual comment also mentions that it puts a bullet into its use with digital signatures so there's probably something I'm missing here. I'm probably mixing up HMAC and digital signatures again.

If you are signing a document, and that dsig is called into question in court in a years time, ten years time, it's likely the possibility of a duplicate signature will call the validity of the signature into doubt.

I don't think anybody has suggested that cooking a plausible looking alternative document that will match the same signature is a realistic implication of this development if that is what you mean (besides, there's more to trying to forge a digital signature than merely beating the hash). Can you describe what sort of attack you're talking about here?

This seems more likely to cut down the workload in attacks such as password cracking.

Non-repudiation is virtually impossible to enforce now, without having to deal with the implications of having used a hash function in the future.

I don't know what point you're making here.

ecksor

test999 wrote:

If you were, e.g. working in a finance environment, and about to roll out a corporate security policy; specifying the use of SHA-1, would be a bad idea.

This is pedantic of me and you probably just typoed, but it can easily happen and can be a genuine problem if it does so I'm going to mention it anyway ...

Specifying any specific technology or algorithm within a policy is a bad idea as policies tend to be difficult to change without a lot of rigamarole. Make the policy an unambiguous but high-level statement of a company's principles and intent that management agrees and signs off and leave the more prescriptive items such as specific technologies to a supporting procedures document that is more easily updateable and under the control of those who's job it is to know what changes should be made to it based on new technical developments and changes to the business.

tck

Capt'n Midnight wrote:

flink in first post wrote:

* 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.

* collisions in SHA-0 in 2**39 operations.

* collisions in 58-round SHA-1 in 2**33 operations.

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).

[edit - image too big]
http://www.corestore.org/cm200.htm - an OLD connection machine, the point here is that each cube contains up to 8096 processors. I'd be fairly sure our friends down at the NSA have several very large rooms full of these, for when they aren't using the rooms across the corridor that house the multi-exabyte arrays of look up tables.

Anyone know if you can perform multiple searchs at the same time. Do you need to do a seperate search for each message or can you just compare your list of intercepts with you list of hashes as you calculate them ?

NSA is the biggest purchaser of computer hardware in the world.
Also half the cray supercomputers sold in the world, are well you guessed it, humming away at their premises.

now thats some serious cpu cycles.

Martyr

test999 wrote:

Err, no, SHA-1 is officially phooked.

'Step away from the broken (in)secure hash algorithm now please...'
nuthin to see here folks....

I'm recommending anyone who uses it, should use SHA-256 or 512 instead.

apart from Bruce Schneier's site, has it been confirmed by others? (and I don't mean El Reg)

I'm no expert on cryptography, and i'm not questioning your authority
on the subject.
All i'm saying is how practical are the attacks against SHA-0/SHA-1
for the average person on the street?
Like i said, unless you want to hide something from a foreign government,
why worry about it?

And if its from the NSA, then using SHA-256/SHA-512 is irrelevant.

Why would such an organisation like the NSA be interested in cracking your digital signatures in the first place anyway?

What have you got to hide that is so important?

I just don't think that they would care all that much about what you purchase on ebay or how much you have in your bank account.

Capt'n Midnight

Average Joe wrote:

What have you got to hide that is so important?

the fact that you are hiding something means you have something to hide

again does anyone know if they can build lookup tables or if the results of one search can be used to crack more than one key at a time, because if so then it would take about the same length of time to break every combination as would just a single one...

ecksor

I think the confusion is (and I know it was my confusion in my last post on this thread until I went poking around sci.crypt) that this doesn't help a person to find a pre-image for any arbitrary hash (as in, if you find a hash value, this work isn't concerned with the problem of finding an input that will produce that hash value), it's to do with cooking up two separate inputs simultaneously that will produce the same hash value.

So, if you get a document or a binary that has been certified with a digital signature then the problem is that now it appears more likely that someone could produce two versions (say properly working binary and a trojan horse) that will hash to the same value. This would also be consistent with the mention of non-repudiation above in relation to documents or transactions.

How practical is it to discover a collision that just happens to involve two meaningful inputs? Not very I'd imagine, but then I may be mistaken.

ecksor

Capt'n Midnight wrote:

the fact that you are hiding something means you have something to hide

Well, the work factor involved in breaking something is important in figuring out whether or not it is a practical attack, which is a valuable way of working out whether or not a certain technology is suitable for a given application with a given threat model.

That is why I asked for the reasoning from test999. If you want to just take this development as evidence that the cracks in SHA1 are showing and we don't know how much more broken it will be proved to be in the near future and it's a good idea to drop it on that basis, then I would see the point to that logic where there's a choice, but I just wanted to see if there was something that I was missing that may apply to situations where there may be good reason to stick with SHA1.