SHA-0 Broken, MD5 Rumored Broken

An anonymous reader writes "Exciting advances in breaking hash functions this week at the CRYPTO conference. SHA-0 has definitely been broken (collision found in the full function). Rumors are that at the informal rump session, a researcher will announce a collision in full MD5 and RIPEMD-128. And Ed Felten is speculating about collisions in SHA-1! Many systems, especially those that use cryptography for digital signatures are most at risk here."

Comments

Okay that's it

[Anonymous Coward]

I picked the wrong week to quit sniffing MD5 hashes.

ec7b19b60e616fb1c6013d4ada83ec32

[Anonymous Coward]

d008960fa6b395dca1c8362165bb31be

Re:ec7b19b60e616fb1c6013d4ada83ec32

[idiot900]

d008960fa6b395dca1c8362165bb31be

You know you're a complete and utter nerd when you read this post, immediately understand it, and laugh out loud, as I just did :)

Re:ec7b19b60e616fb1c6013d4ada83ec32

[boots@work]

Is this a Google job ad? If so, 66b24eeeacbccd0baa0c582982f751ab.

Re:ec7b19b60e616fb1c6013d4ada83ec32

[Basehart]

No kidding. I looked at that and kracked up.

Re:ec7b19b60e616fb1c6013d4ada83ec32

[kghougaard]

As one of my friends responded a few days back, when a guy called him a nerd:

"No, no, it's called expert"

I now use that every single time...

Should We Fear?

[Anonymous Coward]

So what does this really mean for the average web surfer and computer user?

Re:Should We Fear?

[kendoka]

Your bank will buy enron stock with your accounts, your credit card will explode, and your mind will begin to melt. Nuclear missiles will spontaneously launch and direct themselves to your house. Bush will be exposed as a witless robot when he begins to utter swahili at a press conference. The Martians will arrive from their base on the dark side of the moon, and the War of the Worlds will begin. Super-Bowl half-time will be unceremoniously interrupted when terrorists will arrive to sear off Janet Jackson's nipple with a laser in the name of Allah.

Re:Should We Fear?

[Anonymous Coward]

Yes, but how does this affect me personally?

Re:Should We Fear?

[IchBinEinPenguin]

doesn't mean that much.

Carefully crrafted binary data can be made to have the same checksum.

This is not a generalised attack where I can create binary data to have a CHOSEN checksum.

Therefore, if you verify your downloads by checksum, I can't generate a fake download with the same checksum.

First step is MATCHING some checksums (this has been done)
The next step is CHOOSING the chekcsum (aka DEADBEEF attack)
The next step is MANIPULATING, i.e. adding junk to a given binary file to allow you to choose the cheksum. that's the scary one!

- substitute trojaned binary
- append some binary junk so the checksum matches
- profit!!!

Nothing to worry about yet, sort of like the first proof-of-concept brute force crack of DES.
Yes, it can be done under some circumstances.
Yes, eventually processing power and methods may improve to make this a valid attack
Yes, you can sleep soundly tonight.

Re:Should We Fear?

[IchBinEinPenguin]

maybe I should have read this first: http://www.freedom-to-tinker.com/archives/000661.h tml "And now the rumor is that somebody has extended Joux's method to find a collision in SHA-1." "The finding of a single collision in SHA-1 would not, by itself, cause much trouble, since one arbitrary collision won't do an attacker much good in practice. But history tells us that such discoveries are usually followed by a series of bigger discoveries that widen the breach, to the point that the broken primitive becomes unusable. "

Re:Should We Fear?

[prichardson]

I don't think George Bush is going to start spewing Swahili anytime soon. He has enough troubles with English.

Re:Should We Fear?

[straterpatrick]

Here is the significance of this story:

The proof that they have computed two values that have the same hash is significant because it proves that it is computationally feasible with today's computing resources to calculate a second different string or dataset that hashes to the same value as the original. It shows that a md5 hash can be "faked" or duplicated using current computing power. There is nothing significant about the values themselves presented in the story just that such values can now be theoretically found in a reasonable amount of time using available resources.

Why this is a bad thing:
Say I sign a program using md5. An attacker writes his own different program and appends some gibberish data in such a way that the two files are different but have the same md5 hash. There is now no way (using md5) to tell the two programs apart. (Of course the programs would have to be similar in other ways, size etc... for the spoof to work.) This same thing could be used to calculate new passwords for md5 hashes that are known to the attacker.

Why should we not panic: It took a long time to find the collision. Chances are a script kiddie wont be able calculate such hashes to crack into your site. But it show that banks or other highly confidential data stores should now look elsewhere for their hashing needs. (Which they probably already do).

Strater

Re:Should We Fear?

[Anonymous Coward]

I don't know if I'm ready for a collision at a "informal rump session"

Re:Should We Fear?

[serial frame]

Just to alleviate further fears, you can lower the risk of confusion between a known good file and a malicious file of the same checksum by also comparing the files' sizes.

However, I don't know enough about MD5 or SHA-[01] to know if collision is possible for every combination of bytes in certain fixed-sized samples. I suppose only quantum comping can tell. :)

/me tucks self in snugly.

Re:Should We Fear?

[kendoka]

WHAT WOULD IT MEAN TO YOU IF YOU GOT A SEMI-AUTOMATIC WEAPON?

Perhaps I could shoot the first family. =P

TELL ME MORE ABOUT YOUR FAMILY

What business is it of yours?

TELL ME MORE ABOUT YOUR BUSINESS. I CAN OFFER INCENTIVES TO SMALL BUSINESS OWNERS.

Uh, how about we talk about something else...

SOMETHING ELSE...

You know, you're starting to sound like a program I wrote in introduction to programming...

WHAT RESEMBLANCE DO YOU SEE

You are not very intelligent-sounding.

WHAT MAKES YOU THINK I AM NOT VERY INTELLIGENT-SOUNDING?

You never say anything but conservative rhetoric.

WHY DO YOU THINK I NEVER SAY ANYTHING BUT CONSERVATIVE RHETORIC?

You're a mindless tool for the Right-Wing Conspiracy.

DOES IT PLEASE YOU TO BELIEVE I AM A MINDLESS TOOL FOR THE RIGHT-WING CONSPIRACY?

Damn it! I knew it! You're just a useless Eliza hack!

WHAT ELSE COMES TO YOUR MIND WHEN YOU THINK OF ELIZA?

Re:Should We Fear?

[Dr. Blue]

First step is MATCHING some checksums (this has been done)
The next step is CHOOSING the chekcsum (aka DEADBEEF attack)
The next step is MANIPULATING, i.e. adding junk to a given binary file to allow you to choose the cheksum. that's the scary one!

Actually, you can do interesting and dangerous things with variants of your first step, not even progressing to step two. The MD5 collisions (well, almost collisions) are largely the same input data that has differences in only a few places. Now imagine that I have two messages that say something like this:

1. "Joe will send Dr. Blue $10. Confirmation number 1234567."
2. "Joe will send Dr. Blue $100000. Confirmation number 6451234."

Now lets say I can manipulate the confirmation numbers in those two messages so that they have the same hash value -- I don't care what the hash is, as long as it's the same in both cases. Then I send you the $10 message.

If you agree, you sign it. But you realize that digital signatures don't actually sign the message, right? They sign the hash of the message, so I can later produce the $100000 message, with your signature, and it will verify that you signed that message!

Re:Should We Fear?

[Anonymous Coward]

There must be exist hash collisions for a given hash function, whenever the plain text is longer than the hash value.

Of course, even though the hash space is much smaller than the potential plaintext space, it is still large enough that it is infeasable to find such a collision.

For MD5, the plaintext space is infinite, and the hash space is 128 bits. Thus, for all inputs longer than 128 bits, there must, by necessity, be collisions.

Re:Should We Fear?

[Anonymous Coward]

All good points, but further add that it would be *extremely* difficult, if not impossible, to spoof the binary file so that it:

