[ntpwg] Security for time bootstrapping and coarse-grained sanity-checking

[Bryan Ford <[e-mail]>]

Dear NTP folks,

I was just made aware last night at the welcome reception that some of my team's recent work might be of relevance to the "future steps for NTP security" topic that I understand this WG is starting to consider.  

In brief, we have developed an efficient, scalable collective digital signing protocol, in which many participants "witness" and contribute counter-signatures to an authoritative statement of some kind.  Clients can then check this collective signature quickly and nearly as efficiently as checking a single signature.  More details about this project and its current status may be found via these links:

- Draft paper: http://arxiv.org/abs/1503.08768 <http://arxiv.org/abs/1503.08768>
- Slides from a recent talk: http://dedis.cs.yale.edu/dissent/pres/151009-stanford-cothorities.pdf <http://dedis.cs.yale.edu/dissent/pres/151009-stanford-cothorities.pdf>
- Prototype implementation: https://github.com/DeDiS/cothority <https://github.com/DeDiS/cothority>

We've been most actively exploring this in the context of the PKI problem and in particular the Certificate Transparency (trans) WG effort - but another particular application of this we've long had in mind is a strong "collective time authority", and in fact a preliminary version of such a collective time service is already implemented and working in our prototype. 

Producing such collective signatures of course incur some latency: in our experiments, currently on the order of 2 seconds for 8000 co-signing witnesses.  Thus, collective timestamps are not going to provide high-precision time like NTP is intended to do.  Instead, they would serve a different, complementary role: namely to provide a highly secure "coarse-grained" notion of the current time, ensuring that adversaries (especially MITM-capable ones) cannot trick clients into thinking the current time is "way off" the reality (e.g., hours or days).

For starters, such a collective time protocol could address this "chicken-and-egg" problem documented in the current NTS draft:

10.2.  Initial Verification of the Server Certificates

   The client may wish to verify the validity of certificates during the
   initial association phase.  Since it generally has no reliable time
   during this initial communication phase, it is impossible to verify
   the period of validity of the certificates.  To solve this chicken-
   and-egg problem, the client has to rely on external means.

In essence, collective timestamping could solve this bootstrapping problem by allowing any client - on initial bootstrap or "once a day" for example - to send a random challenge or nonce to the collective time authority or any of its co-signing witnesses.  Once every few seconds, the collective time authority and its co-signing witnesses aggregate all recently submitted challenges into a scalable Merkle tree, which in this case never actually needs to be transmitted anywhere "in bulk" by anyone.  The time authority proposes and broadcasts a timestamped tree root, then all of its witness/cosigners sanity-check the timestamp while contributing their co-signatures.  Finally, each client gets the collectively signed root along with a Merkle inclusion proof demonstrating that the timestamp is "fresh" from that client's perspective, and the collective signature attests to the client that not just a single time authority but many independent participants have independently sanity-checked the signed timestamp.

In addition to the bootstrapping motivation, a second motivation is merely to protect clients against stronger time-related attacks - for example downgrade attacks against one or more NTP servers, or even MITM attacks against clients attempting using authenticated NTS connections with an NTP server whose private key has been secretly stolen or otherwise "acquired".  Some attacks of this type have been getting some news recently (e.g., http://arstechnica.com/security/2015/10/new-attacks-on-network-time-protocol-can-defeat-https-and-create-chaos/ <http://arstechnica.com/security/2015/10/new-attacks-on-network-time-protocol-can-defeat-https-and-create-chaos/>).  When clients are using their current notion of time to check whether a certificate has expired, we don't need the client's notion of the time to be millisecond-resolution but we want to be very certain it's not days or months off due to MITM attacks.  

Similarly, having a secure coarse-grained notion of the time may be important for software update protocols: e.g., if an attacker can convince a client (perhaps one that's been offline for a while or is even just "waking up" for the first time) that the current time is days or months behind the reality, then the attacker might be able to persuade the client via replay attacks to accept an old version of its OS or some other software package, which has a known vulnerability that the attacker would just love to exploit.

If there is interest and any time (so to speak) in the NTP meeting this afternoon, I would be happy to do a 5-to-10-minute summary if there is any time available and the WG chairs would deem that to be a suitable use of it.

Thanks
Bryan

_______________________________________________
ntpwg mailing list
[e-mail]
http://lists.ntp.org/listinfo/ntpwg