paiza Online Hackathon #5 in JavaScript
これやったポスト が 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.onInstalled
が chrome 本体のアップデートでも発火するのを見落としてたので, chrome のアップデートのたびにデータが初期化されるみたいになってた。気を付けたい。。
paiza Online Hackathon #5
これやった。競技プログラミングっぽい感じがするけど入門者向けという感じで簡単に解ける。
競技プログラミングっぽいというのはイメージで実際に競技プログラミングの問題を見たことはないです。
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('')); });
素直に解ける
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
さくさく解ける
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
どんどん解ける
レナルート
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
バンバン解ける
適当にキャッシュっぽいのを作った。2次元配列 table
のインデックスと指定される座標が1ずれてるのに注意した。
書ける人はどれくらいのタイム出せるものなんだろう。
エクストラステージもある。
15パズル解くやつ。ヒューリスティック関数とかの話を今大学で聞いてるのでやってみたい。
あとがき
1問目を慣れてるJSで書いたせいでミスって JavaScript の答案としてこの記事が取り上げられてしまったので全部JSで書き直した。
KSNCTF #26 Sherlock Holmes
問題
考えたこと
英語がつらつら書いてあるのはドイルの『ボヘミアの醜聞』。昔読んだと思うけど記憶が消えた。
最初は I から III までざっと眺めておかしいところがないか探してみたけどそういうことではなさそうだった。
トップに戻ると index.pl
が動いてることに気づく。Perl の CGI というだけで脆弱性があるような気がする。
index.pl/foo.bar
で foo.bar
というファイルを開いてるっぽいので適当に探せば旗見つかる気がした。
試しに index.pl/flag.txt
見たら一発でファイル存在した。ちょろw
と思ったけど、旗取れなくて、まずは index.pl
本体を見ろと怒られた。
確かに flag.txt
が存在するであろうということは KSNCTF を今まで解いてきたからわかることであって、そんなメタではその場しのぎにしかならない。反省しました。
改めて index.pl
を読むと、 1行目に h@ck3d!
と書かれてる cracked.txt
が存在すれば旗取れるらしい。
どうしたもんかと思ったけど、「perl cgi 脆弱性」 でググると一発で出てきた。
open
文に末尾が |
の文字列を渡すと OS コマンドが実行されるというかなりダメそうな脆弱性があるということ。
echo "h@ck3d" > cracked.txt |
で旗取れた。
OS コマンドインジェクションこわい。
適当に rm -rf /
とかやっちゃうとどうなるのかなと思ったけど怖かったのでやってない。
KSNCTF #25 Reserved
問題
考えたこと
ぱっと見で単換字式暗号かなと思ったけど2ワード目が1文字な文はそんなになさそう。
よくみてると print
とか eval
, each
とか見たことある言葉も結構ある。
この辺でタイトルに気付いて、問題文はプログラミング言語の予約語から構成されてる気がした。
勉強したことない言語らしくてわからなかったので、たまたま目に入った getservbyname
という長めの言葉でググれば見つかる気がした。
「getservbyname 予約語」 でググるとこんな記事が出てきた。
http://developer.cybozu.co.jp/takesako/2007/05/fizzbuzz.html
Fizzbuzz を Perl で書くという記事だけど、2番の ppencode バージョンというやつがまさに問題文と一緒!ppencode というのが怪しい。
ppencode - JAPH perl program encode
調べてみたところ perl のコードの難読化のやり方で、見たとおり予約語だけを使うということらしい。しゅごい。
難読化しただけなので普通に実行できる。問題文を適当に reserved.pl
とかで保存して perl reserved.pl
で旗取れる。
ちょっと日が開いてしまったのでソースを忘れてしまったけど、キモい FizzBuzz 書ける自慢みたいな感じで、Perl の世界にもある文字列をどうやって出力するかみたいな遊びがあるらしい。なるほど。
KSNCTF #31 KanGacha [わからん!!!!!!!!!!]
問題
考えたこと
与えられてるソースにはだいたいこんなことが書いてる.
$salt
: フラッグ.$shipname
: 大きさ11 の配列で$shipname[10]
に$salt
が含まれてる.0..9 までの整数のなかからランダムにひとつ選ぶ.
ship
: cookie. ランダムに選んだ整数をコンマ区切りで保存してる.signature
: cookie.$salt
とship
を連結した文字列のSHA512ハッシュ.$salt
とship
を連結して暗号化したものと,signature
が一致していれば,ship
の各数字 n について$shipname[n]
を出力する.
要は ship=10; signature=hogehoge
という感じで cookie を作れればいいという話だと思うけど, 肝心の $salt
がわからないと正しい signature
がわからない.
ship
と signature
の組はたくさん手に入るけど 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 とかを参考にしてコード書いたけど, 何回書いても通らない.
これで $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
問題
考えたこと
ぱっと見て縦に長かったのでほんとに正方形か?と思って調べたけど 31*31 の正方形だった。
31 ってなんだろうとか正方形のものってなんだろうと考えてみたけどわからなかった。
眺めてみると使われてる文字は a-zA-Z っぽい。大文字小文字がごちゃごちゃになってる。
各行の頭文字を見てたら大文字が含まれていないことに気付いた。もしかしてと思って1行目も見てみたら大文字が含まれていないことに気付いた。
もしかしたら
小小小...
小大大...
小大小...
って感じで小文字の層と大文字の層からできているのでは?と思ったけど、そんなことはなさそうだった。
でも外周に大文字が含まれてないのは気になったので、大文字だけハイライトしてみた。
やったぜ。このまま読み込もうとしたけど当然だめだったので QR コードを生成してくれるようなコード書くことにした。
とりあえず、大文字か小文字かという情報だけが重要なので、さくっと小文字=0, 大文字=1 に直した。
:%s/[a-z]/0/g :%s/[A-Z]/1/g
あとはこの01を元にしてなんとか画像を生成できるやろと思ってたけど、なかなかよさそうな方法が見つからなかった。
HTML5 の Canvas を使うのが一番楽そうだったのでそうした。
https://github.com/sekai013/ksnctf/tree/master/square_cipher
01のやつを貼り付けてボタン押すと QR コードを描くようにした。無事読み込めて旗取れた。Canvas 初めて見たけど面白かった。