Subject: [TICTOC] WGLC on NTS: Round trips for key exchange

From: Sharon Goldberg <[email-masked]>
Date: Wed, 23 Mar 2016 03:59:48 -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 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.

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?

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.

References
[1] https://www.cs.bu.edu/fac/canetti/
[2] https://simons.berkeley.edu/people/hugo-krawczyk
[5]
https://media.defcon.org/DEF%20CON%2023/DEF%20CON%2023%20presentations/DEFCON-23-Jose-Selvi-Breaking-SSL-Using-Time-Synchronisation-Attacks.pdf
[6] https://eprint.iacr.org/2015/1020.pdf
[7]
http://arstechnica.com/security/2015/10/new-attacks-on-network-time-protocol-can-defeat-https-and-create-chaos/

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

---

From: Hal Murray <[email-masked]>
Date: Wed, 23 Mar 2016 14:19:18 -0700

[email-masked] said:
> This is an interesting idea, but wouldn't the server have to save the
> incremental hash between client's requests? An NTP server normally doesn't
> keep any state for clients and when it does (e.g. for monitoring and rate
> limiting), it's all in a constant amount of memory to prevent DoS attacks on
> the server. Clients that would benefit most from having timestamps
> authenticated retroactively probably would be the ones that poll the server
> least frequently and are most likely to have their state on the server lost.

I think it is worth thinking about that issue.  Memory has gotten a lot 
cheaper since the early days of NTP.  We now have problems with bufferbloat.

I think the limit on dedicated public NTP servers in network bandwidth.  A 
gigabyte or two would not be a problem.

For non-public servers, either there aren't a lot of clients (small network) 
so the memory requirements won't be a problem when NTP is run in the corner 
of another server or there are enough clients so the total cost of having a 
dedicated server isn't a serious problem.

The DoS problem gets interesting.  Does the server need storage between NTP 
requests or just for a short time while getting started?

-- 
These are my opinions.  I hate spam.

---

From: Sharon Goldberg <[email-masked]>
Date: Wed, 23 Mar 2016 18:17:33 -0400

> > > incremental hash between client's requests? An NTP server normally
> > > doesn't keep any state for clients and when it does (e.g. for
> > > monitoring and rate limiting), it's all in a constant amount of memory
> > > to prevent DoS attacks on the server.
> >
> >
> > If an incremental hash is used, then it would require a constant amount
> of memory on the server.
>
> Per client, right?
>
> Right.  But only for the duration of the KE; afterwards this could be
purged.

However, if this per client state really bothers us, there is a way around
it.

Before I say how to get around it, I was wondering why this bothers us so
much?  The current ntpd already has the server saves per-client state, for
poll interval, rate limiting, and symmetric keys.  Is this really such a
problem to store a bunch of additional ~256 bit values for each client?
And especially if this state only lives for the duration of the KE?

Anyway, here is a generic trick for getting rid of state on the server,
that could be useful for NTS.  The trick is to use a cookie.

1)  Let the server have a local symmetric key $k$ that only it knows. It
only needs on key for each client.
2)  Let $s$ be the per client state that the server doesn't want to store.
For example, the session key with the client, or the incremental hash, or
whatever we want.
3) The server computes cookie $c$ = AuthEnc_{$k$} ($s$), where AuthEnc is
an authenticated encryption scheme like GCM [1].
4) The server sends $c$ to the client.
5) The client stores $c$.  Note that since the client doesn't know $k$, it
can't read what is in $c$.
6) The client sends $c$ to the server with its request.
7) The server knows $k$, and can AuthDec_{$k$}($c$) to learn $s$.

We would need to be careful with session identifiers so attackers can't
replay old cookies here but this is the basic idea.  I can do some research
on exactly how this should be done, I think there have been papers on it.

But I think it is worthwhile to carefully evaluate if this type of approach
is really needed for NTS, or is it just adding additional complexity.

> > Clients that would benefit most
> > > from having timestamps authenticated retroactively probably would be
> the
> > > ones that poll the server least frequently and are most likely to
> > > have their state on the server lost.
> >
> >
> > I'm not sure I understand this point.  If a client is querying
> > infrequently, why not just wait until the KE completes, and the key is
> > established, before sending timing messages that can then be
> authenticated
> > with the established key?   Why would you want to start a timing exchange
> > in parallel with the KE?
>
> My thought was that clients using longer interval would save more time
> by having old timestamps authenticated.
>
> If I understand the scheme you propose correctly, the client would
> have samples from previous packets in the NTS initialization validated
> when the last packet in the initialization is received.

Yes. So I imagine the client starting. Then it initiates NTS and in
parallel does some timing exchanges that are not MAC'd. These timing
exchanges won't update the clock yet.  Then once the NTS KE completes, it
also authenticates these timing exchanges.  At this point, the client can
choose to update its clock (or not) per the usual NTP processes.

> The question
> is what the client could do with these extra samples. I guess they
> could be useful to estimate the frequency error of the clock as ntpd
> does in the freq state for instance. A client polling at 64s interval
> would save more time with this than a client using 2s poll (iburst).
>
> Not sure, not an expert on NTP's timing algos. But we have seen that upon
initalization, ntpd requires about 4 timing samples before it updates its
clock. So it could collect these timing samples while the NTS KE is running.

