Subject: SHA-1 broken

From: Konrad Rosenbaum <[email-masked]>
Date: Thu, 17 Feb 2005 07:50:49 +0100

Hi,

http://www.schneier.com/blog/archives/2005/02/sha1_broken.html

While this attack reduces SHA-1 from strength 2^80 to 2^69 and 2^69 
operations is still unreachably much, likelihood seems high that someone 
will improve this attack once the paper has been released.

Should we phase out SHA-1? But in favour of what?

This also means that DSA/DSS is broken (a downgrade attack becomes 
possible). Should we return to suggesting RSA as signature algorithm?

	Konrad

---

From: Lutz Donnerhacke <[email-masked]>
Date: Thu, 17 Feb 2005 09:36:08 +0000 (UTC)

> Should we phase out SHA-1? But in favour of what?

Don't panic. This problem is already solved by allowing different
hash-algorithms in the packet format. As long as no detailed examination of
other algorithms is available, OpenPGP should not change MAYs and MUSTs.

---

From: Werner Koch <[email-masked]>
Date: Thu, 17 Feb 2005 11:39:41 +0100

> hash-algorithms in the packet format. As long as no detailed examination of

The fingerprint and the MDC both use SHA-1 hardwired.

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.

Salam-Shalom,

   Werner

---

From: "Vlad \"SATtva\" Miller" <[email-masked]>
Date: Thu, 17 Feb 2005 17:19:01 +0600

On 17.02.05 15:36, Lutz Donnerhacke wrote:
>> While this attack reduces SHA-1 from strength 2^80 to 2^69 and
>> 2^69 operations is still unreachably much, likelihood seems high
>> that someone will improve this attack once the paper has been
>> released.
>> 
> hash-algorithms in the packet format. As long as no detailed
> examination of other algorithms is available, OpenPGP should not
> change MAYs and MUSTs.

Although I agree that we must not rush, but make weighted decisions,
there is a ground for some misgivings. For instance, v4 key format
relies solely on SHA-1 for fingerprints and MDC calculation, and when
(and if) the attack in question will become more useful in practical
sense, may lead to bad results.

-- 
Respectfully yours,

 __________________________________
 Vladislav "SATtva" Miller
 "PGP in Russia" project leader
 http://www.pgpru.com

 PGP public key ID: 0x4D8BB49E
 http://www.pgpru.com/contacts/

 Email encryption and digital signing
 is highly desired. Preferred method
 is OpenPGP, otherwise S/MIME.

---

From: Ian G <[email-masked]>
Date: Thu, 17 Feb 2005 12:58:24 +0000

>The fingerprint and the MDC both use SHA-1 hardwired.

It would seem an easy matter to add some options
on fingerprint.  That's something that could be
added to the standard as a MAY and people can
switch across if the weaknesses in SHA1 move
across to economically exploitable status.

For the MDC, that sounds more of a challenge.  I
would suspect that the call is now on for a change to
the draft to allow alternate algorithms there!  Are
there any easy ways?  Or is this a deal breaker?

Given the rapid advance of the attack by the Shandong
team we should basically expect SHA-1 to be broken
within the year.  So, I would guess within the time
frame of completing the draft, we may have to set
it up so that it is prepared for that event.

Which would mean that all uses of SHA-1 would have
an alternate.  It doesn't necessarily mean that SHA-1
changes from MUST to SHOULD.

>replacement for SHA-1 but to meet the requirements of AES and to

I think if all attacks are still limited by the fundamental
birthday principle, SHA-256 is likely to be safe.  What is
worrying to the academic world is the fact that the
foundation of SHA-256 is as an extended SHA-1 (which
was an extended MD5, which was....) and this entire
approach is now being subjected to reduced rounds
attacks.  Note that SHA-1 in unpadded form has lost
11 of its 80 bits.  Even if SHA-256 lost 80 of 160 bits it
would still be good!

Academic elegance does not concern us here.

If SHA-256 is big-and-ugly enough to overcome all but
the most ridiculous of birthday attacks then it will serve
our purposes .... perhaps at least for the five year interim
required for the academics to come up with the next
generation.

(Quick question - how long was it from the start of the
AES competition to the announcement?  About 4 years?)

iang

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

---

From: David Shaw <[email-masked]>
Date: Thu, 17 Feb 2005 09:00:10 -0500

> across to economically exploitable status.

I don't think it's all that easy to just add options to the
fingerprint.  Let's say you specified a fingerprint (which is
currently just HASH) with ALGO:HASH.  So, my current (SHA-1)
fingerprint would be:

  2:7D92FD313AB6F3734CC59CA1DB698D7199242560

Simple enough, but my fingerprint would also be (MD5):

  1:B9E4614F2E6FACD8F5DD32010AC50AAC

and even (SHA-512):

  10:00C2C9BBF4AC3AD6D45275C041E1EE88AA6B0564F227AD4FBE0F7BBE845B8B47342A941A88384A79CFC0858572DCDE326AC21625D7822B2102CA3857669C381B

Allowing multiple representations of the fingerprint allows for all
sorts of problems where an attacker can force a particular hash
algorithm.  There is even a warning about this attack (in the context
of signatures) in the draft.

If SHA-1 is showing its age, well, that's to be expected.  It's had a
good run, but even before this new attack came to light, it was
already being phased out by NIST.

Rather than trying to jury-rig something together to allow using other
hashes, I think I would rather just declare a V5 key format (which can
be essentially the same as V4), which uses a different hash.  Users
can continue using V4 keys as long as they desire, and developers will
have time to add support for V5 so it's ready when it is needed.  This
ties in neatly with other things recently discussed here : for
example, a V5 key could be said to have AES as the default algorithm.

