「セグメント木と代数構造の理論」の補遺

先日, 表題に挙げた名前で文書(というよりは論文)を公開した: https://elliptic-shiho.github.io/segtree/segtree.pdf

この論文は@kimiyuki_uと私が書いたものである. 書いていたのは2019年のはじめから2021年にかけてであり, しかしその後約三年の間塩漬けとなってしまっていた. 公開にあたっての心持ちについてはPDF先頭に書いているので省略することとし, 本記事はその後読み直していて色々と思い出してきたことを書き綴っておきたい.

なお, 2024年現在における新規性の有無については未検証である. もしも研究が出ているのであれば教えてほしい.

我々の目指したかったところについて

そもそもこの論文を書く理由は(競プロ的な意味では)殆ど存在しない. 仮にこれを読んだところで新しく解けるようになる問題があるわけではないし, 確実な新規性と言えるものもない. しかしながら, 私も彼も数学の目線で競プロに関する話をしたい, なおかつ面倒な計算の嫌いな人間であった. それが執筆を始めた一つの理由である.

たとえば当時の記録によれば, 我々の間では木構造とは次のように定義されている:

$V$を集合としたとき, $\top\in V$, $P\colon V\setminus\left\lbrace\,\top\,\right\rbrace\to V$について以下が成立するならば$(V, P, \top)$を根付き木と呼ぶ.

$$ \forall v\in V\setminus\left\lbrace\,\top\,\right\rbrace.\ \exists! k\in\mathbb{N}.\ \mathrm{s.t.}\ P ^ k(v) = \top. $$

根付き木$T = (V, P, \top)$について, $v\in V$を$T$の頂点と呼び, $v\in V$を$v\in T$で略記する. また, $\top$を$T$の根と呼び, $\mathrm{root} _ T$で表す. $T$が明らかな場合には$\mathrm{root}$とすることもある. 各$v\in T$について$P ^ k(v) = \mathrm{root}$なる$k\in\mathbb{N}$は唯一つ定まることから, これを$\operatorname{depth}(v) := k$とおいて$v$の深さと呼ぶ.

$P$の逆像$P^{-1}$について, $P ^ {-1}(v)$の元を$v$のと呼ぶ. また, $\operatorname{{Le}{af}}(T) := \left\lbrace\,v\mid v\in V, P ^ {-1}(v) = \emptyset\,\right\rbrace$の元を$T$のと呼ぶ. 以降, $C(v)$で$P ^ {-1}(v)$を表すものとする. $v\in V$, $k\in\mathbb{N}$について$P ^ k(v)$を$P$の祖先と呼ぶ. 明らかに$\mathrm{root}$は任意の頂点について祖先である. このことから, $v, u\in V\setminus\left\lbrace\,\mathrm{root}\,\right\rbrace$について$P ^ a(v) = P ^ b(u)$なる$a, b\in\mathbb{N}$が必ず存在し, $v$が$u$の祖先でない場合(あるいは$u$が$v$の祖先でない場合)には$P ^ {a-1}(v)\ne P ^ {b-1}(u)$が成立. この$P ^ a(v)$あるいは$P ^ b(u)$は$v, u$の最近共通祖先と呼ばれる.

このように, (病的なまでに)形式化された状態で数学の世界に競プロに頻出の概念を埋め込んでしまえば, 面倒な具体計算を減らせるし, それにある程度は自動化した議論ができるようになる. そのためには「お気持ち解説」では不足なのである1. 彼はkmyk/Jikkaにおいてその夢を(競プロ問の自動回答という形で)いくらか実現していたし, 私はデータ構造という曖昧な対象をより深く理解できるようになった.

しかしながら, セグメント木の定義そのものを研究するのはとても難易度が高かった(次節参照). そのため「セグメント木の上には代数的な構造がいろいろと"乗る"らしい」というところから「セグメント木の上に乗る代数的構造とはどのようなものか」について興味を向けたのは自然な成り行きだと言えよう. 私は, 彼が既存研究として持っていた「複数のクエリの合成を一般的にやるための十分条件」について, それを遅延伝播構造・遅延伝播積といった道具を追加定義して純数学的な立場から示した. その結果を整理・体系化したものがこの論文である.

圏への拡張の際には加群圏やモノイダル圏, 加群によって豊穣化された圏などを用いて表現できるだろうかという夢想をしていたが, 今の所それらは検討段階のままである.

セグメント木そのものについて

構造だけ見ればセグメント木はただの二分探索木である. 実際には区間クエリとの束として扱うことでセグメント木はセグメント木として扱われている. ところで, たとえば動的セグメント木の木構造は完全二分探索木としては扱われず, 単なる二分木として扱われる. セグメント木は完全二分木に限定されたデータ構造ではない にあるように, 学術的・歴史的にも平衡二分木として扱われるケースはあるようだ. いずれにせよ, 完全二分探索木の場合にのみ適用可能なテクニックはこれらにおいて通用しない.

ここまで二分木が用いられてきたわけだが, その理由が最終的に「二分探索するのがoptimal caseになるから」になることは想像に難くない. この点は事実そうなのだが, 実際には一般の木構造であっても, 適切に区間を割り振れば同様の構造を実現できる. このことから, 「セグメント木とはたんに木構造の各頂点に区間を割り当てる写像としては理解できないだろうか?」ということを考えていた.

