Kagi検索のためのPrivacy Pass認証

 (blog.kagi.com)
2 ポイント 投稿者 GN⁺ 2025-02-14 | 1件のコメント | WhatsAppで共有
  • Kagi Searchは、有料の検索権限を確認しつつも検索リクエストをアカウントと直接結び付けないようにするため、Privacy Pass認証を導入した
  • この方式はトークン生成とトークン使用を分離し、Kagiが有効性は検証できても、トークンだけからユーザーや生成時点を逆追跡できないようにする
  • 初期対象は無制限検索が含まれるProfessional、Ultimate、Family、Teamプランで、検索量制限のあるTrialとStarterはトークン紛失・超過利用の問題が残るため対象外
  • Orion、Kagi Androidアプリ、Chrome・Firefox拡張でそのまま利用できるが、Safariは拡張APIの制約によりまだ未対応
  • トークンだけでは検索とアカウントを結び付けにくい一方、IPアドレス・ブラウザーフィンガープリント・反復検索パターンのようなサイドチャネルは残るため、TorやVPNの利用が推奨される

Kagi Searchに追加されたPrivacy Pass認証

  • KagiはKagi SearchにPrivacy Pass認証を導入するとともに、Tor onion serviceも公開した
  • Privacy Passは、クライアントがアクセス権を証明しつつ、サーバーがどのユーザーが接続したかを識別できないようにする認証プロトコル
  • 有料検索エンジンであるKagiは検索権限の確認が必要だが、この機能によって検索リクエストを特定アカウントと結び付けない技術的保証が追加される
  • 実装はRaphael RobertのRust Privacy Pass実装を出発点とし、コードはkagisearch/privacypass-extensionで公開されている

対応プランとクライアント

  • Privacy Passはまず、無制限検索プランであるProfessional、Ultimate、Family、Teamのユーザーに提供される
  • TrialとStarterプランは現在サポートされていない
    • この2プランは月間検索回数が制限されている
    • 拡張機能の削除などで生成済みトークンを失うと、ユーザー体験が悪化するおそれがある
    • Kagiはトークン使用時点ではアカウントやプランを把握できないため、理論上は許可検索数を超えるトークン利用が可能になりうる
  • 対応クライアントは以下の通り
  • 既存のKagi Search拡張を使っているユーザーは、互換性問題を避けるため最新バージョンへ更新するか無効化する必要がある
    • Firefoxは0.7.6
    • Chromeは1.2.2.5

Privacy Passの認証フロー

  • Privacy Passは認証をトークン生成とトークン使用の2段階に分ける
  • トークン生成段階では、ユーザーがKagiのセッションクッキーでトークン生成権限を証明する
    • 生成されたトークンは、サーバー視点ではランダムなトークンと区別できない
    • トークンは生成したユーザーや、同一ユーザーが作成した他のトークンへ追跡できない
  • 検索リクエスト時には、事前に作成したトークン1つを提出してアクセス権を証明する
    • サーバーは、そのトークンが有効に生成されたことがあるという事実だけを確認する
    • トークンを特定の生成段階に結び付けることはできない
  • トークンは使い切り
    • サーバーは既使用トークンを追跡して重複使用を防ぐ
    • クライアント側も同じトークンを2回送信してはならず、そうしないことで異なる使用段階の結び付きも防げる
  • トークンには固定の有効期間があり、古すぎるトークンは新たに生成する必要がある

Kagiの実装モデルとセキュリティ特性

  • Kagiの配備モデルは、Privacy Pass標準のShared Origin, Attester, Issuer構成に従う
    • KagiがAttester、Issuer、Originの役割をすべて担う
    • ユーザーはPrivacy Passブラウザー拡張またはOrionの標準対応を通じてクライアント役を担う
  • 拡張機能はインストール後およびその後も定期的に大量のトークンを生成して保存する
  • ユーザーは検索時に、既存のセッションクッキーで認証するか、Privacy Passトークンで認証するかをトグルで選べる
  • ユーザー保護の特性は3つある
    • 生成-使用の非連結性: Kagiは検索時に提出されたトークンを特定のトークン生成段階に結び付けられない
    • 使用-使用の非連結性: Kagiは異なる2つの検索が同じユーザーによるものかを、トークンだけでは判断できない
    • 使用時の奪取防止: トークン生成過程を観測した盗聴者が、その情報だけでトークンを盗んで使うことはできない
  • Kagiを保護する特性も含まれる
    • 正常に生成されたトークンはKagiの検証を通過する
    • 悪意あるクライアントは、正しく生成されたトークンを知っていても新たな有効トークンを偽造できない

