Temporum: secure time: a paranoid fantasy

[fanf]

Imagine that...

Secure NTP is an easy-to-use and universally deployed protocol extension...

The NTP pool is dedicated to providing accurate time from anyone to everyone, securely...

NIST, creators of some of the world's best clocks and keepers of official time for the USA, decide that the NTP pool is an excellent project which they would like to help. They donatate machines and install them around the world and dedicate them to providing time as part of the NTP pool. Their generous funding allows them to become a large and particularly well-connected proportion of the pool.

In fact NIST is a sock-puppet of the NSA. Their time servers are modified so that they are as truthful and as accurate as possible to everyone, except those who the US government decides they do not like.

The NSA has set up a system dedicated to replay attacks. They cause occasional minor outages and screwups in various cryptographic systems - certificate authorities, DNS registries - which seem to be brief and benign when they happen, but no-one notices that the bogus invalid certificates and DNS records all have validity periods covering a particular point in time.

Now the NSA can perform a targeted attack, in which they persuade the victim to reboot, perhaps out of desperation because nothing works and they don't understand denial-of-service attacks. The victim's machine reboots, and it tries to get the time from the NTP pool. The NIST sock-puppet servers all lie to it. The victim's machine believes the time is in the NSA replay attack window. It trustingly fetches some crucial "software update" from a specially-provisioned malware server, which both its DNSSEC and X.509 PKIs say is absolutely kosher. It becomes comprehensively pwned by the NSA.

How can we provide the time in a way that is secure against this attack?

(Previously, previously)

Comments

[dsrtao]

So the first plausible answer that occurs to me is a requirement for provenance and cross-checking. If all the major time-source consortiums provide reports on the quality of the others, then a discrepancy between them will indicate a problem, although you may not know who to trust.

This would need an implementation similar to the Perspectives project for cross-verifying SSL certificates. Perhaps cooperating time services would provide an any k-of-n proof of knowledge of a signature that they would publish at longer intervals.

[fanf]

But in my scenario the provenance and cross-checking says everything is fine! The NIST servers give the right time to their cross-checkers and will happily replay an old cross-check result to prove to a victim that they had the right time during the NSA replay window.

The crucial thing is proving that you are actually, right now, talking to multiple independent sources, that are not colluding to fool you.

[dsrtao]

Is everyone lying to you, or just a large percentage?

On trusting time

[ewen]

It would appear that in the full version of fanf's scenario, everyone who you ask has been brought into the fold of telling you The Truth As You Are Supposed To Know It (either by being "in on it", or by being told lies themselves which they believe). But yes, the usual verification method is to have multiple uncorrelated sources of the information you want to verify.

In this case it seems to me that the main two other mechanisms of defence one has (other than "ask multiple people") are time-specific:
1. Time is monotonically increasing: it doesn't flow backwards; if it seems to be, either you overcounted earlier, or someone is lying to you, or both -- all of those are exceptional situations where the paranoid could require, eg, manual intervention.

2. Time flows at a steady rate, which you can reasonably accurately follow over short periods by "dead reckoning" (eg, local oscillator); if the external view of time appears to be flowing significantly more unevenly than your local oscillator, you have a problem that needs manual intervention. (Which at least limits the attack to gradual slowing at whatever fudge factor you permit your local oscillator to be unstable by.)

If you don't have (a) a local source of starting time that you can at least vaguely trust, and (b) a local oscillator whose stability you trust over short periods within some margin you can live with being off by, then you are at the mercy of what the outside world is telling you -- if they are in cahoots to tell you lies, you will believe lies. (And yes, lots of embedded hardware is in exactly this position -- no local RTC, wildly unstable local oscillator, naively believing the outside world usually with no authentication.)

Ewen

PS: I strongly suspect that time is another of those things like (well deployed) crypto: the strongest thing in a weak system. So everything else is attacked instead. But maybe if there was a really juicy replay attack...