実際, 彼は 完全二分木への添字付けであってセグメント木ではないものを考える において「添字の割り当て方」としてこの区間割当の考え方に触れている. 半年ほどの間「セグメント木とはどのような区間割当のことか, 或いは区間割当写像はいつセグメント木になるのか」について考え続けはしたのだが, 結局この点については考えがまとまらないままストールしてしまった.

セグメント木のなす空間について

管理したい列の長さを$n$としたとき, 半群$S$の乗っているセグメント木の区間操作は$S ^ n \to S ^ n$という写像だと思える. 列から列への状態遷移全てを収めてしまえば, 実際にはそのセグメント木によって表現可能な世界は一つの圏をなすのではないか. というような仮説を立てて考えていたことがある. その場合クエリは関手として取り扱われる (ことになるだろう. 完全には未証明, 検証段階のネタ).

上述定義は「セグメント木は何らかの圏として表される」という見方である. でも実際にはそれよりも面白そうな世界がある. それは「遅延伝播構造を対象, 遅延伝播構造の間の準同型を射とした圏」である. これは「遅延伝播セグメント木を対象, 遅延伝播セグメント木の間の(代数構造に関する)準同型を射とした圏」と言い換えてもよい.

本論文において示している「一定の十分条件を満たせば, セグメント木同士で直積・直和に相当する演算が可能である」という主張は, 上の圏における直和・直積の議論に言い換えられることが予想される(完全には未証明). これは「セグメント木全体からなる世界は何かしらの構造を持っていそうだ」という示唆だと思えないだろうか. セグメント木からセグメント木への射の形次第では「セグメント木同士の射が一体どのような形をしているのか」という表現論的な研究もできるだろう2.

加えて, "セグメント木全体がなす圏"が仮に$\mathbf{Sets}$や$\mathbf{Ab}$の部分圏に収まるような範囲だとすれば, そこには自然にトポス的な距離感を入れることも可能であろう. 実際のところ, 2024年現在の私が気にかかっているのはこの点, あるいはもっと引いた「セグメント木のモジュライ空間とはいかなる形をしているか」という代数幾何学的な視点である. ここまで来ると計算可能性などどうでもよくなってしまうので, その点でも彼の(あくまで計算する立場からの)助言は嬉しかったなと反復している次第だ.

最後に

セグメント木に注目して, 思い出せた範囲でこの論文に関するトピックをいくつか並べてみた. 他にもより一般の議論ができそうな箇所はあるし, 山のように存在するメモ用紙やノートを掘り返せばネタはあると思うのだが, 今思い出せないのであればそれほど考えてもいなかったことなのだろうと一旦区切ることにする. 公開できずにストールするよりも, 公開できたほうがよい.

彼の関東における住居は私の家から数駅の場所だった. その選定理由が私とこの論文に関する議論をしやすくするためだと本人に聞いた際には驚いたものだ3が, 実際そのぐらい熱を入れて書かれた作品でもある. 今となっては拙い証明も含まれているが, Twitterにおける発言の通りどうか読んでやってくれという気持ちだ.


  1. 実際のところ, 私がセグメント木について実務的要請から調べている際に「競プロにおける解説はどれもお気持ち解説しかない! まともな解説かと思ったらコード書いてるだけ! こんなんで一体人々はどうやってセグメント木という対象を理解・勉強してるんだ?」とキレて彼に質問した際に「それはまともな定義がそもそも存在しないからですよ」と返ってきたのが本研究の端緒である. なお, 目的が違うがためにこのような感想になっているだけで, お気持ち解説自体を批判する意図はない.
  2. 計算量とセットで考えなければならない計算機科学の文脈においては, 線形演算が如く 「小さい演算」の形式的定義 をwell-definedに定義してやらなければならない可能性は実際に高い.
  3. 普段からの交流もしやすくなったのはとてもよかった. たとえば mod で計算するときに零の重複度も持つテク は私が暇だからと彼を呼びつけたコメダでの議論が元になっている. リモート勤務全盛の今言うのも何だが, オフラインでの自由度の高さは生産性に無視できない影響を与えることを実感した.

TPMとの戯れ long version

はじめに

この記事はセキュリティ・キャンプ全国大会 2023のLT大会で発表した以下のスライドを解説するものです. このときは5分程度しかなかったのでまともに解説できなかった. なんか色々書いていたら9000文字を越えてしまったので, 暇なときにつまみ読んでもらえればと思います.

https://elliptic-shiho.github.io/slide/Playing_with_TPM.pdf

この記事は少し砕けた形で書いてみようかと思いますが, 普段硬い文章ばかり書いているので読みづらいかもしれません. その点ご容赦ください. あとやたら長い.

前提としては「認証と認可の違い」「応用情報処理程度のPKIの知識」あたりがあるとわかりやすいと思います.

TPMとは

皆さんTPM使ってますか? Windows 11へのアップグレード時にお世話になるあれです1. TPMという単語はTrusted Platform Moduleのアクロニムで, Windows11で要求される「2.0」は2023年現在の最新バージョンです. 実はTPM 2.0はちゃんとISO規格にもなっています2. 策定はTrusted Computing Group (TCG) が行っており, 著名なチップメーカーやOSメーカーが名を連ねています.

2.0の一個前のバージョンは1.2です. こちらもISO規格となっており3, BitLocker等で既に利用されています.

