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
...really secure or safe anymore? This scares me...
Friends help you move...
REAL Friends help you move dead bodies... ^_^
Time to move on to SHA-2 and MD6SUM
So what does this really mean for the average web surfer and computer user?
just got that working with xsupplicant today.
hello CAs.
Oh this is going to be a fun week.
My Paintball Pics
... inevitable that eventually all crypto will be broken? Surely it's only a matter of time.
It might be wise to shut off your SSH server until MD5 has either been confirmed reliable, or replaced.
MOUNT TAPE U1439 ON B3, NO RING
Can a crypto-geek sum up the consequences for all of us dummies? Thanks.
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?
thisnukes4u.net
No GNU has been Hurd during the making of this comment.
In the wake of stories like this, and last year's story about RSA-576 being cracked (here [slashdot.org]), is this a message that we need more secure forms of encryption than we already have? RSA is great so far, but how long until 1024 is broken? Or any other schemes, like the MD5 hashing that's used for digital signatures? Topics that people with lots of credentials behind their names are going to have to solve. Keeping ahead of the crackers is a big concern not only for security of transactions, but for personal privacy as well.
It was bound to happen, we will create stronger ones and as computers get better we will need better and better ones.
md5 and sha1 hashes have been crackable with different programs for a very long time.
Good plan. I will switch all my systems to "telnet" immediately. Thank you for your insightful comment.
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.
thisnukes4u.net
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.
Help I'm a rock.
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.
As long as we don't tell anybody, it doesn't exist right?
Oh...
Not a Twitter sockpuppet... but I wish I was.
If it's brute force, I'm not worried. If it's a cryptologically trivial computation, I'll have to go back to ROT26.
"Draco dormiens nunquam titillandus."
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?
n3rd pr0n
NOTHING IS SECURE FOREVER!
That's nothing. I can decrypt 1024-bit encryption in my head, in under 60 seconds, with Natalie Portman and Halle Berry rolling about in hot grits just off to the side of my 6 flatpanels.
Seriously though, makes you wonder how long the spooks have known about this.
(yells out) "Hon? Where's the tin foil?"
Considering that MD5 is mostly use to "sign" programs, how likely do you think it is that someone could "trojan" your app while keeping the MD5 sums the same. On another note, there could be big problems when we uses these in, oh, a password database. I guess the severity of the problem really depends on how you're using it.
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.
Many systems, especially those that use cryptography for digital signatures are most at risk here."
Well, they still beat some Microsoft "encryption" method from Microsoft...
"A door is what a dog is perpetually on the wrong side of" - Ogden Nash
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
Does this collision actually mean anything?
OK, so somebody found two documents that have the same digest. This doesn't mean that they can construct a document to match any given digest. Even it did, the document so constructed would be gibberish.
Does this discovery point to any kind of meaningful exploit?
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."
"It required approximatively 80 000 CPU hours"
You'll excuse me, I'm sure, if I refrain from panicking just yet? If this is true, we do need better algorithms, but that's still 9-10 years to find a collision! Not likely to be a problem, at least for the stuff I try to keep secure (our physical security is far, far weaker than that, for example).
BTW, it wasn't that long ago that /. reported about the Feds finally formally dropped DES.
Hulk SMASH Celiac Disease
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.
Wer mit Ungeheuern kämpft, mag zusehn, dass er nicht dabei zum Ungeheuer wird. --Nietzsche
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?
ZZ
for a new millennium
would be a few stanzas
with the resultant md5
as a closing line.
e2f536c7a7836ad (jk)
It's an IBM high-end Unix server. Runs Linux too, if you desire. Or both AIX and Linux simultaniously. Pretty sweet machines, and very enjoyable to work with.
IBM p690
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.
pr0n - keeping monitor glass spotless since 1981.
I've been running Outlook Express 4 and IE 3.05 unpatched on Win98SE for ages without a single probl@$#%@&^+++NO CARRIER+++
And here ladies and gentlemen, we have an example of the classic "NO CARRIER" joke. This probably was already in use before the 1-digit UID serie even started on Slashdot. It is quite old, and most people are tired of it, but some still thing it's funny.
And now, we'll move to the next MOSJ exhibit: a large former-USSR flag, and words printed on swappable cards...
IBM p-series 690
"I use a Mac because I'm just better than you are."
At this point, all hashes other than SHA-1 (for practical purposes) are known broken.
The paper is pretty definitive about MD4, MD5, HAVAL-128, RIPEMD and SHA-0. SHA-1 is rumored to be about to fall too.
And yes, this is bad.
Why wouldn't they release the details? Expect a full paper to follow as soon as they can get it polished off... something like this should breeze through peer review. This is good cryptanalysis and good science... this is what mathematicians (well, a subset of them) do. Why wouldn't they release the details?
I've had this sig for three days.
Pretty big rumor!
fuck...
You're just using a known plaintext attack. Nothing impressive about that at all.
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
Why wouldn't they release the details?
You know, some people, unlike you, actually left their parent's basement with 30 and have to make some money.
Just kidding. Someone had to say it.
Glad I stuck with ROT13.
And you all said I was a fool!
Well I think the idea is that someone running a mirror could replace that nice linux installer executable with a short executable containing a root exploit followed by however many junk bytes are required to make the md5 come out right. Previously it was thought too hard to figure out an apropriate sequence of junk bytes to achieve the same md5 (in any reasonable amount of time), but now apparently someone has succeeded in doing it.
So the amazing thing is not that md5 can have collisions. That's obvious. The big deal is that someone actually computed a sequence that hashes with md5 to a particular given hash value.
md5
ripemd
digital signature
cryptograph
crypto conference
Ed Felten
-jim
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.
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.]
This is the first comment I've seen that accurately describes the real problem.
The "goal" of md5 is not encryption. I'm not sure what you have in mind.
The purpose of a one-way (no, you can't "decode" it) hashing function is either passwords or checksums.
It is called a "one-way" has for a reason. The hash value is only unique for some degree of "unique".
In the case of checksums, the hope is that small changes in the original data will produce large changes in the generated hash, or at least some change.
It is "possible" that a classified government document will produce the same hash as a warez binary of counter strike 2, but in that case, a sanity check would prevail.
Common sense wins again.
True. It's not clearly stated HOW they found the colliding data blocks.
This was done by using a generalization of the attack presented at Crypto'98 by Chabaud and Joux. This generalization takes advantage of the iterative structure of SHA-0. We also used the neutral bit" technique of Biham and Chen (To be presented at Crypto'2004).
Could anyone with a background on maths shed some light on how this attack works, and how feasible is creating a data block for a given hash with it? That's all that matters.
Sometimes the jokes just write themselves, don't they...
With 30 what?
I've had this sig for three days.
$ echo "I have no dick" | md5sum
WOOT!!
As soon as they get a Beowulf cluster of, say TI-87 Calculators working on the problem, then the search will go much quicker.
Of course, I didn't RTFA, but what did they use. Obviously it wasn't 111 years of a single CPU.
This issue is a bit more complicated than you think.
uhhh...does "oh shit" cover it?...
"I think, therefore I get paid."
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.
Absolutely. Let's all just revert back to telnet. Or perhaps for maximum security we should all administrate our boxes with VNC ...
"The dew has clearly fallen with a particularly sickening thud this morning"
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...
He subtly switched from "checksum" to "hash" starting from his point #2 in order to demolish the grandparent's post about "checksums" using arguments for "hashes".
Gee, correct me if I'm wrong, but aren't collisions like this absolutely inevitable?
You have many bits of data becoming fewer bits of data. There WILL BE collisions.
What does this REALLY mean about the strength of the algorithm, though? In one possible instance, a file could be changed in a very particular way that could theoretically result in a non-nonsensical modification to the source while the hash remained the same. Does this mean the algorithm is "broken"?! No.
Or, if it DOES mean the algorithm was broken, then it was broken since it was dreamed up in some mathematician's mind.
Save time now so you can waste it later
forty-two.
A collision in a hashing function wouldn't make an exploit in something that uses a block cipher ie ssh, they are not the same thing. Something that did use a hash in the event of a collision would cause a leak of information, not a application exploit.
"I use a Mac because I'm just better than you are."
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...
So now I can get a personalized freemail account!
Um, wait a minute...
http://www.certainkey.com/md5challenge/
The creators are welcome to apply.
HAHAHA, no MD5 breaking algorithm can decrypt my clear-text passwords.
On another note... read Dan Brown's "Digital Fortress" if this Crypto stuff gets ya goin...
Now, so as not to be -1 offtopic (for the shameless book plug)... Can't say I'm surprised at this sort of an announcement, and not to be a conspiracy theory-monger, but you've gotta believe the NSA has computers that will readily break basic MD5 and SHO-0 encryption. Bergofsky Principle quite simplified states that an unbreakable mathematical algorithm cannot be created. In contrapositive therefore, given enough time and trial, even the longest and most complex encryption can be broken.
I won't be happy until someone disproves that theory, and writes something that is truly immune to the CPU-cycle approach to break in. God only knows what the NSA would want with my emails and files, but I'm thinking that if it really came down to that, I wouldn't really be around to speculate for very long...
my 2 yen's worth (grossly inflated, of course)
~Ess
If someone has found a way to generate a collision with a specific SHA-1 hash, or has a development that leads to someone else making such a breakthrough, then it cracks Trusted Computing wide open. SHA-1 is part of the central foundation of Trusted Computing.
Cracking SHA-1 would certainly cause a variety of problems in other areas, but if it kills Trusted Computing then I'm all for it.
-
- - You can't take something off the Internet! That's like trying to take pee out of a swimming pool.
On another note, there could be big problems when we uses these in, oh, a password database.
I'm no cryptographer, but I don't think this is a problem. After all, an md5 sum is longer than an 8-character password; most passwords won't have a conflict of reasonable length.
Post checksums for your files using 2 different hashing algorythms (e.g. MD5 & SHA-1). Even if both do eventually get broken, the collision spaces have about 0% chance of overlapping.
Say someone cracks the hosting server and modifies the downloadable binary in such a way that the MD5 sum is still the same. There are only a select few ways of modifying that file while preserving the same MD5 sum. Picking any one of those, the SHA-1 value will have changed.
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
My favorite compression algorithm is one that a college professor demonstrated:
1 - Whiteboard is covered with text (our dataset)
2 - Grab tissue and erase whiteboard
3 - The tissue now has the compressed dataset
4 - Your Homework: write a decompression algorithm
But I tried, though ;)
/usr/share/dict/linux.words (45427 words from RedHat9)
/usr/share/dict/linux.words`;do if [ "`echo $line|md5sum`" == "ec7b19b60e616fb1c6013d4ada83ec32" ]; then echo "match: $line"; break; else echo $line ; fi; done
All I know it doesn't match any words in
$ for line in `cat
"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.
Yeah, but all that padding.. Sure the MD5 sum will match up, but will the file sizes?
Suddenly, you check file sizes and MD5 sum and you can be pretty sure of your archive's authenticity.
Moot point.
Exactly. There's no such thing as a hash function that doesn't produce collisions (assuming the data is allowed to grow longer than the checksum). All you need to do to produce a collision is to append a sequence of bytes that's longer than the resulting hash; it may take a very long time to discover a collision, but it's certainly possible to produce one regardless of the algorithm. It is not a problem unless you know how to produce a collision quickly enough to become practical.
"In prison you just have to shut your eyes and take it. Here you have to shut your eyes and give it."
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?
If I remember correctly, PGP (IIRC up to 2.6.x) used MD5 as the hash in PGP signatures. Some (possibly current) versions use/used RIPE-MD/160. Current versions of PGP/GPG use SHA1. I could imagine someone taking a signed message, replacing its text with readable/understandable text that has the same hash, and releasing it as a supposedly-valid message.
The OpenPGP standard (RFC 2440), which PGP and GPG support (at least partially), list MD5, SHA-1, RIPE-MD/160, and MD2 as possible hash algorithms, with support required for SHA-1 (and suggested for MD5). HAVAL, TIGER-192, and an undefined double-width SHA algorithm have spaces reserved on the list, but that is all that's said. If (Once) MD5 and SHA-1 are broken, now long will it it be until PGP and GPG are updated to support new algorithms, and (in the case of PGP) would the update be free?
It's also worth noting that X.509 certificates and SSL use MD5 and SHA-1 (I think SSL may just use MD5). How secure would SSL and X.509 be if SHA-1 and MD5 are broken? SSL transactions don't leave much time to intercept and forge a packet, but X.509 used in e-mail and other messages could certainly sit around long enough to be messed with.
Oh, well. It was bound to happen; let's see how well/quickly a solution/workaround is found (and let's see if the vulnerability is as bad as many have made it out to be)!
We'd never have figured that out for ourselves.
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."
You wasted a GMail account registration on that username?
sed s/"reverse the digest process, and extract the original data from the digest"/"generate different data with the same hash"
I made a mistake, now I am corrected, thanks all for the info. I'm off to go read the shadow(3) and ssh(1) man pages now...
Instant mass computing. Illegal? Yes, but still easy for your avg /nerd.
[Fuck Beta]
o0t!
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
What's wrong with it?
Not a Twitter sockpuppet... but I wish I was.
see your parent for clues on decrypting subject.
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."
MD5 takes that group about an hour to break.
I suspect this qualifies at "not good".
j
What if you took the SHA-1 and MD5 and
:-)
ran both on your data (for example, a
password) and then stored them both side-
by-side? Wouldn't that make it nearly
impossible to break? Sure, you could,
according to this theory, find a new
set of data that matches, say, the SHA-1
hash, but that data couldn't *possibly*
match the MD5, could it?
Problem is, I'm sure there's a patent
on serial variant hashing. If not,
here's my prior art
Peace & Blessings,
bmac
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.
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.
cause it is.
The Internet's nature is peer to peer - 20050301_cs_profs.pdf
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.
:) 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).
"HashClash" has been around since the first hash function was written.
One of the properties necessary to a good hash function is that one finds it extremely difficult to find two documents that hash to the same value. These guys managed to do it. That in itself isn't such a big deal; we knew that throwing enough compute cycles at the problem would eventually allow someone to find a collision.
But that period of time should be measured in decades. The author of this paper did it in just a little over 13 days. I'm not quite sure what he did; something about neutral bits... which sounds an awful lot like a way to predict which bits can be switched together to produce the same hash.
Cryptographic strength is based on np complete problems. The problems that you have to solve to break a hash function are typically characterized as one that can only be solved in less than polynomial time by having an oracle function; that is, some way to know the result of a calculation without having to actually do that calculation.
Neutral bits sounds like an oracle function. 80 000 CPU hours on a 256-way system is just a little over 14 days. Now I'm just waiting to see if SHA-1 is vulnerable. (let's hope not!!!)
I am disrespectful to dirt! Can you see that I am serious?!
I think it's a hands-on instructional session.
--
"Outlook not so good." That magic 8-ball knows everything! I'll ask about Exchange Server next.
OMG! Somebody just trojaned my carefully selected meaningless binary string in just 80,000 CPU hours! Excuse me while I go drown myself.
A friend of mine was in the building at georgia tech when some computer students cracked the encryption protecting the microsoft source code. I think he said it was Rot 20 something
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.
Well... As long as you can only do it with Natalie and Halle there, I guess the world of crypto has nothing to worry about.
This is probably the checksum for Longhorn... we'll never figure it out now.
James Tiberius Kirk: "Spock, the women on your planet are logical. No other planet in the galaxy can make that claim."
which is harder to find a collision for: hashing with two very different algorithms, or hashing with the same algorithm but using a longer target string? collisions occur either way . . .
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.
All's true that is mistrusted
So what, the signature hashing of data is one way and collisions are the way in which data is protected in a one-way encryption scheme. Linear and Quadratic probing of collisions are common with those key value signature offsets. Sure O(1) is no longer true, but if all collisions were handled (via a logic decay into a stupid simple linked list) the signature could be predicted and regenerated incrementally. However, the likelihood of a data set being the exact size is very remote due to the probabilistic nature of the actual content being more than one "thing" (i.e. sorry, but the man-in-the-middle will have to wait).
I guess there are quite a number of software that use MD5 or SHA-1 hashes as if a collision is impossible, and indeed even when there is code to handle hash collision, it had been hard to test that code when no real collisions were known. Now, if such software is fed with two pieces of data with identical MD5 hashes, it might well break in horrible ways --- at least a DoS attack.
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. ;)
..how long you've had that one stored up. You must have been dying for an appropriate time for your marketing campaign launch...
Does Blamo make these?
---------------------
- Have you ever noticed that the more you learn about technology, the more stupid you sound trying to explain it?
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.
If I had any mod points... going on 2 years now
and by NIST. Makes you wonder what NSA ...) ?
...
is doing with those acres & acres of
mainframes in the underground bunkers.
Or is it just a matter of "good enough
for the rest of us" (and simple enough
for us to decrypt
I now reach for my tin-foil hat
Google VENONA !
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.
Write content whose MD5 hash is identical to the content. :)
Write content that produced the same hashes in 2 or more different algorithms.
And many more
It seems the ugliness of OTP is there are plenty of stupid/ignorant people around who don't understand it.
So you may be convicted and executed based on your "decrypted" "confession" and evidence from an "expert" witness.
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.
Actually, if you reuse a one time pad and a few samples of encrypted data are intercepted, it becomes trivial to crack. Hence the name: One Time Pad.
What about including the Hash of the plaintext in the original?
Something like:
Hello Worlde59ff97941044f85df5297e1c302d260
and then hashing that new plaintext?
Move Sig. For great justice.
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!
Could someone explain the meaning here ? Ok, they found a
collision, so... ?
Actually XOR is the strongest unbreakable encryption algorithm... providing some simple yet uncomfortable rules.
1) The key is the exact length of the cryptogram.
2) The key is made using really good enthropy source.
3a) The key is used to encrypt/decrypt the (arbitrary) content just once
or
3b) The content entropy is pretty high as well.
I heard about this: A pair of 2 identical CDs filled with white noise, identical. Encrypt the content with one, decrypt with the other, with next chunk of content move on to next (unused yet) piece of the noise. Destroy the CDs after all the noise has been used up.
Anagram("United States of America") == "Dine out, taste a Mac, fries"
I mean, the number of possible messages greatly exceeds the number of possible hashes, since the hashes are of fixed length. So, isn't it just a matter of time before a collision is found for any given CHF?
"The problem with internet quotations is that many are not genuine" -Abraham Lincoln
...that result in the exact same log entry. Which obviously result in the same hash. Either that, or your program is broken.
Kjella
Live today, because you never know what tomorrow brings
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."
Nuclear missiles will spontaneously launch and direct themselves to your house.
At least my neighbors will be safe.
paintball
That is of arbitrary length and will never be obsolete. In effect, it's perfect.
Hmmm.... GNU or U.S. Patent Office?
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
I beat you over the head and take your CD.
That's the biggest issue with the one-time pad - it has to physically exist somewhere, so now you have to secure it physically.
On the other hand, a "password" can exist in a head. Maybe not as computationally secure, but definitely more physically secure.
paintball
At least as long as you need to decode the one time pad.
I just come over to your house and beat you until you give me your pad and decode the message.
paintball
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.
Once you hash a password you are giving an attacker more combinations against it. The best thing to do is encrypt the password with itself.
To quote from the French email about SHA-0:
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.
So finding an SHA-0 collision is probably out of the range of most attackers, at least for a couple of years.
*I'd* be happy. Missing seeing that comet would definitely suck.
...that this would be just like asking the person to be executed whether he'd like a blindfold or not?
Kjella
Live today, because you never know what tomorrow brings
"Young lady, in this house we obey the Laws of Thermodynamics!!"
--Homer to Lisa
...is great if you can use them as they are meant to be used. Take a huge random pad (e.g. a DVD), deliver it through a secure channel (preferably in person), and use it for point-to-point communications.
The reality of it is that for most connections, this is hopeless. Remember, you can have no authority model in any way as they all rely on cryptography. Every point needs to be connected to every other point, each with their own OTP.
Symmetric cryptography has made the OTP redundant. While public-key algorithms (which typically involve hashes of digests too) are under scrutiny, I don't remember there ever being any common symmetric algorithm that has been cryptographically broken (i.e. with less work than keysize). DES is still broken by brute force.
Kjella
Live today, because you never know what tomorrow brings
read:
http://eprint.iacr.org/2004/199.pdf
and comment this
--
^^MAg^^
I like movies about Gladiators.
Fischer is/was a great chess player, but the guy thinks that Sept. 11 was a great thing, and so... he's a shithead. I don't care what kinda chess skillz he has - he is a shithead. Not that America is any safer if they get him, but on the other hand I won't shed any tears for that jerk.
.. am I off-topic?
And Michael Moore is a fat boob.
Hmm
These are the two messages that collided
First message (2048 bits represented in hex):
a766a602 b65cffe7 73bcf258 26b322b3 d01b1a97 2684ef53 3e3b4b7f 53fe3762
24c08e47 e959b2bc 3b519880 b9286568 247d110f 70f5c5e2 b4590ca3 f55f52fe
effd4c8f e68de835 329e603c c51e7f02 545410d1 671d108d f5a4000d cf20a439
4949d72c d14fbb03 45cf3a29 5dcda89f 998f8755 2c9a58b1 bdc38483 5e477185
f96e68be bb0025d2 d2b69edf 21724198 f688b41d eb9b4913 fbe696b5 457ab399
21e1d759 1f89de84 57e8613c 6c9e3b24 2879d4d8 783b2d9c a9935ea5 26a729c0
6edfc501 37e69330 be976012 cc5dfe1c 14c4c68b d1db3ecb 24438a59 a09b5db4
35563e0d 8bdf572f 77b53065 cef31f32 dc9dbaa0 4146261e 9994bd5c d0758e3d
Second message:
a766a602 b65cffe7 73bcf258 26b322b1 d01b1ad7 2684ef51 be3b4b7f d3fe3762
a4c08e45 e959b2fc 3b519880 39286528 a47d110d 70f5c5e0 34590ce3 755f52fc
6ffd4c8d 668de875 329e603e 451e7f02 d45410d1 e71d108d f5a4000d cf20a439
4949d72c d14fbb01 45cf3a69 5dcda89d 198f8755 ac9a58b1 3dc38481 5e4771c5
796e68fe bb0025d0 52b69edd a17241d8 7688b41f 6b9b4911 7be696f5 c57ab399
a1e1d719 9f89de86 57e8613c ec9e3b26 a879d498 783b2d9e 29935ea7 a6a72980
6edfc503 37e69330 3e976010 4c5dfe5c 14c4c689 51db3ecb a4438a59 209b5db4
35563e0d 8bdf572f 77b53065 cef31f30 dc9dbae0 4146261c 1994bd5c 50758e3d
#hostfile 0.0.0.0 primidi.com 0.0.0.0 www.primidi.com 0.0.0.0 radio.weblogs.com
"To be cryptographically sound, a CHF should have two main properties. (1) Given a digest, it must be essentially impossible to figure out what data generated that digest. (2) It must be essentially impossible to find find a "collision", that is, to find two different data values that have the same digest."
Which is as I stated, however, 80,000 hours to find a collision? is that essentially impossible? Given his hardware, on SHA-0 ?
Now, the collision is spookily close, but it looks like they cannot explain that. 80,000 hours is a heart beat in cryptography though.
Yes, it is interesting...
#hostfile 0.0.0.0 primidi.com 0.0.0.0 www.primidi.com 0.0.0.0 radio.weblogs.com
So Alice sends Bob a file, along with it's checksum. Bob applies the hashing function to the file, and controls the result with the checksum. Bob sees they match and concludes Mallory can't possibly have tampered the file, as there's one chance in a google that the tampered file would have the same checksum.
But what exacty proves to Bob that Mallory's hypothetical man-in-the-middle attack
didn't also replace the checksum with one consistant with the tampered file he tries to inject ?
So it was developed by BULL SH? I thought so...
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.
:)
Hahahaha!
It's rare to see a correct, informative post with a really clever joke in it. My hat's off to you, sir/madam
(For those not getting it, the pigeonhole principle refers to having N+1 pigeons and putting them in N holes, which guarantees you will have at least one hole with 2 pigeons in it. I think I'll use this explanation in the future though, it's much more fun!)
Endless arguments over trivial contradictions in books written by ignorant savages to explain thunder in the dark.
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)
History will be kind to me, for I intend to write it - Sir Winston Churchill
http://eprint.iacr.org/2004/199.pdf
History will be kind to me, for I intend to write it - Sir Winston Churchill
1998: Differential Collisions in SHA-0p df
by Florent Chabaud & Antoine Joix
http://fchabaud.free.fr/English/Publications/sha.
It presents the algorithm, an actual collision found and the conclusion, quote, "...our attack will therefore be totally inefficient on SHA1."
It didn't generate that much noise back in 1998. I'm wondering if it has to do with stock market...
I like my outfit, it's inexpensive, but cool -- April Ryan
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.
I wonder if this posting is a case of advanced trolling.
When coming up with the DES (Data Encryption Standard), some government agency insisted on a modification of the S-Boxes (the part that scrambles the bits) that later turned out to make DES more strong against the at that time (publically) unknown differential cryptanalysis technique, making it very reasonable that this agency knew about that attack technique.
This is described in Simon Singh's "code book".
Thus I wonder if there are two similiar stories, or if you intentionally or not, messed up the storiy.
Regards,
Marc
Other than an impressive show of mathematical calculation, this really doesn't change much as long as you don't give away the files containing the hashes, does it?
I'd be more interested in an achievement which found a string that causes a mathematical fault when md5 or sha-0 are called on it. In terms of probabilities isn't a fault just as probable as as collision?
+++ATHZ 99:5:80
I can't belive you used the term "Dark side of the moon" and no astro-geek has leaped up to correct you. Usually there's fifty posts along the lines of "You're wrong blah blah Tidal Locking blah Synchronous rotation blah blah."
What ? Don't look at me. *I* am not going do start that kinda thing !
--LordPixie
Maybe not the most technical answer, but clear and informative...
news that appeals to 0.00000000000000000000000012% of the world's population. neat! :)
"hey, could you pass me a paper towel? er.. I mean... DEPLOY ABSORBTION PANEL!"
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.
The Apple ][ did not support lower case characters, so your third equation contains an error ((26+26+10+1) should be (26+10+1)).
This PDF explains the MD5 Collision: http://eprint.iacr.org/2004/199link
The birthday paradox is about how long you have to look to find a collision. Which, in the example that you offer, says how long it would take to find two passwords that collide. But neither of them is likely to be the one that you wanted to break, so that doesn't help you.
First they hash you,
then they match you,
then they install you,
and then you are in.
f53f
Thanks for posting and for the clear explaination.
I'm guilty of fuzzy thinking here. I was thinking that these are iterative algorithms, similar to random number generators. And that a larger input stream would result in better distribution. But there is no reason to think this on reflection.
The relevant bit from:
Pure Crypto Project
which was 'cited' from:
http://diswww.mit.edu/bloom-picayune/crypto/13190
-- begin quote --
Adi Shamir once proposed the following hash function:
Let n = p*q be the product of two large primes, such that
factoring n is believed to be infeasible.
Let g be an element of maximum order in Z_n^* (i.e. an
element of order lambda(n) = lcm(p-1,q-1)).
Assume that n and g are fixed and public; p and q are secret.
Let x be an input to be hashed, interpreted as a
non-negative integer. (Of arbitrary length; this may be
considerably larger than n.)
Define hash(x) = g^x (mod n).
Then this hash function is provably collision-resistant, since
the ability to find a collision means that you have an x and
an x' such that
hash(x) = hash(x')
which implies that
x - x' = k * lambda(n)
for some k. That is a collision implies that you can find a
multiple of lambda(n). Being able to find a multiple of lambda(n)
means that you can factor n.
I would suggest this meets the specs of your query above.
Cheers,
Ron Rivest
Ronald L. Rivest
Room 324, 200 Technology Square, Cambridge MA 02139
Tel 617-253-5880, Fax 617-258-9738, Email
-- end quote --
My question is that does such a hash function live up to Shamir's and Rivest's claims? If so, such hash functions are a lot simpler to understand, use, and implement in software. Apart from the 'factoring n' bit, I can see no problems with this hash function as well but I am not a 'hardcore' mathematician like Rivest and Shamir are.
PS: Please help me decode the following:
0x0d0a (568518) 's signature line:
US War on Terror victories: an old chess champion, a student volunteer forum moderator, a US-planted mole. Proud?
old chess champion = Robert James 'Bobby' Fischer.
So who are the other two?
I cannot ask 0x0d0a by email, he/she won't give their email address out.
Bryan Taylor
iamcf13@hotpop.com
SpamByte code: 7
(see http://www.cf13.com/game-over-spammers.htm )
http://www.cf13.com/press-release.htm
All email containing unwanted content will be summarily deleted or reported as spam.
But, have you ever been to a Turkish Bath? :-P
"Creativity is allowing ones self to make mistakes. Art is knowing which ones to keep" - Scott Adams
-What's our vector Victor
-What?
-Roger
-What?
-You have clearence Clarence
-What?
-Roger
-What?
-What Victor?
-Our takeoff vector
-Roger...
-What Clarence?
and so on....
Here we go again!
Maybe I don't understand this but would it be possible to defeat a signed program using this exploit? For instance in RSA 2048.
LavaRND uses a lens-capped webcam on high-gain to generate provably random numbers, /dev/random is only pseudo-random, and not suitable for mission-critical randomness, IE: One-time pads for important data.
LavaRND is bullet-proof, weapons grade true random, for all the cost of a £20 web-cam.
Windows is only $500 if your time is worthless.
Im just wondering if I can think really stupidly and say this:
There are more possible character combinations (in fact, an infinite amount) in an arbitary-lengthed string than possible combinations in an md-5 string. Obviously, if this is not a one-to-one relationship, then there are going to be some (well, a lot of) collisions.
"Crap. I hope this can't be expanded to a full-on attack on MD5 or SHA1."
(SHA1 and MD5 are used heavily in all sorts of systems for password verification and message integrity checks. "Breaking" them - which would involve the discovery of a way to easily create a message with a given hash or create two messages with the same hash and specific content - would have all sorts of nasty implications.)
TANSTAAFI: There Ain't No Such Thing As A Free iPod.
Terrorists can attack freedom, but only Congress can destroy it.
Here are collisions for the real, off-the-shell MD5 algorithm.
C:\tmp> sha1sum x1 x2
a34473cf767c6108a5751a20971f1fdfba97690a x1
4283dd2d70af1ad3c2d5fdc917330bf502035658 x2
C:\tmp> md5sum x1 x2
79054025255fb1a26e4bc422aef54eb4 x1
79054025255fb1a26e4bc422aef54eb4 x2
C:\tmp> hexdump x1
0000000 31d1 02dd e6c5 c4ee 3d69 069a af98 5cf9
0000010 ca2f 87b5 4612 ab7e 0440 3e58 fbb8 897f
0000020 ad55 0634 f409 02b3 e483 8388 7125 5a41
0000030 5108 e825 cdf7 9fc9 1dd9 f2bd 3780 5b3c
0000040 82d8 313e 3456 5b8f 6dae d4ac c936 c619
0000050 53dd b4e2 da87 fd03 3902 0663 48d2 a0cd
0000060 9fe9 4233 570f e87e 54ce 70b6 a880 1e0d
0000070 98c6 bc21 a8b6 9383 f996 2b65 f76f 702a
C:\tmp> hexdump x2
0000000 31d1 02dd e6c5 c4ee 3d69 069a af98 5cf9
0000010 ca2f 07b5 4612 ab7e 0440 3e58 fbb8 897f
0000020 ad55 0634 f409 02b3 e483 8388 f125 5a41
0000030 5108 e825 cdf7 9fc9 1dd9 72bd 3780 5b3c
0000040 82d8 313e 3456 5b8f 6dae d4ac c936 c619
0000050 53dd 34e2 da87 fd03 3902 0663 48d2 a0cd
0000060 9fe9 4233 570f e87e 54ce 70b6 2880 1e0d
0000070 98c6 bc21 a8b6 9383 f996 ab65 f76f 702a
Not quite true - a one time pad cipher where the key is as long, or longer than the message is impossible to break.
That would be using it improperly.
The phone line between the Kremlin and the White house is enciphered this way.
According to the Crypto Museum, during the cold war, there was a teletype (not a phone line) between the Kremlin and the White House, and it was enciphered, but not with a one-time pad.
I hereby place the above post in the public domain.
Consider various standards that incorporate secure hash functions. Those standards might persist for a while even if a secure hash function is broken. It might be tempting to retain support for such standards for the sake of backwards compatibility. Someone might not realize that such a standard has become insecure. It is easy to not get around to updating software.
pr0n bot... mmmm, instant access
And she freaking lost tonight. I am looking forward to that one ass spending time in jail, however.
All that is necessary for the triumph of good is that evil men do nothing.
In Soviet Russia, ROT-16.5 encrypts YOU! ... Stupid Cyrillic Alphabet having an odd cardinal value. :P
I am unamerican, and proud of it!
A question for the more attuned: What if (and i'm not saying it is true, but this should be checked into) it were the case that, where hash collisions do occur, that the original plaintext messages are necessarily of different lengths. That is, even though they result in the same hashes, they are different lengths. Couldn't a method taking advantage of that knowledge make it possible to identify the "true" original plaintext? Am I at least potentially right? Or should I just go back to reading my Archie comic book?
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.
Well it should be called Boyles Observation. I guess any crazy gas breaking it ain't gonna do time. Boyle studied the nature of the physical, measurable, unchanging nature of gases. It is not as if Boyle said, "Article 1: You shall behave as ideal gases, and let P1V1 = P2V2, otherwise I'll send the boys around". If he did he is Gayer than Gay Lussac ;-) *sorry had to be said*
Moores law is just an idle, incidental observation that has no foundation in reality - only circumstancial observation. It is like throwing ten dead monkeys into the air, and then prediciting how the next ten monkeys will fall, then using that to predict the 10 pandas you are going to throw next year.
No animals were harmed in the making of this post. Several small children were placed in pressurised heated gas chamber, each holding a barometer, just for empirical research.
Boyle and Lussac are dudes, they rock.
#hostfile 0.0.0.0 primidi.com 0.0.0.0 www.primidi.com 0.0.0.0 radio.weblogs.com
It is, shall we say, not widely socially excepted.
Unless you're being an annoying wordplayer and describing humans as a species of animals or talking about other species of animals themselves.
Unless you have 2^2048 monkeys and-- Illiad? Oh, sorry, I thought you said Hamlet. You're right then.
Sincerely,
Pan Tarhei Hosé, PhD.
"Homo sum et cogito ergo odi profanum vulgus et libido."
That comment might've just happened to hash to the same Google hit, mightn't it?
chese chinese guys. ive seen the files they have created. there data in them is different. but the md5 key generated is the same......so how have then not cracked it?
True. The file sizes almost certainly won't match. Good point.
To quote from A. Joux, "Multicollisions in Iterated Hash Functions", LNCS 3152 (presented at this very conference):