Subject: [dnsext] Rabin-Williams signatures for DNSSEC

From: "Adam Langley" <[email-masked]>
Date: Tue, 7 Oct 2008 13:31:19 -0700

I had the pleasure of chatting with Paul Vixie recently and he
described some of the cryptographic issues with DNSSEC, specifically
that smaller signatures would be very nice.

So I wrote up [1] and [2]. [1] is in the form of an ID, although I've
not actually submitted it as such yet. [2] contains the full
(executable) specification of the signature scheme described in [1]

Abstract:

This document describes how to use Rabin-Williams public keys and
signatures in DNSSEC. Rabin-Williams signatures provide for faster
verification and smaller signatures than an equivalent RSA scheme, yet
a hash-generic attack is provably equivalent to factoring.

Introduction:

DNSSEC seeks to secure the Domain Name System by using signatures that
are precomputable to avoid requiring nameservers to perform a public
key operation for each request. Thus, for DNSSEC, verification speed
is vastly more important than signing speed.

However, DNSSEC  still uses UDP as the primary transport layer
protocol and, despite increasing the maximum payload size, large
signatures are problematic both because of bandwidth and because of
the amplification possibilities in a denial of service attack.

This would suggest that elliptic curve signature schemes should be
attractive. By using a group of points of an elliptic curve rather
than a multiplicative group, index calculus (and related) attacks are
much less effective and a smaller group is still sufficiently secure.

Using the ECDSA scheme on the NIST P192 curve results in 384-bit
signatures. However, the verification operation is nearly 25x slower
than 1024-bit RSA (2.33GHz Core2).

A 1024-bit Rabin-Williams scheme (B=0, fixed, unprincipled,
compressed) results in 512-bit signatures and the verification speed
is about 4x faster than 1024-bit RSA. Due to Bernstein, we have a
proof that a hash generic attack on such a scheme is equivalent to
factoring.

[1] http://www.imperialviolet.org/binary/draft-agl-dnsext-rwb0fuz.html
[2] http://github.com/agl/rwb0fuz1024/tree/master%2Frwb0fuz1024.pdf?raw=true

Cheers

-- 
Adam Langley [email-masked] http://www.imperialviolet.org

--
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: Thierry Moreau <[email-masked]>
Date: Thu, 09 Oct 2008 05:40:21 -0500

Dear Adam,

To me personally, it's refreshing to see the R-W (Rabin-Williams) 
cryptosystem being proposed for standard body adoption. However, the 
dnsext wg audience is perhaps not ready to read the arguments and 
appreciate them as if the mathematical properties could be rationally 
assessed.

If I may rephrase your proposal, you are basically making three points:
(1) the R-W cryptosystem has better mathematical proofs than RSA,
(2) thanks to a recent development, the R-W signatures in the proposed 
variant are about half the size of RSA, and
(3) ietf dnsext should consider this for DNSSEC purposes.

Item (1) has been around for decades, with very little, if any, 
standards body adoption of the R-W for protocol applications. In part, 
this is due to the 4:1 ambiguity that is handled differently in the many 
R-W variants (the mathematical symbols e and f in your draft). In part, 
the mathematical proofs, paradoxically, appear in retrospect as not so 
good selling point as one would initially expect.

Item (2) is new to me, so I presume it would be new to many 
cryptographic experts influencing the IETF/IESG adoption of standards. 
ECC (Elliptic Curve Cryptography) also offers smaller signatures, which 
inevitably will bring lengthy discussions as to the relative merits (...).

Item (3) is challenging. You need not only to revise your draft (which 
is fine as a revision-00 as it makes the point for readers with previous 
knowledge of R-W mathematics) to speak to implementors in a language 
that they understand. You probably need to show an implementation as an 
openssl and/or gnutls source code contribution. And above all, you need 
to overcome power-of-the-installed-base resistance and inertia in the 
IETF processes.

But yes indeed, smaller signatures would be fine for DNSSEC. And I see 
the benefits of R-W signatures. So, good luck with this initiative.

Regards,

- Thierry Moreau

-- 

- Thierry Moreau

CONNOTECH Experts-conseils inc.
9130 Place de Montgolfier
Montreal, Qc
Canada   H2M 2A1

Tel.: (514)385-5691
Fax:  (514)385-5900

web site: http://www.connotech.com
e-mail: [email-masked]

---

From: Eric Rescorla <[email-masked]>
Date: Thu, 09 Oct 2008 08:32:53 -0700

At Tue, 7 Oct 2008 13:31:19 -0700,
> proof that a hash generic attack on such a scheme is equivalent to

First, let me observe that this all has a very strong whiff of premature
optimization. Given that there has been next to no deployment of
DNSSEC, I think the evidence that either signature size *or* 
signature verification performance is going to be an issue is
fairly weak.

With that in mind, it's even less clear to me that R-W is the right
choice here.