BitLockerという単語が登場したことで, TPMが暗号に関係することを皆さんは想像したことでしょう. 大正解です. TPMは暗号処理に関するコプロセッサとして登場したものです. 特に「安全な乱数生成」「TPMチップ固有の情報を用いた所有者認証」あたりが目玉でしょうか. TPM2.0は更に複雑になっているのですが, そのあたりの詳細はそのうちまた別に記事を書くこととします.

TPMは暗号処理全般を担当できますから, 「TPMを用いることによって, 暗号に関する処理をCPU上で行う必要がなくなる」というメリットもあります. 耐タンパ性より「安全に鍵を保存できる」という性質もあるといたれりつくせりですね. 当然TPM内から秘密鍵を持ち出せないようにするオプションもあり, これを用いることで「当該TPMをもっていない場合秘密鍵の復元はできない」というような状況を容易に作り出せます.

ハードウェア編

そんなTPM, ぜひともお話してみたいと思いませんか? ここでは思うことにしておいてください. この手の部品は秋月や千石ではまず手に入りませんので, 初手でDigi-keyを見に行きます.

調べると結構出てくるもので, アクティブな製品に限ってもInfineon, Microchip, STMicroelectronicsと著名なメーカーの製品が100件ほどヒットします.

今回は手元にだぶついていたMicrochip MCP2221A (USB - I2C / UART / GPIOコンボという便利なチップ)を使いたかったため, 通信手段はI2Cに限定します. そしてMicrochip / Atmelの製品は細かいデータシートが公開されていないため4に一旦除外. 当然バージョンは2.0固定. 絞っていくと案外製品は少なくなるもので, 最終的にはInfineon社のSLB96735というチップに収まりました. 購入当時は1チップ828円でした.

次は回路設計です. 今回はハードウェアの話をしたいわけではないので, 詳細は省きます. 実は私はプログラミングに触れるより前から回路設計をしています.

シンプルにつないだだけで, それ以外はSLB9673のデータシートにある推奨回路とUSB回りの設計からESD対策を抜いたぐらいです. 良い子の皆さんはちゃんと入れましょう. 一点もののつもりだったので, 完成品は以下のとおりユニバーサル基板製です.

0.5mmピッチのQFNはそこまではんだ付けしにくくなく, どれかといえばmicroUSB端子へのはんだ付けの難易度のほうが高かった. あれはすぐ外れてしまう...

ソフトウェア編 - MCP2221A

今回はMCP2221AのUSB-HIDデバイスドライバをRustで自作しています. その要約をさらっと書き記します.

当初MCP2221AのドライバがLinux kernelに取り込まれていると聞き喜んでそちらを使っていたのですが, 実はこの実装はいくらかバグっています. 具体的にはI2C通信がたまにストールします. そもそもLinux専用ですので, MacWindowsでは動きません. それではUSBドングルとしての汎用性に欠けてしまいます. ということで既存実装を探しました. そのうちgoogle/mcp2221-rsZakKemble/libmcp2221をここで取り上げます.

まず前者はRustとlibusbによる実装で, 最初から開発に利用していたものです. しかしlibusbは新し目のMacと相性が悪く6, カフェなんかに出ておしゃれに7TPMプロトコル・スタック開発をやろうとしていた私の用途には合いませんでした.

後者はC言語による実装ですので, Rustで使う場合FFIを書かないといけません. 今回Unsafe Rustは可能な限り扱いたくなかったので, この選択肢も結局除外されます.

最終的に, これなら作ったほうがいいやとエイヤで書きました. USB-HIDレイヤまではhidapi任せなのでそこまで難しくありません. 普通のデバドラ開発と同じですね.

ソフトウェア編 - TCTI

TPMの仕様書は4分冊となっていますが, 実はこれは不完全です. というのも, この仕様書では「TPMに対するコマンド体系とその基本思想」は完璧に定義されているのですが, 「具体的にどう送るのか」に関しては一切定義がないのです.

当然これは意図的なもので, TCGはその下位レイヤーをTPM Command Transmission Interface (TCTI) と称し, 様々なインターフェイスごとに別個に規格書を出しています. I2C, SPI, LPC, TCPといったインターフェイスそれぞれについてです.

特にPC関連のTCTIに関する記述は TCG PC Client Platform TPM Profile Specification for TPM 2.0 - https://trustedcomputinggroup.org/resource/tcg-tpm-i2c-interface-specification/物理層からの全てが記載されています. プルアップ抵抗値やデバイスアドレス, チップ形状ごとのピンアサインまで細かく規定されており, これを読んでいればメーカーのデータシートは不要なのではと思わせるほどです.

また, TCG PC Client Device Driver Design Principles for TPM 2.0 - https://trustedcomputinggroup.org/resource/tcg-pc-client-device-driver-design-principles-for-tpm-2-0/ という素晴らしいドキュメントのおかげで, 我々はTCTIレイヤに関して詰まることなく実装を進められます. 実はTPM 2.0の参考書というものはほぼ見当たらないのですが, その一因はこの親切な定義にあるのではとちょっとばかり思っています.

tpmGoフラグを1にし忘れていたがために動作しない, MCP2221A側のデバドラがバグっていたなどの困難はありましたが, ここまでを実装してようやくTPMとお話できるようになります.

ソフトウェア編 - TPM API

TPM自体の仕様書はTrusted Platform Module Libraryという名前で総称されており, それは以下の4冊からなります. この4冊は合計でも2000ページほどしかなく, Intel SDMやTegraの仕様書を読み慣れた低レイヤーの民としては短くて感謝の念が起きるほどです.

  1. Part 1: Architecture (TPM 2.0のアーキテクチャ・理念)
  2. Part 2: Structures (TPM 2.0に関する構造・型)
  3. Part 3: Commands (TPM 2.0に搭載されているコマンド)
  4. Part 4: Supporting Routines (TPM 2.0の仕様の利用に関する情報8)

