Subject: Re: Standardize RSA/SHA256 ?

From: Russ Mundy <[email-masked]>
Date: Mon, 8 May 2006 12:24:05 -0400

[ Moderators note: Post was moderated, either because it was posted by
   a non-subscriber, or because it was over 20K.  
   With the massive amount of spam, it is easy to miss and therefore 
   delete relevant posts by non-subscribers. 
   Please fix your subscription addresses. ]

I strongly support the need for standarization of this algorithm and
incorporation of it into the set of DNS RFCs.

Russ Mundy

On 5/8/06 at 11:41 AM -0400, Ólafur  Gu›mundsson /DNSEXT co-chair
<[email-masked]> wrote: 

>
>
>Dear colleagues
>
>The Working group has had a document for the last few months that
>defines a new DNSKEY algorithm RSA/SHA256. Discussion on this
>document has been non existent.
>
>The chairs would like to ask the working group following question:
>Is there support in the working group to add a new RSA algorithm
>to the list of supported algorithms?
>
>The benefit is SHA256 is stronger digest than the SHA1 that is in use
>today. Given that DNSSEC signatures are over structured data, it is
>not known how much effort is needed to create RRSET that matches
>existing signature for a particular name, type and class.
>Further consideration is the fact that DNSSEC signatures
>have a limited lifetime, restricting the window that a forged RRSET
>can be used by DNSSEC validating resolvers.
>
>The alternative to defining RSA/SHA256 now is to wait for efforts to
>standardize new digest algorithms by NIST which will take 4-5 years.
>
>Please give your chairs guidance on how to proceed, if there is
>sufficient support (minimum of 5 people) for defining RSA/SHA256
>we will start a formal last call.
>
>   Olafur & Olaf 
>
>
>--
>to unsubscribe send a message to [email-masked] with
>the word 'unsubscribe' in a single line as the message text body.
>archive: <http://ops.ietf.org/lists/namedroppers/>

--
to unsubscribe send a message to [email-masked] with
the word 'unsubscribe' in a single line as the message text body.
archive: <http://ops.ietf.org/lists/namedroppers/>

---

From: Francis Dupont <[email-masked]>
Date: Mon, 08 May 2006 19:44:57 +0200

In your previous mail you wrote:

=> I support

[email-masked]

---

From: Rob Austein <[email-masked]>
Date: Mon, 08 May 2006 13:52:34 -0400

> we will start a formal last call.

I support standardizing RSA/SHA256

(As the chairs no doubt remember, I threatened to write a draft
proposing this, but somebody else kindly wrote it first....)

---

From: Mike StJohns <[email-masked]>
Date: Mon, 08 May 2006 14:18:16 -0400

Um...

OK...  I don't think this is the right question 
or set of questions to ask.  Obviously stronger is good but:

1) Should we standardize RSA/SHA256?   - Yes
2) Should we standardize DSA/SHA256?  - No comment?
3) Should we deprecate RSA/SHA1?  Yes, but what does that mean?
4) Should RSA/SHA256 be Mandatory to Implement 
(at both the signing side and the resolver side)?  Yes.
5) Should the root (and/or lower trust anchors) 
be signed with RSA/SHA256 in addition to or in 
replacement of RSA/SHA1? - Well, that brings in 
the whole question of algorithm rollover...and "downgrade attacks"  *sigh*

So while I would agree that this might be "A GOOD 
THING" - I think its handwaving to just say yes 
to RSA/SHA256 without dealing with all the other things.

DNSSEC has gotten consistently more complex - the 
addition of NSEC3 and the interactions with NSEC 
still don't give me warm fuzzies.  After many 
long sessions with the folks that should know how 
this should all work I still don't have a good 
feeling about using more than one signature 
algorithm in a trust chain.  How do 
NSEC/NSEC3/RSASHA1/RSASHA256 all play together?

The specific document has some issues as well - 
specifically dealing with RSA DNSKEY records - it 
shouldn't have a TBA for the format of RSA in 
DNSKEY records for example.  While it's OK to 
cite PKCS2.1 as the source for the format of the 
RSA/SHA256 signature blob (specifically the 
prefix), it should also give the actual ASN.1 
used to form the blob and consider that the 
definitive version.  As above, I'd like a bit 
more discussion on operational considerations for 
switching from SHA1 to SHA256.

Later, Mike

---