> There is also a question whether the client would really want to use
> any samples from the non-timing NTS exchanges as the packets are
> longer and asymmetric, creating an extra error in the measurements.
>
>
So, in my mind, the timing messages would be sent in separate packets from
the NTS KE messages.  They would be sent in parallel. That way, the crypto
done in NTS does not mess up the accuracy of the timing exchanges.

[1] https://en.wikipedia.org/wiki/Galois/Counter_Mode

Sharon Goldberg

---

From: Sharon Goldberg <[email-masked]>
Date: Wed, 23 Mar 2016 18:18:29 -0400

Sorry correction to my email: the key $k$ held by server is just one key
for ALL clients.

On Wed, Mar 23, 2016 at 6:17 PM, Sharon Goldberg <[email-masked]> wrote:

> But I think it is worthwhile to carefully evaluate if this type of
> approach is really needed for NTS, or is it just adding additional
> complexity.
>

---

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

Sharon Goldberg writes:

...

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

If the two sides already have an ntp.keys file then this key can be used
for a MAC, correct?

If so, your paragraph can become:

 We believe the NTS KE can be modified to authenticate timing messages
 sent in parallel with the KE. Note that this MAY 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
 NTS-delievered symmetric key.  A traditional MAC produced as described
 in RFC5905 may still be used.

correct?

H

---

From: Harlan Stenn <[email-masked]>
Date: Thu, 24 Mar 2016 05:07:11 +0000

Also note that we do our best to avoid blocking in the server when doing
processing.

We cannot rely on threads, either.

If we're going to do a known-expensive CPU operation, we're very likely
going to find a way to do that operation while continuing to enable
processing of "normal" NTP packets.

There are a number of choices here, including deciding to delay the
response packet for a little while to give an expensive CPU operation
running in another thread or process time to complete.

H

---

From: Dieter Sibold <[email-masked]>
Date: Thu, 24 Mar 2016 10:02:45 +0100

> Am 23.03.2016 um 23:17 schrieb Sharon Goldberg <[email-masked]>:
> 
> > If an incremental hash is used, then it would require a constant amount of memory on the server.
> 
> Per client, right?
> 
> Right.  But only for the duration of the KE; afterwards this could be purged.
> 
> However, if this per client state really bothers us, there is a way around it.  
> 
> Before I say how to get around it, I was wondering why this bothers us so much?  The current ntpd already has the server saves per-client state, for poll interval, rate limiting, and symmetric keys.  Is this really such a problem to store a bunch of additional ~256 bit values for each client?  And especially if this state only lives for the duration of the KE?

Yes, this is true. But the capabilities of NTP to keep track of the states are very limited. Our NTP servers with the most current NTPD are only able to store about 12000 records, in which the oldest records are about 10 to 60 seconds old. They even cannot guarantee to memorize the state of a client when it is in iburst mode. Perhaps the implementation can be adjusted to allow for even more state information. However when we started this project we had and still have the requirement to have a solution that can allow a NTPD to serve at least 10^5 clients. That is the practical reason we wanted to have an approach that is stateless on the server side. Another reason is RFC 7384, Sec. 5.7, which state that a security mechanism should minimize the storage requirements of client state in the server.

Dieter

> 
> Anyway, here is a generic trick for getting rid of state on the server, that could be useful for NTS.  The trick is to use a cookie.  
> 
> 1)  Let the server have a local symmetric key $k$ that only it knows. It only needs on key for each client.
> 2)  Let $s$ be the per client state that the server doesn't want to store. For example, the session key with the client, or the incremental hash, or whatever we want.
> 3) The server computes cookie $c$ = AuthEnc_{$k$} ($s$), where AuthEnc is an authenticated encryption scheme like GCM [1].
> 5) The client stores $c$.  Note that since the client doesn't know $k$, it can't read what is in $c$.
> We would need to be careful with session identifiers so attackers can't replay old cookies here but this is the basic idea.  I can do some research on exactly how this should be done, I think there have been papers on it.
>  
> But I think it is worthwhile to carefully evaluate if this type of approach is really needed for NTS, or is it just adding additional complexity.
> 
> > > from having timestamps authenticated retroactively probably would be the
> > established, before sending timing messages that can then be authenticated
> Yes. So I imagine the client starting. Then it initiates NTS and in parallel does some timing exchanges that are not MAC'd. These timing exchanges won't update the clock yet.  Then once the NTS KE completes, it also authenticates these timing exchanges.  At this point, the client can choose to update its clock (or not) per the usual NTP processes.
>  
> The question
> Not sure, not an expert on NTP's timing algos. But we have seen that upon initalization, ntpd requires about 4 timing samples before it updates its clock. So it could collect these timing samples while the NTS KE is running.
>  
> So, in my mind, the timing messages would be sent in separate packets from the NTS KE messages.  They would be sent in parallel. That way, the crypto done in NTS does not mess up the accuracy of the timing exchanges.
> 
> [1] https://en.wikipedia.org/wiki/Galois/Counter_Mode <https://en.wikipedia.org/wiki/Galois/Counter_Mode> 
>  
> Sharon Goldberg
> http://www.cs.bu.edu/~goldbe <http://www.cs.bu.edu/~goldbe>_______________________________________________
> TICTOC mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tictoc