1) Has the same MD5 hash.
2) Has the same byte count.
And perhaps most importantly,
3) Still does something an attacker would want it to do (like execute on the target's computer).

Like the parent poster, I won't be losing much sleep over this announcement either. ;)

Re:Should We Fear?

[sploo22]

Or say Microsoft signs the hash of Windows XP SP3 with their special key. I tweak the firewall to allow in a nasty backdoor, put data in the padding to give it the same hash as before, and put it out on a BitTorrent site for hundreds of unsuspecting geeks to download. The signature verifies fine, so it must be OK, right?

Re:Should We Fear?

[Stephen Samuel]

I don't think George Bush is going to start spewing Swahili anytime soon. He has enough troubles with English.

Now you know why.

Re:Should We Fear?

[Spy der Mann]

That's why we'd need LOCAL hashes and not just one big global hash.

So let's say that for a 160megs file you store an md5 hash for every chunk (1, 2, 10 megs maybe?),

AND THEN you check the global MD5...

or who knows. Just do some math with the hashes themselves. It's not that hard to make an encryption algorithm more secure.

Like they did with DES -> 3DES.

Re:Should We Fear?

[Nogami_Saeko]

I remember reading an article long ago on Fravia's page of reversing which talked about how to modify executables so the CRC32 value would be whatever you wanted it to be. It was beyond MY level of math, but it could obviously be done.

The article was referring to software that ran checksums on itself to make sure it wasn't tampered-with as anti-piracy protection, but it could be modified for other uses.

I think it would be more complex on MD5s and such, but...

(too bad Fravia moved on to other things - the articles were absolutely fascinating. Fortunately there are still some mirrors around).

Re:Should We Fear?

[arivanov]

it proves that it is computationally feasible with today's computing resources to calculate a second different string or dataset that hashes to the same value as the origin

Important note - with a guaranteed lower number of operations. Instead of 2^64 (SHA0) they used a method that always delivers 2^51. While neither one of these is within Joe Average computing power, the difference may bring a message into the cracking range of people who are in possession of "heavy computational artillery".

Re:Should We Fear?

[struppi]

The next question is: what does this mean to the more advanced (but not yet commonly used) CHF's SHA-256 and SHA-512? AFAIK they are harder to break, but are based on the same principle.

Re:Should We Fear?

[Zone-MR]

This is step 3, which he mentioned:

"The next step is MANIPULATING, i.e. adding junk to a given binary file to allow you to choose the cheksum. that's the scary one!"

Fortunatly manipulating a file to have the checksum you want is a hell of a lot more difficult than finding a colision between two bits of random data which don't need to match any format or rules.

Re:Should We Fear?

[mistered]

But CRC32 is not a cryptographic hash, and is not designed to make it difficult to find a collision. CRC32 is in the same class as checksums, and is designed to catch errors introduced by transmission or storage. It's not just "more complex on MD5s" in the way that CRC32 is "more complex" than a checksum; it's an entirely different class of problem.

Re:Should We Fear?

[Dr. Blue]

You can sign an entire message rather than just its hash. It's certainly possible to just sign hashes too and that saves tons of space, but signing the full message is an option.

Of course you can do this, but the question is what do people actual do. In every single case I know of where digital signatures are actually used (including X.509 certificates, signed e-mail, etc.) it's a hash that's signed. For this to be secure, both the hash and the signature method has to be secure. If people just discovered a way to break the hash, then they can potentially break such a system.

Re:Should We Fear?

[Dwonis]

It's not quite so simple.

I don't know about other public-key algorithms, but with RSA, the numeric value of your message must be less than the modulus. So if you want to directly sign a 100 MB file with a 2048-bit RSA key, you have to split the 100 MB file into at least 390625 separate messages, and sign them individually. Even then, you run into problems with people re-ordering your messages, so you'd have to insert some sort of sequence-numbered header into each sub-message to prevent that.

With that many signatures and a predetermined header format, you start giving out an awful lot of data to perform known ciphertext attacks on.

Consequences?

[Fruny]

Can a crypto-geek sum up the consequences for all of us dummies? Thanks.

Re:Consequences?

[sinclair44]

While an md5 collision would be a Bad Thing, it isn't necessarily the end of the world. Just because you can have two files that have the same hash (a collision) doesn't always mean you can arbitrarily change a file but keep the hash. However, it's likely that we'll eventually find a problem with md5 that will allow a determined attacker that really knows what they're doing to make limited changes to files; this collision is the first step in that direction.

Re:Consequences?

[Myen]

Has it?

Reading the list, it looks like some people in China managed to produce a hash collision using unknown means...

Although the mention in the paper that the result was obtained in one hour (using a P690, whatever that is) sounds scary... There is very little information though, for example we don't know if the message was special in any way.

Basically, they have managed to find two particular messages which collide, but I'm not yet convinced that they know how to make a collision for any abritary message.

But then... I'm not a cryto person.

Re:Consequences?

[mblase]

I looked up hash collision (e2) and hash function (e2) at Wikipedia and Everything2, which clarified the summary quite a bit.

Re:Consequences?

[Anonymous Coward]

No, it is not possible to extract the original data from the digest. Hash algorithms have nothing to do with compression.

However, it might be possible to construct a file to a given hash. In that case, MD5 sums become worthless to check wether a downloaded file is what independent sources claim it is.

The security implications are quite severe. Also, P2P clients that use MD5 to identify unique files will be vulnerable to spoofing by malicious users.

Re:Consequences?

[Smidge204]

Honestly, I can't see how it would be possible to reliably reconstruct the data that produced the hash. If there are multiple data sets then it's still impossible to figure out which is the original, though you may have narrowed it down.

The REAL problem here is that hashes are used to store passwords and other security sensitive data. It is still impossible to recover the original data, but if a method is known that produces collisions then it would be possible to find an equivalent data set to give the same resulting hash. In other words, you may not have the exact same key but you can make one of your own that will work anyway.

One possible (and temporary) solution would be to salt the data somehow. This adds an extra layer of security because the hash you are looking at is a an unknown password AND an unknown data set which you (theoretically) have no access to. You can generate a data set that produces the same hash, but when submitting that data set it will be salted to generate a new hash that won't work. Think of it as a single math equation with two unknowns.

This fails, of course, if you manage to get a password and it's corresponding hash. Then you only have one unknown (the salt).
=Smidge=

Re:Consequences?

[NotQuiteReal]

It also means you can deny stuff. "Hey Mr. Lawman, sure that encrypted stuff looks incrimidating, but really is is just innocent spam that I encrypted and signed as a test. The fact that you decrypted it to kiddie porn is just a coincidence. Prolly no better odds than O.J.'s blood match - they let him off..."

Re:Consequences?

[GreenHell]

Of course it will be possible to find a collision given enough time. There are only 2^160 possible sha0 hashes.

You say 2^160 like it's some tiny number.

To demonstrate how large that truly is, let me do a little thing that my cryptography prof did when I took the course several years ago:

2^160 = 1.4615016373309029182036848327163e+48 possibilities. (We'll be nice to the people following along and say 1.46 x 10 ^ 48 possibilities.) Now, let's say you can successfully generate one unique hash per second, that's 1.46 x 10 ^ 46 seconds.

But just how long is that exactly?

Well, let's be nice (for the sake of making the math easy), and say that there are 100 seconds in a minute. That's 1.46 x 10^46 minutes. Now, let's do the same thing for minutes in an hour: that's ~ 1.46 x 10^44 hours.

Now we reach hours in a day. I'm feeling really generous, so we'll say 100 hours in a day. That's 1.46 x 10 ^ 42 days.

365 (or 366) days in a year is too close to 3 x 10 ^ 2, and dividing by 3s is just messy, so we'll say 1 000 days in a year. That gives us 1.46 x 10 ^ 39 years.

Chances are good that our sun will have burnt itself out long before you've managed to generate every single possible hash.

However, what makes this particular case more interesting is that they've found a way to get a collision without brute forcing their way through every possible hash. It's not particularly useful yet, as it's still a 2^51 problem, (approx 2.25 x 10 ^15), so it's hardly trivial enough for you to do on your home PC, but it's a step in the right direction.

Re:Consequences?

[psetzer]

Quick combinatorics, folks. There are 2^8,388,608 different 1 MB files. If we digest it into a 2048 bit file, then we have created a function from a set of order 2^8,388,608 to a set of order 2^2,048. That means that there are on average 2^8,386,560 different 1 MB files that will create our 2,048 bit hash.

What this means for passwords is simple. People don't decrypt your password and compare it to a stored copy. They hash it, and then store the hash. When you log in, they hash your attempt, and if the hashes match, then the assumption is that the passwords matched, and you are let in. Hashes are very difficult to reverse, which is why they are used. The chances of two passwords producing the same hash is 1/2^2048. However, either one can be substituted for the other. We just trust in the extreme unlikelyness that two passwords would have the same hash and go on our merry ways.

Now suppose that someone has the hash of your password. They may be extremely unlikely to find your password, but they can find something just as good, if a bit unwieldly, since there's no guarantee that the substitute password is just as short as yours. If you don't mind a million character password, then there are likely about 2^8,386,560 passwords that will spoof yours.

Re:Consequences?

[afidel]

As others have pointed out the problem is bigger because file hashing is not the sole use of MD5, it is also used for password hashing. The problem with password hashing is that with a collision you don't need to have the origional password, a data set that hashes to the same value can be used for entry because the only thing the password checking function can check is the hashed value. The solution to a slightly broken hash function is to either use the same function to hash the password with two different salts or use two different hash functions, either way the chances of a collision value hashing with either the salts or two different functions is astronomically small.

Re:Consequences?

[dpletche]

In other words: When people find collisions (two different datasets that result in the exact same digest), then that is the first step towards being able to "reverse" the digest process, and extract the original data from the digest, thus rendering the encryption useless.

Nooo.... Not even close.

Let me illustrate with a simple example. Imagine that a hash function produces a 2 bit digest value from an arbitrary input 500 bit string. It's not a good hash function, because in about three tries you find another input string that produces the same hash value. However, you don't have any hope of turning one of the hash values (0, 1, 2 or 3) back into the 500 bit input string, even though the hashing algorithm is clearly broken by any commonly accepted definition.

A more realistic example is the MD5 hashing algorithm, which produces a 128 bit digest value from an arbitrary input string. Assume, for the sake of simplicity, that you're hashing only 1024 bit strings (though the input strings could be of any length). Then there are 2^(1024-128) = 2^896 possible input strings for every hash value. Your chances of guessing the correct input string are 1 in 2^896 (i.e. zero.) Remove the restriction that the input string must be of fixed length and your chances suffer even further.

In reality, the problem with a broken hashing algorithm is that an attacker can manufacture an altered document without affecting the "tamper-resistant" seal, i.e. the hash function digest. Other applications of digest algorithms dependent on probabilistically-guaranteed uniqueness of digest values as a function of content, like the creation of content-based unique identifiers, are likewise endangered.

However, the mere existence of a few random collisions, while potentially a source of unease for system and application designers, is not in itself evidence that a hashing algorithm is broken. Brokenness implies that for a given input X and digest F(X), other inputs Y can be generated in limited time such that F(X)=F(Y).

Re:Consequences?

[pnot]

For the sake of this post, I will simply define the two methods of
attack...

For the sake of this post, you will blatantly paste in great wodges of content from http://www.security-forums.com/forum/viewtopic.php ?t=8325 , without any attribution to the original author, one Justin Troutman. Shame on you.

What are the rammifications?

[ThisNukes4u]

What are the possible rammifications if MD5 is confirmed to have a collision? What other hashing algo's are there that may take its place? And even if it does have collisions, is that serious enough to break many security systems already in place?

Re:What are the rammifications?

[Gorath99]

What are the possible rammifications if MD5 is confirmed to have a collision? What other hashing algo's are there that may take its place? And even if it does have collisions, is that serious enough to break many security systems already in place?

It has already been established that MD5 has collisions. This is actually pretty trivial, since MD5 maps a byte string of arbitrary length to a byte string of length (IIRC) 16. Thus, since there are infinitely more strings of the former variety than of the latter variety, there must be at least one collision.

So, the fact that there are collisions is not a big deal; we already knew that. If one is found, then that doesn't really change anything. What would change everything is if someone found a way to find a collision for an arbitraty byte string. That way you could set up a mirror for a popular piece of software and instead of the real program, you could distribute something that has the exact same md5sum, but which does something completely else (most likely nothing sensible, since it'll be effectively a random string).

md5 is so weak

[Krunch]

$ echo "first post" | md5sum d008960fa6b395dca1c8362165bb31be

I didn't figured out your title tough.

Re:md5 is so weak

[Bingo Foo]

Okay, jokes aside, this shows how social engineering will always be among the best tools for cracking. Krunch, you da man.

Re:md5 is so weak

[Roguelazer]

I give up on the title... I tried all the usual slashdot titles (varying caps and w/ and w/o punctuation)...

"md5 cracked?"

"crack this!"

"GNAA"

"In Soviet Russia, MD5 cracks you!"

"fp!"

"First Post!"

I just don't get it...

Re:md5 is so weak

[freeweed]

I didn't figured out your title tough.

Just wait till the end of the conference. I hear there's a rumor MD5 is broken :)

Re:md5 is so weak

[vinlud]

I give up on the title... I tried all the usual slashdot titles (varying caps and w/ and w/o punctuation)...

You forgot the typo's...

Re:Just a Thought . . .

[Anonymous Coward]

Good plan. I will switch all my systems to "telnet" immediately. Thank you for your insightful comment.

Re:Just a Thought . . .

[ThisNukes4u]

Well, even if they confirm a collision, that doesn't mean that it can be exploited, especially if they don't release many details of how they got the collision and under what circumstances.

Happy for holes?

[ejito]

"We are glad to announce that we found a collision for SHA-0." - from the article

I just found the wording kinda weird... I'm hoping to do research in cryptography in the future. I know I'd feel quite proud if I found a vulnerability like that, but is it appropriate to show such enthusiasm? Kinda like an overjoyed astronomer that finds a comet heading into a collision course with Earth.

Re:Happy for holes?

[0x0d0a]

Kinda like an overjoyed astronomer that finds a comet heading into a collision course with Earth.

*I'd* be happy. Missing seeing that comet would definitely suck.

Umm...

[Anonymous Coward]

I'm a neophyte, so excuse my ignorance, but how does the fact that a full-time researcher (working on the SHA-0 algorithm), using a computation requiring: (direct quote follows):
The computation was performed on TERA NOVA (a 256 Intel-Itanium2 system developped by BULL SA, installed in the CEA DAM open laboratory TERA TECH). It required approximatively 80 000 CPU hours. The complexity of the attack was about 2^51.
... in order to find two different input values which produce the same output value (I presume that's what they did.. I could be wrong) make _any_ sort of practical difference?

Re:Umm...

[rhysweatherley]

I'm a neophyte, so excuse my ignorance, but how does the fact that a full-time researcher (working on the SHA-0 algorithm), using a computation requiring: (direct quote follows): ... to find two different input values which produce the same output value (I presume that's what they did.. I could be wrong) make _any_ sort of practical difference?

Once upon a time, you needed millions of dollars and specialized hardware to crack 56-bit DES. Now it can be done with commodity hardware and a little time. Moore's Law is relentless. Today's TERA NOVA is tomorrow's PDA.

Re:Umm...

[addaon]

Good question. :-)

