curve25519 for authentication?
kaxisus
authentication (certificates, signing, etc.) as a replacement for RSA,
or should curve25519 only be used for Diffie-Hellman key agreement?
Thanks,
-Andrew
Tom St Denis
This is one of the downsides to homebrew crypto. People dive into it
and few others have really looked at it. The NIST series of curves and
typical implementations are well suited to DH and DSA already...
That said ...
Look for postings by "xmath". He/she/it were working on ways of making
digital signatures with curve25519 by recovering the Y coordinate.
Tom
Mark Wooding
I can't think of any reason why EC(KC)DSA wouldn't be a sensible
signature scheme to use with this curve.
As far as I can see, it's just a curve for which djb has worked out an
efficient way of doing arithmetic, and in which the DDH problem seems to
be hard. The security proofs for DSA variants tend to show that they're
secure assuming only that the discrete log problem in the relevant group
is hard, which is obviously necessary for DDH to be hard. So I don't
see any problem with using curve25519 for signatures, as long as you
keep your signing keys for signing and key-exchange keys for key-
exchange.
-- [mdw]
xmath
Authentication doesn't always require signatures. In fact, for
communications between two parties you can (and probably should) just
use a MAC whose key has been set up by DH key agreement. Signatures
are only strictly needed if you need non-repudiation, meaning everyone
can verify that the signature is yours. With a MAC, any party who can
verify it must have the key, and would also be able to forge the MAC.
DH+MAC quickly gets inefficient for many recipients, as you need a key
agreement per recipient. Verification is always faster than verifying
an ECDL-based signature though, and if you already use static-static DH
for encryption then you get authentication almost for free.
Anyway, as for real signatures, you can just stick curve25519 into
basically any DL-based signature scheme. For performance you can omit
the y-coordinate everywhere if you do a trick during key generation:
make sure the y-coordinate of the public key is "positive" by negating
the private key if your original choice made the public key "negative".
Then when you need to recover the y-coordinate during signature
verification, you also pick the "positive" one.
Note that there isn't actually such a thing as positive or negative in
a finite field, but you should just pick some definition. My favorite
is to define elements with the least significant bit set (when fully
reduced) to be negative, and non-zero elements with the least
significant bit clear (when fully reduced) to be positive. This makes
sure that if x is positive then -x (= p-x) is negative and vice versa.
- xmath
kaxisus
> Authentication doesn't always require signatures. In fact, for
> communications between two parties you can (and probably should) just
> use a MAC whose key has been set up by DH key agreement. Signatures
> are only strictly needed if you need non-repudiation, meaning everyone
> can verify that the signature is yours. With a MAC, any party who can
> verify it must have the key, and would also be able to forge the MAC.
The idea is to use certificates to validate the identity of both sides
of the connection (peers) to prevent an attacker doing nasty things and
modifying packets in the middle of the connection. Ephemeral DH is
vulnerable to MIM attacks, so the idea would be to use pre-shared
public keys to validate the peer's identity, similar to SSH host keys
(or TLS, but without the complexity of X.509 certificates).
> DH+MAC quickly gets inefficient for many recipients, as you need a key
> agreement per recipient. Verification is always faster than verifying
> an ECDL-based signature though, and if you already use static-static DH
> for encryption then you get authentication almost for free.
Well, a MAC requires that a secret key is already established, so it
doesn't solve the MIM problem. Obviously once a key is established a
MAC is useful for guarding the integrity of individual messages.
My idea is that presumably curve25519 used in a signature scheme would
be faster then RSA, and require smaller keys to provide the same level
of security.
For comparison, on my notebook your curve25519 EC-KCDSA takes 1.25ms to
generate a signature compared to 5ms for 1024-bit RSA (OpenSSL impl.),
and presumably djb's assembly implementations would be even faster.
Actually, that brings to mind another question, what is the relative
security (in terms of bits) of RSA vs. EC? I've seen a comparisn of
1024 bit RSA to 170 bit EC (based on current known attacs), which seems
to be about 3:1. Is this correct?
Thanks,
-Andrew
Mark Wooding
> Actually, that brings to mind another question, what is the relative
> security (in terms of bits) of RSA vs. EC? I've seen a comparisn of
> 1024 bit RSA to 170 bit EC (based on current known attacs), which seems
> to be about 3:1. Is this correct?
The ratio gets bigger for larger key lengths. This is because
the best known attacks against RSA are subexponential, whereas the best
known attacks against (properly-chosen) elliptic curves are fully
exponential. You need /much/ longer RSA keys for equivalent security to
a double-size elliptic curve.
See, for example, RFC3526 for a quick comparison table, and Annex D of
IEEE P1363a for more detailed comparisons.
-- [mdw]
xmath
> The idea is to use certificates to validate the identity of both sides
> of the connection (peers) to prevent an attacker doing nasty things and
> modifying packets in the middle of the connection. Ephemeral DH is
> vulnerable to MIM attacks, so the idea would be to use pre-shared
> public keys to validate the peer's identity, similar to SSH host keys
Yes, so you could do DH with static keys -- where the public keys are
either known good by the parties (securely exchanged in advance) or
signed by a trusted CA.
Once the public DH key has been verified to be genuine (you'd have the
same problem with signing keys) it takes only one DH operation to
establish a shared secret that you can use for MAC. Furthermore you
can even cache this shared secret if you communicate with that peer
often. You then use ephemeral-ephemeral DH, protected under this MAC,
to negotiate the session key for forward secrecy.
Even without the caching, doing one static-static DH is faster than a
signature verification (unless you use factorization-based signatures,
in which case it's the signing that gets slow).
You can even directly use the static-static DH shared secret (possibly
hashed with a nonce) for encryption + MAC if you don't need forward
secrecy.
> My idea is that presumably curve25519 used in a signature scheme would
> be faster then RSA
RSA verification has faster verification though, and is possibly a
better choice for certificates (which are signed once and verified
often). ECDL-based signatures and public keys are smaller though and,
allows for code reuse.
> Actually, that brings to mind another question, what is the relative
> security (in terms of bits) of RSA vs. EC?
I think NIST equates 256-bit ECDLp with 3072-bit RSA or classic DL.
- xmath