---

From: Dieter Sibold <[email-masked]>
Date: Thu, 24 Mar 2016 15:17:18 +0100

> Am 24.03.2016 um 09:49 schrieb Miroslav Lichvar <[email-masked]>:
> 
> On Wed, Mar 23, 2016 at 06:17:33PM -0400, Sharon Goldberg wrote:
>> poll interval, rate limiting, and symmetric keys.
> 
> The NTP specification doesn't require servers to save any state per
> client. The monitoring and rate limiting are optional features.

This is a valid argument. Together with the requirements formulated in RFC7384 this implies to formulate of a security mechanism which is stateless on the server side. But if we formulate NTS in such a way that the server keeps state of the client, NTS has to introduce the state. We cannot rely on NTP mechanisms.

>> Is this really such a
> That depends on the implementation. You can have an SNTP server with a
> GPS refclock running on a microcontroller with couple kilobytes of RAM
> and it can serve time to hunderds of thousands of clients. With NTS
> the requirements on memory shouldn't change much, the CPU just has to
> be faster or have the crypto algorithms implemented in HW.
> 
> There is no limit on the duration. The client may be polling the
> server just couple times a day. Let's not forget the key exchange will
> happen not only when the client is started, but also when the server
> refreshes its seed. We certainly don't want clients to drop to their
> minimum polling intervals or start a burst when that happens.
> 
> Yes. To me it looks like a lot of complexity with little gain.
> 
> I'm not sure if it's intentional, but recent versions of ntpd now
> update the clock with the first (authenticated) sample. Older versions
> and other implementations may require more.
> 
> Hm, I thought the incremental hash was meant for timestamps in the
> first few NTS packets.
> 
> If there were two associations per client, I think it would be even
> more complex. There would have to be some mechanism for the server to
> identify and link the two client associations, so it can hash the
> right timestamps (and not timestamps for some other client behind NAT
> for instance). The client would have to make sure requests from the
> two associations are not too close to each other to not violate the
> minimum request interval on the server.
> 
> This would effectively double the polling rate. If the client is
> allowed to increase its polling rate, I think it would be more useful
> to do that with the NTS association rather than adding an extra
> association, so the client would get the first authenticated sample
> sooner.
> 
> --
> Miroslav Lichvar
> _______________________________________________
> ntpwg mailing list
> [email-masked]
> http://lists.ntp.org/listinfo/ntpwg

---

From: [email-masked]
Date: Thu, 24 Mar 2016 15:40:53 +0100

> Anyway, here is a generic trick for getting rid of state on the 
> server, that could be useful for NTS.  The trick is to use a cookie.  
>
> 1)  Let the server have a local symmetric key $k$ that only it 
> knows. It only needs on key for each client.
> 2)  Let $s$ be the per client state that the server doesn't want to 
> store. For example, the session key with the client, or the 
> incremental hash, or whatever we want.
> 3) The server computes cookie $c$ = AuthEnc_{$k$} ($s$), where 
> AuthEnc is an authenticated encryption scheme like GCM [1].

Pretty straightforward.

> We would need to be careful with session identifiers so attackers 
> can't replay old cookies here but this is the basic idea.  I can do 
> some research on exactly how this should be done, I think there have
> been papers on it.
>
complexity.

Absolutely.
See also the end of this mail.

> exchanges won't update the clock yet.  Then once the NTS KE 
> completes, it also authenticates these timing exchanges.  At this 
> point, the client can choose to update its clock (or not) per the 
> usual NTP processes.
>
> > The question
> Not sure, not an expert on NTP's timing algos. But we have seen that
> upon initalization, ntpd requires about 4 timing samples before it 
> updates its clock. So it could collect these timing samples while 
> the NTS KE is running.
>  

I also do not think the client should use any such samples.

> So, in my mind, the timing messages would be sent in separate 
> packets from the NTS KE messages.  They would be sent in parallel. 
> That way, the crypto done in NTS does not mess up the accuracy of 
> the timing exchanges.

Yes, this seems like it would make the most sense for employing the 
proposed technique actually.
However, it does not get around the chicken-and-egg problem that was 
outlined earlier: a client who is initially without any sense of 
time/clock could be convinced to take old crypto data/certificates and 
then that would impede the security of everything that follows.

My position on the whole issue would be that if we introduced a mechanic 
as outlined in 1) - 7) *just* for an a posteriori verification of a small 
number of initial exchanges, then the cost of the added complexity would 
be too high.
If, on the other hand, we figured out how to get more use out of such 
techniques, then it might be worth it.

---

From: Sharon Goldberg <[email-masked]>
Date: Thu, 24 Mar 2016 15:44:10 -0400

> This sounds a lot like the TLS PSK (Pre-Shared Key) mode [3][4].

In TLS PSK there is still a key establishment handshake, to allow the two
sides to agree to use the PSK. Also, the PSK is usually just used to
authenticate the key exchange, not the actual traffic.