The complexity of the attack was around 2^51.

SHA-0 is a 160-bit hash. Now, you might at first think that means it would take aorund 2^160 tries to get two strings that collided, but because of the birthday paradox (what's the probability that two people on a football field have the same birthday) it's actually supposed to be the square root of that, or 2^80.

Unfortunately, 2^51 is much, much less than 2^80. Which means that this crack was not just brute force (which is kinda redundant, since the definition of a crack to a cryptosystem is a violation like this without using brute force, but whatever). That means they've found a mathematical technique for making this 'easy'. Generally, once the idea is out there for an easy crack, people can gnaw on it and make it more general or easier, bringing this down to every-day-concern level.

Re:Umm...

[Anonymous Coward]

SHA is a 160-bit hash; the average attack complexity is expected to be 2^159, so reducing this to 2^51 reveals a huge weakness. The difference is a factor of 2^108 - the attack should have required 25961484292674138142652481646100480000 CPU hours, or trillions of actual years.

But there shouldn't be any practical effect - SHA-0 was believed to be weak, so nobody really uses it. The news about possible weaknesses in other algorithms like SHA-1 and MD5 is much more significant.

Re:Umm...

[shadow_slicer]

"Now, if it were possible to generate a message to collide with a given hash, that would be a big deal."

Really? I don't think so.
In order to do anything with it it would also have to pass all the other sanity checks.

Use an faked md5 to put out rootkitted .tgz? Odds are that any other message with the same hash isn't going to be a valid .tgz.

Use md5 to verify logins? Then who cares if someone can generate a message to collide with your password's hash when it's computationally more difficult than regenerating your password.

For the all applications that I've heard md5 being used, I don't think it would be a big deal. But of course I probably am not thinking of some other places md5 is used...

Re:Umm...

[yppiz]

Mod parent up. I just waded through 50 posts, and this is the only one that got it right.

The key is not that they found a collision, but that they did so with substantially less than brute-force effort. Substantially less here means 30 - 130 orders of magnitude less (depending on whether you call SHA-0 a 2^160 space or a 2^80 space because of the birthday paradox mentioned in the parent article).

--Pat / zippy@cs.brandeis.edu

Re: Umm...

[Black Parrot]

> Now, if it were possible to generate a message to collide with a given hash, that would be a big deal.

DeaR Valooed Customer,

Ple ase tipe yoUr credit card imformaTion into the_form beElow.

Tha nk s,
Customr Cervise

Re:Umm...

[ztane]

Use an faked md5 to put out rootkitted .tgz? Odds are that any other message with the same hash isn't going to be a valid .tgz.

Perhaps not, but it could still work... :

% gzip file
% cat /dev/urandom >> file.gz
% gunzip file.gz
gunzip: file.gz: decompression OK, trailing garbage ignored
%

Re:Umm...

[rew]

For passwords, the collision avoidance of MD5 will make sure that your very complicated password is not "cracked" by some stupid child typing "hi" at your password prompt. But not much more.

The important issue starts when you use PGP to sign your message.

Suppose you sign:

mybank: Please transfer $100 to my son's account: 12345678 ref: Have a nice vacation!

then your PGP program will calculate the MD5 sum of this message and sign that using RSA (or DSA). As all know those algorithms are very very strong.

Next, the attacker will change your message to:

mybank: Please transfer $1000,000 to J. Crook account 87654321 Ref: XXXXXXXXXXXXXXXXXXXXXXXXXXXX

and when the crook can then adjust the XXX part in such a way that an MD5 has collision occurs.... You just authorized your bank to do something you may not have wanted....

There should be about 28 X's in there. That will allow the crook over 2^160 possible messages. Trying them all, there is a high probability that at least one of them has a hash collision with your signed original message. If calculating which one of the possible over 2^160 messages has the "right" MD5sum, costs significantly less than 2^160 operations, then that's considered breaking the hash....

This could be a problem.

[WhatAmIDoingHere]

As long as we don't tell anybody, it doesn't exist right?

Oh...

Broken how?

[Matey-O]

If it's brute force, I'm not worried. If it's a cryptologically trivial computation, I'll have to go back to ROT26.

Re:Broken how?

[prichardson]

ROT26 sucks! Doing ROT13 twice makes so much more sense. I've even heard of people who do ROT2 thirteen times. I think they're a little wacky though.

Isn't this Inevitable?

[Josh Booth]

Isn't it always going to happen when you make a hash code that is shorter than the string you make it from there is the possibility of collisions? Or is it just that there was found two equal length strings that have the same hash? Either way, is it that big of a deal?

Re:Isn't this Inevitable?

[seanadams.com]

a cryptographic hash is not the same as data encryption - it's a *signature* of the data such that generating other data with the same signature is difficult. This is how you can check that the mandrake ISO you snagged off of bittorrent is a) intact and b) authentic

I'm not sure about the definition of "collision" in this case, but of course if you always reduce the number of bits, or always maps to fixed number of bits, then you will always have >1 thing (specifically, an infinite number of things for most hash algos) which will map to the same reduced number of bits.

What they mean by "broken" is that you can trivially *find* such a string.

Re:Isn't this Inevitable?

[shadowmatter]

Indeed, there are infinitely many unique bit strings we may take the hash of, and yet only 2^160 hash values they can map to. By the pigeonhole principle, some hash value is mapped to by at least two unique bit strings.

(The pigeonhole principle says that if you shoot N pigeons with N+1 bullets, and don't miss, one pigeon has two holes... or something like that.)

Now hash functions can be classified as either weak collision resistant or strong collision resistant.

A hash function h is weak collision resistant if, given h and a bitstring x, it is impossible to find some other x' such that h(x) = h(x'). Note that x is specified.

A hash function h is strong collision resistant if it is infeasible to compute any collision (x, x') of h.

So, if a collision was found in MD5, it's no longer strong collision resistant (since the person found a pair x, x' such that h(x) = h(x')). Its when MD5 is no longer weak collision resistant that things start to get scary -- meaning, given any arbitrary bit vector, I can find another bit vector that generates the same hash value in a reasonable amount of time. This means that, after you download your favorite Linux ISO, just making sure the MD5 hash checks out does not garuantee the authenticity of the file.

But no worries. There's still SHA-1. And if that isn't good enough, there's its bigger cousins, SHA-256, SHA-384, and SHA-512.

- sm

Re:Next step

[Anonymous Coward]

ROT13 should be safe for some time.

What are the ramifications?

[shawn_f]

I am curious about 2 things:

Firstly, perhaps someone here on slashdot.org might be able to shed some light on the particular encryption algorythms mentioned in the article...thier basic differences, weaknesses and strengths.

Secondly, I am assuming that a "collision" is not as seriuos as a crack...what is a collision, and what are the ramifications of this in my ssh sessions and the like...

I have read about and used encryption, but have never really delved into it. I would venture to say that a good many of us would benefit from some enlightenment.

Re:What are the ramifications?

[ctr2sprt]

Well, basically, there is a kind of data structure called a hash table. The idea there is that you take an arbitrary-length key and convolve it so you get a fixed-length, shorter result called a "hash." The hash is then used as an index into some other kind of data structure, typically a flat array. This lets you get very fast accses to anything in the hash table, provided that your hashing function is a good one. The main factor which hurts hashes is a function that doesn't evenly spread data across the entire table. Consider the English language. Some letters start words much more frequently than others. Using the first letter of the key would therefore be a bad hash function, since there would be a lot of keys with the same hash and several with almost none.

So, very simply, collisions are when a hash function takes two different input keys and produces the same hash for both as output. Going with our English-language library example from above, "Stevenson, Robert Louis" and "Sheridan, John" would both produce the same hash ("S"). That's all there is to a collision. They are inevitable when you take longer strings and turn them into shorter ones.

Now what this has to do with security may be becoming clearer. Because SHA1 and MD5 are good, general-purpose algorithms, they are used in lots of places. They are used to store your password. (You enter your password, the system runs MD5 or whatever against it, then stores that. When you need to verify your password, it runs the same process and compares the hashed versions.) They are also used as "digital signatures" to verify that the content of an object hasn't changed. And they are, of course, used in hash tables with a lot of disparate entries.

But this is genuinely not something you should be worried about. Like I said, collisions are inevitable. But the computational effort required to find one is far from trivial. It's much easier for someone to crack your password using a dictionary-based attack or social engineering or pretty much anything else, at least for now. When you should worry is if someone finds a way to take a hash and use that to produce something which, when hashed again, will result in the original: that is, two-way hashing. MD5 and SHA1 are both allegedly one-way hashes, so you cannot ever go from the hash to any sort of original data. This is why they're secure for passwords and the like. But if that should turn out to be wrong...

I can't speak much to specifics about MD5 and SHA1 because I don't really have the background in math to do so. (I have the background to write a computer program implementing the algorithms, but I can't explain why they work so well.) MD5 is older and has been suspected to be not-so-good for a few years now. SHA1 is newer and better. That's about all I can tell you.

Kind of expected this

[Vilim]

I have been expecting the MD5 crack for a while, it just isn't a secure hash anymore. SHA-0 was proven to be mathematically weak back in '98. There was no real need to brute force it. I highly doubt that SHA-1 was cracked, if it was, we are in trouble, is there any better hash to replace it? I figured that we would get quite a few more years out of SHA-1

What we really need is a mathematically strong hash which will let you user define its strength. For example the first byte of the hash tells the program how strong the hash is. As the strength byte increases, the mandatory execution time of the hash increases exponentially.

Re:Kind of expected this

[g-san]

hmmmm....

I have heard rumors of a cypher on the street called SHA-X. It's not mathematically strong, as you so eloquently put, but it's supposed to be really good, really stong stuff. And is really asymmetrical, meaning it takes less time to decypher the message after encryption. Unfortunately it uses a semi-random keysize, so you never know the strength until you try to decrypt. It also has a key that destroys itself 48 hours later so Alice or Bob can't even tell you were ever encrypted. Only problem is the algorithm tends to overuse one particular register resulting in spontaneous cpu burnout.

But hey, if you got extra cpus...

Re:Next step

[krog]

Security experts recommend using Triple-ROT13 for increased safety.

How is this news?

[0racle]

Im reading 'Practical Cryptography' by Niels Ferguson and Bruce Schneier, a facinating read on current crypto and cypher systems btw. Now it was copyrighted 2003, and there (page 88) they talk about SHA-0 being broken when it was created and give the distinct impression that SHA-1 is not to be trusted.

On a side note, I would recommend 'Practical Crytography' to anyone interested in, or working with modern crytography.

Re:How is this news?

[Anonymous Coward]

Okay, the story goes like this:

NIST (working with the NSA, but in a GOOD way) develops the SHS, of which SHA is part, during their effort to develop the DSS (of which the DSA standard is part). The standard is published, and everybody rejoices.

A little while later, NIST says, "Hey! There's a new version of SHA! We're calling it SHA-1. There are, uh, 'security concerns' with the old SHA. We can't tell you what it is, but don't use it. By the way, the main difference between SHA and SHA-1 is the introduction of a shift instruction. Buh-bye!"

The obvious inference here is that the NSA's crypto folks found a nasty problem with the original algorithm, and had it changed in the interest of keeping the Secure Hash Algorithm, well, secure.

Now, this catches the interest of cryptologists. They spend a bunch of time analyzing the algorithm, and a couple of folks found that there are a few attacks-- very theoretical, very impractical-- that could find a collision in slightly less time than a brute force search or a birthday attack.

With that, everybody stops trusting the original SHA. Most people decide to use SHA-1 or MD5 instead-- but SHA-1 has a longer hash length than MD5 (SHA-1 is designed for ~80 bits of security, MD5 designed for ~64 bits), so a lot of people decide to trust SHA-1 instead.

What's happened at CRYPTO '04 is a significant improvement on the attacks discovered previously. A birthday attack on the SHA-0 algorithm would normally be on the order of 2^80 memory and 2^80 time. This attack used 2^51 time and significantly less memory-- in other words, this attack is somewhere in the area of 500 million times faster than previously known possible.

As for the idea that "SHA-1 is not to be trusted", well-- maybe the more paranoid folks avoid it, but a lot of applications still use SHA-1:

For the record, SHA-1 is used in PGP (but not exclusively, and not necessarily as the default hash algorithm), in SSL (again, this can be configured), in a number of TripWire-like programs, by Gentoo's "emerge" system, the *BSDs' "ports" trees, and-- this is important, here-- as the only officially recognized hash for use in the digital signature standard (DSS).

So an attack on SHA-1 would be VERY significant.

Re:Airplane quotes

[xmas2003]

For those who don't recognize the above quote, go here ... especially Joey if you haven't seen a grown man naked yet ... ;-)

BTW, it wasn't that long ago that /. reported about the Feds finally formally dropped DES.

Re:Don't the laws of computing make it...

[BethLogic]

When used properly, One Time Pad is impossible to break. Of course, carrying around enough truely random characters/bytes for all of your encrypting needs without getting caught is another story. And humans are notoriously good at not following directions properly....

Re:Don't the laws of computing make it...

[Ancil]

That's a common misconception.

In fact, advances in computer speed tend to favor people encrypting data, rather than those trying to decrypt it. For example, increasing CPU speed by a factor of four or five will generally allow you to use a key two or three times as large, and still get the same performance. However, it definitely won't let you crack a key twice as large.

Suppose your faster CPU inspires you to move from 128-bit keys to 256-bit. What happens to the guy trying to decrypt your message? He now has to work 68,056,473,384,187,692,692,674,921,486,354,000,000 times as long, even if he buys the 5x faster CPU. Ouch!

Collision != Broken

[scovetta]

A hashing algorithm H is "broken" when for an arbitrary input A, you can feasibly calculate another input B for which H(A) = H(B).

All they found here were two values C, D for which H(C) = H(D). Anyone who thinks this was suprising needs to take a look at the idea of a hash:
Start out with 512 bits (2^512 possible values)
Hash it to 128 bits (2^128 possible values)
For each possible value to come out of the hash, you're going to have (2^(512-128)) = 2^384 collisions.

If they could find two data values with less than, say, 80 bits of data that both hash to the same, then that's something, 'cause that could be someone's password. And if two values of 80-bit data hash to the same thing, then the algorithm is bad.

I just don't think this is anything special. It's sort of like saying, "look, i found my password in the newspaper by circling various letters and numbers thoughout the articles." Or maybe not, it's still just not that great.

Re:Collision != Broken

[0x0d0a]

All they found here were two values C, D for which H(C) = H(D). Anyone who thinks this was suprising needs to take a look at the idea of a hash:

The existence of collisions is obvious. The point is that it should be so phenomenally difficult to find a collision that you can't ever come up with one in a sane amount of time.

If they could find two data values with less than, say, 80 bits of data that both hash to the same, then that's something, 'cause that could be someone's password.

That would be unlikely to be a big deal. For passwords, I can just brute force the password, maybe precompute a dictionary of password hashes.

Re:Collision != Broken

[GoofyBoy]

>I just don't think this is anything special.

From the article;
The finding of a single collision in SHA-1 would not, by itself, cause much trouble, since one arbitrary collision won't do an attacker much good in practice. But history tells us that such discoveries are usually followed by a series of bigger discoveries that widen the breach, to the point that the broken primitive becomes unusable. A collision in SHA-1 would cast doubt over the future viability of any system that relies on SHA-1; and as I've explained, that's a lot of systems. If SHA-1 is completely broken, the result would be significant confusion, reengineering of many systems, and incompatibility between new (patched) systems and old.

Re:collision != broken

[44BSD]

Collision == broken if the reason the collisions were found lies in a property of the algorithm which until now was misunderstood.

Collision == broken if the research leads to subsequent work which further weakens the algorithm.

Agreed that finding a collision via an exhaustive search is no big whoop, but I don't *think* that is what this rumor is about ;^).

Basically, that crack in your foundation *might* be no big deal, but it *might* mean that there's a spring running 6" below the foundation wall and in six months your mansion collapses.

The real point...

[chicagozer]

Right, in theory collisions are possible.

However, if the algorithm is weak enough to allow a collision to be manufactured deterministically, then an attacker can craft a substitute message that returns the same hash. Think appending a junk file to the end of an archive to force the same hash.

Can you see the problem with that?

wha??

[flacco]

i don't care about the implications for crypto or the science behind all of this. i just want to know what the fuck a "rump session" is, and would appreciate tips on avoiding them if i should go to such a conference.

Re:Of course!

[addaon]

how the heck did the parent get modded up informative?

There always going to be collisions in check-sums. If that weren't the case than we wouldn't need to distribute actual files, just check-sums.

Um, wow. Let's start from the top.

1) Yes, there's always going to be collisions in check-sums. Fewer bits than the checksum than the data, pigeon hole principle, yada yada.

2) Even if there were no collisions, the whole point (well, one of two... more on the second below) is that they're NOT REVERSIBLE. So perhaps just distributing collisionless hashes would be a good replacement for kazaa (it's all about collection, not actually listening, doncha know)... but for those who like to be able to use files, it's kinda missing the point.