From: Wes Hardaker <[email-masked]>
Date: Mon, 08 May 2006 13:25:24 -0700

>>>>> On Mon, 08 May 2006 11:41:23 -0400, [email-masked] (Olafur Gudmundsson) said:

Olafur> The alternative to defining RSA/SHA256 now is to wait for efforts to
Olafur> standardize new digest algorithms by NIST which will take 4-5 years.

I believe we should standardize it now rather than wait.  If we
believe that a particular algorithm will likely used in the future,
and I believe this one will be, then I don't see the point in waiting
to define it later if we have the time and energy now.  More
importantly, I think it would be detrimental to delay defining it now
assuming it will be defined at some point.

The only way I think not defining it now is wise is if we're uncertain
that it'll be selected for future use.
-- 
Wes Hardaker
Sparta, Inc.

---

From: Ólafur Guðmundsson /DNSEXT co-chair <[email-masked]>
Date: Mon, 08 May 2006 16:51:30 -0400

At 14:18 08/05/2006, Mike StJohns wrote:
>So while I would agree that this might be "A 
>GOOD THING" - I think its handwaving to just say 
>yes to RSA/SHA256 without dealing with all the other things.

Thanks Mike for your list of follow up questions,
few comments:
Q2: is a different question and does not belong here, but this is a related
         question. As far as I can tell right now no-one has shown any interest
         in using DSA when deploying DNSSEC. As long as that is the case the
         question about DSA/SHA256 should be asked at the same time as the
         kill DSA question is raised.

Q3: My personal opinion not speaking as a chair:
         If RSA/SHA256 is specified then RSA/SHA1 should be
         tagged as "Not recommended".

Q4: If we are defining it and we think it is "better" than what is used
         today then it should be mandatory to implement.

Q5: Outside the scope of namedroppers/DNSEXT, we 
provide the toys, the operators
         get to pick which one they play with.

>DNSSEC has gotten consistently more complex - 
>the addition of NSEC3 and the interactions with 
>NSEC still don't give me warm fuzzies.  After 
>many long sessions with the folks that should 
>know how this should all work I still don't have 
>a good feeling about using more than one 
>signature algorithm in a trust chain.  How do 

Excellent point, this is one of the reasons why 
Olaf and I are looking for guidance.
Holding off changing signature algorithms right now may reduce the cost of
deployment, so we need to weight the tradeoffs.

Thanks for your feedback.

         Olafur

---

From: Dean Anderson <[email-masked]>
Date: Tue, 9 May 2006 17:07:38 -0400 (EDT)

> can be used by DNSSEC validating resolvers.

Adding more crypto options requires more software in nameservers and resolvers.  
Yes, SHA1 is breakable in principle, with a lot of work. But all crypto, with
the exception of a one-time pad, is breakable in principle. The only real shock
with SHA1 is that people _expected_ it to be one-way.  But people should not
have expected SHA1 to be unbreakable. Shame on them.  Their shock is their own
fault.  It is also well to note here that (so far as the Chinese paper goes)  
SHA1 has not actually been reversed, but that the computational effort to
perform a reversal requires less effort than previously thought.  The
computational effort is still very high. As I understand it, it is still beyond
the feasible capabilities of most or all governments, much less the capabilities
of some group of hackers.

Second, the crypto security needs only to be comparable to the physical security
of the root DNS servers. If the physical security of the root (or rather the
root zone signing infrastructure) is compromised, then one can obtain the keys
without a brute force attack (a "black bag" attack). An estimated cost, that is
a dollar (or euro)  cost, can be assigned to this "black bag" effort and the
cost compared with the cost of the breaking SHA1 hash by computer.  I suspect
the cost of physically obtaining the keys through physical breakin is much less
than that of breaking the SHA1 hash. This would make SHA1 strong enough for our
purposes.  A more detailed analysis may be in order, however.

Third, the security of zones below root are dependent on the security of the
root. Making e.g. av8.com (or perhaps .com) more secure than the root offers no
benefit, since the delegations can be sent to other servers if the root (or
upper level) responses can be falsified. The security equation is
          
	    subzone.av8.com <= av8.com <= com <= .

> standardize new digest algorithms by NIST which will take 4-5 years.

