Crack in Computer Security Code Raises Red Flag

March 15, 2005
Crack in Computer Security Code Raises Red Flag
Obscure but Worrying Flaw Compromises 'Fingerprint' Widely Used on
Internet
By CHARLES FORELLE
Staff Reporter of THE WALL STREET JOURNAL

With worries about online security already at a high pitch, the
discovery of a crack in a widely used Internet encryption technique has
raised another red flag among government agencies and computer-code
experts.

The technique, called a "hash function," has been used for years by
Web-site operators to scramble online transmissions containing
credit-card information, Social Security numbers and other sensitive
data. Hash functions are at work, for instance, for most of the
millions of transactions that take place on the Internet every day. The
system, involving an algorithm, or mathematical formula, was thought to
be impenetrable.

But last month, a team of researchers from Shandong University in
eastern China began circulating a draft of a paper showing that a key
hash function used in state-of-the-art encryption could be less
resistant to an attack by hackers than had been thought.

Hash functions generate digital fingerprints, or "hashes," of documents
or data. As with fingerprints, the uniqueness of the hash is what makes
hash functions a great tool for verifying the authenticity of
information.

But the Chinese team found different pieces of data that yielded the
same hash when team members used a hash algorithm called SHA-1 -- and
their method generated the identical hash far more efficiently than
experts thought possible. SHA-1 is a federal standard promulgated by
the National Institute of Standards and Technology and used by the
government and private sector for handling sensitive information. It is
thought to be the most widely used hash function, and it is regarded as
the state of the art.

Cryptographers say exploiting the flaw for malevolent purposes doesn't
seem practical, even using a lot of computer power. Hash functions are
also often used in conjunction with other cryptographic techniques,
which haven't shown any flaws. But if someone were to exploit the
newfound flaw, the most immediate threat would be to applications
involving "authentication." A hacker theoretically 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.

Despite what are believed to be remote chances of abuse, the discovery
has set off alarms in the computer-security industry because it
overturns a bedrock belief about a popular encryption system. "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." PGP has begun to replace SHA-1 in its programs.

Another provider of widely used security systems, RSA Security Inc. of
Bedford, Mass., is doing an inventory of its products to see how they
use SHA-1 with an eye toward phasing it out. (RSA makes the popular
SecurID cards used by many companies to ensure that only employees have
remote access to computer networks.) The National Institute of
Standards and Technology recommends not using SHA-1 in any new
applications and is instructing federal agencies to develop plans for
removing it from existing ones.

The Chinese team hasn't published its paper on SHA-1, but the flaw is
"real," says Bruce Schneier, a cryptographer and chief technology
officer of Counterpane Internet Security Inc., who has seen a draft of
the paper. "Academically, this is stunning work."

The Chinese researchers "haven't caused panic yet," says Avi Rubin, a
computer-security expert at Johns Hopkins University. But "it's
definitely a wake-up call."

The discovery follows recent research showing flaws in other hash
functions. And it comes at a time when information-security concerns
have been sharply heightened by problems not involving hash functions.

Recent breaches at data aggregators ChoicePoint Inc. and Reed Elsevier
PLC's LexisNexis exposed personal data on more than 100,000 Americans
to identity thieves. And a poorly designed online system allowed scores
of business-school applicants earlier this month to view decision
letters ahead of time.

Hash functions take a piece of data -- anything from an e-mail message
to a giant database file -- and generate a short string of ones and
zeros, 160 of them in SHA-1, that functions as the datum's unique
fingerprint. Nothing else should generate the same "hash," and a person
in possession of only the hash can't figure out what the e-mail said or
what the database contained.

Those properties make hash functions well-suited to "authentication" --
they are used to make sure the Web site to which you send money
actually belongs to, say, your bank or credit-card company -- not some
rogue operator out for a scam. Hash-function-based authentication is at
the core of "digital signatures" used to verify the identity of users
producing documents or e-mail messages.

Two different chunks of data yielding the same hash is known as a
"collision," and the Shandong team found the one in SHA-1 far faster
than thought possible. Their work hasn't shown any instances of a more
serious flaw that would enable attackers to create duplicating hashes
for their choice of data.

Burt Kaliski, vice president of research at RSA Security, says
collisions don't greatly affect many applications of hashing. But it's
possible, he says, that a person presenting you a document to be signed
digitally with a hash has secretly created a second document designed
to "collide" with the first. Then, by signing the first, you're
unknowingly also signing the second.

