あけましておめでとうございます
あけましておめでとうございます。
生きております。
記事を書くのも約3ヶ月振りです。
昨年の振り返りを途中まで書き出していたのですが、
だるくなったのでやめました。自分らしいです。
そして今年です。
冬コミを落とす（記事書く時間がなかった）結果になったので、
夏コミに向けて、日常生活をハックしつつ時間を作り、
その時間を夏コミの同人誌制作にあてていきます。
時間がなかった、というのは言い訳だよねーとは自分でも思っています。
例えば通勤時の電車で座れる時間帯の電車に乗り、
パソコン開いて記事書くとか、時間を作り出すことは可能でした。
ということで、今から夏コミに向けて動いていきます。
先に夏コミのネタを投下しておきますと、
・ファミコンエミュ作成
の予定しております。
キー配列を変更
お久しぶりです、生きてます。
もう一ヶ月経ちますが、先月から脱ニートして社会人になりました。
楽しい日々を送っています。
情弱キャラが板についてきましたよ（どやぁ
んで、キー配列を変更した話を少し。
仕事ではPerlでプログラミングしているんですけど、
Perlでプログラミングするのは好きじゃなかったです。
理由：$が打ちにくい。
変数を記述する度に手が止まるのがストレスだったんですね。
左手でShiftを小指で押しつつ中指で$を打つ手の状態は、
どうしてもタイピングが一時的に止まってしまう形でした。
そこでキー配列の変更ですよ！
自分にはそんな発想はなかったんですが、触発されたのがこれです。
「キーボードをいじろう！」 by @handlename
http://www.slideshare.net/handlename/yapcasia-ltthon
決してdvorakにしたわけではなくてｗ、数字と記号を入れ替えてみました。
入れ替えてみて、最近は違和感なくなってきたなぁと感じたので、その感想です。
1. Perlで$を打つときに一時的に止まらない
単純にShiftを押す必要がなくなり、打ちやすくなったからですね
2. for構文が打ちやすい
例えばこれ、Shiftを押すのが3回しかないです
for($i = 0; $i<1000; ++$i)
^ ^ ^あと、プログラミングにおいては数字を打つより記号を打つことが多いわけですから、
単純にShiftを押す回数が減りますね。
思い切ってキー配列を変更して良かったです。
Perlプログラミングも快適、というお話でした。
身内ハッカソン
ここ数実は身内ハッカソンに参加していました。
3泊4日、ほぼ3日間のハッカソンになります。
各自自由にテーマを取り組むという、完全にソロプレイ。
自分はファミコンのエミュ作成にチャレンジすることにしました。
普段ソフトウェアばっかりなので、ハードウェアとの関係を思い出したくなったのですｗ。
初日：
大量のレッドブル。
翼を授けてくれるようですが、今回ばかりは死に近づくアイテムです。
まずは、資料集めから始めました。
そして、ひたすら資料を読む作業（白目）
グラフィック周辺処理がいくら読んでもよくわからない…
とにかく、グラフィック周辺の処理の完成を目処にして進めることにしました。
エミュ作成の流れを確認して、資料を眺めながら初日終了。
2日目：
仕様書の意味がわからない（困惑
わかるところだけをとにかく実装、GUIとしての出力はXlibを利用することに。
夜にはなんとか HELLO, WORLD! を出力するところまで進む！
ここが最高潮ｗ
3日目：
仕様書の意味がわからない（涙目
NESのサンプルROMを拾ってきて、動かしながらデバッグを行う。
バグのいくつかを闇に葬った。
Les's PIZA
ノリでピザを頼んではいけない、後の祭りだった（半分余ったｗ
4日目
仕様書の意味がわからない（怒り
気付いたらハッカソン終了してた☆
実装できたのは、CPUの各命令と、グラフィック周辺（未実装多し）
クロック数調整、割り込み、音声までは手が回りませんでした。
ほとんどの時間を仕様書に費やす…が、あまり成果なし。
そして待ちに待った各自発表タイム。
みんなすごかったｗ
楽しい4日間を過ごしました。
暇なときにエミュ作成の続きをしたいと思います。
ksnctfに取り組んだ話
ここ最近、ksnctfというものをやっていました。
主にコンピュータセキュリティに関する問題が出題され、FLAGをゲットする遊びです。
現時点(全21問)では全問正解しましたので、私なりにヒントを書きます。
書こうと思ったのは、勉強になるので是非やってみてほしいと考えたからです。
はじめに、CTFを知らない人もいると思いますので、軽く説明です。
CTFについて
CTFとは、世界各地で開催されている著名な旗取り合戦競技（Capture The Flag）のことで、セキュリティ技術を競うコンテストの総称です。クイズ形式の問題の謎を解いたり、実験ネットワーク内で疑似的な攻防戦を行ったりします。クイズ形式の場合、出題ジャンルは、暗号、バイナリ、ネットワーク、Web、プログラミングなど多岐に渡り、セキュリティのみでなくプログラミングに関する知見も問われ、攻撃技術、防御技術、解析技術、暗号の知見、ネットワーク技術など、広範な知識と経験が必要となっています。CTFはIT技術に関する総合的な問題解決力を磨くうえで最適な競技と言えるでしょう。
http://www.seccon.jp/p/ctf.html
日本でも今年からSECCON（SECurity CONtest）というのができました。
定期的にCTFも開催する様子ですので、興味のある方は参加されてはいかがでしょうか。
ksnctfについて
http://ksnctf.sweetduet.info/
まずは、感想を述べたいと思います。
出題された問題はいずれも素晴らしいと感じました。
私から見て（CTF初心者）、
・ぐぐればなんとかなる（難易度設定が良い
・勉強になるような題材
の2点です。
ストレートで解けた問題は多くなくて、本当にだいたいぐぐってます。
全体を通して、多少の予備知識（ぐぐるためのキーワードに心当たりがある程度）と、
気合があれば解けるんじゃないでしょうか。（予備知識の程度は人によりますが…）。
楽しい時間を提供してくれた作成者であるkusano_kさんにこの場をお借りして感謝を。
個人的に いいね！ と思ったのは、
4: Villager A
6: Login
9: Digest is secure!
13: Proverb
21: Perfect cipher
これら5つの問題を挙げたい。いずれも勉強になりました。
下記から各問題のヒント？になります。※反転させてください
中にはヒントになっていないものもありますがご容赦ください。
もう少しヒント欲しいという方はコメントか、もしくはTwitterとかで。
1: Test Problem
hint1: やるだけ
2: Easy Cipher
hint1: 古典暗号
3: Crawling Chaos
hint1: javascriptのデバッグツールを使う,あとは気合
4: Villager A
hint1: フォーマットストリング攻撃
hint2: GOT overwrite
5: Onion
hint1: base64
hint2: fileコマンド便利だよね
6: Login
hint1: ' OR 1=1--
hint2: Blind SQL Injection, データベースによって関数が異なるよ
7: Programming
hint1: whitespace,あとは気合
8: Basic is secure?
hint1: BASIC認証
9: Digest is secure!
hint1: Digest認証の仕組みを知っていますか？
10: #!
hint1: んあー
11: Riddle
hint1: リバースエンジニアリングだから気合です
12: Hypertext Preprocessor
hint1: 関係ない数値がありますよね, 2012-1823
13: Proverb
hint1: シンボリックリンク
14: John
hint1: john the ripper
hint2: 2chでよくある読み方
15: Jewel
hint1: apk -> jar, がんばって読む
16: Math I
hint1: RSA暗号
17: Math II
hint1: 超える値と超えない値で二分探索しました
18: USB flash drive
hint1: forensic問題, autopsy, FTK Imager etc
19: ZIP de kure
hint1: pkcrack
20: G00913
hint1: G00913ってGoogleで調べろってことです
21: Perfect cipher
hint1: XORの性質
hint2: メルセンヌツイスターの擬似乱数生成は条件が揃うと予測可, XORShiftは逆算可能
XORShiftの逆算
XORShiftされた値を逆算する機会がありましたのでメモ書きです。
y = x ^ (x << t) のとき、y ,t が分かってるとして、xを求めたい。 x << t の値は下位t桁は必ず0になっているから、 y & ((1 << t) - 1) と x & ((1 << t) - 1) は等しい。 また、x << tの t桁 ~ 2*t - 1桁目も y & ((1 << t) - 1) と等しい。 今回は x = 22, t = 3 を例として下記に示す。 x = 000010110 x << 3 = 010110000 y = 010100110 y & ((1 << 3) - 1) = ______110 x & ((1 << 3) - 1) = ______110 x << 3 の 3桁 ~ 5桁目 = ___110___ この時点で判明してるのは、y と x << t の 0桁 ~ 2*t - 1桁目までである。 x << t の判明してる部分をzと置く。XORの性質を利用すると、 z = ___110000 y = 010100110 x' = z ^ y = ___010110 よって、x の t桁 ~ 2*t - 1桁目が新たに得られた。 x' << 3 = 010110000 z' = 010110000 ; x << tの判明している部分 y = 010100110 x'' = z' ^ y = 000010110 これでxの全ての桁が復元できた。 右シフトのXORShiftもほぼ同様の処理で逆算可能である。 ただし、右シフトは算術シフトか論理シフトで値が異なる点に注意。 ちなみに、C言語の右シフトは算術シフトか論理シフトかは処理系依存。 gccではsignedでは算術シフト、unsignedでは論理シフトになる。
sample code（左シフト）
#include <stdio.h> // 1 <= t <= 31 unsigned int decodeXORLeftShift(unsigned int y, int t){ unsigned int x; unsigned int z = (y & ((1U << t) - 1)) << t; unsigned int mask = ((1U << t) - 1) << t; while( mask ){ x = z ^ y; z = z | ((x & mask) << t); mask <<= t; } return x; } unsigned int encodeXORLeftShift(unsigned int x, int t){ return x ^ (x << t); } int check(){ int i; unsigned int j; for(i=1; i<32; i++){ for(j=0; j<10000; j++){ if( j != decodeXORLeftShift(encodeXORLeftShift(j,i), i) ){ return 0; } } } return 1; } int main(){ puts(check() ? "OK" : "NO"); return 0; }
実行結果 OK
AOJ.1178 A Broken Door
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1178&lang=jp
35msまで高速化頑張ってました。
現在1位の29msに届かなかったのが残念です。
解法はいくつかあるようですが、BFS+ダイクストラで解きました。
入口から出口までの1つの経路を考えたとき、通過するドアのうちで故障していたら最も困るケース（必要になるカード枚数が一番多い）が、その経路におけるコストになります。
どのドアが故障しているかは事前にわからないので、部屋から部屋へ移動するときに、そのドアが故障していた場合のカード使用枚数を調べる必要があります。
これは、ある部屋(x,y)から方向dirのドアが故障していた場合として、出口までの最小のカード使用枚数をBFSで計算します。
それから、入口からある部屋までの経路のうちで、もしドアが故障していた場合における入口から出口までのコストで最悪のものをworststepとし、これをダイクストラにおける比較コストにします。
見落としとしては、ある部屋(x,y)において2つの状態を考えます。
状態i : 現在のカード使用数 = a、worststep = bとします
状態j : 現在のカード使用数 = c、worststep = dとします
このとき、worststepだけで比較を行うと間違った答えになる場合があります。
仮に b < d でも、a > c の場合、状態jのほうが後になって最適解を出す場合があります。
ですので、この場合はどちらも最適解を導く可能性があるので、両方とも状態を保持する必要があります。
にしても、1位速いなぁ…。
