Subject: [TICTOC] WGLC on NTS: Public key crypto for key exchange

From: Sharon Goldberg <[email-masked]>
Date: Wed, 23 Mar 2016 03:50:57 -0400

Dear WG,

Aanchal Malhotra and I reviewed the client/server (unicast) key
exchange (KE) protocol in the NTS draft (-013). We also discussed
it with cryptographers Ran Canetti [1] and Hugo Krawcyzk [2], who
have invented HMAC [3] and TELSA, developed the KE protocols used
in TLS and IPsec, and have also authored one of the standard models
for proving the security of KE protocols (the Canetti-Krawcyzk
model[4]), etc.

Currently the NTS KE protocol requires *three* public-key crypto
operations as part of the KE: two signatures and one encryption.
Only *one* public-key crypto operation is needed for most one-sided
authentication KEs (where the client authenticates the server, but
the server does not authenticate the client, as in NTS's default
mode).

The use of two signatures and one encryption in the KE has some
undesirable consequences:

(2a) Performance. Requiring three PK operations more
computationally intensive than using just one. Especially if RSA is
used in the current KE protocol, see * below.

(2b) Key management. The protocol requires the client to have an
*encryption* keys, and the server to have a *signing key*. Because
of NTP's hierarchical client-server model, this means that most
hosts with need to main *two* public keys and corresponding
certificates---one for signing and one for encrypting. (Think of a
stratum 2 host that is the client of a stratum 1, and also a server
from straum 3 hosts.) These hosts now how to purchase, renew, etc
two crypto certificates instead of one.

We believe the protocol can be modified to use only one public-key
crypto operation. Regarding these modifications we have these
questions:

a) What certificate authority (CA) infrastructure will NTS use? The
same one as is used for TLS?

According to Hugo, today's TLS CA infrastructure makes it easier to
obtain certificates for *signing keys* (that can be used for
public-key (PK) signatures) than for *encryption keys* (that can be
used for PK encryption). Also, most CAs only offer RSA keys for PK
encryption, which has performance some issues for NTS's current KE,
see * below.

b) Does NTS prefer to require hosts to have certificates for PK
*signing* or for PK *encryption*? It should be possible to have KE
that uses only one PK crypto operation in either case. Or does either
option work?

Sharon

* If NTS's current KE wanted to have only one certificate per host,
it would need to use RSA certificates, because these can be used
for both signing and encrypting. But:

a) RSA has a performance disadvantage for NTS's current KE.
RSA signing/decrypting is at least 10x slower than RSA
verifying/encrypting. The current NTS KE has the *server* doing two
signing operations and one decryption. Thus, the server is doing 2
(out of 3) computationally expensive RSA operations (signing),
while the client is doing only 1 (out of 3) expensive RSA operation
(decrypting). We might want to have less load on the server, since
a server will have more NTS associations than a client.

b) Being locked into RSA means that elliptic curve cryptography
(ECC) cannot be used. Many WG's moving toward ECC [5,6,7,8]
because:

    - ECDSA signatures provides higher security levels with shorter
signatures and shorter keys than RSA. For example, 3072-bit RSA
(which has 3072-bit keys and signatures) is though to provide a
security level equivalent to 256-bit ECDSA (which has 256-bit keys
and 512-bit signatures.

   - ECDSA signing is about 3x times faster to compute than RSA
   signing for similar security levels.  In fact, when ECDSA is
   optimized it can even be 10x faster than RSA: see the performance
   numbers in the table on page 21 of this ID [9].

References
[1] https://www.cs.bu.edu/fac/canetti/
[2] https://simons.berkeley.edu/people/hugo-krawczyk
[3] https://cseweb.ucsd.edu/~mihir/papers/hmac.html
[4] http://link.springer.com/chapter/10.1007/3-540-44987-6_28#page-1
[5]
http://www.sigcomm.org/sites/default/files/ccr/papers/2015/October/0000000-0000002.pdf
[6] https://www.cloudflare.com/dnssec/ecdsa-and-dnssec/
[7] https://www.ietf.org/rfc/rfc4492.txt
[8] http://w2spconf.com/2014/papers/TLS.pdf
[9] https://tools.ietf.org/html/draft-vcelak-nsec5-02

-- 
Sharon Goldberg
Computer Science, Boston University
http://www.cs.bu.edu/~goldbe

---

From: Kurt Roeckx <[email-masked]>
Date: Wed, 23 Mar 2016 18:56:02 +0100

> encryption, which has performance some issues for NTS's current KE,

An RSA key should have:
            X509v3 Key Usage: critical
                Digital Signature, Key Encipherment

If you don't have the "Key Encipherment" you wouldn't be able to
do an RSA key exchange.

An ECDSA certificate can only be used to sign.

A related question is if we should have special requirements for
certificates.  For instance, is a domain validated certificate
good enough?  Should we do OCSP?  Can we staple the OCSP or should
the CAs support OCSP with a nonce?

Kurt

---

From: Harlan Stenn <[email-masked]>
Date: Thu, 24 Mar 2016 04:37:38 +0000

For some associations, one-sided authentication is all that is needed.

For others, both sides will need to authenticate.  We're looking at
creating some authorization capabilities as well, down the road a little
bit.

We should be able to determine 1- or 2-sided authentication as part of
the exchange, and act accordingly.

H