Also worrying cryptographers is a stream of recent hash compromises. At
a conference in August, problems were reported with MD5, widely used to
ensure integrity of computer data, and other, lesser-used functions.
And a French researcher threw cold water on the commonly held belief
that using two hash functions is more secure than using one.

Recent research has also showed that MD4, long known to have problems,
was so weak that collisions could be found with a few hand calculations
-- no supercomputer required. A Czech cryptographer using the Chinese
method claimed this month to have found collisions in MD5 in only eight
hours on a standard laptop.

Hash functions are perhaps the least well understood cryptographic
functions, cryptographers say. The functions perform a bunch of math on
a piece of data, switch the order of some bits, chop the result down to
a fixed length and spit out the fingerprint. Basically, "you stir it
all around and hope you can't unstir," says Mr. Schneier.

The National Institute of Standards and Technology says it recommends
moving to improved variants of SHA-1 that generate a longer hash,
making it harder to find collisions. The National Security Agency says
SHA-1 is fine for now, but should be phased out by 2010.

But Mr. Schneier and some other top cryptographers believe federal
agencies and academic researchers need to develop entirely new flavors
of harder-to-break hash functions. "All the red flags are up for the
SHA family," says Arjen K. Lenstra, a researcher at Lucent Technologies
Inc.'s Bell Labs. "We can no longer trust them."

SHA-1 was based on MD5, which came from MD4. Xiaoyun Wang, the lead
author of the SHA-1 paper, says her team's method "does not seem to
apply directly" to the stronger SHA variants. Still, in an e-mail she
recommends developing "different style algorithms." The small team's
work has been presented at respected cryptography conferences and its
hash-function paper, while unpublished, has been reviewed in draft form
by experts.

Experts say the research weighs particularly on the technology
underlying secure Web sites. An online-banking site, for example,
displays a "certificate" of authenticity to a Web browser, which then
compares it, using hashes, to a third-party certificate repository to
be sure the site actually belongs to the bank.

Mr. Lenstra and colleagues used the Chinese method to produce two
different certificates with the same hash -- something that shouldn't
happen. The certificates aren't for real sites.

=============================================

MrPepper11

MrPepper11 wrote:
> March 15, 2005
> Crack in Computer Security Code Raises Red Flag
> Obscure but Worrying Flaw Compromises 'Fingerprint' Widely Used on
> Internet
> By CHARLES FORELLE
> Staff Reporter of THE WALL STREET JOURNAL

Way to report LAST MONTHS news....

Newsflash: xenophobia != good for a news agency...

Tom

tomstdenis@gmail.com

wrote:

> MrPepper11 wrote:
>
>>March 15, 2005
>>Crack in Computer Security Code Raises Red Flag
>>Obscure but Worrying Flaw Compromises 'Fingerprint' Widely Used on
>>Internet
>>By CHARLES FORELLE
>>Staff Reporter of THE WALL STREET JOURNAL
>
>
> Way to report LAST MONTHS news....
>
> Newsflash: xenophobia != good for a news agency...
>
> Tom
>
Last month. That is very recent for newspaper reports on pure science.

Andrew Swallow

Andrew Swallow

On 15 Mar 2005, postulated in
news: oups.com:

>
> MrPepper11 wrote:
>> March 15, 2005
>> Crack in Computer Security Code Raises Red Flag
>> Obscure but Worrying Flaw Compromises 'Fingerprint' Widely Used on
>> Internet
>> By CHARLES FORELLE
>> Staff Reporter of THE WALL STREET JOURNAL
>
> Way to report LAST MONTHS news....
>
> Newsflash: xenophobia != good for a news agency...
>
> Tom
>
>

I don't share your sense of superiority because another article on
this discovery was posted here a few weeks ago. "Last month's" news
is entirely relevant to today's encryption standards and we have yet
to feel the ramifications of this discovery to the computer industry
as a whole.

Also, this article explains the problem in detail and presents the
issue fairly and honestly. I did not get this sense from the other
article on this discovery, posted here last month.

I don't understand your comment about xenophobia, unless you felt,
perhaps, that the Times article shouldn't have named the nationality
of the researchers?

More interesting to me would be to learn, what if anything, are
people are doing about this? I recently changed the code of a web-app
in development to use SHA256 for password hashing (instead of SHA1)
and I'm considering retrofiting a couple of apps that are in use.

How about you?

-- ipgrunt

IPGrunt

IPGrunt <> writes:
> More interesting to me would be to learn, what if anything, are
> people are doing about this? I recently changed the code of a web-app
> in development to use SHA256 for password hashing (instead of SHA1)
> and I'm considering retrofiting a couple of apps that are in use.
>
> How about you?

