Fighting the forces of clock skew when syncing password payloads

A good password manager should be able to securely store, sync, and even autofill your username and password when logging into websites and apps. A password manager like…Dropbox Passwords!

When we released Dropbox Passwords in the Summer of 2020, it was important we ensured that a user’s logins would always be available—and up to date—on any device they used. Luckily, Dropbox has some experience here, and we were able to leverage our existing syncing infrastructure to copy a user’s encrypted password info, known as a payload, from one device to another. However, while implementing this crucial component, we encountered an unexpected syncing issue where, sometimes, out-of-date login items would overwrite newer, more recent changes.

Eventually we found a solution that built on prior Dropbox syncing work. But it also involved contemplating the very nature of time itself.

The two-way merge

Dropbox Passwords uses zero-knowledge encryption. This means the private encryption key for a user’s passwords is only stored on their local devices, and the server is unable to decrypt them. While this is good for security purposes, it means we need to rely on the client to manage syncing and merging, and thus cannot rely on the server as a source of truth for recency as we typically would.

Initially, our sync algorithm used a two-way merge. If a user edited an existing login item—thus, modifying the client’s local payload—the client performed the following steps:

Update the local payload with the new details and current time.
Download the equivalent payload from the server.
Compare the timestamp of the local login item with the timestamp of the remote login item.
Use the newer login item as the winner.

Here’s a diagram illustrating what the flow might look like when a user updates their password from hunter1 to hunter2.

A successful merge and sync.

In theory, this worked nicely. Old items were replaced with their most recent versions. In practice, however, we noticed that some items were syncing incorrectly. One of our engineers discovered a phenomenon in which an older item would somehow trump a newer one.

After some thorough investigation, we found our culprit: clock skew.

Conflicting clocks

Let’s consider the following scenario. You are a happy Dropbox Passwords user with a computer and phone synced to the same account. You edit the notes field on one of your login items from your phone so that you can remember those pesky security questions. A few minutes later, you realize that you made a mistake when typing one of the questions—but your phone is all the way across the room. So you open up your computer to fix your mistake. After updating the notes field, you save the item, but something strange has happened. You are shocked to see your initial change—the one you made from your phone—has overwritten the newer change you just made on your laptop. How could this be?

Recall that the client is responsible for setting the timestamps on each item. We generally assume that our electronic devices have an accurate representation of the current time, but this is not always the case. It is actually possible for a device’s time to be out of sync with true time. This could be the result of a dead CMOS battery, an incorrect time zone setting, or perhaps even malware.

In our example, the phone’s login item trumps the computer’s login item because of this clock skew. If the computer’s clock is behind true time—by ten minutes, ten seconds, or even ten years—it’s possible that a more recent change will actually be marked as older. Here is a diagram illustrating what a failed sync might look like with offset clocks.

An example of a failed merge. Note that the timestamp on the newer change is older than the stable version.

The three-way merge

In order to tackle this problem, we borrowed the idea of a three-way merge from Git, the popular source control tool. Git uses a three-way merge when a user wants to merge two branches but there isn’t a linear path to merge from one branch to another branch. In these cases, there is a common ancestor of both branches, but no branch is an ancestor of the other. In a three-way merge, the common ancestor and the tips of both branches are used to generate a merged commit.

In fact, we already use the same idea in the Dropbox desktop client when syncing files between devices. Although this client has a more advanced version of conflict handling, the basic principle is the same. We realized a three-way merge might help us here, too.

In our case, the main problem with doing a two-way merge is that, because we can’t use the server as source of truth, we don’t have a revision history to keep track of which revision is earlier. As a result, we always rely on timestamps to determine which update is newer. In order to solve this problem, we introduced a third payload copy known as base. Now…

We have a local payload that represents what the user sees on their client.
We have a remote payload that represents what is stored on the Dropbox server.
We have a base payload that represents the most recently synced payload on that client.

Instead of a simple time comparison of local and remote, we can now generate a diff from local <> base and a diff from remote <> base. If there are any differences between base and the payload to which we are comparing it, we know that the most recent change must come from the non-base payload, since there is no way to edit base directly.

Once we obtain a list of local diffs and remote diffs, we can attempt to consolidate changes, with a goal of bringing the three payloads back in sync. There are two possible outcomes when comparing the diffs:

Entries in either diff but not both. This means that the diffs do not conflict with each other. Both changes can be safely applied.
Entries in both diffs. Changes in this category are considered conflicted, because both the local and remote payloads have updates to the same item. In this case, we will use their timestamp to resolve conflicts. The winner of the change will be the one that has a more recent timestamp.

A keen reader will point out that this merging process is still susceptible to clock skew—but under normal usage, this is unlikely to ever occur. A user would not only need two devices with out-of-sync clocks, but would have to edit the same item on both devices at the same time.

With the three-way merge in place, it was clear the addition of a base payload solved our merge issue. In a typical clock skew scenario, we no longer need to compare timestamps as there should be no conflicts during our merge.

A successful merge and sync with skewed clocks.

A solid foundation for the future

After a year in general availability, the three-way merge has proven to be a much more robust solution than what we had before. We were especially thankful for the extra stability as we added new features throughout 2021—including support for password sharing and payment card items. Our two-way merge issue could have been much more frustrating for users trying to modify a shared item, so we were happy to solidify our foundation before building atop it.

But why read about it when you can try it for yourself? Install Dropbox Passwords today and let your device finally experience the thrill of a three-way merge.

One more thing…

Do you value the security of your passwords and a silky-smooth syncing experience? Dropbox is hiring! Whether you have a passion for solving hard problems, or prefer the ritual of a routine bugfix, we’re always looking for curious new engineers. Dropbox would love to welcome you aboard! Visit our careers page to apply.