Subject: RE: [ietf-dkim] agenda item on upgrading hash algorithms?

From: "Hallam-Baker, Phillip" <[email-masked]>
Date: Thu, 23 Feb 2006 13:54:49 -0800

Clean room implementation is irrelevant as far as patents are concerned.

I do not believe the 25% inefficiency introduced by base 64 encoding
adds to the problem of small DNS record sizes in a significant or
important manner or that your proposed transition to a binary format
solves the problem to a significant or useful degree.

We know that 4096 bit keys will not fit into a standard DNS record.

The difficulties you raise with TXT records appear to be insignificant
compared to the fact that about half the deployed infrastructure does
not support new binary records and it will be 2009 at the very earliest
before the vendor concerned makes a new server release.

People might not mind your endless confused speculation over
non-problems so much if you appeared to be interested in the real
problems we face.

> -----Original Message-----
> From: Douglas Otis [mailto:[email-masked]] 
> Sent: Thursday, February 23, 2006 4:42 PM
> To: Hallam-Baker, Phillip
> Cc: [email-masked]
> Subject: Re: [ietf-dkim] agenda item on upgrading hash algorithms?
> 
> 
> On Feb 23, 2006, at 12:32 PM, Hallam-Baker, Phillip wrote:
> 
> > I think that we are all aware that IP owners have a duty to their 
> > shareholders to promote the value of their IP in the best possible 
> > light.
> >
> > We do not need point compression for our purposes.  Nor is 
> efficiency 
> > a critical issue.  The only crucial criteria is a bit 
> length of 1024 
> > bits or less.
> 
> The issue raise regarding IPR was not related to point compression.   
> In addition to defending against known attacks, Certicom IPR 
> claims also relate to basic algorithm improvements which 
> makes clean-room development difficult.  Is there 
> elliptic-curve code within the public domain not encumbered, 
> which can be safely used in the near future?  If ECC code is 
> not ready now, when will it be?  Can someone predict whether 
> ECC, with its small keys sizes, will not become vulnerable as 
> has SHA-1?  There is less private key information to leak.
> 
> Although there are text-based conventions for entering binary 
> RRs into DNS, this discussion was considering whether space 
> was available within the TXT RR to accommodate upgrade 
> declarations, or whether a binary structure for DKIM key RR 
> should be considered.  An ability to accommodate 2048 bit 
> keys does not preclude use of ECC, when that proves feasible 
> and desirable.  However, not having an ability to accommodate 
> 2048 bits may create much greater disruption.  Why paint DKIM 
> into a corner?  Surely a binary RR is easier than developing 
> cryptography.
> 
> -Doug
> 
> 
> 
> 

_______________________________________________
NOTE WELL: This list operates according to 
http://mipassoc.org/dkim/ietf-list-rules.html

---

From: Jon Callas <[email-masked]>
Date: Thu, 23 Feb 2006 17:21:16 -0800

> We know that 4096 bit keys will not fit into a standard DNS record.

But Phill, we don't *need* 4096 bit keys before 2009.

A DKIM key isn't a CA root key. It signs a message to take  
responsibility for it. The semantic lifetime of a given signature has  
an upper bound of somewhere between a week and a month. According to  
NIST's estimates, a 3k key has 128 bits of strength. For DKIM  
purposes, a 2k key changed once a year is great. DKIM is ones of the  
places where even paranoids like me don't twitch at 1k keys. If  
someone goes and builds one of Adi Shamir's optical crackers, they  
can do a single key a year for $10M.

If there's so much money in abusing unauthenticated email that this  
is a threat, then we have problems cryptography can't solve. Yeah,  
yeah, by 2020 or 2030, we'd better be on ECC. And by then, there  
won't be IP issues. Unless of course someone makes practical quantum  
computers, but that's a different issue.

	Jon

---

From: Douglas Otis <[email-masked]>
Date: Thu, 23 Feb 2006 18:53:29 -0800

> Clean room implementation is irrelevant as far as patents are  

Agreed, which is why it would be difficult. : )

> I do not believe the 25% inefficiency introduced by base 64  
> encoding adds to the problem of small DNS record sizes in a  
> significant or important manner or that your proposed transition to  
> a binary format solves the problem to a significant or useful degree.

When a 2048 bit key is to be handled, with the 'g=' parameter and a  
new hash callout, the space remaining is 93 bytes, assuming a domain  
with 4 labels with a selector.  From these 93 bytes, 5 labels, the  
local-part and hash function must be defined where the average item  
size must be less than 14 bytes.  When a binary DKIM Key RR is used,  
the remaining available space is 192 bytes, which then allows an  
average item size to be greater than 27 bytes.  This provides twice  
the available space, which is _not_ insignificant.  The cases where  
the DNS payload overflows would be much fewer.

> We know that 4096 bit keys will not fit into a standard DNS record.

By the time this size key is needed, hopefully DNSsec is also available.

> The difficulties you raise with TXT records appear to be  
> insignificant compared to the fact that about half the deployed  
> infrastructure does not support new binary records and it will be  
> 2009 at the very earliest before the vendor concerned makes a new  
> server release.

There was not a suggestion to use a new binary record.  The proposal  
was to employ an existing record in a binary fashion.

> People might not mind your endless confused speculation over non- 
> problems so much if you appeared to be interested in the real  
> problems we face.

Calculating DNS payloads is out a concern related to exceeding DNS  
payload limitations which is a real problem.  Dismissal of concerns  
by indicating it does not work with 4096 bit keys and with the  
comment about a 25% inefficiency without exploring the ramifications  
seem highly speculative and not related to the problems at hand.  I  
have every desire to see DKIM succeed by paying attention to these  
details.

-Doug

---