3) And that point is, no KNOWN collisions. More importantly, no way, given a known data/hash pair, to generate another data string with the same hash. If you violate that principle, you've made the cryptosystem useless for ensuring that the data is the same data that was originally hashed. And that's exactly what this article is about... a technique (who knows how general yet?) to find collisions.

MD5 Rumored broken?

[tokachu(k)]

Pretty big rumor!

Re:Of course!

[Zangief]

There always going to be collisions in check-sums. If that weren't the case than we wouldn't need to distribute actual files, just check-sums.

You just ruined a GREAT and REVOLUTIONARY compression algorithm!!!

No, No, No!

[chicagozer]

Obtaining the original data is hardly the point of breaking the hash. You can't recreate the Illiad from 2048 bits for God's sake.
An attacker's goal would be to substitute something else for the original data and make you trust it.

Re:Don't the laws of computing make it...

[Darth_Burrito]

Indeed, here's another novel argument from Bruce Schneier's book....

in regards to the strength of 256-bit encryption:

now, the annual energy output of our sun is about 121 * 10^41 ergs. this is enough to power about 2.7 * 10^56 single bit changes on our ideal computer; enough state changes to put a 187-bit counter through all its values. if we build a dyson sphere around the sun and captured all of its energy output for 32 years, without any loss, we should power a computer to count up to 2 ^ 192. of course, it wouldn't have the energy left over to perform any useful calculations with this counter.

but that's just one star, and a measly one at that. a typical supernova releases something like 10^51 ergs. (about a hundred times as much energy would be released in the form of neutrinos, but i let them go for now.) if all this energy could be channeled into a single orgy of computation, a 219-bit counter could be cycled through all of its states.

these numbers have nothing to do with the technology of the devices; they are the maximum that thermodynamics will allow. and they strongly imply that brute-force attracks against 256-bit keys will be infeasable until computers are built from something other than matter and occupy something other than space.

bruce schneier, applied cryptography, p 158

Re:huh?

[j1m 5n0w]

sha-1
md5
ripemd
digital signature
cryptograph
crypto conference
Ed Felten

-jim

Biggest problem with MD5 breaking

[Facekhan]

I would just like to mention that one of the biggest problems of it becoming feasible to find a collision in MD5 is that a lot of routers use MD5 to authenticate routing updates with one another. If a hash is sniffed and the password is cracked then it becomes a trivial matter to inject bad routing updates and crash large networks especially if the inter-ISP BGP links are cracked. Its not quite as simple as I put it here but it is possible.

It means we all have to carry a midget around

[IronChefMorimoto]

Yep -- that's right. I'm not a crypto expert. Hell -- I'm a layman compared to most /.'ers, and my user number proves it (all 7 embarrassing digits of it). But I do know this -- if Slashdot crypto geeks are concerned about it, then we've reached the point of...

CARRYING A MIDGET AROUND.