Another alternative is just sticking with SHA1 and working on more pressing
problems. There are much more significant problems with DNSSEC in actual
operation than a slightly weaker than expected hash algorithm.  DNSSEC requires
stateful DNS, and stateful DNS on Anycast roots is a big problem that people are
only just beginning to grapple with.  I expect that it will take a couple years
to fully resolve the current stateful anycast problems, which delays widespread
DNSSEC use anyway.  So, there is no rush to replace the hash algorithm.

> we will start a formal last call.

For the above reasons, I think that we have time to consider the correct course
of action. There is no need to rush into more algorithms which require more code
on nameservers and resolvers. 

		--Dean

-- 
Av8 Internet   Prepared to pay a premium for better service?
www.av8.net         faster, more reliable, better service
617 344 9000

---

From: Simon Josefsson <[email-masked]>
Date: Wed, 10 May 2006 10:52:00 +0200

Dean Anderson <[email-masked]> writes:

> perform a reversal requires less effort than previously thought.

There is no reversal attack on SHA-1 currently.  Wang et al's attack
find a collision in 2^69 operations, instead of the expected 2^80.  I
believe the limit has been improved (2^63 in August 2005).  For
digital signatures, a collision is all that is required though, you
don't need reversal.

> For the above reasons, I think that we have time to consider the
> correct course of action. There is no need to rush into more
> algorithms which require more code on nameservers and resolvers.

Yes, or at least, we need to document a more compelling reason to do
RSA-SHA-265.

Regards,
Simon

---

From: Ben Laurie <[email-masked]>
Date: Wed, 10 May 2006 07:41:14 -0700

> digital signatures, a collision is all that is required though, you

"Required" in what sense? Yes, it allows you to produce two things with
the same signature. What is the attack on DNSSEC that arises from this?

-- 
http://www.links.org/

---

From: Simon Josefsson <[email-masked]>
Date: Wed, 10 May 2006 17:10:27 +0200

Ben Laurie <[email-masked]> writes:

> "Required" in what sense?

"Required" to break the signature scheme.

> Yes, it allows you to produce two things with the same
> signature. What is the attack on DNSSEC that arises from this?

Wouldn't such a break violate the property of DNSSEC that after
successful verification of the digital signature, you know the data
you received was the intended published data?

/Simon

---

From: Jelte Jansen <[email-masked]>
Date: Fri, 12 May 2006 10:56:27 +0200

> Yes, or at least, we need to document a more compelling reason to do

So why is this an issue for RSA/SHA256, and not for
draft-ietf-dnsext-ds-sha256-05.txt, which also makes SHA256 mandatory?

btw, both drafts don't deprecate SHA-1 but do assume that SHA256 is
stronger and contain text about downgrade attacks based on this assumption.

Jelte

---

From: Simon Josefsson <[email-masked]>
Date: Fri, 12 May 2006 11:54:56 +0200

> draft-ietf-dnsext-ds-sha256-05.txt, which also makes SHA256 mandatory?

I suppose it applies to both.

Changing the RSA signature algorithm also begs the question: Do we
want to move to RSA-PSS?  See PKCS#1 2.1 in RFC 3447.

I believe RFC 3447, and RSA Labs has encouraged a gradual shift from
RSA-PKCS#1 1.5 to RSA-PSS for a few years now:

http://www.rsasecurity.com/rsalabs/node.asp?id=2005

One advantage with RSA-PSS is that it is easier to analyse
theoretically, and there are security proofs for it.

One disadvantage is that RSA-PSS requires entropy during signing.

> stronger and contain text about downgrade attacks based on this assumption.

Ólafur wrote:

/Simon

---

From: Ólafur Guðmundsson /DNSEXT co-chair <[email-masked]>
Date: Fri, 12 May 2006 10:54:07 -0400

>draft-ietf-dnsext-ds-sha256-05.txt, which also makes SHA256 mandatory?

<Chair-hat=on>
The issues here are slightly different.

DS digest is the SAME for the lifetime of the DS record.
Digest inside a RRSIG is going to be different each time the signature is
regenerated for that set, thanks to the different signature lifespan timers.
Thus in the case of DS an attacker has much longer to be able to generate
a DNSKEY that has a matching DS digest to an existing one.

The WG was advised by our Security Area Advisor (Russ Housley) that any use
of SHA-1 without HMAC wrapper should be retired. As DS was the most vulnerable
the chairs got that effort stared on the spot and RFC4509 should be published
any day now.

