Subject: Re: SHA-1 broken

From: [email-masked]
Date: Thu, 17 Feb 2005 21:18:18 +0100

Werner Koch <[email-masked]> wrote on 17 Feb 2005:

 >We should really start thinking on how to switch to a different hash
 >algorithm.  The question is whether sha-256 is really that much more
 >secure.  From my understanding it has not been developed as a
 >replacement for SHA-1 but to meet the requirements of AES and to
 >extend DSA.

While not being opposed to David's suggestion of a potential V5 key
with AES/SHA-256, I still can't see any real need for replacing SHA-1
in the near future.

What are the actual facts behind these "SHA-1 is broken" rumours?
Someone found a way to reduce the SHA-1 strenght by 11 binary digits.
This has the exact same effect as if someone boosted the current
processor speeds by a factor of 2096.

Does this mean that any 128 bit hash gets "broken" by building a
cluster of 2096 PCs?

Let us be realistic and avoid any panic mode. Quickly announcing
changes to the OpenPGP protocol is doing us a bad service as it
undermines public trust for no good reason at all.

The recent announcement of Jon Callas et al. was - in my eyes - not
helpful at all. It solved a non-existing problem (not one single
existing OpenPGP implementation suffered from the "oracle" effect),
and the result in the media (at least in Germany) was rather
catastrophic: Even the (normally pretty conservative) Heise Verlag
published panic articles that "all automatic encrypt/decrypt systems
based on OpenPGP are broken"!

So the actual effect of the announcement was that, while not fixing
any real security problem, it seriously caused a Public Relations
damage for crypto gateways like our "KT Mail gateway"
(www.redtenbacher.de/info/gateway.htm) or "PGP Universal" (from PGP
Inc.).

Please, let us stop making any "change announcements" to the public if
there is not an actual security problem to be solved!

- Wolfgang Redtenbacher

---------------------------------------------------------------------
Redtenbacher Software                Tel.:   +49 7159 17046
Roemerstr. 11/1                      Fax:    +49 7159 17047
D-71272 Renningen                    e-mail: [email-masked]
---------------------------------------------------------------------

---

From: Ian G <[email-masked]>
Date: Thu, 17 Feb 2005 21:13:08 +0000

>processor speeds by a factor of 2096.

Right now, that's about it.  It looks like
the 'padding' issue is unimportant and
the only issue is the number of bits
of reduced strength.  So I don't think
we have to change SHA-1...

>there is not an actual security problem to be solved!

Well, I'm not sure anyone has made any
"change announcements" unless you mean
that recent minor oracle attack.

(off topic for the draft group...)

I would disagree in the question of making
announcements.  Recent research and
thinking has led to the notion that we have
to be very aggressive about announcing
our weaknesses and going OTT (over the
top) in how we present these weaknesses.
It seems that we have to go through a
period of actually revealing these things
and encouraging people not to panic.

Elsewise we go back to the bad old days
where we keep all quiet.

iang

-- 
News and views on what matters in finance+crypto:
        http://financialcryptography.com/

---

From: Jon Callas <[email-masked]>
Date: Thu, 17 Feb 2005 14:07:10 -0800

My feeling is that a key fingerprint is the *least* of the things that 
are in danger from a SHA-1 break.

A key fingerprint is little more than a hash of the key material, the 
creation time, and a few constants. There's very little place in there 
to manufacture a collision. Fingerprints need little more than 
one-way-ness.

Furthermore, it is imperative that a fingerprint be short. The whole 
reason for having them is that they are short. All the things you want 
a fingerprint for require it being short. Twenty bytes is plenty long 
enough for one. Otherwise just get rid of the fingerprint and just 
write down the key.

	Jon

---

From: Jon Callas <[email-masked]>
Date: Thu, 17 Feb 2005 17:46:54 -0800

> based on OpenPGP are broken"!

I'm sorry that the German press was so twitchy about it. I sent 
releases to both Reuters and UPI here, and got a polite response back 
from Reuters thanking me for being so humble about it. There's not been 
a further peep on it, and I've been waiting for it. Should this ever 
happen again, I'll try to make sure that the German press isn't silly. 
I know people who can do German translations -- not that I'm expecting 
to ever have to do that again, mind you.

I think it would have been less helpful, however, to do as a different 
organization did the previous week over a botched IV. They said that it 
wasn't worth fixing and no one needs that anyway and there was a storm 
of press over here.

	Jon

---

From: Konrad Rosenbaum <[email-masked]>
Date: Fri, 18 Feb 2005 08:16:37 +0100

> based on OpenPGP are broken"!

Since when is the Heise Newsticker "pretty conservative"? If they can draw 
attention to their website they will do it. 

You're free to contact them and ask for an update of that article... ;-)

	Konrad

---

From: Lutz Donnerhacke <[email-masked]>
Date: Fri, 18 Feb 2005 08:30:49 +0000 (UTC)

> to manufacture a collision. Fingerprints need little more than 

IBTD, sorry.

The recent attack allows to construct two "random" messages differing in
some (few) bits generating the same hash.

So a possible attack might be to generate such a collision and search one of
the messages in existing key material from the key servers. If some key was
found containing one of those sequences, it can be replaced by a different
key by changing those few bits.

This manipulation does not change the fingerprint and might not change the
key signature nor the user certificates, so the modified key is a drop in
replacement for the old one.

The main advantage for the attacker is, that the modified key might be easily
factorised. Very likely. So the attacker can mount a MITM attack using the
web of trust to hide it.

Bad news.

---

From: Werner Koch <[email-masked]>
Date: Fri, 18 Feb 2005 12:46:49 +0100

> I'm sorry that the German press was so twitchy about it. I sent

I only know the Heise report (ct magazine and the most known IT news
ticker).  Their article[1] didn't talk about a practical attack or
spread panic - don't known about the trolls on their forum; I don't
read that.  The article was quite okay.  They even didn't call me -
what they usually do if there are OpenPGP or GnuPG problems.

Shalom-Salam,

   Werner

[1] http://www.heise.de/pda/newsticker/m56350.html

---

From: Ian G <[email-masked]>
Date: Fri, 18 Feb 2005 12:25:37 +0000

Jon Callas wrote:

> organization did the previous week over a botched IV. They said that 
> it wasn't worth fixing and no one needs that anyway and there was a 
> storm of press over here.

I personally hated the announcement ... BUT ...

It is what we should be doing.  I base this remark on
a research line in economics that I've picked up over
the last year, inspired by Adam Shostack's question
of "what is a security signal?"  This has led me to
question "what is security?"  Between the two of us
and with help from others, we've been gradually
forming an idea about what economics has to say
about all this.

The upshot is that the disclosure of weaknesses is
highly recommended.  It turns out, and I think we can
show this in economics terms, that disclosing the
protocol's weaknesses in clear and obvious detail
is a good security signal.

Now, back in the real world, many protocols and
security systems simply don't do that.  So I think
there is going to be a period of adjustment, where
those that disclose in glorious and self-flagellating
terms will be leading the others, in many senses.

iang