Harlan you are suggesting MACing the actual traffic with PSK right away
before the KE completes? I don't think this works since you will, just like
TLS, still need a key exchange to agree you need a PSK.

Moreover, adding a PSK mode to NTS adds additional complexity. Do we really
want to introduce this additional complexity?   I am very wary of this, as
recent attacks on TLS and IPsec have shown that the proliferation of modes
and complexity in these protocols can be exploited by attackers [1],[2].

Sharon

[1]
https://nohats.ca/wordpress/blog/2014/12/29/dont-stop-using-ipsec-just-yet/
[2] https://weakdh.org/
[3] https://eprint.iacr.org/2014/037.pdf
[4] https://tools.ietf.org/html/rfc4279

---

From: Sharon Goldberg <[email-masked]>
Date: Thu, 24 Mar 2016 16:05:56 -0400

On Thu, Mar 24, 2016 at 4:49 AM, Miroslav Lichvar <[email-masked]>
wrote:

> server just couple times a day.

Sorry, I'm confused.  The NTS key exchange is a 6-message exchange that
should happen "atomically" (ie. the server gets the clients KE msg,
processes it, and immediately sends its own message. & vice versa: the
client gets the servers KE msg, processes it, and immediately sends its own
message. )

If we are discussing state that only lives for the *duration of the KE* why
does it matter how often the client polls the server?

Let's not forget the key exchange will
> That's interesting point, but could you clarify why that would happen? Why
would clients react in this way?

> and other implementations may require more.
I think Danny Mayer told me that was a bug. But I don't know. ntpd 4.2.6
needs several samples.

> for instance).The client would have to make sure requests from the

> minimum request interval on the server.

Yes, that's true. This whole thing adds additional complexity.
So we should be sure it is needed before adding it!

> If the client is

I'm sorry I don't understand this last point, can you clarify?

Sharon

---

From: Dieter Sibold <[email-masked]>
Date: Fri, 25 Mar 2016 00:33:17 +0100

> Am 24.03.2016 um 21:05 schrieb Sharon Goldberg <[email-masked]>:
> 
> 
> 
> On Thu, Mar 24, 2016 at 4:49 AM, Miroslav Lichvar <[email-masked] <mailto:[email-masked]>> wrote:
> Sorry, I'm confused.  The NTS key exchange is a 6-message exchange that should happen "atomically" (ie. the server gets the clients KE msg, processes it, and immediately sends its own message. & vice versa: the client gets the servers KE msg, processes it, and immediately sends its own message. )
> 
> If we are discussing state that only lives for the *duration of the KE* why does it matter how often the client polls the server? 
> 
> That's interesting point, but could you clarify why that would happen? Why would clients react in this way?
>  

When the server refreshes his seed the client has to get its cookie. This is assumed to be done via a cookie exchange — one the last of the rounds of the KE. Therefore the client don’t need to reduce its polling interval. It will only miss one authenticated time exchange. 

> I think Danny Mayer told me that was a bug. But I don't know. ntpd 4.2.6 needs several samples.
>

---

From: Harlan Stenn <[email-masked]>
Date: Fri, 25 Mar 2016 09:09:19 +0000

Sharon Goldberg writes:
> Harlan wrote:
>> If the two sides already have an ntp.keys file then this key can be
>> used for a MAC, correct?
> 
> Harlan you are suggesting MACing the actual traffic with PSK right
> away before the KE completes? I don't think this works since you will,
> just like TLS, still need a key exchange to agree you need a PSK.

I'm only suggesting this as a possibility for situations where the
ntp.keys file is available.  This is OK as a solution for smallish sets
of machines.

It doesn't make much sense to set up private/symmetric key stuff only to
handle initial packets on a larger scale.

> Moreover, adding a PSK mode to NTS adds additional complexity. Do we
> really want to introduce this additional complexity?  I am very wary
> of this, as recent attacks on TLS and IPsec have shown that the
> proliferation of modes and complexity in these protocols can be
> exploited by attackers [1],[2].

Can one have reliable IPSEC if the time is unknown?

Once upon a time, we had Bell 212A modems (that had constant-delay
characteristics) and real copper wire between endpoints.  It did a
surprisingly good job of moving time around.  Then we got soft modems,
which introduced noticeable variation in the processing delays, and then
the phone system changed as well.  Phones are no longer a useful way to
move time around accurately.  IPSEC likely adds variable delays as well.

H

---

From: Hal Murray <[email-masked]>
Date: Tue, 29 Mar 2016 04:35:59 -0700

[email-masked] said:
> If I understand how NTS will be implemented correctly, the duration of the
> KE is proportional to the polling interval. 

It probably needs to be smarter than that.  If not, rekeying will take a long 
time after the polling interval has ramped up.

---

From: Miroslav Lichvar <[email-masked]>
Date: Tue, 29 Mar 2016 12:15:54 +0200

> client gets the servers KE msg, processes it, and immediately sends its own

As I understand it, NTS doesn't change anything in the NTP polling
process. It should be similar to Autokey. Clients poll the server as
they would normally without any authentication and NTS extension
fields are added to the packets depending on what state the NTS
association is currently in. Only when the NTS association is
initialized, the received packets are used for synchronization.

