Slashdot Mirror
Chinese Prof Cracks SHA-1 Data Encryption Scheme
Hades1010 writes to mention an article in the Epoch Times (a Chinese newspaper) about a brilliant Chinese professor who has cracked her fifth encryption scheme in ten years. This one's a doozy, too: she and her team have taken out the SHA-1 scheme, which includes the (highly thought of) MD5 algorithm. As a result, the U.S. government and major corporations will cease using the scheme within the next few years. From the article: " These two main algorithms are currently the crucial technology that electronic signatures and many other password securities use throughout the international community. They are widely used in banking, securities, and e-commerce. SHA-1 has been recognized as the cornerstone for modern Internet security. According to the article, in the early stages of Wang's research, there were other data encryption researchers who tried to crack it. However, none of them succeeded. This is why in 15 years Hash research had become the domain of hopeless research in many scientists' minds. "
I'm a big fan of teams like this in unraveling the security defects out there -- giving others more reason to make more secure schemes. I'd love to know how one can finance these groups (legally?). What does her group specifically gain from all this labor? Who pays for them?
Science, 1. Religion, 0.
I've fallen off your lawn, and I can't get up.
It looks like she did this almost 2 years ago. So why is this being announced now?
SHA-1 is a hash algorithm, not an encryption algorithm. Achieve competence or quit.
Aside from confusing hashing with real encryption, and saying that MD5 is part of SHA-1, isn't this article just repeating what was covered in these two slashdot stories?
Ewige Blumenkraft.
This is total crap. I can't believe anyone would give any second thought to Chinese propaganda.
MD5 and RC4 was not "cracked" and I highly doubt SHA-1 was "cracked" either. Some weaknesses were found in MD5 that do not affect the majority of uses of it. I suspect the situation is the same here.
I've had enough abrasive sigs. Kittens are cute and fuzzy.
The article doesn't make sense. There are no technical details and SHA-1 is a cryptographic digest algorithm, not an encryption algorithm. AES is what everyone uses for encryption now -- message digests are used for signatures. Important, yes, but encryption hasn't been rendered useless.
They also use the word "online" too many times for me to take them seriously. The implication is that because the professor broke SHA 1 that my online bank account is going to be drained. Not likely.
My other car is first.
This article is completely devoid of any real content. It just says she "cracked it" over and over, not explaining whether a crack is a collision, preimage, or other attack. It also seems technically inaccurate, saying that SHA-1 'includes' MD5? I know that no one RTFA, but c'mon, at least cover for a crappy article by having a good summary: this story has neither.
The article seems to mix "hashing" and "encryption". SHA1 is not encryption algorithm. It is hashing algorithm.
Overlooking the fact that a hash function does NOT equal "encryption", the above-quoted paragraph goes far beyond word choice and grammar errors, and appears outright factually... Well, not "wrong" so much as "completely absurd" - It would have to make at least some sense to actually evaluate as "wrong".
Anyone have a link to info on this that makes sense? Like perhaps the nature of the specific weakness Xiaoyun found, and by how much it weakens SHA-1? Makes a big difference whether this means you can obtain an arbitrary SHA1, vs reducing the search space by one or two bytes.
Coral cache : http://en.epochtimes.com.nyud.net:8090/news/7-1-11 /50336.html
sw5YRhw4ln3pr7$Ock1/4ma0u8Lw2Tm5l6/7DOiC5e6t4NSb6
The original article is full of misstatements like this doozy:
this SHA-1 encryption includes the world's gold standard Message-Digest algorithm 5 (MD5). Before Professor Wang cracked it, the MD5 could only be deciphered by today's fastest supercomputer running codes for more than a million years.
SHA-1 is NOT encryption, and it certainly doesn't "include" MD5. They are 2 completely different hashing algorithms. Hash algorithms are not "deciphered". Neither of them has been "cracked". They have been found, in theory, to not be as collision-proof as previously thought, but noone has yet found a way to take one block of data and modify it such that it would have an identical hash signature as the original. Both are merely found to be not quite as collision-proof (the most important thing for any hashing algorithm) as previously thought. This is old news.
The original article blows and contains no useful information whatsoever, it was written by someone who hasn't the faintest hint of knowledge about cryptography or mathematics in general.
I guess she cracked any encryption schemes, but found some loopholes. Great job indeed, given she has all those encryption schemes to her name, but the linked article is full propaganda, and less on details
and
Duh...
major corporations will cease using the scheme within the next few years... :)
so its cracked by the chineese and it takes a couple years to change. sounds great anybody know where to get ahold of this
Doctors do Massage in Longview WA now, who knew?
Makes me wonder just how much trouble the US or international financial community would be in if an adversarial organization cracked a major security encryption and didn't politely announce it, but instead kept their achievement secret. And then either cracked mountains of banking/military data at a leisurely pace, selling it piecemeal to finance rogue networks OR timed a widespread release of the crack algorithm for a catastrophic hit upon (inter)national security. What steps are being taken to combat this from eventually occurring?
There are two kinds of people: 1) those who start arrays with one and 1) those who start them with zero.
Gung'f jul V arire hfr nal bs gubfr arjsnatyrq rapelcgvba fpurzrf, guvf bar jbexf, naq fur jvyy arire jevgr n negvpyr ba oernxvat vg.
The Epoch times is a strange newspaper (http://en.wikipedia.org/wiki/The_Epoch_Times) - it seems to be an anti-establishment periodical with lots of fluff stories about people living in China and articles on the Falun gong movement (http://en.wikipedia.org/wiki/Falun_Gong)..
Far from being a Chinese newspaper it's actually published out of New York, and you might see (Chinese) people handing out copies on the street in your country (I see them in NZ from time to time).
So yeah, it wouldn't surprise me if the article was vague... I'd take it all with a grain of salt.
But they are certainly weak against attacks using rainbowtables. Both algorithms should be tossed into the bit bucket for something a little more secure. New services including Hashbreaker, Schmoo, freerainbowtables etc show how easy it is to brute force using rainbowtables. RE: http://www.hashbreaker.com/ and distributed rainbowtable generation http://hashbreaker.com:8700/ http://wired.s6n.com/files/jathias/ http://www.freerainbowtables.com/index-rainbowtabl es-distributed.html/
http://www.darknet.org.uk/2006/02/password-crackin g-with-rainbowcrack-and-rainbow-tables/
-Spudster
Any hash algorithm can be used as a stream cipher: hash the key and take successive values to make a pseudorandom stream, and then XOR it against the plaintext. This is the idea behind Daniel J. Bernstein's Snuffle ciphers.
From the original article cited by the epoch times article (at the moment /.ed)
Busted! A crisis in cryptography
"LAST year, I walked away saying thank God she didn't get a break in SHA-1," says William Burr. "Well, now she has." Burr, a cryptographer at the National Institute of Standards and Technology in Gaithersburg, Maryland, is talking about Xiaoyun Wang, a Chinese cryptographer with a formidable knack for breaking things. Last year Wang, now at Tsinghua University in Beijing, stunned the cryptographic community by breaking a widely used computer security formula called MD5. This year, to Burr's dismay, she went further. Much further."
cute...
In other words, this attack is 2^17, or 131,072 times faster than brute forcing the hash, and from what I've read, this is considered pretty impressive stuff. That said, crypto researchers have known for a while that SHA-1 is on its last legs. From Schneider's blog in February, 2005: Jon Callas, PGP's CTO, put it best: "It's time to walk, but not run, to the fire exits. You don't see smoke, but the fire alarms have gone off." That's basically what I said last August. So there's nothing much to see here, except a sensationalist newspaper article. This has almost certainly been reported before on Slashdot two years ago, so this story probably counts as a dupe.
We're been Pwned! I just hope they don't hrack our ID-10-Tee hash algorithm encryption! Then all our base will belong to them!
FLR
All your bank, are belong to us.
We are all just people.
The use of the word "online" reminds the reader that data security over an untrusted network is a much less mature field than physical security.
Without bothering to read the article, I will point out that as far as your bank is concerned, digest algorithms protect SSL negotiation in general and the key exchange in particular. A worst-case break in SHA-1 and MD5 can negate the protections provided by RSA and AES.
A short note about the attack has been available for a couple of years as well. The note shows collisions for two different reduced versions of SHA-1.
Though it's not absolutely certain, my guess is that the reality behind the new announcement is that they've actually found a collision for the full version of SHA-1, and possibly for MD-5 as well. OTOH, maybe the mention of MD-5 is just a journalist's hashed (no pun intended) version of the fact that SHA-1 is based closely enough on MD-5 that an algorithm that's successful against SHA-1 will probably be effective with respect to MD-5 as well.
The universe is a figment of its own imagination.
The probability is very small in a random universe, not any one you pick. And it still only implies a finite number of universes. And the correct spelling is "astronomically", which however means extremely large. You probably meant "infinitesimally"
That is 1 for school masterism, 0 for responding without thinking.
Here's what you really need to look out for: what's the NSA's reaction?
In the past, it was widely understood that the NSA was well ahead of the private sector in terms of both encryption and decryption. During the 70s and 80s, the private sector basically closed the "encryption gap" and produced some ciphers that (at least most people suspect) are as secure as those used by the NSA.
What's still an open question, is how far ahead the NSA is of the private/corporate sector in terms of breaking other people's ciphers.
Depending on the NSA's reaction, it might be possible to know whether or not this break was anticipated. If they're using SHA-1 internally, one can assume they didn't know about this discovery already, and they've fallen behind of the position many folks assumed they had. If they just shrug and smile, then they may have already known about this (and possibly been using it) for some time now.
"Ladies and gentlemen, my killbot features Lotus Notes and a machine gun. It is the finest available."
While the article is pretty much useless, there may be something to the overall point. I mean, it's not as though anyone can expect your average newspaper reporter, much less a Chinese state run paper reporter, to know much about the subject of encryption/hashing/etc..., so I think it's useful to look past the obvious errors in the article, and talk about what the underlying story actually is. _IF_ this is a new report of a collision in SHA-1, that wouldn't be surprising. Prof. Wang and her team have been responsible for discovering more than a few attacks against SHA and MD5 ( http://www.schneier.com/blog/archives/2005/02/sha1 _broken.html ), so it's possible that she discovered a method of causing a collision in full SHA-1 in even less than the 2^63 operations that had previously been the max. This article could just be poorly reporting that.
Or it could be 2 years behind the times.
Either way, MD5, SHA-0 and SHA-1 have been known to have collision issues for a while now. At least in my own applications, I've moved on to using SHA-512 (a SHA-2 variant with a larger block size and 512 bit output), and as far as I know, there've been no reports of a collision attack against it.
Incredibly old news. EE Times reported on it at the time, correctly referring to SHA-1 as a hashing algorithm, nothing more... by itself, anyway.
In the crossfire between Disinformation and counter-Disinformation, it takes Disinformation Theory to figure out what's going on.
Fortunately, my coauthor Prof. Philip Fellman (Southern New Hampshire University) and I have been working for years on a rigorous foundation for Mathematical Disinformation Theory. Or so we want you to believe.
-- Prof. Jonathan Vos Post
Cool...
SHA-1 hashes are used in HDCP authentication. This may be one more step in making HDCP (even more) useless.
...does anyone hear the mathematicians scream?
Don't tailgate - the end is near!
1) Hashing IS encryption. It is one-way encryption where the length of the ciphertext is much shorter than the length of the plaintext. It is used for message integrity and digital signatures of private key+plaintext. "Collision" is an inherent weakness of hashes due to the much shorter ciphertext to plaintext ratio.
1 _broken.html
2) MD5 was "cracked", by changing as few as 24 bytes of a 1k packet. The technique is the same as cracking CRC32 by changing just 4 bytes of a packet. Example: http://www.x-ways.net/md5collision.html
3) This is all old news, reported in Jan 2005 and discussed at length at: http://www.schneier.com/blog/archives/2005/02/sha
End of the day, message integrity can be compromised which makes this a big deal, of much more concern than cracked passwords.
Just so you know, SHA-1 is a hash, not an encryption algorithm. You can't really encrypt anything with it because you wouldn't be-able to get the plaintext back. Which is kinda the (one way) point of hashes....
I disagree with your assessment of MD5 and the majority of uses of it. There is a property of MD5 which is broken. It is possible to construct two bytestrings that have the same MD5 hash. In fact, it's relatively easy to.
This breaks an important property that most people assume is true about cryptographic hash functions. I think it's actually very hard, in practice, to determine whether or not losing that property renders a particular system more vulnerable to attack. I don't believe that downplaying the associated risk does anybody any favors. I believe MD5 should be treated as "Effort should be made to remove the use of this algorithm from any existing code unless a convincing case can be made that the break doesn't affect it.".
SHA-1 is similarly 'broken'. But, the break in SHA-1 is not currently computationally trivial to exploit. It is just less computationally expensive than it should be to generate two bytestrings with the same SHA-1 hash than it should be given the length of the hash. But once people start discovering weaknesses in algorithms, it's common that someone refines the technique to make the weakness worse. So, I would treat SHA-1 as "No new code should use this, and it should be removed from existing code if the required effort isn't very large.".
The biggest problem is that there isn't a clear algorithm to move to from SHA-1. SHA-256 and SHA-512 are based on the same principles as SHA-1, so there is worry (but no proof) that the break in SHA-1 could be extended to these two hash functions as well. But WHIRLPOOL, the other major contender, has received very little scrutiny.
I've save a bunch of interesting links about hash functions on del.icio.us.
Need a Python, C++, Unix, Linux develop
Cheeni Madarchod - sabko chord kar inki ma chodo.
Please note that Epoch Times is NOT a geek like paper its something you can get free at least here in Vancouver once a week I believe, most of the people reading it are not people who know much about the difference between hash vs encryption vs pi. Epoch Times is, but I might be wrong about this, a falun gong publication, and does at times put forth less news than propaganda, though something like this is probably 'news' even if it is old, and not really accurately reported.
rehashed story makes collision attacks ^2 as bad ! doh !
First they work over Jack Bauer, and now this!
SHA-1 is GPG's default signing algorithm for e-mail etc....
Block ciphers and hash algorithms are basically the same thing in two different modes. If you look at the SHA-1 algorithm, you'll notice that the main part of the algorithm is taking a 160-bit input (previous hash) and a 512-bit input (data to hash) and producing a 160-bit result (new hash).
Something about the SHA-1 algorithm is that if you know the 512 bits of data and the 160-bit output, you can find the 160-bit input. Just do all the rounds in reverse. This means that if you rearrange the parameters, you can make a 160-bit block cipher: the 512 bits are the key, and the 160 bits are the block to be encrypted. Knowing the key lets you reverse the whole thing. This is what the SHACAL algorithm is.
You can turn a block cipher into a hash algorithm as well, by using the data to be encrypted as the key.
Block ciphers and hash algorithms are designed with different security goals, however. A block cipher cares most that you can't find the key if given plaintext/ciphertext pairs. A hash algorithm cares most that two keys do not have the same effect, because those two keys are a hash collision by definition. As a real-world example, the "Tiny Encryption Algorithm" has a flaw where each key functions identically to 3 others. On a block cipher, this means that the algorithm is 4 times weaker, because there are 1/4 the keys - not a big deal if the keys are big enough. When using it as a hash algorithm, however, it means that each input has 3 other easily-found inputs that have the same hash! This is what the piracy group Xecutor exploited to break the "version 1.1" Xbox.
"Screw Sun, cross-platform will never work. Let's move on and steal the Java language." - Visual J++ Product Manager
>I think it's actually very hard, in practice, to determine whether or not losing that property renders a particular system more vulnerable to attack.
It is computationally feasible, now, to build collding X.509 certificates.
It is possible, in some common environments and with a little cleverness, to Create two documents which are both human-readable and meaningful and which have the same MD5 hash.
Those are attacks which a collision-resistant hash function is supposed to prevent.
A collision-resistant hash function which has been shown not to be collision-resistant is broken. As of today, there's no published way for someone to start with a file you created and match its MD5 with a document they created. But in the case where an attacker can generate both files (say, the new $MUSTHAVE binary that gets signed by the repository and the separate binary with the same MD5 that contains a Trojan) MD5 has lost its usefulness.
I still think the fact that a hash algorithm is broken can be relatively unimportant. I mean, for your average Linux distribution, if you want to trick someone into using your 'fake' iso, you will have to change the bits you want to change to make certain software vulnerable, or malignant, and then you will have to make sure it is giving the exact same checksum. You are not just looking for some collissions. The collissions have to be useful to you as well.
My question is, how trivial is it to create, say, a binary that features the command "take over user's computer" whilst keeping the same hash as the original.
The question I would ask myself is, what is easier, cracking the website where the program is stored, and replacing the hashes with the hashes of my binary, or trying to come up with a working binary that has my misfeatures in it. I still think that if you can make things difficult enough, then you have achieved the objective. Isn't this the idea behind crypto/hashes anyway. They are not 100% foolproof, but the required level is so hard as to not be worth it.
does anyone have a mirror of the newpaper handy?
Here is a coral cache of professor Xiaoyun Wang's actual site with PDFs of her papers Its in English. Note that loading the original URL takes quite a while because its hosted in china, and the coral cache of her papers is much faster.
Coral cache here. Sorry, the original link was from the chinese server.
Seems to be slashdotted.
Here is the text. Appears that the confusing parts of this article may be due to a combination of translation errors, and just poor knowledge on the parts of the writer and translator.
Chinese Professor Cracks Fifth Data Encryption Algorithm
SHA-1 added to list of "accomplishments"
Central News Agency
Jan 11, 2007
Associate professor Wang Xiaoyun of Beijing's Tsinghua University and Shandong University of Technology has cracked SHA-1, a widely used online data encryption algorithm. (Daniel Berehulak/Getty Images)
TAIPEI--In five years, the U.S. government will cease to use SHA-1 (Secure Hash Algorithm) and convert to a new and more advanced computer data encryption, according to the article "Security Cracked!" from New Scientist . The reason for this change is that 41-years old associate professor Wang Xiaoyun of Beijing's Tsinghua University and Shandong University of Technology has already cracked SHA-1.
According to a Beijing digest, this SHA-1 encryption includes the world's gold standard Message-Digest algorithm 5 (MD5). Before Professor Wang cracked it, the MD5 could only be deciphered by today's fastest supercomputer running codes for more than a million years.
However, professor Wang Xiaoyun, a graduate of Shandong University of Technology's mathematics department, and her research team obtained results by using ordinary personal computers.
In early 2005, Wang and her research team announced that they had succeeded in cracking SHA-1. In addition to the U.S. government, well known companies like Microsoft, Sun, Atmel, and others have also announced that they will no longer be using SHA-1.
Two years ago, Wang convened an international data encryption conference to announce that her team had successfully cracked the four world-class standards of data encryption algorithms of MD5, HAVAL-1 28, MD4 and RIPEMD within 10 years.
A few months later, she then cracked the even more advanced and difficult SHA-1.
According to the article, Hash was Wang's area of research. Hash is the basis of MD5 and SHA-1, the two most extensive data encryption algorithms now used in the world.
These two main algorithms are currently the crucial technology that electronic signatures and many other password securities use throughout the international community. They are widely used in banking, securities, and e-commerce. SHA-1 has been recognized as the cornerstone for modern Internet security.
According to the article, in the early stages of Wang's research, there were other data encryption researchers who tried to crack it. However, none of them succeeded. This is why in 15 years Hash research had become the domain of hopeless research in many scientists' minds.
Wang's method of cracking the encryptions differs from all others. Although encryption analysis usually cannot be done without the use of computers, according to Wang, the computer only assisted in cracking the algorithm. Most of the time, she calculated manually, and manually designed the methods.
Wang said, "Hackers crack passwords with bad intentions. I hope efforts to protect against password theft will benefit [from this]. Password analysts work to evaluate the security of data encryption and to search for even more secure encryption algorithms."
She added, "On the day that I cracked SHA-1, I went out to eat. I was very excited. I knew I was the only person who knew this world-class secret."
Within ten years, Wang cracked the five biggest names in data encryption. Many people would think the life of this scientist must be monotonous. However she said, "That ten years was a very relaxed time for me."
During her work, she bore a daughter and cultivated a balcony full of flowers. The only mathematics related habit in her life is how she remembers the license plates of taxi cabs.
With any generic news agency, highly technical things like this usually get boiled down to mush. However, here is a coral cache of Professor Xiaoyun Wang's site. I am using coral cache because it is faster than going directly to the chinese-hosted site.
I think you need to reread that article. SHA-256 and SHA-512 are based on SHA-2, not SHA-1.
TFA refers to its own source as the New Scientist. A quick search there reveals the article in question is dated February 2005. So I guess this should probably come under "oldnews", but in any case the NSA had had plenty of time to play with it.
What concerns me is that in the last two years I've heard no news about a replacement for SHA-1. Maybe every's hoping that if they ignore the problem, it'll go away.
With the site you have to scroll down to find the papers, some wierd formatting for some reason.
>Bullshit propaganda
>This is total crap.
>Chinese propaganda.
Published research, reviewed and confirmed by other cryptographers. Check the archives of any crypto mailing list.
The NIST has started a hash function working group to replace SHA-1.
"it is clear that it will be necessary to [move away from SHA-1] in the not-too-distant future", according to the Bellovin-Rescorla paper about the impact of cracks of hash functions.
A work factor reduction to on the order to 2^63 operations puts SHA-1 collision generation into the realm of possibility. 2^80, which people used to believe was the number of trials needed to generate an SHA-1 collision, would have been out of reach for decades.
"According to a Beijing digest, this SHA-1 encryption includes the world's gold standard Message-Digest algorithm 5 (MD5)."
Where do I start? SHA-1 stands for 'Secure Hash Algorithm 1' and is not an encryption scheme. Neither does it include MD5 which is a completely different hash (or message digest) algorithm.
See Schneier - http://www.schneier.com/blog/archives/2005/02/sha1 _broken.html
and http://www.schneier.com/blog/archives/2005/02/cryp tanalysis_o.html for actual coverage of the break. "They can find collisions in SHA-1 in 2**69 calculations, about 2,000 times faster than brute force. Right now, that is just on the far edge of feasibility with current technology. Two comparable massive computations illustrate that point." That's down from 2**80, so it's a concern, but not exactly the end of the world.
New apps being written should probably be using SHA-256 (256 bits) rather than with SHA1 (160 bits only).
"It doesn't cost enough, and it makes too much sense."
A pithy and insightful post.
People who dislike China tend to mention Tiananmen Square a lot, but they always forget the Tank Man is also a Chinese.
Indeed. How hard is it to generate two files of any kind which digest to the same md5 hash? Just curious...
This was covered by Slashdot many times before.
I agree however, that the editor did such a lousy job with this submission. Where the fuck are the "Related Stories" links? Where the fuck is the name of the professor? Zonk deserves a kick in the balls for this shit!
If you don't fail at least 90 percent of the time, you're not aiming high enough. (Alan Kay)
I can't seem to find a thread that addresses the issue of what this means to groups of people. I'd assume that if I was trying to protect highly classified and sensitive information and was using a form of this scheme that it would be a big deal, but that's not me. I run a website that requires users to log in and uses MD5 to encrypt their password (I'm not really even that sure if that is the correct terminology to describe what happens; I only understand encryption on a basic level), is this something I should be worried about? I don't want my user's personal information to be stolen, but I'm not storing anything sensitive like credit card or social security numbers. Basically, who should care about this development, from the developers point of view?
Sorry for the typo, I obviously meant "Are you sure about the "only if" part?".
The AACS key is NOT 0xF606EEFD628B1CA427BEA93A9CA9773F
However, it took a slashdot editor to generate colliding dupe stories of old news... Take that, Ms. Xiaoyun!
The AACS key is NOT 0xF606EEFD628B1CA427BEA93A9CA9773F
Oh.
It's a small world and it smells funny; I'd buy another if it wasn't for the money; Take back what I paid (SoM)
Sun has been investing in Elliptic Curve Cryptography for many years. Now that SHA1 has been broken, ECC appears to be urgently needed as a strong encryption replacement for common internet usage. According to the Sun Labs page, ECC is also a high-performance technology.
Zen tips: Pay attention. Don't take it personally. Believe nothing.
She had some fun then...
I guess explains why they were broken so easily...
The AACS key is NOT 0xF606EEFD628B1CA427BEA93A9CA9773F
Because the contents of your sig data will not register you ought to be arrested.
Where are we going and why are we in a handbasket?
SHA-2 is a new family of hash algorithms. But that's kind of like saying that Twofish is a new cipher algorithm that isn't Blowfish. Realistically, if someone finds a major flaw in Blowfish that wasn't anticipated in the design of Twofish, it's quite possible that Twofish has the same flaw because they're built along the same lines, despite being different algorithms.
The SHA-2 family is designed by the same people who designed the SHA-1 algorithm, and they were designed before the flaws in SHA-1 were discovered. And from what I understand, the internal structure of SHA-1 and algorithms in the SHA-2 family are very similar.
Need a Python, C++, Unix, Linux develop
What moron approved this poorly-written and inaccurate story? Oh wait this is Slashdot.....
It is relatively easy with MD5. It would probably require less than a week of time on a modern computer, possibly only hours.
If you spent 10 million on an SHA-1 cracking box, it's estimated that it would take about 127 days to find two colliding files.
Here is a PDF that's my source for this information.
An additional problem is that you can embed interesting things in .pdf, .ps or even HTML documents. You could embed both the evil code, and the good code. Then use a colliding block someone found a long time ago to choose between the evil code and the good code. So, once even one collision is found, it's possible to leverage that one collision into all kinds of existing documents because of the block nature of the two algorithms.
I expect that .pdf and .ps documents rarely see code review looking for evil code. So it's quite likely something like this would go compeltely undetected until the evil version was released into the wild causing a ton of confusion and lost time before someone figured out what was wrong.
Need a Python, C++, Unix, Linux develop
...you should be ejected from the planet.
These algorithms are block oriented. As soon as you have two blocks that collide, you can use those two blocks to make a code path decision. If you have one of the two colliding blocks, the 'good' path is chosen. If you have the other of the two colliding blocks, the 'evil' path is chosen. It doesn't matter what the two blocks are. Any two blocks will do.
Sure the 'good' path and the 'evil' path are both in the same binary. But if you can manage to get them into the binary instead of the source, the will never be found by review. If, for example, you are an evil Debian packager this isn't that hard.
Here is an example of this technique using Postscript.
Need a Python, C++, Unix, Linux develop
OMFG, w3ZA 411 0\/\/nZoR3d!!!! +3h ch1n3zE h4v3 haXXor3D 411 0uR 3ncryp+10n 411g0r1+himZ!
Now it will only take them 130 Quadrillion years to crack a 1024bit SHA1 hash rather than the usual 460 Quadrillion - just imagine the consequences!
w3Za d000m3d!
We suffer more in our imagination than in reality. - Seneca
Well with military bases in around 130 countries having hundreds of thousands of soldiers stationed in them, constant interference in world affairs, continual invasions under the guise of freedom, a planetwide surveillance network and renewed plans for space-based weaponry, some would say Americas relevance in world affairs is already worrisome enough. Look at China as the Yin to your Yang, a balancing force that will work out for the benefit of the whole.
The latest versions of TrueCrypt suggest not using SHA-1 and instead using RIPEMD-160 or Whirlpool. It wasn't because of the work done by this professor; rather, it was because they felt that there was some "mild" risk because of inherent weaknesses and collisions in SHA-1 that could make it easier to crack.
You're right of course, but as long as you use MD5 for simple checksums you should be OK. The possibility of a finding a collision in the "real world" remains extremely low. Heck, MD5 has had a pretty good run since Rivest came up with it in the early 90s.
Eventually we can all move to SHA-256 or whatever.
The game is Risk.
[roll dice]
Two for you. One for me.
[roll dice]
Two for me. One for you.
[roll dice]
Three for you. Zero for me.
[roll dice]
Three for me. Zero for you.
Don't make me play my cards! Ugh! I have to. I have too many.
[army buildup]
[roll dice]
And so on.
I have seen my position change in one turn of those friendly cards. Don't take this lightly.
qz
Where are all the Prof. Wang jokes? I am disappointed in y'all.
qz
...for the Big Leap Forward :P
Call me a total thicky, but can't we strengthen any application that uses a hash by using several different hashes? e.g. concatenate the md5sum, SHA-1, SHA-256 and RIPEMD-160 of the input data to make a composite "super-hash". Wouldn't that make finding a collision very difficult?
Even if you have a way to find a collision for each of the algorithms in isolation, you now have to find a collision for all of them at the same time, which is surely far far harder.
Please do correct me if I'm wrong, I'm interested to know why this won't work because it seems to be the obvious approach in light of the problems that have emerged with MD5 and SHA-1.
>north
You're an immobile computer, remember?
This news is almost 2 years old:5 24883.300-goldstandard-online-security-code-cracke d-.html
/etc/passwd by default, why didn't they switch to other algorithm in 2 years?
http://www.newscientisttech.com/channel/tech/mg18
The question is: why are they bringing up this news again? Moreover, why has there been so little talk about SHA-1 vulnerability during these 2 years? Most linux distro's still use SHA-1 based MD5 for
My bet is that the NSA knew this vulnerabity and has been actively exploiting it. 2 years ago this news was not good for them because people might switch to other algorithms they cannot break (so easily). That would be a reason to let the vulnerability go ignored by the software industry, as long as only the NSA could break it.
2 years has been enough time for the NSA to discover vulnerabilities and to build computers capable of breaking more advanced algorithms (SHA-2?). So it makes sense to push now for an upgrade SHA-1 to SHA-2, which the Chinese probably still don't know how to break. Thus the NSA would be regaining it's strategic advantage in cryto over the Chinese.
"Chinese Prof Cracked SHA-1 Data Encryption Scheme"
about several years ago in fact.
"Nothing to see here, move along.."
This article is simply wrong. It does not belong on the front page of an edited site. SHA-1 is a hash, not an encryption algorithm. SHA-1 is one of many hash functions, including the mentioned MD5. It and other hash functions can be used in a HMAC (Hashed Message Authentication Code) but that is also not an encryption algorithm. DES, AES (Advanced Encrypyion System), Blowfish, Twofish, IDEA are encyption algorithms. See Schneier's site. or any crypto faq
I recommend you read Marshall McLuhan. Technology (what he calls media) is active, not passive: It changes how we react and can react to things.
While it may be the person who pulls the trigger, the fact that the gun is there allows for a form a violence that was not possible before its invention. The automobile is not sentient, but its availability allows for city structures / densities with large distances between points of interest, which make walking and public transint impractical. Highways, as a reaction to automobiles, hollowed out most US cities and brought urban blight as communities collapsed. The Internet (and telephone, and telegraph, and radio, etc.) allows for forms of communication that were not possible before, regardless of the actuall information being communicated.
What you're saying is if the bullets reach the right people for the right reason then guns can be good, but if the slugs hit the wrong person or for the wrong reason then they're bad. (If the right type of rays from a TV hit the right person's eyes than TV is good. If the right bits travel through the IP network and reach the right destination for the right reason the Internet is good.)
Doesn't the above sound a bit silly? A technology has an impact regardless of how it's used.
Firearms (or any technology) change our outlook on what is possible and perhaps even what is desirable.
To say that technology "isn't the culprit" is naive and simplistic IMHO.
And you cannot simply let slide a technology, because it does have an affect on how society functions. The technology changes the psyche of individuals and crowds, regardless of how it's used (or what information is transmitted,).
http://www.ningning.org/blog/?m=200503
Liberty freedom are no1, not dicks in suits.
http://www.ningning.org/blog/?m=200503
Btw re Firefox, why cant firefox 100% cache slashdot images and never re-read them from the server, or at last check weekly ONCE!!
Liberty freedom are no1, not dicks in suits.
I find it odd that the professor's nationality was placed prominently in the headline. I can see why the original paper would place that in the headline since it is a Chinese paper (of some sort). But the real point from a slashdot perspective is whether the algorithms have been cracked or not and the nationality isn't really part of the technical story. Unless there is some sort of political aspect to the story (which hasn't really been mentioned).
SHA-1 is a secure hash, not a cipher. It is an assurance that it will be computationally intensive to find a message that corresponds to a given digest. The claim in the article is rather vague. But nobody ever claimed that SHA was unbreakable. Merely doing "better than brute force" doesn't mean anything remotely like your basic TLS stream can be compromised. I expect when we hear the details, it will be something like, a 2**80 problem can be reduced to 2**64 for a given input (the attacks on SHA-0 are of such a nature).
-fb Everything not expressly forbidden is now mandatory.
Basically you just pad the document you want to match with spaces or baseX strings until the md5 matches the one you want to replace. Maybe I should RTFA... :)
I downloaded a piece of Encryption software on CNET and it mentions that SHA-1 and MD5 had been broken.
0 00-2092_4-10578367.html
The software is called '448 Bit Marx Encryption' and runs on Windows.
The release date was 14th Sept. 2006!
Here is the link:
http://www.download.com/448-Bit-Marx-Encryption/3
Any big group that operates as part of a government, particularly a government as enormous as that of the USA, WITHOUT extensive public oversight, will be hopelessly crippled by earmarking, cronyism, and all other manner of corruption and incompetence. I mean, if the NSA was worth half a shit in a tin can they'd have been able to stop people like McVeigh, Kaczynski, or the doofuses* that thought it would be a good idea to hijack a few planes.
A handful of really bright people working on a project that they truly care about can perform miracles of creativity and insight. If governments really want to get things done, they need to focus more on identifying those people and giving them the support they need -- whether it's a research grant, a loan with which to start a small business, or even just an environment where creativity and hard work are appreciated and respected. A "keep up the good work" now and then can go a long, long way (a woman I talked to who worked in HR suggested that a bit of respect and encouragement could easily avert 90% of the labour issues that her department dealt with BEFORE they became severe enough that HR had to waste time and money on them).
* Doofuses? Just look how well that has worked out for their feelow Muslims... their 70 virgins are probably going to turn out to be 70 desperate truckers with a taste for the dark meat...
The writing in this story has got to be the worst, most horrendous writing of any technical story I have ever read in my life.
To summarize the *real* story as I know it so far, this lady (and her team) has weakened MD5, RIPEMD, and SHA-0 to the point of being useless (i.e., she is able to easily construct artificial collisions) in August of 2004. A year later in 2005, she showed that SHA-1 is significantly weaker than its advertised strength, however she did *NOT* fully weaken it (i.e., she, nor anyone else, has yet found a collision). It is widely assumed in the crypto community, however, that work along similar lines are likely to eventually weaken SHA-1 to the point of being as weak as SHA-0 is now. People like Bruce Schneier and others have already publically stated that we should stop using SHA-1 for any new algorithms. So it does not in any way surprise me that the Chinese government is going to stop using SHA-1 -- *EVERYONE* should stop using SHA-1 where it is possible. This is actually a real problem, BTW, since there are no well tested 160-bit secure hash algorithms available as substitute. The best candidate choices are things like Whirlpool (based on AES), but this algorithm has not been subjected to serious scrutiny yet. My personal preference, is to try to give myself some breathing room, and I've gone ahead and just shifted to 256 bits with SHA-256.
Now this piece of broken writing comes out. Can someone please tell me -- has Wang produced more results, or is this just a terribly written recap of events we are already aware of?
Actually, you don't know what you're talking about. Go read "Multicollisions in Iterated Hash Functions. Application to Cascaded Constructions" by Antoine Joux. Unfortunately, it's not generally available online, but Hal Finney wrote a nice explanation of the problem here.
http://outcampaign.org/
Thanks, that's really useful. I had not seen that before.
>north
You're an immobile computer, remember?
http://en.wikipedia.org/wiki/Xiaoyun_Wang
I think the grandparent poster was asking something different. He wants to know how hard it is to create an evil binary that has the same hash as some preexisting non-evil binary, assuming that you have no control over the contents of the non-evil binary. The answer, as I understand it, is that this is still quite intractable. It's easy to create two *new* messages which collide, but it's very hard to create a message which collides with some specific existing message.
IMO, attacks like the one you describe are not actually very interesting. Signing executable code (including postscript) which you did not create yourself is asking for trouble, whether or not your hash is broken. Someone could just as easily write a program which behaves differently depending on, say, the current time. So, today you sign that check for 50 cents and tomorrow the same check -- still signed -- claims to be for $1,000,000. No collisions needed.
Do you know of any better examples of ways to exploit hash collisions?
Is there any actual proof that this person has actually cracked it?
//obligutory
We remember the other turnip from that land who claimed all that stuff he had done on stem cell research only to be declared a fraud and charlatan, stripped of his title and given a good old ear bashing.
I want to beleive....
Your post is much better than my "score:4 informative" post. Well done.
People who dislike China tend to mention Tiananmen Square a lot, but they always forget the Tank Man is also a Chinese.
Dude, I don't know whether or not she cracked SHA-1, but, as brilliant, 39-year-old, female mathematics professors go, this chick is HOT!!!
Man, what I wouldn't do to make babies with a chick like that...
Dude, I don't know whether or not she cracked SHA-1, but, as brilliant, 39-year-old, female mathematics professors go, this chick is HOT!!!
Man, what I wouldn't do to make babies with a chick like that...
I had always wondered what the deal with tenure was. Thank you for your excellent post. It was very informative.
That's like saying the cipher formerly known as RC4 isn't a cipher because it generates a stream of bits and then XORs them against the plaintext to produce ciphertext. Most common stream ciphers do that.
" Though it's not absolutely certain, my guess is that the reality behind the new announcement is that [...snip...] "
There is no new announcement. No new paper published, no new conference presentation, nothing mentioned on the crypto lists and newsgroups... absolutely nothing anywhere. The professor's own webpage doesn't mention anything more recent than 2005.
The Epoch Times story is the only thing that has been published and they're just two years behind the news. End of no-story.
People can choose to do good things or do bad things.
But, if you could do something so that people were not able to make the bad choice at all, would you do it?
In the extreme case, a guy with a gun is robbing a bank and has hostages. Now, he can choose to shoot the hostages, or he can choose not to shoot the hostages. If you had the opportunity to shoot the robber dead so he can't choose to shoot the hostages, would you?
People can choose to drink and drive or not drink or not drive. If there was an inexpensive, perfect piece of technology that was convenient and stopped some people from driving drunk and never stopped sober people from driving, would you require people to install it in their cars?
Yes, people have choice. But some people will choose to do bad things. Saying that the murderer is responsible for killing the victim doesn't stop people from killing victims.
Some choices people shouldn't be allowed to make.
paintball
I'm very newbish on crypto but I feel I have to ask these questions:
1) So now that MD5 is done for, what's next?
2) She said that she had to manually write algorthiums to crack MD5... does that mean she can do it again or with a computer? For that matter, how long does it take her to do it again? If it takes 5 years to crack one password, is it something to worry about?
please... let me sleep... a little more... yay, no longer annonmyous coward.
PC World commented on the issue in 2005
Also Bruce Schneier wrote about it back then.
I guess it takes a while for the US government and Microsoft, et al to take action on the news.
Well, the postscript example is possible to exploit in a context that's not quite so contrived...
In Mercurial, revisions are identified with hashes of their contents. So, you can submit a change to something like a postscript file that nobody will review the source of. Then, later, you can trick someone involved in the project from pulling a repository copy from you that has the evil version of the Postscript file. With any luck, you can get the evil version to infect the project with nobody realizing it until someone notices the strange behavior.
The problem is that the submission is likely to eventually be traced back to you once the strange behavior is noticed. But the reputation of the project would be severely tarnished and you might be able to get access to the systems of various people who used it.
It would be surprisingly hard to exorcise the bad version from the various distributed repositories. You'd have to just replace the file and state that any version before X is potentially infected. And even then a badly done merge might easily re-introduce the file.
This is basically a trickier way to get someone else to sign something for you.
And the case of a certificate authority is interesting too. The very nature of a CA is to sign documents made by someone else.
But, no, I can't really think of situations in which its really useful unless the attacker is in some way getting someone else to lend their authority or reputation to the attacker.
Need a Python, C++, Unix, Linux develop
"I mean, if the NSA was worth half a shit in a tin can they'd have been able to stop people like McVeigh, Kaczynski, or the doofuses* that thought it would be a good idea to hijack a few planes."
... this really isn't that much of a stretch. It is hard for people without a certain moral flexibility to fully understand however, which is why it never gets traction.
And what better way to convince the people who sign your checks (i.e. congress) to give you lots of funding than to get most of 'em, but let a few slip by? I'm not advocating wild conspiracy theories, but come on
Pretend for a moment that you're willing to sacrifice a few hundred, or a few thousand, to justify hundreds of millions in funding. People that run these groups are willing to do just that.
ECC is a potential replace for RSA, an asymmetric cryptographic algorithm. It still requires a hash function.
Finkployd
Bin Laden is an entirely different manner of thing. If Al Qaeda wanted to slaughter the infidels, they'd just DO it. There are more than enough Americans living abroad that they could kill thousands every month. But that's not what they want. They want to accomplish a particular set of political goals: they want America to abandon Israel, they want America to remove it's military bases from "the holy land" (ie: the entire middle east), and a few other bits of ridiculous nonsense. And what has happened? America now has a major military presence in Iraq and an increased military presence in other allied middle-eastern nations. America is now less likely than ever to turn against Israel -- Israel is the West's ace in the hole. A trump card to played if things ever get too desperate. And an entire muslim government has been basically destroyed (the Taliban isn't quite out of it yet, but they're close). Pakistan is practically a puppet of the US now, and that kind of tolerant atmosphere can only lead to horrors like bilateral trade deals and human rights agreements.
So what we see is that Bin Laden has accomplished precisely the opposite of anything that is, from the perspective of Islamic extremists, positive. Radical Islam has taken a severe blow; there is now MORE democracy and LESS Islamic theocracy in the world. Being a muslim is on about the same level as having leprosy throughout most of the world. The "holy land" is being trampled by boots that have "Made in America" written in relief in the sole.
So what do we call people like Osama Bin Laden, who fuck up so completely and utterly? To call them doofuses is about as nice as it gets. Most other suitable terms would not be appropriate to use in front of children.
Meanwhile, the Bush government has accomplished EXACTLY what they have intended to, more or less. They have used fear to control the American people. They have used patriotism, cowardice, religion, bigotry, lies, and non-stop propaganda to dupe the people into waging a war. The goal? To let companies like Halliburton rape the United States for trillions of dollars in tax money. Funny how most of the major members of the Bush government are closely tied to the businesses that are being paid out of YOUR pocket for the reconstruction of Iraq, huh?
Everything that's happened has been in accordance with what is best for people like Bush and Cheney. Even when their government falls, America will still be in Iraq, and will still be stealing money from YOUR pocket to pay Bush and Cheney's business interests to rebuild Iraq. They'll be making incredble amounts of money for years or decades to come. Actually holding power is irrelevant once they've gotten things lined up how they want them.
Bush and Cheney are the ones that set the trap. The victims? Muslims (who are trapped in the middle of all of this). The American people -- who are having their hard-earned income stolen with basically NOTHING to show for it. And I'd even go so far as to say the Republican party -- who are gradually becoming Pariahs because of the corruption and evil of the GOP. As much as I oppose Republican politics, I can't help but feel bad for sane and reasonable Republicans, who are being blamed for what a handful of greedy monsters and religious psychopaths are doing.
- Lebensraum for me and my children
- Access to the oil-fields of central Asia
- Preventing the enemy from installing ICBMs just a few miles off our shore
- Control of the mediterranean tin trade
- Forcibly opening a market to our products
- They're-different-than-us-and-that-pisses-me-of
f -because-deep-down-I'm-still-a-retarded primate
- Etcetera
Many of these conflicts were wrapped in religious or racial terms. But religion and race were absolutely tertiary. It all actually comes down to politics.All war is political. It can never be any other way. And Bin Laden is just a particularly bloody-minded and ineffectual politician (any politician that has to live in a cave is a failure). Think about it this way: anyone who releases propaganda is a politician. Pat Robertson? Totally political. He doesn't give a shit about god (if he did, he wouldn't use the lord's name in vain on a daily basis). He's just a big blowhard who's trying to exert political influence. When Bush babbles like a retarded chimpanzee about being God's personal messenger on Earth, that's just his way of duping idiots into voting for him. When Bin Laden grossly misinterprets and selectively edits the Koran, he's just trying to get chumps to do his dirty work for him.
I've read several articles over the past couple years about this or that encryption method broken... can someone who has kept up let me know what is still safe? AES? I'm kinda lost, I just want the executive summary of 'use this, this, or this', rather than 'this isn't safe, that isn't safe'. I'm looking for a positive list (what still works) rather than a negative list (this was broken, that is no longer secure).
I've looked around on Google, but I keep finding negative articles rather than something listing the encryption methods that haven't yet been broken.
Thanks.
"I will trust Google to 'do no evil' until the founders no longer run it." Hello Alphabet.