I think it's not worth retrofitting old applications, especially for
things like passwords, which are relatively low security to begin
with. And for the long term, some of us are concerned that even the
SHA2 hashes (SHA256/384/512) aren't secure enough, because of how
their design works. So we working cryppies continue to use SHA1 for
the time being while waiting for standards bodies, CA organizations,
and so forth, to reach consensus about the SHA1 situation and deploy a
replacement.

Paul Rubin

IPGrunt wrote:
> I don't share your sense of superiority because another article on
> this discovery was posted here a few weeks ago. "Last month's" news
> is entirely relevant to today's encryption standards and we have yet
> to feel the ramifications of this discovery to the computer industry
> as a whole.

"encryption standards" is exactly the sort of comment someone who
doesn't understand the field would say... It's a hash not a cipher
[well they're ciphers used for hashing...but that's too technical].

> Also, this article explains the problem in detail and presents the
> issue fairly and honestly. I did not get this sense from the other
> article on this discovery, posted here last month.

My complaint is that "yet another" article about something that isn't
officially public yet is kinda moot.

> I don't understand your comment about xenophobia, unless you felt,
> perhaps, that the Times article shouldn't have named the nationality
> of the researchers?

Well yes, that was part of it. Also early reports were calling them
"hackers" and other such negative things...

> More interesting to me would be to learn, what if anything, are
> people are doing about this? I recently changed the code of a web-app

> in development to use SHA256 for password hashing (instead of SHA1)
> and I'm considering retrofiting a couple of apps that are in use.
>
> How about you?

I've hated SHA-2 since the day it came out. It's yet another lateral
move for the crypto standards bodies and frankly there isn't much use
for it.

Tom

tomstdenis@gmail.com

While the flaw does exist and that flaw is directly related to the hash
mechanism,exploiting this is not simple. There was a lot of discussion
on this, when the paper was initially released. I have read the
original paper that describes the hash flaw. I believe Mr. Rubin gives
sound advice. I might not rely on the encryption for secrets, for the
routine, and for now, it is probably sound enough.

Winged

winged

The "attack" , while at the current edge of feasible computing really
is not
meaningful, even when it is carried out. Even if improved to 2^50 or
so it
would not be meaningful.

Why?

Because the attack does not construct messages that are either
meaningful,
or are related in any way. i.e. if I want to sign a letter, one
would presuppose that
the letter would consist of English text. A random string of bits will
not be English text.
Of course, if you are signing random data, then the attack is
meaningful.

Suppose I wanted to send a letter to my stockbroker saying "Buy".
The stock takes a nose dive and I want to repudiate my letter. How do
I then
find two messages M1 and M2 such that both are meaningful text, M1
contains
"Buy" and M2 contains "Sell"? The current attack does not allow
this.

It is not a pre-image attack. And even if it were a pre-image attack,
I can't
imagine that I could find M2 such that Hash(M2) = Hash("Buy") AND

M2 contains a meaningful message saying "Sell". M2 is going to be a
random
(or nearly so) string of bits.

Pubkeybreaker

On 15 Mar 2005 05:50:43 -0800, in alt.computer.security "MrPepper11"
<> wrote:

>But the Chinese team found different pieces of data that yielded the
>same hash when team members used a hash algorithm called SHA-1

If the hash is shorter than the source (as they generally are), than
it is an utter certainty that different bit strings with the same
signature must exist. These are called "hash collisions".

Actually, it's fairly simple to generate two colliding bit strings;
some strings will have far more collisions than others. You have a
problem with your hash function when, given an original bit string,
there is an easy method of generating another string with which it
collides.

If you look ar SHA-1, you're left asking: "How do we *know* it's a
good hash?" How do we know that all of those so called "round
functions" are really doing their job? For that matter, how do we
know that it's hard to factor large numbers? It has never been proven
that algorithms of linear order don't exist. Someday, some grad
student is going to deliver a paper that'll turn the crypto community
on its ear!

Hell, I think it's exciting.

Jones

!Jones

wrote:
> Well yes, that was part of it. Also early reports were calling them
> "hackers" and other such negative things...

Let me correct this a bit. I don't think "hacker" is a negative word.
I think the way the media uses it [e.g. that hacker can forge messages
in your name] is bad.

Moreso, they're cryptographers not hackers. Hackers are the types of
folk who see how things work together and build things in an almost
playful sense. Cryptographers [in this case] analyze protocols and
break things by finding flaws.

Tom

tomstdenis@gmail.com