If the clients sent a new request immediately, that would create a
rapid burst and the server might drop the packets due to rate
limiting. If the server didn't respond, the client would have to use a
timeout for a new request with some exponential backoff. To me it
seems easier to rely the normal NTP polling process, which was
designed to not overload the server.

>From the server point of view, I think there should be no change in
the observed packet rate (after IP defragmentation) when clients
enable NTS.

> does it matter how often the client polls the server?

If I understand how NTS will be implemented correctly, the duration of
the KE is proportional to the polling interval.

> would clients react in this way?

They might want to reinitialize the NTS association as quickly as
possible and this would increase the request rate observed on the
server. I suspect the expensive crypto operations will be a problem on
busy servers even if the request rate doesn't change and the servers
will probably need to use multiple seeds for groups of clients split
by their IP address and refresh the seeds sequentially in order to
spread the extra CPU load.

> I think Danny Mayer told me that was a bug. But I don't know. ntpd 4.2.6

Yes, from the commit message it does look like an unintentional
change.

> I'm sorry I don't understand this last point, can you clarify?

If we compare clients that send the same number of packets in the same
interval, the client that puts all packets in the association using
NTS will have the first authenticated sample sooner than a client that
has a parallel association with the server. Here is an illustration:

packet #        client 1                client 2

1               client_access           client_access
2               client_assoc            non-NTS
3               client_cook             client_assoc
4               time_request            non-NTS
5               time_request            client_cook
6               time_request            non-NTS
7               time_request            time_request

-- 
Miroslav Lichvar

---

From: Miroslav Lichvar <[email-masked]>
Date: Tue, 29 Mar 2016 15:26:06 +0200

> time after the polling interval has ramped up.

If the client is using a long polling interval, why would long NTS
reinitialization be a problem?

A missed NTP packet or client dropping a bad sample is a common
occurence. For instance, the clock filter in ntpd can drop up to 7
consecutive samples. A couple of samples dropped due to invalid
authentication after the server refreshes its seed shouldn't be a big
deal.

-- 
Miroslav Lichvar

---

From: Sharon Goldberg <[email-masked]>
Date: Tue, 29 Mar 2016 10:22:56 -0400

> authentication after the server refreshes its seed shouldn't be a big

What if an NTS KE message is lost?  How will NTS recover and will it need
to wait an entire poll interval to do that?

Sharon

---

From: Sharon Goldberg <[email-masked]>
Date: Tue, 29 Mar 2016 10:44:23 -0400

On Tue, Mar 29, 2016 at 6:15 AM, Miroslav Lichvar <[email-masked]>
wrote:

> This worries me.

Note that NTS uses certificates to authenticate the KE.  Generally, a
certificate chain cannot fit into a single IP packet.

See below for some examples. The first is a "Certificate" messages from
TLSv1.2 for a certificate chain of length 2; it was sent in 2 TCP
segments.  The second "Certificate" message was for a chain of length 4
that had to be sent in 4 segments.  Adding OCSP would take further length
to the packet.

http://www.cs.bu.edu/~goldbe/share/oneCertMsg2Pkts.PNG
http://www.cs.bu.edu/~goldbe/share/oneCertMsg4Pkts.PNG

It seems very likely that even just one single message of the NTS KE will
require sending multiple packets to the server.  This needs to be dealt
with somehow.

As such, I'm not convinced that sending these KE messages according to the
NTP polling interval makes sense.  I'm further concerned because I don't
understand how the NTS KE will deal with lost packets.

Sharon

---

From: Miroslav Lichvar <[email-masked]>
Date: Tue, 29 Mar 2016 16:51:48 +0200

> What if an NTS KE message is lost?  How will NTS recover and will it need

A missed reply doesn't change the client's NTS state. On next poll, it
will send a new request with the same NTS message as before, just
nonce will be different.

> to wait an entire poll interval to do that?

Yes and that interval needs to be slowly increasing up to the maximum,
as NTP and other network protocols normally do when packets are
getting lost. If the server was operating at its maximum capacity and
a significant number of its clients shortened their interval after
missed reply, I think it would basically be a DoS attack.

-- 
Miroslav Lichvar

---

From: Miroslav Lichvar <[email-masked]>
Date: Tue, 29 Mar 2016 17:26:54 +0200

> > the observed packet rate (after IP defragmentation) when clients

(Sharon, the last sentence is not from my mail, it seems your client
breaks quoting sometimes).

> certificate chain cannot fit into a single IP packet.

Yes, there was a discussion about that on the ntpwg list recently and
currently NTS relies on IP fragmentation even with the standard
ethernet MTU of 1500. I agree it could be a problem. It seems IPv6
doesn't even require hosts to defragment packets larger than 1500
octets.

Adding fragmentation to the NTP protocol seems like a horrible idea.

Would it be safe to assume an NTP+NTS packet can always contain a
single certificate without requiring fragmentation with MTU of 1500?
Perhaps the server_cook message could be split into multiple messages.
With the client_cook message I suspect it would be much more
difficult.

-- 
Miroslav Lichvar

---

From: Harlan Stenn <[email-masked]>
Date: Tue, 29 Mar 2016 22:36:55 +0000

