sekai013's blog

JavaScriptとかを勉強する

paiza Online Hackathon #5 in JavaScript

paiza.jp

これやったポスト が 5問中 4問 Ruby で書いたのに ミスって JavaScript の答案として取り上げられてしまった ので反省して全部 JavaScript で解いた。

Mission #1

process.stdin.on('data', function (chunk) {
    var line = chunk.toString();
        console.log(line.split('').filter(function(val, index, array) {
            return (index % 2 === 0) ? true : false;
        }).join(''));
});

これだけもともと JavaScript で書いてた。

Mission #2

process.stdin.on('data', function (chunk) {
    var lines = chunk.toString().split('\n');

    lines.shift();

    var result = [0,0,0,0,0,0,0];

    lines.forEach(function(value, index) {
        result[index % 7] += +value;
    });

    for(var i = 0; i < result.length; i++) {
        console.log(result[i]);
    }
});

Mission #3 Minami

process.stdin.on('data', function (chunk) {
    var lines = chunk.toString().split('\n').map(function(line) {
        return line.trim();
    });
    var columns = [];
    var info = lines.shift().split(' ');
    var columnSize = info[0], 
        rowSize = info[1];

    for(var i = 0; i < columnSize; i++) {
        columns[i] = [];
    }

    var pushUnexplodedBomb = function(value, index) {
        if (value === "1") {
            columns[index].push(value);
        }
    }

    for(i = 0; i < rowSize; i++) {
        data = lines[i].split(' ');
        data.forEach(pushUnexplodedBomb);
    }

    for(i = rowSize - 1; i >= 0; i--) {
        result = ''
        for(var j = 0; j < columnSize; j++) {
            result += (columns[j][i] ? columns[j][i] : '0') + ' ';
        }
        console.log(result.trim());
    }

});

Mission #3 Rena

process.stdin.on('data', function (chunk) {
    var lines = chunk.toString().split('\n');
    var info = lines.shift().split(' ');
    var rowSize = info[0], 
            columnSize = info[1],
            rangeSize = info[2];
    
    var table = [], ranges = [];
    var decrement = function(value) {
        return value - 1;
    };

    for(var i = 0; i < lines.length; i++) {
        if (i < columnSize) {
            table.push(lines[i].split(' '));
        } else {
            ranges.push(lines[i].split(' ').map(decrement));
        }
    }
    
    var result = 0;
    var cache = '';
    
    for(i = 0; i < ranges.length; i++) {
        var x1 = ranges[i][0], y1 = ranges[i][1], x2 = ranges[i][2], y2 = ranges[i][3];

        for(var j = y1; j <= y2; j++) {
            for(var k = x1; k <= x2; k++) {
                var coordinate = '(' + k + ',' + j + ')';

                if (cache.indexOf(coordinate) === -1) {
                    result += +table[j][k];
                    cache += coordinate;
                }
            }
        }
    }
    
    console.log(result);
});

エクストラステージ の15パズル解く奴はマンハッタン距離を評価関数にした最良優先探索とか反復深化で探索とかしようとして書いたけど途中でループしてうまくいかなかった。
ゴールデンウィークだけどプロセッサを書かないといけなかったりレポートを書かないといけなかったりでいろいろ忙しいのでいろいろが片付いたらまた書きなおしたい。

Livetube Notifier v1.4.2 公開しました。 chrome.runtime.onInstalled の発火タイミングを間違えてた話

概要

  • データが初期化されることがあるバグを修正しました。

ミスったこと

前回のアップデートでストレージしておくデータ(ワードや各種オプション)のフォーマットを変えたとき

chrome.runtime.onInstalled.addListener(function() {
    if(旧形式データ) {
        新データ = formatter(旧データ);
        新データを保存;
        旧データを破棄;
    } else {
        新データ = initializeData();
    }
});

だいたいこんな感じの書き方をしてしまったんだけど, chrome.runtime.onInstalledchrome 本体のアップデートでも発火するのを見落としてたので, chrome のアップデートのたびにデータが初期化されるみたいになってた。気を付けたい。。

paiza Online Hackathon #5

paiza.jp

これやった。競技プログラミングっぽい感じがするけど入門者向けという感じで簡単に解ける。

競技プログラミングっぽいというのはイメージで実際に競技プログラミングの問題を見たことはないです。

Mission 01

なんとなく JavaScript を選んだ。

process.stdin.on('data', function (chunk) {
    var line = chunk.toString();
        console.log(line.split('').filter(function(val, index, array) {
            return (index % 2 === 0) ? true : false;
        }).join(''));
});

素直に解ける

f:id:sekai013:20150423025630p:plain

Mission02

