[cryptography] Authenticated Time Synchronization

Peter Todd pete at petertodd.org
Mon Sep 16 01:06:57 EDT 2013

On Tue, Sep 03, 2013 at 11:06:56AM +0200, Stephen Röttger wrote:

Sorry, for the late reply, I was out of town.

> > Specifically a client can generate a unique 128-bit nonce and have the trusted server timestamp it by signing a message including the nonce and the current time T. If the time between the request and the reply was dt, the actual time must be in the range (T, dt)
> > 
> > We can then extend this to an arbitrary number of clients with a merkle tree and one or more levels of untrusted servers. The servers combine all the nonces they receive in some time interval t into a merkle tree, then timestamp the digest of the tip of that tree. The clients then receive the merkle paths from the server, a proof of log2(n) size.
> I'm not sure if I understand you correctly. Do you mean that a time
> server will store the nonces of all requests from different clients in a
> given period and afterwards publish a merkle tree of these requests with
> a signed root node? I think this approach would have roughly the same
> computing overhead as our approach: one asymmetric signature per time
> period vs. one asymmetric signature per client and then ~2 hashes per
> time request vs. 3 in our approach.
> > If a client doesn't trust the server at all, they know the time is within (T, dt); if they are willing to place some trust in the server the server can measure the interval between when they got the request and sent the proof, dt', and the client can take that into account for a more precise time. 
> If the server is not trusted, what prevents him from lying to the client
> and just forging some merkle tree in this case?

The idea is to allow multiple untrusted servers to assist a single (or
small number) of trusted servers so that the trusted servers don't have
to have the capacity to handle every client. The total computational
overhead isn't much different; the advantage is that the load can be met
by untrusted servers yet still give trustworthy times.

An example of this system could be for NIST to run a single trusted time
server that cryptographically signs time requests. Now Debian wants to
make it possible for Debian Linux installations to use trusted,
authenticated, NTP out of the box, but they themselves don't have the
resources to operate trusted servers with secure hardware and dedicated
administration. However they can procure plenty of untrusted server
capacity via cheap VPS hosting, and NIST is willing to let them connect
to the NIST trusted time server provided the Debian project doesn't make
more than, say, 100 requests a second.

Now, for all of the above, you can also think in terms of NIST operating
a *timestamping* service. Now what Debian is doing with their untrusted
servers is extending that one trusted timestamping service's capacity
with merkle trees - rather than timestamp the message directly,
timestamp n messages hashed into a merkle tree, and prove the timestamps
are real with the merkle paths to the trusted signature.

My observation, is that if you can get a nonce timestamped by an honest
timestamper the time on the timestamp must be the current time, modulo
easily measurable network delays. Is all this as accurate as traditional
NTP? No, but it's close enough for a lot of applications and it scales
really well.

Does that all make sense?

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 490 bytes
Desc: Digital signature
URL: <http://lists.randombit.net/pipermail/cryptography/attachments/20130916/2b8bbb9c/attachment-0001.asc>

More information about the cryptography mailing list