しかしそれでも問題は起きます. たとえばTPMTPM2_Startup というコマンドを実行することでスタートアップ処理を実行するのですが, 「このコマンドを実行するために何をどうエンコードして送ればいいのか」に関する直接的な情報はどこにもありません. 要するに, 「この4分冊をどう読めばいいのか」という段階で詰まってしまうのです.

理解した今であれば「Part 1でコマンド実行体系を掴み, Part 3でコマンドごとのパラメータリストをチェックした上で, Part 2に書かれている構造体に格納・エンコードする」と言えるのですが, 読み始めた当時はそんなことはわかりません.

色々と探した結果, 入門書として公開されている A Practical Guide to TPM 2.0: Using the Trusted Platform Module in the New Age of Security という書籍の第五章 "Navigating the Specification" に行き着きました. この章はTCP経由で利用できるTPMのシミュレータを利用し, 実際に仕様書のどこを読めばいいのかに関する読み方を提供するもので, これをもとに試しにいくつか手で作ったコマンドを送って確かめることで読み方を学びました.

とりあえず TPM2_Startup を実行できたら, 次は TPM2_SelfTest を実行できるように. 今度は TPM2_GetRandom で乱数を...といった形で実装し, 後は必要な構造体を必要なときに作るだけでよいところまで来ました.

実装に悩んだ箇所として, TPM2にはinterface typeという特殊な型があります. これは「TPMチップに依存して実装有無が変わるもの」という認識でよいです. Rustで書いている都合上, 動的にenumを変化させるのは難しいですし, かといって定数化してしまうのはちょっとどうかなというところ. 結局subenum crateを使って「実装されているかどうかはユーザーの責任として確認」「基本interface typeは部分型として実現」という形に収めました.

また, interface typeの最大の活用例である「暗号アルゴリズムの実装状況によって変化する型」には一番悩まされました. TPM2の仕様書には !ALG.ax のような謎の表記があります. これは「任意の非対称かつ署名に利用できるアルゴリズム」と読みます. そして !ALG.AX になると「任意の非対称かつ署名に利用できるアルゴリズムで, 特にそれ以外の用途に使えないもの」と読みます. TPMの世界においては暗号アルゴリズムにはa(非対称)やx(署名)といった属性が付与されており, これらを選択するためのものです. 以下に Trusted Platform Module Library Part 2: Structures p.93 §9.33 TPMI_ALG_SIG_SCHEMEより例を引用します:

これをsubenumで実装することに私は負けてしまい, だいぶ煩雑な形で実装することになってしまいました. いまでもこれをどう書くときれいに収まるのかに関しては悩み続けています. どなたかいい案あったら教えてください: https://github.com/ssh-slb9673-playground/tpm-ssh-agent/blob/b5e5aef420cfede64592fe19668830669a72254c/tpm_i2c/tpm/structure/algorithm/identifiers.rs

ソフトウェア編 - SSH Agent

せっかく単体で動くTPMボードがあるのですから, なにか実用的な目的を設定したいです. ということでSSH Agent9を作りました. といっても中身は殆ど既存crate( wiktor-k/ssh-agent-lib )を利用したもので, 私が書いたのはTPMとの通信処理と鍵生成ぐらいです.

なお, 私の書いたコードは TPM2_CreatePrimary を利用したもので, 特に TPM2_EvictControl による永続化をしているわけではないため, 再接続時に鍵は失われます. それでもちゃんと接続はできました. 「特定のハードウェアをもっていなければ接続できないSSHサーバー」の完成です.

ただし, プライマリキーの生成方法の都合上, 実はここにはセキュリティ的な課題があります. この点はTPMアーキテクチャに深く関わるものですので, 皆さんも是非この「CreatePrimaryが作る鍵は一体なんなのか」から仕様書と仲良くなってみてはいかがでしょう?

おわりに

今回書いたコードは https://github.com/ssh-slb9673-playground/tpm-ssh-agent にあります. 開発期間は概ね2週間程度, キャンプ終了時点の行数は4700行程度とそこそこの大きさになりました. いい勉強にはなったのではないでしょうか.

TPM 2.0はあまり国内のアマチュアが触れていない領域ということもあり, 今後何かしらこの分野の情報発信ができたらいいなあなどと考えています. USBは皆仕様書を読んでいるのに, TPM 2.0は誰も読んでいない. 不公平.

現時点ですぐに触れられる情報源のうち最も有名なのは Will Arthur, David Challener, and Kenneth Goldman. 2015. A Practical Guide to TPM 2.0: Using the Trusted Platform Module in the New Age of Security. Apress Berkeley, CA. だと思います. これは無料公開もされているため, 皆さんもすぐに読み始めることができます: https://link.springer.com/book/10.1007/978-1-4302-6584-9

また, Trusted Computing全体を通観するために私が読んだ本として Graeme Proudler, Liqun Chen, and Chris Dalton. 2014. Trusted Computing Platforms: TPM2.0 in Context. Springer. を挙げておきます. というかこの2冊以外にすぐに手に入る範囲のTPM 2.0の解説書はありませんでした. 本書は実務でTPM関連の開発をする人にも有用と思われますが, 些かアーキテクトに寄っている感もあります. TPM1.2とTPM2.0の差分に関する記述もありますので, 研究の際にもよい資料となるでしょう.

