googleの新しい時刻同期プロトコル Roughtimeとは

[追記] 2020年1月時点の動向について、新しく記事を書きました
asnokaze.hatenablog.com


Googleの「Adam Langley氏のブログ」で、新しい時刻同期プロトコルについて紹介されている。このRoughtimeは特定のタイムサーバに依存しないセキュアな方法で時刻同期を行うことを目的としたプロトコルです。すでに、googleのサーバで動作しており、roughtime.sandbox.google.com:2002に向けて公開されている専用クライアントで接続できる。


現在のセキュリティは現在の時刻に依存しており、その重要性はましています。証明書の有効期限や、OCSPレスポンス、Kerberosのチケット、DNSSECの応用やPGP鍵といった機能でも重要です。しかし、Chromeの証明書エラーのうち25%はローカルの時刻に起因するとしているとしています。


現在、最も使用されているNTPプロトコルの認証機能はほとんど使用されていないとし、MITM攻撃で時刻を操作することが出きる旨記述している。


この問題に対して、それらを改善することを目的に新しい時刻同期プロトコルroughtimeを提案している。

roughtimeの特徴

  • UDPプロトコル
    • 増幅攻撃を防ぐため、リクエストメッセージは1kバイトになるようにパディングされる
  • 現段階では正確な時刻同期を目標としておらず、10秒以下であれば満足とする
  • 認証されているタイムサーバでも複数のタイムサーバを用いて正しくない振る舞いをするタイムサーバを検出する
  • 公開鍵方式で署名される
    • Ed25519のみをサポートしてる
    • サーバのレスポンスは、クライアントが生成して提出したノンスと時刻について署名して応答される
    • long-term identity key から委譲されるonline public keyを使用する
    • 複数のリクエストに対してバッチ的に署名する (Merkle treeのルートに対して署名する)
    • レスポンスに含まれるMerkle treeは、実際には対象のノンスから、ルーに到達するのに必要なノードとindex(left or rigth)が与えられる(木のリーフは1~64)
    • Skylakeチップで1コアで1秒あたり430万リクエストを署名できると見積もっている
  • うるう秒を24時間に分割して時刻に反映する

roughtimeプロトコル概要

クライアントは乱数を生成し、それをnonceとしてRoughtime リクエストをサーバに送信します(1024バイトまでパディングされる)。サーバはそのノンスと時刻に対する署名、サーバ証明書などをroughtimeレスポンスとして返します。


この時、クライアントが生成したノンスに対して署名されて返ってくるため、その時生成されたことが保証されます。


つまり、サーバAに問い合わせて結果を得たあとに,サーバBに問い合わせた場合。サーバAから得られた時刻 より、サーバBから得られた時刻のほうが新しいはずということがわかります。この時サーバBに問い合わせるときに、サーバAからの応答をハッシュしてノンスとして使えば、その順序も確実であるといえます。それぞれから得られた時刻で矛盾があればなにかおかしいことに気づくことができます。


この手続を6つ以上の独立したサーバで行えば不正なサーバを検出でき、正しい時刻を定めるのに十分正確だとしています。

roughtimeメッセージ

Roughtime メッセージ(リクエスト or レスポンス)は、タグの数を示すヘッダと、複数のタグと値のペアからなります。タグ名は32bit値であり、ドキュメント中では文字として"NONC "や"CERT"と記述されます。3文字の場合は4文字目だけ16進数で明示的に記述されます("SIG\x00")。タグはそれぞれ値をもちます。

roughtime リクエス

Roughtime リクエストは、NONCタグを持つメッセージです。NONC の値は64バイト値です。それ以外のタグは無視されます。増幅攻撃を防ぐためにPAD\xffタグを用いて1024バイト以上にする必要があります。

Roughtimeレスポンス

レスポンスは以下のタグで構成されます

  • SREP: 署名されるメッセージ。Merkle treeの根と、時刻を示す2つのタグMIDP,RADIを含みます
  • SIG\x00: SREPの署名値である64バイト値。Ed25519 のみが署名アルゴリズムとしてサポートされており。
  • CERT:サーバの証明書。署名に使用するonline public keyと有効期間と、この鍵に対する署名。
  • INDXPATH: 複数のクライアントのリクエストに含まれるノンスはMerkle treeの葉となる。複数のリクエストに対して署名を行うため、Merkle treeのルートのみに署名を行う。このMerkle treeをルートまでたどるのに必要な経路PATH(ノードのリスト)と、たどる際のノードが左右のどちらのノードなのかを示すINDX
Roughtime UTC

タイムスタンプはMIDPRADIの2つのタグで表現されます。MIDPタグはマイクロ秒で時刻範囲の中心点をunit64として持ちます。一方RADI タグは時刻範囲の半径をマイクロ秒でuint32で表現します。


Roughtime の"正しい時刻"は、24時間でうるう秒をならしたUTCです。1日かけて均等に反映されていきます。

実装

C++ と Goの実装が公開されている。 C++はbazelを導入し、ビルドする必要があるが、Goは比較的すぐに動作確認することができる。

vagrant@vagrant:~/go/gopath/src$ git clone https://roughtime.googlesource.com/roughtime roughtime.googlesource.com

vagrant@vagrant:~/go/gopath/src/roughtime.googlesource.com/go/client$ go build

vagrant@vagrant:~/go/gopath/src/roughtime.googlesource.com/go/client$ ./client --servers-file=../../roughtime-servers.json --chain-file=$HOME/roughtime-chain.json
Quorum set to 1 servers because not enough valid servers were found to meet the default (3)!
real-time delta: -16.306032ms


roughtime-servers.jsonGoogleのサーバとその公開鍵が指定されており時刻の誤差が表示される、一つしかないのでサーバの検証は実施されない。


20/10/11 表現を少々修正しました
前) 正確な時刻同期を目標としておらず、10秒程度の誤差は許容する
後) 現段階では正確な時刻同期を目標としておらず、10秒以下であれば満足とする