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

From: [email-masked]
Date: Thu, 24 Mar 2016 08:19:04 +0100

Hello Sharon, 

first of all: thank you. We appreciate your extensive and highly valuable 
feedback.
Replies to some of the points you made can be found in line.

Best regards,
Kristof

>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).

Do I understand correctly that the goal of having only *one* operation 
would only be achievable in connection with the contents of your second 
mail (regarding the shortening of the KE protocol to 2 instead of 3 round 
trips)?

>
>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.

Point taken.

>
>(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 designed things this way so that there would be different certificates 
for the two different roles. What we had in mind was that the client 
authorization and server authorization aspects could be managed by 
separate authorities.

Note that the certificate for an NTS client will presumably have generally 
lower trust requirements than that for an NTS server, to the point where 
for many use cases, the client certificate may just be self-signed.

>
>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?

The aim in all NTS-related documents was to intentionally leave the choice 
of CA infrastructure generic.
(Related: do you see any points in the specification documents where this 
is not the case? Our lack of expertise in the area of CA infrastructures 
might have caused this.)

>
>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?

I honestly have no answer to this question, because I had always 
considered it good practice to keep those two aspects separate, especially 
key-wise.

>
>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.

Apart from shortening the KE protocol (see below), what would be the 
outline of your proposal to lessen the server's workload?

>
>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].
>
> 

> 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 Ran Canetti [1] and Hugo Krawcyzk [2]. As I wrote in an earlier 
email, we believe NTS's KE can > be modified
> to use one public key crypto operation, rather than three.
>
> We also believe that the protocol can be modified to done in 2
> round trips (4 messages), rather than in 3 round trips (or 6
> messages). The current NTS draft cleverly protects against off-path
> DDoS amplification attacks, using the first round trip. Our
> suggestions would compress the last two round trips into one.  How this 
is done depends on answers to > my questions in my previous email.

There was appoint in time at which we discussed doing this (we formerly 
had separate exchanges for algorithm negotiation and certification, and we 
had this discussion after we united those two exchanges). We decided 
against it, as far as I recall because of reasons which are not valid 
anymore (we once had a sign-first-then-encrypt scheme which would have 
made things difficult, and our discussion also took place when the access 
messages protecting against DDoS were not yet in place).

Currently, I do not at first glance see concrete reasons why the 
association and cookie messages could not be united into one single 
exchange. However, we would like to run any proposal for such a new 
exchange through automated analysis tools before bringing it into the 
specification.

>
> This would help the KE complete faster, so clients could start to
> take authenticated time sooner.
>
> Also, the WG discussed running client/server timing queries in
> parallel with the NTS KE, so clients can get time fast. (eg running
> iburst in parallel with the NTS KE). We believe that this is
> possible, but from a *security perspective* this must be done
> carefully.
>
> Why?
>
> Suppose an unauthenticated timing exchange happens and convince 
> the client to update its clock before > KE completes. Then,
> man-in-the-middle can trick the client into updating its clock to a
> bogus time in the past. Then, the attackers inject old compromised
> certificates into the KE exchange. (That is, a revoked/expired
> certificate for which the attacker has learned the secret key
> corresponding to the public key in the certificate.) The client is
> in the past, so it accepts the old bogus certificates, and the
> attacker has defeated any protection provided by NTS. (This is very
> related to the attack by Selvi in [5] and what we wrote about
> attacking SSL certificates in Section III of our paper [6]. See
> also [7].)
> 
> We believe the NTS KE can be modified to authenticate timing
> messages sent in parallel with the KE. Note that this must be done
> *without* requiring these initial timing messages to be MAC'd,
> since before the KE completes, the client and server will not have
> a shared symmetric key.
> 
> We believe that the NTS KE can be modified to include this feature.
> See *. Is this of interest?

I have toyed with ideas like this previously, although for me the 
application had always been more in the direction of reducing latency on 
time_response messages (by sending a verifying MAC in a later message). 
The reason we never introduced anything like it was that (as you also 
state below for your outlined proposal) it would require modifications to 
the client behavior on the level of the time synchronization protocol, 
whereas we have always tried to specify NTS in such a way that, at least 
for unicast, it can run without modifications to the time synchronization 
mechanisms themselves. 

>
> Sharon
>
> * Roughly, the idea is to compute an incremental hash of all the
> unathenticated timing messages running in parallel with the KE.
> Then, once the KE completes and the client and server share a key,
> this key can be used to MAC this incremental hash. In addition to
> this, we would require the client *not* to update its local clock
> until it has validated this MAC of the incremental hash. In other
> words, the client collects timing samples while the KE is running,
> but updates its clock only after the KE completes. If the KE
> completes in 2 round trips, this might perform reasonably well.