DEDA – 追跡ドットの抽出・デコード・匿名化ツールキット

 (github.com/dfd-tud)
2 ポイント 投稿者 GN⁺ 2025-04-03 | 1件のコメント | WhatsAppで共有
  • DEDAは、カラーレーザープリンターの出力物に含まれる文書カラー追跡ドット、つまり黄色いドットを読み取り、デコードし、匿名化するツールキット
  • 文書カラー追跡ドットは、プリンターと出力物の情報をエンコードする小さな体系的なドットパターンで、ほぼすべての商用カラーレーザープリンターに組み込まれている
  • スキャン画像から追跡データを読み取ったり比較したり、未知のパターンを抽出したり、PDFに独自の追跡ドット行列を追加したりできる
  • 匿名化機能は、スキャン画像の追跡データを大部分除去するか、プリンター別の匿名化マスクを作成してPDF文書に適用する方式で動作する
  • 良好な結果を得るには、入力スキャンは可逆圧縮、300 dpi、中立的なコントラストが推奨され、白黒ページやインクジェット出力物には追跡ドットが存在しない場合がある

DEDAが扱う問題

  • Document Colour Tracking Dotsまたは黄色いドットは、プリンターと出力物自体に関する情報をエンコードする小さな体系的なドット
  • この仕組みは、ほぼすべての商用カラーレーザープリンターに組み込まれている
  • ほぼすべての出力物には、ソースデバイスに関するコード化された情報が含まれ、例としてシリアル番号が含まれることがある
  • DEDAは、このフォレンジック上の特徴を読み取り、デコードする機能と、任意の追跡を防ぐための匿名化機能をあわせて提供する
  • ソフトウェア使用時には次の論文の引用を求めている
    • Timo Richter, Stephan Escher, Dagmar Schönfeld, Thorsten Strufe. 2018. Forensic Analysis and Anonymisation of Printed Documents. IH&MMSec '18, 127-138. DOI: https://doi.org/10.1145/3206004.3206019

インストールとGUIの実行

  • Python 3のインストールが必要
  • PyPIからインストール可能
    • pip3 install --user deda
  • 現在のディレクトリからもインストール可能
    • pip3 install --user .
  • deda_anonmask_applyの任意依存関係として、UnixとGNU/LinuxでWandをインストールできる
    • pip3 install --user wand
    • Wandがない場合、画像内の白い領域を含むページは匿名化できない
  • GUIは次のコマンドで実行する
    • deda_gui

ターミナルツールでできること

  • 追跡データの読み取り

    • スキャン画像から追跡データを読み取り、場合によってはデコードできる
    • 良好な結果を得るには、入力にpngのような可逆圧縮、300 dpi、中立的なコントラストを使用する必要がある
    • 実行コマンド:
      • deda_parse_print INPUTFILE

  • スキャン文書の束から別のプリンターを探す

    • 複数のスキャン文書から、別のプリンターで出力された文書を見つけられる
    • 実行コマンド:
      • deda_compare_prints INPUT1 INPUT2 [INPUT3] ...

  • 未知の追跡パターンの分析

    • 新しいパターンはparse_printで認識されない場合がある
    • 追加分析のために黄色いドットを抽出できる
    • 実行コマンド:
      • deda_extract_yd INPUTFILE

  • 独自の追跡ドットを作成する

    • 独自の追跡ドット行列を作成し、PDF文書に追加できる
    • 内容はdeda_create_dots -hに従ってパラメーターとして渡す
    • 実行コマンド:
      • deda_create_dots PDFINPUT
    • deda_anonmask_create -wで作成した補正ページを入力として使用できる