情報源が少ない理由はいくつかありますが, そのうち1つは間違いなく「十分に使いやすいプロトコルスタックの提供がなされている」という点にあるでしょう. たとえば https://github.com/tpm2-software/tpm2-tsshttps://github.com/microsoft/TSS.MSR です. 自作する必要性がない上, この中身に触れるような人は間違いなく仕様書を読めます. つまり解説の必要がない.

単純に「TPM 2.0はできることが多すぎる」という点も挙げられます. 今のTPM 2.0はPCRバンクを用いた起動時の整合性検証(所謂secure boot)の他, 「TPMに対して発行したコマンド列とその結果が間違いなくこちらの指示通りであることを確認しつつ, その実行されているTPMが本当に我々の指定したTPMであるか否かを識別する」とか, 「OSから特定の条件を与え, 起動ステートが一定の状態になっていなければ復号できない秘密鍵」みたいなものを作ることもできます.

上記事項に関してはPCR, ポリシー, remote attestation, audit sessionで調べてみると魔境が見えるのでおすすめです. 当然CPU - TPM間の通信を暗号化することもできますし, 生成した秘密鍵にはAuthValueなる個別のパスワード的なものを設定できます. TPM内のオブジェクトの認可制御だけで一冊書けるのではないでしょうか.

SSH agentにする際並行実行可能にする必要に気づき, そこからほぼ手を付けていなかったRustでの並行プログラミングをやるようなこともありましたね. tokio + reqwest程度なら触っていたけど, ちゃんと構造体にSync書いたのは初めてに思います.

最近実は少しアップデートを挟んでおり, Remote AttestationのProof-of-Conceptを実装してあります. 回路図のpdfも置いてあるので, もし必要であればご利用ください.

Future work

勢いで書いただけあってコードがかなり汚いです. もう少し真面目にクラス図描いた方が良かった気がします. ということで来年以降もう少し行儀の良いTPMプロトコル・スタックを作りたいと思っています.

TPM 2.0は認可制御が本当に複雑で, その上TPMにおけるセッションと認可の間の包含関係はベン図がないと理解できない状態です (A Practical Guide to TPM 2.0 p.168 Figure 13-1. Authorizations and sessions Venn diagram にその図があります). このあたりをきれいに見通せるよう組み直す試みだけで2ヶ月ほど経過してしまった.

私が今回調べた限り, アカデミア領域では研究対象になっているTPM 2.0も, アマチュアで楽しむには情報源が少ない状況です. 時間に余裕があれば, セキュリティモデルの概説や各種技術詳細を読む記事を書いていくのもありなのかなと夢想はしています. どこにそのような時間が?

おまけ

私は一点もののつもりだったのですが, このUSBドングルはどうせならもっとドングルらしくしたいなとは思っていました. チップも余っていますし...

そこで, 昨年のキャンプ受講生だったsaitenさん ( @sort_reverse )はそういえばプリント基板作ってたじゃんとお願いしてみたところ, USBドングル然としたTPM基板が出来上がりました. 大変感謝しています (いつも面倒だからPCB設計やらないのです...).


本記事は@leno3sさんに軽くレビューしてもらいました. ありがとうございます.


  1. 実は私はWindows10登場後ちょっとしてからWindowsを見限ってしまい, この経験はありません... 2023年末になってもオフラインの検証機はWindows7です.
  2. ISO/IEC 11889:2015
  3. ISO/IEC 11889:2009
  4. NDA必須. なお通信プロトコルやピンアサインはTPM仕様側で決まっており, 特殊なことをしない限りは利用可能.
  5. 当時はアクティブステータスだったのですが, 今見ると最終購入期限が設定されてしまっています. SLB9670の上位機種としてはあまり売れなかったのでしょうか... (I2CでTPMと通信する需要自体があまりなかった...?)
  6. https://github.com/libusb/libusb/issues/1014
  7. カフェに居るぐらいしか時間がなかったとも言う
  8. 実はPart 2, Part 3は機械可読であるように書かれており, 手実装する必要はありません. そのためのフォーマット情報や, 環境依存のパラメータリストの既定値等が収録されています.
  9. SSHの公開鍵認証を代行するデーモン. 便利.

古典暗号 - 一致指数を用いた多表式暗号の解読

この記事は CTF Advent Calendar 2016 - Adventar の22日目の記事です. 21日目の記事は@nolzeさんの どのCTFに出たらいいか分からない人のためのCTF年表 (2016年版) - A602 です.


多表式暗号の解読ではカシスキー・テストを用いた解読法がよく知られているが, 実はFriedman Testと呼ばれる一致指数(Index of coincidence)を用いた方法がこれとは別に存在し, (精度は劣るものの)カシスキー・テストよりも単純な計算で鍵長を推測することができる. この記事では, 一致指数を用いて多表式暗号を解読する手法をVigenere暗号に対して解説した後CTF(Capture the Flag)の暗号カテゴリの過去問題を実際に解いてみる. この記事では通して英語を平文にもつことを仮定するが, 他の言語でも同様に解読が可能である.

今回題材とする問題は 0CTF 2015: oldcrypto である.

一致指数

