2016-09-05

Tokyo Westerns/MMA CTF 2nd 2016 write-up

ちょくちょくできないなりにCTF参加してるけど、記録を残さないと自分でも忘れてしまうので。
Web系が一つもできないのはつらい。アセンブリ読むの好きといいつつPwnも全然ダメ。このあたりができればもっと楽しいのだろうなぁ。

[Misc] [Warmup] Welcome!! (10pt)

問題文に書いてあるのを入れるだけ。

[Pwn] [Warmup] judgement (50pt)

printfの第一引数に入力が渡っている。スタック上に残っているflagのポインタを読むように"%28$s"を渡してやればよい。

[PPC] [Warmup] Make a Palindrome! (20pt / 30pt)

10! = 3628800通り全部試しても3分の時間制限に間に合う。

[Crypto] [Warmup] Twin Primes (50pt)

p*qと(p+2)*(q+2)が与えられるので、p+qが求まって、解と係数の関係でpとqがわかってしまう。あとはencrypt.pyの逆の手順をたどればよい。

[Reverse] [Warmup] Reverse Box (50pt)

とりあえず動かしてみると、実行ごとに同じ入力でも出力が変わるが、一回の実行中に同じ文字には同じ出力しか出ない雰囲気。rand(3)を使っているところが初期化の一箇所だけで、しかも下位8bitしか使われない。rand(3)をLD_PRELOADでフックして256通りの値を試すと、TWCTFが問題文に書かれた出力になるのはrand(3)が214を返すとき。あとは換字表を作って変換すればよい。

[Crypto] Super Express (100pt)

ごちゃごちゃやっているけど結局入力の線形変換になるので、先頭をTWCTFとしたときの変換式を求めてデコードする。

[Crypto] Backpacker's cipher - easy mode (200pt)

pとqがわかったときにどうdecryptするか考える。mod p上でpubkeyの各要素をqで割ると、pubkeyのi番目の値は下から見てiビット目で初めて1が立つ値になる。messageをqで割ったものについて、下から順に1が立っているかどうかをチェックし、1が立っているときにpubkeyをqで割ったものを引くようにすると、DESで暗号化したビット列が得られる。
generate_keyのaの作り方から、pubkeyの最後の要素は2^1023*q%p、その一個前の要素は2^1022*q%pまたは3*2^1022*q%p。前者の場合にpが312桁の素数になってそれっぽい。2^1023の逆数を掛ければqも求まる。

[Crypto] Vigenere Cipher (200pt)

