CS とかよくわからんのでミーハー魂をくすぐるものを読んだふりをする
How to break MD5 and other hash functions (Xiaoyun Wang and Hongbo Yu)
前置き
MD5 のコリジョン生成方法が発見された時の話。
彼女が研究を始めてから15年ほど経っていた。既にこの内容は中国国内では発表済みだが世界には知られていない。スイスから上海に戻ったIDEA設計者のXuejia Laiが中国国内でしか知られていない、この研究を知った。Laiは思った。「これは偉業だ。世界は、このことを一刻も早く知るべきだ」。急遽英文の論文にしたてあげ、投稿。しかし論文としては質が低いので落選。それでハッシュのコリジョンを示すという内容でePrintにサブミット。つたない英語。big endianとlittle endianを間違えて論文に載せるという初歩的なミス。しかし、たとえ方法論が無視されていても、ハッシュがコリジョンを見つけたという事実は無視できない。
この辺から、「風の～なかの～す～ばる～」のBGMがかかりつつ、なぜビザが必要なアメリカへすぐに出発することできたのか、最後の拍手の鳴り止まない感動のフィナーレまで、色々な謎と物語が展開しつつ話は続くわけですが、それはまたどこかで。
abstract
The best known result so far was a semi free-start collision: 好きな値で hash の計算を開始できる攻撃はあった? 最初からよくわからんな…
コリジョンを 15 分から 1 時間でお手軽に。
今回の攻撃は differential attack で、一般的な攻撃というのは xor を a measure of difference として使うけど、今回のは modular integer subtraction を使うよ。
1. intro
MD5(M0+M1)==MD5(M0'+M1') となる (M0,M0') を 2^39 回程度の MD5 operation で、 (M1,M1') を 2^32 回程度の MD5 operation で求められるんですよ。
あ、たぶん M0 とか M1 とか M0' とか M1' とかは MD5 の 1ブロックなんで 512bit のデータ。
2. description of MD5
そういや MD5 って書いたことないな…
ぱっと見 SHA の scheduling (って言うんだっけ?) のところでメッセージを混ぜてない気がする。オペレーションの詳細は全くわからんが、 MD5 は w[16] を 64 回のループで同じところをヘンな順番で 4 回ずつ読む感じだけど、 SHA 一族だと 16 回読んだ後の 48 回は今までの 16 個のうち 4 つをぐにょぐにょ混ぜたものを使って w[64] を構成するみたいな。
3. Differential Attack for Hash Functions
差分をどう使うのかよくわからんけど、 XOR 差分だけじゃなくて引き算の差分情報もあるともっと詳しいことがわかりますよ。例えば引き算差分が X'-X=2^3==8==0b1000 になる時、 XOR 差分は 0b1000, 0b11000, 0b111000, ... なんかの可能性があって、かつ 0b11000 以降の場合は X と X' に条件がつく。
ハッシュってのは差分がΔH_k=ΔH(...ΔH(ΔH(ΔH_0,M0,M0'),M1,M1')...,M_k-1,M'_k-1) とつもってくもんで、ΔH_k がもし 0 ならそれがコリジョン。
なんか知らんがうまいこと衝突の可能性が高いメッセージのいじりかたをするんだぜ、と。
4. Differential Attack on MD5
こっから本題…だが MD5 のアルゴリズムが全く頭に入ってないのでつらい。
衝突の確率を高くするために、いくつかの変数を特定の値のどれかに固定するようメッセージのいじりかたをするらしい。
その条件を満たすにはこういういじりかたをすればええよ…みたいな感じ? 最終的にそのいじり方をすればたかだか 2^37+2^30 の空間を探索すれば見つかるよん…と。
感想
よくわからん。特に最初の integer subtraction がどうこうと、 MD5 の変数を固定するための条件の関係みたいなのがわからん。なんとなく雰囲気を妄想でおぎなうくらいはできるけど、言語化できない。
ちなみにこの人はその後 SHA-1 についても考えはじめて、 brute force だと 2^80 必要な SHA-1 を 2^63 に落としたらしい。その後他の人が 2^52 だというのを論文にしたけど、なんかおかしいってことで取り下げたとのこと。
ていうか読んだフリにしては時間かけすぎた
ちなみに僕の興味というのは MD5 やらなんやらで Quine や、ループ (e.g., M=MD5(MD5(M))) を作れるか…っていうどうでもいいことなのであった。
Conjugate coding (Stephen Wiesner)
前置き
量子鍵配送は量子情報の神、 Charles H. Bennett (量子鍵配送も量子テレポーテーションも superdense coding もあれもれこれもこの人みたいなひどい人) が発見した…と思ってたけど、 BB84 の 14 年前、 1970 には既に発見していたらしい。
Bennett の BB84 には Wiesner の論文も cite してあるし、 superdense coding も Wiesner との joint work ぽいし、はてどんな感じなんやろね…
ところで量子鍵配送は量子情報の世界では唯一実用的なのではないかという感が漂っている物体で、正直量子コンピュータとか30年(この数字は適当な僕のフィーリングです)とかいうスパンでも実用的にはならんのじゃないかなーとかいう感じなのに対して、量子鍵配送は普通に実験とかされてて、需要さえあれば実用化が可能な雰囲気をただよわせている。問題はライバルである RSA が十分に実用的すぎることで、 RSA を倒すには量子コンピュータが必要で…ということで困った! 予算が取れない!! とかいう感じになってると予想される。
量子鍵配送が量子コンピュータとかと違って実用性が高いのは entanglement を使わない点が大きい、はず。
BB84 の復習
何度読んでも忘れるものの一つ。似たようなものとして日本酒の製法などがよく知られている。
量子ビットとは…! |0> と |1> だけだと古典ビットなわけだけど、なんか中途半端な |0>+|1> とか |0>-|1> とかを取れるファンキーな物体。何故そんなものが存在するかという質問に答えられる人は存在しない。世界がそうなってるらしいからしょうがない。社会が悪い。
一般的には cos(θ)|0>+sin(θ)|1> の円みたいな感じだと思えばいい。本当は複素球面だけど、 BB84 ではそもそも |0>, |1|, (|0>+|1>)/sqrt(2), (|0>-|1>)/sqrt(2) しか使わんからどうでも良い。以下 sqrt(2) とかめどいので省略する。
量子ビットを古典的な情報に落とす時は観測をする。例えば |0> か |1> かを判定する観測を |0> に対して行なうと「これは |0> である！」という結果が 100% 得られる。問題は |0>+|1> に対して行なった時で、この場合は「これは |0> である！」という結果と「これは |1> である！」という結果が 50% ずつの確率で起きる。つまりなんの情報も得られないと言える。
また、 |0>+|1> か |0>-|1> かを判定する観測なんてのもできる。これは |0>+|1> か |0>-|1> の判定には 100% の精度で使えるが、 |0> と |1> に対してこの判定をすると、 50% ずつの確率で |0>+|1> か |0>-|1> がかえってくる。
さらに、この観測の後には、観測前の量子ビットというのは残っていなくて、観測結果の量子ビットが残る。つまり |0>+|1> を |0> か |1> を判定する方法で判定すると、結果の状態は |0> か |1> になってしまって、元の状態 |0>+|1> は残らない。この、観測した時に状態が変わちゃってる、ってのはキモの一つ。このへんも再度、全く直感に反してるんだけど、これも社会が悪いという以上の説明をできる人はいない、量子力学の原理の一つ。
ついでに言うと量子ビットはコピーすることもできない。コピーできたら2つコピー作って違う2種類の観測すれば |0>, |1>, |0>+|1>, |0>-|1> のどれかを特定する観測ができるんだけどね…
という前提で BB84 。 N ビットの鍵を共有したいとする。 Alice はランダムに 5N ビットくらいの鍵を作る。これを K としよう。 K を Bob に遅るんだけど、この時 |0>, |1> か |0>+|1|, |0>-|1> を使って、量子経路で送る。 |0>, |1> を使ったか |0>+|1|, |0>-|1> を使ったかは覚えておく。この記憶を A とする。
さて Bob は、受け取った 5N ビットの量子ビットを、フィーリングで |0>, |1> か |0>+|1|, |0>-|1> を使って観測する。当然そのフィーリングも記憶しておく。この記憶を B としておく。
Alice は A を古典経路で公開する。
Bob は A と B が一致してないビットを捨てる。元々 5N ビットあったので、 2N ビット程度くらいはたぶん残るだろう…残らなかったらやりなおし。
2N ビット中 N ビットを使って、 Alice と Bob は答えあわせをする。答えがあってなければ、 Eve が盗聴したと考えていい。やりなおし。
Alice が Bob に量子経路で送った情報を Eve が見れたとして、この段階では Alice が |0>, |1> と |0>+|1>, |0>-|1> のどっちでエンコードしたかわからんので、 Eve はカンでどっちかの観測をすることになる。この時 Alice のエンコードと一致した方法で観測すれば問題ないのだけど、一致してない場合 (これは 1/2 の確率で起きる)、状態を変えてしまうことになる。状態を変えてしまった場合、 Bob の観測は 1/2 の確率で Alice のエンコードと逆の結果を返す。 Eve の盗聴が二人の確認作業に悪影響をおよぼさない確率 (3/4)^N は N が大きければほとんどありえない。
内容
これは…なんか、 BB84 そのまんまだ。差分は暗号の鍵配送に使える、ってことを言ってないことくらい。
かわりの応用として、これ使うと偽造不能な量子マネーを作ることができるとか、2つの文章のうち片方しか読めませんよーという文章を送ることができる(全く用途が不明である)、とか言ってる。
鍵配送に使えると言ってれば良かったのだろうけど…惜しい。しかしこの論文は RSA より以前だから無理に決まってるのであったー
LZMA
前置き
LZMA は 7-zip の作者、 Igor Pavlov の自己申告によると 1996 年から開発していて、 1999 年に発表された 7-zip に 2001 年から使われはじめたアルゴリズム、らしい。
長い間使われてる上にオープンソースなのにも関わらず、論文とか説明がどこにも無い謎のアルゴリズムだった、らしい。ほんまかいな。
そんなわけで論文が無いのでこのへんを読んだ。
内容
よくわからん。前者は色々書いてあるんだけど、後者に簡潔にまとめてある以上のことがよくわからんかった。
話としては、
- 単に一番長いマッチを探すんじゃなくて、今回のマッチが短くても次のマッチが長くなるなら OK みたいな先読みをしてるよ
- マッチした後に現れたマッチできなかったリテラルは特殊な子なので、前回マッチの先頭と xor 取って省スペース(直感的にはそんなもんかなあと思うけど…?)
- 最近マッチできたかとかに応じて state マシンが動いて、その state 次第で挙動を変えることによって構造化されたデータに強い
とかそういう話らしい。
Non-Orthodox Combinatorial Models Based on Discordant Structures (Romanov V. F.)
kinaba さんの P NP リンクにあったので、全く読んでないけど、これは結局どういう結末を向かえたのだろうか…とちょっと前にぐぐったので書いておく。結論を書いておくとどういう結末を向かえたかは不明。
まずこのブログポストがよくわからない。
主要な登場人物は二人、 Romanov と Dmitry 。このブログのサブドメインは Romanov から取ってると思われるが、このブログポストは Dmitry が投稿したとシステムは言っていて、しかしこのブログポストの末尾には Romanov の署名がある。このブログのコメントに答えているのは基本 Dmitry 。 Romanov は一度だけコメントをしていて、そのコメントでは "Thank you for your attention to my work." とか言っている。あとこのブログは2つしかポストが無いのだけど、もう一つの方は Yury という人によってなされている。
全く意味がわからんが、つまりたぶん Dmitry による Romanov ファンサイトなんじゃないかと思う。それにしても色々不思議だが。まあきっとこれがロシア式なのよ。
で、結論としては間違ってるか間違ってないかとかはよくわからんかったのだけど(ミーハーなので論文の中身は全く読まずに批判を探していただけ)、二種類の批判を見た。
このデータに対しておかしな結果返してるよパターン。これに対しては dmitry が、「あ、それは実装のバグだわ、ごめん」みたいな返事をしてた。「github でもう修正しといたよん」とか言ってるの見ると新時代ですね…!
2つ目。論文によると、
- HSS というのが作れなかった場合は not satisfiable
- HSS っての作れて、かつ充足させる変数の組み合わせが出てきた場合は satisfiable
- HSS ってのが作れたけど、充足させる変数の組み合わせがわかってない場合は、分類失敗!
最後のが起きたらヤバいんだけど、 410000 のデータで実験してみて全部成功したから大丈夫なんじゃね? とか論文には書いてある感じで、たぶん3つ目のケースが起きないことは証明せずにそのままシメに入っている。
あと、ブログへの Romanov の唯一のコメントでは、論文に間違いあったからお前の作業止めた方がいいかも…とか言っていたりもする。
まとめると、色々とうさんくさいことこの上ないんだけど、しかし実装があるというのはなんか魅力的ですよね…みたいな。
We crashed, Now What? (Cristiano Giuffrida)
前置き
ぐぐったら Tanenbaum のところ、という情報が出てきたのでぐぐったらそうらしい。
全然関係ないことを調べたかったんだけど、たまたま目に入った何やら楽しげなタイトルなので読もうとした…が途中で飽きてきて適当。
1. Intro
OS のリカバリってのは、汎用的だけどすっげー遅いやつか、速いんだけど ad-hoc に機能ごとに復帰コード突っ込んでいくような、実装者の負担がありえんヤツの2種類があって、どっちもありえん。 Multics 作ってた人が俺の書いたコードの半分はエラーリカバリだと言ってるらしいぜ。
2. Crash-Recovery Problem
問題の定義
3. Our approach
OS の中心を single thread な event loop にする。各サブシステムはそこ経由の IPC でやりとり。 event loop の最初の状態はまっとうなんで、そこに復帰できるようにする。どうやってやるかっつーとコードを全部 LLVM 通して、状態に書き込むところで stable だった時の状態をこっそり保存するようにしておく、と。
確実にクラッシュする stable な状態になっちゃった場合は、その後はひたすらクラッシュ→リカバリ→クラッシュ→リカバリ…のループになっちゃうんだけど、そのへんはなんとかなると思うよ。 future work でもあるし次章でも少し言う。
4. Practical Crash Recovery
飽きた
5. Current Results
MINIX 3 の上に LLVM 使って実際にやってみた。あんまマジメにやってないけどいいんじゃね？みたいな？エラーとかはあんま現実的なシナリオでやったわけじゃないけど？そのへんは TODO でよろしく。
思ったこと
MINIX と LLVM の時代を越えまくったコラボみたいな。クラクラした。
Considered Harmful
いよいよ真剣にどうでもいいものを読む
1968年。 goto とか primitive すぎるじゃん。死ね。
1987年。いや、大域脱出とかで便利じゃね…
長ったらしくて読む気起きない。先の論文のケースはこういう言語機能があればいいだけの話だけど、確かにたまに使いたいシーンはあるよね…ただ goto の mis-use の悲劇を考えると dijkstra の説は一般的なアドバイスとしては良くて…みたいな。
まとめ
偉い人が自転車小屋の議論に参加してもしょせんは自転車小屋の議論…
Optimizations in the Intel Compiler
プロファイル取っての optimization 、 vectorization や parallelization はやるらしいねーと聞いたような話。
知らなかったのは実行時に自分の CPU type を調べて、それに応じて別のコード使うようなことができて、 portability と performance を両立できている、という話。
Static Call Graph Generator for C++ using Debugging Information
デバッグ情報という文字列にひかれて読んだら聞いたことあるような話だったでござる。まぁ頑張ったねー的な話。
動的なほげほげならともかく、静的なほげほげならさすがにコンパイラとかコンパイラの内部出力とか使った方がいいんではないのかな…と思うけど、まぁお手軽感は良い話ではあると思う。
ねむい
適当に目に入ったなんとなく面白そうなものをメモっておく
Debug All Your Code: Portable Mixed-Environment Debugging
Mostly Lock-Free Malloc
最終更新：2011年03月07日 01:46