JavaScript で書いたけど出力がうまくいってない気がしたので Ruby で書き直した。

line_number = gets.to_i
result = [0] * 7

(0...line_number).each do |index|
    result[index % 7] += gets.to_i
end

puts result

さくさく解ける

f:id:sekai013:20150423025704p:plain

Mission03

Mission03 でミナミルートとレナルートに分岐する。ぼくはミナミ派ですが両方解きました。

ミナミルート

column, row = gets.split(' ').map {|v| v.to_i}

columns = []
(0...column).each {|n|
    columns[n] = []
}

(0...row).each {|n|
    input = gets.split(' ').map {|v| v.to_i}
    input.each_with_index {|value, index|
        if value != 2
            columns[index].push value
        end
    }
}

columns.each_with_index {|column_array, index|
    columns[index] = [0] * (row - column_array.size) + column_array
}

(0...row).each do |n|
    result = ''

    columns.each {|column_array|
        result += "#{column_array[n]} "
    }
    puts result.chop
end

どんどん解ける

f:id:sekai013:20150423025721p:plain

レナルート

column_count, row_count, range_count = gets.split(' ').map{|v| v.to_i}

table = []
(0...row_count).each {|n|
    row = gets.split(' ').map{|v| v.to_i}
    table.push row
}

cache = ''
result = 0

(0...range_count).each {|n|
    x_1, y_1, x_2, y_2 = gets.split(' ').map{|v| v.to_i}
    
    (x_1..x_2).each {|x|
        (y_1..y_2).each {|y|
            if cache.include? "(#{x},#{y})"
                next
            else
                cache += "(#{x},#{y}) "
                result += table[y-1][x-1]
            end
        }
    }
}
puts result

バンバン解ける

f:id:sekai013:20150423025803p:plain

適当にキャッシュっぽいのを作った。2次元配列 table のインデックスと指定される座標が1ずれてるのに注意した。

書ける人はどれくらいのタイム出せるものなんだろう。

エクストラステージもある。

paiza.jp

15パズル解くやつ。ヒューリスティック関数とかの話を今大学で聞いてるのでやってみたい。

あとがき

1問目を慣れてるJSで書いたせいでミスって JavaScript の答案としてこの記事が取り上げられてしまったので全部JSで書き直した。

paiza Online Hackathon #5 in JavaScript - sekai013's blog

KSNCTF #26 Sherlock Holmes

問題

ksnctf - 26 Sherlock Holmes

考えたこと

英語がつらつら書いてあるのはドイルの『ボヘミアの醜聞』。昔読んだと思うけど記憶が消えた。

www.221b.jp

最初は I から III までざっと眺めておかしいところがないか探してみたけどそういうことではなさそうだった。

トップに戻ると index.pl が動いてることに気づく。PerlCGI というだけで脆弱性があるような気がする。
index.pl/foo.barfoo.bar というファイルを開いてるっぽいので適当に探せば旗見つかる気がした。
試しに index.pl/flag.txt 見たら一発でファイル存在した。ちょろw

と思ったけど、旗取れなくて、まずは index.pl 本体を見ろと怒られた。
確かに flag.txt が存在するであろうということは KSNCTF を今まで解いてきたからわかることであって、そんなメタではその場しのぎにしかならない。反省しました。

改めて index.pl を読むと、 1行目に h@ck3d! と書かれてる cracked.txt が存在すれば旗取れるらしい。
どうしたもんかと思ったけど、「perl cgi 脆弱性」 でググると一発で出てきた。

4-1. ファイルオープン時のパスにご用心

open 文に末尾が | の文字列を渡すと OS コマンドが実行されるというかなりダメそうな脆弱性があるということ。
echo "h@ck3d" > cracked.txt | で旗取れた。

OS コマンドインジェクションこわい。
適当に rm -rf / とかやっちゃうとどうなるのかなと思ったけど怖かったのでやってない。

KSNCTF #25 Reserved

問題

ksnctf - 25 Reserved

考えたこと

ぱっと見で単換字式暗号かなと思ったけど2ワード目が1文字な文はそんなになさそう。

よくみてると print とか eval, each とか見たことある言葉も結構ある。

この辺でタイトルに気付いて、問題文はプログラミング言語予約語から構成されてる気がした。

勉強したことない言語らしくてわからなかったので、たまたま目に入った getservbyname という長めの言葉でググれば見つかる気がした。

「getservbyname 予約語」 でググるとこんな記事が出てきた。

http://developer.cybozu.co.jp/takesako/2007/05/fizzbuzz.html

FizzbuzzPerl で書くという記事だけど、2番の ppencode バージョンというやつがまさに問題文と一緒!ppencode というのが怪しい。

