Slashdot Mirror
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."
I picked the wrong week to quit sniffing MD5 hashes.
d008960fa6b395dca1c8362165bb31be
Can a crypto-geek sum up the consequences for all of us dummies? Thanks.
No GNU has been Hurd during the making of this comment.
Good plan. I will switch all my systems to "telnet" immediately. Thank you for your insightful comment.
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):
... 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?
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.
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.
Yes, but how does this affect me personally?
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.
History will be kind to me, for I intend to write it - Sir Winston Churchill
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.
"I use a Mac because I'm just better than you are."
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....
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!
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.
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.
May we never see th
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. "
I don't think George Bush is going to start spewing Swahili anytime soon. He has enough troubles with English.
Help I'm a rock.
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.
ZZ
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
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.]
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.
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.
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:
- The function is 'one-way'. You can't determine from the output what any of the input was.
- 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.
- 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...
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
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.
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.
It's true.
e tzdowd. com/msg02579.html
Paper here:
http://eprint.iacr.org/2004/199.pdf
Independently verified here:
http://www.mail-archive.com/cryptography@m
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.
Tom Swiss | the infamous tms | my blog
You cannot wash away blood with blood
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.
"I won't mod you down - I feel the need to call you a twit explicitly, rather than by implication."
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
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
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.
Sincerely,
Pan Tarhei Hosé, PhD.
"Homo sum et cogito ergo odi profanum vulgus et libido."
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?
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).
You're so wrong it's funny :)
:) there *is* no further analysis you can make. lets take the following:
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
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.
You can't win a fight.
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:
- "Joe will send Dr. Blue $10. Confirmation number 1234567."
- "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!
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.
"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.
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.
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?
Karma: Segmentation fault (tried to dereference a null post)
For more fun see Ultimate physical limits to computation by Seth Lloyd
Now you know why.
Free Software: Like love, it grows best when given away.
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
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.
Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.
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. ;)
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.
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.
fish and pipes
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
Arash Partow's Philosophy: Be a person who knows what they don't know, and not a person who doesn't know.
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!
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."
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
Live today, because you never know what tomorrow brings