PPS: If your protocol/implementation can keep state ("we did this already") then you have another means to avoid replays beyond "you're saying this happened a while ago".

Re: On trusting time

[fanf]

Right. Thanks for the thoughtful comment!

This would hurt then

[cozminsky.livejournal.com]

There is a proposal from Nick Mathewson from tor to replace the timestamp with a random number because a wrongly set clock can be used to fingerprint people. http://www.ietf.org/mail-archive/web/perpass/current/msg00168.html

Getting a quorum of servers would be hard if this idea was widely deployed.

random time

[cozminsky.livejournal.com]

Nick Mathewson of the tor project was suggesting that the timestamp be removed from the TLS handshake as it can be used to fingerprint clients/servers which have the time set incorrectly. I saw some traffic about it on the TLS mailing list at the IETF. I might not matter for temporum since I think it's only for the client handshake.

Re: random time

[fanf]

Yes, Nick added code to tlsdate to get the time from the web server Date: header instead.

[pete stevens (from livejournal.com)]

In order for this to work the NSA would have to be supplying more than half the answers and unless they're considerably more than half it's going to look a bit suspect.

There's currently 4000 NTP pool servers distributed all around the world and it's nice and easy to add more. Even if you're slaving from a NIST server it doesn't matter because you're effectively proxying the victim from them.

So the defence would be not to allow NIST to have a substantial fraction of the pool, given the ease of which you can set up an ntp server that shouldn't be too hard.

I'd make it a requirement of secure DNS that the DNS server must also run a secure NTP server which ups the difficulty of the attack considerably - compromising every root server would be very hard.

[fanf]

Yes, I think you are right that that kind of scale provides a decent defence. The question is then how a pool client could get a trustworthy list of legitimate and diverse time servers.

[pete stevens (from livejournal.com)]

This is only a problem on first boot. NTP servers are long lived so you can set caching times to be weeks long and store the list of ntp servers over boot.

If you have no local storage at all then it gets a bit harder :-)

[bjh21.livejournal.com]

To an extent, ntpd's "panic threshold" provides a defence against this kind of attack, at least for systems that allow it to work. Such a system would only be willing to step the clock back a limited amount (by default 1000s), which means that the NSA has a somewhat limited replay window. It might be possible for the NSA to step the target's clock backward in stages, but this would be rather slow and could easily be defended against by a more paranoid sanity check in ntpd.

[fanf]

Yes, a battery-backed clock is an effective defence, if you have one and if it is set correctly. But I would like hardware to be able to boot securely without human assistance even if it is too cheap to have a clock or cannot be sure its clock is right.

Tiny systems

[houstonjames.livejournal.com]

One advantage there is that the attacker probably doesn't *know* you're a tiny system with no RTC: if they send their junk time to most machines, it will be noticed as inconsistent with either the local clock, or other NTP peers. To avoid detection, they'd need to keep the time delta within tolerance of any local RTC you might have, as well as be close enough to all the other NTP peers you may be using.

You could also use a GPS receiver, or a GSM modem to get the phone network's time data (or, more generally, for attack purposes you *could* be using that if you were suitably paranoid), so they'd have to modify that to ensure avoiding detection.

(As an amusing aside: after exile from 131.111 to another university much further north, I found one of the central NTP servers my department's machines used misbehaving and raised a support ticket with the central IT department. A few days later, the ticket got escalated back to me ... apparently, their servers thought they got their time feed from mine. Whoops. A rather wonky Cisco firewall was eating UDP packets between some central servers, meaning the most reliable path between two of their NTP servers was now via client machines in another building...)

[(Anonymous)]

Isn't this a bit like, 'What if you were kidnapped while you were asleep, and woke up in an exact replica of your house, in an exact replica of your city, populated by actors surgically altered to look exactly like your family, friends, neighbours and acquaintances?'

PS I'm not supposed to tell you but that actually happened to you, last Thursday night.