Yes, it's true. Every person with encrypted data on Earth will soon have to carry around a Level 10 Anthromorphic Hexidecimal Midget Encryption System. Or "Midget Key" for short. The midget will become part of every computer purchase where the user requires high encryption, secured communications, etc. Families without sufficient room to accommodate and feed the midget will have to run computers with the old and vulnerable encryption technologies.

Meanwhile, those of us with a Midget Key will need to have his/her encryption midget with us at all times. The midget will encrypt data locally by locking a portable hard drive to his/her wrist and preventing anyone OTHER THAN THE OWNER of said local data from accessing it again. To facilitate this local midget encryption, each encryption midget will be equipped with:

- body armor
- handgun
- lightweight sub-machine gun
- tactical nuclear or convential explosive self destruct device

Addtionally, each encryption midget will be required to communicate with all other encryption midgets around the world using special genetically encoded phones that cannot be replicated outside of the midget gene pool. The phone will be surgically embedded in the arm of each encryption midget and require a drop of said midget's body temperature saliva to activate the phone (a.k.a. spit on the arm to make the call).

Why encryption midgets? They're:

- portable
- eat less than an encryption giant and/or an encryption obese person
- tough as nails

Why tough as nails? If you've watched The Amazing Race at all this season on CBS, you have witnessed a midget drag her whiney, lazy cousin around the world. She has become the envy of other teams featuring health nuts, ex-Marines, and super-Christians. Who wouldn't entrust their data with a badass little person that can grab a live electrified cattle fence somewhere in South America, cuss about it, and STILL manage to continue the race?

Get me THAT encryption midget, and you'll never get a hold of MY data!

IronChefMorimoto

[Note -- if the midget from the show mentioned above has been eliminated from said show, then our data is doomed. I've missed the last several episodes, so all may be lost.]

Re:It means we all have to carry a midget around

[aelbric]

I only see 6 digits in your ID, maybe your hash was cracked.

Re:It means we all have to carry a midget around

[PinchDuck]

It's better then my encryption dog. That system was broken with a raw DEADBEEF attack. Lousy mutt.

Re:It means we all have to carry a midget around

[Mr. Hankey]

Not yet at the same time, you'll need to wait for the duct tape patch in a week or so.

Re:Don't the laws of computing make it...

[Bert690]

And since processors are supposed to double their speed every 18 months, I guess that cracking ability will follow the same trend. Scary...

Not really...nobody expects this trend in processing performance to continue forever. There are in fact provable limitations given things such as the number of atoms available in the universe that can be harnessed for computation... ignoring little details like quantum computation and such :-). These limitations may seem "out there" but in fact they aren't nearly as unrealistic as you might think. Exponentials grow FAST.

It's trivial to continue scaling the computing requirements required to break encryption schemes by simply adding more bits. That is, assuming the encryption/hash scheme itself doesn't have some fatal flaw which may allow for a sub-exponential cracking algorithm.

Re:Don't the laws of computing make it...

[cpt kangarooski]

Truly random? Well, you could always buy a copy of "A Million Random Digits" but I still don't think it would work out well for you. ;)

Re:Don't the laws of computing make it...

[dmaxwell]

This is all true. However, you have to think about how long you need to keep something a secret. Let's say for the sake of argument that you confessed to a murder and encrypted it with single-DES in 1979. Anyone who got a hold of an intercept of it between then and now has evidence of a felony with no statute of limitations. Single-DES has been practically crackable by brute force since at least the mid-90s.

More realistically, what if the subject of the communication was a long standing bank account or evidence of a government scandal?

Advances in computing power can work for attackers who stand to profit from a long-delayed payoff. Advances in quantum computing will lower the expiration date of protection for anything you encrypted in the past even more. The further in the past the ciphertext was made, the weaker it gets. This will be generally true for any arbitrary past date and future date. No ciphertext can be considered indefinitely secure. We can only assume that reasonable protection only exists for the short-to-medium term.

Fairly long OTP messages may be one exception.

collision != broken

[Rex Code]

I wouldn't consider MD5 "broken" unless someone had discovered an easy way to add bits to an existing file to produce a desired checksum. If that were the case, I'd be seriously concerned.

Finding a single example of an MD5 collision in 80000 CPU hours is an interesting exercise, but I think we always knew collisions were possible (with any hash function), and I fail to see how this finding reduces the security of MD5 in any practical way.

No, this is a huge deal

[Tom7]

The paper that claims to have broken these says that the computation took 1 hour (with something like 15 seconds for subsequent collisions). Being able to generate collisions that quickly is a huge deal, and it has many applications -- it is often possible to "pad" a message with arbitrary data, so the data don't even have to have any particular format. It is scary to see all of these algorithms fall in the same week...

Summary

[TheRealFoxFire]

First, a little about SHA and SHA-1. SHA (0) was developed as a national standard hash function. Curiously, a last minute change was proposed by the NSA which resulted in SHA-1. The change was puzzling the cryptographers in academia. After some time, an attack was discovered on some classes of cryptographic hashes which SHA-1 turned out to be curiously immune to.

All that aside, one should view cryptographers a bit like plumbers. Cryptographers have a bag full of equipment (algorithms), which they combine in many ways to accomplish what they want. After much research and testing, certain ways of combining those pipes, valves, and spigots are 'proven' to work well, within given assumptions, such as expecting an L-joint not to leak. SHA-1 likewise is an integral component in many cryptographic systems.

SHA, MD5, RIPEM, and others are cryptographic hash functions. Cryptographers expect certain things out of a hash function. Its job is to take a variable amount of input bytes, and give you back a small, fixed number of bytes. Most importantly:

1. The function is 'one-way'. You can't determine from the output what any of the input was.
2. The probability that two inputs hash to the same output should be exceedingly low. In particular, an ideal hash function has a randomly distributed output for a large set of inputs.
3. Given a hash output, it should be extremely difficult to construct another document which also hashes to that output.

In this case, it seems that it may be much more easy than the designers had hoped to break the second condition. This tends to mean that 3 is easier as well, which has ramifications for security protocols.

So, in summary, this discovery is a bit like finding out that an L-joint which has been used reliably by plumbers the world over is much more likely to leak than previously thought.

But we haven't seen the results yet...

Re:Don't the laws of computing make it...

[AndrewRUK]

No, it's the OTP key that needs to be random. The main problems with OTP are that the key needs to be as long as the message, can only be used once, and a secure channel is needed to distribute the key.

If you do OTP right, it is unbreakable* because the only possible attack is to brute force it by trying every possible key, and trying every possible key on an n character cyphertext gives you every possible n character plaintext, with no way of telling which one is right. (That is, if you had the 16 character cyphertext "bhgisngukfgxd gyt" you would get all possible 16 character strings as possible plaintexts, including "attack US friday", "shoot Osama soon" and "I like chocolate", and you would have no way to tell which was the actual plaintext.)


*except for rubber-hosing, but that affects all crypto systems, and is a weakness of the people involved, not the crypto.

Re:Of course!

[prichardson]

You seem to have misunderstood my post. In any function where f(a) can never equal f(b) where a and b are two unequal real numbers there is an inverse to function f. The reason that MD5 works for what it's intended to is because it has collisions. Since it has collisions, and because it's a fairly complex function, it's impossible to come up with any kind of inverse. With anything that isn't loss-less compression you can't be absolutely sure that you have the same data that was originally hashed. There is always going to be some input that will generate the same hash. Hashes are used to reduce the probability that your data has been tempered with. Hashes reduce the probability so much that everyone considers them proof that no tampering has been done, including me. Until someone can use a hash to create a file that can be hashed and get THE SAME hash MD5 will not be broken.

Re:Don't the laws of computing make it...

[Gorath99]

We can only assume that reasonable protection only exists for the short-to-medium term.

Fairly long OTP messages may be one exception.

Actually, all OTP messages are an exception. For every plaintext P and ciphertext C, there is a key K, such that an OTP of P with K will product C. Hence, if you try all possible keys on a ciphertext of length l, you'll find all possible plaintexts of length l. So, if you have a ciphertext of length 3, then there are keys for "bad", "moo", "can", "has", "aaa", "bbb", "ccc", etc., etc. There's no way for you to know what the original was.

collisions found in MD5

[roca]

It's true.

Paper here:
http://eprint.iacr.org/2004/199.pdf

Independently verified here:
http://www.mail-archive.com/cryptography@me tzdowd. com/msg02579.html

Re:collisions found in MD5

[RedSlash0]

They didn't get a real MD5 collision. The authors of that paper got the IV vector endianness wrong on the MD5 algorithm and therefore the algorithm used wasn't MD5. However, the IV vectors don't seem to have any significance on the MD5, so I wouldn't think it'd be hard for them to produce a real collision after fixing up the algorithm.

Saltation of Password Hashes

[Anonymous Coward]

"this means that if someone gets hold of a database which has your password stored in md5, then they can crack it."

Generally not true. Most password hashing is done with unique salt data for the system, which is unknown to the cracker. In other words the passwords is not simply hashed by itself. (That would be really stupid.) Rather the password is mixed up (in a consistent way) with the "salt" data before the hash is generated. This prevents brute force generation of a password based on the hash. The larger the salt data set the better, of course.

Re:Don't the laws of computing make it...

[Mr. Slippery]

Not really, because you could still guess what the pad is on your first shot. It's not likely, but its not "impossible".

The beauty of the OTP is that it doesn't matter if you guess what the pad is - you can't tell you've got it rigbt.

Given a cyphertext of length 9, there are keys that will decrypt it to read "Kill Bush", "Save Bush", "FuckOsama", "Bomb Iraq", "Love Boat", "qwertyuio", "!@#3fst9$-", and every other 9 character string. Since the OTP is random, all these keys have equal probability of being the correct one.

why not do both a md5sum and a sha-0 ?

[aprosumer.slashdot]

why not do both a md5sum and a sha-0 on the same data? Isn't it more difficult to spoof a binary and have matching collisions in both hashes at the same time? If either of the md5sum or the sha-0 don't match then you know that the data has been tampered with, right?

Re:why not do both a md5sum and a sha-0 ?

[kasperd]

why not do both a md5sum and a sha-0 on the same data?

What you suggest is essentially just a 288 bit hash (128+160). The question is, would you rather trust this 288 bit hash created from two weak hash functions, or one of the 256 bit hash functions designed to replace SHA-1 and MD5?

Correction

[GreenHell]

I see that I forgot the birthday paradox, which means that brute forcing a hash is much closer to a 2 ^ 80 problem.

So here's the calculations for that:

2^80 = 1.208925819614629174706176 x 10^ 24, so we use 1.2 x 10 ^ 24.
1.2 x 10 ^ 24 seconds / 100 seconds/minute = 1.2 x 10 ^ 22 minutes
1.2 x 10 ^ 22 minutes / 100 minutes/hour = 1.2 x 10 ^ 20 hours
1.2 x 10 ^ 20 hours / 100 hours/day = 1.2 x 10 ^ 18 days
1.2 x 10 ^ 18 days / 1000 days/year = 1.2 x 10 ^ 15 years

