×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

SHA-1 Broken

timothy posted more than 9 years ago | from the sha-na-na dept.

Encryption 751

Nanolith writes "From Bruce Schneier's weblog: '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 announcing their results...'" Note, though, that Schneier also writes "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."

cancel ×
This is a preview of your comment

No Comment Title Entered

Anonymous Coward 1 minute ago

No Comment Entered

751 comments

Sigh (5, Funny)

Anonymous Coward | more than 9 years ago | (#11685458)

And I just got done upgrading from MD5.

Re:Sigh (4, Funny)

dasunt (249686) | more than 9 years ago | (#11685544)

About a month ago, I needed a mechanism for password hashes.

After some research, I decided that SHA1 was more secure than MD5.

So I hunted down some good public domain SHA1 code, read through it, and added it to my code.

Thanks /.!

Re:Sigh (2, Insightful)

ottothecow (600101) | more than 9 years ago | (#11685578)

Well, without /. they would be quietly circulating a paper on how to break your hashes and it would still be quiet.

Maybe its easier to upgrade from SHA1 than it was from MD5.

Re:Sigh (2)

mlyle (148697) | more than 9 years ago | (#11685673)

A mechanism to find collisions does not affect SHA-1's strength as a password hashing algorithm or its use in a hashed message authentication code. So you'll be just fine.

Broken or not? (-1, Troll)

AddressException (187785) | more than 9 years ago | (#11685461)

At this point I can't tell if the attack is real

Is this news?

Info on what exactly SHA-1 is ... (5, Informative)

Hulkster (722642) | more than 9 years ago | (#11685462)

For those interested, here is the actual detailed/lengthy FIPS PUB 180-1 from NIST, [nist.gov] as typical, Wikipedia has a nice summary, [wikipedia.org] and the W3 Folks [w3.org] have a short snippet ...

Re:Info on what exactly SHA-1 is ... (5, Interesting)

interiot (50685) | more than 9 years ago | (#11685541)

So SHA-1 was created by the NSA, and was broken nine years after it was released. Is there any chance that the NSA knew it had a secret weakness, and promoted it for that specific reason?

Re:Info on what exactly SHA-1 is ... (0)

Anonymous Coward | more than 9 years ago | (#11685563)

The NSA has a history of making suggestions to prevent early weaknesses. They probably estimated it would be good for a decade.

Re:Info on what exactly SHA-1 is ... (2, Insightful)

digitalchinky (650880) | more than 9 years ago | (#11685651)

In realistic terms, would you have predicted such rapid advancement in computer processing power over the last 9 years? Ok, so maybe the answer to that question is yes, but encryption schemes are not specifically meant to protect things forever, just the length of time that the information contained could be damaging in the 'wrong hands'

Any encryption scheme that lasts about 10 years has given a pretty good service I would think.

woot! (-1, Offtopic)

Anonymous Coward | more than 9 years ago | (#11685464)

Woohoo!

Hmm (0, Redundant)

Jicksta (760596) | more than 9 years ago | (#11685466)

So... anyone care to explain exactly what SHA-1 is?

Re:Hmm (2, Insightful)

metlin (258108) | more than 9 years ago | (#11685517)

It's a hashing algorithm - SHA stands for Secure Hashing Algorithm.

Is it so hard to look it up? [wikipedia.org]

Re:Hmm (2, Funny)

Anonymous Coward | more than 9 years ago | (#11685603)

Ya.. 20 years ago we used a hashing algorithm at college. Not sure how secure it was but we got really messed up.

Re:Hmm (2, Informative)

defile (1059) | more than 9 years ago | (#11685552)

If your system has an md5sum command, it will also have a sha1sum command. Same idea, different output: feed each of them a file and they will give you a hash of that file that fits in 128-bits (md5) or 160-bits (sha1).

In practice, no two files (or period of a data stream) will have the same signature. Hashing algorithms are used in data integrity checks and authentication.

An sha1 crack likely means that they found a way to make tampered data still hash to a desired value, maybe.

sha1 and md5 are generally considered so weak that they should only be used to combat error or accidents, not fraud.

Re:Hmm (1, Interesting)

Anonymous Coward | more than 9 years ago | (#11685649)

> sha1 and md5 are generally considered so weak that they should only be used to combat error or accidents, not fraud

No. At least, until very recently, SHA-1 was considered a serious cryptographic hash function, well suited for digital signatures and such.

Maybe you're mixing them with CRC-32, which is indeed well suited to combat transmission errors, but not intentional foul-plays.

Re:Hmm (1)

MindStalker (22827) | more than 9 years ago | (#11685653)

sha1 and md5 are generally considered so weak that they should only be used to combat error or accidents, not fraud.

Not untill resently they wern't.

Btw anyone know what hash GPG uses for signing?

Re:Hmm (0)

Anonymous Coward | more than 9 years ago | (#11685669)

In practice, no two files (or period of a data stream) will have the same signature. Hashing algorithms are used in data integrity checks and authentication.
I think you mean in theory, not in practice. In theory, theory and practice are the same, but in practice they're different.

Re:Hmm (1, Insightful)

Anonymous Coward | more than 9 years ago | (#11685558)

So... anyone care to explain exactly what SHA-1 is?

Sure. SHA-1 is something you could and should look up, thereby gaining an answer more quickly, and not wasting the time of others in a techinical forum.

Next week: How to find the number for 911.

Re:Hmm (0, Troll)

Donny Smith (567043) | more than 9 years ago | (#11685559)

> So... anyone care to explain exactly what SHA-1 is?

So... Anyone care to mark the fucking string, right click SHA-1 and choose Search the Web for "SHA-1"?
How hard is that?

Re:Hey (2, Funny)

Anonymous Coward | more than 9 years ago | (#11685628)

oops I accidentally highlighted 'fucking' from your post instead and searched for that

I am outraged! Does this disgusting thing called 'fucking' really happen ? I must know.

first post (-1, Offtopic)

Anonymous Coward | more than 9 years ago | (#11685470)

la la la

OHNO! (0)

Anonymous Coward | more than 9 years ago | (#11685472)

the world is ending!

f1r5t p00st (-1, Offtopic)

Anonymous Coward | more than 9 years ago | (#11685474)

wooooooooooo f1r5t p00st

Well (1, Insightful)

metlin (258108) | more than 9 years ago | (#11685480)

Had to happen, didn't it?

No algorithm is all-powerful - it only withstands attacks for so long.

The strength of the algorithm lies in how long it can stand up - to attacks and to future technologies.

Yeah... (0)

game kid (805301) | more than 9 years ago | (#11685571)

The hashing is done by mathematic operations, so I'm sure something like SHA can be "cracked" almost (almost because they're just hashes and not full files) like solving an equation, right?

Re:Yeah... (5, Informative)

Ctrl-Z (28806) | more than 9 years ago | (#11685650)

Well, no. Not exactly. SHA-1 is supposed to be a one-way function, meaning that you can't just reverse the operation. So you can't just "crack" it like solving an equation.

I'm not sure if you are talking about retrieving the original file from the hash, but if you are, then you don't understand what hash functions are for. In this case, there are an infinite number of combinations of bytes that have the same SHA-1 hash. The goal is to find one that has the same hash value, regardless of whether it is actually the same file. SHA-1 is not a cipher.

Obligatory Gentoo reference (1, Troll)

bonch (38532) | more than 9 years ago | (#11685598)

I just finished compiling it an hour ago, and then I see this announcement on Slashdot! This always happens.

Re:Well (2, Interesting)

FireballX301 (766274) | more than 9 years ago | (#11685619)

Of course they're not supposed to be all-powerful, but considering details as to how exactly the algorithm is broken are not available, I'm quite interested as to how they broke it.

I'm particularly worried about BT users, personally. The breaking of SHA-1 will essentially allow the RIAA and others to corrupt many bittorrent downloads.

Re:Well (0)

Anonymous Coward | more than 9 years ago | (#11685622)

No algorithm is all-powerful - it only withstands attacks for so long.

Er, would you care to prove this?

Start recoding (0)

Anonymous Coward | more than 9 years ago | (#11685491)

I've now got to go recode many many applications. We've been scrooged folks! My comment starts with Oh and ends with a word very similar to fsck.

But I still won't believe it till Netcraft confirms it!

Prison. (5, Funny)

Seumas (6865) | more than 9 years ago | (#11685496)

A lot of companies and products use SHA1 in some form or another. Does this mean that we can arrest and imprison these "researchers" if they ever step foot in America?

Re:Prison. (0)

Anonymous Coward | more than 9 years ago | (#11685579)

I am not sure how this goes...

Welcome to planet Earth.

We speak English as you do, but I think you are talking about the Universe YOU come from....

Time to switch.... (4, Funny)

Anonymous Coward | more than 9 years ago | (#11685498)

... to SHA-2!

Re:Time to switch.... (3, Informative)

metlin (258108) | more than 9 years ago | (#11685530)

Which *one* of SHA-2?

FYI, SHA-224, SHA-256, SHA-384, and SHA-512 are all referred to as SHA-2.

Re:Time to switch.... (3, Informative)

prockcore (543967) | more than 9 years ago | (#11685626)


FYI, SHA-224, SHA-256, SHA-384, and SHA-512 are all referred to as SHA-2.


Doesn't matter. The only difference is key length. The algorithm is the same.

Re:Time to switch.... (0)

Anonymous Coward | more than 9 years ago | (#11685660)

Ron Richardson: Yeah? Are you gonna make it all 220?

Jack Butler: Yeah. 220... 221, whatever it takes.


-- Mr. Mom [imdb.com]

Time to start a panic (4, Funny)

psetzer (714543) | more than 9 years ago | (#11685500)

If you don't switch to the newest, latest hashing algorithm, you will die horribly when your corrupted emacs RPM performs malicious code!!! Everyone, delete everything and log off of the Internets now!!! We're all gonna die!!! HELP!!!

I heard... (1)

game kid (805301) | more than 9 years ago | (#11685610)

there's rumors on the uh, Internets that we're going to get owned with this SHA1 thingy. (Forgive me, I'm from the Bronx [cnn.com] .)

yah right! (-1, Troll)

Anonymous Coward | more than 9 years ago | (#11685501)

And cold fusion has been discovered too!

Slashdot... All the "news" thats not fit to print, or even copy and paste like a good little editor... er I mean janitor!

P.S. Anybody else laugh at the way "Roblimo" (???) referred to himself as a "journalist" in the interview with the Microsoft guy)?

Brought to You By (5, Informative)

z0ink (572154) | more than 9 years ago | (#11685504)

Same group of people that found the MD5 Hash Collision. Self [slashdot.org] references [slashdot.org] and the MD5 paper [iacr.org] .

Question (1, Interesting)

Anonymous Coward | more than 9 years ago | (#11685535)

Why is it they found a hash collision in, but could not break, MD5; but have apparently broken SHA-1? This could just be due to a quirk of the respective algorithms, but it could also mean that the nature of their SHA-1 paper purported by the weblogs is mistaken.

May be a big deal... (2, Interesting)

ThisNukes4u (752508) | more than 9 years ago | (#11685505)

This may be a big deal, because if I understand correctly, SHA-1 is a similiar algorithm to MD5, which is commonly used to uniquely identify files. If that could be cracked using a similiar technique, a better method of hashing files may have to be found.

Re:May be a big deal... (1)

BobSutan (467781) | more than 9 years ago | (#11685585)

The short short version of what a hash does is you take a file, an email for example, and you create a hash value from it. Then you send the email and the hash to a recipient. That person then does the same thing. If the hash values are the same then the person who recieved the email knows it wasn't doctored or messed with en route, hence proving that it's integrity is sound (in theory).

Re:May be a big deal... (0)

Anonymous Coward | more than 9 years ago | (#11685641)

Then you send the email and the hash to a recipient. That person then does the same thing. If the hash values are the same then the person who recieved the email knows it wasn't doctored or messed with en route, hence proving that it's integrity is sound (in theory).

Make sure you send the email and the hash via different channels. Otherwise you are relying on the interloper being dumb enough to change the email without updating the hash as well.

What a hash is/does (3, Informative)

cbr2702 (750255) | more than 9 years ago | (#11685662)

No, that would be one application of a hash (and not a very good one, because someone wanting to mess with it enroute could just re-hash the doctored version and pass on the new hash. What you discribe could be a way to check for accidental errors, though.). A hash is a function that given data gives a smaller amount of data. This smaller amount of data is then also called the hash of the origonal data. A good hash function has the property that if you know the hash for a file, you shouldn't be able to come up with another file that has the same hash without a prohibitive amount of work. A hash function is broken if this property stops holding.

Re:May be a big deal... (2, Informative)

Ctrl-Z (28806) | more than 9 years ago | (#11685680)

Actually, that wouldn't really work in practice. What would stop someone from intercepting it and changing the message and the hash before your receive it?

I think what you are thinking of is a digital signature system, where the document is hashed and then the hash is signed. Any tampering would invalidate the signature. The hash is used because it takes a lot of random data to encrypt an arbitrary file, while it takes quite a bit less to encrypt a short, fixed-length hash like SHA-1. Since (in theory), the probability of message collision is quite low, the hash is (practically) as good as the real thing for signing.

Damn it (2, Funny)

afidel (530433) | more than 9 years ago | (#11685508)

/me
Log into VPN Firewall
Check VPN settings
Notices SHA for authentication type
Swears
Checks other option, notices {none} and {md5}
scratches head
decides to go with MD5 until that too is broken /me wishes security were easier

Re:Damn it (0)

Anonymous Coward | more than 9 years ago | (#11685537)

MD5 is also broken.

Although Bruce sez it's not an issue for HMAC applications, which would be the case w/ your firewall.

Re:Damn it (1)

DAldredge (2353) | more than 9 years ago | (#11685550)

Please tell me you are joking and didn't change your security policies with out know which is better.

BTW, this same research group published a paper about 'breaking' md5 some months back :)

Now what do we use? (2, Interesting)

enos (627034) | more than 9 years ago | (#11685509)

With SHA-1 being MD5's replacement after that was broken, which hash function do we use now?

Re:Now what do we use? (1, Interesting)

Anonymous Coward | more than 9 years ago | (#11685556)

Run data through SHA-1, then MD5, then XOR.

Re:Now what do we use? (5, Informative)

jd (1658) | more than 9 years ago | (#11685595)

Whirlpool has the same hash length as SHA-256 and is based on the Rijndael encryption function, which is currently believed "safe enough". As such, I'm going to say that that is the best bet right now.


The Hashing Function Lounge [terra.com.br] also lists Cellhash, Parallel FFT-Hash , RIPEMD-128, RIPEMD-160, Subhash and Tiger as (so far) unbroken.

Re:Now what do we use? (3, Informative)

Ant2 (252143) | more than 9 years ago | (#11685639)

Well, for starters, there's:
SHA-256
SHA-384
SHA-512

The numbers refer to the bit length of the generated hash. SHA-1 uses only a 160 bit length, called a message digest. But then, you'd know all that if you would have rtfa.

--I wish there was some way to automatically append a line of text to messages posted on slashdot.

And they scoffed at my continued reliance on MD5! (0)

js7a (579872) | more than 9 years ago | (#11685514)

Another reason to avoid IPsec and WEP.

Re:And they scoffed at my continued reliance on MD (3, Informative)

Anonymous Coward | more than 9 years ago | (#11685614)

Doest not affect HMAC. So it does not affect IPSEC and WEP.

RTFA.

Re:And they scoffed at my continued reliance on MD (0)

Anonymous Coward | more than 9 years ago | (#11685638)

md5 has already been broken.

Re:And they scoffed at my continued reliance on MD (1)

elmegil (12001) | more than 9 years ago | (#11685663)

It's not like MD5 is Any Better [slashdot.org]

Re:And they scoffed at my continued reliance on MD (3, Insightful)

js7a (579872) | more than 9 years ago | (#11685681)

Finding a single collision after a huge search isn't the same as being able to generate a collision on demand, which is what the SHA-1 breakage apparently purports to be.

Xbox-Linux Project B Complete? (0)

Anonymous Coward | more than 9 years ago | (#11685520)

Is there a self-boot disc on non-modded xbox's in our near furture?

http://www.xbox-linux.org/docs/projectboverview. ht ml

I won't believe it (0)

Anonymous Coward | more than 9 years ago | (#11685524)

Until Netcraft confirms it.

what's left (2, Interesting)

Yonkeltron (720465) | more than 9 years ago | (#11685529)

wait a sec....no MD5 and no SHA-1. what is going to take the place of those things? something like anubis or whirlpool?

maybe more people will use GPG now!

Re:what's left (2, Funny)

mboverload (657893) | more than 9 years ago | (#11685546)

Everyone should just randomly hit keys on their keyboard for each file. Totally random, but most files with be "sfkhadou"

Re:what's left (0)

Anonymous Coward | more than 9 years ago | (#11685674)

Everyone should just randomly hit keys on their keyboard for each file.

Isn't that the standard technique for generating /. posts?

So What? (2, Funny)

cr0y (670718) | more than 9 years ago | (#11685561)

Long live ROT-13.

Maybe crackers would stop messing with our encryption if it was extremely easy to deal with.

SupahLeetCodah: d00d i just cracked SHA-1 and MD5,6 AND 7!!!1

Steve: So did my grandma and my proctologist.

While her husband says... (1)

game kid (805301) | more than 9 years ago | (#11685657)

Eshcuse me shonny, d'you know where I can find shome booty^H^H^H^H^Hshource code?

Bittorrent? (4, Interesting)

oman_ (147713) | more than 9 years ago | (#11685562)

Is it time to update bittorrent?
How hard is it going to be for people to provide garbage data with correct SHA-1 hashes to screw up downloads?

Let me be the first to say... (0)

Just Some Guy (3352) | more than 9 years ago | (#11685596)

...oh, shit. This is so seriously beyond Not Good that it's not funny. SHA-1 is used for all sorts of things, many of which critically depend on it as the background of their security.

We (possibly? probably?) can't trust MD5 anymore, and now SHA-1 might have fallen. Does anyone know whether their exploits are overlapping? If not, can we reasonably move to H(x)=MD5(SHA-1(x))? Are there any other good hash algorithms working their way through the pipeline?

Broken, but not for everything... (4, Insightful)

JM (18663) | more than 9 years ago | (#11685599)

One collision in 2**69 operations... that's quite minimal...

Sure, for signatures, it means that you can't trust the algorithm 100% anymore.

But for storing passwords, and other operations where collisions are not important, it doesn't matter much, even if there's another password that can generate the same hash, you still need to brute-force it.

Re:Broken, but not for everything... (4, Insightful)

beaststwo (806402) | more than 9 years ago | (#11685676)

You never could trust it 100%! That was the idea! The algorithm gives you a very high probability of authenticity, not any kind of guarantee (unless the original message is shorter than the output of the hash and everyone who hashes it later absolutely knows the length of the original message).

It's an assurance, that's all. The only guarantee is a one-time pad, and Bruce Schneier's website is full of info on why these aren't practical!

End of the world (0)

Anonymous Coward | more than 9 years ago | (#11685601)

It's the end of the world as we know it...I can already feel the foundations of civilisation crumbling beneath me.

So what's the big deal for the rest of us? (5, Interesting)

beaststwo (806402) | more than 9 years ago | (#11685615)

I've been reading about hash collisions for the last few years and haven't figured out why this is a crisis problem.

I'm not a cryptographer, just a nerdy engineer, but let me explain my rationale: a hash algorithm takes an arbitrary message and generates a fixed-length signature that has a high probability (10**50 or better for most modern algorithms) of being the original.

Let's assume that your hash algorithm generates a 128-bit hash. Anyone who knows anything about probability can see that is the original message is greater than 128 bits, there MUST be more than one message that will generate the same hash. For long messages, there may be thousands or millions of messages out of a filed of 10**50 (or better) that have the same hash, although many of them will be meaningless garbage.

So SHA-1 has been broken by a group of cryptographers/mathematicians. Does this really mean that they can generate can alter any message in a way that will generate the same hash as the original, thus fooling the math that we use to validate content? No Way! I read Bruce Scheier's Cryptogram every month and he often makes the same argument.

So yes, this means that from a long-term systems security standpoint, we should all move to stronger hashes. Does it mean that SHA-1-based transactions are inherently secure right now?

I think not!

My Research team broke RSA! (1)

kevlar (13509) | more than 9 years ago | (#11685624)


The only problem is that I can't show you the paper or demonstrate it for you. OH yeah, I also have a lottery drawing app that'll give you the powerball numbers for Friday...

Meanwhile in Redmond (0, Flamebait)

Profane MuthaFucka (574406) | more than 9 years ago | (#11685630)

A marketing guy has a bright idea:

"Hey Bob, I was in the airport the other day and these two geeks were talking all about SHA-1. Said they read about it on Slashdot, and a Chinese research team was spending an awful lot of time working on it. We should definitely put this SHA-1, whatever it is, into the next release of our products. Send a memo to the development managers, and call our guy over at Gartner."

Impact on Digital Certificates & Issuer Liabil (2, Interesting)

Anonymous Coward | more than 9 years ago | (#11685636)

Is SHA-1 used in x509 digital certificates, and if so does this mean that people can forge digital certificates ?

If someone can do this, then what are the liability concerns for certificate issuers (or even their customers) ?

So the concern is..... (0)

Anonymous Coward | more than 9 years ago | (#11685656)

From what I understand, then, the concern is that attackers can craft a message that will hash to the same value, and then attempt to claim that the crafted message was signed by the signer in question, but in fact it was not.

Could someone please explain scenarios where a flaw, such as the one illustrated in this article, could be used to actually craft an attack. What would be a realistic scenario where one would need to be concerned with this flaw?

Unfortunately the SHA series seems to be suspect (5, Interesting)

jd (1658) | more than 9 years ago | (#11685659)

The Hashing Function Lounge [terra.com.br] lists other problems with the SHA functions:


  • (R04) V. Rijmen, "Update on SHA-1", accepted for CT-RSA'2005
  • P. Hawkes, M. Paddon, G. G. Rose, "On Corrective Patterns for the SHA-2 Family", Cryptology ePrint Archive, Report 2004/207 [iacr.org]


If this definite break is confirmed, I think we will need to conclude that the entire family is suspect for any genuinely important purpose.


There are a bunch of hashing algorithms on the Hashing Function Lounge that are listed as having no known attacks. At present, the most widespread is Whirlpool. I think it likely that one of these will replace SHA as the hashing function of choice in major cryptographic areas.

I Can See Bruce Now.... (3, Funny)

Alan Hicks (660661) | more than 9 years ago | (#11685683)

Bruce sits at his desk, reading over the encrypted e-mail sent to him about breaking SHA-1, when a loud scream echoes from his office

I JUST SENT OUT MY NEWSLETTER THIS MORNING!

Load More Comments
Slashdot Account

Need an Account?

Forgot your password?

Don't worry, we never post anything without your permission.

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>
Sign up for Slashdot Newsletters
Create a Slashdot Account

Loading...