Privacy Passモードで減る機能

  • Privacy PassモードではKagiがユーザーを識別できないため、アカウント設定を適用できない
  • Kagiはこれを「一般的なプライバシーと完全な機能」または「最大限のプライバシーと中核機能」のどちらかをユーザーが選ぶ構成として提供する
  • Kagi Assistantはリリース時点ではPrivacy Passで利用できない
    • Kagi AssistantはUltimateメンバーのみが利用可能
    • Privacy Passではアカウント情報がないため、どのプランか検証できない
  • リリース時点のPrivacy PassはKagi Search認証にのみ使われる
  • Kagiは今後数週間以内に、以下のサービスへ対応を拡大する計画
    • Kagi Assistant
    • Kagi TranslateとKagi Maps
    • Kagi Universal SummarizerとAsk questions about page
  • 現時点でこれらのサービスを使うにはPrivacy Passを無効化する必要がある

サイドチャネルとTor利用

  • Privacy Passはトークンだけではトークン生成と使用を結び付けられなくするが、オンライン相互作用全体を数学モデルで完全に説明できるわけではない
  • 悪意あるサーバーはサイドチャネル情報でクライアント追跡を試みる可能性がある
    • 毎日同じ時刻に同じ具体的な検索を繰り返せば、それらの検索が同一人物によるものと推定されうる
    • ブラウザーのuser-agentやIPアドレスといったシグナルはPrivacy Passの外側にある情報
    • 同じIPからトークン生成リクエスト直後にトークン使用リクエストが来れば、同一人物の要求と見なされる可能性がある
  • RFC 9576は、トークン生成と使用を時間的に分離するか、Torのような匿名化サービスで空間的に分離することを推奨している
  • KagiのPrivacy Pass拡張とOrionの標準実装は、HTTPヘッダーとクッキーを除去してブラウザーフィンガープリントを可能な限り均一化するよう処理する
  • KagiはTorネットワークから直接アクセスできるonionアドレスを提供している
  • Torだけを使えばIPアドレスは隠せるが、Privacy Passなしでログイン状態のままだと、検索は理論上単一アカウントに結び付けられうる
  • TorとPrivacy Passを併用すると、Kagiが分かるのは、その検索が以前にトークン受領権限の検証を受けたユーザーから来たという点だけで、アカウントや位置情報は分からない

トークン数、性能、保存容量

  • 無制限検索プランのユーザーは、1つのepoch、つまり1か月あたり2,000個のトークンを生成できる
  • 追加トークンが必要な場合はsupport@kagi.comに依頼できる
  • 500個の検索トークン生成には、一般的な消費者向けノートPCで約1秒の計算が必要
    • サーバー接続と応答時間のため、さらに数秒かかる場合がある
    • 拡張機能のインストール時には可能な限りバックグラウンドで実行される
  • トークン1個は216バイトで、トークン生成リクエストごとの保存容量は約100KiB
  • 現在、トークン検証サーバーはus-central1リージョンにのみ配備されており、Kagiはリリース直後に拡張する計画