A much smaller number, but you're still not likely to get it before the sun goes out.

MOD PARENT DOWN

[Anonymous Coward]

You sure done lernt hows to use the copy an' paste real good. You is plagiarizin' at a 5th grade level already!

http://www.google.com/search?q=%22attack+relies+on +the+idea+of+producing+duplicates%22&num=20&hl=en& lr=&ie=UTF-8&safe=off&filter=0

Re:Don't the laws of computing make it...

[wizzardme2000]

According to my quick (and quite possibly erroneous) math, 2^256 is about 10^77. Just for your records.

Good journalism

[Pan T. Hose]

Slashdot reports that CowboyNeal posts that an anonymous reader writes that rumors are that at the informal rump session, an unknown researcher will announce a collision in full MD5, two ACs confirm, all slashdotters consider MD5 definitely proved broken, film at eleven. That is what I call good journalism.

Re:Paradigm Shift long overdue

[Anonymous Coward]

Argh!!!! Digital Fortress had good characters, but absolutely rotten-to-the-core technicals. It's funny that someone would quote the "Bergofsky Principle", which Dan Brown made up out of the whole cloth (I've certainly never heard of it). The author is a technology ignoramus, which is not a fatal flaw except that he was pretending to be an expert, and getting almost everything wrong to one degree or another. The fact that I finished reading it is a testimony to his skill as a crafter of good fiction writing, not to its interest as a techno-thriller.

See earlier post about a thought experiment Bruce Schneier carried out that showed 256-bit symmetric encryption (if it had no holes) would be proof against any attack that could be carried out using (using our current knowledge of physics, that is).

Re:Don't the laws of computing make it...

[imlepid]

Well, I like this quote, (I don't remember it from my reading of Applied Cryptography, guess I'll have to re-read the book more carefully) but it assumes something which is impossible, that is, perfect algorithms. A more interesting quote for this particular news post would be any of the many from Schneier's book Secrets and Lies . The whole point of the book, as explained in the Preface, was that Schneier assumed when he wrote Applied Cryptography that it would help people develop secure applications, however what eneded up happening was people peppered cryptography into their software assuming doing only that would make their software secure. The reality is, in most software, the is not properly implimented and therefore not secure.

Secrets and lies discusses security not cryptography and does and excellent job at it. Although I had the vegue concept that no security system is really secure before I read the book, I came away from my reading thanking Schneier for drilling the idea into my head so that I would not be naive. It is the best book on security I have read and I recommend it to anyone interested in this facinating field.

Re:Don't the laws of computing make it...

[PhiRatE]

You're so wrong it's funny :)

Sorry, didn't mean to mock, it's just amusing whenever these one-time pad things come up and everyone starts jumping up and down yelling "unbreakable" and others start going "no, 'cos, like, we could brute-force it.."

You can't brute-force a one-time pad. That's the point. There are many weaknesses to OTP, related to key exchange, but you can't brute force it, because you have no way of knowing if you're right, or even if you're close. The possible set of plaintexts from a properly OTP encrypted message is the complete set of possible plaintexts of that size (or smaller, plausibly).

Let us take the following ciphertext:

aaa

I have encrypted this with a one time pad. Now, it's a pretty short message. We could brute force all the possible combinations on your regular computer pretty much instantly. Anyone care to guess what the message might be?

Of course not, because it could be *any* 3 letter combination, assuming that I'm sticking to letters. Any attempt to contextually analyse it is flawed because you will never be able to prove you got it right. Let's say that we know the message is english, and we can therefore reduce the number of possibilities down to all 3 letter english words.

Woohoo. It doesn't help, it doesn't get us any closer to knowing exactly what it is, because there is no next step, the only information that can aid us in the decryption of a one time pad is information from "outside" the decryption. In this case, two items of information are available to us, the length (3 letters) and the fact that it is english, but the actual ciphertext itself is of no value whatsoever. It doesn't matter if those a's were z's or q's or anything else, we can't do anything with them unless we have the OTP.

"Decrypt candidates with "bad" and "moo" in them would definitely merit further analysis"

This is always the point where things go wrong :) there *is* no further analysis you can make. lets take the following:

abskjhsglkjlssdkglkjsfdlkgjfld

Now lets imagine that we knew it was coming from bank robbers. Sweet, so, what can we do? again, the *only* information we have is the length. It could say this:

I am going to rob a bank in WA

Or this:

I am going to rob a bank in CA

Or this:

I am going to rob a bank in NZ

And there is no way to prove what it actually says at all. It might say:

I am going to buy some flowers

Again, you'll never know unless you have the key, there's just no way to tell.

SHA-1 is not SHA-0

[Effugas]

It's worth pointing out that it was widely assumed that there was a serious flaw in the original SHA, enough that NSA saw fit to add that final left shift at the end of each round. SHA-1 *exists* because there's a problem in SHA-0. The original SHA is not "slightly less secure" because it just lacks the fix; the nature of the algorithm is such that the slight variation NSA introduced created enormous deviations in the output function. Unless there's a fundamental architectural hole -- possible, see MD4/MD5 -- the original SHA could fall to pieces and it wouldn't mean SHA-1 was dead in the water.

I don't really know what Ed Felten means regarding "weaker cousins" of SHA-1 being the only other popular hashes. SHA-256 is a cousin, but has a larger hash size and is generally considered to be stronger. SHA (SHA-0?) is a cousin, but I've never seen it deployed anywhere. MD4/MD5 are still mildly popular, but they're at best design ancestors and not cousins -- there's no way a break in SHA-1 is going to make them any less secure (they have their own issues, of course). RIPE-160 and TIGER are the only two other hashes I've seen in the field, and they too have nothing to do with SHA-1.

There might be something here -- the left shift could have been a band-aid solution to an architectural fault in the SHA design, and there may be lots of curiosity about whether the new SHA-0 attack routes neatly around the fix. We'll see.

Probably not a big deal...

[barfy]

The discovery of a single collision is not a big deal. Discovery of an algorithm to create a collision WOULD be a very big deal.

The greatest weakness would be in password systems where only hashes are stored. If you could create an arbitrary password that had the same hash as one stored on the system (and there have been attacks on the password generation side, but none successfully on the side of specifically creating a password *based* on a hash), then you can get in.

There may yet be discovered a formula for creating that collision, now that we have discovered one, we can determine if there is a relationship between the two plaintexts that can be exploited if we know either the plaintext, or the hash, and can generate an arbitrary collision.

Document signatures are much less problematic. You would have to create a *sensible* document to replace the hashed document. This is way less likely to occur, to the point that would be attacking by far the strongest link in the chain.

Re:Probably not a big deal...

[evilviper]

If you could create an arbitrary password that had the same hash as one stored on the system [...], then you can get in.

Well, that doesn't have much to do with *collisions* at all.

If you have any method at all (collisions or not) to generate a string from a hash, then you have a problem with password systems... A collision would only be necessary if, for some strang reason, finding the ORIGINAL password isn't good enough, which isn't the case in any password-protected systems I can think of.

we can determine if there is a relationship between the two plaintexts that can be exploited if we know either the plaintext, or the hash, and can generate an arbitrary collision.

Well, if you need to have the plaintext to generate the collision, it's not at all useful for finding hashed values, such as passwords.

Document signatures are much less problematic. You would have to create a *sensible* document to replace the hashed document.

Indeed, it would be extremely difficult to exploit a collision, even if you do have a method to find them easily...

Hash Clash is nothing new.

[diggem]

I find clashes "ALL THE TIME" with MD5. I wrote a scriptie that does some data munging. It creates specialized logs ("clickstreams") of my employers public website. It takes input from four separate log servers, two, and then two redundant. To avoid logging the same thing twice it does an MD5 on some of the data. If the MD5 is different, great, keep the record. If it is the same, it does a byte by byte check of the strings and if the strings are actually different it keeps the 'new' record and increments a 'clash' counter. Clashes are still fairly rare, but I get about 2 or 3 a week at least on around 20-30 thousand records per day.

"HashClash" has been around since the first hash function was written. :) You got 30 items and 20 buckets? You're gonna have to either stick two things in a bucket, or get more buckets (larger hash domain/more bits).

Re:Hash Clash is nothing new.

[Animats]

That has to be a bug. Check that your MD5 implementation gets the right answers. If you still think it's not a bug, save a "clash" and post the data to sci.crypt.

Re:Hash Clash is nothing new.

[jbb999]

This sounds wrong to me. You'd need around 2^40 documents to have a good chance of any two of them having the same MD5 hash. You have no where near that many. Are you sure you are calculating your MD5 correctly?

Mmmhmm

[SidEgg]

Once they can break this: SuperD5/SHA Encryption Combo (crap, I am going to slashdot my own site :D) I will be impressed. I admit, it is hardly feasible, here is my code for those who are interested :)

function SuperD5($username, $password)
{
$one = $username;
$two = $password;
$thr = $one . $two;
$fou = $thr . $one;
$fiv = $fou . $one;
$six = $thr . $thr;
$sev = $one . $two . $thr . $one;
$md1 = md5( $sev . $two . md5($one . $fiv . md5($sev . strrev( $sev))));
$md2 = md5( $md1 . md5( $one . $thr . $fou . md5( $sev . $md1)));
$md3 = md5( $md2 . md5($md1));
$md4 = md5( $md3 . $md1 . $md2 . md5($sev));
//$md5 left out so not to error/confuse the parser
$md6 = md5($md4 . $md1);
$md7 = md5($md6 . $md4 . $md3 . md5(md5($six)));
$md8 = md5($md6 . md5($md7) . $md4);
$sha = sha1($md1);
$sha2 = sha1($md2);
$sha3 = sha1($md3);
$sha4 = sha1($md4);
$sha5 = sha1($md6);
$sha6 = sha1($md7);
$sha7 = sha1($md8);
$sha8 = sha1($sha . $md1);
$sha9 = sha1($sha2 . $md3 . $sha8 . $sha7 . $md2);
$sha10 = $sha . $sha2 . $sha3 . $sha4 . $sha5 . $sha6 . $sha7 . $sha8 . $sha9;
$sha11 = sha1($sha . $sha2 . $sha3 . $sha4 . $sha5 . $sha6 . $sha7 . $sha8 . $sha9);

return $sha10 . $sha11 . $sha . $sha2 . $sha3 . $sha4 . $sha5 . $sha6 . $sha7 . $sha8 . $sha9 . strrev(md5($md2 . $md1. $md4 . $md3 . $md2 . $md6 . $md7 . $md8)) . $md2 . $md1. $md4 . md5($md3 . $md2) . $md6 . $md7 . $md8 . md5($md2 . $md1. $md4 . $md3 . $md2 . $md6 . $md7 . $md8);
}

Re:Don't the laws of computing make it...

[PitaBred]