I don't think we want a *requirement* that we "advance" the NTS
handshake process in strict lockstep with the NTP packet exchange.

This could be the choice of an implementation but it should not be a
requirement.

As I recall (and I could be wrong), the 3rd NTS packet, which is the
start of the 2nd NTS exchange, contains information that is
computationally expensive for the "other side" to process.  While the
extra processing in between T2 and T3 delay is not an issue for the
protocol itself, it could well be more expensive than is desired for a
blocking operation.

For a multitasking server, it could well be that one "thread" does the
ordinary NTP handling while another does the NTS work.  The first thread
might say "I'm willing to wait N milliseconds before I reply to this
request", and if the NTS processing gets done in time then the
client_assoc info is ready in that response.  If not, a "plain" response
goes back, the client sends a plain NTP packet as its next query, and
the server replies with NTP+NTS-client_assoc.

I think it's a Bad Idea to make assumptions and "proactive restrictions"
about how to do these exchanges.

H

---

From: Miroslav Lichvar <[email-masked]>
Date: Wed, 30 Mar 2016 10:06:02 +0200

> the server replies with NTP+NTS-client_assoc.

If the server is not able to respond in time (whatever that means), it
shouldn't respond at all. The client will try again later. Responding
with a plain NTP message would not help as the client would ignore the
reply. Even if it didn't ignore it, the new request would have to be
the same NTS message as before, because the server doesn't have the
previous request. I doubt any server implementation would want to
cache requests and replies.

> about how to do these exchanges.

What restrictions would you like to loose? The suspension of the NTS
protocol with plain NTP messages you described seems to me like a
major complication in the protocol, which would require the server to
cache the client's requests.

-- 
Miroslav Lichvar

---

From: [email-masked]
Date: Wed, 30 Mar 2016 10:06:31 +0200

>It seems very likely that even just one single message of the NTS KE
>will require sending multiple packets to the server.  This needs to
>be dealt with somehow.
>
>As such, I'm not convinced that sending these KE messages according
>to the NTP polling interval makes sense.  I'm further concerned
>because I don't understand how the NTS KE will deal with lost
>packets.

We will add a paragraph treating the topic of lost packets.

Our intended approach is to just have the client go into a waiting state for each of its still unanswered requests.

This waiting state would either be ended successfully by a verifiable reply (what verifiable means depends on the context), or unsuccessfully by reaching a timeout value (which would be configurable in its length, but whose existence would be mandatory). In the latter case, either a re-transmission of the last message or a restart of the protocol would occur, depending on context

Does anyone here have criticism or other suggestions on this topic?

Kristof

---

From: Harlan Stenn <[email-masked]>
Date: Wed, 30 Mar 2016 10:57:35 +0000

> cache requests and replies.

I disagree, but this may need to become a local policy choice.

Are you suggesting the server saves state between the first incoming
client request that we can't respond to "fast enough" and then on the
next poll the server sees that the client request is identical, so it
can immediately respond with the data it has had time to generate?

If the answer is "no" then the client will never get an NTS handshake.

> What restrictions would you like to lose? The suspension of the NTS

As opposed to degrading the server's performance?

We're not talking about caching very much information here, or caching
it for very long.

I think we should define as few restrictions as possible here, and leave
it to the implementation to decide what works best.

H

---

From: Miroslav Lichvar <[email-masked]>
Date: Wed, 30 Mar 2016 13:27:33 +0200

> can immediately respond with the data it has had time to generate?

Yes, if you really needed to significantly delay the response, this
would be one way do to it without having to modify the NTS spec. But I
still don't see how it's useful and I'd be worried about DoS attacks
it could bring in.

> As opposed to degrading the server's performance?

I'm not sure I follow. How is this related to the server's performance?

> it to the implementation to decide what works best.

As long as the protocol stays simple and secure, I'm ok with that.

-- 
Miroslav Lichvar

---

From: Danny Mayer <[email-masked]>
Date: Wed, 30 Mar 2016 14:15:46 -0400

On 3/29/2016 10:44 AM, Sharon Goldberg wrote:
> will require sending multiple packets to the server.Â  This needs to be
> dealt with somehow.Â Â 
> 
> As such, I'm not convinced that sending these KE messages according to
> the NTP polling interval makes sense.Â  I'm further concerned because I
> don't understand how the NTS KE will deal with lost packets.
> 

Some of this was discussed elsewhere. There are two cases to look at:

1) Client sends a packet and the server doesn't receive it
This is the simple case. If the client doesn't get a response from the
server it can reissue the same request and hope that the server gets it
the second time. Open issue is how many retries should there be before
it gives up?

2) The client sends the packet and the server receives it and responds
but the client doesn't get the response. If the client now resends the
request, what should the server do? Resend? Ignore? Does it need to
remember what it last sent? This is a much harder case to resolve.

Danny

---

From: Danny Mayer <[email-masked]>
Date: Wed, 30 Mar 2016 14:16:18 -0400

Danny

---

From: Hal Murray <[email-masked]>
Date: Wed, 30 Mar 2016 14:53:37 -0700

...
> Open issue is how many retries should there be before it gives up?

Does crypto complicate that decision?