ppencode - JAPH perl program encode

調べてみたところ perl のコードの難読化のやり方で、見たとおり予約語だけを使うということらしい。しゅごい。

難読化しただけなので普通に実行できる。問題文を適当に reserved.pl とかで保存して perl reserved.pl で旗取れる。

ちょっと日が開いてしまったのでソースを忘れてしまったけど、キモい FizzBuzz 書ける自慢みたいな感じで、Perl の世界にもある文字列をどうやって出力するかみたいな遊びがあるらしい。なるほど。

KSNCTF #31 KanGacha [わからん!!!!!!!!!!]

問題

ksnctf - 31 KanGacha

考えたこと

与えられてるソースにはだいたいこんなことが書いてる.

  • $salt: フラッグ.

  • $shipname : 大きさ11 の配列で $shipname[10]$salt が含まれてる.

  • 0..9 までの整数のなかからランダムにひとつ選ぶ.

  • ship: cookie. ランダムに選んだ整数をコンマ区切りで保存してる.

  • signature: cookie. $saltship を連結した文字列のSHA512ハッシュ.

  • $saltship を連結して暗号化したものと, signature が一致していれば, ship の各数字 n について $shipname[n] を出力する.

要は ship=10; signature=hogehoge という感じで cookie を作れればいいという話だと思うけど, 肝心の $salt がわからないと正しい signature がわからない.
shipsignature の組はたくさん手に入るけど SHA512 の前には無力!!!!死!!!!!!

と思ってググってたらこういう記事たちを見つけた.

Length extension attack っぽい.

未知の文字列 salt に対して hash(salt + hoge), hoge, salt.length が既知のとき任意の文字列 piyo に対して hash(salt + hoge + padding + piyo) を求められるというようなことが書いてある気がする.

とりあえず紹介されている Hashpump を導入して, ガチャを回して ship=1; signature=24b7447578c89ea8f5f8854d60e253f23bb5b8856d8a135c19af423db354ac60a1a4c932cecd800a0550211e8cc6e28e73e1ac93e7b9c786adc24702e48701c5 となることを確認して, 2つのブログ記事とか, もっと近そうな
write-ups-2014/plaid-ctf-2014/mtpox at master · ctfs/write-ups-2014 · GitHub とかを参考にしてコード書いたけど, 何回書いても通らない.

gist.github.com

これで $salt の長さを正しく指定してたら '1' + padding + ',10' とそれに対応する signature が得られて, ソース中の

hash('sha512', $salt.$_COOKIE['ship']) === $_COOKIE['signature']

を通過できて$shipname[10]が表示できると思うんだけど $salt の長さ1~500まで試しても上の条件を通過できていなかった.

さっぱりわからん・・・数ヶ月くらい考えては諦めしてていい加減投げたいけど方針間違ってない気がしててそれでも通らないの気持ち悪くて投げるに投げられない・・・

何かおかしいのはわかるけどわかるけど Length Extension Attack の問題の writeup 見てもこれと似たようなことをしていて何がおかしいのかわからん・・・しんどい・・・

KSNCTF #22 Square Cipher

問題

ksnctf - 22 Square Cipher

考えたこと

ぱっと見て縦に長かったのでほんとに正方形か?と思って調べたけど 31*31 の正方形だった。
31 ってなんだろうとか正方形のものってなんだろうと考えてみたけどわからなかった。

眺めてみると使われてる文字は a-zA-Z っぽい。大文字小文字がごちゃごちゃになってる。
各行の頭文字を見てたら大文字が含まれていないことに気付いた。もしかしてと思って1行目も見てみたら大文字が含まれていないことに気付いた。

もしかしたら

小小小...
小大大...
小大小...

って感じで小文字の層と大文字の層からできているのでは?と思ったけど、そんなことはなさそうだった。
でも外周に大文字が含まれてないのは気になったので、大文字だけハイライトしてみた。

f:id:sekai013:20150406220358p:plain

やったぜ。このまま読み込もうとしたけど当然だめだったので QR コードを生成してくれるようなコード書くことにした。

とりあえず、大文字か小文字かという情報だけが重要なので、さくっと小文字=0, 大文字=1 に直した。

:%s/[a-z]/0/g
:%s/[A-Z]/1/g

あとはこの01を元にしてなんとか画像を生成できるやろと思ってたけど、なかなかよさそうな方法が見つからなかった。
HTML5Canvas を使うのが一番楽そうだったのでそうした。

https://github.com/sekai013/ksnctf/tree/master/square_cipher

01のやつを貼り付けてボタン押すと QR コードを描くようにした。無事読み込めて旗取れた。Canvas 初めて見たけど面白かった。