From: Mark Delany <[email-masked]>
Date: Fri, 24 Feb 2006 03:09:30 +0000

> By the time this size key is needed, hopefully DNSsec is also available.

Or more realistically RFC2671 published 1999 and on standards track.

> was to employ an existing record in a binary fashion.

I presume you mean to *change* an existing one to support the extra
Selector goop invent here (and yet to be invented in the coming
months).

I also presume you have the support of the original authors and
consumers of your favoured alternative RR to make such changes and
extensions? Barging in on someone's favour RR and wanting to change it
without their support would prove to be a very painful, yes?

Mark.

---

From: Douglas Otis <[email-masked]>
Date: Thu, 23 Feb 2006 22:04:15 -0800

> Or more realistically RFC2671 published 1999 and on standards track.

This becomes required with DNSsec which lacks name compression and  
adds additional overhead.  Until DNSsec blazes that trail, everyone  
will continue to bump their head on the low branches.

>> There was not a suggestion to use a new binary record.  The  
>> proposal was to employ an existing record in a binary fashion.
>

This could be the TLV structure replacing the 't=value;' approach.   
There is not much need for creativity.  This structure could be  
placed upon an even boundary by having a byte value defined following  
the algorithm field such as "group". : )

0         5                   15
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|  tag  |       length        |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
\           value             \
/                             /
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

tag
---
0 = reserved
1 = key data
2 = granularity
3 = services
4 = notes
5 = test
6 - 15 reserved

If this looks okay, a draft and sample code populating and reading  
this resource record can be provided.  It seems like a good investment.

> extensions? Barging in on someone's favour RR and wanting to change  
> it without their support would prove to be a very painful, yes?

Use of this RR as suggested does not impact RFC2538 or the pending  
revision.  The DKIM Key and signature header provides the same  
function as a CERT RR.  DKIM also takes the step of using a unique  
label to access this RR.   Only an IANA assignment should be needed  
based upon consensus of the DKIM wg.  In every case, a separate  
document describes the structure of the data following the CERT  
header.  An overview of DKIM would not be missed.  If this wg is  
interested in pursing this, I'll be happy to follow up with those  
involved and report back.

-Doug

---

From: Eliot Lear <[email-masked]>
Date: Fri, 24 Feb 2006 08:02:49 +0100

The other alternative to squeezing bits in a DNS record is providing a
redirect to another service.

Eliot

---

From: John Levine <[email-masked]>
Date: 24 Feb 2006 15:53:38 -0000

>redirect to another service.

Sure, but now you have the extra cost of another transaction.  If you're
going to do that, you might as well invent another q= lookup scheme,
probably via HTTP, and use it directly.

It seems to me that since DKIM signatures are expected to have short
lifetimes and to have only moderate value, and that we've established
quite thoroughly that there is not yet an obvious successor to SHA-1,
it would be OK simply to note that we'll need something more secure in
the future and leave it at that.

R's,
John

---

From: Eliot Lear <[email-masked]>
Date: Fri, 24 Feb 2006 17:01:19 +0100

> probably via HTTP, and use it directly.
Right... this is really where I was aiming.
> the future and leave it at that.

How many times do you want to do this?!

Eliot

---

From: Stephen Farrell <[email-masked]>
Date: Fri, 24 Feb 2006 16:05:38 +0000

> the future and leave it at that.

I didn't get that impression from this thread.

My impression was that the consensus was heading towards something
very close to Dave's message from a few days ago [1], but I wasn't
clear exactly on whether we ended up with a MUST or SHOULD on
sha-256 for signers.

Almost quoting Dave:

     A validator MUST support {SHA-1, SHA-256}.
     A signer [SHOULD|MUST] use {SHA-256}.

Stephen.

[1] http://mipassoc.org/pipermail/ietf-dkim/2006q1/002326.html

---

From: "John R Levine" <[email-masked]>
Date: 24 Feb 2006 11:09:24 -0500

> How many times do you want to do this?!

Ideally never, pragmatically, once.  If I thought we had enough info to do
it now, I'd agree that we should try to do it now, but we don't.

I don't see a hash upgrade as urgent.  Even as SHA-1 becomes easier to
break, it doesn't seem likely that it'll be broken badly enough to make it
possible to put fake signatures on messages at high speed.

Regards,
John Levine, [email-masked], Primary Perpetrator of "The Internet for Dummies",
Information Superhighwayman wanna-be, http://www.johnlevine.com, Mayor
"I shook hands with Senators Dole and Inouye," said Tom, disarmingly.
_______________________________________________
NOTE WELL: This list operates according to 
http://mipassoc.org/dkim/ietf-list-rules.html

---

From: Dave Crocker <[email-masked]>
Date: Fri, 24 Feb 2006 08:35:40 -0800

> How many times do you want to do this?!

I believe that Jon Callas' note about PGP usage history made clear that the 
exigencies of the security algorithm world make the answer to your question be: 
periodically, because transition to new security algorithms is a fact of life.

d/
-- 

Dave Crocker
Brandenburg InternetWorking
<http://bbiw.net>
_______________________________________________
NOTE WELL: This list operates according to 
http://mipassoc.org/dkim/ietf-list-rules.html

---

From: Dave Crocker <[email-masked]>
Date: Fri, 24 Feb 2006 08:51:46 -0800

> How many times do you want to do this?!

<<Apologies for my last posting; I responded to the second paragraph's focus on 
algorithm agility, rather than the first paragraph's suggestion of an alternate 
query service>>

I think the answer is: once, and we want to wait as long as possible, before 
trying to create that additional infrastructure.

This was one of the main points of differentiation between domainkeys and 
identified internet mail.  The dominant feeling is that creating a new query 
service infrastructure is a very, very high barrier to entry.

d/
-- 

Dave Crocker