一致指数(Index of coincidence)とは, 通常の文字列に対して考えると2つの文字列の間の一致の割合を見る計測の手段として用いることの出来る手法である. しかし, 暗号解析の分野では2つの文字列の間ではなく1つの文字列から2つの文字をそれぞれ取ってきた時にどの程度一致するかを見るために使う. 考え方としては, ある文字列$t$とある文字$x$について, $t$の異なる位置から文字$a$, $b$を取ってきた時, $a = b = x$ を満たす割合を求めれば良い. これは$a = x$となる割合が$\frac{tに含まれるxの数}{tの長さ}$, かつ$b = x$となる割合が$\frac{tに含まれるxの数 - 1}{tの長さ - 1}$であることからこれらの積を取ることで求められる. 実際には$x$は文字全体を動く*1ので, 各$x$について総和を取ることでこれを計算する. 定義をちゃんと書き直すなら以下の通りになる.


長さ$N$の文字列$t$とアルファベット$\Omega = \{x_i\}$がある時, $t$に文字$x\in \Omega$が含まれる数を$\phi_t(x)$で表すと, 一致指数$\mathrm{IC} _ \Omega(t)$は次のように定義できる.

$$ \mathrm{IC} _ \Omega (t) := \frac{1}{N(N-1)} \sum_{x \in \Omega} \phi_t(x)(\phi_t(x) - 1) $$


実際にはアルファベットの長さ$|\Omega|$をかけて正規化したりもするが, この記事では正規化はしない.

暗号解読への応用 - シーザー暗号

一致指数の定義は示したが, どう応用されるのかは見当が付かない. なので, まずはシンプルなシーザー暗号について考える.

シーザー暗号は, 鍵文字を1文字決め, その文字を0-indexな数値にした数だけ平文をずらすことで暗号化している. 例えば, 鍵文字をCとし, HELLOWORLDを暗号化する時を考えると, 鍵文字Cは0-indexで2番目の文字なので

H -> J
E -> G
L -> N
O -> Q
W -> Y
R -> T
D -> F

とずらせる. すると, 暗号文はJGNNQYQTNFであることが分かる. ここで重要なのは, 暗号文は常に平文の同じ文字は同じ文字へ動くということで, このことは文字列の頻度解析による解読法の考案に至っている. 頻度解析はここでは扱わないが, 文字通り文字の分布を調べてその分布に従って鍵を推測していく手法だ.

シーザー暗号を解読するために, まずは一般的な平文の一致指数を考える. 自然言語の場合文字分布がある程度偏っている(英語ではeが一番高頻度で出現する等)ことから, その一致指数の値は計算可能であると言える.

英語の頻度表を利用してこの一致指数の値を求めてみる. 文字列の長さは$\infty$とするのが理想だが, 大きな値(ここでは65537)で代用する.

これを動かすと, 0.0661051931653という値が得られる. つまり, 平均的な英語の文字列の一致指数は約0.0661だと言える.

これを利用してシーザー暗号を解いてみる. 考え方としてはある文字$x$を鍵を仮定し, 実際にその鍵で解読した際にその解読文について「1文字目を英語の頻度表から取ってきて, 2文字目を解読文から取ってきたと仮定した」一致指数を計算し, これと標準的な一致指数0.0661との差の絶対値を求める. この差の絶対値が一番小さなものが鍵だと推測できる.

少しわかりづらい説明になってしまったので, プログラムコードを先に示す. サンプルとして, Lady Chatterly's Lover: History of English - van Gelderenのテキストを利用させて頂いた.

このスクリプトは動かすと実際に鍵sを出力し, 平文へと解読ができる.

キモとなるのは,

  table += [abs(0.0661 - sum(map(lambda x: (x[0]-1)*x[1][1] / (len(tmp) - 1), zip(count_alphabet(tmp, alphabet), sorted_freq))))]

の行だ. これはまさに『解読文について「1文字目を英語の頻度表から取ってきて, 2文字目を解読文から取ってきたと仮定した」一致指数を計算し, これと標準的な一致指数0.0661との差の絶対値を求める』という記述をそのまま実装したものだと言える.

一致指数のシグマの中は$\frac{\phi_t(x)}{N} \frac{\phi_t(x) - 1}{N-1}$と書くこともできることから, $\frac{\phi_t(x)}{N}$を英語の頻度表(つまり, 理想的な(平文に一番近いような)値)から直接代入した上で$\frac{\phi_t(x)-1}{N-1}$を解読文から計算し, これを全ての$x$について計算して総和を取ることで「1文字目を英語の頻度表から取ってきて, 2文字目を解読文から取ってきたと仮定した」一致指数を計算している. これは解読文の頻度が平文と言える値になると0.0661に近くなることから, 差の絶対値の中で最小値を取った鍵が実際の鍵だという推測ができる.

暗号解読への応用 - Vigenere暗号

多表式暗号では, まずシーザー暗号では使えた頻度解析が原則的に使えない. なぜなら, 平文と暗号文の文字は一対一ではないため, 頻度解析を行っても平文と同じ頻度表には成り得ないためだ. これを一致指数を用いて考えると, 鍵長$k$の多表式暗号によって暗号化された暗号文$t$から2つ文字を持ってきた時にこの文字が文字$t$と一致する割合は, 鍵長$k - 1$の時よりも低くなる. なぜなら, 平文と暗号文の文字が一対一ではなく一対$k$の対応になることからランダムネスが上がるため, 全体としての一致の割合が低くなるからだ. 逆に考えれば, 多表式暗号の場合、一致指数はその「鍵の長さ」によって変わるとも言えることが分かる. つまり, 文字列全体の一致指数を取ることで鍵長をある程度推測できると言えるのではないか?と考えられる. これがFriedman Testと呼ばれる鍵長推測の手法である.

