Article

Secure hash functions: Whither in 2005?

Nadia Ilyin, Contributing Writer

Recent announcements of the "breaking" of the SHA-1 hash function, hard on the heels of successful attacks on the MD5 and SHA-0 algorithms last year, surprised the cryptography community [and possibly the NSA], who expected it, but not so soon. Will 2005 also be, as Adi Shamir said of 2004, another "year of the hash function?"

The SHA-1 function is widely used for digital signatures in such applications as e-mail and Web browsers. Though experts agree this

    Requires Free Membership to View

attack method by China's Shandong University researchers should be viewed more as an academic milestone than as an immediate threat to application security, it did introduce new tools.

A hash function operates on a message -- which might be random characters, an e-mail, a software binary, etc. -- to produce a message digest, or hash. These functions have two security properties: it is extremely difficult to find two messages that produce the same hash value [collision resistant]; and they are one way, meaning that given a message digest, one cannot reconstruct the original document.

So the loose term "broken" must be refined to say which of these two properties is broken, and how badly. The SHA-1 function produces a hash 160 bits long. In theory,

Read more

An introduction to SSH2
The differences between SSH1 and SSH2, and why you should consider the upgrade.

Cryptography basics for infosecurity managers
Let's face it
cryptography is intimidating. The idea that cryptography is full of complicated mathematical algorithms causes IT managers to shy away from it and delegate responsibility without truly understanding what's going on behind the scenes.

it should take 2^80 comparisons before two identical, random message hash results are found. That is several years' work for a huge number of cooperating PCs or one very powerful supercomputer -- although as computers become faster, the time becomes shorter.

The recent SHA-1 break is a collision in which two random, non-meaningful messages were found to have the same hash in 2^69 comparisons, or about 2000 times faster than the brute-force method. That is still a very long job. Furthermore, the researchers applied some constraints on what the input message can look like in order to achieve this result.

Breaking the one-way property -- reconstructing the original message -- is much harder. Finding a second pre-image is harder still, and according to Dr. Burt Kaliski, chief scientist at RSA Laboratories, "there is no suggestion here that that is possible."

"The discovery of these tools opens new avenues to researchers," Kaliski said, adding that we can expect to see "thorough analysis of SHA through the rest of this year, and likely incremental improvements on this result."

Even if breaking a digital signature were possible, each one would still be a big effort, and "an attack on software distribution, such as patches or ActiveX controls, seems more likely than one on e-mail," opined security consultant Olin Sibert of Oxford Systems, "since many users may trust a single software download signature."

Kaliski believes one should look for additional ways to defend against this sort of real-world threat.

For instance, SHA-1 is the most used descendent of a family of algorithms that began with Ron Rivest's MD4 in the early 1990s. Later versions that produce longer message digests and are thus harder to break are collectively called SHA-2. The National Institute of Standards and Technology [NIST] previously recommended migration to SHA-2 by 2010. Kaliski believes NIST is unlikely to move that date up, since it would take almost that long to implement a changeover anyway.

Migration to SHA-2 "is a good stopgap, but I'd like to see more," Bruce Schneier of Counterpane Internet Security commented in his blog. "I'd like to see NIST orchestrate a worldwide competition for a new hash function" not based on the MD4 family. Kaliski concurred: "I'm not suggesting we abandon present algorithms, but it's good to have diversity in our approaches."


There are Comments. Add yours.

 
TIP: Want to include a code block in your comment? Use <pre> or <code> tags around the desired text. Ex: <code>insert code</code>

REGISTER or login:

Forgot Password?
By submitting you agree to receive email from TechTarget and its partners. If you reside outside of the United States, you consent to having your personal data transferred to and processed in the United States. Privacy
Sort by: OldestNewest

Forgot Password?

No problem! Submit your e-mail address below. We'll send you an email containing your password.

Your password has been sent to: