20151108 - The Authenticated Time issue

If you have been following NTP recently, you know that a paper came out with a study of attacks on the NTP protocol.

It’s a good paper, hat-tip to the authors, but there really isn’t anything new in it, they’ve merely published what we all knew to be the case and coupled it with a UDP reassembly bug in some subset of current kernels.

The fundamental problem is that timing packets and doing crypto operations on their content are incompatible activities.

The seriously compunding problem is key-distribution for a stateless protocol where servers have thousands or even millions of clients.

Attempts have been made, it didn’t work. New attempts are being made, and I’m pretty sure they won’t work either.

Both Autokey and NTS could work, but I seriously don’t think people will take the effort: Crypto is both hard and boring.

But I may have found a solution.

Time from HTTPS servers

First, credit where credit is due:

The first inspiration is Jacob Appelbaums tlsdate which will set your clock by pulling the timestamp out of SSL/TLS handshake packets.

I’m calm and somewhat comfortable with somebody like Jacob Appelbaum grubbing around inside the SSL/TLS protocol, but I’d rather not have to do it myself.

The major problem is that these timestamps are whole-second granularity, and by the time you add cryptooverhead and packet travel time, you are into the plus/minus two or three second territory, which by most standards is unacceptable.

But add the other inspiration, from Judah Levine, and the situation improves a fair bit:

Judah has pointed out that computer clocks these days are relatively stable, by which he (and I) mean that they don’t change frequency a lot and they don’t do so abrubtly.

In other words: The current NTPD is far to eager to yank clocks around.

Putting these two things together, not particularly precise but highly trustable timestamps and relatively stable clocks, we have a defense against network attacks on the NTP protocol.

Getting time from a HTTPS server

We open a SSL/TLS connection to a HTTPS server, and we send it a request:

HEAD / HTTP/1.1
Host: <his_address>

We’ll get some kind of HTTP response back, and HTTP responses are supposed to contain a “Date:” header, which gives us a full second granulatiry timestamp.

But we can do better than that.

Imagine we do it, and the HTTPS server tells us the date is ‘4s’.

That tells us, that the time was [4s…5s[ on the server, sometime between our transmission and our reception:

4s                  5s                  6s                  7s
|...................|...................|...................|............

   TX----------RX(4s)
...======================4s=========]
    [===========5s======================================]
    #################################

From this we can deduce that second ‘4s’ will end no later than a second from our local RX timestamp, and that the next second ‘5s’ can start no earlier than our local TX timestamp, and end no later than one second after the possible 4s second.

Somewhere in the timeinterval (###) between our TX timestamp and at most a second after our RX timestamp, the second must change on the server.

The uncertainty is exactly (1 second + Round-trip-time) which is not very useful, but since the HTTPs connection is still open we can ask it again during the next second, and this time we aim for the middle of the uncertainty interval.

Lets imagine the server tells us ‘5s’ this time:

4s                  5s                  6s                  7s
|...................|...................|...................|............

   TX----------RX(4s)
...======================4s=========]
    [===========5s======================================]
    #################################

    Moved 1sec later:    #################################
                                  TX-------RX(5s)
                                  =================5s===========]
                                   [========6s===========================
                                   #######################

From that we learn the earliest possible start for the ‘6s’ second is our TX timestamp, and that chops the front 1/3 of our uncertainty interval.

We can continue during the next seconds and do a binary search until the uncertainty assymptotically approaches the RTT.

If we dare look into how the RTT is spent, like we do for NTP packets, we can narrow it down further, but so far my experiments indicate no reliable and significant improvement.

To get down to the 128msec NTP max offset, we generally have to prod the HTTPS server 4-5 times.

Can we actually use this ?

For this to be useful, four condiitions must be fulfilled.

HTTPS servers with good timekeeping must exist

I don’t think this is really in doubt, but just in case I’m running a little survey where I attept to get time this way from random IP numbers. I’ll report back on that.

HTTPS servers with trustworth timekeeping must be used

This is an entirely different kettle of fish, and like all issues of trust, it will be a judgement call for the user.

People running HTTPS servers don’t get upset

A “HEAD /” is likely the least invasive request we can possibly send, and if we send three to five of them on a single connection, spaced over a couple of seconds at most once every hour, the incremental load from one client is very, very small, but not zero.

In my considered judgement, we’ll be fine, but some kind of protocol needs to be implemented, so servers can avoid being punked.

The timestamps must have value

These relatively imprecise, but trustable timestamps need to be useful for us from a timekeeping point of view.

This should not be a problem, given the triangular probability densities we use in Ntimed-client, and Judahs point about clocks being pretty stable to begin with.

We may not be able to hold tight to NTP’s ±128 msec offset limit, the RTT gets in the way, but for most purposes, even ± 1 second would be fine.

But you said you hate OpenSSL, right ?

Don’t even get me started.

I’m actually going to make this more general than the above, so that I can avoid linking OpenSSL or any other SSL/TLS library into Ntimed.

What I’ll do is popen(“someprogram”) which returns a range inside which the time difference between this machine and some other time-source lies.

One of the possible programs to run is one which implements the above trick, but the general scheme is more broadly applicable.

For instance you could ssh to a remote server and run date(1) doing the exact same binary search as above. The obvious improvement is to use a program which tells us also the fractional second on the remote system.

But either way, yes, I hate OpenSSL and ntimed-client won’t be linked against it.

For the ‘someprogram’ I’ll probably even popen(“openssl …” to avoid OpenSSL for that too.

More later…

phk

PS: If you see “HEAD /” requests from this server in your web-server logs, that’s just me checking your clock.