匿名化ワークフロー

  • スキャン画像の匿名化

    • スキャン画像から追跡データを大部分除去する
    • 実行コマンド:
      • deda_clean_document INPUTFILE OUTPUTFILE

  • 印刷用文書の匿名化

    • 文書をPDFとして保存し、DOCUMENT.PDFとして置く
    • 次のコマンドで作成したtestpage.pdfを余白なしで印刷する
      • deda_anonmask_create -w
    • その文書を300 dpiでスキャンし、可逆ファイルを次のコマンドに渡す
      • deda_anonmask_create -r INPUTFILE
    • この手順により、個別プリンターの匿名化マスクであるmask.jsonが生成される
    • 生成されたマスクをPDFに適用する
      • deda_anonmask_apply mask.json DOCUMENT.PDF
    • 結果として匿名化されたmasked.pdfが作成され、ページ余白0の設定で印刷できる
    • マスクがプリンターの追跡ドットを覆っているかを顕微鏡で確認する必要がある
    • マスクのドット半径、xオフセット、yオフセットはdeda_anonmask_applyのパラメーターで調整できる
    • DOCUMENT.PDFに白色または明るい色のグラフィック領域がある場合、その領域はWandがインストールされている場合にのみマスキング可能

トラブルシューティング

  • deda_parse_print: command not foundが発生した場合は、DEDAのインストールを確認するか、PATHにPythonユーザーbinパスを追加する
    • export PATH="$PATH:$(python -c 'import site,os; print(os.path.join(site.USER_BASE, "bin"))')"
  • DEDAが追跡ドットを認識できない場合、スキャンプログラムが紙の構造や追跡ドットをしきい値処理で除去しないように設定する必要がある
    • 白黒ページとインクジェット出力物には追跡ドットがない場合がある
  • プリンターが追跡ドットを出力しない場合、独自の追跡ドットを作成するか、別のプリンターで補正ページを印刷して自分のプリンター用マスクとして使用できる
    • deda_create_dotsで独自の追跡ドットを生成可能
    • deda_anonmask_create -wで補正ページを生成可能
    • 匿名化された追跡ドット版を使うか、deda_anonmask_create --copyでコピーできる
  • x86_64-linux-gnu-gcc関連のインストールエラーは、GUIに必要なeel依存関係が原因の可能性がある
    • 提案コマンド:
      • sudo apt-get install build-essential autoconf libtool pkg-config python3.6-dev gcc && pip3 install --user eel
  • wand.exceptions.PolicyErrorでPDF操作がセキュリティポリシーによりブロックされる場合、ImageMagick設定が原因

関連記事

