// 執筆：ジョン・カラビノス、トニー・シュウ、アンドリュー・ハノン、2022 年 5 月 17 日
目次
優れたパスワード マネージャーとは、ユーザー名とパスワードを安全に保管および同期するだけでなく、ウェブサイトやアプリにログインする際には認証情報を自動で入力できるツールのことです。たとえば、Dropbox Passwords がその好例です。
2020 年夏の Dropbox Passwords リリース時に重視したのは、どのデバイスを使っていてもログイン情報が必要なときにすぐに利用でき、さらに情報を最新に維持することでした。幸運なことに、Dropbox はこの分野ではある程度の実績がありました。既存の同期ストラクチャーを活用して、ユーザーの暗号化済みパスワード情報（これはペイロードとも呼ばれます）をあるデバイスから別のデバイスへと移すことができたのです。ただし、この重要なコンポーネントを実装するにあたって、同期の意外な問題が発生しました。それは、ログイン情報を変更したときに、古い情報が誤って新しい情報を上書きしてしまうケースがある、という問題でした。
最終的には、Dropbox の同期作業の前に構築できるソリューションが見つかりましたが、解決までの過程で、時間の性質について深く考える機会がありました。
1. 2 方向マージ
Dropbox Passwords はゼロ知識暗号化を使用しています。つまり、パスワードの暗号化に使う秘密鍵はユーザーのローカルデバイスのみに保存されていて、サーバーはパスワードの複合化をすることができません。このアプローチはセキュリティの観点からは適切ですが、同期やマージの管理をクライアント側に委ねる必要があります。通常はサーバー側に管理情報を集約してどの情報が最新かを判断していますが、今回はこの手法を使用できません。
当初、同期アルゴリズムでは 2 方向マージを採用していました。たとえば、ユーザーが既存のログイン情報を変更したとします。つまり、クライアントのローカルにあるペイロードが編集されます。すると、クライアント側では以下のことが実行されます。
- 新しい情報と現在の時刻を使って、ローカルにあるペイロードを更新する。
- サーバーから対応するペイロードをダウンロードする。
- ローカルのログイン情報のタイムスタンプを、リモートのログイン情報のタイムスタンプと比較する。
- 日時がより新しい情報を使用する。
ユーザーがパスワードを hunter1 から hunter2 に変更した場合は、次のダイアグラムのような処理が行われます。
理論上、このフローには問題がないように見えます。古い情報が最新のバージョンで置き換えられる仕組みです。しかし実際には、一部のケースで誤った同期が行われることがわかったのです。エンジニアチームの 1 人が、古いログイン情報がどういうわけか新しい情報を上書きしてしまう現象を確認しました。
徹底した調査の結果、理由を明らかにすることができました。原因は「クロック スキュー」です。
2. 時刻の競合
次のような状況を考えてみましょう。あなたは Dropbox Passwords のユーザーです。1 つのアカウントをスマートフォンとパソコンで使っています。ある時、スマートフォンを使ってあるログイン項目のメモ欄を編集しました。「秘密の質問」の答えを忘れないようにするためです。数分後、自分が書いたメモに間違いがあったことに気がつきます。ただし、スマートフォンが離れた場所にあったため、手元のパソコンを開いてメモ欄を修正しました。ログイン情報のメモ欄を変更して保存した後、奇妙なことが起こります。どういうわけか、スマートフォンで行った最初の変更が、時間的には後に行ったはずのパソコンでの変更を上書きしているのです。いったい何が起きたのでしょうか？
少し前にお話ししたように、タイムスタンプの設定はクライアント側で管理しています。私たちは通常、電子機器が示す現在時間は正確だと考えますが、時には例外もあるのです。デバイスの時刻がずれるということは実際に起こります。たとえば、CMOS バッテリーの消耗、タイムゾーンの設定ミス、場合によってはマルウェアの仕業でずれることもあります。
先ほどの例では、スマートフォンのログイン情報がパソコンのログイン情報を上書きしていました。これは、クロック スキュー、つまり時刻のずれによるものです。パソコンの時刻が遅れていた場合、実際には新しいはずの情報が「古い」と誤認されてしまうことがあります。時刻のずれは、数分から 10 分程度かもしれませんが、場合によっては 10 年単位でずれることもありえます。時刻がずれていた場合に起こる同期の失敗を次のダイアグラムで表しました。
3. 3 方向マージ
この問題を解決するため、定番のソース コード管理ツール Git で使われている 3 方向マージという考えを採用しました。ユーザーがマージしようとしているブランチ同士が直線的なパスで結ばれていない場合に、Git では 3 方向マージを行います。このようなケースでは、両方のブランチに共通する祖先がありますが、ブランチ同士は祖先と子孫という関係にはなっていません。3 方向マージでは、共通祖先と各ブランチの先端を使ってマージ コミットを作成します。
私たちはすでに、Dropbox のデスクトップ クライアントでも、デバイス間でファイルを同期する際に同じ手法を採用していました。このクライアントではより高度な競合処理をしていますが、基本的なところでは同じ考え方です。私たちは、ログイン情報の更新と同期でも、3 方向マージが有効ではないかと考えたのです。
2 方向マージでの大きな問題は、サーバーの情報を頼りにできないという点です。どのバージョンが新しいのかを管理できるバージョン管理が存在しないからです。そのため、どの更新情報が新しいのかを判断するためには、タイムスタンプを頼りにするほかありませんでした。この問題を解決するために、3 つ目のペイロード コピーを使うことにしました。これは、ベースと呼ばれます。新たな構成は以下のとおりです。
- ローカルのペイロード：ユーザーがクライアント上で目にする情報
- リモートのペイロード：Dropbox サーバーに保存されている情報
- ベースのペイロード：そのクライアントで最後に同期されたペイロード
ローカルとリモートのタイムスタンプを単純に比較するのではなく、ローカルとベース、そしてリモートとベースのそれぞれの差分を生成することにしました。ベースと比較対象ペイロードの間に差分があった場合、ベース ペイロードが直接編集されることはないため、最も新しい変更はベースではないペイロードで発生したと考えられます。
ローカルの差分とリモートの差分を取得できたら、次は 3 つのペイロードを同期できるよう変更点の結合を試みます。これらの差分を比較して得られる結果には、2 種類あります。
- 両方ではなく、片方のみの差分に存在するエントリー：この場合、差分は競合していません。どちらの変更点も問題なく適用できます。
- 両方の差分に存在するエントリー：この種の変更は、「競合」とみなされます。ローカルとリモートにあるペイロードで、同じ項目に変更を加えているからです。この場合、両者のタイムスタンプを比較して競合を解決します。より新しいタイムスタンプのある変更が採用されます。
ここまで読んでくださった皆さんは、問題点に気づくかもしれません。このマージプロセスにしても、まだクロックスキューが入り込む余地があります。ただし、一般的な使用においてはそうした事態は起こらないはずです。時刻がずれた 2 台のデバイスを使っているだけでなく、その 2 台を使って同時に同じ項目を編集するというのは考えにくいでしょう。
3 方向マージの ベース ペイロードを導入したことで、今回のマージ問題を解決することができました。クロック スキューが起こる一般的なシナリオでは、マージの際に競合が発生しないはずなので、タイムスタンプを比較する必要がなくなりました。
4. 今後を見据えた盤石な基盤
一般公開となってから 1 年が経ちましたが、3 方向マージは 2 方向に比べてより強力なソリューションであるという実績を誇っています。2021 年にパスワード共有や支払カード項目といった新機能を追加できたのも、この卓越した安定性のおかげです。複数のデバイスでパスワードを共有しているユーザーにとって、2 方向マージが引き起こしていた問題はとても厄介でした。それだけに、盤石な基盤を確立できたことを大変嬉しく思っています。
ここまで読んでくださった皆さん、次は実際に使ってみませんか？
Dropbox Passwords をインストールして、3 方向マージの魅力をぜひ体験してみてください。