<Chair-hat=off>
A mitigating fact that RRSIG is not as vulnerable as plain text, against the
known SHA1 attacks, is the structured data format of an RRset.
Having said that if attack on RRSIG digest, or other structured formats,
is valuable enough some smart people will figure out a way to design
such an attack.

Following up on Hilarie and Rip's messages:
One part of the security analysis should be how long signature lifetime can be
for the different digest algorithms used as a function of time.
This is similar to what is available for lengths of public keys.

         Olafur

---

From: Ben Laurie <[email-masked]>
Date: Fri, 12 May 2006 18:43:53 +0100

> you received was the intended published data?

If the publisher of the data chooses to publish stuff which could have
one of two values for the same signature, then clearly that's what he
indended.

So, I don't see the problem.

Cheers,

Ben.

-- 
http://www.apache-ssl.org/ben.html           http://www.links.org/

"There is no limit to what a man can do or how far he can go if he
doesn't mind who gets the credit." - Robert Woodruff

---

From: Mike StJohns <[email-masked]>
Date: Fri, 12 May 2006 14:09:53 -0400

>one of two values for the same signature, then clearly that's what he

I think this was sarcasm, but its so hard to tell with Ben.  So lets 
assume not:

If given an SHA1 summary over DNS data (and it's the summary that is 
"signed" not the actual data in DNSSEC), I have a method which lets 
me create a data blob which when summarized will equal that original 
summary, I can substitute my data blob for the DNS data that was 
signed and the recipient can't tell the difference.

Of course, this assumes that the created data blob can be formatted 
in a way that it looks like valid DNS data...

---

From: Mark Feldman <[email-masked]>
Date: Fri, 12 May 2006 14:32:21 -0400

As I understand it,  for an attack using collisions that can be  
generated in current cryptographic hash functions to be effective,  
the attacker must control the creation of the documents to be  
signed.  In the case of DNSSEC, the attacker would have to create  
both the ostensibly valid RRSET (with a bunch of binary gobbledygook  
to make things work ) that is signed and its fraudulent alternative.   
Since the responsibility for generating and signing an RRSET usually  
falls to the same individual, breaking the crypto would seem to be  
unnecessary.   I think Ben was referring to this.

The Daum/Lucks scenario (http://www.cits.rub.de/MD5Collisions/) works  
because Postscript is interpreted and the delta between the good and  
bad documents is used in a conditional to determine which of two  
views of the document should be presented.  Such interpretation is  
not native to DNS.   One might also argue that the set of people  
likely to look at an RRSET is larger than the set of people likely to  
look at the Postscript source of a document.  Note that it is now  
possible to create pairs of visually distinct Postscript documents  
that will produce the same MD5 hash without having to do any  
computation by simply reusing the core of the Daum/Lucks documents.

  Mark

On May 12, 2006, at 2:09 PM, Mike StJohns wrote:

> I think this was sarcasm, but its so hard to tell with Ben.  So  
> lets assume not:
>
> If given an SHA1 summary over DNS data (and it's the summary that  
> is "signed" not the actual data in DNSSEC), I have a method which  
> lets me create a data blob which when summarized will equal that  
> original summary, I can substitute my data blob for the DNS data  
> that was signed and the recipient can't tell the difference.
>

---

From: Chris Thompson <[email-masked]>
Date: Fri, 12 May 2006 19:44:53 +0100 (BST)

> in a way that it looks like valid DNS data...

You are missing the point that "produce two things with the same signature"
is not the same thing as "produce a thing with the same signature as a
given thing". The existing attacks on MD5 / SHA1 are of the former type:
at most they generate two alternative (not too short) bit strings that 
can be spliced into a given string to produce a pair with the same hash.

Of course, the fear is that this will not remain the case.

-- 
Chris Thompson
Email: [email-masked]

---

From: Ben Laurie <[email-masked]>
Date: Sat, 13 May 2006 11:35:39 +0100

> I think this was sarcasm, but its so hard to tell with Ben.  So lets

It wasn't. But thanks for the compliment

> "signed" not the actual data in DNSSEC), I have a method which lets me
> create a data blob which when summarized will equal that original
> summary, I can substitute my data blob for the DNS data that was signed
> and the recipient can't tell the difference.

Correct, but only if the DNS data that was signed was _also_ chosen by
you. So, as I said, clearly you intended for this to be the case.

> Of course, this assumes that the created data blob can be formatted in a
> way that it looks like valid DNS data...

Indeed.

Cheers,

Ben.