> 2) The client sends the packet and the server receives it and responds but
> the client doesn't get the response. If the client now resends the request,
> what should the server do? Resend? Ignore? Does it need to remember what it
> last sent? This is a much harder case to resolve. 

I agree.  That needs to be part of evaluating any proposal that involves 
multiple packets.

--------

Perhaps the setup exchange should not be piggybacked on top of NTP packets.

If it uses a separate port or TCP it would be easier to put the setup work in 
a separate process.

TCP avoids the lost packet problem.  (Or at least simplifies it.)  It might 
avoid the problems with certificate chains overflowing a packet.

---

From: Harlan Stenn <[email-masked]>
Date: Wed, 30 Mar 2016 22:32:27 +0000

> still don't see how it's useful and I'd be worried about DoS attacks

I don't know how to describe this any better.

What is the DoS vector you see?

The premise is that the crypto calculations "take longer than we want to
wait" for something to do in between T2/T3.

If these crypto operations take "a relatively long time" we may choose
to do them outside the main processing "thread".

> I'm not sure I follow. How is this related to the server's performance?

A server cannot do "expensive" operations in-line.

This is the thing I don't know how to describe better.  I've described it
several times from several angles.

> As long as the protocol stays simple and secure, I'm ok with that.

OK.

H

---

From: Hal Murray <[email-masked]>
Date: Wed, 30 Mar 2016 15:47:41 -0700

> A server cannot do "expensive" operations in-line.

Are you confusing the general problem with a specific implementation?

How do I decide if something is "expensive"?

---

From: Harlan Stenn <[email-masked]>
Date: Wed, 30 Mar 2016 23:11:50 +0000

> Are you confusing the general problem with a specific implementation?

I don't think so.  It's a general implementation issue, not a specific
implementation issue.

> How do I decide if something is "expensive"?

I don't know, how do you decide if something is "expensive"?

H

---

From: Miroslav Lichvar <[email-masked]>
Date: Thu, 31 Mar 2016 09:27:03 +0200

> What is the DoS vector you see?

Any state that the protocol would require on the server is a potential
vector for a DoS attack. How easy is for an attacker to make new
"connections" and allocate memory on the server? Can the attacker
prevent other clients from fully forming the NTS association?

> to do them outside the main processing "thread".

Ok, but why would you not send the result to the client when the
operation is finished? Are you expecting it will take longer than some
minimum expected polling interval of the client (e.g. 1 second)?

-- 
Miroslav Lichvar

---

From: Harlan Stenn <[email-masked]>
Date: Thu, 31 Mar 2016 07:50:08 +0000

Miroslav Lichvar writes:
> "connections" and allocate memory on the server?

While great hunks of this are implementation-dependent, I suspect no
additional memory will be required to answer "now" as opposed to
"later".  The difference is "duration" and it's easy enough to deal with
that.  There are other steps that can be taken, too.

> Can the attacker prevent other clients from fully forming the NTS
> association?

How?

> minimum expected polling interval of the client (e.g. 1 second)?

In a client/server situation, how would you propose to do that before
the next poll?

What benefit do you gain from doing this?

H

---

From: Miroslav Lichvar <[email-masked]>
Date: Thu, 31 Mar 2016 09:58:44 +0200

> the second time. Open issue is how many retries should there be before

I think this is handled by NTP. If it's a persistent association, the
client doesn't give up, it will just increase the polling interval up
to the maxpoll. If it's an ephemeral association, it will be
demobilized at some point.

I'm not sure if NTS needs to change anything in that.

> remember what it last sent? This is a much harder case to resolve.

I'd expect the server to respond to all requests it can or is
configured to (e.g. with rate limiting), like an NTP server normally
does. Should it be different with NTS?

-- 
Miroslav Lichvar

---

From: Miroslav Lichvar <[email-masked]>
Date: Thu, 31 Mar 2016 10:54:49 +0200

> that.  There are other steps that can be taken, too.

If you want to respond later, you need to save that response
somewhere. And when you have too many reponses saved, you need to drop
some of them.

> > Can the attacker prevent other clients from fully forming the NTS

By forcing the server to drop the saved response which the client will
need. If the server doesn't save any state, there is nothing for the
attacker to play with.

> In a client/server situation, how would you propose to do that before

Like with any other NTP packet? Respond immediately when the request
is processed. The crypto operations should be much faster than the 2s
iburst interval, I don't think we need to worry about clients sending
new request before they get the reply. If there are more requests than
the server can handle, then some of them will be dropped.

-- 
Miroslav Lichvar

---

From: Hal Murray <[email-masked]>
Date: Thu, 31 Mar 2016 02:02:47 -0700

[email-masked] said:
> I'd expect the server to respond to all requests it can or is configured to
> (e.g. with rate limiting), like an NTP server normally does. Should it be
> different with NTS? 

Since it's reasonably easy to inject packets with forged source address, rate 
limiting is an opportunity for denial of service without sending a lot of 
traffic that might attract notice.  If you want to keep a site from using 
NTP, just send enough requests "from" that site to all the NTP servers it 
might use.  You only need to send enough traffic to keep the the rate 
limiting activated.

---

From: Harlan Stenn <[email-masked]>
Date: Thu, 31 Mar 2016 09:14:46 +0000