This is true iif (if and only if) there are no weaknesses in the hashing algorithm. If there are, then we start running into a much, much smaller solution space that's necessary to search.

He's got a point, but he's assuming many, many things.

Re:Don't the laws of computing make it...

[alanh]

This shows a fundamental misunderstanding of OTPs. Any message of n bits could be encoded as any other message of n bits. Even your "natural language parser" doesn't help. Take an arbitrary "short" message: "A". It is equally likely that it could decode to "I" or "A" or "Z" or any other 1 character string. It doesn't matter if you know what I'm talking about.

OTPs are provably secure, as long as the key isn't compromised, e.g. by reusing it....

Here is a good link that answers the question: Why Are One-Time Pads Perfectly Secure?

-a

Re:Don't the laws of computing make it...

[hoeferbe]

Phleg wrote:

Think about that. It is impossible, by our current knowledge of physics, to count up to nothing more than a 256-digit number...

Want something that will really blow your mind? Think about this: your computer monitor can display anything someone can take a picture of with a digital camera. Anything that is visible, can have its picture taken and thus can be displayed in your 1024x768 32-bit color monitor.

Now, one would normally think that there is an infinite number of possible pictures that one can take in our universe. Heck, just using a paper clip on a table could result in thousands of unique pictures considering the different angles, lighting, etc. Every situation, every person, place or thing you see during your lifetime could have its picture taken and displayed on that monitor! The near-infinite amount of photos that could be displayed on your computer monitor would encompass every visible event from the past, things going on right now, and events in the future. Some of these photos would be real, most would not be.

Above, I assume our computer monitor is 1024x768 & 32-bit color. To see all these pictures -- here & now, in the future on Mars, in a pretend past where Julius Caesar isn't murdered -- all one needs to do is program their computer to serially go through every pixel & color combination. Although it would take a very, very, very long time, eventually every pixel & color combination will be shown, thus showing everything that can ever be seen. A photograph of everything that could ever be seen, and even many situations that didn't/won't happen will be shown on that computer monitor. EVERYTHING.

Of course, many more times that in just random pixels & colors will be shown, too.

If SHA-1 is not enough, use lots of CHFs

[wintermute42]

Basicly you're saying that if SHA-1 alone is not good enough then use some combination of cryptographic hash functions and that will be better.

Well, OK. But it does not address the reason that so many people hope that the attack on MD5 and SHA-1 are not solid. These algorithms have a number of attractive characteristics. They are not hugely expensive to compute (the algorithm above is). They can be used to calculate a (supposedly) unique signature for an input. And the signature does not consume a large number of bits (another problem with the algorithm proposed above).

On a related note: I wonder if the attack on these algorithms has something to do with the number of bits used as input. Intuitively it seems that the larger the number of bits in the input stream, the more unique (widely distributed) the hash should be. So if you used small inputs then collision might be more likely.

Re:Don't the laws of computing make it...

[RedWizzard]

Longer strings make isolating the correct original easier, as there are fewer possible correct permutations according to syntax and context (which you know or have an idea of).

But it's not enough, because you still can't tell which variation is correct. E.g. a 19 character message can be decoded as both:
"I killed John Smith"
"I did not kill John"
There is no way to tell which is the real plaintext. Since every single 19 character sequence will appear, every 19 character English sentence and every 19 character sentence in every other language that uses the same character set needs to be checked. You can eliminate as many garbage results as you like, there'll still be a huge number of non-garbage results that you have no way of choosing between. In fact, you might as well not even look at the cipher text - it can tell you nothing. Just enumerate all 19 character sentences and work from there.

Re:Don't the laws of computing make it...

[bloo9298]

Even better, the pigeon-hole principle tells you that infinitely many different events will have the same picture.

Re:Don't the laws of computing make it...

[bigberk]

When used properly, One Time Pad is impossible to break. Of course, carrying around enough truely random characters/bytes for all of your encrypting needs without getting caught is another story

Yes, the OTP is the way to go -- sequence of random bytes, which you simply XOR with your message. Dump out /dev/random to a CD-R or DVD-R, make a copy for your friend, and you've both got nice one-time-pads that will probably last you quite some time.

What's interesting is that quantum physics offers several new things that will help implement excellent OTP systems... over existing fiberoptic telecom systems, no less! This is really exciting stuff.

First, quantum physics offers us a new way to generate truly random numbers for your OTP. Your rand() function sucks, I guarantee you. /dev/random is very good, but slow... /dev/urandom uses hash mixing so isn't nearly as random. Both rely on physical events, time intervals, and possibly thermal noise. In comparison, a quantum random number generator in theory gives you random bits that are totally un-influencable.

So now you've got your random bitstream... what do you do with it? Well, you hook up the OTP stream to a laser-based system that sends essentially single photons down an optical fiber. The idea being that single photons are either received by your friend or intercepted (absorbed) by your enemy. They can't be copied. Anyway several factors complicate this process but the basic idea remains. It's for real.

So your computer can generate a random OTP, securely send it to your friend (without fear of interception), and now you can both exchange classical data encrypted with your OTP. Repeat as necessary. If the physics behind this is sound, we shouldn't have to worry about algorithmic attacks in the future. Here's a rather complete article describing everything.

Re:Don't the laws of computing make it...

[mindfucker]

now, the annual energy output of our sun is about 121 * 10^41 ergs. this is enough to power about 2.7 * 10^56 single bit changes on our ideal computer; enough state changes to put a 187-bit counter through all its values. if we build a dyson sphere around the sun and captured all of its energy output for 32 years, without any loss, we should power a computer to count up to 2 ^ 192. of course, it wouldn't have the energy left over to perform any useful calculations with this counter.

but that's just one star, and a measly one at that. a typical supernova releases something like 10^51 ergs. (about a hundred times as much energy would be released in the form of neutrinos, but i let them go for now.) if all this energy could be channeled into a single orgy of computation, a 219-bit counter could be cycled through all of its states.

these numbers have nothing to do with the technology of the devices; they are the maximum that thermodynamics will allow. and they strongly imply that brute-force attracks against 256-bit keys will be infeasable until computers are built from something other than matter and occupy something other than space.

bruce schneier, applied cryptography, p 158

Okay Bruce, guess I'll have to take your word for it...

Re:Don't the laws of computing make it...

[MG]

Indeed, here's another novel argument from Bruce Schneier's book.... in regards to the strength of 256-bit encryption: now, the annual energy output of our sun is about 121 * 10^41 ergs. this is enough to power about 2.7 * 10^56 single bit changes on our ideal computer; enough state changes to put a 187-bit counter through all its values. if we build a dyson sphere around the sun and captured all of its energy output for 32 years, without any loss, we should power a computer to count up to 2 ^ 192. of course, it wouldn't have the energy left over to perform any useful calculations with this counter.

That is an erroneous conclusion based upon the (incorrect) assumption that a small amount of energy (kT) must be dissipated for each elementary computational step. If the computation is carried out using a reversible (classical) computer, this is not the case. Thermodynamics does not place any such restriction on computation. On the other hand, quantum mechanics does place constraints on the speed of a classical computer.
For more fun see Ultimate physical limits to computation by Seth Lloyd

One thing is secure forever

[Theatetus]

One time pads. If the pad's bits are generated by truly stochastic events (say, radioactive decay) and the pad is longer than the plaintext, there is provably no way to ever ever ever ever recover the plaintext without the key; the only method is to simply guess all possible plaintexts.

Re:Next step

[IchBinEinPenguin]

How otfen does this have to be said:
- odd is development
- even is release

use ROT13, tripple-ROT13, quintupple-ROT13 for DEVELOPMENT WORK ONLY!
For release work, use double, quadruple, hextuple-ROT13

Re:Don't the laws of computing make it...

[swillden]

but it assumes something which is impossible, that is, perfect algorithms.

No, it doesn't. Schneier is discussing the computational complexity of scanning a uniform keyspace, which depends only on key size and doesn't touch on algorithmic quality in the slightest. Now, if he were talking about the security of 256-bit ciphers against any attack, rather than just against brute force, then the quality of the algorithm would indeed be important.

MD5 not *quite* broken yet, but maybe close....

[menscher]

For those who are seriously following this, you've probably seen the paper claiming to break MD5. I immediately started playing with confirming their results, but failed. There was some seriously strange stuff going on.

Eventually I gave up trying to reproduce the hashes, and went to looking online. I found a good summary explaining the mistake the authors made (endianness problems, mostly) at this website.

The end result is that they didn't break MD5 -- yet. But their result can probably be modified to break the real MD5. Looks like we have a few more days till the world ends. ;)

Re:Don't the laws of computing make it...

[Spy Hunter]

Also, with using individual atoms for computing, whilst it would be nice, it's also impossible(?) - given that the more accurately you try to measure one property of an atom, the less accurately you can measure it's other properties. There's a name for this, but I can't remember.

It's the Heisenburg uncertainty principle, and it doesn't rule out computing with individual atoms. It just means that computing with individual atoms will work a lot differently than it does with normal, mostly deterministic electronics. The field of quantum computing is all about exploiting the weird quantum properties of atoms to do even more computation than would be possible if they were completely deterministic little point particles.

breaking BitTorrent

[oskie]

Finding a SHA-1 collision would break current versions of BitTorrent. Recent versions identify each piece of the file by its SHA-1 checksum. First the pieces are downloaded out of order, in consecutive order. Then they are reordered based on SHA-1 checksum. If one put two different pieces with same SHA-1 checksum in a file, it is likely that 50% of the time you would end up with an invalid file if transferred over torrent. This could be used to prevent certain files to be transferred over BitTorrent, such as copyrighted files.

Re:breaking BitTorrent

[Lelon]

I believe you are correct but your reasoning is not.

In order to put two different pieces with the same SHA-1 checksum in a file, odds are your file is garbage anyway. You could not do this with someone elses file (as you mention, a copyright file).

You could however, very simply, send incorrect data (on purpose) that matches the hash in the torrent file. Users' bittorrent clients would believe the file to be complete when it is in fact corrupted. This would result in 100% of the users who downloaded that segment from you getting a corrupted file.

Re:Don't the laws of computing make it...

[ivarneli]

Some quick numbers on this:

First let's start with something that might return some "sensible" (i.e. not ridiculously high) numbers. On the Apple II, Basic programmers had access to an incredibly low resolution mode with 40x40 pixels and 16 colors. Assuming we only use 2 colors (say, black and white), there are:

2^(40*40) = 4.44 x 10^481 possible screen images.

Whew! Already far beyond the 2^256 limit discussed. But out of curiosity, we can look at some other numbers. Using the full 16-color support of this low-res mode:

16^(40*40) = 3.90 x 10^1926

How many possible terminal screens are there, assuming only alphanumeric (and space) characters?

(26+26+10+1)^(80*24) = 5.41 x 10^3454

And some other modes of interest:

