Subject: [dnsext] DNSCurve and alternative cryptosystems

From: Matthew Dempsky <[email-masked]>
Date: Wed, 24 Mar 2010 12:57:39 -0700

One of the issues that was raised in the WG meeting yesterday (and in
the past) was a desire to support additional cryptosystems; in
particular, using a NIST elliptic curve (e.g., NIST P-256) and
(presumably) AES and an authenticated-encryption mode on top of it.

The one big issue I see with supporting NIST P-256 is public key size.
 NIST P-256 is defined using a short Weierstrass form elliptic curve,
so public keys need both the x- and y-coordinates of the elliptic
curve points, and so a 256-bit field requires a 64-byte public key.
My understanding is that it's possible to "compress" an elliptic curve
point by just sending the 32-byte x-coordinate and requiring the
recipient to reconstruct the y-coordinate (at some extra computational
work), but also that this is supposedly covered by US patent 6141420.

(In contrast, Curve25519 uses a Montgomery form curve, so scalar
multiplication requires only the x-coordinate.  So only the 32-byte
x-coordinate needs to be transmitted, and the recipient never has to
compute the y-coordinate, directly or indirectly.)

So as DNSCurve is currently defined with 32-byte public keys in mind,
supporting 64-byte public keys has some small consequences:

  - Any encoding of a 64-byte key is going to require at least 64
bytes, and so won't fit into a single DNS label; but this can be
fairly easily resolved by simply spreading the key across two adjacent
labels.

  - Since Curve25519 public keys are really 255-bit integers, DNSCurve
takes advantage of this when encoding them in base-32 to save an extra
byte; again, easily resolved by just encoding other keys in full
(unless similar optimizations can be added).

  - When using 64-byte public keys, TXT format cannot be used to query
names containing 64-byte public keys without the resulting qname
exceeding 255 bytes.  (Even with 32-byte public keys, some query
packets will encode to qnames over 255 bytes, but there's at least
enough headroom to support queries for names up to about 100 bytes.)
This could perhaps be remedied somehow using EDNS options, but I don't
have any ideas off hand right now.

  - Name server names will be larger still; this may or may not prove
an issue though.

Elliptic curve selection issues aside, I'm interested in knowing
exactly what flexibility people are interested in for cryptosystems.
E.g., would defining just Curve25519+XSalsa20+Poly1305 and
NIST-P-256+AES256+HMAC-SHA-512 (or maybe GCM-mode instead of HMAC) be
a satisfactory starting point?  My instinct is that people who are
satisfied with using Curve25519 will also be satisfied with using
Salsa20 and Poly1305, and people who require NIST-P-256 will also
require AES and HMAC or GCM.

Also, I don't see value in defining lower security primitives like
AES128 or SHA1 when the computational work differences are dwarfed by
the DH computation, but I'm open to being convinced otherwise.  (Well,
I wouldn't mind using a lower security primitive if no one is going to
care about using a higher one, but I don't see value in defining
*both*.)

---

From: Matthew Dempsky <[email-masked]>
Date: Wed, 24 Mar 2010 14:02:06 -0700

> work), but also that this is supposedly covered by US patent 6141420.

To clarify this, I'm not taking a stance on the patent as valid or
not.  I've heard it's a concern, and so I'm cautious of it.  However,
if the people interested in using NIST-P-256 instead of Curve25519 are
not concerned about it, them I'm not either.