ASCIIのplain textをBase64 エンコードしているので、必ず0が来るビットがある。全文についてこの性質が成り立つことを利用すると、keyの要素は繰り返し使われるので、keyの長さや範囲を絞ることができる。
この時点でkeyの長さが12、そのうち8要素はほぼ中身が確定するので、一度元の文字列らしきものを出してみると、最後のほうにflag is TWCTF{という文字列が来そうなので、残りのkeyも確定できる。

[Reverse] [PPC] Whiteout Mathmatics (200pt)

Whitespaceのプログラムを読むと、与えられた数値の間の各数について約数の和を求め、それの最大値を出力することがわかる。要は10^12までの数で約数の和が最大になる数の、その約数の和を答えればよい。
どうせそのような概念は既にあるだろうと約数のWikipediaを眺めたら、高度過剰数という概念がありOEIS経由でテーブルにたどりつけた。あとは995886571680をfactorして約数の和を求めればよい。

[PPC] Lights Out! (100pt / 300pt)

各マスを縦に、押したときに変化するマスを横にとった行列を作って、GF(2)上でAx=bを解けばよい。normalはガウス消去で十分速い。
lunaticはできていない。O(N^3)だと死んでしまうので、疎行列であることを利用して反復法で解くのかなとか考えていた。素因数分解でblock Lanczos法を使うように。

[Misc] glance (50pt)

情弱なのでWindows上でフリーソフトでGIFを分解してBMPにしたのち、BMPのフォーマットを参考にしつつ各行を順に結合して新しいBMPを吐くプログラムを書いた。もう少し楽なやり方があったかもしれない。

[Misc] ninth (100pt)

zlibでIDATの中身をinflateすると、画像データのあとにflagが書いてあった。

2015-06-02

Piet golfでハマる

npiet(1.3d時点)のGIF周りのバグや未実装機能など。全ピクセルを愚直に圧縮せず、末端(最終行など右下方面)は書かないというのがゴルフ的な手法だが、ハマリポイントだった。

まず、npietはGIFのimage部分しか見ていないため、Background Color Indexは無視される。GIFの規格を読んだ感じでは、imageが割り当たっていないpixelの色はBackground Colorで塗りつぶされるらしいので、Pietコードをterminateさせるために作るL字領域の作成に便利なのだが。

次に、エンコードされたピクセル数が一行の幅に足りない場合。GIFLIBはエラーを返すが、npietはそれを握りつぶしている(握りつぶしてくれなかったら大変だ)。このとき足りなかったピクセルはnpietが用意した状態のままで、color index 0が埋まった状態になっているようだ。mallocしただけの領域なので、理屈の上では他の値になってもおかしくないが、ヒープの末端かどこかのサラピンの領域がもらえているのかな。なので、color tableを作るときに、image末端のエンコードをサボる部分の色をcolor index 0にする必要がある。

さらにこれに関連してハマるポイントとして、ある行でピクセル数が足りずエラーが返ると、GIFLIBの内部ステート(ピクセルスタック)が変な状態で止まってしまい、次の行をnpietが処理したときに、先頭に(color index 0でなく)ゴミが描かれる場合がある。ゴミの正体は、複数ピクセルを表すコードを使ったときにエラーが返った行の上の行からエラーが返った行に持ち越したピクセル(長い)。たとえば以下の絵でいうと、右上のnB nRを一語にエンコードして、かつ、xxの部分で終了するようなソースコードを書いた場合、zzの部分はyy同様color index 0の色で塗られることを期待するが、実際はxxの行に持ち越したnRで塗られてしまう。

.. .. .. .. nB
nR .. xx yy yy
zz yy yy yy yy

2012-07-30

最近のあなごる

約四年ぶりに書いてみる。あなごるは321. add_sub_brainfuck_code以来二年ぶり。

590. Time Arithmetic

時間の足し算をする問題。64bitに8文字まとめてとって演算してからごにょごにょすることを考えたが、6進や10進ではビット演算が使えない上に、24進の処理に困ることが容易にわかったので諦めて、time_t的な何かにして足し算する方針に。この時点でこのあたりはライブラリ関数に任せたほうが短いと思い込んで、出力はstrftimeかなぁと思いつつctimeのmanを眺める。

strptime->mktime->足し算->gmtime->strftimeでchar[8]->int[9]->time_t->int[9]->char[8]と変化するコード。Cだとstruct tm(=int[9])とtime_tがあって面倒。

k[9];p;
t(){mktime(k,p=strptime(p,"%T+",k));}
main(b,c){
  for(k[5]=40;gets(p=&c);){
    b=t()+t()-21600;
    strftime(k,9,"%T",gmtime(&b));printf("%s=%s\n",&c,k);
  }
}

特筆すべきポイントは、k[5]=40でstruct tmのtm_yearに値を入れているところ。これがないとmktimeが発狂して-1を返す。あと、UTC+9環境なので、時刻をずらすための補正が必要で、変な項が増えている。cでなく&cになっているのは、ライブラリ関数で環境変数を読む関係だったはず。

time_tからダイレクトにchar*にできるctimeを使えないか考えると、printfのフォーマットを使ってできることがわかる。これで締め切り前の122Bにだいぶ近いのだけど、ここから環境依存で詰める。不毛で楽しい作業。

p;
t(k){mktime(k,p=strptime(p,"%T+",k=&p-39));}
main(c){for(;gets(p=&c);printf("%s=%.8s\n",&c,ctime(&p)+11))p=t()+t()+9104;}

struct tmの初期化を嫌って、あらかじめtm_yearっぽい値が書かれているところを使う。手元の環境では39でなく38だった。補正項の9104は、time_tの和がオーバーフローする関係。3600の倍数でない意外性があってテンションが上がる。

と、ここまでがんばって、フタを開けてみると、この問題の最短を競い合ってきたkouさんのコードの入力処理の短さにびっくり。struct tm経由はやはり長かった。ループの終了条件など甘いところを詰めて、出力部分だけ自分のコードを使って115Bにたどりついた。

うーん、ライブラリ関数が短いと思い込んだ以前に、最初に二つに分けて処理しようとした時点でまずかったらしい。

593. fill dots

55B解に至ったところで出力文字を決めるロジックに無駄が見えなくなってしまって、これ以上無理に思えていたけれど、まだ制御部が短くなって53B。よく見たら典型的なパタンだった。

600. Regular polygon

%.fで出すだけかと思ったら-0に苦労する問題。負の値ならマイナスを出してもしょうがない。PI/2と3PI/2で両方正の値を出すためには、PIの値を変えてもだめで、答えを少しずらしてやらないといけない。マクロ関数の括弧のあとのスペースが要らないのは知っていたけれど、名前の直後に単項演算子が来てもいいのは初めて知った。

nn(kou)さんの84Bが美しすぎる。たしかに、これでうまくいくなぁ。

602. the same ArrayA as ArrayB

入力が弱い。埋め込みに見えるが敢えてxor+αか、とも思ったけれども、歴戦のあなごる戦士にチート的発想で勝てる気がしなかったのでパス。

598. ICUP

アツい。ここまで短くなるとは思っていなかった。

最初の観察で、番号順に見たときに左の人からの距離は広義単調減少するものの1/2にしていくだけではだめなことがわかったので、最大値から距離を減らしていくことにした。最初は、出力用の数値と次に数値が入っている要素までの距離のペアを持つ形式で230B。

a[99];b[99];
main(i,k,N,d){
  for(;~scanf("%d",&N);){
    printf("%d:",N);
    for(k=a[*b=d=N-1]=N>2?2:0,*a=1;d>1;d--){
      for(i=0;i<N;i++){
        b[i]>=d*2?b[i+d]=b[i]-d,b[i]=d,a[i+d]=++k:0;
      }
    }
    for(i=0;i<N;i++){
      a[i]=b[i]=!printf(a[i]?" %d":" _",a[i]);
    }
    puts("");
  }
}

全体的に無駄が多いけれども、あなごるのトレンドとしては、とりあえずvprintf使うべきというところだろうか。

ロジックで何が悪いのか考えると、右端の2のための処理と、空白距離テーブルの更新に手間がかかっている。forが一つ増えるが、数値の配列をなめたほうがマシ。

a[99];
main(N,d,p,x,k,i){
  for(;*a=x=~scanf("%d",&N);){
    for(d=N;--d;){
      for(p=1;++p<N;){
        for(k=i=N;i--;){
          k*=abs(p-i)>d|!a[i];
        }
        k?a[p]=--x:0;
      }
    }
    printf("%d:",N);
    for(i=0;i<N;i++){
      a[i]=!printf(a[i]?" %d":" _",~a[i]);
    }
    puts("");
  }
}

配列の中身が負論理(?)になっている。absがカッコ悪いが198B。200Bを切って喜んでsubmitしたら、直前にushたんが195Bでトップならず。

その後の展開は以下のとおり。

// AC 196B
a[];main(N,d,p,x,k,i){for(;x=~scanf("%d",&N);puts("")){for(*a=~N,d=N;--d;)for(p=1;++p<N;k?a[p]=--x:0)for(k=i=N;i--;)k*=abs(p-i)>d|!a[i];for(;d<N;)a[d++]=!printf(d?a[d]?" %d":" _":"%d: 1",~a[d]);}}

// AC 193B
a[];main(N,d,p,x,k,i){for(;x=~scanf("%d",&N);puts(""))for(*a=d=~N;++d<N;)d>=0?a[d]=!printf(d?a[d]?" %d":" _":"%d: 1",~a[d]):({for(p=1;++p<N;k?a[p]=--x:0)for(k=i=N;i--;)k*=abs(p-i)>-d|!a[i];});}

// AC 192B
a[];main(N,d,p,x,k,i){for(;x=~scanf("%d",&N);puts(""))for(*a=d=~N;++d<N;d<0||printf(d?a[d]?a[d]=0," %d":" _":"%d: 1",~a[d]))for(p=1;++p<N;d*k<0?a[p]=--x:0)for(k=i=N;i--;)k*=abs(p-i)>-d|!a[i];}

// AC 191B
a[];main(N,d,p,x,k,i){for(;x=~scanf("%d",&N);puts(""))for(*a=d=~N;p=++d<N;d<0||printf(d?a[d]?a[d]=0," %d":" _":"%d: 1",~a[d]))for(;++p<N;d*k<0?a[p]=--x:0)for(k=i=N;i--;)k*=abs(p-i)>-d|!a[i];}

// AC 190B
a[];main(N,d,p,x,k,i){for(;x=~scanf("%d",&N);puts(""))for(*a=d=~N;p=++d<N;d<0||printf(d?a[d]?a[d]=0," %d":" _":"%d: 1",~a[d]))for(;d<0&++p<N;k?a[p]=--x:0)for(k=i=N;i--;)k*=(p-i)/~-d||!a[i];}

// AC 189B
a[];main(N,d,p,x,k,i){for(;x=~scanf("%d",&N);puts(""))for(*a=d=~N;p=++d<N;d<0||printf(d?a[d]?a[d]=0," %d":" _":"%d: 1",~a[d]))for(;d<-1&++p<N;k?a[p]=--x:0)for(k=i=N;i--;)k*=(p-i)/d||!a[i];}

printfをひとつにまとめて、生成と出力を一つのforで処理するようにして、absのところを除算にして、(ここでpost mortem)

// AC 184B
a[];main(N,d,p,x,k,i){for(;x=~scanf("%d",&N);puts(""))for(*a=d=~N;p=++d<N;d<0||printf(d?a[d]?a[d]=0," %d":" _":"%d: 1",~a[d]))for(;d<-1&++p<N;k?a[p]=--x:0)for(k=i=d;++i+d;)k*=!a[p+i];}

// AC 177B
a[];main(N,d,p,x,i){for(;x=~scanf("%d",&N);puts(""))for(*a=d=~N;p=++d<N;d<0||printf(d?a[d]?a[d]=0," %d":" _":"%d: 1",~a[d]))for(;d<-1&++p<N;i/d?a[p]=--x:0)for(i=-d;!a[p+--i];);}

// AC 176B
a[];main(N,d,p,x,i){for(;x=~scanf("%d",&N);puts(""))for(*a=d=~N;p=++d<N;d<0||printf(d?a[d]?a[d]=0," %d":" _":"%d: 1",~a[d]))for(;d<-1&++p<N;i/d?a[p]=--x:0)for(i=d;!a[p-++i];);}

// AC 175B
a[];main(N,d,p,x,i){for(;x=~scanf("%d",&N);puts(""))for(*a=d=~N;p=++d<N;)for(;d<0?++p<N:!printf(d?a[d]?a[d]=0," %d":" _":"%d: 1",~a[d]);i>-d?a[p]=--x:0)for(i=d-1;!a[p-++i];);}

// AC 174B
a[];main(N,d,p,x,i){for(;x=~scanf("%d",&N);puts(""))for(*a=d=~N;p=++d<N;)for(;d<0?++p<N:!printf(d?a[d]?a[d]=0," %d":" _":"%d: 1",~a[d]);i>1-d?a[p]=--x:0)for(i=d;!a[p-i++];);}

// AC 173B
a[];main(x,N,d,p,i){for(;~scanf("%d",&N);x=puts(""))for(*a=d=N;p=--d>-N;)for(;d>0?++p<N:!printf(d?i?a[-d]=0," %d":" _":"%d: 1",i=a[-d]);i<~d?a[p]=++x:0)for(i=d;!a[p+i--];);}

// AC 174B
*b,a[];main(x,N,d,p,i){for(;~scanf("%d",&N);x=puts(""))for(*a=d=N;p=--d>-N;)for(b=a-d;d>0?++p<N:!printf(d?*b?*b=0," %d":" _":"%d: 1",*b);i<~d?a[p]=++x:0)for(i=d;!a[p+i--];);}

// AC 167B
*p,a[];main(x,N,d,i){for(;~scanf("%d",&N);x=puts(""))for(*a=d=N;--d+N;)for(p=a-d;d>0?++p<a+N:!printf(d?*p?*p=0," %d":" _":"%d: 1",*p);i<~d?*p=++x:0)for(i=d;!p[i--];);}

// AC 166B
*p,a[];main(x,N,d,i){for(;gets(a);x=puts(""))for(*a=d=N=atoi();--d+N;)for(p=a-d;d>0?++p<a+N:!printf(d?*p?*p=0," %d":" _":"%d: 1",*p);i<~d?*p=++x:0)for(i=d;!p[i--];);}

absだったところを番兵つきのループに変えて(a[0]で必ず引っかかる)、生成対象の配列要素と出力対象の配列要素を同じポインタで指せるようにして、166Bに。

出力フォーマットのせいとかでなく長めのコードになる問題は、やれることがいろいろあって、短縮のしがいがあって、楽しい。

(追記)puts(a)にできるパターンに気づいていなかった。

// AC 163B
*p,a[];main(x,N,d,i){for(;gets(a);x=puts(a))for(*a=d=N=atoi();--d+N;)for(p=a-d;d<1?*p=!printf(d?*p?" %d":" _":"%d: 1",*p):++p<a+N;i<~d?*p=++x:0)for(i=d;!p[i--];);}

599. tritri fixed description

どこまで書いていいものか。子の文字を決める部分はエンコードも何もせずにいたって普通が短いような感触。制御部はmain再帰が有利なのかな。手元で動くのは114Bまでで、112Bは若干運ゲー入っているので微妙。同じ114Bでも、nnさんはスペースが入っているので、環境非依存のロジックでまだ縮む余地があるのかもしれない…。

(追記)ロジック変更で、運ゲー要素を排除して111B。

588. Palindromic formula

一文字ごとに分けた出力のコストや、12,13,14,23,34の生成コストが大きくて迷走していた。結局普通にやるのが短いのかな。

2008-08-10

PKU2503 Babelfish (2)

Ozyさんのところでコードが紹介されたので(http://d.hatena.ne.jp/Ozy/20080809#p1)、こちらも晒します。

2008-08-10

PKU1163 The Triangle

G++で最短をとれた記念。

解法

よくある問題なので簡単に書くと、ピラミッドの各点について、自分にたどりつくまでのコストの最大値を求めながらDP。短くするためには、一番最初に与えられるピラミッドの段数の処理を工夫する必要がある。たぶん、getsや場合分けで無視するより、三角形の内部の点だと思って計算して、最後に答えから段数を引いたほうが短い。

fmaxが大活躍するOzyさんのコードはこちら。http://d.hatena.ne.jp/Ozy/20070204#p1

コード

一昨年通した113BのGCCのコード。

nu4nu@hatena

Tokyo Westerns/MMA CTF 2nd 2016 write-up

[Misc] [Warmup] Welcome!! (10pt)

[Pwn] [Warmup] judgement (50pt)

[PPC] [Warmup] Make a Palindrome! (20pt / 30pt)

[Crypto] [Warmup] Twin Primes (50pt)

[Reverse] [Warmup] Reverse Box (50pt)

[Crypto] Super Express (100pt)

[Crypto] Backpacker's cipher - easy mode (200pt)

[Crypto] Vigenere Cipher (200pt)

[Reverse] [PPC] Whiteout Mathmatics (200pt)

[PPC] Lights Out! (100pt / 300pt)

[Misc] glance (50pt)

[Misc] ninth (100pt)

Piet golfでハマる

最近のあなごる

619. Alphabet texture

622. group elements

618. Bitwise Counting

最近のあなごる

608. GCD Again

609. Fixed Rows

606. Cross Product of two Strings

610. Similarity Expansion

15. Card Sharp

618. Bitwise Counting

最近のあなごる

590. Time Arithmetic

593. fill dots

600. Regular polygon

602. the same ArrayA as ArrayB

598. ICUP

599. tritri fixed description

588. Palindromic formula

PKU2503 Babelfish (2)

PKU1163 The Triangle

解法

コード