Posted on 03/16/2005 5:29:28 PM PST by Golden Eagle
Internet security takes a hit
Report says computer-code experts concerned after flaw discovered in popular encryption technique.
NEW YORK (CNN/Money) - The discovery of a crack in a commonly used Internet encryption technique raised concerns among government agencies and computer-code experts, according to a report by The Wall Street Journal.
"Our heads have been spun around," Jon Callas, chief technology officer at encryption supplier PGP Corp., told the newspaper.
The technique, called a "hash function," has been commonly used by Web site operators to scramble online transmissions containing credit-card information, Social Security numbers and other personal information.
Hash functions were thought to be impenetrable, but a team of researchers in China found that this encryption method was not as resistant to hackers than previously thought, according to the report.
(Excerpt) Read more at money.cnn.com ...
Huge? Not much info has come out since it was announced yesterday.
Vulnerability found in encryption method (India)
http://news.newkerala.com/india-news/?action=fullnews&id=86355
[World News]: NEW YORK, March 15 : Chinese researchers have found a flaw or vulnerability in a widely used Internet encryption technique, the Wall Street Journal said Tuesday.
A team of researchers from Shandong University in eastern China have found a way to replicate the digital fingerprints or "hashes" of documents of data by using an algorithm called SHA-1, a U.S. standard promulgated by the National Institute of Standards and Technology for use with sensitive information.
The most immediate threat of the new-found vulnerability would be to applications involving "authentication," experts say A hacker could set up a dummy Web site that appears to have the security credentials of a trusted, secure site -- and then steal data that is shipped to this site by unsuspecting users.
The discovery of the SHA-1 vulnerability has set off alarms in the computer-security industry.
"Our heads have been spun around," says Jon Callas, chief technology officer at encryption supplier PGP Corp.of Palo Alto, Calif."Everything is now topsy-turvy."
Pretty vague report.
I thought the SHA-1 vulnerability was announced about a month ago.
Anyone have any idea what sort of encryption SHA-1 uses? Is this the RSA public key type encryption? Seems to me breaking that would be a pretty significant mathematical feat.
I think SHA-1 was announced previously, but I didn't see that in the original article. It was in the second article I found from India though, so maybe this is the previously announced issue.
Now we're getting somewhere...
Schneier on Security
http://www.schneier.com/blog/archives/2005/02/cryptanalysis_o.html
Cryptanalysis of SHA-1
On Tuesday, I blogged about a new cryptanalytic result -- the first attack faster than brute-force against SHA-1. I wrote about SHA, and the need to replace it, last September. Aside from the details of the new attack, everything I said then still stands. I'll quote from that article, adding new material where appropriate.
One-way hash functions are a cryptographic construct used in many applications. They are used in conjunction with public-key algorithms for both encryption and digital signatures. They are used in integrity checking. They are used in authentication. They have all sorts of applications in a great many different protocols. Much more than encryption algorithms, one-way hash functions are the workhorses of modern cryptography.
In 1990, Ron Rivest invented the hash function MD4. In 1992, he improved on MD4 and developed another hash function: MD5. In 1993, the National Security Agency published a hash function very similar to MD5, called SHA (Secure Hash Algorithm). Then, in 1995, citing a newly discovered weakness that it refused to elaborate on, the NSA made a change to SHA. The new algorithm was called SHA-1. Today, the most popular hash function is SHA-1, with MD5 still being used in older applications.
One-way hash functions are supposed to have two properties. One, they're one way. This means that it is easy to take a message and compute the hash value, but it's impossible to take a hash value and recreate the original message. (By "impossible" I mean "can't be done in any reasonable amount of time.") Two, they're collision free. This means that it is impossible to find two messages that hash to the same hash value. The cryptographic reasoning behind these two properties is subtle, and I invite curious readers to learn more in my book Applied Cryptography.
Breaking a hash function means showing that either -- or both -- of those properties are not true.
Earlier this week, three Chinese cryptographers showed that SHA-1 is not collision-free. That is, they developed an algorithm for finding collisions faster than brute force.
SHA-1 produces a 160-bit hash. That is, every message hashes down to a 160-bit number. Given that there are an infinite number of messages that hash to each possible value, there are an infinite number of possible collisions. But because the number of possible hashes is so large, the odds of finding one by chance is negligibly small (one in 280, to be exact). If you hashed 280 random messages, you'd find one pair that hashed to the same value. That's the "brute force" way of finding collisions, and it depends solely on the length of the hash value. "Breaking" the hash function means being able to find collisions faster than that. And that's what the Chinese did.
They can find collisions in SHA-1 in 269 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.
In 1999, a group of cryptographers built a DES cracker. It was able to perform 256 DES operations in 56 hours. The machine cost $250K to build, although duplicates could be made in the $50K-$75K range. Extrapolating that machine using Moore's Law, a similar machine built today could perform 260 calculations in 56 hours, and 269 calculations in three and a quarter years. Or, a machine that cost $25M-$38M could do 269 calculations in the same 56 hours.
On the software side, the main comparable is a 264 keysearch done by distributed.net that finished in 2002. One article put it this way: "Over the course of the competition, some 331,252 users participated by allowing their unused processor cycles to be used for key discovery. After 1,757 days (4.81 years), a participant in Japan discovered the winning key." Moore's Law means that today the calculation would have taken one quarter the time -- or have required one quarter the number of computers -- so today a 269 computation would take eight times as long, or require eight times the computers.
The magnitude of these results depends on who you are. If you're a cryptographer, this is a huge deal. While not revolutionary, these results are substantial advances in the field. The techniques described by the researchers are likely to have other applications, and we'll be better able to design secure systems as a result. This is how the science of cryptography advances: we learn how to design new algorithms by breaking other algorithms. Additionally, algorithms from the NSA are considered a sort of alien technology: they come from a superior race with no explanations. Any successful cryptanalysis against an NSA algorithm is an interesting data point in the eternal question of how good they really are in there.
For the average Internet user, this news is not a cause for panic. No one is going to be breaking digital signatures or reading encrypted messages anytime soon. The electronic world is no less secure after these announcements than it was before.
But there's an old saying inside the NSA: "Attacks always get better; they never get worse." Just as this week's attack builds on other papers describing attacks against simplified versions of SHA-1, SHA-0, MD4, and MD5, other researchers will build on this result. The attack against SHA-1 will continue to improve, as others read about it and develop faster tricks, optimizations, etc. And Moore's Law will continue to march forward, making even the existing attack faster and more affordable.
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.
It's time for us all to migrate away from SHA-1.
Luckily, there are alternatives. The National Institute of Standards and Technology already has standards for longer -- and harder to break -- hash functions: SHA-224, SHA-256, SHA-384, and SHA-512. They're already government standards, and can already be used. This is a good stopgap, but I'd like to see more.
I'd like to see NIST orchestrate a worldwide competition for a new hash function, like they did for the new encryption algorithm, AES, to replace DES. NIST should issue a call for algorithms, and conduct a series of analysis rounds, where the community analyzes the various proposals with the intent of establishing a new standard.
Most of the hash functions we have, and all the ones in widespread use, are based on the general principles of MD4. Clearly we've learned a lot about hash functions in the past decade, and I think we can start applying that knowledge to create something even more secure.
Hash functions are the least-well-understood cryptographic primitive, and hashing techniques are much less developed than encryption techniques. Regularly there are surprising cryptographic results in hashing. I have a paper, written with John Kelsey, that describes an algorithm to find second preimages with SHA-1 Â-- a technique that generalizes to almost all other hash functions -- in 2106 calculations: much less than the 2160 calculations for brute force. This attack is completely theoretical and not even remotely practical, but it demonstrates that we still have a lot to learn about hashing.
It is clear from rereading what I wrote last September that I expected this to happen, but not nearly this quickly and not nearly this impressively. The Chinese cryptographers deserve a lot of credit for their work, and we need to get to work replacing SHA.
And the last horse finally crosses the finish line. Let's give CNN a hand for being such a good sport, folks. And maybe a copy of the Applied Cryptography or at least Tom McCune's PGP FAQ.
We sure love our technology. But wouldn't it be cool if someone were able to take control of our robotic aircraft and turn them against us? Or shut down our linked systems? From power stations to street lights, is there any aspect of American life that isn't computer controlled? Down goes Wall street or maybe the airplanes Al Queda couldn't touch. Who needs a mad bomber when a virus or even a hacker can cause all displays in a new airliner like a B777 revert to the blue screen of death. Ironic name, there.
Yep, we sure do love our tech. Human pilots are obsolete. Get rid of the pilots and have robots fly our planes. Yeah, that'll be great!
What caught my eye was the comment from the CTO at PGP, the article was pathetically vague, for sure.
All classical encryption (not quantum) is breakable by brute force. If your message says "we bomb beijing in five minutes" and it takes ten minutes for them to decrypt it, it worked.
Just about anything's possible, with enough money.
It seems like you have a small problem in the transcription of Schneier's article. Doesn't he mean that the cracking time has been reduced from 2 to the 80th power to 2 to the 69th power? I think the superscripting got lost.
If this doesn't wake a little American Pride nothing will.
I think that is correct, on the order of 2000 times easier, according to something I just read (but no longer have available, sorry).
Wow. For a minute there I thought it really had been cracked. Then I realized its just the month same old paper about reducing the SHA-1 brute force from 2**80 to 2**69 that all but crypto researchers yawned about.
Unlike computer encryption, with military cryptography you require not only the key in use, you also require the actual equipment used.
This is why John Walker deserves the death penalty. When he was actively spying for the Soviet Union, he provided them with both the keys and the hardware.
Tech Ping
Disclaimer: Opinions posted on Free Republic are those of the individual posters and do not necessarily represent the opinion of Free Republic or its management. All materials posted herein are protected by copyright law and the exemption for fair use of copyrighted works.