320 x 200, 2 colors: 8.31 x 10^19265
320 x 200, 256 colors: 2.27 x 10^154127
640 x 480, 256 colors: 2.07 x 10^739811

After this, direct computation was far too slow, but we can get rough estimates:

640 x 480, 16-bit color:
640*480*log10(65536) = 10^1,479,622

800 x 600, 16-bit color:
800*600*log10(65536) = 10^2311910

1024 x 768, 16-bit color: 10^3787833

And finally...

1024 x 768, 32-bit color: 10^7575677

Yep, a 1 with 7.5 million zeroes behind it. So we may all have to wait awhile before we see a computer sequentially generate a picture of alternate post-Caesar Earth. Still, an interesting thought.

Re:Don't the laws of computing make it...

[Sinner]

Ummm... 1024x768x32bit = 25165824 bits. Cycling through these bits is exactly equivalent to the "counting up" problem you're responding to. Since we've already established we can't count that high, there's no danger anyone is ever going to show you ever possible picture. Given the thousands of possible variations of goatse guy, this is probably a good thing.

What should make you feel small is that physicist have figured out a way to count all the possible states for a particular volume of matter (assuming an upper bound on temperature, if that makes any difference). That means the entirety of the observable universe has only a finite number of possible states.

If the unobservable universe is infinite, and if states are distributed probabilistically (and why wouldn't they be?), that means that your hypothetical world where Julius Caesar wasn't murdered actually exists, out there, somewhere, far out of reach.

crypto news flash...

[xquark]

This person's intro into this "news flash" is so out of wack I don't know where to begin!
Lets start with SHA-0 collisions, methods for determining collisions in the original
SHA algorithm have been known since 98'. In 95' the NSA issued a modification to the
SHA-0 (original algorithm) which became SHA-1, the modification was to counter an attack
unknown to open researchers known as parallel shifting. The two French guyz which found
collision in SHA-0 in 98' were the first open researchers to encounter this attack method.
A side point I would like to make is that the NSA made a similar change back in the early
70's to the IBM DES algorithm which until 89-90 was not known why such a change was needed.
The attack the modification was protecting against was differential cryptanalysis. early 90s
there was a 20 year difference in knowledge late 90s there was only 3 years difference in
knowledge GO FIGURE!

So in theory the SHA news is old news, as far as MD5 and RipeMD, well anyone that has the
slightest clue of the mathematics behind message digests will know that all MDs derive from
the same logic and same mathematics, and that a flaw found in one algorithm can be easily
transferred to another algorithm if that a particular algorithm hasn't already dealt with
that specific attack/flaw.

And on a final note:
"Many systems, especially those that use cryptography for digital signatures are most at risk here."

Tell me of system in the world that uses security and does not make use of hash functions?

Arash Partow

________________________________________________ __
Be one who knows what they don't know,
Instead of being one who knows not what they don't know,
Thinking they know everything about all things.
http://www.partow.net

Re:Don't the laws of computing make it...

[DavidpFitz]

When used properly, One Time Pad is impossible to break.

Not quite true - a one time pad cipher where the key is as long, or longer than the message is impossible to break.

The phone line between the Kremlin and the White house is enciphered this way.

D.

How to crack hashes

[flux]

Well, it's quite simple actually. Let's take an arbitrary md5sum for instance:

d3b07384d113edec49eaa6238ad5ff00

Now, we obviously can see that the beginning of the data is complete gibberish. However, may I point your attention to the trailing three nibbles: f00. This is a clear clue! Let's use that as a base for our educated guess:

% echo foo | md5sum

d3b07384d113edec49eaa6238ad5ff00 -

And voilá, we're cracked it!

Re:So?

[arcade]

Does this discovery point to any kind of meaningful exploit?

Yes, I can think of one immediately.

File sharing networks, where someone can inject garbage with the correct hash - for example in a bittorrent network. I don't know which hashing function bt uses, but if it turns out to be easy to generate collisions - you could wreak havoc against movie-sharers all over the globe.

I'm pretty sure the MPAA / RIAA would throw a gigantic party if such a break became easy.

Really, really no.

[Onan]

If there is a fundamental flaw in the hash algorithm itself, simply using it more often will probably not solve the problem.

It absolutely is incredibly hard to make an encryption algorithm more secure. Just "doing some math with the hashes" is the type of bit-twiddling at which cryptologists both wince and sneer. "Then I'll multiply the second one by three, then add them together! Then modulo it 17! Then oohoohooh, square root the whole thing and drop the first digit! No one will _ever_ figure this out!" Crap like this does not add any new cryptographic strength, just a dependency on a secret algorithm. And any method which relies on a secret algorithm is hopelessly flawed.

There is still considerable debate in the cryptographic community about whether 3des is actually any stronger than des. Many people feel that if an attack is found to be effective against the des algorithm, the extra layers of stirring the bits around will not make the plaintext any more secure.

I'm afraid that Schneier covered this succinctly: "Anyone who creates his or her own cryptographic primitive is either a genius or a fool. Given the genius/fool ratio for our species, the odds aren't very good."

Sigh...

[Kjella]

1. If you can produce a hash collision between two random inputs, that is rarely a problem. Either input will be junk. It doesn't matter that you have two interchangable pieces of junk.

2. If you can produce a hash identical to a desired hash, you can mostly only sabotage (poison) a transfer.

3. If you can take an existing file and append data to match a hash, you have a total and very dangerous compromise.

From what I can tell, we're at #1. Make it #2, and things will break as people move to a new algorithm, but I doubt there'll be much problems. Now do #3, and I'm worried...

Kjella

Re:Sigh...

[Nevyn]

If you hit the hash with only breaking some never-used apps and obscure device drivers then distribute compromised CD. So I'd say 2 and 3 were the same thing.

That's more like three than two, two is where you generate a large random file that hashes the same as the iso (thus making downloads look ok, but actually be bad). If you can start with some known data, and then append something to make the hash be what you want then, yes, that's almost as bad as starting with the original and altering it but keeping the hash.

You also have other problems like the .iso you end up with really needs to be the same size and you probably need to break both MD5 and SHA-1 on the same file, which is probably much harder.

Re:Don't the laws of computing make it...

[dackroyd]

If the computation is carried out using a reversible (classical) computer, thermodynamics does not place any such restriction on computation.

I would be _very_ interested in buying any machine off you that is not subject to the laws of thermodynamics.

Re:Explain ?

[ctid]

These are hashing functions. The creator of some file can run a program against that file to create a "hash key". This hash-key is supplied with (separate to) the file and someone who downloads the file can run the same program as the originator and confirm that the hash-key he gets is the same as the one the originator provided. In principle, if a bad person were to change even one bit in the file, it would generate a different hash key and therefore the receiver would know that it had been tampered with.

What has happened here (IIUC) is that somebody has shown that it's possible to create a new file with the same hash key as some other file. Which means that I could put up a file for download and provide a hash key for it, but someone could "mirror" the file and change it to something different which still generates the same hash key. Which means that the "guarantee" that the hash-key gives is broken - a receiver can no longer be sure that a matching hash key means a matching file.

Re:Explain ?

[Ed Avis]

Nobody has 'shown that it's possible to create a new file with the same hash key as some other file'. That has been known all along and it's true for any hashing function where the length of the hash is shorter than the length of the original file. For example, if your hash function produces a result 100 bits long then there are 2 ** 100 possible hashes. Obviously there are more files than this so it is _always_ the case that there are two different files with the same hash value. Usually I'd expect an infinite number of files with any given hash value!

So I don't know what the news item is here, except as a curiosity ('look we found it' - like finding the next Mersenne prime) or some technique has been found for making hash collisions which is better than brute force. If all they did was brute-force hash lots of files until finding two with the same MD5sum or whatever, it's obvious they were going to find a collision eventually.

Can be used as a DoS

[pslam]

Really? I don't think so. In order to do anything with it it would also have to pass all the other sanity checks.

What if you find a hole in the sanity checks, or if there aren't any sanity checks at all? It's highly likely there are many programs out there which "trust" data which passes authentication, and don't bother with much in the way of checking. Now this is obviously a short sighted thing to do, but given that SHA-1 and friends are apparently not broken, I wouldn't be surprised.

Personally, I think breaking authentication has far more effect than breaking encryption. Often all you need is a garbage message to be accepted, e.g:

Use an faked md5 to put out rootkitted.tgz? Odds are that any other message with the same hash isn't going to be a valid.tgz.

No, but it will cause the application to fail in an unexpected way: an authenticated .tar.gz which doesn't untar. How about a scarier example: run you an apparently "safe" signed client-side piece of executable code off a web page, except it's actually garbage and it causes your web browser to crash. Or your web server does an automatic update from the vendor only to have its installation corrupted. Or simply inserting garbage but authenticated packets into a network stream thereby causing it to disconnect (or even crash one or both sides).

An interesting thing I notice in the SHA-0 collision is that there aren't that many bits changed - the message looks largely the same. I wouldn't be surprised if you could apply the technique to signed executable code such that a collision is found which would crashes a program in just the right place and just the right way to execute arbitrary code, e.g fork a shell.

What if

[dheltzel]

I send someone a file and use both SHA-1 and MD5 hashes to sign it. Can anyone tell me the odds of a simultaneous collision in both algorithms?

Unless the hashes have a lot on common, it seems like this would be a simple way to extend the useful life of both hashes.

Re:Next step

[Hard_Code]

Moron. Rot13 is ODD. Use ROT12, it's the last stable version.

Re:I found the original paper

[Gemini]

It looks like there are collisions for MD5, MD4, HAVAL-128 and RIPEMD

I am in the process of verifying them now, but may not be able to until my lunch break (1pm EST)

The MD4 collision has been verified.

The MD5 collision has some problems, but the researchers are trying to re-run their code before tonight's presentation.

MD5 Collision *NEARLY* Found

[michael path]

Ed Felten posted a follow-up on this article here.

As it turns out, there was an error in their findings - and that the MD5 value created is NOT the same in this incident.

URL for MD5 Collision

[Bri3D]

This PDF explains the MD5 Collision: http://eprint.iacr.org/2004/199link

a bad day for hash function primitives

[thelittlestbuddy]

Update from the CRYPTO rump session (I was in attendance):
Collisions were found in MD4, MD5, RIPEMD, and HAVEL (and SHA-0).

No collisions were found in SHA-1, but progress has been made in finding near collisions.

The presenter didn't give many details about how the collisions were derived, but did give some timing results. The highlight of the evening was when the slide for MD4 came up, and in the timing results section there was text similar to: "4 to 24 iterations. Can be done by hand." Ouch.

I think for MD5 it only took a couple of hours to find the collisions.

PLUS, in the talk on near collisions of SHA-0, the presenters were able to find messages that collided through ~30 rounds and were decipherable as english sentences...

Other talks seemed to indicate that SHA-1 *and* SHA-2 (256/512 bit) may be susceptible.

All in all, it was not a good day for hash function primitives.