以下のスクリプトを用いて実際に実験してみる. サンプルテキストは, 上で用いたものと同じものを使う.

このスクリプトは, 鍵の長さごとにランダムな鍵でVigenere暗号を用いて暗号化し, その一致指数の平均値を算出して表示する. 実行結果は以下のようになる.

[+] Key length = 1, IC = 0.0653856
[+] Key length = 2, IC = 0.0510465
[+] Key length = 3, IC = 0.0466506
[+] Key length = 4, IC = 0.04432
[+] Key length = 5, IC = 0.0433219
[+] Key length = 6, IC = 0.0418646
[+] Key length = 7, IC = 0.0413971
[+] Key length = 8, IC = 0.040794
[+] Key length = 9, IC = 0.0403788
[+] Key length = 10, IC = 0.0402034
[+] Key length = 11, IC = 0.0398683
[+] Key length = 12, IC = 0.0396422
[+] Key length = 13, IC = 0.0394859
[+] Key length = 14, IC = 0.0393217
[+] Key length = 15, IC = 0.0392352
[+] Key length = 16, IC = 0.0390873
[+] Key length = 17, IC = 0.039084
[+] Key length = 18, IC = 0.0389093
[+] Key length = 19, IC = 0.038822
[+] Key length = 20, IC = 0.0387942
[+] Key length = 21, IC = 0.0387419
[+] Key length = 22, IC = 0.0386404
[+] Key length = 23, IC = 0.0386087
[+] Key length = 24, IC = 0.0385671
[+] Key length = 25, IC = 0.0384884

鍵長1の時は最初に計算した0.0661に近く, 鍵長毎に差があるのは確かに見て取れる. *2 これを利用して鍵長を推測してみる. 平文は先と同じものを使い, 鍵長3, 5, 7のそれぞれで一致指数を計算し, 一番近い鍵長の一致指数を求めることで鍵長を推測する.

何度か動かすと分かるが, 誤差が$\pm 1$〜$2$ほど存在する. うまく行けば,

[+] K = oau (3)
[+] Guessed key length = 3
[+] K = imryu (5)
[+] Guessed key length = 5
[+] K = qzomygn (7)
[+] Guessed key length = 7

のように綺麗に判定してくれるが,

[+] K = jeg (3)
[+] Guessed key length = 5
[+] K = abfsn (5)
[+] Guessed key length = 6
[+] K = vsbgyqd (7)
[+] Guessed key length = 9

のようにずれることもある. こればかりは鍵長が長くなれば長くなるほど誤差も大きくなるため比較手法について考えるか誤差を大きく判定するしか無いだろう. しかし, こうやって鍵長の候補が求まれば, シーザー暗号と同じように一致指数から平文に一番近い解読文を導出できる. 最終的な解読文の中でも一番一致指数が鍵長1の時の一致指数に近いものが平文に近いと言えるので, 判定も容易そうに思える. 実際, カシスキー・テストでは鍵長の倍数が求まることがあり, この倍数から鍵長を導出するには因数分解しなければならないので, こちらのほうが自動化をしやすいと言える*3.

それも含めて, 上のコードに解読部分のコードを付け加えたものが以下になる. このコードは実質的に任意のVigenere暗号文を解読することのできるコードになっている.

暗号解読への応用 - CTF過去問題

ここでは冒頭に言ったようにCTFの過去問題を一致指数を用いて解く. 問題は0CTF 2015 - oldcryptoを使う. この問題はタイトルからして古典暗号, 配布されている問題ファイルの中身はというと暗号化用スクリプトと暗号文のみというシンプルなもの. 暗号化・復号関数を以下に抜粋する.

def encrypt(plaintext, key):
    ciphertext = ""
    for i in xrange(len(plaintext)):
        p = ord(plaintext[i]) - ord('a')
        k = ord(key[i % len(key)]) - ord('a')
        c = (tr[k][p] + i**7) % 26
        ciphertext += chr(c + ord('a'))
    return ciphertext

def decrypt(ciphertext, key):
    plaintext = ""
    for i in xrange(len(ciphertext)):
        c = ord(ciphertext[i]) - ord('a')
        k = ord(key[i % len(key)]) - ord('a')
        p = tr[k][(c - i**7) % 26]
        plaintext += chr(p + ord('a'))
    return plaintext

tr はファイル中に定義されている変換テーブル. 簡単に暗号化処理をわかりやすく書き直すと,

import string

def encrypt(plaintext, key):
  ciphertext = ""
  keylen = len(key)
  alphabet = string.lowercase
  plaintext = map(lambda x: alphabet.index(x), plaintext)
  key = map(lambda x: alphabet.index(x), key)
  for i in xrange(len(plaintext)):
    k = key[i % keylen]
    p = plaintext[i]
    c = (tr[k][p] + i**7) % 26
    ciphertext += alphabet[c]
  return ciphertext

i**7 は暗号文から簡単に取り除ける上本質的ではないのでこれを取り除く. すると,

import string

def encrypt_without_i7(plaintext, key):
  ciphertext = ""
  keylen = len(key)
  alphabet = string.lowercase
  plaintext = map(lambda x: alphabet.index(x), plaintext)
  key = map(lambda x: alphabet.index(x), key)
  for i in xrange(len(plaintext)):
    k = key[i % keylen]
    p = plaintext[i]
    c = tr[k][p]
    ciphertext += alphabet[c]
  return ciphertext