1. The performance comparison you're making here isn't really
   that useful because 192-bit ECDSA is much more comparable
   to 1776-bit RSA (see http://www.keylength.com/en/3/), which
   is rather slower (I'm guessing 3-4x) than 1024-bit RSA. 
   128-bit ECDSA would be a more accurate comparison.

2. There's a tradeoff between signature size and performance.
   BLS allows you to get signatures down to 160 bits (at the
   80-bit security level comparable to ECC-160) but at the
   cost of a much slower verification. It incidentally also
   allows aggregating multiple signatures into one. So,
   we should be clear on what it is we value the most.

3. I did a little looking and it doesn't seem to me that
   anyone has standardized R-W. I generally prefer to see
   [and I think is more or less common practice] 
   IETF only adopt algorithms which have been vetted by 
   one of the more crypto-oriented standards bodies
   (IEEE, NIST, etc.)

-Ekr

---

From: Thierry Moreau <[email-masked]>
Date: Thu, 09 Oct 2008 11:19:27 -0500

Eric Rescorla wrote:

>>signatures in DNSSEC.
>    anyone has standardized R-W.

At least ISO/9796:1991 did. I would be surprised IEEE P1363 does not 
include some R-W variant. Granted that no *protocol* standard can be 
readily identified where R-W is an option.

(How we got to this point is besides the point.)

Regards,

-- 

- Thierry Moreau

---

From: "Adam Langley" <[email-masked]>
Date: Thu, 9 Oct 2008 09:20:37 -0700

On Thu, Oct 9, 2008 at 3:40 AM, Thierry Moreau
<[email-masked]> wrote:
> Item (3) is challenging. You need not only to revise your draft (which is
> fine as a revision-00 as it makes the point for readers with previous
> knowledge of R-W mathematics) to speak to implementors in a language that
> they understand. You probably need to show an implementation as an openssl
> and/or gnutls source code contribution. And above all, you need to overcome
> power-of-the-installed-base resistance and inertia in the IETF processes.

Well, I'm only here to help, I'm not starting a RW crusade within the IETF ;)

The referenced document[1] is actually an example of literate
programming and contains a functional implementation of the scheme.
Although it does use GMP rather than OpenSSL due to GMP's superb
square root algorithm. The source code is at [2]. The source should
also be considered a -00, although several people, including Dan
Bleichenbacher, were kind enough to review it.

[1] http://github.com/agl/rwb0fuz1024/tree/master%2Frwb0fuz1024.pdf?raw=true
[2] http://github.com/agl/rwb0fuz1024

AGL

---

From: "Adam Langley" <[email-masked]>
Date: Thu, 9 Oct 2008 09:35:33 -0700

>   128-bit ECDSA would be a more accurate comparison.

Thanks for the pointer, it seems that ECRYPT put 1024-bit
multiplicative at about 144-bit EC. However, NIST don't define a curve
over a prime field < 192-bits. They do have a binary curve of 163
bits, but, with OpenSSL, it's no quicker[2] and NIST suggests[1] that
it's the same strength as the 192-bit prime curve. However, a curve
with a 128 or 144-bit prime field should be quicker, if one were
defined.

[1] http://csrc.nist.gov/groups/ST/toolkit/documents/dss/NISTReCur.pdf
, table on page 2.
[2] ECRYPT benchmarks: http://bench.cr.yp.to

>   we should be clear on what it is we value the most.

Perfectly true, I did this only because Vixie suggested that it might
be useful. It's a tool that DNSSEC could make use of.

AGL

---

From: Paul Vixie <[email-masked]>
Date: Thu, 09 Oct 2008 18:11:44 +0000

> optimization. Given that there has been next to no deployment of DNSSEC,
> I think the evidence that either signature size *or* signature
> verification performance is going to be an issue is fairly weak.

i remain very concerned about signature sizes due to packet size issues
related to IP fragmentation in EDNS, and due to round trip delays and
fragility in TCP/53.  i think it's very worthwhile to pursue smaller
signature sizes, and any counterargument of the form "but algorythm
agility is an unsolved problem" should be dismissed with prejudice.

---

From: Eric Rescorla <[email-masked]>
Date: Thu, 09 Oct 2008 12:01:36 -0700

At Thu, 09 Oct 2008 18:11:44 +0000,
> agility is an unsolved problem" should be dismissed with prejudice.

How convenient that I didn't make any such argument, then.

What I said was that this was premature optimization and that if one
*was* really concerned about signature size that one could do quite a
bit better than the R-W signature that Adam proposed, though at the
expense of computational performance.

Incidentally, the argument for an aggregatable signature scheme such
as BLS becomes for stronger in cases where a packet will contain
multiple RRSIGs.

Again, I'm not necessarily arguing against introducing another signature
scheme. What I am arguing is that we should really understand the performance
parameters and what we're trying to optimize for before we select a
scheme based on "performance", since there are a series of tradeoffs
which must be made.

-Ekr

---

From: Eric Rescorla <[email-masked]>
Date: Thu, 09 Oct 2008 13:32:33 -0700

At Thu, 09 Oct 2008 08:32:53 -0700,
>    BLS allows you to get signatures down to 160 bits (at the

I may have mentioned this already, but I believe BLS is patented,
though I can't seem to find the patent right now. If people start
taking BLS seriously and I can find the patent, I'll file a disclosure.

-Ekr