> somewhere. And when you have too many reponses saved, you need to drop

How is that significantly different from having lots of NTS connections
starting up at the same time?

Regardless, this is a pretty easy situation to address.  I'm not worried
about it at all.

> need. If the server doesn't save any state, there is nothing for the

Same as above.  This is something that's pretty easy to address.

> the server can handle, then some of them will be dropped.

Again, that's a local policy choice.  If you choose that approach and
the crypto work is "expensive" you've just traded one attack vector for
another.

H

---

From: Miroslav Lichvar <[email-masked]>
Date: Thu, 31 Mar 2016 11:45:21 +0200

> might use.  You only need to send enough traffic to keep the the rate 

Yes, that is a security issue in the implementation of rate limiting
in ntpd, which was published last year. You may have seen posts from
authors of the paper on this list :). The fix is to respond randomly
when the clients appear to be sending too many requests, so they can't
be starved from responses completely. At least one NTP implementation
already does that.

-- 
Miroslav Lichvar

---

From: Harlan Stenn <[email-masked]>
Date: Thu, 31 Mar 2016 10:23:03 +0000

> be starved from responses completely. At least one NTP implementation

We're now doing a number of different things along those lines.  There
are probably more things we could do, too.

H

---

From: [email-masked]
Date: Thu, 31 Mar 2016 13:58:35 +0200

> Adding fragmentation to the NTP protocol seems like a horrible idea.

To be honest, we had never assumed for IP fragmentation (on one request 
and one response) to be a huge problem.
If people see grave problems with it, we would welcome an elaboration as 
to why this is.

> With the client_cook message I suspect it would be much more

Just for the record: as per the current draft version, the messages in 
question (those which likely exceed MTU because they contain certificate 
chains are server_assoc and client_cook).
To clarify: does the reason you suspect that splitting client_cook is more 
difficult lie only in the stateless nature of the server and the fact that 
client_cook is a request, sent from client to server? Or am I missing 
something?

Kristof

---

From: Miroslav Lichvar <[email-masked]>
Date: Thu, 31 Mar 2016 14:59:08 +0200

> and one response) to be a huge problem.

One request and response could still be a problem. If the client is
not able to receive fragmented packets, it won't be able to initialize
the NTS association.

> If people see grave problems with it, we would welcome an elaboration as 

I'm not sure and I was hoping others would comment on that. It seems
to me problems with IPv4 fragmentation are quite common due to
firewalls dropping ICMP packets or IP fragments, and IPv6 doesn't seem
to recommend sending packets larger than 1500.

> client_cook is a request, sent from client to server?

Yes, precisely. The client keeps the NTS state, so in the worst case
the server could be authenticated in multiple steps, sending one
certificate at a time. But splitting the client_cook message at the
NTP or NTS layer would not be from the server point of view different
from fragmenting a single packet at IP layer.

-- 
Miroslav Lichvar

---

From: Sharon Goldberg <[email-masked]>
Date: Thu, 31 Mar 2016 09:22:40 -0400

> not able to receive fragmented packets, it won't be able to initialize
Right, to second that, there are middleboxes that block fragmented packets.

> > If people see grave problems with it, we would welcome an elaboration
> as  to why this is.
>

To add to that, fragmentation is commonly used as an attack vector.  I
would strongly discourage the use of IP fragmentation in what is supposed
to be a security protocol.  Please see these references for a small
sampling of examples.

https://www.nanog.org/sites/default/files/mon.general.fragmentation.bonica.pdf

http://www.hpl.hp.com/techreports/Compaq-DEC/WRL-87-3.pdf

http://arxiv.org/abs/1205.4011

https://media.blackhat.com/bh-eu-12/Atlasis/bh-eu-12-Atlasis-Attacking_IPv6-WP.pdf

http://www.iss.net/security_center/reference/vuln/TearDrop.htm

https://www.offensive-security.com/wifu/Fragmentation-Attack-in-Practice.pdf

Even if you don't see a SPECIFIC attack on NTS in these papers, my point
is that we can usually find a way to exploit IP fragmentation in unexpected
ways to break security. This has happened over and over in the last two
decades on many different protocols. In fact this is exactly what we did in
our recent NTP paper, Section VI:

.https://eprint.iacr.org/2015/1020.pdf

I would strongly object to having NTS rely on IP fragmentation.   This
would be a horrible design decision.

Thanks,
Sharon

---

From: Miroslav Lichvar <[email-masked]>
Date: Thu, 31 Mar 2016 17:39:21 +0200

> starting up at the same time?

I think the difference is that new NTS associations can't break
existing associations if the server doesn't keep any NTS state per
client. It's easy to control the number of requests that are processed
at the same time, but it's difficult to tell which associations are
still alive.

-- 
Miroslav Lichvar

---

From: Sharon Goldberg <[email-masked]>
Date: Thu, 31 Mar 2016 16:59:00 -0400

Thanks. For the record see the "priming the pump" attack in our paper:

https://eprint.iacr.org/2015/1020.pdf

On Thursday, March 31, 2016, Harlan Stenn <[email-masked]> wrote:

> [email-masked] <javascript:;>