これは典型的な多表式暗号である. よって, 先の一致指数を用いたVigenere暗号と同じ議論で鍵長を求め, 鍵を導出することができる. これらを踏まえてコードに起こすと, 次のようになる.

しかし, この暗号文は鍵長が長いためか誤差が大きく, $\pm 2$の誤差では解読ができなかった. そのため, 鍵長を導出できた10から今回計算している25まで全て候補に探索してやることで鍵が導出できた. 具体的には132行目の

for L in xrange(guessed_len - 2, guessed_len + 3):

for L in xrange(guessed_len - 2, guessed_len + 26):

と書き換える.

> python oldcrypto.py 
[+] Guessed key length = 10 +- 2
skumsnui
snucgshin
iphssisfun
qniqnllggsz
sdussncgscum
gninihcwnsnni
nnwdqiqnunlgxg
ipasniyaunicanl
slkmswumscunsnks
ucnsginhnhinscvzn
snicqnaqknnucgqgis
kishnsniignnqgdwlsg
classicalcipherisfun
hincgiznlgsichunqygzk
qnsdqmsikntinfhindgnin
zazuumqukdlznrzwcgvgiiu
slumsncwncumcniihicgszuv
igankiphnuiuausiyaunilaun
kvxnulcwtslnigaiuiioanurhd
nnucflhiignlgwjgisiniigmcsl
ncgmhnqnnnussknnhdwmsruilguz
lkipitcisirsswglskngdrvngqqqq
cphsrisfucilaisisfuniyhvsicgun
kiwjawqlbjlsznmqcnfnuahhnvionuq
slkmquqinnunsukinokishumscusznis
cogginsnicfqnhlnlsgzlzgnscuglwnso
qwgssilllhspangnnmghniinhdlgnmkvwu
ikaunisauniuzznighsiiraizipannilaes
[+] Guessed Key = classicalcipherisfun
[+] plaintext = incryptanalysiskasiskiexaminationisamethodofattackingpolyalphabeticsubstitutioncipherssuchasthevigenerecipherinpolyalphabeticsubstitutioncipherswherethesubstitutionalphabetsarechosenbytheuseofakeywordthekasiskiexaminationallowsacryptanalysttodeducethelengthofthekeywordusedinthepolyalphabeticsubstitutioncipheroncethelengthofthekeywordisdiscoveredthecryptanalystlinesuptheciphertextinncolumnswherenisthelengthofthekeywordtheneachcolumncanbetreatedastheciphertextofamonoalphabeticsubstitutioncipherassucheachcolumncanbeattackedwithfrequencyanalysisthekasiskiexaminationinvolveslookingforstringsofcharactersthatarerepeatedintheciphertextthestringsshouldbethreecharacterslongormorefortheexaminationtobesuccessfulthenthedistancesbetweenconsecutiveoccurrencesofthestringsarelikelytobemultiplesofthelengthofthekeywordthusfindingmorerepeatedstringsnarrowsdownthepossiblelengthsofthekeywordsincewecantakethegreatestcommondivisorofallthedistancesthereasonthistestworksisthatifarepeatedstringoccursintheplaintextandthedistancebetweencorrespondingcharactersisamultipleofthekeywordlengththekeywordletterswilllineupinthesamewaywithbothoccurrencesofthestringthedifficultyofusingthekasiskiexaminationliesinfindingrepeatedstringsthisisaveryhardtasktoperformmanuallybutcomputerscanmakeitmucheasierhowevercareisstillrequiredsincesomerepeatedstringsmayjustbecoincidencesothatsomeoftherepeatdistancesaremisleadingthecryptanalysthastoruleoutthecoincidencestofindthecorrectlengththenofcoursethemonoalphabeticciphertextsthatresultmustbecryptanalyzedoooooooooooooooooooopsflagisthekeywithoopsprefixandbraces

flagisthekeywithoopsprefixandbraces とあるように, 鍵の前後に 0ctf{ } を付けたものがフラグになる.

よって, 最終的なフラグは 0ctf{classicalcipherisfun} である.

まとめ

一度計算すれば大方の予測がついてしまうため, 一致指数を用いるFriedman Testはカシスキー・テストよりも扱いやすい. しかし, その分誤差も大きく, その意味ではカシスキー・テストのように鍵長の倍数がすぐに出てくるものよりは劣る. 実際に解読するツールにするには, これらを組み合わせて誤差を吸収するような仕組みを作るほうが良いだろう. 一致指数自体は一般に2つの文字列の差とも言えることから, ある程度の平文がわかっている換字式の自動解読コードを書く時には利用できるかも知れない. テクニックとして覚えておくことに損はないので, 是非とも覚えて使ってもらいたい.

参考文献


明日は@hama7230氏によるcamp ctfのwriteupです.

*1:例えばこの記事では英語を扱うのでアルファベットが文字全体となる. 以降, アルファベットという単語で文字全体を表す.

*2:これは実は$k$についての極限値を求めることができて, 鍵長が∞(いわゆる「ワンタイムパッド」の時)は全ての文字が全ての文字へ写される可能性があると言えて, 一致指数は各文字毎に$(\frac{1}{26}) ^ 2$で, この総和は$\frac{1}{26} = 0.0384615384615385$となる

*3:無論, 両方を実装すればより精度の高い導出が可能である.