Subject: [openpgp] Dealing with clock skew

From: "Neal H. Walfield" <[email-masked]>
Date: Fri, 15 Nov 2019 12:17:49 +0100

Hi,

Our OpenPGP library is being used in an application that does a
real-time exchange.  Specifically, two MUAs sometimes communicate via
an imap folder.  During testing, the application developers observed
that the message exchange would sometimes fail, because a signature
was considered invalid.

Eventually, we figured out that the problem was due to clock skew: the
sender would sign a message at, say, 9:00 and the receiver would
correctly reject it because its clock said that the current time was
8:59, and 9:00, the time stored in the message's Signature Creation
Time subpacket, is clearly in the future.

It turns out that a second of clock skew is actually pretty good.  The
testing was done on a VM and the application developer reported that
up to 20 minutes of clock skew are not unusual.

Adding a tolerance seems like a reasonable way to deal with this
problem.  But, there are situations where a tolerance would cause
other problems.  Consider, for instance, an application that generates
messages that contain its current state, and we want to know its state
at some point in time.  Specifically, consider messages, Ma and Mb,
and a time T.  If Ta < T < Tb (< current time), then we should use Ma.
But, if T is significantly close to Tb, we may not reject Mb and use
it instead!

An obvious example of this type of message is self signatures.  It is
tempting to just not use tolerances with self-signatures, but if an
application generates a key, and immediately sends it to another
computer, the second computer may reject the key as being invalid,
because it doesn't consider it to have any valid self-signatures!  So,
some tolerance is also needed for self signatures.  Also, the example
also applies to normal ("user data") messages, so specially handling
self-signatures is not the right approach, anyway.

Perhaps the best thing to do is to only use a tolerance when asking if
a signature is valid "now".

How do other implementations deal with this?  Thoughts?

Thanks!

:) Neal

---

From: "Derek Atkins" <[email-masked]>
Date: Fri, 15 Nov 2019 06:38:06 -0500

Hi Neal,

There is plenty of prior art on dealing with time skew.  Kerberos, for
example, has been dealing with it since the 1980s!  In short, you have a
sliding window of acceptance.  Kerberos sets this as +/- 5 minutes.  So if
the timestamp is within that 10-minute range it is considered current
(valid).

If you are seeing 20-minute clock skew on a VM, then you should really set
up ntp.

As for your second issue, my questions to you are:
1) are the messages are guaranteed to be in order (or could they be
reordered).
2) can the validator maintain per-sender state?

If YES to both questions, then the easiest thing to do is maintain the
last timestamp sent and reject if the next message has a timestamp prior
to the last one seen.  Note that this state must be per-sender, so if you
have Alice talking to Bob and Charlie, Alice needs to maintain separate
last-seen numbers for both Bob and Charlie, because their clocks can be
skewed differently.

Hope this helps,

-derek

On Fri, November 15, 2019 6:17 am, Neal H. Walfield wrote:
> _______________________________________________
> openpgp mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/openpgp
>

-- 
       Derek Atkins                 617-623-3745
       [email-masked]             www.ihtfp.com
       Computer and Internet Security Consultant

---

From: Bill Frantz <[email-masked]>
Date: Sat, 16 Nov 2019 09:01:27 -0500

>If you are seeing 20-minute clock skew on a VM, then you should really set

Amateur radio operators have a significant time skew problem 
when using certain digital modes (Key words: FT8, FT4, wsjt-x, 
and wsjt). To successfully complete a decode, the sender and 
receiver's clocks must be within 1/2 to 1 second of each other.

For the majority of operators, NTP is "good enough". Some 
operations, particularly those in locations without Internet 
access, use atomic clocks or GPS time.

Cheers - Bill

-----------------------------------------------------------------------
Bill Frantz        |Security, like correctness, is| Periwinkle
(408)356-8506      |not an add-on feature. - Attr-| 16345 
Englewood Ave
www.pwpconsult.com |ibuted to Andrew Tanenbaum    | Los Gatos, 
CA 95032

---

From: Claudio Luck <[email-masked]>
Date: Sat, 16 Nov 2019 18:40:16 +0100

> How do other implementations deal with this?  Thoughts?

If we live in an asynchronous messaging world with no global time
concept, then the sender is free to hand out back-dated signatures. The
receiver can't tell the difference between in-transit delay and
back-dating. This can be used on purpose by the sender to induce some
tolerance at the receiver side.

Cheers
Claudio

---

From: Jon Callas <[email-masked]>
Date: Sat, 16 Nov 2019 15:06:13 -0800

> On Nov 16, 2019, at 9:40 AM, Claudio Luck <[email-masked]> wrote:
> 

We do live in that world; it's not an if.

Newton argued for a notion of absolute time, but also conceded Galileo's point that you can switch frames of reference and have a conversion between them. Leibniz, on the other hand, argued that space is meaningless except as relative distance and that time *only* makes sense as an expression of relative motion. Ernst Mach also had a number of pithy things to say about this, particularly that even if you have absolute space or time, all math and physics works if you declare that you're still and the universe is moving or ticking.

I'm especially fond of Poincaré's "The Measure of Time" as he hits not only on the physical aspects but the experiential ones as well (English translation here: <https://en.wikisource.org/wiki/The_Measure_of_Time>). Of course, Einstein tied a bow around all of this in his Special Relativity which flat out declares what Leibniz gestures toward, that space and time are linked and there is no preferred frame of reference.

Of course, I can do the same thing towards Einstein that Leibniz and Mach did and note that if there's no preferred position or clock, I can just declare one and everything works fine. Operationally, this is what we do with GPS/atomic/NTP time. We declare that to be our frame of reference.

However, even that breaks down for surprisingly short distances. Network delays and the consequent "lag" means that you can't establish primacy on most multiplayer games in a lot of circumstances. This is why lots of them try to avoid situations where jumping around corners etc. are easy to cheat at. This is exactly the same problem you're talking about. There are a lot of interesting papers, but here's one that is precisely trying to create an absolute frame of reference, "Lag Compensation for First-Person Shooter Games in Cloud Gaming" <https://link.springer.com/chapter/10.1007/978-3-319-90415-3_5>. Note that they're not doing any mathematical security (like signatures) here, this is all trusting the network. They have this problem because it is inherent to any system that has space and time involved with it.

In the general case, you can't consider a time measurement to be a scalar, it has to be at the very least a complex number of the form [time, skew]. As Derek noted, Kerberos used a skew of five minutes. While Neal Walfield noted in his original post that he's seen skew of 20min, I concur that that seems a bit long. My naive home set-up commonly has alarms across devices being ±2s or less, but that's because they're all getting time from some combination of NTP and cellular network time, which is ultimately GPS time (and of course, skew). I think five minutes is likely reasonable, but *some* skew is unavoidable. Moreover, anyone who's on satellite networks is seeing latency of over a second and once you throw in normal exponential backoff, five minutes seems about as short as is reasonable.

Thus, you're absolutely right, if time is a scalar, then someone can cheat. There are situations (like real-time internet games) where the exact problem you mention, that someone can hide cheating in the skew is a well-known, unsolvable problem.

	Jon

---

From: Benjamin Kaduk <[email-masked]>
Date: Mon, 18 Nov 2019 01:50:01 -0800

> In the general case, you can't consider a time measurement to be a scalar, it has to be at the very least a complex number of the form [time, skew]. As Derek noted, Kerberos used a skew of five min…

I believe that if Kerberos was starting over now, the 5 minutes would be
seen as excessively long, FWIW.

-Ben