パーソナライズと設定が制限される理由

  • Privacy Pass検索ではKagiがユーザーを把握できないため、ユーザーのカスタム設定に合わせた結果を提供できない
  • Kagiは、リクエストごとに(language, region, safe-search)のような小さな設定を送る案を検討したが、現時点では匿名性を大きく下げると判断している
  • 例示分析では、特定の言語設定であるLang 10を送るユーザーは、Privacy Passユーザーが約1,000人いる場合、使用-使用の非連結性保証を自動的に失う可能性がある
  • Kagiはこの推定が過度に保守的かもしれないと見ているが、現時点ではPrivacy Pass認証ユーザーに対し基本的なパーソナライズ水準も有効にしていない
  • 手動の検索設定は、検索語にbangsを付けることで一部適用できる
    • たとえば検索語の先頭に!deを付けると、ドイツ地域の検索を実行する
  • 完全にパーソナライズされた検索体験を望むなら、従来のログイン方式を使い、Privacy Passを無効化する必要がある

Safari・プライベートブラウズなどの制約

  • Privacy Passはブロックチェーンを使用しない
    • 楕円曲線、ハッシュ関数、検証可能な忘却疑似乱数関数の構造を利用する
    • トークンはブロックチェーン上で生成・保存・取引されない
  • Chrome・Firefoxのプライベートブラウズではトークン生成が動作しない
    • トークン生成にはセッションクッキーへのアクセスが必要
    • プライベートブラウズでは拡張機能がセッションクッキーにアクセスできない
    • Orionではプライベートブラウズでもトークン生成が動作する
  • Privacy Passを有効にしても、TCP/IPの仕組みによりKagiは検索リクエストのIPアドレスを見られる
    • IPアドレス露出が気になる場合はTorまたは信頼できるVPNの使用が推奨される
  • すべてのトークンは、生成月をXとするとX+2月の1日午前0時に失効する
    • 同じ時点に生成されたトークン群の似た失効日が、複数検索の識別に使われる問題を避けるための方式
  • Safariは現在サポートされていない
    • Safari拡張APIは、リクエストからクッキーを削除する機能をサポートしていないとKagiは把握している
    • クッキーを削除できないと、ログイン済みアカウントで認証され続ける
    • WebKitベースで近いネイティブ体験を望むなら、Privacy Passが統合されたOrion Browserを代替として使える

関連記事