1件のコメント

 
GN⁺ 2025-04-03
Hacker News のコメント

  • 私たちのチームは10年ほど前、DARPA 文書シュレッダー復元チャレンジで、この黄色い追跡ドットを使って裁断された文書を再構成した
    裁断文書を合わせていく間、プログラムがドットを強調表示する様子を見られる: https://www.youtube.com/watch?v=uzZDhyrjdVo
    そのおかげで大差で優勝できた

    • 小学生のころ、Daily Planet でこのチャレンジのことを聞いた記憶が残っている
      後日談を見て、忘れていた記憶がよみがえってきてかなり不思議な感じがした
    • Vinge の Rainbows End に出てくる図書館のシュレッダー/スキャナーは、遺伝子シーケンシングをゆるく置き換えたSF設定だと思っていただけだったが、ほぼ現実に近い実装を見ると面白い
    • 裁断片をプログラムに入れるためのスキャン工程がどんなものだったのか気になる
      解法アルゴリズムと同じくらい、その工程だけでも記事にできそうだし、ああいう混沌を扱える性格というのも別にありそうだ

  • 最近、ここでは明かしにくい事情で追跡ドットを少し調べる機会があった
    青色LEDの懐中電灯をカラー印刷物に当ててみるとよい。ページ全体に砂をまき散らしたように、ものすごい数のドットが打たれていて衝撃的だ

    • プリンターメーカー各社が、これまで余分に使ってきた黄色トナーのせいで集団訴訟を起こされていないのは意外だ
    • もはやプリンターだけの話でもない: https://datadotusa.com/technology.htm
    • レーザー、カラーレーザー、インクジェットのうち、どのプリンターのことを言っているのか気になる

  • 自分のプリンターが追跡ドットを打たないなら、別のプリンターの追跡ドットを偽造できるという考えは、否認可能性という点でかなり興味深い
    ただしこの場合でも、匿名化マスクを印刷するには元のプリンターにアクセスする必要がありそうだ

    • Wikipedia によると、ドット配列は機器のシリアル番号と印刷日時をエンコードするので、他人のプリンターを偽装するには実質的にシリアル番号さえあればよい
      今ではプリンター設定を通じてリモートでもアクセスできるかもしれない
    • 追跡ドットまで調べるようなフォレンジック調査の段階なら、偽造の試みの大半はかなり明白に露見し、むしろこうした手法を知っている人に容疑者を絞り込む証拠になる可能性が高い
      ざっくり分析する人ならだませるだろうが、熟練した調査官なら「追跡ドットは明らかに X ブランドだが、グレースケールに使われているラスタは明らかに Y 系だね」といった見方をしそうだ

  • 関連して面白い記事を見逃していたなら、ここにある: https://news.ycombinator.com/item?id=42880704

    • 最近「発見された」初期のPokemon カードのプレイテスト版が、このドットの存在と解読を根拠に、偽物か少なくとも非常に怪しいと判明した話なので読む価値がある
      さらに興味深いのは、その発見と分析を投稿した人物が、偽カードにすでに数千ドルを費やしていて個人的に損をする可能性があったにもかかわらず、結果を公開した点だ

  • 同じページを複数のプリンターで印刷したらどうなるのか気になる
    1台目のプリンターが実際の内容を印刷し、ほかのプリンターがまだ白い領域にごく少しずつだけ追加で印刷する形なら、あるプリンターが別のプリンターの追跡ドットを壊すのだろうか？

    • そうなるだろう。プリンターには、そうしてはいけないと知る方法がないのだから
      ただし詳細な条件によっては、一部または全部をなお読み取れる可能性もある

  • プリンター版OpenWRTのようなプロジェクトを始める変わり者の家には、MIB が訪ねてくるのではないかと思い始めている
    追跡不能な表現は許容できず、不都合なミームの出所を外科手術のように攻撃できなければならない、というわけだ。だから craigslist で手に入れた白黒レーザープリンターを別 VLAN に置き、CUPS サーバーを中継にして使っている
    Niantic がこの10年以上やってきたことについて、十分な情報を得たうえで同意した人など誰もいないし、すべての印刷物が追跡可能になることにも誰も同意していない。製品にもプロセスにも、「目に見える識別子がないからといって識別子がないわけではない。ステガノグラフィックな識別子が存在する可能性がある」とは警告されていない
    私たちが買った製品の中にある汎用機械が、所有者である私たちの望むように再利用できないほどロックされているのも同じだ。商業組織と国家機関から投げつけられる侮辱を「クソのサンドイッチでも食うか、それともサンドイッチなしで殴られるか」として受け入れるようになってしまったし、Louis Rossmann の Consumer Action Taskforce（CAT）はこうした事例を集める優れたアンソロジーになりつつある
    いまこそ反撃する時だ。まともなプリンターをハックし、ファームウェアを実用的なものに置き換え、こういうくだらないものから抜け出すべきだ。こうした追跡ドットや他のステガノグラフィックな追跡方式は、私のような人間、隠れた統制の仕組みを指摘し、巨大な黒曜石のイカが情報リスクや誤情報とレッテル貼りしたミームを広める人間を追跡し、沈黙させるために存在している

    • 偽造をしようとするなら、普通の家庭/オフィス式に紙へ印刷するのではなく、精密公差の小さい時計職人用のCNCのようなものを手に入れて、アルミなどで印刷用スタンプを作っただろうと思う
      一般的な紙幣取扱者でも簡単に見抜ける方法なので、紙にプリントするのは愚かに見える

  • 今後数年でかなり重要になりそうだ
    デモのビラやパンフレットを印刷する予定なら、信頼できる人がいる場合は専門の印刷所に任せるか、少なくともプリンターを現金で買い、絶対にインターネットに接続せず、Linux コンピューターに USB だけで接続するのがよい
    macOS と Windows はプリンタードライバーを自動インストールでき、そのドライバーが本社に連絡してプリンターIDを何らかの識別子と結び付けることもあり得る

    • 東欧圏の全体主義国家でこうしたことがどのように行われていたかは、サミズダートを見ればよい: https://en.m.wikipedia.org/wiki/Samizdat
    • そこまで気にするなら、シルクスクリーンキットを買うほうがよい
      Tシャツも刷れる
    • ビラを配る人たちを追跡するほうが、ずっと簡単なのでは？
    • あるいは、現金で買ったプリンターで、文書全体に有効だがランダム化した追跡ドットを大量に打てばよい

  • 公開ツールで復号できるプリンターがどの程度の割合なのか、本当に気になる
    どのメーカーのコードが破られているのか、統計はあるのだろうか？

    • GitHub では、Timo Richter、Stephan Escher、Dagmar Schönfeld、Thorsten Strufe による 2018 年の論文 Forensic Analysis and Anonymisation of Printed Documents を参照している
      コピーはこちらにある: https://ericbalawejder.com/assets/hexview/Forensic-Analysis-...
      表 1 はメーカー、分析したプリンター台数、ドットが見つかったかどうかを整理している: Brother 1 台はなし、Canon 10 台はあり、Dell 4 台はあり、Epson 8 台は一部モデル、Hewlett-Packard 43 台は一部モデル、IBM 1 台はあり、KonicaMinolta 21 台は一部モデル、Kyocera 4 台はあり、Lanier 1 台はあり、Lexmark 6 台は一部モデル、NRG 1 台はあり、Okidata 9 台は一部モデル、Ricoh 6 台はあり、Samsung 5 台はなし、Savin 1 台はあり、Tektronix 4 台はなし、Unknown 1 台はあり、Xerox 15 台は一部モデル
      論文で説明されているいくつかの手がかりを除けば、ドットパターンが見つかった場合はおおむね解明されているように見える

  • 白黒レーザープリンターも追跡ドットを生成するのだろうか？
    そして、こうした追跡にどんな意味があるのだろう。原則として、私たちの生活の隅々まで追跡されなければならないのか？

    • 白黒プリンターのステガノグラフィックな識別子について確実に知っているわけではないが、白黒プリンターが追跡情報を埋め込まないのだとしたら、むしろ驚くと思う
      あらゆるものに出所情報をばらまくことは、国家安全保障上の価値があまりにも大きい。いつも安全やセキュリティを理由に掲げ、すぐに「でも何が害なんですか、やってはいけないことをしているわけではないでしょう……そうですよね？」が続く
    • Secret Service が、紙幣を簡単に再現できるほどプリンターの品質が向上した後、メーカーにドットを追加するよう要請した、あるいは要求したのだと理解している
      主な用途が偽札犯の追跡なら、白黒プリンターには不要で、そのため含まれていないという話になる
    • https://www.eff.org/pages/list-printers-which-do-or-do-not-d...
      この一覧は 2017 年以降更新されておらず、おそらく一人の人物が FOIA 請求をもとに推論した結果だった可能性が高い。次に中国の大学が米国政府の機密を公開するまで待つしかなさそうだ
    • 白黒の 20 ドル紙幣にだまされる人はいないので、あえてドットを打つ必要はない、という発想なのだと思う
    • モノクロプリンターには黄色いドットがない
      数十年前、文字のカーニングを調整して情報を隠すソフトウェアの仕事をしたことがあるが、私の知る限り、そのプロジェクトは特に成果につながらなかった

  • これも興味があるかもしれない: https://en.wikipedia.org/wiki/EURion_constellation

    • そして、あまり知られていないがより新しい、目に見えないデジタルウォーターマークベースのバージョンもある
      残念ながら、そちらは公開情報がほとんどない: http://www.cl.cam.ac.uk/users/sjm217/projects/currency/