Note that keyservers and other programs that use OpenPGP will need to
understand whatever we do.  Not messing about with the well-understood
and widely implemented definition of V4 keys will make this easier.

David

---

From: Ian G <[email-masked]>
Date: Thu, 17 Feb 2005 15:01:29 +0000

>example, a V5 key could be said to have AES as the default algorithm.

Having now read the "note" that the Shandong
team distributed, I'm less inclined to think this
is the end of the world.  See my blog for some
snippets.

Declaring a need for a V5 key makes a lot of
sense, if we believe that we can survive that
long.  However, the first thing would be that
I'd say a redesign of the key structure would
be better than just a minor change to one
element.  I don't think it's worth carring the
costs of an entire new key structure in code
without making it worth carrying on for the
next N decades.

But, yes, V4 keys are old too.  A good point.

iang

---

From: David Shaw <[email-masked]>
Date: Thu, 17 Feb 2005 13:36:38 -0500

> without making it worth carrying on for the

We're much in agreement, though I don't forsee any key version making
it much beyond 10-15 years.  The technology changes, and there is no
easy way to get around that.  V4 keys have lasted for around 7-8 years
now, and will likely hang on for years to come; that's a pretty good
run.  I think designing a V5 key that will last much longer than that
is not possible without a crystal ball.  The best we can do is to
design it to last as long as possible, and know that someday we'll be
making a V6 key.

My main argument for a V5 key is that doing patch work on V4 has the
potential to split the installed base into "old V4" and "new V4".
Rather than end up like that, just call "new V4" "V5" instead.  It is
also an opportunity to fix the handful of little details that bug
people about V4: the default cipher can be AES instead of 3DES.  The
key expiration dates can be hard or soft (not just soft as in V4).
And so on.

I don't know that this should necessarily be in 2440bis, though, or
2440bis may never be released.

David

---

From: Werner Koch <[email-masked]>
Date: Thu, 17 Feb 2005 20:21:44 +0100

> key expiration dates can be hard or soft (not just soft as in V4).

I am all in favor of this. Some time ago we even discussed that a v5
signature format would be a good idea so solve some things.  We could
even addres the back signature thing better with a new format.

> 2440bis may never be released.

More than 6 years since the last RFC so it is indeed time to have a
new one, defining what the current standard is and showing a warning
that a v5 format is being worked own.  This will give enough time to
work out the problems and analyze what's up with the hash algorithms.

Salam-Shalom,

   Werner

---

From: David Shaw <[email-masked]>
Date: Thu, 17 Feb 2005 14:42:05 -0500

On Thu, Feb 17, 2005 at 07:32:00PM +0000, Ian G wrote:
> OK, so you would propose an intermediate
> "fixes lots of little things" V5.  I don't know
> what the balance between these future
> paths would be ...

What I'm trying to get at is there is no "intermediate".  The word
intermediate implies that there is some ultimate goal and this would
be a step towards it.  My argument is that there is no ultimate goal,
and shooting for one is something we can spend a lot of time arguing
over to no avail.  Without a time machine, we don't know what
cryptography will become in the future.  We can just do the best we
can with the knowledge we have, ponder where we think things are going
over the next 10 years, build in as much future proofing as we can
think of - and even then expect that eventually there will need to be
a V6.

David

---

From: Ian G <[email-masked]>
Date: Thu, 17 Feb 2005 19:32:00 +0000

>2440bis may never be released.

I think if we can make an assessment that
SHA-1 is still good for another couple of
years, then we should go for it.  Sure, shove
a note in there that it's a worry, but life is
full of worries...

(Which is to say that seeing as there are
some major difficulties in replacing SHA-1
in the current structures, then we should
just shrug and move on.  No removal unless
it is absolutely necessary.)

iang

---

From: Konrad Rosenbaum <[email-masked]>
Date: Fri, 18 Feb 2005 07:59:19 +0100

On Thursday 17 February 2005 15:00, David Shaw wrote:
> 10:00C2C9BBF4AC3AD6D45275C041E1EE88AA6B0564F227AD4FBE0F7BBE845B8B47342A94
>1A88384A79CFC0858572DCDE326AC21625D7822B2102CA3857669C381B
>
[cut]
> be essentially the same as V4), which uses a different hash.

Why not do both?

If the hash ID used for the fingerprint is part of the key format and 
consequently hashed together with the key then there shouldn't be much of 
an attack vector left. The only one who can enforce a certain hash to be 
used is the key owner, if anybody else tries it ultimately changes the 
fingerprint.

	Konrad

---

From: Konrad Rosenbaum <[email-masked]>
Date: Mon, 21 Feb 2005 20:57:07 +0100

> replacement for SHA-1 but to meet the requirements of AES and to

How would SHA-256 extend DSA? DSA uses a q of 160 bit(*), which limits the 
implementation to any hash that delivers 160 bits or cutting the hash back 
to 160 bit.

As long as we still allow any hash to be used with DSA one can attempt a 
downgrade attack by altering the signature to use SHA-1 and then try to 
find a fitting text(**).

Or would that create a DSA-2 which uses a q of 256 bit? 
How large would p be then?
Would that DSA-2 get a new Algorithm-ID or is the q of 256 bit indicator 
enough?

(*)apart from the p of 1024 bit
(**)yes, I know 2^69 is still a lot of computation and the attack wasn't 
about finding a duplicate for a specific message, but....

	Konrad