1件のコメント

 
GN⁺ 2025-02-14
Hacker Newsの意見

  • Kagiが今や Privacy Pass を使っているのは良いし、会社自体も全体的に悪くなさそうに見える。
    ただしKagiは、私がしばらく取り組んでいたIETFドラフト [1] とRust実装 [2] を実質的に取り込み、その上に薄いラッパー [3] を作ったうえで「KagiのPrivacy Pass実装」と呼んでいる。
    私にもある程度のクレジットは与えられるべきだったと思う。IETFでの作業やオープンソースソフトウェアの作業は大半が自発的かつ無償で、勤務時間外に行われることも多い。こういう扱いを受けると、モチベーションが下がる。Kagiならもっときちんとできるはずだ。
    [1] https://datatracker.ietf.org/doc/draft-ietf-privacypass-batc...
    [2] https://github.com/raphaelrobert/privacypass
    [3] https://github.com/kagisearch/privacypass-lib/blob/e4d6b354d...

    • 正直なところ、記事で言う「KagiのPrivacy Pass実装」は、RFCやプロトコル実装そのものではなく、その機能をKagiのサーバーとクライアントに統合した部分を指しているように思える。RFCについては記事内でも認めている。
    • Kagiが「raphaelrobertへのクレジット」を追加するか、ライセンスのコピーをコードのどこかに入れれば準拠したことになるのか気になる。
      自分のオープンソースが実際に使われたことはなく、普段はMITライセンスで配布しているので、他のグループや組織が実際にライセンスをどう遵守しているのか知りたい。
    • 2025年2月14日東部時間午後12時15分ごろにREADMEのヘッダーをキャプチャしたとき、こう書かれていた。

      This repository contains the source code of the core library implementing the Privacy Pass API used by Kagi.
      これは確かに印象が良くない。ただ、Kagi側の人たちは「raphaelrobert/privacypass向けの Crystal Langラッパー を実装したコアライブラリ」のように、より正確な表現へ変えることには前向きだと思う。意図的というより、動くようにすることに集中していて、文言を読み返す人を付けられなかった可能性が高い。

  • 素晴らしい。自分が使っているサービスが、自社よりもユーザーに利益のあることを実際にしているのを見るのは珍しい。予想外だが、とても気持ちの良い驚きだ。
    この拡張機能がブラウザーのコンテキストを自動的に理解して、よりうまく統合されるといい。つまり通常モードでは自分のセッションを使い、プライベートブラウジングモード（browser.extension.inIncognitoContext）では、こちらが別途何もしなくてもPrivacy Passで認証してくれる、という形だ。
    OrionはGNU/Linux版がないので使っていない。

    • こうしたことが珍しくなった理由は、この分野の大半の企業、実際には多くのテック企業が、あるユーザーグループに何かを提供し、その結果を別のユーザーグループに売って収益を上げる両面市場モデルを使ってきたからだ。
      実際の売上を生むのは後者なので、基本的に前者のグループの利益と後者のグループの利益は衝突し、前者に敵対的な構造になりやすい。
      Kagiや他の新しいテック企業が新鮮なのは、このモデルを捨て、自分たちがサービスを提供し収益を得る相手を1つのグループに絞る「昔ながら」のモデルに戻ったからだ。
    • Linux向け Orion の作業を昨日始めた。
    • この方式の欠点は、大きなネットワーク上にいない場合、IPアドレスだけでも匿名性が崩れる可能性があることだ。
      Kagiはユーザーがログインしていることを知っており、ユーザーがプライベートウィンドウでセンシティブな検索をすれば、それらの検索を結び付けられる。モードを素早く行き来するのは望ましくない。
    • もし知らなかったなら、2024年末ごろにポッドキャストで Orion Linux版 を計画中だと発表していた。
    • Kagiを使っていると、正しい選択をすることに慣れてくる。本当にこれといった失敗がなかったのは驚くほどだ。
      私のKagi Tシャツもそうだったらよかったのに。2回目の洗濯で裾がほどけて、今では寝間着兼庭仕事用のシャツになっている。交換用の無料シャツクーポンはもらったが、まだ発送されていない。

  • 記事でも示唆されているが、アカウントなしで Privacy Passを購入できるストア があれば筋が通る。
    何らかの暗号通貨、おそらくMoneroに対応する必要があり、GNU Talerのようなものも、その技術がいつか実用に足るようになれば対応するとよい。

    • KagiはBitcoinを受け付けているが、創業者のVladがフォーラムで、このオプションを使う人が少なすぎるため Monero対応 に投資する意味はないと述べていた。
    • アカウントなしでトークンを販売するサードパーティストアが理想的な解決策だという点には同意する。ただし、アカウントがないと、Kagiを便利にしている機能、たとえば特定のドメインを結果から除外したり、特定の結果タイプの優先順位を上げたりする機能を利用できなくなる。

  • これが結局、ログを残さないと仮定したうえでのプライバシーなのかが気になる。難癖をつけたいわけではなく、この部分が本当に理解できていない
    ユーザーAがKagiにトークンを要求し、Kagiが「いいよ、トークンを500個あげる」と言ったとしよう。Kagiが今ユーザーAに渡した500個のトークンを記録しておけば、後でそのうちの1つが使われたときに、そのトークンがユーザーAに割り当てられたものだと分かるのではないか？
    もちろんKagiがこのデータを保持しなければ、トークン自体は有効/無効だけが示され、「Y日にユーザーAに渡した有効なトークン」としては残らないので問題ないだろうが、それがすべてなのか？ 自分は何か誤解しているのだろうか？

    • サーバーがトークンを生成するのではなく、クライアントがトークンを生成する。サーバーはそのトークンが、生成権限を得たクライアントによって作られたものかを検証できなければならないが、どのクライアントが作ったものかは分からないようになっていなければならない。少なくともサイドチャネル情報なしではそうであるべき

      The main building block of our construction is a verifiable oblivious pseudorandom function (VOPRF)
      このプリミティブがどれほど検証されているのかはよく分からないが、少なくともサーバーがクライアントにトークンを配っておいて、誰に渡したか分からないふりをするよりは、はるかに多くの仕組みがあるように見える
      参考論文: https://petsymposium.org/popets/2018/popets-2018-0026.pdf

    • Privacy Passの文書 [0] はこの部分を扱っているが、主に論文の中でより深く説明されている。要点は、サーバーが返したトークンと、クライアントが再び送る修正済みトークンとがリンク不可能だということだと思う
      サーバーは、あるユーザーたちにトークンA、B、Cを返し、後でトークンX、Y、Zを受け取ったことは分かる。X、Y、Zが有効であることも分かるが、自分が発行したトークンとの対応関係は分からない。ここでは楕円曲線暗号が使われている
      [0] https://privacypass.github.io/
    • アイデアは、トークンがどのアカウントにも結び付かないということ。匿名トークンである
    • Privacy Passトークンの前提を理解していないように思う
      核心は、サーバーがどのトークンがどのクライアントに属するのかを知らないということ。サーバーはトークンを生成しない

  • 自分がいつも見ていたKagiの最大の欠点が、これで解決された。製品をほぼすべての人にとって魅力的にするために、耳を傾けて取り組んでくれてありがとう

  • まだKagiを使っていない人たちの大きな不満の1つは、ログインと決済情報を求められることによるプライバシー上の懸念だ
    自分はその点を心配していた側ではないが、実際に心配していた人たちにとって、この変更がどの程度その懸念を和らげるのか気になる

    • 自分はその心配をしていた側で、検索エンジンにログインするということが今でも信じがたいほどだ。もちろん、今ではどれだけ多くの人がそうしているかは知っている
      システムを簡単に検証した後なら、今はかなり登録する可能性が高い
    • 暗号がKagiの言う通りに動作すると仮定すれば、この方式は検索リクエストをアカウント情報から完全に分離してくれる。アカウントが複数の検索トークンを作り、各検索リクエストごとにトークンを1つ消費する仕組みだ
      トークンはデバイス上で生成され、使われるまでデバイスの外に出ないため、理論上、Kagiがトークンだけを見て、どのアカウントがそのトークンを作ったのかを知る方法はない。フィンガープリント追跡やIPの関連付けまでは解決しないが、FirefoxとChrome向けのプラグインがフィンガープリント追跡を減らすための措置を講じるという。これはGoogleやDuckDuckGoをそのまま使うより悪くも良くもなく、本当にプライバシーを求めるならTorでも動作する
      トークンをまったく共有せずにどうやって正当性を証明するのかははっきりしないが、おそらく何らかの~~ゼロ知識証明~~のようなものが入っているのだろう
      修正: ゼロ知識証明ではなく、ブラインド署名のようだ

  • Kagi 側の誰かが、トークンテーブルにトークンを生成したユーザーとその SessionCookie を入れる新しい列を追加するのを、何が防いでいるのか分からない
    元のトークン生成者と非常に簡単には結び付けられない理由が見えない

    • 実装者です。Privacy Pass の「発行」プロトコルの中で、クライアントがサーバーが処理する「メッセージ」を生成します。サーバーの出力はクライアントに戻され、クライアントはこの出力をさらに修正して最終的なトークンを作ります
      最後のクライアント側の修正段階でこれらのトークンがランダム化されるため、サーバーはそのトークンがどの発行プロセスに属していたのかを識別できなくなります
      本当に素晴らしい点は、サーバーが自分の段階で悪さをしようとしても、なおそうなることです。なのでユーザーはクライアントソフトウェアだけを信頼すればよく、私たちはこれをオープンソースで公開しています: https://github.com/kagisearch/privacypass-extension
      ブラインド署名に言及している人が何人かいますが、実際 Privacy Pass はそれを構成要素として利用できます。ただし正確に言うと、Kagi では「忘却疑似乱数関数」（OPRF）に基づく「Privately Verifiable Tokens」(https://www.rfc-editor.org/rfc/rfc9578.html#name-issuance-pr...) を使っていて、個人的には OPRF の方がブラインド署名よりも格好いいと思っています
    • 引用されている論文 [1]、つまり暗号学的匿名トークンプロトコルの論文で説明されている内容のようです。単純な平文トークンではありません
      https://petsymposium.org/popets/2018/popets-2018-0026.php（「Privacy Pass: Bypassing Internet Challenges Anonymously」）
      Cloudflare も同じものを実装していたようです。少なくとも HN のコメントは同じ論文にリンクしています
      https://news.ycombinator.com/item?id=19623110（「Privacy Pass (cloudflare.com)」、53 comments）
    • トークンはクライアント側で「生成」され、サーバーはそのローカル生成トークンが「有効」になるのに十分な情報だけをクライアントに渡します。それでいて、そのトークンを特定の検証試行と結び付けることはできません
    • 私もまさにその疑問を思い浮かべました。サーバー側の信頼に依存するわけにはいかないので、自分が何か誤解しているのか気になります
    • 私の理解が正しければ、「Privacy Pass」はブラインド署名を使っているので、TokenResponse に含まれるトークンと検索クエリに提供されるトークンを互いに関連付けることはできません

  • これは実際に機能するのか？ トークンは一度しか使えないので、現実的にはクライアントが特定の検索セッション内でトークンを生成して使うループを回すことになるはずで、そうするとペアを結び付けるのは非常に簡単になる。記事でもこう述べている

    For this reason, it is highly recommended to separate token generation and redemption in time, or “in space” (by using an anonymizing service such as Tor when redeeming tokens, see below).
    Tor は空間をランダム化してくれるだろうが、時間はどうするのか？ それで「下を参照」という部分を見たが、関連する内容は見つけられなかった。十分なリクエスト量があれば、クライアント同士が時間的に互いを隠してくれるという考えなのか？
    また Tor も、セッションを継続的に作り直さない限り、空間をランダム化するには限界がある。私の知る限り、ループはセッション中は固定され、セッションを作り直すには 10 秒ほどかかる。では本当に空間をランダム化していると言えるのか？

    • 1 回のトークンリクエストで N 個のトークンを作れます。私たちは N = 500 に設定しているので、ほとんどのユーザーは新しいトークンをかなりまれにしかリクエストしません

  • 本当にクールで素晴らしい仕事です
    以前、Privacy Pass に似たブラインド署名認証を作ったことがあるのですが、マルチデバイスアクセスをどう扱うのか気になります
    おそらく、別のデバイスでトークンへのアクセス権を失う問題を緩和するために、まず無制限検索ユーザーだけにリリースしたのだと理解しています。長期的な計画について何かアイデアがあるのか気になります。以前このようなシステムを作ったときは、常にエンドツーエンド暗号化同期と組み合わせる必要がありました。これはエンドユーザーにとって面倒なだけでなく、ストレージ更新とブラインド検索リクエストを互いに関連付ける余地も生みます
    いずれにせよ本当に素晴らしく、これからは Kagi をただ信頼するのではなく、信頼する必要がないことを検証できるようになるので、さらに楽しみです

    • その通りで、マルチデバイスは確かに簡単ではありません。いくつかのアイデアを試してみましたが、明確な答えがある問題ではありません
      現在はレート制限によって、各デバイスが独立してトークンを生成する形で、複数デバイス上で Privacy Pass を使えるようにしています。どう進むかを見てユーザーからのフィードバックを聞いたうえで、また設計に戻る予定です

  • これは Cloudflare がクライアントの CAPTCHA 回避を許可するために使っていたものと同じ Privacy Pass なのか？ もしそうなら、このシステムの本当にきれいな応用だ。有料サービスに匿名で認証するために使えるとは考えたことがなかった

    • Privacy Pass の基盤になっている暗号技術 [1] は実は Ecash[2] から来ているので、結局一周して戻ってきたわけです
      [1] https://www.petsymposium.org/2018/files/papers/issue3/popets...
      [2] https://en.m.wikipedia.org/wiki/Ecash
    • そうです。ただ、私の知る限り Cloudflare は Privacy Pass の試験運用を終了しています
      Safari がこれをネイティブに実装した唯一のブラウザだったと記憶していますが、今では Orion もサポートしているようです